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