contrib/compiler-rt/lib/sanitizer_common/sanitizer_vector.h

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