Deleted Added
sdiff udiff text old ( 341825 ) new ( 344779 )
full compact
xray_segmented_array.h (341825) xray_segmented_array.h (344779)
1//===-- xray_segmented_array.h ---------------------------------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//

--- 18 unchanged lines hidden (view full) ---

27
28/// The Array type provides an interface similar to std::vector<...> but does
29/// not shrink in size. Once constructed, elements can be appended but cannot be
30/// removed. The implementation is heavily dependent on the contract provided by
31/// the Allocator type, in that all memory will be released when the Allocator
32/// is destroyed. When an Array is destroyed, it will destroy elements in the
33/// backing store but will not free the memory.
34template <class T> class Array {
1//===-- xray_segmented_array.h ---------------------------------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//

--- 18 unchanged lines hidden (view full) ---

27
28/// The Array type provides an interface similar to std::vector<...> but does
29/// not shrink in size. Once constructed, elements can be appended but cannot be
30/// removed. The implementation is heavily dependent on the contract provided by
31/// the Allocator type, in that all memory will be released when the Allocator
32/// is destroyed. When an Array is destroyed, it will destroy elements in the
33/// backing store but will not free the memory.
34template <class T> class Array {
35 struct SegmentBase {
36 SegmentBase *Prev;
37 SegmentBase *Next;
38 };
39
40 // We want each segment of the array to be cache-line aligned, and elements of
41 // the array be offset from the beginning of the segment.
42 struct Segment : SegmentBase {
35 struct Segment {
36 Segment *Prev;
37 Segment *Next;
43 char Data[1];
44 };
45
46public:
47 // Each segment of the array will be laid out with the following assumptions:
48 //
49 // - Each segment will be on a cache-line address boundary (kCacheLineSize
50 // aligned).

--- 6 unchanged lines hidden (view full) ---

57 // through appropriate alignment.
58 //
59 // We then compute the size of the segment to follow this logic:
60 //
61 // - Compute the number of elements that can fit within
62 // kCacheLineSize-multiple segments, minus the size of two pointers.
63 //
64 // - Request cacheline-multiple sized elements from the allocator.
38 char Data[1];
39 };
40
41public:
42 // Each segment of the array will be laid out with the following assumptions:
43 //
44 // - Each segment will be on a cache-line address boundary (kCacheLineSize
45 // aligned).

--- 6 unchanged lines hidden (view full) ---

52 // through appropriate alignment.
53 //
54 // We then compute the size of the segment to follow this logic:
55 //
56 // - Compute the number of elements that can fit within
57 // kCacheLineSize-multiple segments, minus the size of two pointers.
58 //
59 // - Request cacheline-multiple sized elements from the allocator.
65 static constexpr size_t AlignedElementStorageSize =
60 static constexpr uint64_t AlignedElementStorageSize =
66 sizeof(typename std::aligned_storage<sizeof(T), alignof(T)>::type);
67
61 sizeof(typename std::aligned_storage<sizeof(T), alignof(T)>::type);
62
68 static constexpr size_t SegmentSize =
69 nearest_boundary(sizeof(Segment) + next_pow2(sizeof(T)), kCacheLineSize);
63 static constexpr uint64_t SegmentControlBlockSize = sizeof(Segment *) * 2;
70
64
65 static constexpr uint64_t SegmentSize = nearest_boundary(
66 SegmentControlBlockSize + next_pow2(sizeof(T)), kCacheLineSize);
67
71 using AllocatorType = Allocator<SegmentSize>;
72
68 using AllocatorType = Allocator<SegmentSize>;
69
73 static constexpr size_t ElementsPerSegment =
74 (SegmentSize - sizeof(Segment)) / next_pow2(sizeof(T));
70 static constexpr uint64_t ElementsPerSegment =
71 (SegmentSize - SegmentControlBlockSize) / next_pow2(sizeof(T));
75
76 static_assert(ElementsPerSegment > 0,
77 "Must have at least 1 element per segment.");
78
72
73 static_assert(ElementsPerSegment > 0,
74 "Must have at least 1 element per segment.");
75
79 static SegmentBase SentinelSegment;
76 static Segment SentinelSegment;
80
77
81private:
82 AllocatorType *Alloc;
83 SegmentBase *Head = &SentinelSegment;
84 SegmentBase *Tail = &SentinelSegment;
85 size_t Size = 0;
78 using size_type = uint64_t;
86
79
87 // Here we keep track of segments in the freelist, to allow us to re-use
88 // segments when elements are trimmed off the end.
89 SegmentBase *Freelist = &SentinelSegment;
90
91 Segment *NewSegment() {
92 // We need to handle the case in which enough elements have been trimmed to
93 // allow us to re-use segments we've allocated before. For this we look into
94 // the Freelist, to see whether we need to actually allocate new blocks or
95 // just re-use blocks we've already seen before.
96 if (Freelist != &SentinelSegment) {
97 auto *FreeSegment = Freelist;
98 Freelist = FreeSegment->Next;
99 FreeSegment->Next = &SentinelSegment;
100 Freelist->Prev = &SentinelSegment;
101 return static_cast<Segment *>(FreeSegment);
102 }
103
104 auto SegmentBlock = Alloc->Allocate();
105 if (SegmentBlock.Data == nullptr)
106 return nullptr;
107
108 // Placement-new the Segment element at the beginning of the SegmentBlock.
109 auto S = reinterpret_cast<Segment *>(SegmentBlock.Data);
110 new (S) SegmentBase{&SentinelSegment, &SentinelSegment};
111 return S;
112 }
113
114 Segment *InitHeadAndTail() {
115 DCHECK_EQ(Head, &SentinelSegment);
116 DCHECK_EQ(Tail, &SentinelSegment);
117 auto Segment = NewSegment();
118 if (Segment == nullptr)
119 return nullptr;
120 DCHECK_EQ(Segment->Next, &SentinelSegment);
121 DCHECK_EQ(Segment->Prev, &SentinelSegment);
122 Head = Tail = static_cast<SegmentBase *>(Segment);
123 return Segment;
124 }
125
126 Segment *AppendNewSegment() {
127 auto S = NewSegment();
128 if (S == nullptr)
129 return nullptr;
130 DCHECK_NE(Tail, &SentinelSegment);
131 DCHECK_EQ(Tail->Next, &SentinelSegment);
132 DCHECK_EQ(S->Prev, &SentinelSegment);
133 DCHECK_EQ(S->Next, &SentinelSegment);
134 Tail->Next = S;
135 S->Prev = Tail;
136 Tail = S;
137 return static_cast<Segment *>(Tail);
138 }
139
80private:
140 // This Iterator models a BidirectionalIterator.
141 template <class U> class Iterator {
81 // This Iterator models a BidirectionalIterator.
82 template <class U> class Iterator {
142 SegmentBase *S = &SentinelSegment;
143 size_t Offset = 0;
144 size_t Size = 0;
83 Segment *S = &SentinelSegment;
84 uint64_t Offset = 0;
85 uint64_t Size = 0;
145
146 public:
86
87 public:
147 Iterator(SegmentBase *IS, size_t Off, size_t S)
148 : S(IS), Offset(Off), Size(S) {}
149 Iterator(const Iterator &) noexcept = default;
150 Iterator() noexcept = default;
151 Iterator(Iterator &&) noexcept = default;
152 Iterator &operator=(const Iterator &) = default;
153 Iterator &operator=(Iterator &&) = default;
154 ~Iterator() = default;
88 Iterator(Segment *IS, uint64_t Off, uint64_t S) XRAY_NEVER_INSTRUMENT
89 : S(IS),
90 Offset(Off),
91 Size(S) {}
92 Iterator(const Iterator &) NOEXCEPT XRAY_NEVER_INSTRUMENT = default;
93 Iterator() NOEXCEPT XRAY_NEVER_INSTRUMENT = default;
94 Iterator(Iterator &&) NOEXCEPT XRAY_NEVER_INSTRUMENT = default;
95 Iterator &operator=(const Iterator &) XRAY_NEVER_INSTRUMENT = default;
96 Iterator &operator=(Iterator &&) XRAY_NEVER_INSTRUMENT = default;
97 ~Iterator() XRAY_NEVER_INSTRUMENT = default;
155
98
156 Iterator &operator++() {
99 Iterator &operator++() XRAY_NEVER_INSTRUMENT {
157 if (++Offset % ElementsPerSegment || Offset == Size)
158 return *this;
159
160 // At this point, we know that Offset % N == 0, so we must advance the
161 // segment pointer.
162 DCHECK_EQ(Offset % ElementsPerSegment, 0);
163 DCHECK_NE(Offset, Size);
164 DCHECK_NE(S, &SentinelSegment);
165 DCHECK_NE(S->Next, &SentinelSegment);
166 S = S->Next;
167 DCHECK_NE(S, &SentinelSegment);
168 return *this;
169 }
170
100 if (++Offset % ElementsPerSegment || Offset == Size)
101 return *this;
102
103 // At this point, we know that Offset % N == 0, so we must advance the
104 // segment pointer.
105 DCHECK_EQ(Offset % ElementsPerSegment, 0);
106 DCHECK_NE(Offset, Size);
107 DCHECK_NE(S, &SentinelSegment);
108 DCHECK_NE(S->Next, &SentinelSegment);
109 S = S->Next;
110 DCHECK_NE(S, &SentinelSegment);
111 return *this;
112 }
113
171 Iterator &operator--() {
114 Iterator &operator--() XRAY_NEVER_INSTRUMENT {
172 DCHECK_NE(S, &SentinelSegment);
173 DCHECK_GT(Offset, 0);
174
175 auto PreviousOffset = Offset--;
176 if (PreviousOffset != Size && PreviousOffset % ElementsPerSegment == 0) {
177 DCHECK_NE(S->Prev, &SentinelSegment);
178 S = S->Prev;
179 }
180
181 return *this;
182 }
183
115 DCHECK_NE(S, &SentinelSegment);
116 DCHECK_GT(Offset, 0);
117
118 auto PreviousOffset = Offset--;
119 if (PreviousOffset != Size && PreviousOffset % ElementsPerSegment == 0) {
120 DCHECK_NE(S->Prev, &SentinelSegment);
121 S = S->Prev;
122 }
123
124 return *this;
125 }
126
184 Iterator operator++(int) {
127 Iterator operator++(int) XRAY_NEVER_INSTRUMENT {
185 Iterator Copy(*this);
186 ++(*this);
187 return Copy;
188 }
189
128 Iterator Copy(*this);
129 ++(*this);
130 return Copy;
131 }
132
190 Iterator operator--(int) {
133 Iterator operator--(int) XRAY_NEVER_INSTRUMENT {
191 Iterator Copy(*this);
192 --(*this);
193 return Copy;
194 }
195
196 template <class V, class W>
134 Iterator Copy(*this);
135 --(*this);
136 return Copy;
137 }
138
139 template <class V, class W>
197 friend bool operator==(const Iterator<V> &L, const Iterator<W> &R) {
140 friend bool operator==(const Iterator &L,
141 const Iterator<W> &R) XRAY_NEVER_INSTRUMENT {
198 return L.S == R.S && L.Offset == R.Offset;
199 }
200
201 template <class V, class W>
142 return L.S == R.S && L.Offset == R.Offset;
143 }
144
145 template <class V, class W>
202 friend bool operator!=(const Iterator<V> &L, const Iterator<W> &R) {
146 friend bool operator!=(const Iterator &L,
147 const Iterator<W> &R) XRAY_NEVER_INSTRUMENT {
203 return !(L == R);
204 }
205
148 return !(L == R);
149 }
150
206 U &operator*() const {
151 U &operator*() const XRAY_NEVER_INSTRUMENT {
207 DCHECK_NE(S, &SentinelSegment);
208 auto RelOff = Offset % ElementsPerSegment;
209
210 // We need to compute the character-aligned pointer, offset from the
211 // segment's Data location to get the element in the position of Offset.
152 DCHECK_NE(S, &SentinelSegment);
153 auto RelOff = Offset % ElementsPerSegment;
154
155 // We need to compute the character-aligned pointer, offset from the
156 // segment's Data location to get the element in the position of Offset.
212 auto Base = static_cast<Segment *>(S)->Data;
157 auto Base = &S->Data;
213 auto AlignedOffset = Base + (RelOff * AlignedElementStorageSize);
214 return *reinterpret_cast<U *>(AlignedOffset);
215 }
216
158 auto AlignedOffset = Base + (RelOff * AlignedElementStorageSize);
159 return *reinterpret_cast<U *>(AlignedOffset);
160 }
161
217 U *operator->() const { return &(**this); }
162 U *operator->() const XRAY_NEVER_INSTRUMENT { return &(**this); }
218 };
219
163 };
164
165 AllocatorType *Alloc;
166 Segment *Head;
167 Segment *Tail;
168
169 // Here we keep track of segments in the freelist, to allow us to re-use
170 // segments when elements are trimmed off the end.
171 Segment *Freelist;
172 uint64_t Size;
173
174 // ===============================
175 // In the following implementation, we work through the algorithms and the
176 // list operations using the following notation:
177 //
178 // - pred(s) is the predecessor (previous node accessor) and succ(s) is
179 // the successor (next node accessor).
180 //
181 // - S is a sentinel segment, which has the following property:
182 //
183 // pred(S) == succ(S) == S
184 //
185 // - @ is a loop operator, which can imply pred(s) == s if it appears on
186 // the left of s, or succ(s) == S if it appears on the right of s.
187 //
188 // - sL <-> sR : means a bidirectional relation between sL and sR, which
189 // means:
190 //
191 // succ(sL) == sR && pred(SR) == sL
192 //
193 // - sL -> sR : implies a unidirectional relation between sL and SR,
194 // with the following properties:
195 //
196 // succ(sL) == sR
197 //
198 // sL <- sR : implies a unidirectional relation between sR and sL,
199 // with the following properties:
200 //
201 // pred(sR) == sL
202 //
203 // ===============================
204
205 Segment *NewSegment() XRAY_NEVER_INSTRUMENT {
206 // We need to handle the case in which enough elements have been trimmed to
207 // allow us to re-use segments we've allocated before. For this we look into
208 // the Freelist, to see whether we need to actually allocate new blocks or
209 // just re-use blocks we've already seen before.
210 if (Freelist != &SentinelSegment) {
211 // The current state of lists resemble something like this at this point:
212 //
213 // Freelist: @S@<-f0->...<->fN->@S@
214 // ^ Freelist
215 //
216 // We want to perform a splice of `f0` from Freelist to a temporary list,
217 // which looks like:
218 //
219 // Templist: @S@<-f0->@S@
220 // ^ FreeSegment
221 //
222 // Our algorithm preconditions are:
223 DCHECK_EQ(Freelist->Prev, &SentinelSegment);
224
225 // Then the algorithm we implement is:
226 //
227 // SFS = Freelist
228 // Freelist = succ(Freelist)
229 // if (Freelist != S)
230 // pred(Freelist) = S
231 // succ(SFS) = S
232 // pred(SFS) = S
233 //
234 auto *FreeSegment = Freelist;
235 Freelist = Freelist->Next;
236
237 // Note that we need to handle the case where Freelist is now pointing to
238 // S, which we don't want to be overwriting.
239 // TODO: Determine whether the cost of the branch is higher than the cost
240 // of the blind assignment.
241 if (Freelist != &SentinelSegment)
242 Freelist->Prev = &SentinelSegment;
243
244 FreeSegment->Next = &SentinelSegment;
245 FreeSegment->Prev = &SentinelSegment;
246
247 // Our postconditions are:
248 DCHECK_EQ(Freelist->Prev, &SentinelSegment);
249 DCHECK_NE(FreeSegment, &SentinelSegment);
250 return FreeSegment;
251 }
252
253 auto SegmentBlock = Alloc->Allocate();
254 if (SegmentBlock.Data == nullptr)
255 return nullptr;
256
257 // Placement-new the Segment element at the beginning of the SegmentBlock.
258 new (SegmentBlock.Data) Segment{&SentinelSegment, &SentinelSegment, {0}};
259 auto SB = reinterpret_cast<Segment *>(SegmentBlock.Data);
260 return SB;
261 }
262
263 Segment *InitHeadAndTail() XRAY_NEVER_INSTRUMENT {
264 DCHECK_EQ(Head, &SentinelSegment);
265 DCHECK_EQ(Tail, &SentinelSegment);
266 auto S = NewSegment();
267 if (S == nullptr)
268 return nullptr;
269 DCHECK_EQ(S->Next, &SentinelSegment);
270 DCHECK_EQ(S->Prev, &SentinelSegment);
271 DCHECK_NE(S, &SentinelSegment);
272 Head = S;
273 Tail = S;
274 DCHECK_EQ(Head, Tail);
275 DCHECK_EQ(Tail->Next, &SentinelSegment);
276 DCHECK_EQ(Tail->Prev, &SentinelSegment);
277 return S;
278 }
279
280 Segment *AppendNewSegment() XRAY_NEVER_INSTRUMENT {
281 auto S = NewSegment();
282 if (S == nullptr)
283 return nullptr;
284 DCHECK_NE(Tail, &SentinelSegment);
285 DCHECK_EQ(Tail->Next, &SentinelSegment);
286 DCHECK_EQ(S->Prev, &SentinelSegment);
287 DCHECK_EQ(S->Next, &SentinelSegment);
288 S->Prev = Tail;
289 Tail->Next = S;
290 Tail = S;
291 DCHECK_EQ(S, S->Prev->Next);
292 DCHECK_EQ(Tail->Next, &SentinelSegment);
293 return S;
294 }
295
220public:
296public:
221 explicit Array(AllocatorType &A) : Alloc(&A) {}
297 explicit Array(AllocatorType &A) XRAY_NEVER_INSTRUMENT
298 : Alloc(&A),
299 Head(&SentinelSegment),
300 Tail(&SentinelSegment),
301 Freelist(&SentinelSegment),
302 Size(0) {}
222
303
304 Array() XRAY_NEVER_INSTRUMENT : Alloc(nullptr),
305 Head(&SentinelSegment),
306 Tail(&SentinelSegment),
307 Freelist(&SentinelSegment),
308 Size(0) {}
309
223 Array(const Array &) = delete;
310 Array(const Array &) = delete;
224 Array(Array &&O) NOEXCEPT : Alloc(O.Alloc),
225 Head(O.Head),
226 Tail(O.Tail),
227 Size(O.Size) {
311 Array &operator=(const Array &) = delete;
312
313 Array(Array &&O) XRAY_NEVER_INSTRUMENT : Alloc(O.Alloc),
314 Head(O.Head),
315 Tail(O.Tail),
316 Freelist(O.Freelist),
317 Size(O.Size) {
318 O.Alloc = nullptr;
228 O.Head = &SentinelSegment;
229 O.Tail = &SentinelSegment;
230 O.Size = 0;
319 O.Head = &SentinelSegment;
320 O.Tail = &SentinelSegment;
321 O.Size = 0;
322 O.Freelist = &SentinelSegment;
231 }
232
323 }
324
233 bool empty() const { return Size == 0; }
325 Array &operator=(Array &&O) XRAY_NEVER_INSTRUMENT {
326 Alloc = O.Alloc;
327 O.Alloc = nullptr;
328 Head = O.Head;
329 O.Head = &SentinelSegment;
330 Tail = O.Tail;
331 O.Tail = &SentinelSegment;
332 Freelist = O.Freelist;
333 O.Freelist = &SentinelSegment;
334 Size = O.Size;
335 O.Size = 0;
336 return *this;
337 }
234
338
235 AllocatorType &allocator() const {
339 ~Array() XRAY_NEVER_INSTRUMENT {
340 for (auto &E : *this)
341 (&E)->~T();
342 }
343
344 bool empty() const XRAY_NEVER_INSTRUMENT { return Size == 0; }
345
346 AllocatorType &allocator() const XRAY_NEVER_INSTRUMENT {
236 DCHECK_NE(Alloc, nullptr);
237 return *Alloc;
238 }
239
347 DCHECK_NE(Alloc, nullptr);
348 return *Alloc;
349 }
350
240 size_t size() const { return Size; }
351 uint64_t size() const XRAY_NEVER_INSTRUMENT { return Size; }
241
352
242 T *Append(const T &E) {
243 if (UNLIKELY(Head == &SentinelSegment))
244 if (InitHeadAndTail() == nullptr)
353 template <class... Args>
354 T *AppendEmplace(Args &&... args) XRAY_NEVER_INSTRUMENT {
355 DCHECK((Size == 0 && Head == &SentinelSegment && Head == Tail) ||
356 (Size != 0 && Head != &SentinelSegment && Tail != &SentinelSegment));
357 if (UNLIKELY(Head == &SentinelSegment)) {
358 auto R = InitHeadAndTail();
359 if (R == nullptr)
245 return nullptr;
360 return nullptr;
361 }
246
362
363 DCHECK_NE(Head, &SentinelSegment);
364 DCHECK_NE(Tail, &SentinelSegment);
365
247 auto Offset = Size % ElementsPerSegment;
248 if (UNLIKELY(Size != 0 && Offset == 0))
249 if (AppendNewSegment() == nullptr)
250 return nullptr;
251
366 auto Offset = Size % ElementsPerSegment;
367 if (UNLIKELY(Size != 0 && Offset == 0))
368 if (AppendNewSegment() == nullptr)
369 return nullptr;
370
252 auto Base = static_cast<Segment *>(Tail)->Data;
371 DCHECK_NE(Tail, &SentinelSegment);
372 auto Base = &Tail->Data;
253 auto AlignedOffset = Base + (Offset * AlignedElementStorageSize);
373 auto AlignedOffset = Base + (Offset * AlignedElementStorageSize);
254 auto Position = reinterpret_cast<T *>(AlignedOffset);
255 *Position = E;
374 DCHECK_LE(AlignedOffset + sizeof(T),
375 reinterpret_cast<unsigned char *>(Base) + SegmentSize);
376
377 // In-place construct at Position.
378 new (AlignedOffset) T{std::forward<Args>(args)...};
256 ++Size;
379 ++Size;
257 return Position;
380 return reinterpret_cast<T *>(AlignedOffset);
258 }
259
381 }
382
260 template <class... Args> T *AppendEmplace(Args &&... args) {
261 if (UNLIKELY(Head == &SentinelSegment))
262 if (InitHeadAndTail() == nullptr)
383 T *Append(const T &E) XRAY_NEVER_INSTRUMENT {
384 // FIXME: This is a duplication of AppenEmplace with the copy semantics
385 // explicitly used, as a work-around to GCC 4.8 not invoking the copy
386 // constructor with the placement new with braced-init syntax.
387 DCHECK((Size == 0 && Head == &SentinelSegment && Head == Tail) ||
388 (Size != 0 && Head != &SentinelSegment && Tail != &SentinelSegment));
389 if (UNLIKELY(Head == &SentinelSegment)) {
390 auto R = InitHeadAndTail();
391 if (R == nullptr)
263 return nullptr;
392 return nullptr;
393 }
264
394
395 DCHECK_NE(Head, &SentinelSegment);
396 DCHECK_NE(Tail, &SentinelSegment);
397
265 auto Offset = Size % ElementsPerSegment;
398 auto Offset = Size % ElementsPerSegment;
266 auto *LatestSegment = Tail;
267 if (UNLIKELY(Size != 0 && Offset == 0)) {
268 LatestSegment = AppendNewSegment();
269 if (LatestSegment == nullptr)
399 if (UNLIKELY(Size != 0 && Offset == 0))
400 if (AppendNewSegment() == nullptr)
270 return nullptr;
401 return nullptr;
271 }
272
273 DCHECK_NE(Tail, &SentinelSegment);
402
403 DCHECK_NE(Tail, &SentinelSegment);
274 auto Base = static_cast<Segment *>(LatestSegment)->Data;
404 auto Base = &Tail->Data;
275 auto AlignedOffset = Base + (Offset * AlignedElementStorageSize);
405 auto AlignedOffset = Base + (Offset * AlignedElementStorageSize);
276 auto Position = reinterpret_cast<T *>(AlignedOffset);
406 DCHECK_LE(AlignedOffset + sizeof(T),
407 reinterpret_cast<unsigned char *>(Tail) + SegmentSize);
277
278 // In-place construct at Position.
408
409 // In-place construct at Position.
279 new (Position) T{std::forward<Args>(args)...};
410 new (AlignedOffset) T(E);
280 ++Size;
411 ++Size;
281 return reinterpret_cast<T *>(Position);
412 return reinterpret_cast<T *>(AlignedOffset);
282 }
283
413 }
414
284 T &operator[](size_t Offset) const {
415 T &operator[](uint64_t Offset) const XRAY_NEVER_INSTRUMENT {
285 DCHECK_LE(Offset, Size);
286 // We need to traverse the array enough times to find the element at Offset.
287 auto S = Head;
288 while (Offset >= ElementsPerSegment) {
289 S = S->Next;
290 Offset -= ElementsPerSegment;
291 DCHECK_NE(S, &SentinelSegment);
292 }
416 DCHECK_LE(Offset, Size);
417 // We need to traverse the array enough times to find the element at Offset.
418 auto S = Head;
419 while (Offset >= ElementsPerSegment) {
420 S = S->Next;
421 Offset -= ElementsPerSegment;
422 DCHECK_NE(S, &SentinelSegment);
423 }
293 auto Base = static_cast<Segment *>(S)->Data;
424 auto Base = &S->Data;
294 auto AlignedOffset = Base + (Offset * AlignedElementStorageSize);
295 auto Position = reinterpret_cast<T *>(AlignedOffset);
296 return *reinterpret_cast<T *>(Position);
297 }
298
425 auto AlignedOffset = Base + (Offset * AlignedElementStorageSize);
426 auto Position = reinterpret_cast<T *>(AlignedOffset);
427 return *reinterpret_cast<T *>(Position);
428 }
429
299 T &front() const {
430 T &front() const XRAY_NEVER_INSTRUMENT {
300 DCHECK_NE(Head, &SentinelSegment);
301 DCHECK_NE(Size, 0u);
302 return *begin();
303 }
304
431 DCHECK_NE(Head, &SentinelSegment);
432 DCHECK_NE(Size, 0u);
433 return *begin();
434 }
435
305 T &back() const {
436 T &back() const XRAY_NEVER_INSTRUMENT {
306 DCHECK_NE(Tail, &SentinelSegment);
307 DCHECK_NE(Size, 0u);
308 auto It = end();
309 --It;
310 return *It;
311 }
312
437 DCHECK_NE(Tail, &SentinelSegment);
438 DCHECK_NE(Size, 0u);
439 auto It = end();
440 --It;
441 return *It;
442 }
443
313 template <class Predicate> T *find_element(Predicate P) const {
444 template
445 T *find_element(Predicate P) const XRAY_NEVER_INSTRUMENT {
314 if (empty())
315 return nullptr;
316
317 auto E = end();
318 for (auto I = begin(); I != E; ++I)
319 if (P(*I))
320 return &(*I);
321
322 return nullptr;
323 }
324
325 /// Remove N Elements from the end. This leaves the blocks behind, and not
326 /// require allocation of new blocks for new elements added after trimming.
446 if (empty())
447 return nullptr;
448
449 auto E = end();
450 for (auto I = begin(); I != E; ++I)
451 if (P(*I))
452 return &(*I);
453
454 return nullptr;
455 }
456
457 /// Remove N Elements from the end. This leaves the blocks behind, and not
458 /// require allocation of new blocks for new elements added after trimming.
327 void trim(size_t Elements) {
328 DCHECK_LE(Elements, Size);
329 DCHECK_GT(Size, 0);
459 void trim(uint64_t Elements) XRAY_NEVER_INSTRUMENT {
330 auto OldSize = Size;
460 auto OldSize = Size;
461 Elements = Elements > Size ? Size : Elements;
331 Size -= Elements;
332
462 Size -= Elements;
463
333 DCHECK_NE(Head, &SentinelSegment);
334 DCHECK_NE(Tail, &SentinelSegment);
335
336 for (auto SegmentsToTrim = (nearest_boundary(OldSize, ElementsPerSegment) -
337 nearest_boundary(Size, ElementsPerSegment)) /
338 ElementsPerSegment;
339 SegmentsToTrim > 0; --SegmentsToTrim) {
464 // We compute the number of segments we're going to return from the tail by
465 // counting how many elements have been trimmed. Given the following:
466 //
467 // - Each segment has N valid positions, where N > 0
468 // - The previous size > current size
469 //
470 // To compute the number of segments to return, we need to perform the
471 // following calculations for the number of segments required given 'x'
472 // elements:
473 //
474 // f(x) = {
475 // x == 0 : 0
476 // , 0 < x <= N : 1
477 // , N < x <= max : x / N + (x % N ? 1 : 0)
478 // }
479 //
480 // We can simplify this down to:
481 //
482 // f(x) = {
483 // x == 0 : 0,
484 // , 0 < x <= max : x / N + (x < N || x % N ? 1 : 0)
485 // }
486 //
487 // And further down to:
488 //
489 // f(x) = x ? x / N + (x < N || x % N ? 1 : 0) : 0
490 //
491 // We can then perform the following calculation `s` which counts the number
492 // of segments we need to remove from the end of the data structure:
493 //
494 // s(p, c) = f(p) - f(c)
495 //
496 // If we treat p = previous size, and c = current size, and given the
497 // properties above, the possible range for s(...) is [0..max(typeof(p))/N]
498 // given that typeof(p) == typeof(c).
499 auto F = [](uint64_t X) {
500 return X ? (X / ElementsPerSegment) +
501 (X < ElementsPerSegment || X % ElementsPerSegment ? 1 : 0)
502 : 0;
503 };
504 auto PS = F(OldSize);
505 auto CS = F(Size);
506 DCHECK_GE(PS, CS);
507 auto SegmentsToTrim = PS - CS;
508 for (auto I = 0uL; I < SegmentsToTrim; ++I) {
509 // Here we place the current tail segment to the freelist. To do this
510 // appropriately, we need to perform a splice operation on two
511 // bidirectional linked-lists. In particular, we have the current state of
512 // the doubly-linked list of segments:
513 //
514 // @S@ <- s0 <-> s1 <-> ... <-> sT -> @S@
515 //
340 DCHECK_NE(Head, &SentinelSegment);
341 DCHECK_NE(Tail, &SentinelSegment);
516 DCHECK_NE(Head, &SentinelSegment);
517 DCHECK_NE(Tail, &SentinelSegment);
342 // Put the tail into the Freelist.
343 auto *FreeSegment = Tail;
344 Tail = Tail->Prev;
345 if (Tail == &SentinelSegment)
346 Head = Tail;
347 else
348 Tail->Next = &SentinelSegment;
349
350 DCHECK_EQ(Tail->Next, &SentinelSegment);
518 DCHECK_EQ(Tail->Next, &SentinelSegment);
351 FreeSegment->Next = Freelist;
352 FreeSegment->Prev = &SentinelSegment;
353 if (Freelist != &SentinelSegment)
354 Freelist->Prev = FreeSegment;
355 Freelist = FreeSegment;
519
520 if (Freelist == &SentinelSegment) {
521 // Our two lists at this point are in this configuration:
522 //
523 // Freelist: (potentially) @S@
524 // Mainlist: @S@<-s0<->s1<->...<->sPT<->sT->@S@
525 // ^ Head ^ Tail
526 //
527 // The end state for us will be this configuration:
528 //
529 // Freelist: @S@<-sT->@S@
530 // Mainlist: @S@<-s0<->s1<->...<->sPT->@S@
531 // ^ Head ^ Tail
532 //
533 // The first step for us is to hold a reference to the tail of Mainlist,
534 // which in our notation is represented by sT. We call this our "free
535 // segment" which is the segment we are placing on the Freelist.
536 //
537 // sF = sT
538 //
539 // Then, we also hold a reference to the "pre-tail" element, which we
540 // call sPT:
541 //
542 // sPT = pred(sT)
543 //
544 // We want to splice sT into the beginning of the Freelist, which in
545 // an empty Freelist means placing a segment whose predecessor and
546 // successor is the sentinel segment.
547 //
548 // The splice operation then can be performed in the following
549 // algorithm:
550 //
551 // succ(sPT) = S
552 // pred(sT) = S
553 // succ(sT) = Freelist
554 // Freelist = sT
555 // Tail = sPT
556 //
557 auto SPT = Tail->Prev;
558 SPT->Next = &SentinelSegment;
559 Tail->Prev = &SentinelSegment;
560 Tail->Next = Freelist;
561 Freelist = Tail;
562 Tail = SPT;
563
564 // Our post-conditions here are:
565 DCHECK_EQ(Tail->Next, &SentinelSegment);
566 DCHECK_EQ(Freelist->Prev, &SentinelSegment);
567 } else {
568 // In the other case, where the Freelist is not empty, we perform the
569 // following transformation instead:
570 //
571 // This transforms the current state:
572 //
573 // Freelist: @S@<-f0->@S@
574 // ^ Freelist
575 // Mainlist: @S@<-s0<->s1<->...<->sPT<->sT->@S@
576 // ^ Head ^ Tail
577 //
578 // Into the following:
579 //
580 // Freelist: @S@<-sT<->f0->@S@
581 // ^ Freelist
582 // Mainlist: @S@<-s0<->s1<->...<->sPT->@S@
583 // ^ Head ^ Tail
584 //
585 // The algorithm is:
586 //
587 // sFH = Freelist
588 // sPT = pred(sT)
589 // pred(SFH) = sT
590 // succ(sT) = Freelist
591 // pred(sT) = S
592 // succ(sPT) = S
593 // Tail = sPT
594 // Freelist = sT
595 //
596 auto SFH = Freelist;
597 auto SPT = Tail->Prev;
598 auto ST = Tail;
599 SFH->Prev = ST;
600 ST->Next = Freelist;
601 ST->Prev = &SentinelSegment;
602 SPT->Next = &SentinelSegment;
603 Tail = SPT;
604 Freelist = ST;
605
606 // Our post-conditions here are:
607 DCHECK_EQ(Tail->Next, &SentinelSegment);
608 DCHECK_EQ(Freelist->Prev, &SentinelSegment);
609 DCHECK_EQ(Freelist->Next->Prev, Freelist);
610 }
356 }
611 }
612
613 // Now in case we've spliced all the segments in the end, we ensure that the
614 // main list is "empty", or both the head and tail pointing to the sentinel
615 // segment.
616 if (Tail == &SentinelSegment)
617 Head = Tail;
618
619 DCHECK(
620 (Size == 0 && Head == &SentinelSegment && Tail == &SentinelSegment) ||
621 (Size != 0 && Head != &SentinelSegment && Tail != &SentinelSegment));
622 DCHECK(
623 (Freelist != &SentinelSegment && Freelist->Prev == &SentinelSegment) ||
624 (Freelist == &SentinelSegment && Tail->Next == &SentinelSegment));
357 }
358
359 // Provide iterators.
625 }
626
627 // Provide iterators.
360 Iterator<T> begin() const { return Iterator<T>(Head, 0, Size); }
361 Iterator<T> end() const { return Iterator<T>(Tail, Size, Size); }
362 Iterator<const T> cbegin() const { return Iterator<const T>(Head, 0, Size); }
363 Iterator<const T> cend() const { return Iterator<const T>(Tail, Size, Size); }
628 Iterator<T> begin() const XRAY_NEVER_INSTRUMENT {
629 return Iterator<T>(Head, 0, Size);
630 }
631 Iterator<T> end() const XRAY_NEVER_INSTRUMENT {
632 return Iterator<T>(Tail, Size, Size);
633 }
634 Iterator<const T> cbegin() const XRAY_NEVER_INSTRUMENT {
635 return Iterator<const T>(Head, 0, Size);
636 }
637 Iterator<const T> cend() const XRAY_NEVER_INSTRUMENT {
638 return Iterator<const T>(Tail, Size, Size);
639 }
364};
365
366// We need to have this storage definition out-of-line so that the compiler can
367// ensure that storage for the SentinelSegment is defined and has a single
368// address.
369template <class T>
640};
641
642// We need to have this storage definition out-of-line so that the compiler can
643// ensure that storage for the SentinelSegment is defined and has a single
644// address.
645template <class T>
370typename Array<T>::SegmentBase Array<T>::SentinelSegment{
371 &Array::SentinelSegment, &Array::SentinelSegment};
646typename Array::Segment Array::SentinelSegment{
647 &Array<T>::SentinelSegment, &Array<T>::SentinelSegment, {'\0'}};
372
373} // namespace __xray
374
375#endif // XRAY_SEGMENTED_ARRAY_H
648
649} // namespace __xray
650
651#endif // XRAY_SEGMENTED_ARRAY_H