1 //===-- tsan_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 a part of ThreadSanitizer (TSan), a race detector. 11 // 12 //===----------------------------------------------------------------------===// 13 14 // Low-fat STL-like vector container. 15 16 #ifndef TSAN_VECTOR_H 17 #define TSAN_VECTOR_H 18 19 #include "tsan_defs.h" 20 #include "tsan_mman.h" 21 22 namespace __tsan { 23 24 template<typename T> 25 class Vector { 26 public: Vector(MBlockType typ)27 explicit Vector(MBlockType typ) 28 : typ_(typ) 29 , begin_() 30 , end_() 31 , last_() { 32 } 33 ~Vector()34 ~Vector() { 35 if (begin_) 36 internal_free(begin_); 37 } 38 Reset()39 void Reset() { 40 if (begin_) 41 internal_free(begin_); 42 begin_ = 0; 43 end_ = 0; 44 last_ = 0; 45 } 46 Size()47 uptr Size() const { 48 return end_ - begin_; 49 } 50 51 T &operator[](uptr i) { 52 DCHECK_LT(i, end_ - begin_); 53 return begin_[i]; 54 } 55 56 const T &operator[](uptr i) const { 57 DCHECK_LT(i, end_ - begin_); 58 return begin_[i]; 59 } 60 PushBack()61 T *PushBack() { 62 EnsureSize(Size() + 1); 63 T *p = &end_[-1]; 64 internal_memset(p, 0, sizeof(*p)); 65 return p; 66 } 67 PushBack(const T & v)68 T *PushBack(const T& v) { 69 EnsureSize(Size() + 1); 70 T *p = &end_[-1]; 71 internal_memcpy(p, &v, sizeof(*p)); 72 return p; 73 } 74 PopBack()75 void PopBack() { 76 DCHECK_GT(end_, begin_); 77 end_--; 78 } 79 Resize(uptr size)80 void Resize(uptr size) { 81 if (size == 0) { 82 end_ = begin_; 83 return; 84 } 85 uptr old_size = Size(); 86 EnsureSize(size); 87 if (old_size < size) { 88 for (uptr i = old_size; i < size; i++) 89 internal_memset(&begin_[i], 0, sizeof(begin_[i])); 90 } 91 } 92 93 private: 94 const MBlockType typ_; 95 T *begin_; 96 T *end_; 97 T *last_; 98 EnsureSize(uptr size)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*)internal_alloc(typ_, cap * sizeof(T)); 113 if (cap0) { 114 internal_memcpy(p, begin_, cap0 * sizeof(T)); 115 internal_free(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 __tsan 126 127 #endif // #ifndef TSAN_VECTOR_H 128