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: Vector()26 Vector() : begin_(), end_(), last_() {} 27 ~Vector()28 ~Vector() { 29 if (begin_) 30 InternalFree(begin_); 31 } 32 Reset()33 void Reset() { 34 if (begin_) 35 InternalFree(begin_); 36 begin_ = 0; 37 end_ = 0; 38 last_ = 0; 39 } 40 Size()41 uptr Size() const { 42 return end_ - begin_; 43 } 44 45 T &operator[](uptr i) { 46 DCHECK_LT(i, end_ - begin_); 47 return begin_[i]; 48 } 49 50 const T &operator[](uptr i) const { 51 DCHECK_LT(i, end_ - begin_); 52 return begin_[i]; 53 } 54 PushBack()55 T *PushBack() { 56 EnsureSize(Size() + 1); 57 T *p = &end_[-1]; 58 internal_memset(p, 0, sizeof(*p)); 59 return p; 60 } 61 PushBack(const T & v)62 T *PushBack(const T& v) { 63 EnsureSize(Size() + 1); 64 T *p = &end_[-1]; 65 internal_memcpy(p, &v, sizeof(*p)); 66 return p; 67 } 68 PopBack()69 void PopBack() { 70 DCHECK_GT(end_, begin_); 71 end_--; 72 } 73 Resize(uptr size)74 void Resize(uptr size) { 75 if (size == 0) { 76 end_ = begin_; 77 return; 78 } 79 uptr old_size = Size(); 80 if (size <= old_size) { 81 end_ = begin_ + size; 82 return; 83 } 84 EnsureSize(size); 85 if (old_size < size) { 86 for (uptr i = old_size; i < size; i++) 87 internal_memset(&begin_[i], 0, sizeof(begin_[i])); 88 } 89 } 90 91 private: 92 T *begin_; 93 T *end_; 94 T *last_; 95 EnsureSize(uptr size)96 void EnsureSize(uptr size) { 97 if (size <= Size()) 98 return; 99 if (size <= (uptr)(last_ - begin_)) { 100 end_ = begin_ + size; 101 return; 102 } 103 uptr cap0 = last_ - begin_; 104 uptr cap = cap0 * 5 / 4; // 25% growth 105 if (cap == 0) 106 cap = 16; 107 if (cap < size) 108 cap = size; 109 T *p = (T*)InternalAlloc(cap * sizeof(T)); 110 if (cap0) { 111 internal_memcpy(p, begin_, cap0 * sizeof(T)); 112 InternalFree(begin_); 113 } 114 begin_ = p; 115 end_ = begin_ + size; 116 last_ = begin_ + cap; 117 } 118 119 Vector(const Vector&); 120 void operator=(const Vector&); 121 }; 122 } // namespace __sanitizer 123 124 #endif // #ifndef SANITIZER_VECTOR_H 125