libsanitizer/sanitizer_common/sanitizer_vector.h

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