1 //===-- 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 #ifndef SCUDO_VECTOR_H_ 10 #define SCUDO_VECTOR_H_ 11 12 #include "common.h" 13 14 #include <string.h> 15 16 namespace scudo { 17 18 // A low-level vector based on map. May incur a significant memory overhead for 19 // small vectors. The current implementation supports only POD types. 20 template <typename T> class VectorNoCtor { 21 public: 22 void init(uptr InitialCapacity = 0) { 23 Data = reinterpret_cast<T *>(&LocalData[0]); 24 CapacityBytes = sizeof(LocalData); 25 reserve(InitialCapacity); 26 } 27 void destroy() { 28 if (Data != reinterpret_cast<T *>(&LocalData[0])) 29 unmap(Data, CapacityBytes); 30 } 31 T &operator[](uptr I) { 32 DCHECK_LT(I, Size); 33 return Data[I]; 34 } 35 const T &operator[](uptr I) const { 36 DCHECK_LT(I, Size); 37 return Data[I]; 38 } 39 void push_back(const T &Element) { 40 DCHECK_LE(Size, capacity()); 41 if (Size == capacity()) { 42 const uptr NewCapacity = roundUpToPowerOfTwo(Size + 1); 43 reallocate(NewCapacity); 44 } 45 memcpy(&Data[Size++], &Element, sizeof(T)); 46 } 47 T &back() { 48 DCHECK_GT(Size, 0); 49 return Data[Size - 1]; 50 } 51 void pop_back() { 52 DCHECK_GT(Size, 0); 53 Size--; 54 } 55 uptr size() const { return Size; } 56 const T *data() const { return Data; } 57 T *data() { return Data; } 58 uptr capacity() const { return CapacityBytes / sizeof(T); } 59 void reserve(uptr NewSize) { 60 // Never downsize internal buffer. 61 if (NewSize > capacity()) 62 reallocate(NewSize); 63 } 64 void resize(uptr NewSize) { 65 if (NewSize > Size) { 66 reserve(NewSize); 67 memset(&Data[Size], 0, sizeof(T) * (NewSize - Size)); 68 } 69 Size = NewSize; 70 } 71 72 void clear() { Size = 0; } 73 bool empty() const { return size() == 0; } 74 75 const T *begin() const { return data(); } 76 T *begin() { return data(); } 77 const T *end() const { return data() + size(); } 78 T *end() { return data() + size(); } 79 80 private: 81 void reallocate(uptr NewCapacity) { 82 DCHECK_GT(NewCapacity, 0); 83 DCHECK_LE(Size, NewCapacity); 84 NewCapacity = roundUpTo(NewCapacity * sizeof(T), getPageSizeCached()); 85 T *NewData = 86 reinterpret_cast<T *>(map(nullptr, NewCapacity, "scudo:vector")); 87 memcpy(NewData, Data, Size * sizeof(T)); 88 destroy(); 89 Data = NewData; 90 CapacityBytes = NewCapacity; 91 } 92 93 T *Data = nullptr; 94 u8 LocalData[256] = {}; 95 uptr CapacityBytes = 0; 96 uptr Size = 0; 97 }; 98 99 template <typename T> class Vector : public VectorNoCtor<T> { 100 public: 101 Vector() { VectorNoCtor<T>::init(); } 102 explicit Vector(uptr Count) { 103 VectorNoCtor<T>::init(Count); 104 this->resize(Count); 105 } 106 ~Vector() { VectorNoCtor<T>::destroy(); } 107 // Disallow copies and moves. 108 Vector(const Vector &) = delete; 109 Vector &operator=(const Vector &) = delete; 110 Vector(Vector &&) = delete; 111 Vector &operator=(Vector &&) = delete; 112 }; 113 114 } // namespace scudo 115 116 #endif // SCUDO_VECTOR_H_ 117