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
16namespace 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.
24template <typename T, size_t StaticNumEntries> class VectorNoCtor {
25public:
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 }
34 void push_back(const T &Element) {
35 DCHECK_LE(Size, capacity());
36 if (Size == capacity()) {
37 const uptr NewCapacity = roundUpPowerOfTwo(Size: Size + 1);
38 if (!reallocate(NewCapacity)) {
39 return;
40 }
41 }
42 memcpy(&Data[Size++], &Element, sizeof(T));
43 }
44 T &back() {
45 DCHECK_GT(Size, 0);
46 return Data[Size - 1];
47 }
48 void pop_back() {
49 DCHECK_GT(Size, 0);
50 Size--;
51 }
52 uptr size() const { return Size; }
53 const T *data() const { return Data; }
54 T *data() { return Data; }
55 constexpr uptr capacity() const { return CapacityBytes / sizeof(T); }
56 bool reserve(uptr NewSize) {
57 // Never downsize internal buffer.
58 if (NewSize > capacity())
59 return reallocate(NewCapacity: NewSize);
60 return true;
61 }
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
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
80protected:
81 constexpr void init(uptr InitialCapacity = 0) {
82 Data = &LocalData[0];
83 CapacityBytes = sizeof(LocalData);
84 if (InitialCapacity > capacity())
85 reserve(NewSize: InitialCapacity);
86 }
87 void destroy() {
88 if (Data != &LocalData[0])
89 ExternalBuffer.unmap();
90 }
91
92private:
93 bool reallocate(uptr NewCapacity) {
94 DCHECK_GT(NewCapacity, 0);
95 DCHECK_LE(Size, NewCapacity);
96
97 MemMapT NewExternalBuffer;
98 NewCapacity = roundUp(X: NewCapacity * sizeof(T), Boundary: getPageSizeCached());
99 if (!NewExternalBuffer.map(/*Addr=*/Addr: 0U, Size: NewCapacity, Name: "scudo:vector",
100 MAP_ALLOWNOMEM)) {
101 return false;
102 }
103 T *NewExternalData = reinterpret_cast<T *>(NewExternalBuffer.getBase());
104
105 memcpy(NewExternalData, Data, Size * sizeof(T));
106 destroy();
107
108 Data = NewExternalData;
109 CapacityBytes = NewCapacity;
110 ExternalBuffer = NewExternalBuffer;
111 return true;
112 }
113
114 T *Data = nullptr;
115 uptr CapacityBytes = 0;
116 uptr Size = 0;
117
118 T LocalData[StaticNumEntries] = {};
119 MemMapT ExternalBuffer;
120};
121
122template <typename T, size_t StaticNumEntries>
123class Vector : public VectorNoCtor<T, StaticNumEntries> {
124public:
125 static_assert(StaticNumEntries > 0U,
126 "Vector must have a non-zero number of static entries.");
127 constexpr Vector() { VectorNoCtor<T, StaticNumEntries>::init(); }
128 explicit Vector(uptr Count) {
129 VectorNoCtor<T, StaticNumEntries>::init(Count);
130 this->resize(Count);
131 }
132 ~Vector() { VectorNoCtor<T, StaticNumEntries>::destroy(); }
133 // Disallow copies and moves.
134 Vector(const Vector &) = delete;
135 Vector &operator=(const Vector &) = delete;
136 Vector(Vector &&) = delete;
137 Vector &operator=(Vector &&) = delete;
138};
139
140} // namespace scudo
141
142#endif // SCUDO_VECTOR_H_
143