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 constexpr void init(uptr InitialCapacity = 0) { 23 Data = &LocalData[0]; 24 CapacityBytes = sizeof(LocalData); 25 if (InitialCapacity > capacity()) 26 reserve(InitialCapacity); 27 } 28 void destroy() { 29 if (Data != &LocalData[0]) 30 unmap(Data, CapacityBytes, 0, &MapData); 31 } 32 T &operator[](uptr I) { 33 DCHECK_LT(I, Size); 34 return Data[I]; 35 } 36 const T &operator[](uptr I) const { 37 DCHECK_LT(I, Size); 38 return Data[I]; 39 } 40 void push_back(const T &Element) { 41 DCHECK_LE(Size, capacity()); 42 if (Size == capacity()) { 43 const uptr NewCapacity = roundUpPowerOfTwo(Size + 1); 44 reallocate(NewCapacity); 45 } 46 memcpy(&Data[Size++], &Element, sizeof(T)); 47 } 48 T &back() { 49 DCHECK_GT(Size, 0); 50 return Data[Size - 1]; 51 } 52 void pop_back() { 53 DCHECK_GT(Size, 0); 54 Size--; 55 } 56 uptr size() const { return Size; } 57 const T *data() const { return Data; } 58 T *data() { return Data; } 59 constexpr uptr capacity() const { return CapacityBytes / sizeof(T); } 60 void reserve(uptr NewSize) { 61 // Never downsize internal buffer. 62 if (NewSize > capacity()) 63 reallocate(NewSize); 64 } 65 void resize(uptr NewSize) { 66 if (NewSize > Size) { 67 reserve(NewSize); 68 memset(&Data[Size], 0, sizeof(T) * (NewSize - Size)); 69 } 70 Size = NewSize; 71 } 72 73 void clear() { Size = 0; } 74 bool empty() const { return size() == 0; } 75 76 const T *begin() const { return data(); } 77 T *begin() { return data(); } 78 const T *end() const { return data() + size(); } 79 T *end() { return data() + size(); } 80 81 private: 82 void reallocate(uptr NewCapacity) { 83 DCHECK_GT(NewCapacity, 0); 84 DCHECK_LE(Size, NewCapacity); 85 NewCapacity = roundUp(NewCapacity * sizeof(T), getPageSizeCached()); 86 T *NewData = reinterpret_cast<T *>( 87 map(nullptr, NewCapacity, "scudo:vector", 0, &MapData)); 88 memcpy(NewData, Data, Size * sizeof(T)); 89 destroy(); 90 Data = NewData; 91 CapacityBytes = NewCapacity; 92 } 93 94 T *Data = nullptr; 95 T LocalData[256 / sizeof(T)] = {}; 96 uptr CapacityBytes = 0; 97 uptr Size = 0; 98 [[no_unique_address]] MapPlatformData MapData = {}; 99 }; 100 101 template <typename T> class Vector : public VectorNoCtor<T> { 102 public: 103 constexpr Vector() { VectorNoCtor<T>::init(); } 104 explicit Vector(uptr Count) { 105 VectorNoCtor<T>::init(Count); 106 this->resize(Count); 107 } 108 ~Vector() { VectorNoCtor<T>::destroy(); } 109 // Disallow copies and moves. 110 Vector(const Vector &) = delete; 111 Vector &operator=(const Vector &) = delete; 112 Vector(Vector &&) = delete; 113 Vector &operator=(Vector &&) = delete; 114 }; 115 116 } // namespace scudo 117 118 #endif // SCUDO_VECTOR_H_ 119