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