1336817Sdim//===-- xray_segmented_array.h ---------------------------------*- C++ -*-===// 2336817Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6336817Sdim// 7336817Sdim//===----------------------------------------------------------------------===// 8336817Sdim// 9336817Sdim// This file is a part of XRay, a dynamic runtime instrumentation system. 10336817Sdim// 11336817Sdim// Defines the implementation of a segmented array, with fixed-size segments 12336817Sdim// backing the segments. 13336817Sdim// 14336817Sdim//===----------------------------------------------------------------------===// 15336817Sdim#ifndef XRAY_SEGMENTED_ARRAY_H 16336817Sdim#define XRAY_SEGMENTED_ARRAY_H 17336817Sdim 18336817Sdim#include "sanitizer_common/sanitizer_allocator.h" 19336817Sdim#include "xray_allocator.h" 20336817Sdim#include "xray_utils.h" 21336817Sdim#include <cassert> 22336817Sdim#include <type_traits> 23336817Sdim#include <utility> 24336817Sdim 25336817Sdimnamespace __xray { 26336817Sdim 27336817Sdim/// The Array type provides an interface similar to std::vector<...> but does 28336817Sdim/// not shrink in size. Once constructed, elements can be appended but cannot be 29336817Sdim/// removed. The implementation is heavily dependent on the contract provided by 30336817Sdim/// the Allocator type, in that all memory will be released when the Allocator 31336817Sdim/// is destroyed. When an Array is destroyed, it will destroy elements in the 32336817Sdim/// backing store but will not free the memory. 33336817Sdimtemplate <class T> class Array { 34344779Sdim struct Segment { 35344779Sdim Segment *Prev; 36344779Sdim Segment *Next; 37336817Sdim char Data[1]; 38336817Sdim }; 39336817Sdim 40336817Sdimpublic: 41336817Sdim // Each segment of the array will be laid out with the following assumptions: 42336817Sdim // 43336817Sdim // - Each segment will be on a cache-line address boundary (kCacheLineSize 44336817Sdim // aligned). 45336817Sdim // 46336817Sdim // - The elements will be accessed through an aligned pointer, dependent on 47336817Sdim // the alignment of T. 48336817Sdim // 49336817Sdim // - Each element is at least two-pointers worth from the beginning of the 50336817Sdim // Segment, aligned properly, and the rest of the elements are accessed 51336817Sdim // through appropriate alignment. 52336817Sdim // 53336817Sdim // We then compute the size of the segment to follow this logic: 54336817Sdim // 55336817Sdim // - Compute the number of elements that can fit within 56336817Sdim // kCacheLineSize-multiple segments, minus the size of two pointers. 57336817Sdim // 58336817Sdim // - Request cacheline-multiple sized elements from the allocator. 59344779Sdim static constexpr uint64_t AlignedElementStorageSize = 60336817Sdim sizeof(typename std::aligned_storage<sizeof(T), alignof(T)>::type); 61336817Sdim 62344779Sdim static constexpr uint64_t SegmentControlBlockSize = sizeof(Segment *) * 2; 63336817Sdim 64344779Sdim static constexpr uint64_t SegmentSize = nearest_boundary( 65344779Sdim SegmentControlBlockSize + next_pow2(sizeof(T)), kCacheLineSize); 66344779Sdim 67336817Sdim using AllocatorType = Allocator<SegmentSize>; 68336817Sdim 69344779Sdim static constexpr uint64_t ElementsPerSegment = 70344779Sdim (SegmentSize - SegmentControlBlockSize) / next_pow2(sizeof(T)); 71336817Sdim 72336817Sdim static_assert(ElementsPerSegment > 0, 73336817Sdim "Must have at least 1 element per segment."); 74336817Sdim 75344779Sdim static Segment SentinelSegment; 76336817Sdim 77344779Sdim using size_type = uint64_t; 78344779Sdim 79336817Sdimprivate: 80336817Sdim // This Iterator models a BidirectionalIterator. 81336817Sdim template <class U> class Iterator { 82344779Sdim Segment *S = &SentinelSegment; 83344779Sdim uint64_t Offset = 0; 84344779Sdim uint64_t Size = 0; 85336817Sdim 86336817Sdim public: 87344779Sdim Iterator(Segment *IS, uint64_t Off, uint64_t S) XRAY_NEVER_INSTRUMENT 88344779Sdim : S(IS), 89344779Sdim Offset(Off), 90344779Sdim Size(S) {} 91344779Sdim Iterator(const Iterator &) NOEXCEPT XRAY_NEVER_INSTRUMENT = default; 92344779Sdim Iterator() NOEXCEPT XRAY_NEVER_INSTRUMENT = default; 93344779Sdim Iterator(Iterator &&) NOEXCEPT XRAY_NEVER_INSTRUMENT = default; 94344779Sdim Iterator &operator=(const Iterator &) XRAY_NEVER_INSTRUMENT = default; 95344779Sdim Iterator &operator=(Iterator &&) XRAY_NEVER_INSTRUMENT = default; 96344779Sdim ~Iterator() XRAY_NEVER_INSTRUMENT = default; 97336817Sdim 98344779Sdim Iterator &operator++() XRAY_NEVER_INSTRUMENT { 99336817Sdim if (++Offset % ElementsPerSegment || Offset == Size) 100336817Sdim return *this; 101336817Sdim 102336817Sdim // At this point, we know that Offset % N == 0, so we must advance the 103336817Sdim // segment pointer. 104336817Sdim DCHECK_EQ(Offset % ElementsPerSegment, 0); 105336817Sdim DCHECK_NE(Offset, Size); 106336817Sdim DCHECK_NE(S, &SentinelSegment); 107336817Sdim DCHECK_NE(S->Next, &SentinelSegment); 108336817Sdim S = S->Next; 109336817Sdim DCHECK_NE(S, &SentinelSegment); 110336817Sdim return *this; 111336817Sdim } 112336817Sdim 113344779Sdim Iterator &operator--() XRAY_NEVER_INSTRUMENT { 114336817Sdim DCHECK_NE(S, &SentinelSegment); 115336817Sdim DCHECK_GT(Offset, 0); 116336817Sdim 117336817Sdim auto PreviousOffset = Offset--; 118336817Sdim if (PreviousOffset != Size && PreviousOffset % ElementsPerSegment == 0) { 119336817Sdim DCHECK_NE(S->Prev, &SentinelSegment); 120336817Sdim S = S->Prev; 121336817Sdim } 122336817Sdim 123336817Sdim return *this; 124336817Sdim } 125336817Sdim 126344779Sdim Iterator operator++(int) XRAY_NEVER_INSTRUMENT { 127336817Sdim Iterator Copy(*this); 128336817Sdim ++(*this); 129336817Sdim return Copy; 130336817Sdim } 131336817Sdim 132344779Sdim Iterator operator--(int) XRAY_NEVER_INSTRUMENT { 133336817Sdim Iterator Copy(*this); 134336817Sdim --(*this); 135336817Sdim return Copy; 136336817Sdim } 137336817Sdim 138336817Sdim template <class V, class W> 139344779Sdim friend bool operator==(const Iterator<V> &L, 140344779Sdim const Iterator<W> &R) XRAY_NEVER_INSTRUMENT { 141336817Sdim return L.S == R.S && L.Offset == R.Offset; 142336817Sdim } 143336817Sdim 144336817Sdim template <class V, class W> 145344779Sdim friend bool operator!=(const Iterator<V> &L, 146344779Sdim const Iterator<W> &R) XRAY_NEVER_INSTRUMENT { 147336817Sdim return !(L == R); 148336817Sdim } 149336817Sdim 150344779Sdim U &operator*() const XRAY_NEVER_INSTRUMENT { 151336817Sdim DCHECK_NE(S, &SentinelSegment); 152336817Sdim auto RelOff = Offset % ElementsPerSegment; 153336817Sdim 154336817Sdim // We need to compute the character-aligned pointer, offset from the 155336817Sdim // segment's Data location to get the element in the position of Offset. 156344779Sdim auto Base = &S->Data; 157336817Sdim auto AlignedOffset = Base + (RelOff * AlignedElementStorageSize); 158336817Sdim return *reinterpret_cast<U *>(AlignedOffset); 159336817Sdim } 160336817Sdim 161344779Sdim U *operator->() const XRAY_NEVER_INSTRUMENT { return &(**this); } 162336817Sdim }; 163336817Sdim 164344779Sdim AllocatorType *Alloc; 165344779Sdim Segment *Head; 166344779Sdim Segment *Tail; 167344779Sdim 168344779Sdim // Here we keep track of segments in the freelist, to allow us to re-use 169344779Sdim // segments when elements are trimmed off the end. 170344779Sdim Segment *Freelist; 171344779Sdim uint64_t Size; 172344779Sdim 173344779Sdim // =============================== 174344779Sdim // In the following implementation, we work through the algorithms and the 175344779Sdim // list operations using the following notation: 176344779Sdim // 177344779Sdim // - pred(s) is the predecessor (previous node accessor) and succ(s) is 178344779Sdim // the successor (next node accessor). 179344779Sdim // 180344779Sdim // - S is a sentinel segment, which has the following property: 181344779Sdim // 182344779Sdim // pred(S) == succ(S) == S 183344779Sdim // 184344779Sdim // - @ is a loop operator, which can imply pred(s) == s if it appears on 185344779Sdim // the left of s, or succ(s) == S if it appears on the right of s. 186344779Sdim // 187344779Sdim // - sL <-> sR : means a bidirectional relation between sL and sR, which 188344779Sdim // means: 189344779Sdim // 190344779Sdim // succ(sL) == sR && pred(SR) == sL 191344779Sdim // 192344779Sdim // - sL -> sR : implies a unidirectional relation between sL and SR, 193344779Sdim // with the following properties: 194344779Sdim // 195344779Sdim // succ(sL) == sR 196344779Sdim // 197344779Sdim // sL <- sR : implies a unidirectional relation between sR and sL, 198344779Sdim // with the following properties: 199344779Sdim // 200344779Sdim // pred(sR) == sL 201344779Sdim // 202344779Sdim // =============================== 203344779Sdim 204344779Sdim Segment *NewSegment() XRAY_NEVER_INSTRUMENT { 205344779Sdim // We need to handle the case in which enough elements have been trimmed to 206344779Sdim // allow us to re-use segments we've allocated before. For this we look into 207344779Sdim // the Freelist, to see whether we need to actually allocate new blocks or 208344779Sdim // just re-use blocks we've already seen before. 209344779Sdim if (Freelist != &SentinelSegment) { 210344779Sdim // The current state of lists resemble something like this at this point: 211344779Sdim // 212344779Sdim // Freelist: @S@<-f0->...<->fN->@S@ 213344779Sdim // ^ Freelist 214344779Sdim // 215344779Sdim // We want to perform a splice of `f0` from Freelist to a temporary list, 216344779Sdim // which looks like: 217344779Sdim // 218344779Sdim // Templist: @S@<-f0->@S@ 219344779Sdim // ^ FreeSegment 220344779Sdim // 221344779Sdim // Our algorithm preconditions are: 222344779Sdim DCHECK_EQ(Freelist->Prev, &SentinelSegment); 223344779Sdim 224344779Sdim // Then the algorithm we implement is: 225344779Sdim // 226344779Sdim // SFS = Freelist 227344779Sdim // Freelist = succ(Freelist) 228344779Sdim // if (Freelist != S) 229344779Sdim // pred(Freelist) = S 230344779Sdim // succ(SFS) = S 231344779Sdim // pred(SFS) = S 232344779Sdim // 233344779Sdim auto *FreeSegment = Freelist; 234344779Sdim Freelist = Freelist->Next; 235344779Sdim 236344779Sdim // Note that we need to handle the case where Freelist is now pointing to 237344779Sdim // S, which we don't want to be overwriting. 238344779Sdim // TODO: Determine whether the cost of the branch is higher than the cost 239344779Sdim // of the blind assignment. 240344779Sdim if (Freelist != &SentinelSegment) 241344779Sdim Freelist->Prev = &SentinelSegment; 242344779Sdim 243344779Sdim FreeSegment->Next = &SentinelSegment; 244344779Sdim FreeSegment->Prev = &SentinelSegment; 245344779Sdim 246344779Sdim // Our postconditions are: 247344779Sdim DCHECK_EQ(Freelist->Prev, &SentinelSegment); 248344779Sdim DCHECK_NE(FreeSegment, &SentinelSegment); 249344779Sdim return FreeSegment; 250344779Sdim } 251344779Sdim 252344779Sdim auto SegmentBlock = Alloc->Allocate(); 253344779Sdim if (SegmentBlock.Data == nullptr) 254344779Sdim return nullptr; 255344779Sdim 256344779Sdim // Placement-new the Segment element at the beginning of the SegmentBlock. 257344779Sdim new (SegmentBlock.Data) Segment{&SentinelSegment, &SentinelSegment, {0}}; 258344779Sdim auto SB = reinterpret_cast<Segment *>(SegmentBlock.Data); 259344779Sdim return SB; 260344779Sdim } 261344779Sdim 262344779Sdim Segment *InitHeadAndTail() XRAY_NEVER_INSTRUMENT { 263344779Sdim DCHECK_EQ(Head, &SentinelSegment); 264344779Sdim DCHECK_EQ(Tail, &SentinelSegment); 265344779Sdim auto S = NewSegment(); 266344779Sdim if (S == nullptr) 267344779Sdim return nullptr; 268344779Sdim DCHECK_EQ(S->Next, &SentinelSegment); 269344779Sdim DCHECK_EQ(S->Prev, &SentinelSegment); 270344779Sdim DCHECK_NE(S, &SentinelSegment); 271344779Sdim Head = S; 272344779Sdim Tail = S; 273344779Sdim DCHECK_EQ(Head, Tail); 274344779Sdim DCHECK_EQ(Tail->Next, &SentinelSegment); 275344779Sdim DCHECK_EQ(Tail->Prev, &SentinelSegment); 276344779Sdim return S; 277344779Sdim } 278344779Sdim 279344779Sdim Segment *AppendNewSegment() XRAY_NEVER_INSTRUMENT { 280344779Sdim auto S = NewSegment(); 281344779Sdim if (S == nullptr) 282344779Sdim return nullptr; 283344779Sdim DCHECK_NE(Tail, &SentinelSegment); 284344779Sdim DCHECK_EQ(Tail->Next, &SentinelSegment); 285344779Sdim DCHECK_EQ(S->Prev, &SentinelSegment); 286344779Sdim DCHECK_EQ(S->Next, &SentinelSegment); 287344779Sdim S->Prev = Tail; 288344779Sdim Tail->Next = S; 289344779Sdim Tail = S; 290344779Sdim DCHECK_EQ(S, S->Prev->Next); 291344779Sdim DCHECK_EQ(Tail->Next, &SentinelSegment); 292344779Sdim return S; 293344779Sdim } 294344779Sdim 295336817Sdimpublic: 296344779Sdim explicit Array(AllocatorType &A) XRAY_NEVER_INSTRUMENT 297344779Sdim : Alloc(&A), 298344779Sdim Head(&SentinelSegment), 299344779Sdim Tail(&SentinelSegment), 300344779Sdim Freelist(&SentinelSegment), 301344779Sdim Size(0) {} 302336817Sdim 303344779Sdim Array() XRAY_NEVER_INSTRUMENT : Alloc(nullptr), 304344779Sdim Head(&SentinelSegment), 305344779Sdim Tail(&SentinelSegment), 306344779Sdim Freelist(&SentinelSegment), 307344779Sdim Size(0) {} 308344779Sdim 309336817Sdim Array(const Array &) = delete; 310344779Sdim Array &operator=(const Array &) = delete; 311344779Sdim 312344779Sdim Array(Array &&O) XRAY_NEVER_INSTRUMENT : Alloc(O.Alloc), 313344779Sdim Head(O.Head), 314344779Sdim Tail(O.Tail), 315344779Sdim Freelist(O.Freelist), 316344779Sdim Size(O.Size) { 317344779Sdim O.Alloc = nullptr; 318336817Sdim O.Head = &SentinelSegment; 319336817Sdim O.Tail = &SentinelSegment; 320336817Sdim O.Size = 0; 321344779Sdim O.Freelist = &SentinelSegment; 322336817Sdim } 323336817Sdim 324344779Sdim Array &operator=(Array &&O) XRAY_NEVER_INSTRUMENT { 325344779Sdim Alloc = O.Alloc; 326344779Sdim O.Alloc = nullptr; 327344779Sdim Head = O.Head; 328344779Sdim O.Head = &SentinelSegment; 329344779Sdim Tail = O.Tail; 330344779Sdim O.Tail = &SentinelSegment; 331344779Sdim Freelist = O.Freelist; 332344779Sdim O.Freelist = &SentinelSegment; 333344779Sdim Size = O.Size; 334344779Sdim O.Size = 0; 335344779Sdim return *this; 336344779Sdim } 337336817Sdim 338344779Sdim ~Array() XRAY_NEVER_INSTRUMENT { 339344779Sdim for (auto &E : *this) 340344779Sdim (&E)->~T(); 341344779Sdim } 342344779Sdim 343344779Sdim bool empty() const XRAY_NEVER_INSTRUMENT { return Size == 0; } 344344779Sdim 345344779Sdim AllocatorType &allocator() const XRAY_NEVER_INSTRUMENT { 346336817Sdim DCHECK_NE(Alloc, nullptr); 347336817Sdim return *Alloc; 348336817Sdim } 349336817Sdim 350344779Sdim uint64_t size() const XRAY_NEVER_INSTRUMENT { return Size; } 351336817Sdim 352344779Sdim template <class... Args> 353344779Sdim T *AppendEmplace(Args &&... args) XRAY_NEVER_INSTRUMENT { 354344779Sdim DCHECK((Size == 0 && Head == &SentinelSegment && Head == Tail) || 355344779Sdim (Size != 0 && Head != &SentinelSegment && Tail != &SentinelSegment)); 356344779Sdim if (UNLIKELY(Head == &SentinelSegment)) { 357344779Sdim auto R = InitHeadAndTail(); 358344779Sdim if (R == nullptr) 359336817Sdim return nullptr; 360344779Sdim } 361336817Sdim 362344779Sdim DCHECK_NE(Head, &SentinelSegment); 363344779Sdim DCHECK_NE(Tail, &SentinelSegment); 364344779Sdim 365336817Sdim auto Offset = Size % ElementsPerSegment; 366336817Sdim if (UNLIKELY(Size != 0 && Offset == 0)) 367336817Sdim if (AppendNewSegment() == nullptr) 368336817Sdim return nullptr; 369336817Sdim 370344779Sdim DCHECK_NE(Tail, &SentinelSegment); 371344779Sdim auto Base = &Tail->Data; 372336817Sdim auto AlignedOffset = Base + (Offset * AlignedElementStorageSize); 373344779Sdim DCHECK_LE(AlignedOffset + sizeof(T), 374344779Sdim reinterpret_cast<unsigned char *>(Base) + SegmentSize); 375344779Sdim 376344779Sdim // In-place construct at Position. 377344779Sdim new (AlignedOffset) T{std::forward<Args>(args)...}; 378336817Sdim ++Size; 379344779Sdim return reinterpret_cast<T *>(AlignedOffset); 380336817Sdim } 381336817Sdim 382344779Sdim T *Append(const T &E) XRAY_NEVER_INSTRUMENT { 383344779Sdim // FIXME: This is a duplication of AppenEmplace with the copy semantics 384344779Sdim // explicitly used, as a work-around to GCC 4.8 not invoking the copy 385344779Sdim // constructor with the placement new with braced-init syntax. 386344779Sdim DCHECK((Size == 0 && Head == &SentinelSegment && Head == Tail) || 387344779Sdim (Size != 0 && Head != &SentinelSegment && Tail != &SentinelSegment)); 388344779Sdim if (UNLIKELY(Head == &SentinelSegment)) { 389344779Sdim auto R = InitHeadAndTail(); 390344779Sdim if (R == nullptr) 391336817Sdim return nullptr; 392344779Sdim } 393336817Sdim 394344779Sdim DCHECK_NE(Head, &SentinelSegment); 395344779Sdim DCHECK_NE(Tail, &SentinelSegment); 396344779Sdim 397336817Sdim auto Offset = Size % ElementsPerSegment; 398344779Sdim if (UNLIKELY(Size != 0 && Offset == 0)) 399344779Sdim if (AppendNewSegment() == nullptr) 400336817Sdim return nullptr; 401336817Sdim 402336817Sdim DCHECK_NE(Tail, &SentinelSegment); 403344779Sdim auto Base = &Tail->Data; 404336817Sdim auto AlignedOffset = Base + (Offset * AlignedElementStorageSize); 405344779Sdim DCHECK_LE(AlignedOffset + sizeof(T), 406344779Sdim reinterpret_cast<unsigned char *>(Tail) + SegmentSize); 407336817Sdim 408336817Sdim // In-place construct at Position. 409344779Sdim new (AlignedOffset) T(E); 410336817Sdim ++Size; 411344779Sdim return reinterpret_cast<T *>(AlignedOffset); 412336817Sdim } 413336817Sdim 414344779Sdim T &operator[](uint64_t Offset) const XRAY_NEVER_INSTRUMENT { 415336817Sdim DCHECK_LE(Offset, Size); 416336817Sdim // We need to traverse the array enough times to find the element at Offset. 417336817Sdim auto S = Head; 418336817Sdim while (Offset >= ElementsPerSegment) { 419336817Sdim S = S->Next; 420336817Sdim Offset -= ElementsPerSegment; 421336817Sdim DCHECK_NE(S, &SentinelSegment); 422336817Sdim } 423344779Sdim auto Base = &S->Data; 424336817Sdim auto AlignedOffset = Base + (Offset * AlignedElementStorageSize); 425336817Sdim auto Position = reinterpret_cast<T *>(AlignedOffset); 426336817Sdim return *reinterpret_cast<T *>(Position); 427336817Sdim } 428336817Sdim 429344779Sdim T &front() const XRAY_NEVER_INSTRUMENT { 430336817Sdim DCHECK_NE(Head, &SentinelSegment); 431336817Sdim DCHECK_NE(Size, 0u); 432336817Sdim return *begin(); 433336817Sdim } 434336817Sdim 435344779Sdim T &back() const XRAY_NEVER_INSTRUMENT { 436336817Sdim DCHECK_NE(Tail, &SentinelSegment); 437336817Sdim DCHECK_NE(Size, 0u); 438336817Sdim auto It = end(); 439336817Sdim --It; 440336817Sdim return *It; 441336817Sdim } 442336817Sdim 443344779Sdim template <class Predicate> 444344779Sdim T *find_element(Predicate P) const XRAY_NEVER_INSTRUMENT { 445336817Sdim if (empty()) 446336817Sdim return nullptr; 447336817Sdim 448336817Sdim auto E = end(); 449336817Sdim for (auto I = begin(); I != E; ++I) 450336817Sdim if (P(*I)) 451336817Sdim return &(*I); 452336817Sdim 453336817Sdim return nullptr; 454336817Sdim } 455336817Sdim 456336817Sdim /// Remove N Elements from the end. This leaves the blocks behind, and not 457336817Sdim /// require allocation of new blocks for new elements added after trimming. 458344779Sdim void trim(uint64_t Elements) XRAY_NEVER_INSTRUMENT { 459336817Sdim auto OldSize = Size; 460344779Sdim Elements = Elements > Size ? Size : Elements; 461336817Sdim Size -= Elements; 462336817Sdim 463344779Sdim // We compute the number of segments we're going to return from the tail by 464344779Sdim // counting how many elements have been trimmed. Given the following: 465344779Sdim // 466344779Sdim // - Each segment has N valid positions, where N > 0 467344779Sdim // - The previous size > current size 468344779Sdim // 469344779Sdim // To compute the number of segments to return, we need to perform the 470344779Sdim // following calculations for the number of segments required given 'x' 471344779Sdim // elements: 472344779Sdim // 473344779Sdim // f(x) = { 474344779Sdim // x == 0 : 0 475344779Sdim // , 0 < x <= N : 1 476344779Sdim // , N < x <= max : x / N + (x % N ? 1 : 0) 477344779Sdim // } 478344779Sdim // 479344779Sdim // We can simplify this down to: 480344779Sdim // 481344779Sdim // f(x) = { 482344779Sdim // x == 0 : 0, 483344779Sdim // , 0 < x <= max : x / N + (x < N || x % N ? 1 : 0) 484344779Sdim // } 485344779Sdim // 486344779Sdim // And further down to: 487344779Sdim // 488344779Sdim // f(x) = x ? x / N + (x < N || x % N ? 1 : 0) : 0 489344779Sdim // 490344779Sdim // We can then perform the following calculation `s` which counts the number 491344779Sdim // of segments we need to remove from the end of the data structure: 492344779Sdim // 493344779Sdim // s(p, c) = f(p) - f(c) 494344779Sdim // 495344779Sdim // If we treat p = previous size, and c = current size, and given the 496344779Sdim // properties above, the possible range for s(...) is [0..max(typeof(p))/N] 497344779Sdim // given that typeof(p) == typeof(c). 498344779Sdim auto F = [](uint64_t X) { 499344779Sdim return X ? (X / ElementsPerSegment) + 500344779Sdim (X < ElementsPerSegment || X % ElementsPerSegment ? 1 : 0) 501344779Sdim : 0; 502344779Sdim }; 503344779Sdim auto PS = F(OldSize); 504344779Sdim auto CS = F(Size); 505344779Sdim DCHECK_GE(PS, CS); 506344779Sdim auto SegmentsToTrim = PS - CS; 507344779Sdim for (auto I = 0uL; I < SegmentsToTrim; ++I) { 508344779Sdim // Here we place the current tail segment to the freelist. To do this 509344779Sdim // appropriately, we need to perform a splice operation on two 510344779Sdim // bidirectional linked-lists. In particular, we have the current state of 511344779Sdim // the doubly-linked list of segments: 512344779Sdim // 513344779Sdim // @S@ <- s0 <-> s1 <-> ... <-> sT -> @S@ 514344779Sdim // 515336817Sdim DCHECK_NE(Head, &SentinelSegment); 516336817Sdim DCHECK_NE(Tail, &SentinelSegment); 517344779Sdim DCHECK_EQ(Tail->Next, &SentinelSegment); 518336817Sdim 519344779Sdim if (Freelist == &SentinelSegment) { 520344779Sdim // Our two lists at this point are in this configuration: 521344779Sdim // 522344779Sdim // Freelist: (potentially) @S@ 523344779Sdim // Mainlist: @S@<-s0<->s1<->...<->sPT<->sT->@S@ 524344779Sdim // ^ Head ^ Tail 525344779Sdim // 526344779Sdim // The end state for us will be this configuration: 527344779Sdim // 528344779Sdim // Freelist: @S@<-sT->@S@ 529344779Sdim // Mainlist: @S@<-s0<->s1<->...<->sPT->@S@ 530344779Sdim // ^ Head ^ Tail 531344779Sdim // 532344779Sdim // The first step for us is to hold a reference to the tail of Mainlist, 533344779Sdim // which in our notation is represented by sT. We call this our "free 534344779Sdim // segment" which is the segment we are placing on the Freelist. 535344779Sdim // 536344779Sdim // sF = sT 537344779Sdim // 538344779Sdim // Then, we also hold a reference to the "pre-tail" element, which we 539344779Sdim // call sPT: 540344779Sdim // 541344779Sdim // sPT = pred(sT) 542344779Sdim // 543344779Sdim // We want to splice sT into the beginning of the Freelist, which in 544344779Sdim // an empty Freelist means placing a segment whose predecessor and 545344779Sdim // successor is the sentinel segment. 546344779Sdim // 547344779Sdim // The splice operation then can be performed in the following 548344779Sdim // algorithm: 549344779Sdim // 550344779Sdim // succ(sPT) = S 551344779Sdim // pred(sT) = S 552344779Sdim // succ(sT) = Freelist 553344779Sdim // Freelist = sT 554344779Sdim // Tail = sPT 555344779Sdim // 556344779Sdim auto SPT = Tail->Prev; 557344779Sdim SPT->Next = &SentinelSegment; 558344779Sdim Tail->Prev = &SentinelSegment; 559344779Sdim Tail->Next = Freelist; 560344779Sdim Freelist = Tail; 561344779Sdim Tail = SPT; 562344779Sdim 563344779Sdim // Our post-conditions here are: 564344779Sdim DCHECK_EQ(Tail->Next, &SentinelSegment); 565344779Sdim DCHECK_EQ(Freelist->Prev, &SentinelSegment); 566344779Sdim } else { 567344779Sdim // In the other case, where the Freelist is not empty, we perform the 568344779Sdim // following transformation instead: 569344779Sdim // 570344779Sdim // This transforms the current state: 571344779Sdim // 572344779Sdim // Freelist: @S@<-f0->@S@ 573344779Sdim // ^ Freelist 574344779Sdim // Mainlist: @S@<-s0<->s1<->...<->sPT<->sT->@S@ 575344779Sdim // ^ Head ^ Tail 576344779Sdim // 577344779Sdim // Into the following: 578344779Sdim // 579344779Sdim // Freelist: @S@<-sT<->f0->@S@ 580344779Sdim // ^ Freelist 581344779Sdim // Mainlist: @S@<-s0<->s1<->...<->sPT->@S@ 582344779Sdim // ^ Head ^ Tail 583344779Sdim // 584344779Sdim // The algorithm is: 585344779Sdim // 586344779Sdim // sFH = Freelist 587344779Sdim // sPT = pred(sT) 588344779Sdim // pred(SFH) = sT 589344779Sdim // succ(sT) = Freelist 590344779Sdim // pred(sT) = S 591344779Sdim // succ(sPT) = S 592344779Sdim // Tail = sPT 593344779Sdim // Freelist = sT 594344779Sdim // 595344779Sdim auto SFH = Freelist; 596344779Sdim auto SPT = Tail->Prev; 597344779Sdim auto ST = Tail; 598344779Sdim SFH->Prev = ST; 599344779Sdim ST->Next = Freelist; 600344779Sdim ST->Prev = &SentinelSegment; 601344779Sdim SPT->Next = &SentinelSegment; 602344779Sdim Tail = SPT; 603344779Sdim Freelist = ST; 604344779Sdim 605344779Sdim // Our post-conditions here are: 606344779Sdim DCHECK_EQ(Tail->Next, &SentinelSegment); 607344779Sdim DCHECK_EQ(Freelist->Prev, &SentinelSegment); 608344779Sdim DCHECK_EQ(Freelist->Next->Prev, Freelist); 609344779Sdim } 610336817Sdim } 611344779Sdim 612344779Sdim // Now in case we've spliced all the segments in the end, we ensure that the 613344779Sdim // main list is "empty", or both the head and tail pointing to the sentinel 614344779Sdim // segment. 615344779Sdim if (Tail == &SentinelSegment) 616344779Sdim Head = Tail; 617344779Sdim 618344779Sdim DCHECK( 619344779Sdim (Size == 0 && Head == &SentinelSegment && Tail == &SentinelSegment) || 620344779Sdim (Size != 0 && Head != &SentinelSegment && Tail != &SentinelSegment)); 621344779Sdim DCHECK( 622344779Sdim (Freelist != &SentinelSegment && Freelist->Prev == &SentinelSegment) || 623344779Sdim (Freelist == &SentinelSegment && Tail->Next == &SentinelSegment)); 624336817Sdim } 625336817Sdim 626336817Sdim // Provide iterators. 627344779Sdim Iterator<T> begin() const XRAY_NEVER_INSTRUMENT { 628344779Sdim return Iterator<T>(Head, 0, Size); 629344779Sdim } 630344779Sdim Iterator<T> end() const XRAY_NEVER_INSTRUMENT { 631344779Sdim return Iterator<T>(Tail, Size, Size); 632344779Sdim } 633344779Sdim Iterator<const T> cbegin() const XRAY_NEVER_INSTRUMENT { 634344779Sdim return Iterator<const T>(Head, 0, Size); 635344779Sdim } 636344779Sdim Iterator<const T> cend() const XRAY_NEVER_INSTRUMENT { 637344779Sdim return Iterator<const T>(Tail, Size, Size); 638344779Sdim } 639336817Sdim}; 640336817Sdim 641336817Sdim// We need to have this storage definition out-of-line so that the compiler can 642336817Sdim// ensure that storage for the SentinelSegment is defined and has a single 643336817Sdim// address. 644336817Sdimtemplate <class T> 645344779Sdimtypename Array<T>::Segment Array<T>::SentinelSegment{ 646344779Sdim &Array<T>::SentinelSegment, &Array<T>::SentinelSegment, {'\0'}}; 647336817Sdim 648336817Sdim} // namespace __xray 649336817Sdim 650336817Sdim#endif // XRAY_SEGMENTED_ARRAY_H 651