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 | |
22 | namespace 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. |
42 | template <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 | |
56 | public: |
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 (!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 | |