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> 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(Addr: ExternalBuffer.getBase(),
90 Size: ExternalBuffer.getCapacity());
91 }
92
93private:
94 bool reallocate(uptr NewCapacity) {
95 DCHECK_GT(NewCapacity, 0);
96 DCHECK_LE(Size, NewCapacity);
97
98 MemMapT NewExternalBuffer;
99 NewCapacity = roundUp(X: NewCapacity * sizeof(T), Boundary: getPageSizeCached());
100 if (!NewExternalBuffer.map(/*Addr=*/Addr: 0U, Size: NewCapacity, Name: "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[256 / sizeof(T)] = {};
120 MemMapT ExternalBuffer;
121};
122
123template <typename T> class Vector : public VectorNoCtor<T> {
124public:
125 constexpr Vector() { VectorNoCtor<T>::init(); }
126 explicit Vector(uptr Count) {
127 VectorNoCtor<T>::init(Count);
128 this->resize(Count);
129 }
130 ~Vector() { VectorNoCtor<T>::destroy(); }
131 // Disallow copies and moves.
132 Vector(const Vector &) = delete;
133 Vector &operator=(const Vector &) = delete;
134 Vector(Vector &&) = delete;
135 Vector &operator=(Vector &&) = delete;
136};
137
138} // namespace scudo
139
140#endif // SCUDO_VECTOR_H_
141

source code of compiler-rt/lib/scudo/standalone/vector.h