1//===-- sanitizer_vector.h -------------------------------------*- C++ -*-===//
  2//
  3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4// See https://llvm.org/LICENSE.txt for license information.
  5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6//
  7//===----------------------------------------------------------------------===//
  8//
  9// This file is shared between sanitizers run-time libraries.
 10//
 11//===----------------------------------------------------------------------===//
 12
 13// Low-fat STL-like vector container.
 14
 15#ifndef SANITIZER_VECTOR_H
 16#define SANITIZER_VECTOR_H
 17
 18#include "sanitizer_common/sanitizer_allocator_internal.h"
 19#include "sanitizer_common/sanitizer_libc.h"
 20
 21namespace __sanitizer {
 22
 23template<typename T>
 24class Vector {
 25 public:
 26  Vector() : begin_(), end_(), last_() {}
 27
 28  ~Vector() {
 29    if (begin_)
 30      InternalFree(begin_);
 31  }
 32
 33  void Reset() {
 34    if (begin_)
 35      InternalFree(begin_);
 36    begin_ = 0;
 37    end_ = 0;
 38    last_ = 0;
 39  }
 40
 41  uptr Size() const {
 42    return end_ - begin_;
 43  }
 44
 45  T &operator[](uptr i) {
 46    DCHECK_LT(i, end_ - begin_);
 47    return begin_[i];
 48  }
 49
 50  const T &operator[](uptr i) const {
 51    DCHECK_LT(i, end_ - begin_);
 52    return begin_[i];
 53  }
 54
 55  T *PushBack() {
 56    EnsureSize(Size() + 1);
 57    T *p = &end_[-1];
 58    internal_memset(p, 0, sizeof(*p));
 59    return p;
 60  }
 61
 62  T *PushBack(const T& v) {
 63    EnsureSize(Size() + 1);
 64    T *p = &end_[-1];
 65    internal_memcpy(p, &v, sizeof(*p));
 66    return p;
 67  }
 68
 69  void PopBack() {
 70    DCHECK_GT(end_, begin_);
 71    end_--;
 72  }
 73
 74  void Resize(uptr size) {
 75    if (size == 0) {
 76      end_ = begin_;
 77      return;
 78    }
 79    uptr old_size = Size();
 80    if (size <= old_size) {
 81      end_ = begin_ + size;
 82      return;
 83    }
 84    EnsureSize(size);
 85    if (old_size < size) {
 86      internal_memset(&begin_[old_size], 0,
 87                      sizeof(begin_[old_size]) * (size - old_size));
 88    }
 89  }
 90
 91 private:
 92  T *begin_;
 93  T *end_;
 94  T *last_;
 95
 96  void EnsureSize(uptr size) {
 97    if (size <= Size())
 98      return;
 99    if (size <= (uptr)(last_ - begin_)) {
100      end_ = begin_ + size;
101      return;
102    }
103    uptr cap0 = last_ - begin_;
104    uptr cap = cap0 * 5 / 4;  // 25% growth
105    if (cap == 0)
106      cap = 16;
107    if (cap < size)
108      cap = size;
109    T *p = (T*)InternalAlloc(cap * sizeof(T));
110    if (cap0) {
111      internal_memcpy(p, begin_, cap0 * sizeof(T));
112      InternalFree(begin_);
113    }
114    begin_ = p;
115    end_ = begin_ + size;
116    last_ = begin_ + cap;
117  }
118
119  Vector(const Vector&);
120  void operator=(const Vector&);
121};
122}  // namespace __sanitizer
123
124#endif  // #ifndef SANITIZER_VECTOR_H