xref: /freebsd/contrib/llvm-project/compiler-rt/lib/scudo/standalone/vector.h (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583)
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 "mem_map.h"
13 
14 #include <string.h>
15 
16 namespace scudo {
17 
18 // A low-level vector based on map. It stores the contents inline up to a fixed
19 // capacity, or in an external memory buffer if it grows bigger than that. May
20 // incur a significant memory overhead for small vectors. The current
21 // implementation supports only POD types.
22 //
23 // NOTE: This class is not meant to be used directly, use Vector<T> instead.
24 template <typename T, size_t StaticNumEntries> class VectorNoCtor {
25 public:
26   T &operator[](uptr I) {
27     DCHECK_LT(I, Size);
28     return Data[I];
29   }
30   const T &operator[](uptr I) const {
31     DCHECK_LT(I, Size);
32     return Data[I];
33   }
push_back(const T & Element)34   void push_back(const T &Element) {
35     DCHECK_LE(Size, capacity());
36     if (Size == capacity()) {
37       const uptr NewCapacity = roundUpPowerOfTwo(Size + 1);
38       if (!reallocate(NewCapacity)) {
39         return;
40       }
41     }
42     memcpy(&Data[Size++], &Element, sizeof(T));
43   }
back()44   T &back() {
45     DCHECK_GT(Size, 0);
46     return Data[Size - 1];
47   }
pop_back()48   void pop_back() {
49     DCHECK_GT(Size, 0);
50     Size--;
51   }
size()52   uptr size() const { return Size; }
data()53   const T *data() const { return Data; }
data()54   T *data() { return Data; }
capacity()55   constexpr uptr capacity() const { return CapacityBytes / sizeof(T); }
reserve(uptr NewSize)56   bool reserve(uptr NewSize) {
57     // Never downsize internal buffer.
58     if (NewSize > capacity())
59       return reallocate(NewSize);
60     return true;
61   }
resize(uptr NewSize)62   void resize(uptr NewSize) {
63     if (NewSize > Size) {
64       if (!reserve(NewSize)) {
65         return;
66       }
67       memset(&Data[Size], 0, sizeof(T) * (NewSize - Size));
68     }
69     Size = NewSize;
70   }
71 
clear()72   void clear() { Size = 0; }
empty()73   bool empty() const { return size() == 0; }
74 
begin()75   const T *begin() const { return data(); }
begin()76   T *begin() { return data(); }
end()77   const T *end() const { return data() + size(); }
end()78   T *end() { return data() + size(); }
79 
80 protected:
81   constexpr void init(uptr InitialCapacity = 0) {
82     Data = &LocalData[0];
83     CapacityBytes = sizeof(LocalData);
84     if (InitialCapacity > capacity())
85       reserve(InitialCapacity);
86   }
destroy()87   void destroy() {
88     if (Data != &LocalData[0])
89       ExternalBuffer.unmap(ExternalBuffer.getBase(),
90                            ExternalBuffer.getCapacity());
91   }
92 
93 private:
reallocate(uptr NewCapacity)94   bool reallocate(uptr NewCapacity) {
95     DCHECK_GT(NewCapacity, 0);
96     DCHECK_LE(Size, NewCapacity);
97 
98     MemMapT NewExternalBuffer;
99     NewCapacity = roundUp(NewCapacity * sizeof(T), getPageSizeCached());
100     if (!NewExternalBuffer.map(/*Addr=*/0U, NewCapacity, "scudo:vector",
101                                MAP_ALLOWNOMEM)) {
102       return false;
103     }
104     T *NewExternalData = reinterpret_cast<T *>(NewExternalBuffer.getBase());
105 
106     memcpy(NewExternalData, Data, Size * sizeof(T));
107     destroy();
108 
109     Data = NewExternalData;
110     CapacityBytes = NewCapacity;
111     ExternalBuffer = NewExternalBuffer;
112     return true;
113   }
114 
115   T *Data = nullptr;
116   uptr CapacityBytes = 0;
117   uptr Size = 0;
118 
119   T LocalData[StaticNumEntries] = {};
120   MemMapT ExternalBuffer;
121 };
122 
123 template <typename T, size_t StaticNumEntries>
124 class Vector : public VectorNoCtor<T, StaticNumEntries> {
125 public:
126   static_assert(StaticNumEntries > 0U,
127                 "Vector must have a non-zero number of static entries.");
Vector()128   constexpr Vector() { VectorNoCtor<T, StaticNumEntries>::init(); }
Vector(uptr Count)129   explicit Vector(uptr Count) {
130     VectorNoCtor<T, StaticNumEntries>::init(Count);
131     this->resize(Count);
132   }
~Vector()133   ~Vector() { VectorNoCtor<T, StaticNumEntries>::destroy(); }
134   // Disallow copies and moves.
135   Vector(const Vector &) = delete;
136   Vector &operator=(const Vector &) = delete;
137   Vector(Vector &&) = delete;
138   Vector &operator=(Vector &&) = delete;
139 };
140 
141 } // namespace scudo
142 
143 #endif // SCUDO_VECTOR_H_
144