1218885Sdim//===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// This file implements a coalescing interval map for small objects. 11218885Sdim// 12218885Sdim// KeyT objects are mapped to ValT objects. Intervals of keys that map to the 13218885Sdim// same value are represented in a compressed form. 14218885Sdim// 15218885Sdim// Iterators provide ordered access to the compressed intervals rather than the 16218885Sdim// individual keys, and insert and erase operations use key intervals as well. 17218885Sdim// 18218885Sdim// Like SmallVector, IntervalMap will store the first N intervals in the map 19218885Sdim// object itself without any allocations. When space is exhausted it switches to 20218885Sdim// a B+-tree representation with very small overhead for small key and value 21218885Sdim// objects. 22218885Sdim// 23218885Sdim// A Traits class specifies how keys are compared. It also allows IntervalMap to 24218885Sdim// work with both closed and half-open intervals. 25218885Sdim// 26218885Sdim// Keys and values are not stored next to each other in a std::pair, so we don't 27218885Sdim// provide such a value_type. Dereferencing iterators only returns the mapped 28218885Sdim// value. The interval bounds are accessible through the start() and stop() 29218885Sdim// iterator methods. 30218885Sdim// 31218885Sdim// IntervalMap is optimized for small key and value objects, 4 or 8 bytes each 32218885Sdim// is the optimal size. For large objects use std::map instead. 33218885Sdim// 34218885Sdim//===----------------------------------------------------------------------===// 35218885Sdim// 36218885Sdim// Synopsis: 37218885Sdim// 38218885Sdim// template <typename KeyT, typename ValT, unsigned N, typename Traits> 39218885Sdim// class IntervalMap { 40218885Sdim// public: 41218885Sdim// typedef KeyT key_type; 42218885Sdim// typedef ValT mapped_type; 43218885Sdim// typedef RecyclingAllocator<...> Allocator; 44218885Sdim// class iterator; 45218885Sdim// class const_iterator; 46218885Sdim// 47218885Sdim// explicit IntervalMap(Allocator&); 48218885Sdim// ~IntervalMap(): 49218885Sdim// 50218885Sdim// bool empty() const; 51218885Sdim// KeyT start() const; 52218885Sdim// KeyT stop() const; 53218885Sdim// ValT lookup(KeyT x, Value NotFound = Value()) const; 54218885Sdim// 55218885Sdim// const_iterator begin() const; 56218885Sdim// const_iterator end() const; 57218885Sdim// iterator begin(); 58218885Sdim// iterator end(); 59218885Sdim// const_iterator find(KeyT x) const; 60218885Sdim// iterator find(KeyT x); 61218885Sdim// 62218885Sdim// void insert(KeyT a, KeyT b, ValT y); 63218885Sdim// void clear(); 64218885Sdim// }; 65218885Sdim// 66218885Sdim// template <typename KeyT, typename ValT, unsigned N, typename Traits> 67218885Sdim// class IntervalMap::const_iterator : 68218885Sdim// public std::iterator<std::bidirectional_iterator_tag, ValT> { 69218885Sdim// public: 70218885Sdim// bool operator==(const const_iterator &) const; 71218885Sdim// bool operator!=(const const_iterator &) const; 72218885Sdim// bool valid() const; 73218885Sdim// 74218885Sdim// const KeyT &start() const; 75218885Sdim// const KeyT &stop() const; 76218885Sdim// const ValT &value() const; 77218885Sdim// const ValT &operator*() const; 78218885Sdim// const ValT *operator->() const; 79218885Sdim// 80218885Sdim// const_iterator &operator++(); 81218885Sdim// const_iterator &operator++(int); 82218885Sdim// const_iterator &operator--(); 83218885Sdim// const_iterator &operator--(int); 84218885Sdim// void goToBegin(); 85218885Sdim// void goToEnd(); 86218885Sdim// void find(KeyT x); 87218885Sdim// void advanceTo(KeyT x); 88218885Sdim// }; 89218885Sdim// 90218885Sdim// template <typename KeyT, typename ValT, unsigned N, typename Traits> 91218885Sdim// class IntervalMap::iterator : public const_iterator { 92218885Sdim// public: 93218885Sdim// void insert(KeyT a, KeyT b, Value y); 94218885Sdim// void erase(); 95218885Sdim// }; 96218885Sdim// 97218885Sdim//===----------------------------------------------------------------------===// 98218885Sdim 99218885Sdim#ifndef LLVM_ADT_INTERVALMAP_H 100218885Sdim#define LLVM_ADT_INTERVALMAP_H 101218885Sdim 102249423Sdim#include "llvm/ADT/PointerIntPair.h" 103218885Sdim#include "llvm/ADT/SmallVector.h" 104218885Sdim#include "llvm/Support/Allocator.h" 105218885Sdim#include "llvm/Support/RecyclingAllocator.h" 106218885Sdim#include <iterator> 107218885Sdim 108218885Sdimnamespace llvm { 109218885Sdim 110218885Sdim 111218885Sdim//===----------------------------------------------------------------------===// 112218885Sdim//--- Key traits ---// 113218885Sdim//===----------------------------------------------------------------------===// 114218885Sdim// 115218885Sdim// The IntervalMap works with closed or half-open intervals. 116218885Sdim// Adjacent intervals that map to the same value are coalesced. 117218885Sdim// 118218885Sdim// The IntervalMapInfo traits class is used to determine if a key is contained 119218885Sdim// in an interval, and if two intervals are adjacent so they can be coalesced. 120218885Sdim// The provided implementation works for closed integer intervals, other keys 121218885Sdim// probably need a specialized version. 122218885Sdim// 123218885Sdim// The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x). 124218885Sdim// 125218885Sdim// It is assumed that (a;b] half-open intervals are not used, only [a;b) is 126218885Sdim// allowed. This is so that stopLess(a, b) can be used to determine if two 127218885Sdim// intervals overlap. 128218885Sdim// 129218885Sdim//===----------------------------------------------------------------------===// 130218885Sdim 131218885Sdimtemplate <typename T> 132218885Sdimstruct IntervalMapInfo { 133218885Sdim 134218885Sdim /// startLess - Return true if x is not in [a;b]. 135218885Sdim /// This is x < a both for closed intervals and for [a;b) half-open intervals. 136218885Sdim static inline bool startLess(const T &x, const T &a) { 137218885Sdim return x < a; 138218885Sdim } 139218885Sdim 140218885Sdim /// stopLess - Return true if x is not in [a;b]. 141218885Sdim /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals. 142218885Sdim static inline bool stopLess(const T &b, const T &x) { 143218885Sdim return b < x; 144218885Sdim } 145218885Sdim 146218885Sdim /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce. 147218885Sdim /// This is a+1 == b for closed intervals, a == b for half-open intervals. 148218885Sdim static inline bool adjacent(const T &a, const T &b) { 149218885Sdim return a+1 == b; 150218885Sdim } 151218885Sdim 152218885Sdim}; 153218885Sdim 154249423Sdimtemplate <typename T> 155249423Sdimstruct IntervalMapHalfOpenInfo { 156249423Sdim 157249423Sdim /// startLess - Return true if x is not in [a;b). 158249423Sdim static inline bool startLess(const T &x, const T &a) { 159249423Sdim return x < a; 160249423Sdim } 161249423Sdim 162249423Sdim /// stopLess - Return true if x is not in [a;b). 163249423Sdim static inline bool stopLess(const T &b, const T &x) { 164249423Sdim return b <= x; 165249423Sdim } 166249423Sdim 167249423Sdim /// adjacent - Return true when the intervals [x;a) and [b;y) can coalesce. 168249423Sdim static inline bool adjacent(const T &a, const T &b) { 169249423Sdim return a == b; 170249423Sdim } 171249423Sdim 172249423Sdim}; 173249423Sdim 174218885Sdim/// IntervalMapImpl - Namespace used for IntervalMap implementation details. 175218885Sdim/// It should be considered private to the implementation. 176218885Sdimnamespace IntervalMapImpl { 177218885Sdim 178218885Sdim// Forward declarations. 179218885Sdimtemplate <typename, typename, unsigned, typename> class LeafNode; 180218885Sdimtemplate <typename, typename, unsigned, typename> class BranchNode; 181218885Sdim 182218885Sdimtypedef std::pair<unsigned,unsigned> IdxPair; 183218885Sdim 184218885Sdim 185218885Sdim//===----------------------------------------------------------------------===// 186218885Sdim//--- IntervalMapImpl::NodeBase ---// 187218885Sdim//===----------------------------------------------------------------------===// 188218885Sdim// 189218885Sdim// Both leaf and branch nodes store vectors of pairs. 190218885Sdim// Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT). 191218885Sdim// 192218885Sdim// Keys and values are stored in separate arrays to avoid padding caused by 193218885Sdim// different object alignments. This also helps improve locality of reference 194218885Sdim// when searching the keys. 195218885Sdim// 196218885Sdim// The nodes don't know how many elements they contain - that information is 197218885Sdim// stored elsewhere. Omitting the size field prevents padding and allows a node 198218885Sdim// to fill the allocated cache lines completely. 199218885Sdim// 200218885Sdim// These are typical key and value sizes, the node branching factor (N), and 201218885Sdim// wasted space when nodes are sized to fit in three cache lines (192 bytes): 202218885Sdim// 203218885Sdim// T1 T2 N Waste Used by 204218885Sdim// 4 4 24 0 Branch<4> (32-bit pointers) 205218885Sdim// 8 4 16 0 Leaf<4,4>, Branch<4> 206218885Sdim// 8 8 12 0 Leaf<4,8>, Branch<8> 207218885Sdim// 16 4 9 12 Leaf<8,4> 208218885Sdim// 16 8 8 0 Leaf<8,8> 209218885Sdim// 210218885Sdim//===----------------------------------------------------------------------===// 211218885Sdim 212218885Sdimtemplate <typename T1, typename T2, unsigned N> 213218885Sdimclass NodeBase { 214218885Sdimpublic: 215218885Sdim enum { Capacity = N }; 216218885Sdim 217218885Sdim T1 first[N]; 218218885Sdim T2 second[N]; 219218885Sdim 220218885Sdim /// copy - Copy elements from another node. 221218885Sdim /// @param Other Node elements are copied from. 222218885Sdim /// @param i Beginning of the source range in other. 223218885Sdim /// @param j Beginning of the destination range in this. 224218885Sdim /// @param Count Number of elements to copy. 225218885Sdim template <unsigned M> 226218885Sdim void copy(const NodeBase<T1, T2, M> &Other, unsigned i, 227218885Sdim unsigned j, unsigned Count) { 228218885Sdim assert(i + Count <= M && "Invalid source range"); 229218885Sdim assert(j + Count <= N && "Invalid dest range"); 230218885Sdim for (unsigned e = i + Count; i != e; ++i, ++j) { 231218885Sdim first[j] = Other.first[i]; 232218885Sdim second[j] = Other.second[i]; 233218885Sdim } 234218885Sdim } 235218885Sdim 236218885Sdim /// moveLeft - Move elements to the left. 237218885Sdim /// @param i Beginning of the source range. 238218885Sdim /// @param j Beginning of the destination range. 239218885Sdim /// @param Count Number of elements to copy. 240218885Sdim void moveLeft(unsigned i, unsigned j, unsigned Count) { 241218885Sdim assert(j <= i && "Use moveRight shift elements right"); 242218885Sdim copy(*this, i, j, Count); 243218885Sdim } 244218885Sdim 245218885Sdim /// moveRight - Move elements to the right. 246218885Sdim /// @param i Beginning of the source range. 247218885Sdim /// @param j Beginning of the destination range. 248218885Sdim /// @param Count Number of elements to copy. 249218885Sdim void moveRight(unsigned i, unsigned j, unsigned Count) { 250218885Sdim assert(i <= j && "Use moveLeft shift elements left"); 251218885Sdim assert(j + Count <= N && "Invalid range"); 252218885Sdim while (Count--) { 253218885Sdim first[j + Count] = first[i + Count]; 254218885Sdim second[j + Count] = second[i + Count]; 255218885Sdim } 256218885Sdim } 257218885Sdim 258218885Sdim /// erase - Erase elements [i;j). 259218885Sdim /// @param i Beginning of the range to erase. 260218885Sdim /// @param j End of the range. (Exclusive). 261218885Sdim /// @param Size Number of elements in node. 262218885Sdim void erase(unsigned i, unsigned j, unsigned Size) { 263218885Sdim moveLeft(j, i, Size - j); 264218885Sdim } 265218885Sdim 266218885Sdim /// erase - Erase element at i. 267218885Sdim /// @param i Index of element to erase. 268218885Sdim /// @param Size Number of elements in node. 269218885Sdim void erase(unsigned i, unsigned Size) { 270218885Sdim erase(i, i+1, Size); 271218885Sdim } 272218885Sdim 273218885Sdim /// shift - Shift elements [i;size) 1 position to the right. 274218885Sdim /// @param i Beginning of the range to move. 275218885Sdim /// @param Size Number of elements in node. 276218885Sdim void shift(unsigned i, unsigned Size) { 277218885Sdim moveRight(i, i + 1, Size - i); 278218885Sdim } 279218885Sdim 280218885Sdim /// transferToLeftSib - Transfer elements to a left sibling node. 281218885Sdim /// @param Size Number of elements in this. 282218885Sdim /// @param Sib Left sibling node. 283218885Sdim /// @param SSize Number of elements in sib. 284218885Sdim /// @param Count Number of elements to transfer. 285218885Sdim void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, 286218885Sdim unsigned Count) { 287218885Sdim Sib.copy(*this, 0, SSize, Count); 288218885Sdim erase(0, Count, Size); 289218885Sdim } 290218885Sdim 291218885Sdim /// transferToRightSib - Transfer elements to a right sibling node. 292218885Sdim /// @param Size Number of elements in this. 293218885Sdim /// @param Sib Right sibling node. 294218885Sdim /// @param SSize Number of elements in sib. 295218885Sdim /// @param Count Number of elements to transfer. 296218885Sdim void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize, 297218885Sdim unsigned Count) { 298218885Sdim Sib.moveRight(0, Count, SSize); 299218885Sdim Sib.copy(*this, Size-Count, 0, Count); 300218885Sdim } 301218885Sdim 302218885Sdim /// adjustFromLeftSib - Adjust the number if elements in this node by moving 303218885Sdim /// elements to or from a left sibling node. 304218885Sdim /// @param Size Number of elements in this. 305218885Sdim /// @param Sib Right sibling node. 306218885Sdim /// @param SSize Number of elements in sib. 307218885Sdim /// @param Add The number of elements to add to this node, possibly < 0. 308218885Sdim /// @return Number of elements added to this node, possibly negative. 309218885Sdim int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) { 310218885Sdim if (Add > 0) { 311218885Sdim // We want to grow, copy from sib. 312218885Sdim unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size); 313218885Sdim Sib.transferToRightSib(SSize, *this, Size, Count); 314218885Sdim return Count; 315218885Sdim } else { 316218885Sdim // We want to shrink, copy to sib. 317218885Sdim unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize); 318218885Sdim transferToLeftSib(Size, Sib, SSize, Count); 319218885Sdim return -Count; 320218885Sdim } 321218885Sdim } 322218885Sdim}; 323218885Sdim 324218885Sdim/// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes. 325218885Sdim/// @param Node Array of pointers to sibling nodes. 326218885Sdim/// @param Nodes Number of nodes. 327218885Sdim/// @param CurSize Array of current node sizes, will be overwritten. 328218885Sdim/// @param NewSize Array of desired node sizes. 329218885Sdimtemplate <typename NodeT> 330218885Sdimvoid adjustSiblingSizes(NodeT *Node[], unsigned Nodes, 331218885Sdim unsigned CurSize[], const unsigned NewSize[]) { 332218885Sdim // Move elements right. 333218885Sdim for (int n = Nodes - 1; n; --n) { 334218885Sdim if (CurSize[n] == NewSize[n]) 335218885Sdim continue; 336218885Sdim for (int m = n - 1; m != -1; --m) { 337218885Sdim int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m], 338218885Sdim NewSize[n] - CurSize[n]); 339218885Sdim CurSize[m] -= d; 340218885Sdim CurSize[n] += d; 341218885Sdim // Keep going if the current node was exhausted. 342218885Sdim if (CurSize[n] >= NewSize[n]) 343218885Sdim break; 344218885Sdim } 345218885Sdim } 346218885Sdim 347218885Sdim if (Nodes == 0) 348218885Sdim return; 349218885Sdim 350218885Sdim // Move elements left. 351218885Sdim for (unsigned n = 0; n != Nodes - 1; ++n) { 352218885Sdim if (CurSize[n] == NewSize[n]) 353218885Sdim continue; 354218885Sdim for (unsigned m = n + 1; m != Nodes; ++m) { 355218885Sdim int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n], 356218885Sdim CurSize[n] - NewSize[n]); 357218885Sdim CurSize[m] += d; 358218885Sdim CurSize[n] -= d; 359218885Sdim // Keep going if the current node was exhausted. 360218885Sdim if (CurSize[n] >= NewSize[n]) 361218885Sdim break; 362218885Sdim } 363218885Sdim } 364218885Sdim 365218885Sdim#ifndef NDEBUG 366218885Sdim for (unsigned n = 0; n != Nodes; n++) 367218885Sdim assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle"); 368218885Sdim#endif 369218885Sdim} 370218885Sdim 371218885Sdim/// IntervalMapImpl::distribute - Compute a new distribution of node elements 372218885Sdim/// after an overflow or underflow. Reserve space for a new element at Position, 373218885Sdim/// and compute the node that will hold Position after redistributing node 374218885Sdim/// elements. 375218885Sdim/// 376218885Sdim/// It is required that 377218885Sdim/// 378218885Sdim/// Elements == sum(CurSize), and 379218885Sdim/// Elements + Grow <= Nodes * Capacity. 380218885Sdim/// 381218885Sdim/// NewSize[] will be filled in such that: 382218885Sdim/// 383218885Sdim/// sum(NewSize) == Elements, and 384218885Sdim/// NewSize[i] <= Capacity. 385218885Sdim/// 386218885Sdim/// The returned index is the node where Position will go, so: 387218885Sdim/// 388218885Sdim/// sum(NewSize[0..idx-1]) <= Position 389218885Sdim/// sum(NewSize[0..idx]) >= Position 390218885Sdim/// 391218885Sdim/// The last equality, sum(NewSize[0..idx]) == Position, can only happen when 392218885Sdim/// Grow is set and NewSize[idx] == Capacity-1. The index points to the node 393218885Sdim/// before the one holding the Position'th element where there is room for an 394218885Sdim/// insertion. 395218885Sdim/// 396218885Sdim/// @param Nodes The number of nodes. 397218885Sdim/// @param Elements Total elements in all nodes. 398218885Sdim/// @param Capacity The capacity of each node. 399218885Sdim/// @param CurSize Array[Nodes] of current node sizes, or NULL. 400218885Sdim/// @param NewSize Array[Nodes] to receive the new node sizes. 401218885Sdim/// @param Position Insert position. 402218885Sdim/// @param Grow Reserve space for a new element at Position. 403218885Sdim/// @return (node, offset) for Position. 404218885SdimIdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, 405218885Sdim const unsigned *CurSize, unsigned NewSize[], 406218885Sdim unsigned Position, bool Grow); 407218885Sdim 408218885Sdim 409218885Sdim//===----------------------------------------------------------------------===// 410218885Sdim//--- IntervalMapImpl::NodeSizer ---// 411218885Sdim//===----------------------------------------------------------------------===// 412218885Sdim// 413218885Sdim// Compute node sizes from key and value types. 414218885Sdim// 415218885Sdim// The branching factors are chosen to make nodes fit in three cache lines. 416218885Sdim// This may not be possible if keys or values are very large. Such large objects 417218885Sdim// are handled correctly, but a std::map would probably give better performance. 418218885Sdim// 419218885Sdim//===----------------------------------------------------------------------===// 420218885Sdim 421218885Sdimenum { 422218885Sdim // Cache line size. Most architectures have 32 or 64 byte cache lines. 423218885Sdim // We use 64 bytes here because it provides good branching factors. 424218885Sdim Log2CacheLine = 6, 425218885Sdim CacheLineBytes = 1 << Log2CacheLine, 426218885Sdim DesiredNodeBytes = 3 * CacheLineBytes 427218885Sdim}; 428218885Sdim 429218885Sdimtemplate <typename KeyT, typename ValT> 430218885Sdimstruct NodeSizer { 431218885Sdim enum { 432218885Sdim // Compute the leaf node branching factor that makes a node fit in three 433218885Sdim // cache lines. The branching factor must be at least 3, or some B+-tree 434218885Sdim // balancing algorithms won't work. 435218885Sdim // LeafSize can't be larger than CacheLineBytes. This is required by the 436218885Sdim // PointerIntPair used by NodeRef. 437218885Sdim DesiredLeafSize = DesiredNodeBytes / 438218885Sdim static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)), 439218885Sdim MinLeafSize = 3, 440218885Sdim LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize 441218885Sdim }; 442218885Sdim 443218885Sdim typedef NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize> LeafBase; 444218885Sdim 445218885Sdim enum { 446218885Sdim // Now that we have the leaf branching factor, compute the actual allocation 447218885Sdim // unit size by rounding up to a whole number of cache lines. 448218885Sdim AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1), 449218885Sdim 450218885Sdim // Determine the branching factor for branch nodes. 451218885Sdim BranchSize = AllocBytes / 452218885Sdim static_cast<unsigned>(sizeof(KeyT) + sizeof(void*)) 453218885Sdim }; 454218885Sdim 455218885Sdim /// Allocator - The recycling allocator used for both branch and leaf nodes. 456218885Sdim /// This typedef is very likely to be identical for all IntervalMaps with 457218885Sdim /// reasonably sized entries, so the same allocator can be shared among 458218885Sdim /// different kinds of maps. 459218885Sdim typedef RecyclingAllocator<BumpPtrAllocator, char, 460218885Sdim AllocBytes, CacheLineBytes> Allocator; 461218885Sdim 462218885Sdim}; 463218885Sdim 464218885Sdim 465218885Sdim//===----------------------------------------------------------------------===// 466218885Sdim//--- IntervalMapImpl::NodeRef ---// 467218885Sdim//===----------------------------------------------------------------------===// 468218885Sdim// 469218885Sdim// B+-tree nodes can be leaves or branches, so we need a polymorphic node 470218885Sdim// pointer that can point to both kinds. 471218885Sdim// 472218885Sdim// All nodes are cache line aligned and the low 6 bits of a node pointer are 473218885Sdim// always 0. These bits are used to store the number of elements in the 474218885Sdim// referenced node. Besides saving space, placing node sizes in the parents 475218885Sdim// allow tree balancing algorithms to run without faulting cache lines for nodes 476218885Sdim// that may not need to be modified. 477218885Sdim// 478218885Sdim// A NodeRef doesn't know whether it references a leaf node or a branch node. 479218885Sdim// It is the responsibility of the caller to use the correct types. 480218885Sdim// 481218885Sdim// Nodes are never supposed to be empty, and it is invalid to store a node size 482218885Sdim// of 0 in a NodeRef. The valid range of sizes is 1-64. 483218885Sdim// 484218885Sdim//===----------------------------------------------------------------------===// 485218885Sdim 486218885Sdimclass NodeRef { 487218885Sdim struct CacheAlignedPointerTraits { 488218885Sdim static inline void *getAsVoidPointer(void *P) { return P; } 489218885Sdim static inline void *getFromVoidPointer(void *P) { return P; } 490218885Sdim enum { NumLowBitsAvailable = Log2CacheLine }; 491218885Sdim }; 492218885Sdim PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip; 493218885Sdim 494218885Sdimpublic: 495218885Sdim /// NodeRef - Create a null ref. 496218885Sdim NodeRef() {} 497218885Sdim 498218885Sdim /// operator bool - Detect a null ref. 499218885Sdim operator bool() const { return pip.getOpaqueValue(); } 500218885Sdim 501218885Sdim /// NodeRef - Create a reference to the node p with n elements. 502218885Sdim template <typename NodeT> 503218885Sdim NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) { 504218885Sdim assert(n <= NodeT::Capacity && "Size too big for node"); 505218885Sdim } 506218885Sdim 507218885Sdim /// size - Return the number of elements in the referenced node. 508218885Sdim unsigned size() const { return pip.getInt() + 1; } 509218885Sdim 510218885Sdim /// setSize - Update the node size. 511218885Sdim void setSize(unsigned n) { pip.setInt(n - 1); } 512218885Sdim 513218885Sdim /// subtree - Access the i'th subtree reference in a branch node. 514218885Sdim /// This depends on branch nodes storing the NodeRef array as their first 515218885Sdim /// member. 516218885Sdim NodeRef &subtree(unsigned i) const { 517218885Sdim return reinterpret_cast<NodeRef*>(pip.getPointer())[i]; 518218885Sdim } 519218885Sdim 520218885Sdim /// get - Dereference as a NodeT reference. 521218885Sdim template <typename NodeT> 522218885Sdim NodeT &get() const { 523218885Sdim return *reinterpret_cast<NodeT*>(pip.getPointer()); 524218885Sdim } 525218885Sdim 526218885Sdim bool operator==(const NodeRef &RHS) const { 527218885Sdim if (pip == RHS.pip) 528218885Sdim return true; 529218885Sdim assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs"); 530218885Sdim return false; 531218885Sdim } 532218885Sdim 533218885Sdim bool operator!=(const NodeRef &RHS) const { 534218885Sdim return !operator==(RHS); 535218885Sdim } 536218885Sdim}; 537218885Sdim 538218885Sdim//===----------------------------------------------------------------------===// 539218885Sdim//--- IntervalMapImpl::LeafNode ---// 540218885Sdim//===----------------------------------------------------------------------===// 541218885Sdim// 542218885Sdim// Leaf nodes store up to N disjoint intervals with corresponding values. 543218885Sdim// 544218885Sdim// The intervals are kept sorted and fully coalesced so there are no adjacent 545218885Sdim// intervals mapping to the same value. 546218885Sdim// 547218885Sdim// These constraints are always satisfied: 548218885Sdim// 549218885Sdim// - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals. 550218885Sdim// 551218885Sdim// - Traits::stopLess(stop(i), start(i + 1) - Sorted. 552218885Sdim// 553218885Sdim// - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1)) 554218885Sdim// - Fully coalesced. 555218885Sdim// 556218885Sdim//===----------------------------------------------------------------------===// 557218885Sdim 558218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 559218885Sdimclass LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> { 560218885Sdimpublic: 561218885Sdim const KeyT &start(unsigned i) const { return this->first[i].first; } 562218885Sdim const KeyT &stop(unsigned i) const { return this->first[i].second; } 563218885Sdim const ValT &value(unsigned i) const { return this->second[i]; } 564218885Sdim 565218885Sdim KeyT &start(unsigned i) { return this->first[i].first; } 566218885Sdim KeyT &stop(unsigned i) { return this->first[i].second; } 567218885Sdim ValT &value(unsigned i) { return this->second[i]; } 568218885Sdim 569218885Sdim /// findFrom - Find the first interval after i that may contain x. 570218885Sdim /// @param i Starting index for the search. 571218885Sdim /// @param Size Number of elements in node. 572218885Sdim /// @param x Key to search for. 573218885Sdim /// @return First index with !stopLess(key[i].stop, x), or size. 574218885Sdim /// This is the first interval that can possibly contain x. 575218885Sdim unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { 576218885Sdim assert(i <= Size && Size <= N && "Bad indices"); 577218885Sdim assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 578218885Sdim "Index is past the needed point"); 579218885Sdim while (i != Size && Traits::stopLess(stop(i), x)) ++i; 580218885Sdim return i; 581218885Sdim } 582218885Sdim 583218885Sdim /// safeFind - Find an interval that is known to exist. This is the same as 584218885Sdim /// findFrom except is it assumed that x is at least within range of the last 585218885Sdim /// interval. 586218885Sdim /// @param i Starting index for the search. 587218885Sdim /// @param x Key to search for. 588218885Sdim /// @return First index with !stopLess(key[i].stop, x), never size. 589218885Sdim /// This is the first interval that can possibly contain x. 590218885Sdim unsigned safeFind(unsigned i, KeyT x) const { 591218885Sdim assert(i < N && "Bad index"); 592218885Sdim assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 593218885Sdim "Index is past the needed point"); 594218885Sdim while (Traits::stopLess(stop(i), x)) ++i; 595218885Sdim assert(i < N && "Unsafe intervals"); 596218885Sdim return i; 597218885Sdim } 598218885Sdim 599218885Sdim /// safeLookup - Lookup mapped value for a safe key. 600218885Sdim /// It is assumed that x is within range of the last entry. 601218885Sdim /// @param x Key to search for. 602218885Sdim /// @param NotFound Value to return if x is not in any interval. 603218885Sdim /// @return The mapped value at x or NotFound. 604218885Sdim ValT safeLookup(KeyT x, ValT NotFound) const { 605218885Sdim unsigned i = safeFind(0, x); 606218885Sdim return Traits::startLess(x, start(i)) ? NotFound : value(i); 607218885Sdim } 608218885Sdim 609218885Sdim unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y); 610218885Sdim}; 611218885Sdim 612218885Sdim/// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as 613218885Sdim/// possible. This may cause the node to grow by 1, or it may cause the node 614218885Sdim/// to shrink because of coalescing. 615218885Sdim/// @param i Starting index = insertFrom(0, size, a) 616218885Sdim/// @param Size Number of elements in node. 617218885Sdim/// @param a Interval start. 618218885Sdim/// @param b Interval stop. 619218885Sdim/// @param y Value be mapped. 620218885Sdim/// @return (insert position, new size), or (i, Capacity+1) on overflow. 621218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 622218885Sdimunsigned LeafNode<KeyT, ValT, N, Traits>:: 623218885SdiminsertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) { 624218885Sdim unsigned i = Pos; 625218885Sdim assert(i <= Size && Size <= N && "Invalid index"); 626218885Sdim assert(!Traits::stopLess(b, a) && "Invalid interval"); 627218885Sdim 628218885Sdim // Verify the findFrom invariant. 629218885Sdim assert((i == 0 || Traits::stopLess(stop(i - 1), a))); 630218885Sdim assert((i == Size || !Traits::stopLess(stop(i), a))); 631218885Sdim assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert"); 632218885Sdim 633218885Sdim // Coalesce with previous interval. 634218885Sdim if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) { 635218885Sdim Pos = i - 1; 636218885Sdim // Also coalesce with next interval? 637218885Sdim if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) { 638218885Sdim stop(i - 1) = stop(i); 639218885Sdim this->erase(i, Size); 640218885Sdim return Size - 1; 641218885Sdim } 642218885Sdim stop(i - 1) = b; 643218885Sdim return Size; 644218885Sdim } 645218885Sdim 646218885Sdim // Detect overflow. 647218885Sdim if (i == N) 648218885Sdim return N + 1; 649218885Sdim 650218885Sdim // Add new interval at end. 651218885Sdim if (i == Size) { 652218885Sdim start(i) = a; 653218885Sdim stop(i) = b; 654218885Sdim value(i) = y; 655218885Sdim return Size + 1; 656218885Sdim } 657218885Sdim 658218885Sdim // Try to coalesce with following interval. 659218885Sdim if (value(i) == y && Traits::adjacent(b, start(i))) { 660218885Sdim start(i) = a; 661218885Sdim return Size; 662218885Sdim } 663218885Sdim 664218885Sdim // We must insert before i. Detect overflow. 665218885Sdim if (Size == N) 666218885Sdim return N + 1; 667218885Sdim 668218885Sdim // Insert before i. 669218885Sdim this->shift(i, Size); 670218885Sdim start(i) = a; 671218885Sdim stop(i) = b; 672218885Sdim value(i) = y; 673218885Sdim return Size + 1; 674218885Sdim} 675218885Sdim 676218885Sdim 677218885Sdim//===----------------------------------------------------------------------===// 678218885Sdim//--- IntervalMapImpl::BranchNode ---// 679218885Sdim//===----------------------------------------------------------------------===// 680218885Sdim// 681218885Sdim// A branch node stores references to 1--N subtrees all of the same height. 682218885Sdim// 683218885Sdim// The key array in a branch node holds the rightmost stop key of each subtree. 684218885Sdim// It is redundant to store the last stop key since it can be found in the 685218885Sdim// parent node, but doing so makes tree balancing a lot simpler. 686218885Sdim// 687218885Sdim// It is unusual for a branch node to only have one subtree, but it can happen 688218885Sdim// in the root node if it is smaller than the normal nodes. 689218885Sdim// 690218885Sdim// When all of the leaf nodes from all the subtrees are concatenated, they must 691218885Sdim// satisfy the same constraints as a single leaf node. They must be sorted, 692218885Sdim// sane, and fully coalesced. 693218885Sdim// 694218885Sdim//===----------------------------------------------------------------------===// 695218885Sdim 696218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 697218885Sdimclass BranchNode : public NodeBase<NodeRef, KeyT, N> { 698218885Sdimpublic: 699218885Sdim const KeyT &stop(unsigned i) const { return this->second[i]; } 700218885Sdim const NodeRef &subtree(unsigned i) const { return this->first[i]; } 701218885Sdim 702218885Sdim KeyT &stop(unsigned i) { return this->second[i]; } 703218885Sdim NodeRef &subtree(unsigned i) { return this->first[i]; } 704218885Sdim 705218885Sdim /// findFrom - Find the first subtree after i that may contain x. 706218885Sdim /// @param i Starting index for the search. 707218885Sdim /// @param Size Number of elements in node. 708218885Sdim /// @param x Key to search for. 709218885Sdim /// @return First index with !stopLess(key[i], x), or size. 710218885Sdim /// This is the first subtree that can possibly contain x. 711218885Sdim unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { 712218885Sdim assert(i <= Size && Size <= N && "Bad indices"); 713218885Sdim assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 714218885Sdim "Index to findFrom is past the needed point"); 715218885Sdim while (i != Size && Traits::stopLess(stop(i), x)) ++i; 716218885Sdim return i; 717218885Sdim } 718218885Sdim 719218885Sdim /// safeFind - Find a subtree that is known to exist. This is the same as 720218885Sdim /// findFrom except is it assumed that x is in range. 721218885Sdim /// @param i Starting index for the search. 722218885Sdim /// @param x Key to search for. 723218885Sdim /// @return First index with !stopLess(key[i], x), never size. 724218885Sdim /// This is the first subtree that can possibly contain x. 725218885Sdim unsigned safeFind(unsigned i, KeyT x) const { 726218885Sdim assert(i < N && "Bad index"); 727218885Sdim assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 728218885Sdim "Index is past the needed point"); 729218885Sdim while (Traits::stopLess(stop(i), x)) ++i; 730218885Sdim assert(i < N && "Unsafe intervals"); 731218885Sdim return i; 732218885Sdim } 733218885Sdim 734218885Sdim /// safeLookup - Get the subtree containing x, Assuming that x is in range. 735218885Sdim /// @param x Key to search for. 736218885Sdim /// @return Subtree containing x 737218885Sdim NodeRef safeLookup(KeyT x) const { 738218885Sdim return subtree(safeFind(0, x)); 739218885Sdim } 740218885Sdim 741218885Sdim /// insert - Insert a new (subtree, stop) pair. 742218885Sdim /// @param i Insert position, following entries will be shifted. 743218885Sdim /// @param Size Number of elements in node. 744218885Sdim /// @param Node Subtree to insert. 745218885Sdim /// @param Stop Last key in subtree. 746218885Sdim void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) { 747218885Sdim assert(Size < N && "branch node overflow"); 748218885Sdim assert(i <= Size && "Bad insert position"); 749218885Sdim this->shift(i, Size); 750218885Sdim subtree(i) = Node; 751218885Sdim stop(i) = Stop; 752218885Sdim } 753218885Sdim}; 754218885Sdim 755218885Sdim//===----------------------------------------------------------------------===// 756218885Sdim//--- IntervalMapImpl::Path ---// 757218885Sdim//===----------------------------------------------------------------------===// 758218885Sdim// 759218885Sdim// A Path is used by iterators to represent a position in a B+-tree, and the 760218885Sdim// path to get there from the root. 761218885Sdim// 762234353Sdim// The Path class also contains the tree navigation code that doesn't have to 763218885Sdim// be templatized. 764218885Sdim// 765218885Sdim//===----------------------------------------------------------------------===// 766218885Sdim 767218885Sdimclass Path { 768218885Sdim /// Entry - Each step in the path is a node pointer and an offset into that 769218885Sdim /// node. 770218885Sdim struct Entry { 771218885Sdim void *node; 772218885Sdim unsigned size; 773218885Sdim unsigned offset; 774218885Sdim 775218885Sdim Entry(void *Node, unsigned Size, unsigned Offset) 776218885Sdim : node(Node), size(Size), offset(Offset) {} 777218885Sdim 778218885Sdim Entry(NodeRef Node, unsigned Offset) 779218885Sdim : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {} 780218885Sdim 781218885Sdim NodeRef &subtree(unsigned i) const { 782218885Sdim return reinterpret_cast<NodeRef*>(node)[i]; 783218885Sdim } 784218885Sdim }; 785218885Sdim 786218885Sdim /// path - The path entries, path[0] is the root node, path.back() is a leaf. 787218885Sdim SmallVector<Entry, 4> path; 788218885Sdim 789218885Sdimpublic: 790218885Sdim // Node accessors. 791218885Sdim template <typename NodeT> NodeT &node(unsigned Level) const { 792218885Sdim return *reinterpret_cast<NodeT*>(path[Level].node); 793218885Sdim } 794218885Sdim unsigned size(unsigned Level) const { return path[Level].size; } 795218885Sdim unsigned offset(unsigned Level) const { return path[Level].offset; } 796218885Sdim unsigned &offset(unsigned Level) { return path[Level].offset; } 797218885Sdim 798218885Sdim // Leaf accessors. 799218885Sdim template <typename NodeT> NodeT &leaf() const { 800218885Sdim return *reinterpret_cast<NodeT*>(path.back().node); 801218885Sdim } 802218885Sdim unsigned leafSize() const { return path.back().size; } 803218885Sdim unsigned leafOffset() const { return path.back().offset; } 804218885Sdim unsigned &leafOffset() { return path.back().offset; } 805218885Sdim 806218885Sdim /// valid - Return true if path is at a valid node, not at end(). 807218885Sdim bool valid() const { 808218885Sdim return !path.empty() && path.front().offset < path.front().size; 809218885Sdim } 810218885Sdim 811218885Sdim /// height - Return the height of the tree corresponding to this path. 812218885Sdim /// This matches map->height in a full path. 813218885Sdim unsigned height() const { return path.size() - 1; } 814218885Sdim 815218885Sdim /// subtree - Get the subtree referenced from Level. When the path is 816218885Sdim /// consistent, node(Level + 1) == subtree(Level). 817218885Sdim /// @param Level 0..height-1. The leaves have no subtrees. 818218885Sdim NodeRef &subtree(unsigned Level) const { 819218885Sdim return path[Level].subtree(path[Level].offset); 820218885Sdim } 821218885Sdim 822218885Sdim /// reset - Reset cached information about node(Level) from subtree(Level -1). 823218885Sdim /// @param Level 1..height. THe node to update after parent node changed. 824218885Sdim void reset(unsigned Level) { 825218885Sdim path[Level] = Entry(subtree(Level - 1), offset(Level)); 826218885Sdim } 827218885Sdim 828218885Sdim /// push - Add entry to path. 829218885Sdim /// @param Node Node to add, should be subtree(path.size()-1). 830218885Sdim /// @param Offset Offset into Node. 831218885Sdim void push(NodeRef Node, unsigned Offset) { 832218885Sdim path.push_back(Entry(Node, Offset)); 833218885Sdim } 834218885Sdim 835218885Sdim /// pop - Remove the last path entry. 836218885Sdim void pop() { 837218885Sdim path.pop_back(); 838218885Sdim } 839218885Sdim 840218885Sdim /// setSize - Set the size of a node both in the path and in the tree. 841218885Sdim /// @param Level 0..height. Note that setting the root size won't change 842218885Sdim /// map->rootSize. 843218885Sdim /// @param Size New node size. 844218885Sdim void setSize(unsigned Level, unsigned Size) { 845218885Sdim path[Level].size = Size; 846218885Sdim if (Level) 847218885Sdim subtree(Level - 1).setSize(Size); 848218885Sdim } 849218885Sdim 850218885Sdim /// setRoot - Clear the path and set a new root node. 851218885Sdim /// @param Node New root node. 852218885Sdim /// @param Size New root size. 853218885Sdim /// @param Offset Offset into root node. 854218885Sdim void setRoot(void *Node, unsigned Size, unsigned Offset) { 855218885Sdim path.clear(); 856218885Sdim path.push_back(Entry(Node, Size, Offset)); 857218885Sdim } 858218885Sdim 859218885Sdim /// replaceRoot - Replace the current root node with two new entries after the 860218885Sdim /// tree height has increased. 861218885Sdim /// @param Root The new root node. 862218885Sdim /// @param Size Number of entries in the new root. 863218885Sdim /// @param Offsets Offsets into the root and first branch nodes. 864218885Sdim void replaceRoot(void *Root, unsigned Size, IdxPair Offsets); 865218885Sdim 866218885Sdim /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 867218885Sdim /// @param Level Get the sibling to node(Level). 868218885Sdim /// @return Left sibling, or NodeRef(). 869218885Sdim NodeRef getLeftSibling(unsigned Level) const; 870218885Sdim 871218885Sdim /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level 872218885Sdim /// unaltered. 873218885Sdim /// @param Level Move node(Level). 874218885Sdim void moveLeft(unsigned Level); 875218885Sdim 876218885Sdim /// fillLeft - Grow path to Height by taking leftmost branches. 877218885Sdim /// @param Height The target height. 878218885Sdim void fillLeft(unsigned Height) { 879218885Sdim while (height() < Height) 880218885Sdim push(subtree(height()), 0); 881218885Sdim } 882218885Sdim 883218885Sdim /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 884218885Sdim /// @param Level Get the sinbling to node(Level). 885218885Sdim /// @return Left sibling, or NodeRef(). 886218885Sdim NodeRef getRightSibling(unsigned Level) const; 887218885Sdim 888218885Sdim /// moveRight - Move path to the left sibling at Level. Leave nodes below 889218885Sdim /// Level unaltered. 890218885Sdim /// @param Level Move node(Level). 891218885Sdim void moveRight(unsigned Level); 892218885Sdim 893218885Sdim /// atBegin - Return true if path is at begin(). 894218885Sdim bool atBegin() const { 895218885Sdim for (unsigned i = 0, e = path.size(); i != e; ++i) 896218885Sdim if (path[i].offset != 0) 897218885Sdim return false; 898218885Sdim return true; 899218885Sdim } 900218885Sdim 901218885Sdim /// atLastEntry - Return true if the path is at the last entry of the node at 902218885Sdim /// Level. 903218885Sdim /// @param Level Node to examine. 904218885Sdim bool atLastEntry(unsigned Level) const { 905218885Sdim return path[Level].offset == path[Level].size - 1; 906218885Sdim } 907218885Sdim 908218885Sdim /// legalizeForInsert - Prepare the path for an insertion at Level. When the 909218885Sdim /// path is at end(), node(Level) may not be a legal node. legalizeForInsert 910218885Sdim /// ensures that node(Level) is real by moving back to the last node at Level, 911218885Sdim /// and setting offset(Level) to size(Level) if required. 912218885Sdim /// @param Level The level where an insertion is about to take place. 913218885Sdim void legalizeForInsert(unsigned Level) { 914218885Sdim if (valid()) 915218885Sdim return; 916218885Sdim moveLeft(Level); 917218885Sdim ++path[Level].offset; 918218885Sdim } 919218885Sdim}; 920218885Sdim 921218885Sdim} // namespace IntervalMapImpl 922218885Sdim 923218885Sdim 924218885Sdim//===----------------------------------------------------------------------===// 925218885Sdim//--- IntervalMap ----// 926218885Sdim//===----------------------------------------------------------------------===// 927218885Sdim 928218885Sdimtemplate <typename KeyT, typename ValT, 929218885Sdim unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize, 930218885Sdim typename Traits = IntervalMapInfo<KeyT> > 931218885Sdimclass IntervalMap { 932218885Sdim typedef IntervalMapImpl::NodeSizer<KeyT, ValT> Sizer; 933218885Sdim typedef IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits> Leaf; 934218885Sdim typedef IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits> 935218885Sdim Branch; 936218885Sdim typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf; 937218885Sdim typedef IntervalMapImpl::IdxPair IdxPair; 938218885Sdim 939218885Sdim // The RootLeaf capacity is given as a template parameter. We must compute the 940218885Sdim // corresponding RootBranch capacity. 941218885Sdim enum { 942218885Sdim DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) / 943218885Sdim (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)), 944218885Sdim RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1 945218885Sdim }; 946218885Sdim 947218885Sdim typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits> 948218885Sdim RootBranch; 949218885Sdim 950218885Sdim // When branched, we store a global start key as well as the branch node. 951218885Sdim struct RootBranchData { 952218885Sdim KeyT start; 953218885Sdim RootBranch node; 954218885Sdim }; 955218885Sdim 956218885Sdim enum { 957218885Sdim RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ? 958218885Sdim sizeof(RootBranchData) : sizeof(RootLeaf) 959218885Sdim }; 960218885Sdim 961218885Sdimpublic: 962218885Sdim typedef typename Sizer::Allocator Allocator; 963218885Sdim typedef KeyT KeyType; 964218885Sdim typedef ValT ValueType; 965218885Sdim typedef Traits KeyTraits; 966218885Sdim 967218885Sdimprivate: 968218885Sdim // The root data is either a RootLeaf or a RootBranchData instance. 969218885Sdim // We can't put them in a union since C++03 doesn't allow non-trivial 970218885Sdim // constructors in unions. 971218885Sdim // Instead, we use a char array with pointer alignment. The alignment is 972218885Sdim // ensured by the allocator member in the class, but still verified in the 973218885Sdim // constructor. We don't support keys or values that are more aligned than a 974218885Sdim // pointer. 975218885Sdim char data[RootDataSize]; 976218885Sdim 977218885Sdim // Tree height. 978218885Sdim // 0: Leaves in root. 979218885Sdim // 1: Root points to leaf. 980218885Sdim // 2: root->branch->leaf ... 981218885Sdim unsigned height; 982218885Sdim 983218885Sdim // Number of entries in the root node. 984218885Sdim unsigned rootSize; 985218885Sdim 986218885Sdim // Allocator used for creating external nodes. 987218885Sdim Allocator &allocator; 988218885Sdim 989218885Sdim /// dataAs - Represent data as a node type without breaking aliasing rules. 990218885Sdim template <typename T> 991218885Sdim T &dataAs() const { 992218885Sdim union { 993218885Sdim const char *d; 994218885Sdim T *t; 995218885Sdim } u; 996218885Sdim u.d = data; 997218885Sdim return *u.t; 998218885Sdim } 999218885Sdim 1000218885Sdim const RootLeaf &rootLeaf() const { 1001218885Sdim assert(!branched() && "Cannot acces leaf data in branched root"); 1002218885Sdim return dataAs<RootLeaf>(); 1003218885Sdim } 1004218885Sdim RootLeaf &rootLeaf() { 1005218885Sdim assert(!branched() && "Cannot acces leaf data in branched root"); 1006218885Sdim return dataAs<RootLeaf>(); 1007218885Sdim } 1008218885Sdim RootBranchData &rootBranchData() const { 1009218885Sdim assert(branched() && "Cannot access branch data in non-branched root"); 1010218885Sdim return dataAs<RootBranchData>(); 1011218885Sdim } 1012218885Sdim RootBranchData &rootBranchData() { 1013218885Sdim assert(branched() && "Cannot access branch data in non-branched root"); 1014218885Sdim return dataAs<RootBranchData>(); 1015218885Sdim } 1016218885Sdim const RootBranch &rootBranch() const { return rootBranchData().node; } 1017218885Sdim RootBranch &rootBranch() { return rootBranchData().node; } 1018218885Sdim KeyT rootBranchStart() const { return rootBranchData().start; } 1019218885Sdim KeyT &rootBranchStart() { return rootBranchData().start; } 1020218885Sdim 1021218885Sdim template <typename NodeT> NodeT *newNode() { 1022218885Sdim return new(allocator.template Allocate<NodeT>()) NodeT(); 1023218885Sdim } 1024218885Sdim 1025218885Sdim template <typename NodeT> void deleteNode(NodeT *P) { 1026218885Sdim P->~NodeT(); 1027218885Sdim allocator.Deallocate(P); 1028218885Sdim } 1029218885Sdim 1030218885Sdim IdxPair branchRoot(unsigned Position); 1031218885Sdim IdxPair splitRoot(unsigned Position); 1032218885Sdim 1033218885Sdim void switchRootToBranch() { 1034218885Sdim rootLeaf().~RootLeaf(); 1035218885Sdim height = 1; 1036218885Sdim new (&rootBranchData()) RootBranchData(); 1037218885Sdim } 1038218885Sdim 1039218885Sdim void switchRootToLeaf() { 1040218885Sdim rootBranchData().~RootBranchData(); 1041218885Sdim height = 0; 1042218885Sdim new(&rootLeaf()) RootLeaf(); 1043218885Sdim } 1044218885Sdim 1045218885Sdim bool branched() const { return height > 0; } 1046218885Sdim 1047218885Sdim ValT treeSafeLookup(KeyT x, ValT NotFound) const; 1048218885Sdim void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, 1049218885Sdim unsigned Level)); 1050218885Sdim void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level); 1051218885Sdim 1052218885Sdimpublic: 1053218885Sdim explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) { 1054218885Sdim assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 && 1055218885Sdim "Insufficient alignment"); 1056218885Sdim new(&rootLeaf()) RootLeaf(); 1057218885Sdim } 1058218885Sdim 1059218885Sdim ~IntervalMap() { 1060218885Sdim clear(); 1061218885Sdim rootLeaf().~RootLeaf(); 1062218885Sdim } 1063218885Sdim 1064218885Sdim /// empty - Return true when no intervals are mapped. 1065218885Sdim bool empty() const { 1066218885Sdim return rootSize == 0; 1067218885Sdim } 1068218885Sdim 1069218885Sdim /// start - Return the smallest mapped key in a non-empty map. 1070218885Sdim KeyT start() const { 1071218885Sdim assert(!empty() && "Empty IntervalMap has no start"); 1072218885Sdim return !branched() ? rootLeaf().start(0) : rootBranchStart(); 1073218885Sdim } 1074218885Sdim 1075218885Sdim /// stop - Return the largest mapped key in a non-empty map. 1076218885Sdim KeyT stop() const { 1077218885Sdim assert(!empty() && "Empty IntervalMap has no stop"); 1078218885Sdim return !branched() ? rootLeaf().stop(rootSize - 1) : 1079218885Sdim rootBranch().stop(rootSize - 1); 1080218885Sdim } 1081218885Sdim 1082218885Sdim /// lookup - Return the mapped value at x or NotFound. 1083218885Sdim ValT lookup(KeyT x, ValT NotFound = ValT()) const { 1084218885Sdim if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x)) 1085218885Sdim return NotFound; 1086218885Sdim return branched() ? treeSafeLookup(x, NotFound) : 1087218885Sdim rootLeaf().safeLookup(x, NotFound); 1088218885Sdim } 1089218885Sdim 1090218885Sdim /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals. 1091218885Sdim /// It is assumed that no key in the interval is mapped to another value, but 1092218885Sdim /// overlapping intervals already mapped to y will be coalesced. 1093218885Sdim void insert(KeyT a, KeyT b, ValT y) { 1094218885Sdim if (branched() || rootSize == RootLeaf::Capacity) 1095218885Sdim return find(a).insert(a, b, y); 1096218885Sdim 1097218885Sdim // Easy insert into root leaf. 1098218885Sdim unsigned p = rootLeaf().findFrom(0, rootSize, a); 1099218885Sdim rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y); 1100218885Sdim } 1101218885Sdim 1102218885Sdim /// clear - Remove all entries. 1103218885Sdim void clear(); 1104218885Sdim 1105218885Sdim class const_iterator; 1106218885Sdim class iterator; 1107218885Sdim friend class const_iterator; 1108218885Sdim friend class iterator; 1109218885Sdim 1110218885Sdim const_iterator begin() const { 1111218885Sdim const_iterator I(*this); 1112218885Sdim I.goToBegin(); 1113218885Sdim return I; 1114218885Sdim } 1115218885Sdim 1116218885Sdim iterator begin() { 1117218885Sdim iterator I(*this); 1118218885Sdim I.goToBegin(); 1119218885Sdim return I; 1120218885Sdim } 1121218885Sdim 1122218885Sdim const_iterator end() const { 1123218885Sdim const_iterator I(*this); 1124218885Sdim I.goToEnd(); 1125218885Sdim return I; 1126218885Sdim } 1127218885Sdim 1128218885Sdim iterator end() { 1129218885Sdim iterator I(*this); 1130218885Sdim I.goToEnd(); 1131218885Sdim return I; 1132218885Sdim } 1133218885Sdim 1134218885Sdim /// find - Return an iterator pointing to the first interval ending at or 1135218885Sdim /// after x, or end(). 1136218885Sdim const_iterator find(KeyT x) const { 1137218885Sdim const_iterator I(*this); 1138218885Sdim I.find(x); 1139218885Sdim return I; 1140218885Sdim } 1141218885Sdim 1142218885Sdim iterator find(KeyT x) { 1143218885Sdim iterator I(*this); 1144218885Sdim I.find(x); 1145218885Sdim return I; 1146218885Sdim } 1147218885Sdim}; 1148218885Sdim 1149218885Sdim/// treeSafeLookup - Return the mapped value at x or NotFound, assuming a 1150218885Sdim/// branched root. 1151218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1152218885SdimValT IntervalMap<KeyT, ValT, N, Traits>:: 1153218885SdimtreeSafeLookup(KeyT x, ValT NotFound) const { 1154218885Sdim assert(branched() && "treeLookup assumes a branched root"); 1155218885Sdim 1156218885Sdim IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x); 1157218885Sdim for (unsigned h = height-1; h; --h) 1158218885Sdim NR = NR.get<Branch>().safeLookup(x); 1159218885Sdim return NR.get<Leaf>().safeLookup(x, NotFound); 1160218885Sdim} 1161218885Sdim 1162218885Sdim 1163218885Sdim// branchRoot - Switch from a leaf root to a branched root. 1164218885Sdim// Return the new (root offset, node offset) corresponding to Position. 1165218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1166218885SdimIntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 1167218885SdimbranchRoot(unsigned Position) { 1168218885Sdim using namespace IntervalMapImpl; 1169218885Sdim // How many external leaf nodes to hold RootLeaf+1? 1170218885Sdim const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1; 1171218885Sdim 1172218885Sdim // Compute element distribution among new nodes. 1173218885Sdim unsigned size[Nodes]; 1174218885Sdim IdxPair NewOffset(0, Position); 1175218885Sdim 1176218885Sdim // Is is very common for the root node to be smaller than external nodes. 1177218885Sdim if (Nodes == 1) 1178218885Sdim size[0] = rootSize; 1179218885Sdim else 1180218885Sdim NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, size, 1181218885Sdim Position, true); 1182218885Sdim 1183218885Sdim // Allocate new nodes. 1184218885Sdim unsigned pos = 0; 1185218885Sdim NodeRef node[Nodes]; 1186218885Sdim for (unsigned n = 0; n != Nodes; ++n) { 1187218885Sdim Leaf *L = newNode<Leaf>(); 1188218885Sdim L->copy(rootLeaf(), pos, 0, size[n]); 1189218885Sdim node[n] = NodeRef(L, size[n]); 1190218885Sdim pos += size[n]; 1191218885Sdim } 1192218885Sdim 1193218885Sdim // Destroy the old leaf node, construct branch node instead. 1194218885Sdim switchRootToBranch(); 1195218885Sdim for (unsigned n = 0; n != Nodes; ++n) { 1196218885Sdim rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1); 1197218885Sdim rootBranch().subtree(n) = node[n]; 1198218885Sdim } 1199218885Sdim rootBranchStart() = node[0].template get<Leaf>().start(0); 1200218885Sdim rootSize = Nodes; 1201218885Sdim return NewOffset; 1202218885Sdim} 1203218885Sdim 1204218885Sdim// splitRoot - Split the current BranchRoot into multiple Branch nodes. 1205218885Sdim// Return the new (root offset, node offset) corresponding to Position. 1206218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1207218885SdimIntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 1208218885SdimsplitRoot(unsigned Position) { 1209218885Sdim using namespace IntervalMapImpl; 1210218885Sdim // How many external leaf nodes to hold RootBranch+1? 1211218885Sdim const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1; 1212218885Sdim 1213218885Sdim // Compute element distribution among new nodes. 1214218885Sdim unsigned Size[Nodes]; 1215218885Sdim IdxPair NewOffset(0, Position); 1216218885Sdim 1217218885Sdim // Is is very common for the root node to be smaller than external nodes. 1218218885Sdim if (Nodes == 1) 1219218885Sdim Size[0] = rootSize; 1220218885Sdim else 1221218885Sdim NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, Size, 1222218885Sdim Position, true); 1223218885Sdim 1224218885Sdim // Allocate new nodes. 1225218885Sdim unsigned Pos = 0; 1226218885Sdim NodeRef Node[Nodes]; 1227218885Sdim for (unsigned n = 0; n != Nodes; ++n) { 1228218885Sdim Branch *B = newNode<Branch>(); 1229218885Sdim B->copy(rootBranch(), Pos, 0, Size[n]); 1230218885Sdim Node[n] = NodeRef(B, Size[n]); 1231218885Sdim Pos += Size[n]; 1232218885Sdim } 1233218885Sdim 1234218885Sdim for (unsigned n = 0; n != Nodes; ++n) { 1235218885Sdim rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1); 1236218885Sdim rootBranch().subtree(n) = Node[n]; 1237218885Sdim } 1238218885Sdim rootSize = Nodes; 1239218885Sdim ++height; 1240218885Sdim return NewOffset; 1241218885Sdim} 1242218885Sdim 1243218885Sdim/// visitNodes - Visit each external node. 1244218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1245218885Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1246218885SdimvisitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) { 1247218885Sdim if (!branched()) 1248218885Sdim return; 1249218885Sdim SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs; 1250218885Sdim 1251218885Sdim // Collect level 0 nodes from the root. 1252218885Sdim for (unsigned i = 0; i != rootSize; ++i) 1253218885Sdim Refs.push_back(rootBranch().subtree(i)); 1254218885Sdim 1255218885Sdim // Visit all branch nodes. 1256218885Sdim for (unsigned h = height - 1; h; --h) { 1257218885Sdim for (unsigned i = 0, e = Refs.size(); i != e; ++i) { 1258218885Sdim for (unsigned j = 0, s = Refs[i].size(); j != s; ++j) 1259218885Sdim NextRefs.push_back(Refs[i].subtree(j)); 1260218885Sdim (this->*f)(Refs[i], h); 1261218885Sdim } 1262218885Sdim Refs.clear(); 1263218885Sdim Refs.swap(NextRefs); 1264218885Sdim } 1265218885Sdim 1266218885Sdim // Visit all leaf nodes. 1267218885Sdim for (unsigned i = 0, e = Refs.size(); i != e; ++i) 1268218885Sdim (this->*f)(Refs[i], 0); 1269218885Sdim} 1270218885Sdim 1271218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1272218885Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1273218885SdimdeleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) { 1274218885Sdim if (Level) 1275218885Sdim deleteNode(&Node.get<Branch>()); 1276218885Sdim else 1277218885Sdim deleteNode(&Node.get<Leaf>()); 1278218885Sdim} 1279218885Sdim 1280218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1281218885Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1282218885Sdimclear() { 1283218885Sdim if (branched()) { 1284218885Sdim visitNodes(&IntervalMap::deleteNode); 1285218885Sdim switchRootToLeaf(); 1286218885Sdim } 1287218885Sdim rootSize = 0; 1288218885Sdim} 1289218885Sdim 1290218885Sdim//===----------------------------------------------------------------------===// 1291218885Sdim//--- IntervalMap::const_iterator ----// 1292218885Sdim//===----------------------------------------------------------------------===// 1293218885Sdim 1294218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1295218885Sdimclass IntervalMap<KeyT, ValT, N, Traits>::const_iterator : 1296218885Sdim public std::iterator<std::bidirectional_iterator_tag, ValT> { 1297218885Sdimprotected: 1298218885Sdim friend class IntervalMap; 1299218885Sdim 1300218885Sdim // The map referred to. 1301218885Sdim IntervalMap *map; 1302218885Sdim 1303218885Sdim // We store a full path from the root to the current position. 1304218885Sdim // The path may be partially filled, but never between iterator calls. 1305218885Sdim IntervalMapImpl::Path path; 1306218885Sdim 1307218885Sdim explicit const_iterator(const IntervalMap &map) : 1308218885Sdim map(const_cast<IntervalMap*>(&map)) {} 1309218885Sdim 1310218885Sdim bool branched() const { 1311218885Sdim assert(map && "Invalid iterator"); 1312218885Sdim return map->branched(); 1313218885Sdim } 1314218885Sdim 1315218885Sdim void setRoot(unsigned Offset) { 1316218885Sdim if (branched()) 1317218885Sdim path.setRoot(&map->rootBranch(), map->rootSize, Offset); 1318218885Sdim else 1319218885Sdim path.setRoot(&map->rootLeaf(), map->rootSize, Offset); 1320218885Sdim } 1321218885Sdim 1322218885Sdim void pathFillFind(KeyT x); 1323218885Sdim void treeFind(KeyT x); 1324218885Sdim void treeAdvanceTo(KeyT x); 1325218885Sdim 1326218885Sdim /// unsafeStart - Writable access to start() for iterator. 1327218885Sdim KeyT &unsafeStart() const { 1328218885Sdim assert(valid() && "Cannot access invalid iterator"); 1329218885Sdim return branched() ? path.leaf<Leaf>().start(path.leafOffset()) : 1330218885Sdim path.leaf<RootLeaf>().start(path.leafOffset()); 1331218885Sdim } 1332218885Sdim 1333218885Sdim /// unsafeStop - Writable access to stop() for iterator. 1334218885Sdim KeyT &unsafeStop() const { 1335218885Sdim assert(valid() && "Cannot access invalid iterator"); 1336218885Sdim return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) : 1337218885Sdim path.leaf<RootLeaf>().stop(path.leafOffset()); 1338218885Sdim } 1339218885Sdim 1340218885Sdim /// unsafeValue - Writable access to value() for iterator. 1341218885Sdim ValT &unsafeValue() const { 1342218885Sdim assert(valid() && "Cannot access invalid iterator"); 1343218885Sdim return branched() ? path.leaf<Leaf>().value(path.leafOffset()) : 1344218885Sdim path.leaf<RootLeaf>().value(path.leafOffset()); 1345218885Sdim } 1346218885Sdim 1347218885Sdimpublic: 1348218885Sdim /// const_iterator - Create an iterator that isn't pointing anywhere. 1349218885Sdim const_iterator() : map(0) {} 1350218885Sdim 1351221345Sdim /// setMap - Change the map iterated over. This call must be followed by a 1352221345Sdim /// call to goToBegin(), goToEnd(), or find() 1353221345Sdim void setMap(const IntervalMap &m) { map = const_cast<IntervalMap*>(&m); } 1354221345Sdim 1355218885Sdim /// valid - Return true if the current position is valid, false for end(). 1356218885Sdim bool valid() const { return path.valid(); } 1357218885Sdim 1358226633Sdim /// atBegin - Return true if the current position is the first map entry. 1359226633Sdim bool atBegin() const { return path.atBegin(); } 1360226633Sdim 1361218885Sdim /// start - Return the beginning of the current interval. 1362218885Sdim const KeyT &start() const { return unsafeStart(); } 1363218885Sdim 1364218885Sdim /// stop - Return the end of the current interval. 1365218885Sdim const KeyT &stop() const { return unsafeStop(); } 1366218885Sdim 1367218885Sdim /// value - Return the mapped value at the current interval. 1368218885Sdim const ValT &value() const { return unsafeValue(); } 1369218885Sdim 1370218885Sdim const ValT &operator*() const { return value(); } 1371218885Sdim 1372218885Sdim bool operator==(const const_iterator &RHS) const { 1373218885Sdim assert(map == RHS.map && "Cannot compare iterators from different maps"); 1374218885Sdim if (!valid()) 1375218885Sdim return !RHS.valid(); 1376218885Sdim if (path.leafOffset() != RHS.path.leafOffset()) 1377218885Sdim return false; 1378218885Sdim return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>(); 1379218885Sdim } 1380218885Sdim 1381218885Sdim bool operator!=(const const_iterator &RHS) const { 1382218885Sdim return !operator==(RHS); 1383218885Sdim } 1384218885Sdim 1385218885Sdim /// goToBegin - Move to the first interval in map. 1386218885Sdim void goToBegin() { 1387218885Sdim setRoot(0); 1388218885Sdim if (branched()) 1389218885Sdim path.fillLeft(map->height); 1390218885Sdim } 1391218885Sdim 1392218885Sdim /// goToEnd - Move beyond the last interval in map. 1393218885Sdim void goToEnd() { 1394218885Sdim setRoot(map->rootSize); 1395218885Sdim } 1396218885Sdim 1397218885Sdim /// preincrement - move to the next interval. 1398218885Sdim const_iterator &operator++() { 1399218885Sdim assert(valid() && "Cannot increment end()"); 1400218885Sdim if (++path.leafOffset() == path.leafSize() && branched()) 1401218885Sdim path.moveRight(map->height); 1402218885Sdim return *this; 1403218885Sdim } 1404218885Sdim 1405218885Sdim /// postincrement - Dont do that! 1406218885Sdim const_iterator operator++(int) { 1407218885Sdim const_iterator tmp = *this; 1408218885Sdim operator++(); 1409218885Sdim return tmp; 1410218885Sdim } 1411218885Sdim 1412218885Sdim /// predecrement - move to the previous interval. 1413218885Sdim const_iterator &operator--() { 1414218885Sdim if (path.leafOffset() && (valid() || !branched())) 1415218885Sdim --path.leafOffset(); 1416218885Sdim else 1417218885Sdim path.moveLeft(map->height); 1418218885Sdim return *this; 1419218885Sdim } 1420218885Sdim 1421218885Sdim /// postdecrement - Dont do that! 1422218885Sdim const_iterator operator--(int) { 1423218885Sdim const_iterator tmp = *this; 1424218885Sdim operator--(); 1425218885Sdim return tmp; 1426218885Sdim } 1427218885Sdim 1428218885Sdim /// find - Move to the first interval with stop >= x, or end(). 1429218885Sdim /// This is a full search from the root, the current position is ignored. 1430218885Sdim void find(KeyT x) { 1431218885Sdim if (branched()) 1432218885Sdim treeFind(x); 1433218885Sdim else 1434218885Sdim setRoot(map->rootLeaf().findFrom(0, map->rootSize, x)); 1435218885Sdim } 1436218885Sdim 1437218885Sdim /// advanceTo - Move to the first interval with stop >= x, or end(). 1438218885Sdim /// The search is started from the current position, and no earlier positions 1439218885Sdim /// can be found. This is much faster than find() for small moves. 1440218885Sdim void advanceTo(KeyT x) { 1441218885Sdim if (!valid()) 1442218885Sdim return; 1443218885Sdim if (branched()) 1444218885Sdim treeAdvanceTo(x); 1445218885Sdim else 1446218885Sdim path.leafOffset() = 1447218885Sdim map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x); 1448218885Sdim } 1449218885Sdim 1450218885Sdim}; 1451218885Sdim 1452218885Sdim/// pathFillFind - Complete path by searching for x. 1453218885Sdim/// @param x Key to search for. 1454218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1455218885Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1456218885Sdimconst_iterator::pathFillFind(KeyT x) { 1457218885Sdim IntervalMapImpl::NodeRef NR = path.subtree(path.height()); 1458218885Sdim for (unsigned i = map->height - path.height() - 1; i; --i) { 1459218885Sdim unsigned p = NR.get<Branch>().safeFind(0, x); 1460218885Sdim path.push(NR, p); 1461218885Sdim NR = NR.subtree(p); 1462218885Sdim } 1463218885Sdim path.push(NR, NR.get<Leaf>().safeFind(0, x)); 1464218885Sdim} 1465218885Sdim 1466218885Sdim/// treeFind - Find in a branched tree. 1467218885Sdim/// @param x Key to search for. 1468218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1469218885Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1470218885Sdimconst_iterator::treeFind(KeyT x) { 1471218885Sdim setRoot(map->rootBranch().findFrom(0, map->rootSize, x)); 1472218885Sdim if (valid()) 1473218885Sdim pathFillFind(x); 1474218885Sdim} 1475218885Sdim 1476218885Sdim/// treeAdvanceTo - Find position after the current one. 1477218885Sdim/// @param x Key to search for. 1478218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1479218885Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1480218885Sdimconst_iterator::treeAdvanceTo(KeyT x) { 1481218885Sdim // Can we stay on the same leaf node? 1482218885Sdim if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) { 1483218885Sdim path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x); 1484218885Sdim return; 1485218885Sdim } 1486218885Sdim 1487218885Sdim // Drop the current leaf. 1488218885Sdim path.pop(); 1489218885Sdim 1490218885Sdim // Search towards the root for a usable subtree. 1491218885Sdim if (path.height()) { 1492218885Sdim for (unsigned l = path.height() - 1; l; --l) { 1493218885Sdim if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) { 1494218885Sdim // The branch node at l+1 is usable 1495218885Sdim path.offset(l + 1) = 1496218885Sdim path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x); 1497218885Sdim return pathFillFind(x); 1498218885Sdim } 1499218885Sdim path.pop(); 1500218885Sdim } 1501218885Sdim // Is the level-1 Branch usable? 1502218885Sdim if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) { 1503218885Sdim path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x); 1504218885Sdim return pathFillFind(x); 1505218885Sdim } 1506218885Sdim } 1507218885Sdim 1508218885Sdim // We reached the root. 1509218885Sdim setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x)); 1510218885Sdim if (valid()) 1511218885Sdim pathFillFind(x); 1512218885Sdim} 1513218885Sdim 1514218885Sdim//===----------------------------------------------------------------------===// 1515218885Sdim//--- IntervalMap::iterator ----// 1516218885Sdim//===----------------------------------------------------------------------===// 1517218885Sdim 1518218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1519218885Sdimclass IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator { 1520218885Sdim friend class IntervalMap; 1521218885Sdim typedef IntervalMapImpl::IdxPair IdxPair; 1522218885Sdim 1523218885Sdim explicit iterator(IntervalMap &map) : const_iterator(map) {} 1524218885Sdim 1525218885Sdim void setNodeStop(unsigned Level, KeyT Stop); 1526218885Sdim bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop); 1527218885Sdim template <typename NodeT> bool overflow(unsigned Level); 1528218885Sdim void treeInsert(KeyT a, KeyT b, ValT y); 1529218885Sdim void eraseNode(unsigned Level); 1530218885Sdim void treeErase(bool UpdateRoot = true); 1531218885Sdim bool canCoalesceLeft(KeyT Start, ValT x); 1532218885Sdim bool canCoalesceRight(KeyT Stop, ValT x); 1533218885Sdim 1534218885Sdimpublic: 1535218885Sdim /// iterator - Create null iterator. 1536218885Sdim iterator() {} 1537218885Sdim 1538218885Sdim /// setStart - Move the start of the current interval. 1539218885Sdim /// This may cause coalescing with the previous interval. 1540218885Sdim /// @param a New start key, must not overlap the previous interval. 1541218885Sdim void setStart(KeyT a); 1542218885Sdim 1543218885Sdim /// setStop - Move the end of the current interval. 1544218885Sdim /// This may cause coalescing with the following interval. 1545218885Sdim /// @param b New stop key, must not overlap the following interval. 1546218885Sdim void setStop(KeyT b); 1547218885Sdim 1548218885Sdim /// setValue - Change the mapped value of the current interval. 1549218885Sdim /// This may cause coalescing with the previous and following intervals. 1550218885Sdim /// @param x New value. 1551218885Sdim void setValue(ValT x); 1552218885Sdim 1553218885Sdim /// setStartUnchecked - Move the start of the current interval without 1554218885Sdim /// checking for coalescing or overlaps. 1555218885Sdim /// This should only be used when it is known that coalescing is not required. 1556218885Sdim /// @param a New start key. 1557218885Sdim void setStartUnchecked(KeyT a) { this->unsafeStart() = a; } 1558218885Sdim 1559218885Sdim /// setStopUnchecked - Move the end of the current interval without checking 1560218885Sdim /// for coalescing or overlaps. 1561218885Sdim /// This should only be used when it is known that coalescing is not required. 1562218885Sdim /// @param b New stop key. 1563218885Sdim void setStopUnchecked(KeyT b) { 1564218885Sdim this->unsafeStop() = b; 1565218885Sdim // Update keys in branch nodes as well. 1566218885Sdim if (this->path.atLastEntry(this->path.height())) 1567218885Sdim setNodeStop(this->path.height(), b); 1568218885Sdim } 1569218885Sdim 1570218885Sdim /// setValueUnchecked - Change the mapped value of the current interval 1571218885Sdim /// without checking for coalescing. 1572218885Sdim /// @param x New value. 1573218885Sdim void setValueUnchecked(ValT x) { this->unsafeValue() = x; } 1574218885Sdim 1575218885Sdim /// insert - Insert mapping [a;b] -> y before the current position. 1576218885Sdim void insert(KeyT a, KeyT b, ValT y); 1577218885Sdim 1578218885Sdim /// erase - Erase the current interval. 1579218885Sdim void erase(); 1580218885Sdim 1581218885Sdim iterator &operator++() { 1582218885Sdim const_iterator::operator++(); 1583218885Sdim return *this; 1584218885Sdim } 1585218885Sdim 1586218885Sdim iterator operator++(int) { 1587218885Sdim iterator tmp = *this; 1588218885Sdim operator++(); 1589218885Sdim return tmp; 1590218885Sdim } 1591218885Sdim 1592218885Sdim iterator &operator--() { 1593218885Sdim const_iterator::operator--(); 1594218885Sdim return *this; 1595218885Sdim } 1596218885Sdim 1597218885Sdim iterator operator--(int) { 1598218885Sdim iterator tmp = *this; 1599218885Sdim operator--(); 1600218885Sdim return tmp; 1601218885Sdim } 1602218885Sdim 1603218885Sdim}; 1604218885Sdim 1605218885Sdim/// canCoalesceLeft - Can the current interval coalesce to the left after 1606218885Sdim/// changing start or value? 1607218885Sdim/// @param Start New start of current interval. 1608218885Sdim/// @param Value New value for current interval. 1609218885Sdim/// @return True when updating the current interval would enable coalescing. 1610218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1611218885Sdimbool IntervalMap<KeyT, ValT, N, Traits>:: 1612218885Sdimiterator::canCoalesceLeft(KeyT Start, ValT Value) { 1613218885Sdim using namespace IntervalMapImpl; 1614218885Sdim Path &P = this->path; 1615218885Sdim if (!this->branched()) { 1616218885Sdim unsigned i = P.leafOffset(); 1617218885Sdim RootLeaf &Node = P.leaf<RootLeaf>(); 1618218885Sdim return i && Node.value(i-1) == Value && 1619218885Sdim Traits::adjacent(Node.stop(i-1), Start); 1620218885Sdim } 1621218885Sdim // Branched. 1622218885Sdim if (unsigned i = P.leafOffset()) { 1623218885Sdim Leaf &Node = P.leaf<Leaf>(); 1624218885Sdim return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start); 1625218885Sdim } else if (NodeRef NR = P.getLeftSibling(P.height())) { 1626218885Sdim unsigned i = NR.size() - 1; 1627218885Sdim Leaf &Node = NR.get<Leaf>(); 1628218885Sdim return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start); 1629218885Sdim } 1630218885Sdim return false; 1631218885Sdim} 1632218885Sdim 1633218885Sdim/// canCoalesceRight - Can the current interval coalesce to the right after 1634218885Sdim/// changing stop or value? 1635218885Sdim/// @param Stop New stop of current interval. 1636218885Sdim/// @param Value New value for current interval. 1637218885Sdim/// @return True when updating the current interval would enable coalescing. 1638218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1639218885Sdimbool IntervalMap<KeyT, ValT, N, Traits>:: 1640218885Sdimiterator::canCoalesceRight(KeyT Stop, ValT Value) { 1641218885Sdim using namespace IntervalMapImpl; 1642218885Sdim Path &P = this->path; 1643218885Sdim unsigned i = P.leafOffset() + 1; 1644218885Sdim if (!this->branched()) { 1645218885Sdim if (i >= P.leafSize()) 1646218885Sdim return false; 1647218885Sdim RootLeaf &Node = P.leaf<RootLeaf>(); 1648218885Sdim return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); 1649218885Sdim } 1650218885Sdim // Branched. 1651218885Sdim if (i < P.leafSize()) { 1652218885Sdim Leaf &Node = P.leaf<Leaf>(); 1653218885Sdim return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); 1654218885Sdim } else if (NodeRef NR = P.getRightSibling(P.height())) { 1655218885Sdim Leaf &Node = NR.get<Leaf>(); 1656218885Sdim return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0)); 1657218885Sdim } 1658218885Sdim return false; 1659218885Sdim} 1660218885Sdim 1661218885Sdim/// setNodeStop - Update the stop key of the current node at level and above. 1662218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1663218885Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1664218885Sdimiterator::setNodeStop(unsigned Level, KeyT Stop) { 1665218885Sdim // There are no references to the root node, so nothing to update. 1666218885Sdim if (!Level) 1667218885Sdim return; 1668218885Sdim IntervalMapImpl::Path &P = this->path; 1669218885Sdim // Update nodes pointing to the current node. 1670218885Sdim while (--Level) { 1671218885Sdim P.node<Branch>(Level).stop(P.offset(Level)) = Stop; 1672218885Sdim if (!P.atLastEntry(Level)) 1673218885Sdim return; 1674218885Sdim } 1675218885Sdim // Update root separately since it has a different layout. 1676218885Sdim P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop; 1677218885Sdim} 1678218885Sdim 1679218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1680218885Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1681218885Sdimiterator::setStart(KeyT a) { 1682218885Sdim assert(Traits::stopLess(a, this->stop()) && "Cannot move start beyond stop"); 1683218885Sdim KeyT &CurStart = this->unsafeStart(); 1684218885Sdim if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) { 1685218885Sdim CurStart = a; 1686218885Sdim return; 1687218885Sdim } 1688218885Sdim // Coalesce with the interval to the left. 1689218885Sdim --*this; 1690218885Sdim a = this->start(); 1691218885Sdim erase(); 1692218885Sdim setStartUnchecked(a); 1693218885Sdim} 1694218885Sdim 1695218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1696218885Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1697218885Sdimiterator::setStop(KeyT b) { 1698218885Sdim assert(Traits::stopLess(this->start(), b) && "Cannot move stop beyond start"); 1699218885Sdim if (Traits::startLess(b, this->stop()) || 1700218885Sdim !canCoalesceRight(b, this->value())) { 1701218885Sdim setStopUnchecked(b); 1702218885Sdim return; 1703218885Sdim } 1704218885Sdim // Coalesce with interval to the right. 1705218885Sdim KeyT a = this->start(); 1706218885Sdim erase(); 1707218885Sdim setStartUnchecked(a); 1708218885Sdim} 1709218885Sdim 1710218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1711218885Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1712218885Sdimiterator::setValue(ValT x) { 1713218885Sdim setValueUnchecked(x); 1714218885Sdim if (canCoalesceRight(this->stop(), x)) { 1715218885Sdim KeyT a = this->start(); 1716218885Sdim erase(); 1717218885Sdim setStartUnchecked(a); 1718218885Sdim } 1719218885Sdim if (canCoalesceLeft(this->start(), x)) { 1720218885Sdim --*this; 1721218885Sdim KeyT a = this->start(); 1722218885Sdim erase(); 1723218885Sdim setStartUnchecked(a); 1724218885Sdim } 1725218885Sdim} 1726218885Sdim 1727218885Sdim/// insertNode - insert a node before the current path at level. 1728218885Sdim/// Leave the current path pointing at the new node. 1729218885Sdim/// @param Level path index of the node to be inserted. 1730218885Sdim/// @param Node The node to be inserted. 1731218885Sdim/// @param Stop The last index in the new node. 1732218885Sdim/// @return True if the tree height was increased. 1733218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1734218885Sdimbool IntervalMap<KeyT, ValT, N, Traits>:: 1735218885Sdimiterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) { 1736218885Sdim assert(Level && "Cannot insert next to the root"); 1737218885Sdim bool SplitRoot = false; 1738218885Sdim IntervalMap &IM = *this->map; 1739218885Sdim IntervalMapImpl::Path &P = this->path; 1740218885Sdim 1741218885Sdim if (Level == 1) { 1742218885Sdim // Insert into the root branch node. 1743218885Sdim if (IM.rootSize < RootBranch::Capacity) { 1744218885Sdim IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop); 1745218885Sdim P.setSize(0, ++IM.rootSize); 1746218885Sdim P.reset(Level); 1747218885Sdim return SplitRoot; 1748218885Sdim } 1749218885Sdim 1750218885Sdim // We need to split the root while keeping our position. 1751218885Sdim SplitRoot = true; 1752218885Sdim IdxPair Offset = IM.splitRoot(P.offset(0)); 1753218885Sdim P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1754218885Sdim 1755218885Sdim // Fall through to insert at the new higher level. 1756218885Sdim ++Level; 1757218885Sdim } 1758218885Sdim 1759218885Sdim // When inserting before end(), make sure we have a valid path. 1760218885Sdim P.legalizeForInsert(--Level); 1761218885Sdim 1762218885Sdim // Insert into the branch node at Level-1. 1763218885Sdim if (P.size(Level) == Branch::Capacity) { 1764218885Sdim // Branch node is full, handle handle the overflow. 1765218885Sdim assert(!SplitRoot && "Cannot overflow after splitting the root"); 1766218885Sdim SplitRoot = overflow<Branch>(Level); 1767218885Sdim Level += SplitRoot; 1768218885Sdim } 1769218885Sdim P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop); 1770218885Sdim P.setSize(Level, P.size(Level) + 1); 1771218885Sdim if (P.atLastEntry(Level)) 1772218885Sdim setNodeStop(Level, Stop); 1773218885Sdim P.reset(Level + 1); 1774218885Sdim return SplitRoot; 1775218885Sdim} 1776218885Sdim 1777218885Sdim// insert 1778218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1779218885Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1780218885Sdimiterator::insert(KeyT a, KeyT b, ValT y) { 1781218885Sdim if (this->branched()) 1782218885Sdim return treeInsert(a, b, y); 1783218885Sdim IntervalMap &IM = *this->map; 1784218885Sdim IntervalMapImpl::Path &P = this->path; 1785218885Sdim 1786218885Sdim // Try simple root leaf insert. 1787218885Sdim unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y); 1788218885Sdim 1789218885Sdim // Was the root node insert successful? 1790218885Sdim if (Size <= RootLeaf::Capacity) { 1791218885Sdim P.setSize(0, IM.rootSize = Size); 1792218885Sdim return; 1793218885Sdim } 1794218885Sdim 1795218885Sdim // Root leaf node is full, we must branch. 1796218885Sdim IdxPair Offset = IM.branchRoot(P.leafOffset()); 1797218885Sdim P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1798218885Sdim 1799218885Sdim // Now it fits in the new leaf. 1800218885Sdim treeInsert(a, b, y); 1801218885Sdim} 1802218885Sdim 1803218885Sdim 1804218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1805218885Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1806218885Sdimiterator::treeInsert(KeyT a, KeyT b, ValT y) { 1807218885Sdim using namespace IntervalMapImpl; 1808218885Sdim Path &P = this->path; 1809218885Sdim 1810218885Sdim if (!P.valid()) 1811218885Sdim P.legalizeForInsert(this->map->height); 1812218885Sdim 1813218885Sdim // Check if this insertion will extend the node to the left. 1814218885Sdim if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) { 1815218885Sdim // Node is growing to the left, will it affect a left sibling node? 1816218885Sdim if (NodeRef Sib = P.getLeftSibling(P.height())) { 1817218885Sdim Leaf &SibLeaf = Sib.get<Leaf>(); 1818218885Sdim unsigned SibOfs = Sib.size() - 1; 1819218885Sdim if (SibLeaf.value(SibOfs) == y && 1820218885Sdim Traits::adjacent(SibLeaf.stop(SibOfs), a)) { 1821218885Sdim // This insertion will coalesce with the last entry in SibLeaf. We can 1822218885Sdim // handle it in two ways: 1823218885Sdim // 1. Extend SibLeaf.stop to b and be done, or 1824218885Sdim // 2. Extend a to SibLeaf, erase the SibLeaf entry and continue. 1825218885Sdim // We prefer 1., but need 2 when coalescing to the right as well. 1826218885Sdim Leaf &CurLeaf = P.leaf<Leaf>(); 1827218885Sdim P.moveLeft(P.height()); 1828218885Sdim if (Traits::stopLess(b, CurLeaf.start(0)) && 1829218885Sdim (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) { 1830218885Sdim // Easy, just extend SibLeaf and we're done. 1831218885Sdim setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b); 1832218885Sdim return; 1833218885Sdim } else { 1834218885Sdim // We have both left and right coalescing. Erase the old SibLeaf entry 1835218885Sdim // and continue inserting the larger interval. 1836218885Sdim a = SibLeaf.start(SibOfs); 1837218885Sdim treeErase(/* UpdateRoot= */false); 1838218885Sdim } 1839218885Sdim } 1840218885Sdim } else { 1841218885Sdim // No left sibling means we are at begin(). Update cached bound. 1842218885Sdim this->map->rootBranchStart() = a; 1843218885Sdim } 1844218885Sdim } 1845218885Sdim 1846218885Sdim // When we are inserting at the end of a leaf node, we must update stops. 1847218885Sdim unsigned Size = P.leafSize(); 1848218885Sdim bool Grow = P.leafOffset() == Size; 1849218885Sdim Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y); 1850218885Sdim 1851218885Sdim // Leaf insertion unsuccessful? Overflow and try again. 1852218885Sdim if (Size > Leaf::Capacity) { 1853218885Sdim overflow<Leaf>(P.height()); 1854218885Sdim Grow = P.leafOffset() == P.leafSize(); 1855218885Sdim Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y); 1856218885Sdim assert(Size <= Leaf::Capacity && "overflow() didn't make room"); 1857218885Sdim } 1858218885Sdim 1859218885Sdim // Inserted, update offset and leaf size. 1860218885Sdim P.setSize(P.height(), Size); 1861218885Sdim 1862218885Sdim // Insert was the last node entry, update stops. 1863218885Sdim if (Grow) 1864218885Sdim setNodeStop(P.height(), b); 1865218885Sdim} 1866218885Sdim 1867218885Sdim/// erase - erase the current interval and move to the next position. 1868218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1869218885Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1870218885Sdimiterator::erase() { 1871218885Sdim IntervalMap &IM = *this->map; 1872218885Sdim IntervalMapImpl::Path &P = this->path; 1873218885Sdim assert(P.valid() && "Cannot erase end()"); 1874218885Sdim if (this->branched()) 1875218885Sdim return treeErase(); 1876218885Sdim IM.rootLeaf().erase(P.leafOffset(), IM.rootSize); 1877218885Sdim P.setSize(0, --IM.rootSize); 1878218885Sdim} 1879218885Sdim 1880218885Sdim/// treeErase - erase() for a branched tree. 1881218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1882218885Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1883218885Sdimiterator::treeErase(bool UpdateRoot) { 1884218885Sdim IntervalMap &IM = *this->map; 1885218885Sdim IntervalMapImpl::Path &P = this->path; 1886218885Sdim Leaf &Node = P.leaf<Leaf>(); 1887218885Sdim 1888218885Sdim // Nodes are not allowed to become empty. 1889218885Sdim if (P.leafSize() == 1) { 1890218885Sdim IM.deleteNode(&Node); 1891218885Sdim eraseNode(IM.height); 1892218885Sdim // Update rootBranchStart if we erased begin(). 1893218885Sdim if (UpdateRoot && IM.branched() && P.valid() && P.atBegin()) 1894218885Sdim IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1895218885Sdim return; 1896218885Sdim } 1897218885Sdim 1898218885Sdim // Erase current entry. 1899218885Sdim Node.erase(P.leafOffset(), P.leafSize()); 1900218885Sdim unsigned NewSize = P.leafSize() - 1; 1901218885Sdim P.setSize(IM.height, NewSize); 1902218885Sdim // When we erase the last entry, update stop and move to a legal position. 1903218885Sdim if (P.leafOffset() == NewSize) { 1904218885Sdim setNodeStop(IM.height, Node.stop(NewSize - 1)); 1905218885Sdim P.moveRight(IM.height); 1906218885Sdim } else if (UpdateRoot && P.atBegin()) 1907218885Sdim IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1908218885Sdim} 1909218885Sdim 1910218885Sdim/// eraseNode - Erase the current node at Level from its parent and move path to 1911218885Sdim/// the first entry of the next sibling node. 1912218885Sdim/// The node must be deallocated by the caller. 1913218885Sdim/// @param Level 1..height, the root node cannot be erased. 1914218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1915218885Sdimvoid IntervalMap<KeyT, ValT, N, Traits>:: 1916218885Sdimiterator::eraseNode(unsigned Level) { 1917218885Sdim assert(Level && "Cannot erase root node"); 1918218885Sdim IntervalMap &IM = *this->map; 1919218885Sdim IntervalMapImpl::Path &P = this->path; 1920218885Sdim 1921218885Sdim if (--Level == 0) { 1922218885Sdim IM.rootBranch().erase(P.offset(0), IM.rootSize); 1923218885Sdim P.setSize(0, --IM.rootSize); 1924218885Sdim // If this cleared the root, switch to height=0. 1925218885Sdim if (IM.empty()) { 1926218885Sdim IM.switchRootToLeaf(); 1927218885Sdim this->setRoot(0); 1928218885Sdim return; 1929218885Sdim } 1930218885Sdim } else { 1931218885Sdim // Remove node ref from branch node at Level. 1932218885Sdim Branch &Parent = P.node<Branch>(Level); 1933218885Sdim if (P.size(Level) == 1) { 1934218885Sdim // Branch node became empty, remove it recursively. 1935218885Sdim IM.deleteNode(&Parent); 1936218885Sdim eraseNode(Level); 1937218885Sdim } else { 1938218885Sdim // Branch node won't become empty. 1939218885Sdim Parent.erase(P.offset(Level), P.size(Level)); 1940218885Sdim unsigned NewSize = P.size(Level) - 1; 1941218885Sdim P.setSize(Level, NewSize); 1942218885Sdim // If we removed the last branch, update stop and move to a legal pos. 1943218885Sdim if (P.offset(Level) == NewSize) { 1944218885Sdim setNodeStop(Level, Parent.stop(NewSize - 1)); 1945218885Sdim P.moveRight(Level); 1946218885Sdim } 1947218885Sdim } 1948218885Sdim } 1949218885Sdim // Update path cache for the new right sibling position. 1950218885Sdim if (P.valid()) { 1951218885Sdim P.reset(Level + 1); 1952218885Sdim P.offset(Level + 1) = 0; 1953218885Sdim } 1954218885Sdim} 1955218885Sdim 1956218885Sdim/// overflow - Distribute entries of the current node evenly among 1957218885Sdim/// its siblings and ensure that the current node is not full. 1958218885Sdim/// This may require allocating a new node. 1959218885Sdim/// @param NodeT The type of node at Level (Leaf or Branch). 1960218885Sdim/// @param Level path index of the overflowing node. 1961218885Sdim/// @return True when the tree height was changed. 1962218885Sdimtemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1963218885Sdimtemplate <typename NodeT> 1964218885Sdimbool IntervalMap<KeyT, ValT, N, Traits>:: 1965218885Sdimiterator::overflow(unsigned Level) { 1966218885Sdim using namespace IntervalMapImpl; 1967218885Sdim Path &P = this->path; 1968218885Sdim unsigned CurSize[4]; 1969218885Sdim NodeT *Node[4]; 1970218885Sdim unsigned Nodes = 0; 1971218885Sdim unsigned Elements = 0; 1972218885Sdim unsigned Offset = P.offset(Level); 1973218885Sdim 1974218885Sdim // Do we have a left sibling? 1975218885Sdim NodeRef LeftSib = P.getLeftSibling(Level); 1976218885Sdim if (LeftSib) { 1977218885Sdim Offset += Elements = CurSize[Nodes] = LeftSib.size(); 1978218885Sdim Node[Nodes++] = &LeftSib.get<NodeT>(); 1979218885Sdim } 1980218885Sdim 1981218885Sdim // Current node. 1982218885Sdim Elements += CurSize[Nodes] = P.size(Level); 1983218885Sdim Node[Nodes++] = &P.node<NodeT>(Level); 1984218885Sdim 1985218885Sdim // Do we have a right sibling? 1986218885Sdim NodeRef RightSib = P.getRightSibling(Level); 1987218885Sdim if (RightSib) { 1988218885Sdim Elements += CurSize[Nodes] = RightSib.size(); 1989218885Sdim Node[Nodes++] = &RightSib.get<NodeT>(); 1990218885Sdim } 1991218885Sdim 1992218885Sdim // Do we need to allocate a new node? 1993218885Sdim unsigned NewNode = 0; 1994218885Sdim if (Elements + 1 > Nodes * NodeT::Capacity) { 1995218885Sdim // Insert NewNode at the penultimate position, or after a single node. 1996218885Sdim NewNode = Nodes == 1 ? 1 : Nodes - 1; 1997218885Sdim CurSize[Nodes] = CurSize[NewNode]; 1998218885Sdim Node[Nodes] = Node[NewNode]; 1999218885Sdim CurSize[NewNode] = 0; 2000234353Sdim Node[NewNode] = this->map->template newNode<NodeT>(); 2001218885Sdim ++Nodes; 2002218885Sdim } 2003218885Sdim 2004218885Sdim // Compute the new element distribution. 2005218885Sdim unsigned NewSize[4]; 2006218885Sdim IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity, 2007218885Sdim CurSize, NewSize, Offset, true); 2008218885Sdim adjustSiblingSizes(Node, Nodes, CurSize, NewSize); 2009218885Sdim 2010218885Sdim // Move current location to the leftmost node. 2011218885Sdim if (LeftSib) 2012218885Sdim P.moveLeft(Level); 2013218885Sdim 2014218885Sdim // Elements have been rearranged, now update node sizes and stops. 2015218885Sdim bool SplitRoot = false; 2016218885Sdim unsigned Pos = 0; 2017218885Sdim for (;;) { 2018218885Sdim KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1); 2019218885Sdim if (NewNode && Pos == NewNode) { 2020218885Sdim SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop); 2021218885Sdim Level += SplitRoot; 2022218885Sdim } else { 2023218885Sdim P.setSize(Level, NewSize[Pos]); 2024218885Sdim setNodeStop(Level, Stop); 2025218885Sdim } 2026218885Sdim if (Pos + 1 == Nodes) 2027218885Sdim break; 2028218885Sdim P.moveRight(Level); 2029218885Sdim ++Pos; 2030218885Sdim } 2031218885Sdim 2032218885Sdim // Where was I? Find NewOffset. 2033218885Sdim while(Pos != NewOffset.first) { 2034218885Sdim P.moveLeft(Level); 2035218885Sdim --Pos; 2036218885Sdim } 2037218885Sdim P.offset(Level) = NewOffset.second; 2038218885Sdim return SplitRoot; 2039218885Sdim} 2040218885Sdim 2041218885Sdim//===----------------------------------------------------------------------===// 2042218885Sdim//--- IntervalMapOverlaps ----// 2043218885Sdim//===----------------------------------------------------------------------===// 2044218885Sdim 2045218885Sdim/// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two 2046218885Sdim/// IntervalMaps. The maps may be different, but the KeyT and Traits types 2047218885Sdim/// should be the same. 2048218885Sdim/// 2049218885Sdim/// Typical uses: 2050218885Sdim/// 2051218885Sdim/// 1. Test for overlap: 2052218885Sdim/// bool overlap = IntervalMapOverlaps(a, b).valid(); 2053218885Sdim/// 2054218885Sdim/// 2. Enumerate overlaps: 2055218885Sdim/// for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... } 2056218885Sdim/// 2057218885Sdimtemplate <typename MapA, typename MapB> 2058218885Sdimclass IntervalMapOverlaps { 2059218885Sdim typedef typename MapA::KeyType KeyType; 2060218885Sdim typedef typename MapA::KeyTraits Traits; 2061218885Sdim typename MapA::const_iterator posA; 2062218885Sdim typename MapB::const_iterator posB; 2063218885Sdim 2064218885Sdim /// advance - Move posA and posB forward until reaching an overlap, or until 2065218885Sdim /// either meets end. 2066218885Sdim /// Don't move the iterators if they are already overlapping. 2067218885Sdim void advance() { 2068218885Sdim if (!valid()) 2069218885Sdim return; 2070218885Sdim 2071218885Sdim if (Traits::stopLess(posA.stop(), posB.start())) { 2072218885Sdim // A ends before B begins. Catch up. 2073218885Sdim posA.advanceTo(posB.start()); 2074218885Sdim if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start())) 2075218885Sdim return; 2076218885Sdim } else if (Traits::stopLess(posB.stop(), posA.start())) { 2077218885Sdim // B ends before A begins. Catch up. 2078218885Sdim posB.advanceTo(posA.start()); 2079218885Sdim if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start())) 2080218885Sdim return; 2081218885Sdim } else 2082218885Sdim // Already overlapping. 2083218885Sdim return; 2084218885Sdim 2085218885Sdim for (;;) { 2086218885Sdim // Make a.end > b.start. 2087218885Sdim posA.advanceTo(posB.start()); 2088218885Sdim if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start())) 2089218885Sdim return; 2090218885Sdim // Make b.end > a.start. 2091218885Sdim posB.advanceTo(posA.start()); 2092218885Sdim if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start())) 2093218885Sdim return; 2094218885Sdim } 2095218885Sdim } 2096218885Sdim 2097218885Sdimpublic: 2098218885Sdim /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b. 2099218885Sdim IntervalMapOverlaps(const MapA &a, const MapB &b) 2100218885Sdim : posA(b.empty() ? a.end() : a.find(b.start())), 2101218885Sdim posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); } 2102218885Sdim 2103218885Sdim /// valid - Return true if iterator is at an overlap. 2104218885Sdim bool valid() const { 2105218885Sdim return posA.valid() && posB.valid(); 2106218885Sdim } 2107218885Sdim 2108218885Sdim /// a - access the left hand side in the overlap. 2109218885Sdim const typename MapA::const_iterator &a() const { return posA; } 2110218885Sdim 2111218885Sdim /// b - access the right hand side in the overlap. 2112218885Sdim const typename MapB::const_iterator &b() const { return posB; } 2113218885Sdim 2114218885Sdim /// start - Beginning of the overlapping interval. 2115218885Sdim KeyType start() const { 2116218885Sdim KeyType ak = a().start(); 2117218885Sdim KeyType bk = b().start(); 2118218885Sdim return Traits::startLess(ak, bk) ? bk : ak; 2119218885Sdim } 2120218885Sdim 2121218885Sdim /// stop - End of the overlapping interval. 2122218885Sdim KeyType stop() const { 2123218885Sdim KeyType ak = a().stop(); 2124218885Sdim KeyType bk = b().stop(); 2125218885Sdim return Traits::startLess(ak, bk) ? ak : bk; 2126218885Sdim } 2127218885Sdim 2128218885Sdim /// skipA - Move to the next overlap that doesn't involve a(). 2129218885Sdim void skipA() { 2130218885Sdim ++posA; 2131218885Sdim advance(); 2132218885Sdim } 2133218885Sdim 2134218885Sdim /// skipB - Move to the next overlap that doesn't involve b(). 2135218885Sdim void skipB() { 2136218885Sdim ++posB; 2137218885Sdim advance(); 2138218885Sdim } 2139218885Sdim 2140218885Sdim /// Preincrement - Move to the next overlap. 2141218885Sdim IntervalMapOverlaps &operator++() { 2142218885Sdim // Bump the iterator that ends first. The other one may have more overlaps. 2143218885Sdim if (Traits::startLess(posB.stop(), posA.stop())) 2144218885Sdim skipB(); 2145218885Sdim else 2146218885Sdim skipA(); 2147218885Sdim return *this; 2148218885Sdim } 2149218885Sdim 2150218885Sdim /// advanceTo - Move to the first overlapping interval with 2151218885Sdim /// stopLess(x, stop()). 2152218885Sdim void advanceTo(KeyType x) { 2153218885Sdim if (!valid()) 2154218885Sdim return; 2155218885Sdim // Make sure advanceTo sees monotonic keys. 2156218885Sdim if (Traits::stopLess(posA.stop(), x)) 2157218885Sdim posA.advanceTo(x); 2158218885Sdim if (Traits::stopLess(posB.stop(), x)) 2159218885Sdim posB.advanceTo(x); 2160218885Sdim advance(); 2161218885Sdim } 2162218885Sdim}; 2163218885Sdim 2164218885Sdim} // namespace llvm 2165218885Sdim 2166218885Sdim#endif 2167