1//===- llvm/ADT/PagedVector.h - 'Lazily allocated' vectors --*- 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// This file defines the PagedVector class.
10//
11//===----------------------------------------------------------------------===//
12#ifndef LLVM_ADT_PAGEDVECTOR_H
13#define LLVM_ADT_PAGEDVECTOR_H
14
15#include "llvm/ADT/PointerIntPair.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/iterator_range.h"
18#include "llvm/Support/Allocator.h"
19#include <cassert>
20#include <vector>
21
22namespace llvm {
23/// A vector that allocates memory in pages.
24///
25/// Order is kept, but memory is allocated only when one element of the page is
26/// accessed. This introduces a level of indirection, but it is useful when you
27/// have a sparsely initialised vector where the full size is allocated upfront.
28///
29/// As a side effect the elements are initialised later than in a normal vector.
30/// On the first access to one of the elements of a given page, all the elements
31/// of the page are initialised. This also means that the elements of the page
32/// are initialised beyond the size of the vector.
33///
34/// Similarly on destruction the elements are destroyed only when the page is
35/// not needed anymore, delaying invoking the destructor of the elements.
36///
37/// Notice that this has iterators only on materialized elements. This
38/// is deliberately done under the assumption you would dereference the elements
39/// while iterating, therefore materialising them and losing the gains in terms
40/// of memory usage this container provides. If you have such a use case, you
41/// probably want to use a normal std::vector or a llvm::SmallVector.
42template <typename T, size_t PageSize = 1024 / sizeof(T)> class PagedVector {
43 static_assert(PageSize > 1, "PageSize must be greater than 0. Most likely "
44 "you want it to be greater than 16.");
45 /// The actual number of elements in the vector which can be accessed.
46 size_t Size = 0;
47
48 /// The position of the initial element of the page in the Data vector.
49 /// Pages are allocated contiguously in the Data vector.
50 mutable SmallVector<T *, 0> PageToDataPtrs;
51 /// Actual page data. All the page elements are allocated on the
52 /// first access of any of the elements of the page. Elements are default
53 /// constructed and elements of the page are stored contiguously.
54 PointerIntPair<BumpPtrAllocator *, 1, bool> Allocator;
55
56public:
57 using value_type = T;
58
59 /// Default constructor. We build our own allocator and mark it as such with
60 /// `true` in the second pair element.
61 PagedVector() : Allocator(new BumpPtrAllocator, true) {}
62 explicit PagedVector(BumpPtrAllocator *A) : Allocator(A, false) {
63 assert(A && "Allocator cannot be nullptr");
64 }
65
66 ~PagedVector() {
67 clear();
68 // If we own the allocator, delete it.
69 if (Allocator.getInt())
70 delete Allocator.getPointer();
71 }
72
73 // Forbid copy and move as we do not need them for the current use case.
74 PagedVector(const PagedVector &) = delete;
75 PagedVector(PagedVector &&) = delete;
76 PagedVector &operator=(const PagedVector &) = delete;
77 PagedVector &operator=(PagedVector &&) = delete;
78
79 /// Look up an element at position `Index`.
80 /// If the associated page is not filled, it will be filled with default
81 /// constructed elements.
82 T &operator[](size_t Index) const {
83 assert(Index < Size);
84 assert(Index / PageSize < PageToDataPtrs.size());
85 T *&PagePtr = PageToDataPtrs[Index / PageSize];
86 // If the page was not yet allocated, allocate it.
87 if (LLVM_UNLIKELY(!PagePtr)) {
88 PagePtr = Allocator.getPointer()->template Allocate<T>(PageSize);
89 // We need to invoke the default constructor on all the elements of the
90 // page.
91 std::uninitialized_value_construct_n(PagePtr, PageSize);
92 }
93 // Dereference the element in the page.
94 return PagePtr[Index % PageSize];
95 }
96
97 /// Return the capacity of the vector. I.e. the maximum size it can be
98 /// expanded to with the resize method without allocating more pages.
99 [[nodiscard]] size_t capacity() const {
100 return PageToDataPtrs.size() * PageSize;
101 }
102
103 /// Return the size of the vector.
104 [[nodiscard]] size_t size() const { return Size; }
105
106 /// Resize the vector. Notice that the constructor of the elements will not
107 /// be invoked until an element of a given page is accessed, at which point
108 /// all the elements of the page will be constructed.
109 ///
110 /// If the new size is smaller than the current size, the elements of the
111 /// pages that are not needed anymore will be destroyed, however, elements of
112 /// the last page will not be destroyed.
113 ///
114 /// For these reason the usage of this vector is discouraged if you rely
115 /// on the construction / destructor of the elements to be invoked.
116 void resize(size_t NewSize) {
117 if (NewSize == 0) {
118 clear();
119 return;
120 }
121 // Handle shrink case: destroy the elements in the pages that are not
122 // needed any more and deallocate the pages.
123 //
124 // On the other hand, we do not destroy the extra elements in the last page,
125 // because we might need them later and the logic is simpler if we do not
126 // destroy them. This means that elements are only destroyed when the
127 // page they belong to is destroyed. This is similar to what happens on
128 // access of the elements of a page, where all the elements of the page are
129 // constructed not only the one effectively needed.
130 size_t NewLastPage = (NewSize - 1) / PageSize;
131 if (NewSize < Size) {
132 for (size_t I = NewLastPage + 1, N = PageToDataPtrs.size(); I < N; ++I) {
133 T *Page = PageToDataPtrs[I];
134 if (!Page)
135 continue;
136 // We need to invoke the destructor on all the elements of the page.
137 std::destroy_n(Page, PageSize);
138 Allocator.getPointer()->Deallocate(Page);
139 }
140 }
141
142 Size = NewSize;
143 PageToDataPtrs.resize(NewLastPage + 1);
144 }
145
146 [[nodiscard]] bool empty() const { return Size == 0; }
147
148 /// Clear the vector, i.e. clear the allocated pages, the whole page
149 /// lookup index and reset the size.
150 void clear() {
151 Size = 0;
152 for (T *Page : PageToDataPtrs) {
153 if (Page == nullptr)
154 continue;
155 std::destroy_n(Page, PageSize);
156 // If we do not own the allocator, deallocate the pages one by one.
157 if (!Allocator.getInt())
158 Allocator.getPointer()->Deallocate(Page);
159 }
160 // If we own the allocator, simply reset it.
161 if (Allocator.getInt())
162 Allocator.getPointer()->Reset();
163 PageToDataPtrs.clear();
164 }
165
166 /// Iterator on all the elements of the vector
167 /// which have actually being constructed.
168 class MaterializedIterator {
169 const PagedVector *PV;
170 size_t ElementIdx;
171
172 public:
173 using iterator_category = std::forward_iterator_tag;
174 using value_type = T;
175 using difference_type = std::ptrdiff_t;
176 using pointer = T *;
177 using reference = T &;
178
179 MaterializedIterator(PagedVector const *PV, size_t ElementIdx)
180 : PV(PV), ElementIdx(ElementIdx) {}
181
182 /// Pre-increment operator.
183 ///
184 /// When incrementing the iterator, we skip the elements which have not
185 /// been materialized yet.
186 MaterializedIterator &operator++() {
187 ++ElementIdx;
188 if (ElementIdx % PageSize == 0) {
189 while (ElementIdx < PV->Size &&
190 !PV->PageToDataPtrs[ElementIdx / PageSize])
191 ElementIdx += PageSize;
192 if (ElementIdx > PV->Size)
193 ElementIdx = PV->Size;
194 }
195
196 return *this;
197 }
198
199 MaterializedIterator operator++(int) {
200 MaterializedIterator Copy = *this;
201 ++*this;
202 return Copy;
203 }
204
205 T const &operator*() const {
206 assert(ElementIdx < PV->Size);
207 assert(PV->PageToDataPtrs[ElementIdx / PageSize]);
208 T *PagePtr = PV->PageToDataPtrs[ElementIdx / PageSize];
209 return PagePtr[ElementIdx % PageSize];
210 }
211
212 /// Equality operator.
213 friend bool operator==(const MaterializedIterator &LHS,
214 const MaterializedIterator &RHS) {
215 return LHS.equals(RHS);
216 }
217
218 [[nodiscard]] size_t getIndex() const { return ElementIdx; }
219
220 friend bool operator!=(const MaterializedIterator &LHS,
221 const MaterializedIterator &RHS) {
222 return !(LHS == RHS);
223 }
224
225 private:
226 void verify() const {
227 assert(
228 ElementIdx == PV->Size ||
229 (ElementIdx < PV->Size && PV->PageToDataPtrs[ElementIdx / PageSize]));
230 }
231
232 bool equals(const MaterializedIterator &Other) const {
233 assert(PV == Other.PV);
234 verify();
235 Other.verify();
236 return ElementIdx == Other.ElementIdx;
237 }
238 };
239
240 /// Iterators over the materialized elements of the vector.
241 ///
242 /// This includes all the elements belonging to allocated pages,
243 /// even if they have not been accessed yet. It's enough to access
244 /// one element of a page to materialize all the elements of the page.
245 MaterializedIterator materialized_begin() const {
246 // Look for the first valid page.
247 for (size_t ElementIdx = 0; ElementIdx < Size; ElementIdx += PageSize)
248 if (PageToDataPtrs[ElementIdx / PageSize])
249 return MaterializedIterator(this, ElementIdx);
250
251 return MaterializedIterator(this, Size);
252 }
253
254 MaterializedIterator materialized_end() const {
255 return MaterializedIterator(this, Size);
256 }
257
258 [[nodiscard]] llvm::iterator_range<MaterializedIterator>
259 materialized() const {
260 return {materialized_begin(), materialized_end()};
261 }
262};
263} // namespace llvm
264#endif // LLVM_ADT_PAGEDVECTOR_H
265

source code of include/llvm-20/llvm/ADT/PagedVector.h