contrib/compiler-rt/lib/xray/xray_segmented_array.h

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