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