1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
//===-- vector.h ------------------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef SCUDO_VECTOR_H_
#define SCUDO_VECTOR_H_
#include "mem_map.h"
#include <string.h>
namespace scudo {
// A low-level vector based on map. It stores the contents inline up to a fixed
// capacity, or in an external memory buffer if it grows bigger than that. May
// incur a significant memory overhead for small vectors. The current
// implementation supports only POD types.
//
// NOTE: This class is not meant to be used directly, use Vector<T> instead.
template <typename T> class VectorNoCtor {
public:
T &operator[](uptr I) {
DCHECK_LT(I, Size);
return Data[I];
}
const T &operator[](uptr I) const {
DCHECK_LT(I, Size);
return Data[I];
}
void push_back(const T &Element) {
DCHECK_LE(Size, capacity());
if (Size == capacity()) {
const uptr NewCapacity = roundUpPowerOfTwo(Size + 1);
reallocate(NewCapacity);
}
memcpy(&Data[Size++], &Element, sizeof(T));
}
T &back() {
DCHECK_GT(Size, 0);
return Data[Size - 1];
}
void pop_back() {
DCHECK_GT(Size, 0);
Size--;
}
uptr size() const { return Size; }
const T *data() const { return Data; }
T *data() { return Data; }
constexpr uptr capacity() const { return CapacityBytes / sizeof(T); }
void reserve(uptr NewSize) {
// Never downsize internal buffer.
if (NewSize > capacity())
reallocate(NewSize);
}
void resize(uptr NewSize) {
if (NewSize > Size) {
reserve(NewSize);
memset(&Data[Size], 0, sizeof(T) * (NewSize - Size));
}
Size = NewSize;
}
void clear() { Size = 0; }
bool empty() const { return size() == 0; }
const T *begin() const { return data(); }
T *begin() { return data(); }
const T *end() const { return data() + size(); }
T *end() { return data() + size(); }
protected:
constexpr void init(uptr InitialCapacity = 0) {
Data = &LocalData[0];
CapacityBytes = sizeof(LocalData);
if (InitialCapacity > capacity())
reserve(InitialCapacity);
}
void destroy() {
if (Data != &LocalData[0])
ExternalBuffer.unmap(ExternalBuffer.getBase(),
ExternalBuffer.getCapacity());
}
private:
void reallocate(uptr NewCapacity) {
DCHECK_GT(NewCapacity, 0);
DCHECK_LE(Size, NewCapacity);
MemMapT NewExternalBuffer;
NewCapacity = roundUp(NewCapacity * sizeof(T), getPageSizeCached());
NewExternalBuffer.map(/*Addr=*/0U, NewCapacity, "scudo:vector");
T *NewExternalData = reinterpret_cast<T *>(NewExternalBuffer.getBase());
memcpy(NewExternalData, Data, Size * sizeof(T));
destroy();
Data = NewExternalData;
CapacityBytes = NewCapacity;
ExternalBuffer = NewExternalBuffer;
}
T *Data = nullptr;
uptr CapacityBytes = 0;
uptr Size = 0;
T LocalData[256 / sizeof(T)] = {};
MemMapT ExternalBuffer;
};
template <typename T> class Vector : public VectorNoCtor<T> {
public:
constexpr Vector() { VectorNoCtor<T>::init(); }
explicit Vector(uptr Count) {
VectorNoCtor<T>::init(Count);
this->resize(Count);
}
~Vector() { VectorNoCtor<T>::destroy(); }
// Disallow copies and moves.
Vector(const Vector &) = delete;
Vector &operator=(const Vector &) = delete;
Vector(Vector &&) = delete;
Vector &operator=(Vector &&) = delete;
};
} // namespace scudo
#endif // SCUDO_VECTOR_H_
|
