Home | History | Annotate | Line # | Download | only in sanitizer_common 
      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
    130