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 128