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: Vector()27 explicit Vector() 28 : begin_() 29 , end_() 30 , last_() { 31 } 32 ~Vector()33 ~Vector() { 34 if (begin_) 35 InternalFree(begin_); 36 } 37 Reset()38 void Reset() { 39 if (begin_) 40 InternalFree(begin_); 41 begin_ = 0; 42 end_ = 0; 43 last_ = 0; 44 } 45 Size()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 PushBack()60 T *PushBack() { 61 EnsureSize(Size() + 1); 62 T *p = &end_[-1]; 63 internal_memset(p, 0, sizeof(*p)); 64 return p; 65 } 66 PushBack(const T & v)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 PopBack()74 void PopBack() { 75 DCHECK_GT(end_, begin_); 76 end_--; 77 } 78 Resize(uptr size)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 EnsureSize(uptr size)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