1249423Sdim//===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===// 2212795Sdim// 3212795Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4212795Sdim// See https://llvm.org/LICENSE.txt for license information. 5212795Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6212795Sdim// 7212795Sdim//===----------------------------------------------------------------------===// 8212795Sdim/// 9212795Sdim/// \file 10212795Sdim/// This file implements a coalescing interval map for small objects. 11212795Sdim/// 12212795Sdim/// KeyT objects are mapped to ValT objects. Intervals of keys that map to the 13212795Sdim/// same value are represented in a compressed form. 14212795Sdim/// 15212795Sdim/// Iterators provide ordered access to the compressed intervals rather than the 16226633Sdim/// individual keys, and insert and erase operations use key intervals as well. 17212795Sdim/// 18212795Sdim/// Like SmallVector, IntervalMap will store the first N intervals in the map 19212795Sdim/// object itself without any allocations. When space is exhausted it switches 20212795Sdim/// to a B+-tree representation with very small overhead for small key and 21212795Sdim/// value objects. 22221345Sdim/// 23212795Sdim/// A Traits class specifies how keys are compared. It also allows IntervalMap 24212795Sdim/// to work with both closed and half-open intervals. 25249423Sdim/// 26212795Sdim/// Keys and values are not stored next to each other in a std::pair, so we 27212795Sdim/// don't provide such a value_type. Dereferencing iterators only returns the 28212795Sdim/// mapped value. The interval bounds are accessible through the start() and 29243830Sdim/// stop() iterator methods. 30212795Sdim/// 31221345Sdim/// IntervalMap is optimized for small key and value objects, 4 or 8 bytes 32249423Sdim/// each is the optimal size. For large objects use std::map instead. 33249423Sdim// 34249423Sdim//===----------------------------------------------------------------------===// 35249423Sdim// 36249423Sdim// Synopsis: 37249423Sdim// 38249423Sdim// template <typename KeyT, typename ValT, unsigned N, typename Traits> 39249423Sdim// class IntervalMap { 40249423Sdim// public: 41249423Sdim// typedef KeyT key_type; 42249423Sdim// typedef ValT mapped_type; 43249423Sdim// typedef RecyclingAllocator<...> Allocator; 44249423Sdim// class iterator; 45212795Sdim// class const_iterator; 46212795Sdim// 47212795Sdim// explicit IntervalMap(Allocator&); 48218893Sdim// ~IntervalMap(): 49249423Sdim// 50218893Sdim// bool empty() const; 51234982Sdim// KeyT start() const; 52218893Sdim// KeyT stop() const; 53212795Sdim// ValT lookup(KeyT x, Value NotFound = Value()) const; 54249423Sdim// 55212795Sdim// const_iterator begin() const; 56218893Sdim// const_iterator end() const; 57212795Sdim// iterator begin(); 58212795Sdim// iterator end(); 59226633Sdim// const_iterator find(KeyT x) const; 60249423Sdim// iterator find(KeyT x); 61212795Sdim// 62212795Sdim// void insert(KeyT a, KeyT b, ValT y); 63212795Sdim// void clear(); 64212795Sdim// }; 65212795Sdim// 66212795Sdim// template <typename KeyT, typename ValT, unsigned N, typename Traits> 67212795Sdim// class IntervalMap::const_iterator { 68243830Sdim// public: 69243830Sdim// using iterator_category = std::bidirectional_iterator_tag; 70243830Sdim// using value_type = ValT; 71243830Sdim// using difference_type = std::ptrdiff_t; 72243830Sdim// using pointer = value_type *; 73243830Sdim// using reference = value_type &; 74243830Sdim// 75243830Sdim// bool operator==(const const_iterator &) const; 76243830Sdim// bool operator!=(const const_iterator &) const; 77243830Sdim// bool valid() const; 78243830Sdim// 79243830Sdim// const KeyT &start() const; 80243830Sdim// const KeyT &stop() const; 81243830Sdim// const ValT &value() const; 82243830Sdim// const ValT &operator*() const; 83243830Sdim// const ValT *operator->() const; 84243830Sdim// 85243830Sdim// const_iterator &operator++(); 86243830Sdim// const_iterator &operator++(int); 87243830Sdim// const_iterator &operator--(); 88243830Sdim// const_iterator &operator--(int); 89243830Sdim// void goToBegin(); 90226633Sdim// void goToEnd(); 91212795Sdim// void find(KeyT x); 92212795Sdim// void advanceTo(KeyT x); 93243830Sdim// }; 94243830Sdim// 95243830Sdim// template <typename KeyT, typename ValT, unsigned N, typename Traits> 96243830Sdim// class IntervalMap::iterator : public const_iterator { 97243830Sdim// public: 98243830Sdim// void insert(KeyT a, KeyT b, Value y); 99212795Sdim// void erase(); 100212795Sdim// }; 101226633Sdim// 102226633Sdim//===----------------------------------------------------------------------===// 103226633Sdim 104239462Sdim#ifndef LLVM_ADT_INTERVALMAP_H 105243830Sdim#define LLVM_ADT_INTERVALMAP_H 106243830Sdim 107243830Sdim#include "llvm/ADT/PointerIntPair.h" 108239462Sdim#include "llvm/ADT/SmallVector.h" 109239462Sdim#include "llvm/Support/Allocator.h" 110239462Sdim#include "llvm/Support/RecyclingAllocator.h" 111243830Sdim#include <algorithm> 112249423Sdim#include <cassert> 113249423Sdim#include <iterator> 114249423Sdim#include <new> 115249423Sdim#include <utility> 116249423Sdim 117249423Sdimnamespace llvm { 118249423Sdim 119249423Sdim//===----------------------------------------------------------------------===// 120212795Sdim//--- Key traits ---// 121212795Sdim//===----------------------------------------------------------------------===// 122212795Sdim// 123243830Sdim// The IntervalMap works with closed or half-open intervals. 124243830Sdim// Adjacent intervals that map to the same value are coalesced. 125243830Sdim// 126243830Sdim// The IntervalMapInfo traits class is used to determine if a key is contained 127243830Sdim// in an interval, and if two intervals are adjacent so they can be coalesced. 128243830Sdim// The provided implementation works for closed integer intervals, other keys 129243830Sdim// probably need a specialized version. 130243830Sdim// 131243830Sdim// The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x). 132243830Sdim// 133243830Sdim// It is assumed that (a;b] half-open intervals are not used, only [a;b) is 134243830Sdim// allowed. This is so that stopLess(a, b) can be used to determine if two 135243830Sdim// intervals overlap. 136243830Sdim// 137243830Sdim//===----------------------------------------------------------------------===// 138243830Sdim 139212795Sdimtemplate <typename T> 140243830Sdimstruct IntervalMapInfo { 141243830Sdim /// startLess - Return true if x is not in [a;b]. 142243830Sdim /// This is x < a both for closed intervals and for [a;b) half-open intervals. 143243830Sdim static inline bool startLess(const T &x, const T &a) { 144243830Sdim return x < a; 145243830Sdim } 146212795Sdim 147243830Sdim /// stopLess - Return true if x is not in [a;b]. 148243830Sdim /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals. 149243830Sdim static inline bool stopLess(const T &b, const T &x) { 150243830Sdim return b < x; 151243830Sdim } 152243830Sdim 153243830Sdim /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce. 154243830Sdim /// This is a+1 == b for closed intervals, a == b for half-open intervals. 155212795Sdim static inline bool adjacent(const T &a, const T &b) { 156243830Sdim return a+1 == b; 157243830Sdim } 158243830Sdim 159243830Sdim /// nonEmpty - Return true if [a;b] is non-empty. 160243830Sdim /// This is a <= b for a closed interval, a < b for [a;b) half-open intervals. 161243830Sdim static inline bool nonEmpty(const T &a, const T &b) { 162243830Sdim return a <= b; 163243830Sdim } 164212795Sdim}; 165243830Sdim 166243830Sdimtemplate <typename T> 167243830Sdimstruct IntervalMapHalfOpenInfo { 168243830Sdim /// startLess - Return true if x is not in [a;b). 169243830Sdim static inline bool startLess(const T &x, const T &a) { 170243830Sdim return x < a; 171212795Sdim } 172243830Sdim 173243830Sdim /// stopLess - Return true if x is not in [a;b). 174243830Sdim static inline bool stopLess(const T &b, const T &x) { 175243830Sdim return b <= x; 176212795Sdim } 177212795Sdim 178243830Sdim /// adjacent - Return true when the intervals [x;a) and [b;y) can coalesce. 179243830Sdim static inline bool adjacent(const T &a, const T &b) { 180243830Sdim return a == b; 181243830Sdim } 182243830Sdim 183212795Sdim /// nonEmpty - Return true if [a;b) is non-empty. 184212795Sdim static inline bool nonEmpty(const T &a, const T &b) { 185243830Sdim return a < b; 186243830Sdim } 187243830Sdim}; 188243830Sdim 189212795Sdim/// IntervalMapImpl - Namespace used for IntervalMap implementation details. 190212795Sdim/// It should be considered private to the implementation. 191212795Sdimnamespace IntervalMapImpl { 192243830Sdim 193243830Sdimusing IdxPair = std::pair<unsigned,unsigned>; 194212795Sdim 195243830Sdim//===----------------------------------------------------------------------===// 196243830Sdim//--- IntervalMapImpl::NodeBase ---// 197243830Sdim//===----------------------------------------------------------------------===// 198243830Sdim// 199243830Sdim// Both leaf and branch nodes store vectors of pairs. 200243830Sdim// Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT). 201243830Sdim// 202212795Sdim// Keys and values are stored in separate arrays to avoid padding caused by 203243830Sdim// different object alignments. This also helps improve locality of reference 204243830Sdim// when searching the keys. 205243830Sdim// 206243830Sdim// The nodes don't know how many elements they contain - that information is 207243830Sdim// stored elsewhere. Omitting the size field prevents padding and allows a node 208243830Sdim// to fill the allocated cache lines completely. 209212795Sdim// 210243830Sdim// These are typical key and value sizes, the node branching factor (N), and 211243830Sdim// wasted space when nodes are sized to fit in three cache lines (192 bytes): 212243830Sdim// 213263508Sdim// T1 T2 N Waste Used by 214263508Sdim// 4 4 24 0 Branch<4> (32-bit pointers) 215243830Sdim// 8 4 16 0 Leaf<4,4>, Branch<4> 216212795Sdim// 8 8 12 0 Leaf<4,8>, Branch<8> 217243830Sdim// 16 4 9 12 Leaf<8,4> 218243830Sdim// 16 8 8 0 Leaf<8,8> 219243830Sdim// 220243830Sdim//===----------------------------------------------------------------------===// 221243830Sdim 222243830Sdimtemplate <typename T1, typename T2, unsigned N> 223243830Sdimclass NodeBase { 224243830Sdimpublic: 225218893Sdim enum { Capacity = N }; 226243830Sdim 227243830Sdim T1 first[N]; 228243830Sdim T2 second[N]; 229218893Sdim 230243830Sdim /// copy - Copy elements from another node. 231243830Sdim /// @param Other Node elements are copied from. 232243830Sdim /// @param i Beginning of the source range in other. 233243830Sdim /// @param j Beginning of the destination range in this. 234218893Sdim /// @param Count Number of elements to copy. 235243830Sdim template <unsigned M> 236218893Sdim void copy(const NodeBase<T1, T2, M> &Other, unsigned i, 237218893Sdim unsigned j, unsigned Count) { 238243830Sdim assert(i + Count <= M && "Invalid source range"); 239243830Sdim assert(j + Count <= N && "Invalid dest range"); 240243830Sdim for (unsigned e = i + Count; i != e; ++i, ++j) { 241243830Sdim first[j] = Other.first[i]; 242243830Sdim second[j] = Other.second[i]; 243243830Sdim } 244243830Sdim } 245243830Sdim 246212795Sdim /// moveLeft - Move elements to the left. 247212795Sdim /// @param i Beginning of the source range. 248243830Sdim /// @param j Beginning of the destination range. 249243830Sdim /// @param Count Number of elements to copy. 250243830Sdim void moveLeft(unsigned i, unsigned j, unsigned Count) { 251243830Sdim assert(j <= i && "Use moveRight shift elements right"); 252243830Sdim copy(*this, i, j, Count); 253243830Sdim } 254243830Sdim 255243830Sdim /// moveRight - Move elements to the right. 256243830Sdim /// @param i Beginning of the source range. 257243830Sdim /// @param j Beginning of the destination range. 258243830Sdim /// @param Count Number of elements to copy. 259243830Sdim void moveRight(unsigned i, unsigned j, unsigned Count) { 260243830Sdim assert(i <= j && "Use moveLeft shift elements left"); 261243830Sdim assert(j + Count <= N && "Invalid range"); 262251662Sdim while (Count--) { 263251662Sdim first[j + Count] = first[i + Count]; 264243830Sdim second[j + Count] = second[i + Count]; 265243830Sdim } 266243830Sdim } 267243830Sdim 268243830Sdim /// erase - Erase elements [i;j). 269243830Sdim /// @param i Beginning of the range to erase. 270212795Sdim /// @param j End of the range. (Exclusive). 271243830Sdim /// @param Size Number of elements in node. 272243830Sdim void erase(unsigned i, unsigned j, unsigned Size) { 273243830Sdim moveLeft(j, i, Size - j); 274243830Sdim } 275212795Sdim 276243830Sdim /// erase - Erase element at i. 277243830Sdim /// @param i Index of element to erase. 278243830Sdim /// @param Size Number of elements in node. 279243830Sdim void erase(unsigned i, unsigned Size) { 280243830Sdim erase(i, i+1, Size); 281243830Sdim } 282243830Sdim 283212795Sdim /// shift - Shift elements [i;size) 1 position to the right. 284243830Sdim /// @param i Beginning of the range to move. 285243830Sdim /// @param Size Number of elements in node. 286243830Sdim void shift(unsigned i, unsigned Size) { 287243830Sdim moveRight(i, i + 1, Size - i); 288243830Sdim } 289243830Sdim 290243830Sdim /// transferToLeftSib - Transfer elements to a left sibling node. 291243830Sdim /// @param Size Number of elements in this. 292243830Sdim /// @param Sib Left sibling node. 293243830Sdim /// @param SSize Number of elements in sib. 294243830Sdim /// @param Count Number of elements to transfer. 295243830Sdim void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, 296212795Sdim unsigned Count) { 297212795Sdim Sib.copy(*this, 0, SSize, Count); 298243830Sdim erase(0, Count, Size); 299243830Sdim } 300243830Sdim 301243830Sdim /// transferToRightSib - Transfer elements to a right sibling node. 302243830Sdim /// @param Size Number of elements in this. 303243830Sdim /// @param Sib Right sibling node. 304243830Sdim /// @param SSize Number of elements in sib. 305243830Sdim /// @param Count Number of elements to transfer. 306243830Sdim void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize, 307212795Sdim unsigned Count) { 308243830Sdim Sib.moveRight(0, Count, SSize); 309243830Sdim Sib.copy(*this, Size-Count, 0, Count); 310243830Sdim } 311212795Sdim 312212795Sdim /// adjustFromLeftSib - Adjust the number if elements in this node by moving 313243830Sdim /// elements to or from a left sibling node. 314243830Sdim /// @param Size Number of elements in this. 315243830Sdim /// @param Sib Right sibling node. 316243830Sdim /// @param SSize Number of elements in sib. 317212795Sdim /// @param Add The number of elements to add to this node, possibly < 0. 318243830Sdim /// @return Number of elements added to this node, possibly negative. 319212795Sdim int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) { 320212795Sdim if (Add > 0) { 321243830Sdim // We want to grow, copy from sib. 322243830Sdim unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size); 323243830Sdim Sib.transferToRightSib(SSize, *this, Size, Count); 324243830Sdim return Count; 325243830Sdim } else { 326212795Sdim // We want to shrink, copy to sib. 327243830Sdim unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize); 328212795Sdim transferToLeftSib(Size, Sib, SSize, Count); 329251662Sdim return -Count; 330251662Sdim } 331251662Sdim } 332251662Sdim}; 333251662Sdim 334251662Sdim/// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes. 335251662Sdim/// @param Node Array of pointers to sibling nodes. 336251662Sdim/// @param Nodes Number of nodes. 337251662Sdim/// @param CurSize Array of current node sizes, will be overwritten. 338243830Sdim/// @param NewSize Array of desired node sizes. 339243830Sdimtemplate <typename NodeT> 340243830Sdimvoid adjustSiblingSizes(NodeT *Node[], unsigned Nodes, 341243830Sdim unsigned CurSize[], const unsigned NewSize[]) { 342243830Sdim // Move elements right. 343212795Sdim for (int n = Nodes - 1; n; --n) { 344243830Sdim if (CurSize[n] == NewSize[n]) 345243830Sdim continue; 346243830Sdim for (int m = n - 1; m != -1; --m) { 347212795Sdim int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m], 348243830Sdim NewSize[n] - CurSize[n]); 349243830Sdim CurSize[m] -= d; 350243830Sdim CurSize[n] += d; 351243830Sdim // Keep going if the current node was exhausted. 352243830Sdim if (CurSize[n] >= NewSize[n]) 353212795Sdim break; 354243830Sdim } 355243830Sdim } 356243830Sdim 357243830Sdim if (Nodes == 0) 358243830Sdim return; 359243830Sdim 360243830Sdim // Move elements left. 361243830Sdim for (unsigned n = 0; n != Nodes - 1; ++n) { 362243830Sdim if (CurSize[n] == NewSize[n]) 363243830Sdim continue; 364243830Sdim for (unsigned m = n + 1; m != Nodes; ++m) { 365212795Sdim int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n], 366212795Sdim CurSize[n] - NewSize[n]); 367212795Sdim CurSize[m] += d; 368212795Sdim CurSize[n] -= d; 369212795Sdim // Keep going if the current node was exhausted. 370243830Sdim if (CurSize[n] >= NewSize[n]) 371243830Sdim break; 372243830Sdim } 373243830Sdim } 374243830Sdim 375243830Sdim#ifndef NDEBUG 376243830Sdim for (unsigned n = 0; n != Nodes; n++) 377243830Sdim assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle"); 378251662Sdim#endif 379251662Sdim} 380243830Sdim 381243830Sdim/// IntervalMapImpl::distribute - Compute a new distribution of node elements 382243830Sdim/// after an overflow or underflow. Reserve space for a new element at Position, 383212795Sdim/// and compute the node that will hold Position after redistributing node 384212795Sdim/// elements. 385212795Sdim/// 386212795Sdim/// It is required that 387212795Sdim/// 388212795Sdim/// Elements == sum(CurSize), and 389212795Sdim/// Elements + Grow <= Nodes * Capacity. 390212795Sdim/// 391212795Sdim/// NewSize[] will be filled in such that: 392212795Sdim/// 393212795Sdim/// sum(NewSize) == Elements, and 394212795Sdim/// NewSize[i] <= Capacity. 395212795Sdim/// 396212795Sdim/// The returned index is the node where Position will go, so: 397226633Sdim/// 398226633Sdim/// sum(NewSize[0..idx-1]) <= Position 399226633Sdim/// sum(NewSize[0..idx]) >= Position 400212795Sdim/// 401212795Sdim/// The last equality, sum(NewSize[0..idx]) == Position, can only happen when 402226633Sdim/// Grow is set and NewSize[idx] == Capacity-1. The index points to the node 403226633Sdim/// before the one holding the Position'th element where there is room for an 404226633Sdim/// insertion. 405226633Sdim/// 406226633Sdim/// @param Nodes The number of nodes. 407226633Sdim/// @param Elements Total elements in all nodes. 408226633Sdim/// @param Capacity The capacity of each node. 409212795Sdim/// @param CurSize Array[Nodes] of current node sizes, or NULL. 410226633Sdim/// @param NewSize Array[Nodes] to receive the new node sizes. 411226633Sdim/// @param Position Insert position. 412226633Sdim/// @param Grow Reserve space for a new element at Position. 413226633Sdim/// @return (node, offset) for Position. 414226633SdimIdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, 415226633Sdim const unsigned *CurSize, unsigned NewSize[], 416226633Sdim unsigned Position, bool Grow); 417226633Sdim 418226633Sdim//===----------------------------------------------------------------------===// 419226633Sdim//--- IntervalMapImpl::NodeSizer ---// 420226633Sdim//===----------------------------------------------------------------------===// 421212795Sdim// 422226633Sdim// Compute node sizes from key and value types. 423226633Sdim// 424226633Sdim// The branching factors are chosen to make nodes fit in three cache lines. 425226633Sdim// This may not be possible if keys or values are very large. Such large objects 426212795Sdim// are handled correctly, but a std::map would probably give better performance. 427226633Sdim// 428226633Sdim//===----------------------------------------------------------------------===// 429212795Sdim 430226633Sdimenum { 431226633Sdim // Cache line size. Most architectures have 32 or 64 byte cache lines. 432226633Sdim // We use 64 bytes here because it provides good branching factors. 433226633Sdim Log2CacheLine = 6, 434212795Sdim CacheLineBytes = 1 << Log2CacheLine, 435226633Sdim DesiredNodeBytes = 3 * CacheLineBytes 436212795Sdim}; 437226633Sdim 438251662Sdimtemplate <typename KeyT, typename ValT> 439251662Sdimstruct NodeSizer { 440251662Sdim enum { 441251662Sdim // Compute the leaf node branching factor that makes a node fit in three 442251662Sdim // cache lines. The branching factor must be at least 3, or some B+-tree 443251662Sdim // balancing algorithms won't work. 444212795Sdim // LeafSize can't be larger than CacheLineBytes. This is required by the 445226633Sdim // PointerIntPair used by NodeRef. 446226633Sdim DesiredLeafSize = DesiredNodeBytes / 447226633Sdim static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)), 448226633Sdim MinLeafSize = 3, 449226633Sdim LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize 450212795Sdim }; 451212795Sdim 452226633Sdim using LeafBase = NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize>; 453226633Sdim 454226633Sdim enum { 455226633Sdim // Now that we have the leaf branching factor, compute the actual allocation 456226633Sdim // unit size by rounding up to a whole number of cache lines. 457212795Sdim AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1), 458212795Sdim 459226633Sdim // Determine the branching factor for branch nodes. 460226633Sdim BranchSize = AllocBytes / 461212795Sdim static_cast<unsigned>(sizeof(KeyT) + sizeof(void*)) 462249423Sdim }; 463249423Sdim 464226633Sdim /// Allocator - The recycling allocator used for both branch and leaf nodes. 465212795Sdim /// This typedef is very likely to be identical for all IntervalMaps with 466226633Sdim /// reasonably sized entries, so the same allocator can be shared among 467249423Sdim /// different kinds of maps. 468226633Sdim using Allocator = 469226633Sdim RecyclingAllocator<BumpPtrAllocator, char, AllocBytes, CacheLineBytes>; 470226633Sdim}; 471226633Sdim 472226633Sdim//===----------------------------------------------------------------------===// 473212795Sdim//--- IntervalMapImpl::NodeRef ---// 474249423Sdim//===----------------------------------------------------------------------===// 475249423Sdim// 476226633Sdim// B+-tree nodes can be leaves or branches, so we need a polymorphic node 477249423Sdim// pointer that can point to both kinds. 478226633Sdim// 479212795Sdim// All nodes are cache line aligned and the low 6 bits of a node pointer are 480249423Sdim// always 0. These bits are used to store the number of elements in the 481249423Sdim// referenced node. Besides saving space, placing node sizes in the parents 482249423Sdim// allow tree balancing algorithms to run without faulting cache lines for nodes 483249423Sdim// that may not need to be modified. 484249423Sdim// 485249423Sdim// A NodeRef doesn't know whether it references a leaf node or a branch node. 486249423Sdim// It is the responsibility of the caller to use the correct types. 487249423Sdim// 488249423Sdim// Nodes are never supposed to be empty, and it is invalid to store a node size 489249423Sdim// of 0 in a NodeRef. The valid range of sizes is 1-64. 490226633Sdim// 491226633Sdim//===----------------------------------------------------------------------===// 492226633Sdim 493226633Sdimclass NodeRef { 494226633Sdim struct CacheAlignedPointerTraits { 495226633Sdim static inline void *getAsVoidPointer(void *P) { return P; } 496212795Sdim static inline void *getFromVoidPointer(void *P) { return P; } 497226633Sdim static constexpr int NumLowBitsAvailable = Log2CacheLine; 498226633Sdim }; 499212795Sdim PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip; 500226633Sdim 501226633Sdimpublic: 502226633Sdim /// NodeRef - Create a null ref. 503226633Sdim NodeRef() = default; 504212795Sdim 505234353Sdim /// operator bool - Detect a null ref. 506249423Sdim explicit operator bool() const { return pip.getOpaqueValue(); } 507234353Sdim 508234353Sdim /// NodeRef - Create a reference to the node p with n elements. 509212795Sdim template <typename NodeT> 510249423Sdim NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) { 511249423Sdim assert(n <= NodeT::Capacity && "Size too big for node"); 512249423Sdim } 513249423Sdim 514249423Sdim /// size - Return the number of elements in the referenced node. 515249423Sdim unsigned size() const { return pip.getInt() + 1; } 516249423Sdim 517212795Sdim /// setSize - Update the node size. 518212795Sdim void setSize(unsigned n) { pip.setInt(n - 1); } 519212795Sdim 520243830Sdim /// subtree - Access the i'th subtree reference in a branch node. 521226633Sdim /// This depends on branch nodes storing the NodeRef array as their first 522226633Sdim /// member. 523226633Sdim NodeRef &subtree(unsigned i) const { 524226633Sdim return reinterpret_cast<NodeRef*>(pip.getPointer())[i]; 525226633Sdim } 526226633Sdim 527226633Sdim /// get - Dereference as a NodeT reference. 528226633Sdim template <typename NodeT> 529226633Sdim NodeT &get() const { 530249423Sdim return *reinterpret_cast<NodeT*>(pip.getPointer()); 531249423Sdim } 532243830Sdim 533226633Sdim bool operator==(const NodeRef &RHS) const { 534212795Sdim if (pip == RHS.pip) 535226633Sdim return true; 536243830Sdim assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs"); 537212795Sdim return false; 538226633Sdim } 539226633Sdim 540226633Sdim bool operator!=(const NodeRef &RHS) const { 541234353Sdim return !operator==(RHS); 542249423Sdim } 543234353Sdim}; 544234353Sdim 545234353Sdim//===----------------------------------------------------------------------===// 546249423Sdim//--- IntervalMapImpl::LeafNode ---// 547249423Sdim//===----------------------------------------------------------------------===// 548249423Sdim// 549249423Sdim// Leaf nodes store up to N disjoint intervals with corresponding values. 550249423Sdim// 551249423Sdim// The intervals are kept sorted and fully coalesced so there are no adjacent 552212795Sdim// intervals mapping to the same value. 553226633Sdim// 554226633Sdim// These constraints are always satisfied: 555249423Sdim// 556226633Sdim// - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals. 557226633Sdim// 558226633Sdim// - Traits::stopLess(stop(i), start(i + 1) - Sorted. 559226633Sdim// 560226633Sdim// - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1)) 561226633Sdim// - Fully coalesced. 562226633Sdim// 563226633Sdim//===----------------------------------------------------------------------===// 564226633Sdim 565226633Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 566212795Sdimclass LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> { 567226633Sdimpublic: 568226633Sdim const KeyT &start(unsigned i) const { return this->first[i].first; } 569243830Sdim const KeyT &stop(unsigned i) const { return this->first[i].second; } 570249423Sdim const ValT &value(unsigned i) const { return this->second[i]; } 571249423Sdim 572249423Sdim KeyT &start(unsigned i) { return this->first[i].first; } 573249423Sdim KeyT &stop(unsigned i) { return this->first[i].second; } 574249423Sdim ValT &value(unsigned i) { return this->second[i]; } 575249423Sdim 576249423Sdim /// findFrom - Find the first interval after i that may contain x. 577249423Sdim /// @param i Starting index for the search. 578243830Sdim /// @param Size Number of elements in node. 579234353Sdim /// @param x Key to search for. 580249423Sdim /// @return First index with !stopLess(key[i].stop, x), or size. 581249423Sdim /// This is the first interval that can possibly contain x. 582249423Sdim unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { 583249423Sdim assert(i <= Size && Size <= N && "Bad indices"); 584249423Sdim assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 585249423Sdim "Index is past the needed point"); 586249423Sdim while (i != Size && Traits::stopLess(stop(i), x)) ++i; 587249423Sdim return i; 588249423Sdim } 589249423Sdim 590226633Sdim /// safeFind - Find an interval that is known to exist. This is the same as 591212795Sdim /// findFrom except is it assumed that x is at least within range of the last 592234353Sdim /// interval. 593234353Sdim /// @param i Starting index for the search. 594226633Sdim /// @param x Key to search for. 595226633Sdim /// @return First index with !stopLess(key[i].stop, x), never size. 596226633Sdim /// This is the first interval that can possibly contain x. 597226633Sdim unsigned safeFind(unsigned i, KeyT x) const { 598226633Sdim assert(i < N && "Bad index"); 599226633Sdim assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 600226633Sdim "Index is past the needed point"); 601212795Sdim while (Traits::stopLess(stop(i), x)) ++i; 602212795Sdim assert(i < N && "Unsafe intervals"); 603226633Sdim return i; 604226633Sdim } 605212795Sdim 606226633Sdim /// safeLookup - Lookup mapped value for a safe key. 607226633Sdim /// It is assumed that x is within range of the last entry. 608226633Sdim /// @param x Key to search for. 609226633Sdim /// @param NotFound Value to return if x is not in any interval. 610212795Sdim /// @return The mapped value at x or NotFound. 611226633Sdim ValT safeLookup(KeyT x, ValT NotFound) const { 612226633Sdim unsigned i = safeFind(0, x); 613226633Sdim return Traits::startLess(x, start(i)) ? NotFound : value(i); 614226633Sdim } 615226633Sdim 616226633Sdim unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y); 617226633Sdim}; 618226633Sdim 619226633Sdim/// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as 620226633Sdim/// possible. This may cause the node to grow by 1, or it may cause the node 621226633Sdim/// to shrink because of coalescing. 622226633Sdim/// @param Pos Starting index = insertFrom(0, size, a) 623226633Sdim/// @param Size Number of elements in node. 624226633Sdim/// @param a Interval start. 625226633Sdim/// @param b Interval stop. 626226633Sdim/// @param y Value be mapped. 627226633Sdim/// @return (insert position, new size), or (i, Capacity+1) on overflow. 628226633Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 629212795Sdimunsigned LeafNode<KeyT, ValT, N, Traits>:: 630212795SdiminsertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) { 631226633Sdim unsigned i = Pos; 632226633Sdim assert(i <= Size && Size <= N && "Invalid index"); 633218893Sdim assert(!Traits::stopLess(b, a) && "Invalid interval"); 634226633Sdim 635226633Sdim // Verify the findFrom invariant. 636226633Sdim assert((i == 0 || Traits::stopLess(stop(i - 1), a))); 637226633Sdim assert((i == Size || !Traits::stopLess(stop(i), a))); 638226633Sdim assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert"); 639226633Sdim 640226633Sdim // Coalesce with previous interval. 641226633Sdim if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) { 642226633Sdim Pos = i - 1; 643226633Sdim // Also coalesce with next interval? 644226633Sdim if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) { 645226633Sdim stop(i - 1) = stop(i); 646226633Sdim this->erase(i, Size); 647226633Sdim return Size - 1; 648226633Sdim } 649226633Sdim stop(i - 1) = b; 650226633Sdim return Size; 651226633Sdim } 652226633Sdim 653226633Sdim // Detect overflow. 654226633Sdim if (i == N) 655226633Sdim return N + 1; 656226633Sdim 657226633Sdim // Add new interval at end. 658226633Sdim if (i == Size) { 659226633Sdim start(i) = a; 660212795Sdim stop(i) = b; 661212795Sdim value(i) = y; 662226633Sdim return Size + 1; 663226633Sdim } 664212795Sdim 665226633Sdim // Try to coalesce with following interval. 666226633Sdim if (value(i) == y && Traits::adjacent(b, start(i))) { 667226633Sdim start(i) = a; 668226633Sdim return Size; 669226633Sdim } 670226633Sdim 671226633Sdim // We must insert before i. Detect overflow. 672212795Sdim if (Size == N) 673226633Sdim return N + 1; 674226633Sdim 675226633Sdim // Insert before i. 676218893Sdim this->shift(i, Size); 677226633Sdim start(i) = a; 678226633Sdim stop(i) = b; 679226633Sdim value(i) = y; 680226633Sdim return Size + 1; 681226633Sdim} 682226633Sdim 683226633Sdim//===----------------------------------------------------------------------===// 684226633Sdim//--- IntervalMapImpl::BranchNode ---// 685226633Sdim//===----------------------------------------------------------------------===// 686226633Sdim// 687226633Sdim// A branch node stores references to 1--N subtrees all of the same height. 688226633Sdim// 689226633Sdim// The key array in a branch node holds the rightmost stop key of each subtree. 690226633Sdim// It is redundant to store the last stop key since it can be found in the 691226633Sdim// parent node, but doing so makes tree balancing a lot simpler. 692226633Sdim// 693226633Sdim// It is unusual for a branch node to only have one subtree, but it can happen 694226633Sdim// in the root node if it is smaller than the normal nodes. 695226633Sdim// 696226633Sdim// When all of the leaf nodes from all the subtrees are concatenated, they must 697226633Sdim// satisfy the same constraints as a single leaf node. They must be sorted, 698226633Sdim// sane, and fully coalesced. 699226633Sdim// 700226633Sdim//===----------------------------------------------------------------------===// 701226633Sdim 702212795Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 703212795Sdimclass BranchNode : public NodeBase<NodeRef, KeyT, N> { 704226633Sdimpublic: 705226633Sdim const KeyT &stop(unsigned i) const { return this->second[i]; } 706212795Sdim const NodeRef &subtree(unsigned i) const { return this->first[i]; } 707226633Sdim 708226633Sdim KeyT &stop(unsigned i) { return this->second[i]; } 709226633Sdim NodeRef &subtree(unsigned i) { return this->first[i]; } 710234982Sdim 711226633Sdim /// findFrom - Find the first subtree after i that may contain x. 712226633Sdim /// @param i Starting index for the search. 713249423Sdim /// @param Size Number of elements in node. 714249423Sdim /// @param x Key to search for. 715226633Sdim /// @return First index with !stopLess(key[i], x), or size. 716226633Sdim /// This is the first subtree that can possibly contain x. 717212795Sdim unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { 718234353Sdim assert(i <= Size && Size <= N && "Bad indices"); 719249423Sdim assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 720212795Sdim "Index to findFrom is past the needed point"); 721212795Sdim while (i != Size && Traits::stopLess(stop(i), x)) ++i; 722212795Sdim return i; 723212795Sdim } 724212795Sdim 725212795Sdim /// safeFind - Find a subtree that is known to exist. This is the same as 726212795Sdim /// findFrom except is it assumed that x is in range. 727212795Sdim /// @param i Starting index for the search. 728249423Sdim /// @param x Key to search for. 729212795Sdim /// @return First index with !stopLess(key[i], x), never size. 730249423Sdim /// This is the first subtree that can possibly contain x. 731212795Sdim unsigned safeFind(unsigned i, KeyT x) const { 732212795Sdim assert(i < N && "Bad index"); 733212795Sdim assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 734212795Sdim "Index is past the needed point"); 735212795Sdim while (Traits::stopLess(stop(i), x)) ++i; 736249423Sdim assert(i < N && "Unsafe intervals"); 737249423Sdim return i; 738212795Sdim } 739212795Sdim 740212795Sdim /// safeLookup - Get the subtree containing x, Assuming that x is in range. 741212795Sdim /// @param x Key to search for. 742212795Sdim /// @return Subtree containing x 743212795Sdim NodeRef safeLookup(KeyT x) const { 744212795Sdim return subtree(safeFind(0, x)); 745249423Sdim } 746212795Sdim 747249423Sdim /// insert - Insert a new (subtree, stop) pair. 748212795Sdim /// @param i Insert position, following entries will be shifted. 749212795Sdim /// @param Size Number of elements in node. 750212795Sdim /// @param Node Subtree to insert. 751212795Sdim /// @param Stop Last key in subtree. 752212795Sdim void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) { 753212795Sdim assert(Size < N && "branch node overflow"); 754249423Sdim assert(i <= Size && "Bad insert position"); 755249423Sdim this->shift(i, Size); 756226633Sdim subtree(i) = Node; 757212795Sdim stop(i) = Stop; 758212795Sdim } 759212795Sdim}; 760212795Sdim 761212795Sdim//===----------------------------------------------------------------------===// 762226633Sdim//--- IntervalMapImpl::Path ---// 763221345Sdim//===----------------------------------------------------------------------===// 764263508Sdim// 765263508Sdim// A Path is used by iterators to represent a position in a B+-tree, and the 766263508Sdim// path to get there from the root. 767263508Sdim// 768212795Sdim// The Path class also contains the tree navigation code that doesn't have to 769212795Sdim// be templatized. 770221345Sdim// 771226633Sdim//===----------------------------------------------------------------------===// 772221345Sdim 773221345Sdimclass Path { 774221345Sdim /// Entry - Each step in the path is a node pointer and an offset into that 775221345Sdim /// node. 776221345Sdim struct Entry { 777221345Sdim void *node; 778212795Sdim unsigned size; 779212795Sdim unsigned offset; 780212795Sdim 781212795Sdim Entry(void *Node, unsigned Size, unsigned Offset) 782212795Sdim : node(Node), size(Size), offset(Offset) {} 783218893Sdim 784234353Sdim Entry(NodeRef Node, unsigned Offset) 785226633Sdim : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {} 786212795Sdim 787212795Sdim NodeRef &subtree(unsigned i) const { 788212795Sdim return reinterpret_cast<NodeRef*>(node)[i]; 789212795Sdim } 790212795Sdim }; 791212795Sdim 792212795Sdim /// path - The path entries, path[0] is the root node, path.back() is a leaf. 793212795Sdim SmallVector<Entry, 4> path; 794212795Sdim 795212795Sdimpublic: 796243830Sdim // Node accessors. 797224145Sdim template <typename NodeT> NodeT &node(unsigned Level) const { 798212795Sdim return *reinterpret_cast<NodeT*>(path[Level].node); 799212795Sdim } 800212795Sdim unsigned size(unsigned Level) const { return path[Level].size; } 801212795Sdim unsigned offset(unsigned Level) const { return path[Level].offset; } 802212795Sdim unsigned &offset(unsigned Level) { return path[Level].offset; } 803212795Sdim 804226633Sdim // Leaf accessors. 805226633Sdim template <typename NodeT> NodeT &leaf() const { 806226633Sdim return *reinterpret_cast<NodeT*>(path.back().node); 807212795Sdim } 808212795Sdim unsigned leafSize() const { return path.back().size; } 809212795Sdim unsigned leafOffset() const { return path.back().offset; } 810212795Sdim unsigned &leafOffset() { return path.back().offset; } 811212795Sdim 812212795Sdim /// valid - Return true if path is at a valid node, not at end(). 813212795Sdim bool valid() const { 814212795Sdim return !path.empty() && path.front().offset < path.front().size; 815212795Sdim } 816212795Sdim 817212795Sdim /// height - Return the height of the tree corresponding to this path. 818212795Sdim /// This matches map->height in a full path. 819212795Sdim unsigned height() const { return path.size() - 1; } 820212795Sdim 821212795Sdim /// subtree - Get the subtree referenced from Level. When the path is 822212795Sdim /// consistent, node(Level + 1) == subtree(Level). 823239462Sdim /// @param Level 0..height-1. The leaves have no subtrees. 824212795Sdim NodeRef &subtree(unsigned Level) const { 825212795Sdim return path[Level].subtree(path[Level].offset); 826212795Sdim } 827212795Sdim 828212795Sdim /// reset - Reset cached information about node(Level) from subtree(Level -1). 829212795Sdim /// @param Level 1..height. The node to update after parent node changed. 830243830Sdim void reset(unsigned Level) { 831212795Sdim path[Level] = Entry(subtree(Level - 1), offset(Level)); 832212795Sdim } 833249423Sdim 834212795Sdim /// push - Add entry to path. 835212795Sdim /// @param Node Node to add, should be subtree(path.size()-1). 836212795Sdim /// @param Offset Offset into Node. 837212795Sdim void push(NodeRef Node, unsigned Offset) { 838212795Sdim path.push_back(Entry(Node, Offset)); 839212795Sdim } 840212795Sdim 841212795Sdim /// pop - Remove the last path entry. 842212795Sdim void pop() { 843212795Sdim path.pop_back(); 844243830Sdim } 845212795Sdim 846212795Sdim /// setSize - Set the size of a node both in the path and in the tree. 847212795Sdim /// @param Level 0..height. Note that setting the root size won't change 848212795Sdim /// map->rootSize. 849212795Sdim /// @param Size New node size. 850243830Sdim void setSize(unsigned Level, unsigned Size) { 851212795Sdim path[Level].size = Size; 852212795Sdim if (Level) 853212795Sdim subtree(Level - 1).setSize(Size); 854212795Sdim } 855249423Sdim 856249423Sdim /// setRoot - Clear the path and set a new root node. 857249423Sdim /// @param Node New root node. 858249423Sdim /// @param Size New root size. 859249423Sdim /// @param Offset Offset into root node. 860249423Sdim void setRoot(void *Node, unsigned Size, unsigned Offset) { 861249423Sdim path.clear(); 862249423Sdim path.push_back(Entry(Node, Size, Offset)); 863243830Sdim } 864249423Sdim 865249423Sdim /// replaceRoot - Replace the current root node with two new entries after the 866249423Sdim /// tree height has increased. 867212795Sdim /// @param Root The new root node. 868249423Sdim /// @param Size Number of entries in the new root. 869212795Sdim /// @param Offsets Offsets into the root and first branch nodes. 870212795Sdim void replaceRoot(void *Root, unsigned Size, IdxPair Offsets); 871249423Sdim 872249423Sdim /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 873212795Sdim /// @param Level Get the sibling to node(Level). 874212795Sdim /// @return Left sibling, or NodeRef(). 875212795Sdim NodeRef getLeftSibling(unsigned Level) const; 876212795Sdim 877212795Sdim /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level 878224145Sdim /// unaltered. 879212795Sdim /// @param Level Move node(Level). 880243830Sdim void moveLeft(unsigned Level); 881212795Sdim 882212795Sdim /// fillLeft - Grow path to Height by taking leftmost branches. 883212795Sdim /// @param Height The target height. 884212795Sdim void fillLeft(unsigned Height) { 885218893Sdim while (height() < Height) 886218893Sdim push(subtree(height()), 0); 887218893Sdim } 888218893Sdim 889218893Sdim /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 890218893Sdim /// @param Level Get the sibling to node(Level). 891218893Sdim /// @return Left sibling, or NodeRef(). 892218893Sdim NodeRef getRightSibling(unsigned Level) const; 893218893Sdim 894218893Sdim /// moveRight - Move path to the left sibling at Level. Leave nodes below 895218893Sdim /// Level unaltered. 896234353Sdim /// @param Level Move node(Level). 897218893Sdim void moveRight(unsigned Level); 898218893Sdim 899234353Sdim /// atBegin - Return true if path is at begin(). 900218893Sdim bool atBegin() const { 901218893Sdim for (unsigned i = 0, e = path.size(); i != e; ++i) 902218893Sdim if (path[i].offset != 0) 903218893Sdim return false; 904218893Sdim return true; 905218893Sdim } 906218893Sdim 907218893Sdim /// atLastEntry - Return true if the path is at the last entry of the node at 908218893Sdim /// Level. 909218893Sdim /// @param Level Node to examine. 910218893Sdim bool atLastEntry(unsigned Level) const { 911218893Sdim return path[Level].offset == path[Level].size - 1; 912218893Sdim } 913218893Sdim 914218893Sdim /// legalizeForInsert - Prepare the path for an insertion at Level. When the 915218893Sdim /// path is at end(), node(Level) may not be a legal node. legalizeForInsert 916218893Sdim /// ensures that node(Level) is real by moving back to the last node at Level, 917218893Sdim /// and setting offset(Level) to size(Level) if required. 918243830Sdim /// @param Level The level where an insertion is about to take place. 919212795Sdim void legalizeForInsert(unsigned Level) { 920243830Sdim if (valid()) 921212795Sdim return; 922226633Sdim moveLeft(Level); 923212795Sdim ++path[Level].offset; 924243830Sdim } 925212795Sdim}; 926212795Sdim 927234353Sdim} // end namespace IntervalMapImpl 928226633Sdim 929249423Sdim//===----------------------------------------------------------------------===// 930226633Sdim//--- IntervalMap ----// 931212795Sdim//===----------------------------------------------------------------------===// 932212795Sdim 933249423Sdimtemplate <typename KeyT, typename ValT, 934249423Sdim unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize, 935212795Sdim typename Traits = IntervalMapInfo<KeyT>> 936243830Sdimclass IntervalMap { 937212795Sdim using Sizer = IntervalMapImpl::NodeSizer<KeyT, ValT>; 938249423Sdim using Leaf = IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits>; 939212795Sdim using Branch = 940249423Sdim IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits>; 941249423Sdim using RootLeaf = IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits>; 942212795Sdim using IdxPair = IntervalMapImpl::IdxPair; 943212795Sdim 944243830Sdim // The RootLeaf capacity is given as a template parameter. We must compute the 945212795Sdim // corresponding RootBranch capacity. 946212795Sdim enum { 947234353Sdim DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) / 948234353Sdim (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)), 949243830Sdim RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1 950243830Sdim }; 951249423Sdim 952249423Sdim using RootBranch = 953234353Sdim IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits>; 954249423Sdim 955249423Sdim // When branched, we store a global start key as well as the branch node. 956249423Sdim struct RootBranchData { 957249423Sdim KeyT start; 958243830Sdim RootBranch node; 959212795Sdim }; 960226633Sdim 961226633Sdimpublic: 962226633Sdim using Allocator = typename Sizer::Allocator; 963226633Sdim using KeyType = KeyT; 964226633Sdim using ValueType = ValT; 965239462Sdim using KeyTraits = Traits; 966239462Sdim 967239462Sdimprivate: 968226633Sdim // The root data is either a RootLeaf or a RootBranchData instance. 969226633Sdim union { 970226633Sdim RootLeaf leaf; 971243830Sdim RootBranchData branchData; 972212795Sdim }; 973226633Sdim 974234353Sdim // Tree height. 975243830Sdim // 0: Leaves in root. 976243830Sdim // 1: Root points to leaf. 977234353Sdim // 2: root->branch->leaf ... 978234353Sdim unsigned height = 0; 979234353Sdim 980234353Sdim // Number of entries in the root node. 981234353Sdim unsigned rootSize = 0; 982218893Sdim 983234353Sdim // Allocator used for creating external nodes. 984239462Sdim Allocator *allocator = nullptr; 985239462Sdim 986234353Sdim const RootLeaf &rootLeaf() const { 987234353Sdim assert(!branched() && "Cannot acces leaf data in branched root"); 988234353Sdim return leaf; 989234353Sdim } 990249423Sdim RootLeaf &rootLeaf() { 991234353Sdim assert(!branched() && "Cannot acces leaf data in branched root"); 992234353Sdim return leaf; 993234353Sdim } 994243830Sdim 995234353Sdim const RootBranchData &rootBranchData() const { 996234353Sdim assert(branched() && "Cannot access branch data in non-branched root"); 997234353Sdim return branchData; 998249423Sdim } 999234353Sdim RootBranchData &rootBranchData() { 1000234353Sdim assert(branched() && "Cannot access branch data in non-branched root"); 1001234353Sdim return branchData; 1002212795Sdim } 1003212795Sdim 1004212795Sdim const RootBranch &rootBranch() const { return rootBranchData().node; } 1005212795Sdim RootBranch &rootBranch() { return rootBranchData().node; } 1006249423Sdim KeyT rootBranchStart() const { return rootBranchData().start; } 1007212795Sdim KeyT &rootBranchStart() { return rootBranchData().start; } 1008243830Sdim 1009243830Sdim template <typename NodeT> NodeT *newNode() { 1010243830Sdim return new (allocator->template Allocate<NodeT>()) NodeT(); 1011249423Sdim } 1012249423Sdim 1013249423Sdim template <typename NodeT> void deleteNode(NodeT *P) { 1014212795Sdim P->~NodeT(); 1015212795Sdim allocator->Deallocate(P); 1016212795Sdim } 1017249423Sdim 1018212795Sdim IdxPair branchRoot(unsigned Position); 1019212795Sdim IdxPair splitRoot(unsigned Position); 1020212795Sdim 1021243830Sdim void switchRootToBranch() { 1022212795Sdim rootLeaf().~RootLeaf(); 1023212795Sdim height = 1; 1024212795Sdim new (&rootBranchData()) RootBranchData(); 1025249423Sdim } 1026243830Sdim 1027243830Sdim void switchRootToLeaf() { 1028212795Sdim rootBranchData().~RootBranchData(); 1029212795Sdim height = 0; 1030212795Sdim new(&rootLeaf()) RootLeaf(); 1031224145Sdim } 1032218893Sdim 1033226633Sdim bool branched() const { return height > 0; } 1034218893Sdim 1035218893Sdim ValT treeSafeLookup(KeyT x, ValT NotFound) const; 1036212795Sdim void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, 1037212795Sdim unsigned Level)); 1038226633Sdim void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level); 1039212795Sdim 1040212795Sdimpublic: 1041212795Sdim explicit IntervalMap(Allocator &a) : allocator(&a) { 1042212795Sdim new (&rootLeaf()) RootLeaf(); 1043243830Sdim } 1044212795Sdim 1045212795Sdim ///@{ 1046249423Sdim /// NOTE: The moved-from or copied-from object's allocator needs to have a 1047249423Sdim /// lifetime equal to or exceeding the moved-to or copied-to object to avoid 1048249423Sdim /// undefined behaviour. 1049249423Sdim IntervalMap(IntervalMap const &RHS) : IntervalMap(*RHS.allocator) { 1050249423Sdim // Future-proofing assertion: this function assumes the IntervalMap 1051249423Sdim // constructor doesn't add any nodes. 1052249423Sdim assert(empty() && "Expected emptry tree"); 1053249423Sdim *this = RHS; 1054249423Sdim } 1055249423Sdim IntervalMap &operator=(IntervalMap const &RHS) { 1056249423Sdim clear(); 1057249423Sdim allocator = RHS.allocator; 1058249423Sdim for (auto It = RHS.begin(), End = RHS.end(); It != End; ++It) 1059249423Sdim insert(It.start(), It.stop(), It.value()); 1060249423Sdim return *this; 1061249423Sdim } 1062249423Sdim 1063249423Sdim IntervalMap(IntervalMap &&RHS) : IntervalMap(*RHS.allocator) { 1064249423Sdim // Future-proofing assertion: this function assumes the IntervalMap 1065226633Sdim // constructor doesn't add any nodes. 1066234353Sdim assert(empty() && "Expected emptry tree"); 1067226633Sdim *this = std::move(RHS); 1068226633Sdim } 1069226633Sdim IntervalMap &operator=(IntervalMap &&RHS) { 1070226633Sdim // Calling clear deallocates memory and switches to rootLeaf. 1071226633Sdim clear(); 1072226633Sdim // Destroy the new rootLeaf. 1073226633Sdim rootLeaf().~RootLeaf(); 1074226633Sdim 1075226633Sdim height = RHS.height; 1076226633Sdim rootSize = RHS.rootSize; 1077226633Sdim allocator = RHS.allocator; 1078226633Sdim 1079226633Sdim // rootLeaf and rootBranch are both uninitialized. Move RHS data into 1080226633Sdim // appropriate field. 1081226633Sdim if (RHS.branched()) { 1082226633Sdim rootBranch() = std::move(RHS.rootBranch()); 1083226633Sdim // Prevent RHS deallocating memory LHS now owns by replacing RHS 1084212795Sdim // rootBranch with a new rootLeaf. 1085212795Sdim RHS.rootBranch().~RootBranch(); 1086212795Sdim RHS.height = 0; 1087249423Sdim new (&RHS.rootLeaf()) RootLeaf(); 1088212795Sdim } else { 1089212795Sdim rootLeaf() = std::move(RHS.rootLeaf()); 1090212795Sdim } 1091212795Sdim return *this; 1092212795Sdim } 1093212795Sdim ///@} 1094218893Sdim 1095212795Sdim ~IntervalMap() { 1096212795Sdim clear(); 1097212795Sdim rootLeaf().~RootLeaf(); 1098218893Sdim } 1099218893Sdim 1100212795Sdim /// empty - Return true when no intervals are mapped. 1101218893Sdim bool empty() const { 1102212795Sdim return rootSize == 0; 1103212795Sdim } 1104212795Sdim 1105212795Sdim /// start - Return the smallest mapped key in a non-empty map. 1106263508Sdim KeyT start() const { 1107251662Sdim assert(!empty() && "Empty IntervalMap has no start"); 1108251662Sdim return !branched() ? rootLeaf().start(0) : rootBranchStart(); 1109251662Sdim } 1110251662Sdim 1111251662Sdim /// stop - Return the largest mapped key in a non-empty map. 1112251662Sdim KeyT stop() const { 1113251662Sdim assert(!empty() && "Empty IntervalMap has no stop"); 1114251662Sdim return !branched() ? rootLeaf().stop(rootSize - 1) : 1115251662Sdim rootBranch().stop(rootSize - 1); 1116251662Sdim } 1117251662Sdim 1118251662Sdim /// lookup - Return the mapped value at x or NotFound. 1119249423Sdim ValT lookup(KeyT x, ValT NotFound = ValT()) const { 1120249423Sdim if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x)) 1121212795Sdim return NotFound; 1122212795Sdim return branched() ? treeSafeLookup(x, NotFound) : 1123212795Sdim rootLeaf().safeLookup(x, NotFound); 1124212795Sdim } 1125212795Sdim 1126212795Sdim /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals. 1127212795Sdim /// It is assumed that no key in the interval is mapped to another value, but 1128226633Sdim /// overlapping intervals already mapped to y will be coalesced. 1129212795Sdim void insert(KeyT a, KeyT b, ValT y) { 1130212795Sdim if (branched() || rootSize == RootLeaf::Capacity) 1131212795Sdim return find(a).insert(a, b, y); 1132249423Sdim 1133249423Sdim // Easy insert into root leaf. 1134249423Sdim unsigned p = rootLeaf().findFrom(0, rootSize, a); 1135249423Sdim rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y); 1136249423Sdim } 1137249423Sdim 1138249423Sdim /// clear - Remove all entries. 1139249423Sdim void clear(); 1140249423Sdim 1141249423Sdim class const_iterator; 1142249423Sdim class iterator; 1143249423Sdim friend class const_iterator; 1144249423Sdim friend class iterator; 1145249423Sdim 1146249423Sdim const_iterator begin() const { 1147249423Sdim const_iterator I(*this); 1148212795Sdim I.goToBegin(); 1149212795Sdim return I; 1150212795Sdim } 1151212795Sdim 1152212795Sdim iterator begin() { 1153249423Sdim iterator I(*this); 1154212795Sdim I.goToBegin(); 1155249423Sdim return I; 1156249423Sdim } 1157249423Sdim 1158212795Sdim const_iterator end() const { 1159212795Sdim const_iterator I(*this); 1160212795Sdim I.goToEnd(); 1161212795Sdim return I; 1162212795Sdim } 1163212795Sdim 1164249423Sdim iterator end() { 1165212795Sdim iterator I(*this); 1166249423Sdim I.goToEnd(); 1167249423Sdim return I; 1168243830Sdim } 1169249423Sdim 1170249423Sdim /// find - Return an iterator pointing to the first interval ending at or 1171243830Sdim /// after x, or end(). 1172212795Sdim const_iterator find(KeyT x) const { 1173212795Sdim const_iterator I(*this); 1174212795Sdim I.find(x); 1175226633Sdim return I; 1176226633Sdim } 1177249423Sdim 1178212795Sdim iterator find(KeyT x) { 1179226633Sdim iterator I(*this); 1180212795Sdim I.find(x); 1181226633Sdim return I; 1182212795Sdim } 1183212795Sdim 1184212795Sdim /// overlaps(a, b) - Return true if the intervals in this map overlap with the 1185212795Sdim /// interval [a;b]. 1186212795Sdim bool overlaps(KeyT a, KeyT b) const { 1187249423Sdim assert(Traits::nonEmpty(a, b)); 1188212795Sdim const_iterator I = find(a); 1189226633Sdim if (!I.valid()) 1190212795Sdim return false; 1191212795Sdim // [a;b] and [x;y] overlap iff x<=b and a<=y. The find() call guarantees the 1192212795Sdim // second part (y = find(a).stop()), so it is sufficient to check the first 1193212795Sdim // one. 1194212795Sdim return !Traits::stopLess(b, I.start()); 1195218893Sdim } 1196226633Sdim}; 1197226633Sdim 1198226633Sdim/// treeSafeLookup - Return the mapped value at x or NotFound, assuming a 1199226633Sdim/// branched root. 1200226633Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1201226633SdimValT IntervalMap<KeyT, ValT, N, Traits>:: 1202249423SdimtreeSafeLookup(KeyT x, ValT NotFound) const { 1203249423Sdim assert(branched() && "treeLookup assumes a branched root"); 1204249423Sdim 1205249423Sdim IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x); 1206249423Sdim for (unsigned h = height-1; h; --h) 1207249423Sdim NR = NR.get<Branch>().safeLookup(x); 1208212795Sdim return NR.get<Leaf>().safeLookup(x, NotFound); 1209218893Sdim} 1210212795Sdim 1211212795Sdim// branchRoot - Switch from a leaf root to a branched root. 1212212795Sdim// Return the new (root offset, node offset) corresponding to Position. 1213212795Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1214212795SdimIntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 1215212795SdimbranchRoot(unsigned Position) { 1216212795Sdim using namespace IntervalMapImpl; 1217212795Sdim // How many external leaf nodes to hold RootLeaf+1? 1218212795Sdim const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1; 1219251662Sdim 1220251662Sdim // Compute element distribution among new nodes. 1221212795Sdim unsigned size[Nodes]; 1222212795Sdim IdxPair NewOffset(0, Position); 1223212795Sdim 1224234353Sdim // Is is very common for the root node to be smaller than external nodes. 1225218893Sdim if (Nodes == 1) 1226218893Sdim size[0] = rootSize; 1227212795Sdim else 1228226633Sdim NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, size, 1229234353Sdim Position, true); 1230226633Sdim 1231226633Sdim // Allocate new nodes. 1232226633Sdim unsigned pos = 0; 1233226633Sdim NodeRef node[Nodes]; 1234226633Sdim for (unsigned n = 0; n != Nodes; ++n) { 1235226633Sdim Leaf *L = newNode<Leaf>(); 1236226633Sdim L->copy(rootLeaf(), pos, 0, size[n]); 1237212795Sdim node[n] = NodeRef(L, size[n]); 1238249423Sdim pos += size[n]; 1239249423Sdim } 1240226633Sdim 1241218893Sdim // Destroy the old leaf node, construct branch node instead. 1242226633Sdim switchRootToBranch(); 1243249423Sdim for (unsigned n = 0; n != Nodes; ++n) { 1244249423Sdim rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1); 1245249423Sdim rootBranch().subtree(n) = node[n]; 1246249423Sdim } 1247249423Sdim rootBranchStart() = node[0].template get<Leaf>().start(0); 1248218893Sdim rootSize = Nodes; 1249249423Sdim return NewOffset; 1250249423Sdim} 1251249423Sdim 1252249423Sdim// splitRoot - Split the current BranchRoot into multiple Branch nodes. 1253249423Sdim// Return the new (root offset, node offset) corresponding to Position. 1254226633Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1255226633SdimIntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 1256234353SdimsplitRoot(unsigned Position) { 1257249423Sdim using namespace IntervalMapImpl; 1258249423Sdim // How many external leaf nodes to hold RootBranch+1? 1259249423Sdim const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1; 1260249423Sdim 1261226633Sdim // Compute element distribution among new nodes. 1262218893Sdim unsigned Size[Nodes]; 1263226633Sdim IdxPair NewOffset(0, Position); 1264226633Sdim 1265226633Sdim // Is is very common for the root node to be smaller than external nodes. 1266226633Sdim if (Nodes == 1) 1267249423Sdim Size[0] = rootSize; 1268226633Sdim else 1269249423Sdim NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, Size, 1270249423Sdim Position, true); 1271249423Sdim 1272249423Sdim // Allocate new nodes. 1273249423Sdim unsigned Pos = 0; 1274249423Sdim NodeRef Node[Nodes]; 1275249423Sdim for (unsigned n = 0; n != Nodes; ++n) { 1276249423Sdim Branch *B = newNode<Branch>(); 1277249423Sdim B->copy(rootBranch(), Pos, 0, Size[n]); 1278249423Sdim Node[n] = NodeRef(B, Size[n]); 1279226633Sdim Pos += Size[n]; 1280249423Sdim } 1281226633Sdim 1282226633Sdim for (unsigned n = 0; n != Nodes; ++n) { 1283226633Sdim rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1); 1284226633Sdim rootBranch().subtree(n) = Node[n]; 1285226633Sdim } 1286263508Sdim rootSize = Nodes; 1287263508Sdim ++height; 1288226633Sdim return NewOffset; 1289226633Sdim} 1290226633Sdim 1291226633Sdim/// visitNodes - Visit each external node. 1292226633Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1293226633Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1294234353SdimvisitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) { 1295234353Sdim if (!branched()) 1296226633Sdim return; 1297226633Sdim SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs; 1298226633Sdim 1299226633Sdim // Collect level 0 nodes from the root. 1300226633Sdim for (unsigned i = 0; i != rootSize; ++i) 1301212795Sdim Refs.push_back(rootBranch().subtree(i)); 1302218893Sdim 1303249423Sdim // Visit all branch nodes. 1304249423Sdim for (unsigned h = height - 1; h; --h) { 1305249423Sdim for (unsigned i = 0, e = Refs.size(); i != e; ++i) { 1306249423Sdim for (unsigned j = 0, s = Refs[i].size(); j != s; ++j) 1307249423Sdim NextRefs.push_back(Refs[i].subtree(j)); 1308249423Sdim (this->*f)(Refs[i], h); 1309249423Sdim } 1310249423Sdim Refs.clear(); 1311249423Sdim Refs.swap(NextRefs); 1312249423Sdim } 1313249423Sdim 1314263508Sdim // Visit all leaf nodes. 1315249423Sdim for (unsigned i = 0, e = Refs.size(); i != e; ++i) 1316249423Sdim (this->*f)(Refs[i], 0); 1317249423Sdim} 1318226633Sdim 1319226633Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1320218893Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1321226633SdimdeleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) { 1322226633Sdim if (Level) 1323226633Sdim deleteNode(&Node.get<Branch>()); 1324218893Sdim else 1325218893Sdim deleteNode(&Node.get<Leaf>()); 1326249423Sdim} 1327249423Sdim 1328249423Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1329249423Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1330243830Sdimclear() { 1331249423Sdim if (branched()) { 1332218893Sdim visitNodes(&IntervalMap::deleteNode); 1333218893Sdim switchRootToLeaf(); 1334249423Sdim } 1335249423Sdim rootSize = 0; 1336249423Sdim} 1337249423Sdim 1338249423Sdim//===----------------------------------------------------------------------===// 1339249423Sdim//--- IntervalMap::const_iterator ----// 1340249423Sdim//===----------------------------------------------------------------------===// 1341212795Sdim 1342243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1343243830Sdimclass IntervalMap<KeyT, ValT, N, Traits>::const_iterator { 1344243830Sdim friend class IntervalMap; 1345226633Sdim 1346226633Sdimpublic: 1347249423Sdim using iterator_category = std::bidirectional_iterator_tag; 1348212795Sdim using value_type = ValT; 1349212795Sdim using difference_type = std::ptrdiff_t; 1350212795Sdim using pointer = value_type *; 1351212795Sdim using reference = value_type &; 1352212795Sdim 1353249423Sdimprotected: 1354226633Sdim // The map referred to. 1355212795Sdim IntervalMap *map = nullptr; 1356212795Sdim 1357212795Sdim // We store a full path from the root to the current position. 1358249423Sdim // The path may be partially filled, but never between iterator calls. 1359249423Sdim IntervalMapImpl::Path path; 1360249423Sdim 1361249423Sdim explicit const_iterator(const IntervalMap &map) : 1362249423Sdim map(const_cast<IntervalMap*>(&map)) {} 1363249423Sdim 1364249423Sdim bool branched() const { 1365249423Sdim assert(map && "Invalid iterator"); 1366249423Sdim return map->branched(); 1367249423Sdim } 1368249423Sdim 1369249423Sdim void setRoot(unsigned Offset) { 1370249423Sdim if (branched()) 1371249423Sdim path.setRoot(&map->rootBranch(), map->rootSize, Offset); 1372249423Sdim else 1373249423Sdim path.setRoot(&map->rootLeaf(), map->rootSize, Offset); 1374249423Sdim } 1375249423Sdim 1376249423Sdim void pathFillFind(KeyT x); 1377249423Sdim void treeFind(KeyT x); 1378249423Sdim void treeAdvanceTo(KeyT x); 1379249423Sdim 1380249423Sdim /// unsafeStart - Writable access to start() for iterator. 1381249423Sdim KeyT &unsafeStart() const { 1382212795Sdim assert(valid() && "Cannot access invalid iterator"); 1383212795Sdim return branched() ? path.leaf<Leaf>().start(path.leafOffset()) : 1384212795Sdim path.leaf<RootLeaf>().start(path.leafOffset()); 1385212795Sdim } 1386249423Sdim 1387212795Sdim /// unsafeStop - Writable access to stop() for iterator. 1388212795Sdim KeyT &unsafeStop() const { 1389212795Sdim assert(valid() && "Cannot access invalid iterator"); 1390234353Sdim return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) : 1391234353Sdim path.leaf<RootLeaf>().stop(path.leafOffset()); 1392234353Sdim } 1393234353Sdim 1394234353Sdim /// unsafeValue - Writable access to value() for iterator. 1395249423Sdim ValT &unsafeValue() const { 1396249423Sdim assert(valid() && "Cannot access invalid iterator"); 1397234353Sdim return branched() ? path.leaf<Leaf>().value(path.leafOffset()) : 1398249423Sdim path.leaf<RootLeaf>().value(path.leafOffset()); 1399234353Sdim } 1400249423Sdim 1401249423Sdimpublic: 1402249423Sdim /// const_iterator - Create an iterator that isn't pointing anywhere. 1403249423Sdim const_iterator() = default; 1404249423Sdim 1405249423Sdim /// setMap - Change the map iterated over. This call must be followed by a 1406249423Sdim /// call to goToBegin(), goToEnd(), or find() 1407249423Sdim void setMap(const IntervalMap &m) { map = const_cast<IntervalMap*>(&m); } 1408249423Sdim 1409234353Sdim /// valid - Return true if the current position is valid, false for end(). 1410234353Sdim bool valid() const { return path.valid(); } 1411234353Sdim 1412234353Sdim /// atBegin - Return true if the current position is the first map entry. 1413234353Sdim bool atBegin() const { return path.atBegin(); } 1414234353Sdim 1415234353Sdim /// start - Return the beginning of the current interval. 1416234353Sdim const KeyT &start() const { return unsafeStart(); } 1417249423Sdim 1418234353Sdim /// stop - Return the end of the current interval. 1419234353Sdim const KeyT &stop() const { return unsafeStop(); } 1420234353Sdim 1421234353Sdim /// value - Return the mapped value at the current interval. 1422234353Sdim const ValT &value() const { return unsafeValue(); } 1423234353Sdim 1424234353Sdim const ValT &operator*() const { return value(); } 1425249423Sdim 1426249423Sdim bool operator==(const const_iterator &RHS) const { 1427234353Sdim assert(map == RHS.map && "Cannot compare iterators from different maps"); 1428234353Sdim if (!valid()) 1429234353Sdim return !RHS.valid(); 1430234353Sdim if (path.leafOffset() != RHS.path.leafOffset()) 1431234353Sdim return false; 1432234353Sdim return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>(); 1433249423Sdim } 1434234353Sdim 1435234353Sdim bool operator!=(const const_iterator &RHS) const { 1436234353Sdim return !operator==(RHS); 1437234353Sdim } 1438234353Sdim 1439234353Sdim /// goToBegin - Move to the first interval in map. 1440234353Sdim void goToBegin() { 1441234353Sdim setRoot(0); 1442234353Sdim if (branched()) 1443234353Sdim path.fillLeft(map->height); 1444234353Sdim } 1445243830Sdim 1446243830Sdim /// goToEnd - Move beyond the last interval in map. 1447243830Sdim void goToEnd() { 1448234353Sdim setRoot(map->rootSize); 1449234353Sdim } 1450234353Sdim 1451249423Sdim /// preincrement - Move to the next interval. 1452249423Sdim const_iterator &operator++() { 1453249423Sdim assert(valid() && "Cannot increment end()"); 1454249423Sdim if (++path.leafOffset() == path.leafSize() && branched()) 1455249423Sdim path.moveRight(map->height); 1456249423Sdim return *this; 1457249423Sdim } 1458249423Sdim 1459249423Sdim /// postincrement - Don't do that! 1460249423Sdim const_iterator operator++(int) { 1461249423Sdim const_iterator tmp = *this; 1462249423Sdim operator++(); 1463249423Sdim return tmp; 1464249423Sdim } 1465249423Sdim 1466234353Sdim /// predecrement - Move to the previous interval. 1467234353Sdim const_iterator &operator--() { 1468234353Sdim if (path.leafOffset() && (valid() || !branched())) 1469234353Sdim --path.leafOffset(); 1470234353Sdim else 1471234353Sdim path.moveLeft(map->height); 1472234353Sdim return *this; 1473234353Sdim } 1474234353Sdim 1475234353Sdim /// postdecrement - Don't do that! 1476234353Sdim const_iterator operator--(int) { 1477234353Sdim const_iterator tmp = *this; 1478234353Sdim operator--(); 1479234353Sdim return tmp; 1480249423Sdim } 1481249423Sdim 1482249423Sdim /// find - Move to the first interval with stop >= x, or end(). 1483249423Sdim /// This is a full search from the root, the current position is ignored. 1484249423Sdim void find(KeyT x) { 1485249423Sdim if (branched()) 1486249423Sdim treeFind(x); 1487249423Sdim else 1488249423Sdim setRoot(map->rootLeaf().findFrom(0, map->rootSize, x)); 1489249423Sdim } 1490249423Sdim 1491249423Sdim /// advanceTo - Move to the first interval with stop >= x, or end(). 1492249423Sdim /// The search is started from the current position, and no earlier positions 1493249423Sdim /// can be found. This is much faster than find() for small moves. 1494249423Sdim void advanceTo(KeyT x) { 1495249423Sdim if (!valid()) 1496249423Sdim return; 1497249423Sdim if (branched()) 1498249423Sdim treeAdvanceTo(x); 1499249423Sdim else 1500249423Sdim path.leafOffset() = 1501249423Sdim map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x); 1502249423Sdim } 1503249423Sdim}; 1504249423Sdim 1505249423Sdim/// pathFillFind - Complete path by searching for x. 1506249423Sdim/// @param x Key to search for. 1507249423Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1508249423Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1509249423Sdimconst_iterator::pathFillFind(KeyT x) { 1510249423Sdim IntervalMapImpl::NodeRef NR = path.subtree(path.height()); 1511249423Sdim for (unsigned i = map->height - path.height() - 1; i; --i) { 1512249423Sdim unsigned p = NR.get<Branch>().safeFind(0, x); 1513249423Sdim path.push(NR, p); 1514249423Sdim NR = NR.subtree(p); 1515249423Sdim } 1516249423Sdim path.push(NR, NR.get<Leaf>().safeFind(0, x)); 1517249423Sdim} 1518249423Sdim 1519249423Sdim/// treeFind - Find in a branched tree. 1520249423Sdim/// @param x Key to search for. 1521249423Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1522249423Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1523249423Sdimconst_iterator::treeFind(KeyT x) { 1524249423Sdim setRoot(map->rootBranch().findFrom(0, map->rootSize, x)); 1525249423Sdim if (valid()) 1526249423Sdim pathFillFind(x); 1527249423Sdim} 1528249423Sdim 1529249423Sdim/// treeAdvanceTo - Find position after the current one. 1530249423Sdim/// @param x Key to search for. 1531249423Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1532249423Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1533249423Sdimconst_iterator::treeAdvanceTo(KeyT x) { 1534249423Sdim // Can we stay on the same leaf node? 1535249423Sdim if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) { 1536249423Sdim path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x); 1537249423Sdim return; 1538249423Sdim } 1539249423Sdim 1540249423Sdim // Drop the current leaf. 1541249423Sdim path.pop(); 1542249423Sdim 1543249423Sdim // Search towards the root for a usable subtree. 1544249423Sdim if (path.height()) { 1545249423Sdim for (unsigned l = path.height() - 1; l; --l) { 1546249423Sdim if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) { 1547249423Sdim // The branch node at l+1 is usable 1548249423Sdim path.offset(l + 1) = 1549249423Sdim path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x); 1550249423Sdim return pathFillFind(x); 1551249423Sdim } 1552249423Sdim path.pop(); 1553249423Sdim } 1554249423Sdim // Is the level-1 Branch usable? 1555249423Sdim if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) { 1556249423Sdim path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x); 1557249423Sdim return pathFillFind(x); 1558249423Sdim } 1559249423Sdim } 1560249423Sdim 1561249423Sdim // We reached the root. 1562249423Sdim setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x)); 1563249423Sdim if (valid()) 1564249423Sdim pathFillFind(x); 1565249423Sdim} 1566249423Sdim 1567249423Sdim//===----------------------------------------------------------------------===// 1568249423Sdim//--- IntervalMap::iterator ----// 1569249423Sdim//===----------------------------------------------------------------------===// 1570249423Sdim 1571249423Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1572249423Sdimclass IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator { 1573249423Sdim friend class IntervalMap; 1574249423Sdim 1575249423Sdim using IdxPair = IntervalMapImpl::IdxPair; 1576249423Sdim 1577249423Sdim explicit iterator(IntervalMap &map) : const_iterator(map) {} 1578249423Sdim 1579249423Sdim void setNodeStop(unsigned Level, KeyT Stop); 1580249423Sdim bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop); 1581249423Sdim template <typename NodeT> bool overflow(unsigned Level); 1582249423Sdim void treeInsert(KeyT a, KeyT b, ValT y); 1583249423Sdim void eraseNode(unsigned Level); 1584249423Sdim void treeErase(bool UpdateRoot = true); 1585249423Sdim bool canCoalesceLeft(KeyT Start, ValT x); 1586249423Sdim bool canCoalesceRight(KeyT Stop, ValT x); 1587249423Sdim 1588249423Sdimpublic: 1589249423Sdim /// iterator - Create null iterator. 1590251662Sdim iterator() = default; 1591251662Sdim 1592263508Sdim /// setStart - Move the start of the current interval. 1593249423Sdim /// This may cause coalescing with the previous interval. 1594249423Sdim /// @param a New start key, must not overlap the previous interval. 1595249423Sdim void setStart(KeyT a); 1596249423Sdim 1597263508Sdim /// setStop - Move the end of the current interval. 1598263508Sdim /// This may cause coalescing with the following interval. 1599263508Sdim /// @param b New stop key, must not overlap the following interval. 1600263508Sdim void setStop(KeyT b); 1601263508Sdim 1602263508Sdim /// setValue - Change the mapped value of the current interval. 1603263508Sdim /// This may cause coalescing with the previous and following intervals. 1604263508Sdim /// @param x New value. 1605249423Sdim void setValue(ValT x); 1606263508Sdim 1607249423Sdim /// setStartUnchecked - Move the start of the current interval without 1608249423Sdim /// checking for coalescing or overlaps. 1609249423Sdim /// This should only be used when it is known that coalescing is not required. 1610249423Sdim /// @param a New start key. 1611249423Sdim void setStartUnchecked(KeyT a) { this->unsafeStart() = a; } 1612249423Sdim 1613249423Sdim /// setStopUnchecked - Move the end of the current interval without checking 1614249423Sdim /// for coalescing or overlaps. 1615249423Sdim /// This should only be used when it is known that coalescing is not required. 1616249423Sdim /// @param b New stop key. 1617249423Sdim void setStopUnchecked(KeyT b) { 1618249423Sdim this->unsafeStop() = b; 1619249423Sdim // Update keys in branch nodes as well. 1620249423Sdim if (this->path.atLastEntry(this->path.height())) 1621249423Sdim setNodeStop(this->path.height(), b); 1622251662Sdim } 1623251662Sdim 1624251662Sdim /// setValueUnchecked - Change the mapped value of the current interval 1625249423Sdim /// without checking for coalescing. 1626249423Sdim /// @param x New value. 1627251662Sdim void setValueUnchecked(ValT x) { this->unsafeValue() = x; } 1628249423Sdim 1629249423Sdim /// insert - Insert mapping [a;b] -> y before the current position. 1630249423Sdim void insert(KeyT a, KeyT b, ValT y); 1631249423Sdim 1632249423Sdim /// erase - Erase the current interval. 1633249423Sdim void erase(); 1634249423Sdim 1635249423Sdim iterator &operator++() { 1636249423Sdim const_iterator::operator++(); 1637249423Sdim return *this; 1638243830Sdim } 1639243830Sdim 1640243830Sdim iterator operator++(int) { 1641243830Sdim iterator tmp = *this; 1642243830Sdim operator++(); 1643249423Sdim return tmp; 1644243830Sdim } 1645243830Sdim 1646243830Sdim iterator &operator--() { 1647249423Sdim const_iterator::operator--(); 1648243830Sdim return *this; 1649243830Sdim } 1650243830Sdim 1651243830Sdim iterator operator--(int) { 1652243830Sdim iterator tmp = *this; 1653249423Sdim operator--(); 1654249423Sdim return tmp; 1655243830Sdim } 1656243830Sdim}; 1657243830Sdim 1658243830Sdim/// canCoalesceLeft - Can the current interval coalesce to the left after 1659243830Sdim/// changing start or value? 1660243830Sdim/// @param Start New start of current interval. 1661243830Sdim/// @param Value New value for current interval. 1662243830Sdim/// @return True when updating the current interval would enable coalescing. 1663243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1664249423Sdimbool IntervalMap<KeyT, ValT, N, Traits>:: 1665243830Sdimiterator::canCoalesceLeft(KeyT Start, ValT Value) { 1666243830Sdim using namespace IntervalMapImpl; 1667243830Sdim Path &P = this->path; 1668243830Sdim if (!this->branched()) { 1669243830Sdim unsigned i = P.leafOffset(); 1670243830Sdim RootLeaf &Node = P.leaf<RootLeaf>(); 1671243830Sdim return i && Node.value(i-1) == Value && 1672243830Sdim Traits::adjacent(Node.stop(i-1), Start); 1673243830Sdim } 1674243830Sdim // Branched. 1675243830Sdim if (unsigned i = P.leafOffset()) { 1676243830Sdim Leaf &Node = P.leaf<Leaf>(); 1677243830Sdim return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start); 1678243830Sdim } else if (NodeRef NR = P.getLeftSibling(P.height())) { 1679243830Sdim unsigned i = NR.size() - 1; 1680243830Sdim Leaf &Node = NR.get<Leaf>(); 1681243830Sdim return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start); 1682243830Sdim } 1683243830Sdim return false; 1684243830Sdim} 1685243830Sdim 1686243830Sdim/// canCoalesceRight - Can the current interval coalesce to the right after 1687243830Sdim/// changing stop or value? 1688243830Sdim/// @param Stop New stop of current interval. 1689243830Sdim/// @param Value New value for current interval. 1690243830Sdim/// @return True when updating the current interval would enable coalescing. 1691243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1692243830Sdimbool IntervalMap<KeyT, ValT, N, Traits>:: 1693243830Sdimiterator::canCoalesceRight(KeyT Stop, ValT Value) { 1694243830Sdim using namespace IntervalMapImpl; 1695243830Sdim Path &P = this->path; 1696243830Sdim unsigned i = P.leafOffset() + 1; 1697249423Sdim if (!this->branched()) { 1698243830Sdim if (i >= P.leafSize()) 1699243830Sdim return false; 1700243830Sdim RootLeaf &Node = P.leaf<RootLeaf>(); 1701243830Sdim return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); 1702243830Sdim } 1703243830Sdim // Branched. 1704249423Sdim if (i < P.leafSize()) { 1705249423Sdim Leaf &Node = P.leaf<Leaf>(); 1706243830Sdim return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); 1707243830Sdim } else if (NodeRef NR = P.getRightSibling(P.height())) { 1708243830Sdim Leaf &Node = NR.get<Leaf>(); 1709243830Sdim return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0)); 1710243830Sdim } 1711243830Sdim return false; 1712243830Sdim} 1713243830Sdim 1714243830Sdim/// setNodeStop - Update the stop key of the current node at level and above. 1715243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1716249423Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1717249423Sdimiterator::setNodeStop(unsigned Level, KeyT Stop) { 1718243830Sdim // There are no references to the root node, so nothing to update. 1719249423Sdim if (!Level) 1720243830Sdim return; 1721243830Sdim IntervalMapImpl::Path &P = this->path; 1722243830Sdim // Update nodes pointing to the current node. 1723243830Sdim while (--Level) { 1724249423Sdim P.node<Branch>(Level).stop(P.offset(Level)) = Stop; 1725243830Sdim if (!P.atLastEntry(Level)) 1726243830Sdim return; 1727249423Sdim } 1728249423Sdim // Update root separately since it has a different layout. 1729263508Sdim P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop; 1730263508Sdim} 1731263508Sdim 1732263508Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1733249423Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1734249423Sdimiterator::setStart(KeyT a) { 1735249423Sdim assert(Traits::nonEmpty(a, this->stop()) && "Cannot move start beyond stop"); 1736243830Sdim KeyT &CurStart = this->unsafeStart(); 1737243830Sdim if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) { 1738249423Sdim CurStart = a; 1739249423Sdim return; 1740249423Sdim } 1741249423Sdim // Coalesce with the interval to the left. 1742249423Sdim --*this; 1743243830Sdim a = this->start(); 1744243830Sdim erase(); 1745243830Sdim setStartUnchecked(a); 1746243830Sdim} 1747243830Sdim 1748243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1749226633Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1750243830Sdimiterator::setStop(KeyT b) { 1751223017Sdim assert(Traits::nonEmpty(this->start(), b) && "Cannot move stop beyond start"); 1752243830Sdim if (Traits::startLess(b, this->stop()) || 1753223017Sdim !canCoalesceRight(b, this->value())) { 1754243830Sdim setStopUnchecked(b); 1755243830Sdim return; 1756223017Sdim } 1757243830Sdim // Coalesce with interval to the right. 1758223017Sdim KeyT a = this->start(); 1759223017Sdim erase(); 1760223017Sdim setStartUnchecked(a); 1761223017Sdim} 1762223017Sdim 1763223017Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1764223017Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1765223017Sdimiterator::setValue(ValT x) { 1766212795Sdim setValueUnchecked(x); 1767212795Sdim if (canCoalesceRight(this->stop(), x)) { 1768212795Sdim KeyT a = this->start(); 1769243830Sdim erase(); 1770243830Sdim setStartUnchecked(a); 1771212795Sdim } 1772243830Sdim if (canCoalesceLeft(this->start(), x)) { 1773212795Sdim --*this; 1774212795Sdim KeyT a = this->start(); 1775218893Sdim erase(); 1776212795Sdim setStartUnchecked(a); 1777212795Sdim } 1778226633Sdim} 1779212795Sdim 1780212795Sdim/// insertNode - insert a node before the current path at level. 1781212795Sdim/// Leave the current path pointing at the new node. 1782212795Sdim/// @param Level path index of the node to be inserted. 1783212795Sdim/// @param Node The node to be inserted. 1784226633Sdim/// @param Stop The last index in the new node. 1785212795Sdim/// @return True if the tree height was increased. 1786212795Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1787212795Sdimbool IntervalMap<KeyT, ValT, N, Traits>:: 1788226633Sdimiterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) { 1789212795Sdim assert(Level && "Cannot insert next to the root"); 1790212795Sdim bool SplitRoot = false; 1791212795Sdim IntervalMap &IM = *this->map; 1792243830Sdim IntervalMapImpl::Path &P = this->path; 1793249423Sdim 1794243830Sdim if (Level == 1) { 1795249423Sdim // Insert into the root branch node. 1796212795Sdim if (IM.rootSize < RootBranch::Capacity) { 1797243830Sdim IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop); 1798212795Sdim P.setSize(0, ++IM.rootSize); 1799212795Sdim P.reset(Level); 1800212795Sdim return SplitRoot; 1801212795Sdim } 1802243830Sdim 1803212795Sdim // We need to split the root while keeping our position. 1804249423Sdim SplitRoot = true; 1805249423Sdim IdxPair Offset = IM.splitRoot(P.offset(0)); 1806249423Sdim P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1807249423Sdim 1808249423Sdim // Fall through to insert at the new higher level. 1809249423Sdim ++Level; 1810249423Sdim } 1811249423Sdim 1812249423Sdim // When inserting before end(), make sure we have a valid path. 1813243830Sdim P.legalizeForInsert(--Level); 1814243830Sdim 1815249423Sdim // Insert into the branch node at Level-1. 1816249423Sdim if (P.size(Level) == Branch::Capacity) { 1817249423Sdim // Branch node is full, handle handle the overflow. 1818249423Sdim assert(!SplitRoot && "Cannot overflow after splitting the root"); 1819249423Sdim SplitRoot = overflow<Branch>(Level); 1820243830Sdim Level += SplitRoot; 1821249423Sdim } 1822243830Sdim P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop); 1823212795Sdim P.setSize(Level, P.size(Level) + 1); 1824249423Sdim if (P.atLastEntry(Level)) 1825249423Sdim setNodeStop(Level, Stop); 1826249423Sdim P.reset(Level + 1); 1827243830Sdim return SplitRoot; 1828243830Sdim} 1829243830Sdim 1830243830Sdim// insert 1831243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1832243830Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1833243830Sdimiterator::insert(KeyT a, KeyT b, ValT y) { 1834243830Sdim if (this->branched()) 1835243830Sdim return treeInsert(a, b, y); 1836249423Sdim IntervalMap &IM = *this->map; 1837243830Sdim IntervalMapImpl::Path &P = this->path; 1838249423Sdim 1839249423Sdim // Try simple root leaf insert. 1840249423Sdim unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y); 1841249423Sdim 1842249423Sdim // Was the root node insert successful? 1843243830Sdim if (Size <= RootLeaf::Capacity) { 1844249423Sdim P.setSize(0, IM.rootSize = Size); 1845249423Sdim return; 1846249423Sdim } 1847249423Sdim 1848243830Sdim // Root leaf node is full, we must branch. 1849243830Sdim IdxPair Offset = IM.branchRoot(P.leafOffset()); 1850243830Sdim P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1851243830Sdim 1852249423Sdim // Now it fits in the new leaf. 1853249423Sdim treeInsert(a, b, y); 1854243830Sdim} 1855243830Sdim 1856243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1857243830Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1858243830Sdimiterator::treeInsert(KeyT a, KeyT b, ValT y) { 1859243830Sdim using namespace IntervalMapImpl; 1860243830Sdim Path &P = this->path; 1861243830Sdim 1862243830Sdim if (!P.valid()) 1863243830Sdim P.legalizeForInsert(this->map->height); 1864243830Sdim 1865243830Sdim // Check if this insertion will extend the node to the left. 1866243830Sdim if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) { 1867243830Sdim // Node is growing to the left, will it affect a left sibling node? 1868243830Sdim if (NodeRef Sib = P.getLeftSibling(P.height())) { 1869243830Sdim Leaf &SibLeaf = Sib.get<Leaf>(); 1870243830Sdim unsigned SibOfs = Sib.size() - 1; 1871249423Sdim if (SibLeaf.value(SibOfs) == y && 1872243830Sdim Traits::adjacent(SibLeaf.stop(SibOfs), a)) { 1873243830Sdim // This insertion will coalesce with the last entry in SibLeaf. We can 1874243830Sdim // handle it in two ways: 1875243830Sdim // 1. Extend SibLeaf.stop to b and be done, or 1876243830Sdim // 2. Extend a to SibLeaf, erase the SibLeaf entry and continue. 1877243830Sdim // We prefer 1., but need 2 when coalescing to the right as well. 1878243830Sdim Leaf &CurLeaf = P.leaf<Leaf>(); 1879243830Sdim P.moveLeft(P.height()); 1880243830Sdim if (Traits::stopLess(b, CurLeaf.start(0)) && 1881243830Sdim (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) { 1882243830Sdim // Easy, just extend SibLeaf and we're done. 1883243830Sdim setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b); 1884243830Sdim return; 1885243830Sdim } else { 1886249423Sdim // We have both left and right coalescing. Erase the old SibLeaf entry 1887249423Sdim // and continue inserting the larger interval. 1888249423Sdim a = SibLeaf.start(SibOfs); 1889249423Sdim treeErase(/* UpdateRoot= */false); 1890249423Sdim } 1891249423Sdim } 1892249423Sdim } else { 1893243830Sdim // No left sibling means we are at begin(). Update cached bound. 1894243830Sdim this->map->rootBranchStart() = a; 1895243830Sdim } 1896243830Sdim } 1897243830Sdim 1898243830Sdim // When we are inserting at the end of a leaf node, we must update stops. 1899249423Sdim unsigned Size = P.leafSize(); 1900249423Sdim bool Grow = P.leafOffset() == Size; 1901243830Sdim Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y); 1902243830Sdim 1903243830Sdim // Leaf insertion unsuccessful? Overflow and try again. 1904249423Sdim if (Size > Leaf::Capacity) { 1905243830Sdim overflow<Leaf>(P.height()); 1906243830Sdim Grow = P.leafOffset() == P.leafSize(); 1907243830Sdim Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y); 1908243830Sdim assert(Size <= Leaf::Capacity && "overflow() didn't make room"); 1909243830Sdim } 1910243830Sdim 1911243830Sdim // Inserted, update offset and leaf size. 1912243830Sdim P.setSize(P.height(), Size); 1913243830Sdim 1914243830Sdim // Insert was the last node entry, update stops. 1915243830Sdim if (Grow) 1916243830Sdim setNodeStop(P.height(), b); 1917243830Sdim} 1918243830Sdim 1919243830Sdim/// erase - erase the current interval and move to the next position. 1920243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1921243830Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1922243830Sdimiterator::erase() { 1923243830Sdim IntervalMap &IM = *this->map; 1924243830Sdim IntervalMapImpl::Path &P = this->path; 1925243830Sdim assert(P.valid() && "Cannot erase end()"); 1926243830Sdim if (this->branched()) 1927243830Sdim return treeErase(); 1928243830Sdim IM.rootLeaf().erase(P.leafOffset(), IM.rootSize); 1929243830Sdim P.setSize(0, --IM.rootSize); 1930243830Sdim} 1931243830Sdim 1932243830Sdim/// treeErase - erase() for a branched tree. 1933243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1934243830Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1935243830Sdimiterator::treeErase(bool UpdateRoot) { 1936243830Sdim IntervalMap &IM = *this->map; 1937243830Sdim IntervalMapImpl::Path &P = this->path; 1938243830Sdim Leaf &Node = P.leaf<Leaf>(); 1939243830Sdim 1940243830Sdim // Nodes are not allowed to become empty. 1941243830Sdim if (P.leafSize() == 1) { 1942243830Sdim IM.deleteNode(&Node); 1943243830Sdim eraseNode(IM.height); 1944243830Sdim // Update rootBranchStart if we erased begin(). 1945243830Sdim if (UpdateRoot && IM.branched() && P.valid() && P.atBegin()) 1946243830Sdim IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1947243830Sdim return; 1948243830Sdim } 1949243830Sdim 1950243830Sdim // Erase current entry. 1951243830Sdim Node.erase(P.leafOffset(), P.leafSize()); 1952243830Sdim unsigned NewSize = P.leafSize() - 1; 1953243830Sdim P.setSize(IM.height, NewSize); 1954243830Sdim // When we erase the last entry, update stop and move to a legal position. 1955243830Sdim if (P.leafOffset() == NewSize) { 1956243830Sdim setNodeStop(IM.height, Node.stop(NewSize - 1)); 1957243830Sdim P.moveRight(IM.height); 1958243830Sdim } else if (UpdateRoot && P.atBegin()) 1959243830Sdim IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1960243830Sdim} 1961243830Sdim 1962243830Sdim/// eraseNode - Erase the current node at Level from its parent and move path to 1963243830Sdim/// the first entry of the next sibling node. 1964243830Sdim/// The node must be deallocated by the caller. 1965243830Sdim/// @param Level 1..height, the root node cannot be erased. 1966243830Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1967243830Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1968243830Sdimiterator::eraseNode(unsigned Level) { 1969243830Sdim assert(Level && "Cannot erase root node"); 1970243830Sdim IntervalMap &IM = *this->map; 1971243830Sdim IntervalMapImpl::Path &P = this->path; 1972249423Sdim 1973243830Sdim if (--Level == 0) { 1974243830Sdim IM.rootBranch().erase(P.offset(0), IM.rootSize); 1975243830Sdim P.setSize(0, --IM.rootSize); 1976243830Sdim // If this cleared the root, switch to height=0. 1977249423Sdim if (IM.empty()) { 1978249423Sdim IM.switchRootToLeaf(); 1979249423Sdim this->setRoot(0); 1980249423Sdim return; 1981243830Sdim } 1982249423Sdim } else { 1983243830Sdim // Remove node ref from branch node at Level. 1984243830Sdim Branch &Parent = P.node<Branch>(Level); 1985243830Sdim if (P.size(Level) == 1) { 1986249423Sdim // Branch node became empty, remove it recursively. 1987243830Sdim IM.deleteNode(&Parent); 1988243830Sdim eraseNode(Level); 1989243830Sdim } else { 1990243830Sdim // Branch node won't become empty. 1991243830Sdim Parent.erase(P.offset(Level), P.size(Level)); 1992243830Sdim unsigned NewSize = P.size(Level) - 1; 1993243830Sdim P.setSize(Level, NewSize); 1994249423Sdim // If we removed the last branch, update stop and move to a legal pos. 1995243830Sdim if (P.offset(Level) == NewSize) { 1996243830Sdim setNodeStop(Level, Parent.stop(NewSize - 1)); 1997243830Sdim P.moveRight(Level); 1998243830Sdim } 1999243830Sdim } 2000243830Sdim } 2001243830Sdim // Update path cache for the new right sibling position. 2002243830Sdim if (P.valid()) { 2003249423Sdim P.reset(Level + 1); 2004249423Sdim P.offset(Level + 1) = 0; 2005249423Sdim } 2006249423Sdim} 2007249423Sdim 2008249423Sdim/// overflow - Distribute entries of the current node evenly among 2009249423Sdim/// its siblings and ensure that the current node is not full. 2010249423Sdim/// This may require allocating a new node. 2011249423Sdim/// @tparam NodeT The type of node at Level (Leaf or Branch). 2012249423Sdim/// @param Level path index of the overflowing node. 2013249423Sdim/// @return True when the tree height was changed. 2014249423Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 2015249423Sdimtemplate <typename NodeT> 2016243830Sdimbool IntervalMap<KeyT, ValT, N, Traits>:: 2017249423Sdimiterator::overflow(unsigned Level) { 2018249423Sdim using namespace IntervalMapImpl; 2019243830Sdim Path &P = this->path; 2020249423Sdim unsigned CurSize[4]; 2021243830Sdim NodeT *Node[4]; 2022243830Sdim unsigned Nodes = 0; 2023249423Sdim unsigned Elements = 0; 2024249423Sdim unsigned Offset = P.offset(Level); 2025212795Sdim 2026212795Sdim // Do we have a left sibling? 2027212795Sdim NodeRef LeftSib = P.getLeftSibling(Level); 2028212795Sdim if (LeftSib) { 2029212795Sdim Offset += Elements = CurSize[Nodes] = LeftSib.size(); 2030212795Sdim Node[Nodes++] = &LeftSib.get<NodeT>(); 2031212795Sdim } 2032212795Sdim 2033212795Sdim // Current node. 2034212795Sdim Elements += CurSize[Nodes] = P.size(Level); 2035243830Sdim Node[Nodes++] = &P.node<NodeT>(Level); 2036212795Sdim 2037212795Sdim // Do we have a right sibling? 2038249423Sdim NodeRef RightSib = P.getRightSibling(Level); 2039218893Sdim if (RightSib) { 2040218893Sdim Elements += CurSize[Nodes] = RightSib.size(); 2041218893Sdim Node[Nodes++] = &RightSib.get<NodeT>(); 2042243830Sdim } 2043218893Sdim 2044218893Sdim // Do we need to allocate a new node? 2045249423Sdim unsigned NewNode = 0; 2046212795Sdim if (Elements + 1 > Nodes * NodeT::Capacity) { 2047212795Sdim // Insert NewNode at the penultimate position, or after a single node. 2048226633Sdim NewNode = Nodes == 1 ? 1 : Nodes - 1; 2049226633Sdim CurSize[Nodes] = CurSize[NewNode]; 2050249423Sdim Node[Nodes] = Node[NewNode]; 2051218893Sdim CurSize[NewNode] = 0; 2052218893Sdim Node[NewNode] = this->map->template newNode<NodeT>(); 2053212795Sdim ++Nodes; 2054243830Sdim } 2055212795Sdim 2056218893Sdim // Compute the new element distribution. 2057212795Sdim unsigned NewSize[4]; 2058249423Sdim IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity, 2059218893Sdim CurSize, NewSize, Offset, true); 2060218893Sdim adjustSiblingSizes(Node, Nodes, CurSize, NewSize); 2061218893Sdim 2062249423Sdim // Move current location to the leftmost node. 2063218893Sdim if (LeftSib) 2064249423Sdim P.moveLeft(Level); 2065249423Sdim 2066249423Sdim // Elements have been rearranged, now update node sizes and stops. 2067218893Sdim bool SplitRoot = false; 2068249423Sdim unsigned Pos = 0; 2069249423Sdim while (true) { 2070226633Sdim KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1); 2071249423Sdim if (NewNode && Pos == NewNode) { 2072226633Sdim SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop); 2073226633Sdim Level += SplitRoot; 2074218893Sdim } else { 2075218893Sdim P.setSize(Level, NewSize[Pos]); 2076212795Sdim setNodeStop(Level, Stop); 2077243830Sdim } 2078243830Sdim if (Pos + 1 == Nodes) 2079212795Sdim break; 2080249423Sdim P.moveRight(Level); 2081234353Sdim ++Pos; 2082243830Sdim } 2083243830Sdim 2084234353Sdim // Where was I? Find NewOffset. 2085249423Sdim while(Pos != NewOffset.first) { 2086239462Sdim P.moveLeft(Level); 2087249423Sdim --Pos; 2088239462Sdim } 2089239462Sdim P.offset(Level) = NewOffset.second; 2090239462Sdim return SplitRoot; 2091243830Sdim} 2092239462Sdim 2093239462Sdim//===----------------------------------------------------------------------===// 2094239462Sdim//--- IntervalMapOverlaps ----// 2095239462Sdim//===----------------------------------------------------------------------===// 2096249423Sdim 2097234353Sdim/// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two 2098249423Sdim/// IntervalMaps. The maps may be different, but the KeyT and Traits types 2099249423Sdim/// should be the same. 2100249423Sdim/// 2101249423Sdim/// Typical uses: 2102249423Sdim/// 2103212795Sdim/// 1. Test for overlap: 2104212795Sdim/// bool overlap = IntervalMapOverlaps(a, b).valid(); 2105249423Sdim/// 2106249423Sdim/// 2. Enumerate overlaps: 2107249423Sdim/// for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... } 2108249423Sdim/// 2109212795Sdimtemplate <typename MapA, typename MapB> 2110212795Sdimclass IntervalMapOverlaps { 2111212795Sdim using KeyType = typename MapA::KeyType; 2112212795Sdim using Traits = typename MapA::KeyTraits; 2113249423Sdim 2114249423Sdim typename MapA::const_iterator posA; 2115212795Sdim typename MapB::const_iterator posB; 2116212795Sdim 2117212795Sdim /// advance - Move posA and posB forward until reaching an overlap, or until 2118226633Sdim /// either meets end. 2119212795Sdim /// Don't move the iterators if they are already overlapping. 2120212795Sdim void advance() { 2121243830Sdim if (!valid()) 2122212795Sdim return; 2123249423Sdim 2124212795Sdim if (Traits::stopLess(posA.stop(), posB.start())) { 2125226633Sdim // A ends before B begins. Catch up. 2126226633Sdim posA.advanceTo(posB.start()); 2127226633Sdim if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start())) 2128226633Sdim return; 2129226633Sdim } else if (Traits::stopLess(posB.stop(), posA.start())) { 2130226633Sdim // B ends before A begins. Catch up. 2131226633Sdim posB.advanceTo(posA.start()); 2132226633Sdim if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start())) 2133234353Sdim return; 2134234353Sdim } else 2135234353Sdim // Already overlapping. 2136226633Sdim return; 2137226633Sdim 2138226633Sdim while (true) { 2139212795Sdim // Make a.end > b.start. 2140226633Sdim posA.advanceTo(posB.start()); 2141226633Sdim if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start())) 2142226633Sdim return; 2143212795Sdim // Make b.end > a.start. 2144212795Sdim posB.advanceTo(posA.start()); 2145243830Sdim if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start())) 2146212795Sdim return; 2147249423Sdim } 2148212795Sdim } 2149226633Sdim 2150226633Sdimpublic: 2151226633Sdim /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b. 2152226633Sdim IntervalMapOverlaps(const MapA &a, const MapB &b) 2153226633Sdim : posA(b.empty() ? a.end() : a.find(b.start())), 2154226633Sdim posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); } 2155226633Sdim 2156226633Sdim /// valid - Return true if iterator is at an overlap. 2157226633Sdim bool valid() const { 2158226633Sdim return posA.valid() && posB.valid(); 2159226633Sdim } 2160234353Sdim 2161234353Sdim /// a - access the left hand side in the overlap. 2162226633Sdim const typename MapA::const_iterator &a() const { return posA; } 2163234353Sdim 2164234353Sdim /// b - access the right hand side in the overlap. 2165234353Sdim const typename MapB::const_iterator &b() const { return posB; } 2166234353Sdim 2167226633Sdim /// start - Beginning of the overlapping interval. 2168226633Sdim KeyType start() const { 2169212795Sdim KeyType ak = a().start(); 2170226633Sdim KeyType bk = b().start(); 2171226633Sdim return Traits::startLess(ak, bk) ? bk : ak; 2172212795Sdim } 2173226633Sdim 2174226633Sdim /// stop - End of the overlapping interval. 2175249423Sdim KeyType stop() const { 2176226633Sdim KeyType ak = a().stop(); 2177249423Sdim KeyType bk = b().stop(); 2178226633Sdim return Traits::startLess(ak, bk) ? ak : bk; 2179212795Sdim } 2180212795Sdim 2181212795Sdim /// skipA - Move to the next overlap that doesn't involve a(). 2182212795Sdim void skipA() { 2183226633Sdim ++posA; 2184226633Sdim advance(); 2185234982Sdim } 2186234982Sdim 2187249423Sdim /// skipB - Move to the next overlap that doesn't involve b(). 2188249423Sdim void skipB() { 2189226633Sdim ++posB; 2190226633Sdim advance(); 2191226633Sdim } 2192226633Sdim 2193226633Sdim /// Preincrement - Move to the next overlap. 2194212795Sdim IntervalMapOverlaps &operator++() { 2195226633Sdim // Bump the iterator that ends first. The other one may have more overlaps. 2196212795Sdim if (Traits::startLess(posB.stop(), posA.stop())) 2197212795Sdim skipB(); 2198212795Sdim else 2199212795Sdim skipA(); 2200249423Sdim return *this; 2201212795Sdim } 2202212795Sdim 2203212795Sdim /// advanceTo - Move to the first overlapping interval with 2204212795Sdim /// stopLess(x, stop()). 2205212795Sdim void advanceTo(KeyType x) { 2206218893Sdim if (!valid()) 2207226633Sdim return; 2208226633Sdim // Make sure advanceTo sees monotonic keys. 2209212795Sdim if (Traits::stopLess(posA.stop(), x)) 2210212795Sdim posA.advanceTo(x); 2211212795Sdim if (Traits::stopLess(posB.stop(), x)) 2212226633Sdim posB.advanceTo(x); 2213212795Sdim advance(); 2214212795Sdim } 2215243830Sdim}; 2216212795Sdim 2217249423Sdim} // end namespace llvm 2218212795Sdim 2219226633Sdim#endif // LLVM_ADT_INTERVALMAP_H 2220226633Sdim