IntervalMap.h revision 7a26aca73ff2c8c4cb3205a776cc6743949b1fb7
1//===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements a coalescing interval map for small objects. 11// 12// KeyT objects are mapped to ValT objects. Intervals of keys that map to the 13// same value are represented in a compressed form. 14// 15// Iterators provide ordered access to the compressed intervals rather than the 16// individual keys, and insert and erase operations use key intervals as well. 17// 18// Like SmallVector, IntervalMap will store the first N intervals in the map 19// object itself without any allocations. When space is exhausted it switches to 20// a B+-tree representation with very small overhead for small key and value 21// objects. 22// 23// A Traits class specifies how keys are compared. It also allows IntervalMap to 24// work with both closed and half-open intervals. 25// 26// Keys and values are not stored next to each other in a std::pair, so we don't 27// provide such a value_type. Dereferencing iterators only returns the mapped 28// value. The interval bounds are accessible through the start() and stop() 29// iterator methods. 30// 31// IntervalMap is optimized for small key and value objects, 4 or 8 bytes each 32// is the optimal size. For large objects use std::map instead. 33// 34//===----------------------------------------------------------------------===// 35// 36// Synopsis: 37// 38// template <typename KeyT, typename ValT, unsigned N, typename Traits> 39// class IntervalMap { 40// public: 41// typedef KeyT key_type; 42// typedef ValT mapped_type; 43// typedef RecyclingAllocator<...> Allocator; 44// class iterator; 45// class const_iterator; 46// 47// explicit IntervalMap(Allocator&); 48// ~IntervalMap(): 49// 50// bool empty() const; 51// KeyT start() const; 52// KeyT stop() const; 53// ValT lookup(KeyT x, Value NotFound = Value()) const; 54// 55// const_iterator begin() const; 56// const_iterator end() const; 57// iterator begin(); 58// iterator end(); 59// const_iterator find(KeyT x) const; 60// iterator find(KeyT x); 61// 62// void insert(KeyT a, KeyT b, ValT y); 63// void clear(); 64// }; 65// 66// template <typename KeyT, typename ValT, unsigned N, typename Traits> 67// class IntervalMap::const_iterator : 68// public std::iterator<std::bidirectional_iterator_tag, ValT> { 69// public: 70// bool operator==(const const_iterator &) const; 71// bool operator!=(const const_iterator &) const; 72// bool valid() const; 73// 74// const KeyT &start() const; 75// const KeyT &stop() const; 76// const ValT &value() const; 77// const ValT &operator*() const; 78// const ValT *operator->() const; 79// 80// const_iterator &operator++(); 81// const_iterator &operator++(int); 82// const_iterator &operator--(); 83// const_iterator &operator--(int); 84// void goToBegin(); 85// void goToEnd(); 86// void find(KeyT x); 87// void advanceTo(KeyT x); 88// }; 89// 90// template <typename KeyT, typename ValT, unsigned N, typename Traits> 91// class IntervalMap::iterator : public const_iterator { 92// public: 93// void insert(KeyT a, KeyT b, Value y); 94// void erase(); 95// }; 96// 97//===----------------------------------------------------------------------===// 98 99#ifndef LLVM_ADT_INTERVALMAP_H 100#define LLVM_ADT_INTERVALMAP_H 101 102#include "llvm/ADT/SmallVector.h" 103#include "llvm/ADT/PointerIntPair.h" 104#include "llvm/Support/Allocator.h" 105#include "llvm/Support/RecyclingAllocator.h" 106#include <iterator> 107 108// FIXME: Remove debugging code. 109#include "llvm/Support/raw_ostream.h" 110 111namespace llvm { 112 113 114//===----------------------------------------------------------------------===// 115//--- Key traits ---// 116//===----------------------------------------------------------------------===// 117// 118// The IntervalMap works with closed or half-open intervals. 119// Adjacent intervals that map to the same value are coalesced. 120// 121// The IntervalMapInfo traits class is used to determine if a key is contained 122// in an interval, and if two intervals are adjacent so they can be coalesced. 123// The provided implementation works for closed integer intervals, other keys 124// probably need a specialized version. 125// 126// The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x). 127// 128// It is assumed that (a;b] half-open intervals are not used, only [a;b) is 129// allowed. This is so that stopLess(a, b) can be used to determine if two 130// intervals overlap. 131// 132//===----------------------------------------------------------------------===// 133 134template <typename T> 135struct IntervalMapInfo { 136 137 /// startLess - Return true if x is not in [a;b]. 138 /// This is x < a both for closed intervals and for [a;b) half-open intervals. 139 static inline bool startLess(const T &x, const T &a) { 140 return x < a; 141 } 142 143 /// stopLess - Return true if x is not in [a;b]. 144 /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals. 145 static inline bool stopLess(const T &b, const T &x) { 146 return b < x; 147 } 148 149 /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce. 150 /// This is a+1 == b for closed intervals, a == b for half-open intervals. 151 static inline bool adjacent(const T &a, const T &b) { 152 return a+1 == b; 153 } 154 155}; 156 157/// IntervalMapImpl - Namespace used for IntervalMap implementation details. 158/// It should be considered private to the implementation. 159namespace IntervalMapImpl { 160 161// Forward declarations. 162template <typename, typename, unsigned, typename> class LeafNode; 163template <typename, typename, unsigned, typename> class BranchNode; 164 165typedef std::pair<unsigned,unsigned> IdxPair; 166 167 168//===----------------------------------------------------------------------===// 169//--- IntervalMapImpl::NodeBase ---// 170//===----------------------------------------------------------------------===// 171// 172// Both leaf and branch nodes store vectors of pairs. 173// Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT). 174// 175// Keys and values are stored in separate arrays to avoid padding caused by 176// different object alignments. This also helps improve locality of reference 177// when searching the keys. 178// 179// The nodes don't know how many elements they contain - that information is 180// stored elsewhere. Omitting the size field prevents padding and allows a node 181// to fill the allocated cache lines completely. 182// 183// These are typical key and value sizes, the node branching factor (N), and 184// wasted space when nodes are sized to fit in three cache lines (192 bytes): 185// 186// T1 T2 N Waste Used by 187// 4 4 24 0 Branch<4> (32-bit pointers) 188// 8 4 16 0 Leaf<4,4>, Branch<4> 189// 8 8 12 0 Leaf<4,8>, Branch<8> 190// 16 4 9 12 Leaf<8,4> 191// 16 8 8 0 Leaf<8,8> 192// 193//===----------------------------------------------------------------------===// 194 195template <typename T1, typename T2, unsigned N> 196class NodeBase { 197public: 198 enum { Capacity = N }; 199 200 T1 first[N]; 201 T2 second[N]; 202 203 /// copy - Copy elements from another node. 204 /// @param Other Node elements are copied from. 205 /// @param i Beginning of the source range in other. 206 /// @param j Beginning of the destination range in this. 207 /// @param Count Number of elements to copy. 208 template <unsigned M> 209 void copy(const NodeBase<T1, T2, M> &Other, unsigned i, 210 unsigned j, unsigned Count) { 211 assert(i + Count <= M && "Invalid source range"); 212 assert(j + Count <= N && "Invalid dest range"); 213 for (unsigned e = i + Count; i != e; ++i, ++j) { 214 first[j] = Other.first[i]; 215 second[j] = Other.second[i]; 216 } 217 } 218 219 /// moveLeft - Move elements to the left. 220 /// @param i Beginning of the source range. 221 /// @param j Beginning of the destination range. 222 /// @param Count Number of elements to copy. 223 void moveLeft(unsigned i, unsigned j, unsigned Count) { 224 assert(j <= i && "Use moveRight shift elements right"); 225 copy(*this, i, j, Count); 226 } 227 228 /// moveRight - Move elements to the right. 229 /// @param i Beginning of the source range. 230 /// @param j Beginning of the destination range. 231 /// @param Count Number of elements to copy. 232 void moveRight(unsigned i, unsigned j, unsigned Count) { 233 assert(i <= j && "Use moveLeft shift elements left"); 234 assert(j + Count <= N && "Invalid range"); 235 while (Count--) { 236 first[j + Count] = first[i + Count]; 237 second[j + Count] = second[i + Count]; 238 } 239 } 240 241 /// erase - Erase elements [i;j). 242 /// @param i Beginning of the range to erase. 243 /// @param j End of the range. (Exclusive). 244 /// @param Size Number of elements in node. 245 void erase(unsigned i, unsigned j, unsigned Size) { 246 moveLeft(j, i, Size - j); 247 } 248 249 /// erase - Erase element at i. 250 /// @param i Index of element to erase. 251 /// @param Size Number of elements in node. 252 void erase(unsigned i, unsigned Size) { 253 erase(i, i+1, Size); 254 } 255 256 /// shift - Shift elements [i;size) 1 position to the right. 257 /// @param i Beginning of the range to move. 258 /// @param Size Number of elements in node. 259 void shift(unsigned i, unsigned Size) { 260 moveRight(i, i + 1, Size - i); 261 } 262 263 /// transferToLeftSib - Transfer elements to a left sibling node. 264 /// @param Size Number of elements in this. 265 /// @param Sib Left sibling node. 266 /// @param SSize Number of elements in sib. 267 /// @param Count Number of elements to transfer. 268 void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, 269 unsigned Count) { 270 Sib.copy(*this, 0, SSize, Count); 271 erase(0, Count, Size); 272 } 273 274 /// transferToRightSib - Transfer elements to a right sibling node. 275 /// @param Size Number of elements in this. 276 /// @param Sib Right sibling node. 277 /// @param SSize Number of elements in sib. 278 /// @param Count Number of elements to transfer. 279 void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize, 280 unsigned Count) { 281 Sib.moveRight(0, Count, SSize); 282 Sib.copy(*this, Size-Count, 0, Count); 283 } 284 285 /// adjustFromLeftSib - Adjust the number if elements in this node by moving 286 /// elements to or from a left sibling node. 287 /// @param Size Number of elements in this. 288 /// @param Sib Right sibling node. 289 /// @param SSize Number of elements in sib. 290 /// @param Add The number of elements to add to this node, possibly < 0. 291 /// @return Number of elements added to this node, possibly negative. 292 int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) { 293 if (Add > 0) { 294 // We want to grow, copy from sib. 295 unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size); 296 Sib.transferToRightSib(SSize, *this, Size, Count); 297 return Count; 298 } else { 299 // We want to shrink, copy to sib. 300 unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize); 301 transferToLeftSib(Size, Sib, SSize, Count); 302 return -Count; 303 } 304 } 305}; 306 307/// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes. 308/// @param Node Array of pointers to sibling nodes. 309/// @param Nodes Number of nodes. 310/// @param CurSize Array of current node sizes, will be overwritten. 311/// @param NewSize Array of desired node sizes. 312template <typename NodeT> 313void adjustSiblingSizes(NodeT *Node[], unsigned Nodes, 314 unsigned CurSize[], const unsigned NewSize[]) { 315 // Move elements right. 316 for (int n = Nodes - 1; n; --n) { 317 if (CurSize[n] == NewSize[n]) 318 continue; 319 for (int m = n - 1; m != -1; --m) { 320 int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m], 321 NewSize[n] - CurSize[n]); 322 CurSize[m] -= d; 323 CurSize[n] += d; 324 // Keep going if the current node was exhausted. 325 if (CurSize[n] >= NewSize[n]) 326 break; 327 } 328 } 329 330 if (Nodes == 0) 331 return; 332 333 // Move elements left. 334 for (unsigned n = 0; n != Nodes - 1; ++n) { 335 if (CurSize[n] == NewSize[n]) 336 continue; 337 for (unsigned m = n + 1; m != Nodes; ++m) { 338 int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n], 339 CurSize[n] - NewSize[n]); 340 CurSize[m] += d; 341 CurSize[n] -= d; 342 // Keep going if the current node was exhausted. 343 if (CurSize[n] >= NewSize[n]) 344 break; 345 } 346 } 347 348#ifndef NDEBUG 349 for (unsigned n = 0; n != Nodes; n++) 350 assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle"); 351#endif 352} 353 354/// IntervalMapImpl::distribute - Compute a new distribution of node elements 355/// after an overflow or underflow. Reserve space for a new element at Position, 356/// and compute the node that will hold Position after redistributing node 357/// elements. 358/// 359/// It is required that 360/// 361/// Elements == sum(CurSize), and 362/// Elements + Grow <= Nodes * Capacity. 363/// 364/// NewSize[] will be filled in such that: 365/// 366/// sum(NewSize) == Elements, and 367/// NewSize[i] <= Capacity. 368/// 369/// The returned index is the node where Position will go, so: 370/// 371/// sum(NewSize[0..idx-1]) <= Position 372/// sum(NewSize[0..idx]) >= Position 373/// 374/// The last equality, sum(NewSize[0..idx]) == Position, can only happen when 375/// Grow is set and NewSize[idx] == Capacity-1. The index points to the node 376/// before the one holding the Position'th element where there is room for an 377/// insertion. 378/// 379/// @param Nodes The number of nodes. 380/// @param Elements Total elements in all nodes. 381/// @param Capacity The capacity of each node. 382/// @param CurSize Array[Nodes] of current node sizes, or NULL. 383/// @param NewSize Array[Nodes] to receive the new node sizes. 384/// @param Position Insert position. 385/// @param Grow Reserve space for a new element at Position. 386/// @return (node, offset) for Position. 387IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, 388 const unsigned *CurSize, unsigned NewSize[], 389 unsigned Position, bool Grow); 390 391 392//===----------------------------------------------------------------------===// 393//--- IntervalMapImpl::NodeSizer ---// 394//===----------------------------------------------------------------------===// 395// 396// Compute node sizes from key and value types. 397// 398// The branching factors are chosen to make nodes fit in three cache lines. 399// This may not be possible if keys or values are very large. Such large objects 400// are handled correctly, but a std::map would probably give better performance. 401// 402//===----------------------------------------------------------------------===// 403 404enum { 405 // Cache line size. Most architectures have 32 or 64 byte cache lines. 406 // We use 64 bytes here because it provides good branching factors. 407 Log2CacheLine = 6, 408 CacheLineBytes = 1 << Log2CacheLine, 409 DesiredNodeBytes = 3 * CacheLineBytes 410}; 411 412template <typename KeyT, typename ValT> 413struct NodeSizer { 414 enum { 415 // Compute the leaf node branching factor that makes a node fit in three 416 // cache lines. The branching factor must be at least 3, or some B+-tree 417 // balancing algorithms won't work. 418 // LeafSize can't be larger than CacheLineBytes. This is required by the 419 // PointerIntPair used by NodeRef. 420 DesiredLeafSize = DesiredNodeBytes / 421 static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)), 422 MinLeafSize = 3, 423 LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize 424 }; 425 426 typedef NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize> LeafBase; 427 428 enum { 429 // Now that we have the leaf branching factor, compute the actual allocation 430 // unit size by rounding up to a whole number of cache lines. 431 AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1), 432 433 // Determine the branching factor for branch nodes. 434 BranchSize = AllocBytes / 435 static_cast<unsigned>(sizeof(KeyT) + sizeof(void*)) 436 }; 437 438 /// Allocator - The recycling allocator used for both branch and leaf nodes. 439 /// This typedef is very likely to be identical for all IntervalMaps with 440 /// reasonably sized entries, so the same allocator can be shared among 441 /// different kinds of maps. 442 typedef RecyclingAllocator<BumpPtrAllocator, char, 443 AllocBytes, CacheLineBytes> Allocator; 444 445}; 446 447 448//===----------------------------------------------------------------------===// 449//--- IntervalMapImpl::NodeRef ---// 450//===----------------------------------------------------------------------===// 451// 452// B+-tree nodes can be leaves or branches, so we need a polymorphic node 453// pointer that can point to both kinds. 454// 455// All nodes are cache line aligned and the low 6 bits of a node pointer are 456// always 0. These bits are used to store the number of elements in the 457// referenced node. Besides saving space, placing node sizes in the parents 458// allow tree balancing algorithms to run without faulting cache lines for nodes 459// that may not need to be modified. 460// 461// A NodeRef doesn't know whether it references a leaf node or a branch node. 462// It is the responsibility of the caller to use the correct types. 463// 464// Nodes are never supposed to be empty, and it is invalid to store a node size 465// of 0 in a NodeRef. The valid range of sizes is 1-64. 466// 467//===----------------------------------------------------------------------===// 468 469class NodeRef { 470 struct CacheAlignedPointerTraits { 471 static inline void *getAsVoidPointer(void *P) { return P; } 472 static inline void *getFromVoidPointer(void *P) { return P; } 473 enum { NumLowBitsAvailable = Log2CacheLine }; 474 }; 475 PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip; 476 477public: 478 /// NodeRef - Create a null ref. 479 NodeRef() {} 480 481 /// operator bool - Detect a null ref. 482 operator bool() const { return pip.getOpaqueValue(); } 483 484 /// NodeRef - Create a reference to the node p with n elements. 485 template <typename NodeT> 486 NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) { 487 assert(n <= NodeT::Capacity && "Size too big for node"); 488 } 489 490 /// size - Return the number of elements in the referenced node. 491 unsigned size() const { return pip.getInt() + 1; } 492 493 /// setSize - Update the node size. 494 void setSize(unsigned n) { pip.setInt(n - 1); } 495 496 /// subtree - Access the i'th subtree reference in a branch node. 497 /// This depends on branch nodes storing the NodeRef array as their first 498 /// member. 499 NodeRef &subtree(unsigned i) const { 500 return reinterpret_cast<NodeRef*>(pip.getPointer())[i]; 501 } 502 503 /// get - Dereference as a NodeT reference. 504 template <typename NodeT> 505 NodeT &get() const { 506 return *reinterpret_cast<NodeT*>(pip.getPointer()); 507 } 508 509 bool operator==(const NodeRef &RHS) const { 510 if (pip == RHS.pip) 511 return true; 512 assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs"); 513 return false; 514 } 515 516 bool operator!=(const NodeRef &RHS) const { 517 return !operator==(RHS); 518 } 519}; 520 521//===----------------------------------------------------------------------===// 522//--- IntervalMapImpl::LeafNode ---// 523//===----------------------------------------------------------------------===// 524// 525// Leaf nodes store up to N disjoint intervals with corresponding values. 526// 527// The intervals are kept sorted and fully coalesced so there are no adjacent 528// intervals mapping to the same value. 529// 530// These constraints are always satisfied: 531// 532// - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals. 533// 534// - Traits::stopLess(stop(i), start(i + 1) - Sorted. 535// 536// - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1)) 537// - Fully coalesced. 538// 539//===----------------------------------------------------------------------===// 540 541template <typename KeyT, typename ValT, unsigned N, typename Traits> 542class LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> { 543public: 544 const KeyT &start(unsigned i) const { return this->first[i].first; } 545 const KeyT &stop(unsigned i) const { return this->first[i].second; } 546 const ValT &value(unsigned i) const { return this->second[i]; } 547 548 KeyT &start(unsigned i) { return this->first[i].first; } 549 KeyT &stop(unsigned i) { return this->first[i].second; } 550 ValT &value(unsigned i) { return this->second[i]; } 551 552 /// findFrom - Find the first interval after i that may contain x. 553 /// @param i Starting index for the search. 554 /// @param Size Number of elements in node. 555 /// @param x Key to search for. 556 /// @return First index with !stopLess(key[i].stop, x), or size. 557 /// This is the first interval that can possibly contain x. 558 unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { 559 assert(i <= Size && Size <= N && "Bad indices"); 560 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 561 "Index is past the needed point"); 562 while (i != Size && Traits::stopLess(stop(i), x)) ++i; 563 return i; 564 } 565 566 /// safeFind - Find an interval that is known to exist. This is the same as 567 /// findFrom except is it assumed that x is at least within range of the last 568 /// interval. 569 /// @param i Starting index for the search. 570 /// @param x Key to search for. 571 /// @return First index with !stopLess(key[i].stop, x), never size. 572 /// This is the first interval that can possibly contain x. 573 unsigned safeFind(unsigned i, KeyT x) const { 574 assert(i < N && "Bad index"); 575 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 576 "Index is past the needed point"); 577 while (Traits::stopLess(stop(i), x)) ++i; 578 assert(i < N && "Unsafe intervals"); 579 return i; 580 } 581 582 /// safeLookup - Lookup mapped value for a safe key. 583 /// It is assumed that x is within range of the last entry. 584 /// @param x Key to search for. 585 /// @param NotFound Value to return if x is not in any interval. 586 /// @return The mapped value at x or NotFound. 587 ValT safeLookup(KeyT x, ValT NotFound) const { 588 unsigned i = safeFind(0, x); 589 return Traits::startLess(x, start(i)) ? NotFound : value(i); 590 } 591 592 unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y); 593 594#ifndef NDEBUG 595 void dump(raw_ostream &OS, unsigned Size) { 596 OS << " N" << this << " [shape=record label=\"{ " << Size << '/' << N; 597 for (unsigned i = 0; i != Size; ++i) 598 OS << " | {" << start(i) << '-' << stop(i) << "|" << value(i) << '}'; 599 OS << "}\"];\n"; 600 } 601#endif 602 603}; 604 605/// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as 606/// possible. This may cause the node to grow by 1, or it may cause the node 607/// to shrink because of coalescing. 608/// @param i Starting index = insertFrom(0, size, a) 609/// @param Size Number of elements in node. 610/// @param a Interval start. 611/// @param b Interval stop. 612/// @param y Value be mapped. 613/// @return (insert position, new size), or (i, Capacity+1) on overflow. 614template <typename KeyT, typename ValT, unsigned N, typename Traits> 615unsigned LeafNode<KeyT, ValT, N, Traits>:: 616insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) { 617 unsigned i = Pos; 618 assert(i <= Size && Size <= N && "Invalid index"); 619 assert(!Traits::stopLess(b, a) && "Invalid interval"); 620 621 // Verify the findFrom invariant. 622 assert((i == 0 || Traits::stopLess(stop(i - 1), a))); 623 assert((i == Size || !Traits::stopLess(stop(i), a))); 624 assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert"); 625 626 // Coalesce with previous interval. 627 if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) { 628 Pos = i - 1; 629 // Also coalesce with next interval? 630 if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) { 631 stop(i - 1) = stop(i); 632 this->erase(i, Size); 633 return Size - 1; 634 } 635 stop(i - 1) = b; 636 return Size; 637 } 638 639 // Detect overflow. 640 if (i == N) 641 return N + 1; 642 643 // Add new interval at end. 644 if (i == Size) { 645 start(i) = a; 646 stop(i) = b; 647 value(i) = y; 648 return Size + 1; 649 } 650 651 // Try to coalesce with following interval. 652 if (value(i) == y && Traits::adjacent(b, start(i))) { 653 start(i) = a; 654 return Size; 655 } 656 657 // We must insert before i. Detect overflow. 658 if (Size == N) 659 return N + 1; 660 661 // Insert before i. 662 this->shift(i, Size); 663 start(i) = a; 664 stop(i) = b; 665 value(i) = y; 666 return Size + 1; 667} 668 669 670//===----------------------------------------------------------------------===// 671//--- IntervalMapImpl::BranchNode ---// 672//===----------------------------------------------------------------------===// 673// 674// A branch node stores references to 1--N subtrees all of the same height. 675// 676// The key array in a branch node holds the rightmost stop key of each subtree. 677// It is redundant to store the last stop key since it can be found in the 678// parent node, but doing so makes tree balancing a lot simpler. 679// 680// It is unusual for a branch node to only have one subtree, but it can happen 681// in the root node if it is smaller than the normal nodes. 682// 683// When all of the leaf nodes from all the subtrees are concatenated, they must 684// satisfy the same constraints as a single leaf node. They must be sorted, 685// sane, and fully coalesced. 686// 687//===----------------------------------------------------------------------===// 688 689template <typename KeyT, typename ValT, unsigned N, typename Traits> 690class BranchNode : public NodeBase<NodeRef, KeyT, N> { 691public: 692 const KeyT &stop(unsigned i) const { return this->second[i]; } 693 const NodeRef &subtree(unsigned i) const { return this->first[i]; } 694 695 KeyT &stop(unsigned i) { return this->second[i]; } 696 NodeRef &subtree(unsigned i) { return this->first[i]; } 697 698 /// findFrom - Find the first subtree after i that may contain x. 699 /// @param i Starting index for the search. 700 /// @param Size Number of elements in node. 701 /// @param x Key to search for. 702 /// @return First index with !stopLess(key[i], x), or size. 703 /// This is the first subtree that can possibly contain x. 704 unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { 705 assert(i <= Size && Size <= N && "Bad indices"); 706 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 707 "Index to findFrom is past the needed point"); 708 while (i != Size && Traits::stopLess(stop(i), x)) ++i; 709 return i; 710 } 711 712 /// safeFind - Find a subtree that is known to exist. This is the same as 713 /// findFrom except is it assumed that x is in range. 714 /// @param i Starting index for the search. 715 /// @param x Key to search for. 716 /// @return First index with !stopLess(key[i], x), never size. 717 /// This is the first subtree that can possibly contain x. 718 unsigned safeFind(unsigned i, KeyT x) const { 719 assert(i < N && "Bad index"); 720 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 721 "Index is past the needed point"); 722 while (Traits::stopLess(stop(i), x)) ++i; 723 assert(i < N && "Unsafe intervals"); 724 return i; 725 } 726 727 /// safeLookup - Get the subtree containing x, Assuming that x is in range. 728 /// @param x Key to search for. 729 /// @return Subtree containing x 730 NodeRef safeLookup(KeyT x) const { 731 return subtree(safeFind(0, x)); 732 } 733 734 /// insert - Insert a new (subtree, stop) pair. 735 /// @param i Insert position, following entries will be shifted. 736 /// @param Size Number of elements in node. 737 /// @param Node Subtree to insert. 738 /// @param Stop Last key in subtree. 739 void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) { 740 assert(Size < N && "branch node overflow"); 741 assert(i <= Size && "Bad insert position"); 742 this->shift(i, Size); 743 subtree(i) = Node; 744 stop(i) = Stop; 745 } 746 747#ifndef NDEBUG 748 void dump(raw_ostream &OS, unsigned Size) { 749 OS << " N" << this << " [shape=record label=\"" << Size << '/' << N; 750 for (unsigned i = 0; i != Size; ++i) 751 OS << " | <s" << i << "> " << stop(i); 752 OS << "\"];\n"; 753 for (unsigned i = 0; i != Size; ++i) 754 OS << " N" << this << ":s" << i << " -> N" 755 << &subtree(i).template get<BranchNode>() << ";\n"; 756 } 757#endif 758 759}; 760 761//===----------------------------------------------------------------------===// 762//--- IntervalMapImpl::Path ---// 763//===----------------------------------------------------------------------===// 764// 765// A Path is used by iterators to represent a position in a B+-tree, and the 766// path to get there from the root. 767// 768// The Path class also constains the tree navigation code that doesn't have to 769// be templatized. 770// 771//===----------------------------------------------------------------------===// 772 773class Path { 774 /// Entry - Each step in the path is a node pointer and an offset into that 775 /// node. 776 struct Entry { 777 void *node; 778 unsigned size; 779 unsigned offset; 780 781 Entry(void *Node, unsigned Size, unsigned Offset) 782 : node(Node), size(Size), offset(Offset) {} 783 784 Entry(NodeRef Node, unsigned Offset) 785 : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {} 786 787 NodeRef &subtree(unsigned i) const { 788 return reinterpret_cast<NodeRef*>(node)[i]; 789 } 790 }; 791 792 /// path - The path entries, path[0] is the root node, path.back() is a leaf. 793 SmallVector<Entry, 4> path; 794 795public: 796 // Node accessors. 797 template <typename NodeT> NodeT &node(unsigned Level) const { 798 return *reinterpret_cast<NodeT*>(path[Level].node); 799 } 800 unsigned size(unsigned Level) const { return path[Level].size; } 801 unsigned offset(unsigned Level) const { return path[Level].offset; } 802 unsigned &offset(unsigned Level) { return path[Level].offset; } 803 804 // Leaf accessors. 805 template <typename NodeT> NodeT &leaf() const { 806 return *reinterpret_cast<NodeT*>(path.back().node); 807 } 808 unsigned leafSize() const { return path.back().size; } 809 unsigned leafOffset() const { return path.back().offset; } 810 unsigned &leafOffset() { return path.back().offset; } 811 812 /// valid - Return true if path is at a valid node, not at end(). 813 bool valid() const { 814 return !path.empty() && path.front().offset < path.front().size; 815 } 816 817 /// height - Return the height of the tree corresponding to this path. 818 /// This matches map->height in a full path. 819 unsigned height() const { return path.size() - 1; } 820 821 /// subtree - Get the subtree referenced from Level. When the path is 822 /// consistent, node(Level + 1) == subtree(Level). 823 /// @param Level 0..height-1. The leaves have no subtrees. 824 NodeRef &subtree(unsigned Level) const { 825 return path[Level].subtree(path[Level].offset); 826 } 827 828 /// reset - Reset cached information about node(Level) from subtree(Level -1). 829 /// @param Level 1..height. THe node to update after parent node changed. 830 void reset(unsigned Level) { 831 path[Level] = Entry(subtree(Level - 1), offset(Level)); 832 } 833 834 /// push - Add entry to path. 835 /// @param Node Node to add, should be subtree(path.size()-1). 836 /// @param Offset Offset into Node. 837 void push(NodeRef Node, unsigned Offset) { 838 path.push_back(Entry(Node, Offset)); 839 } 840 841 /// pop - Remove the last path entry. 842 void pop() { 843 path.pop_back(); 844 } 845 846 /// setSize - Set the size of a node both in the path and in the tree. 847 /// @param Level 0..height. Note that setting the root size won't change 848 /// map->rootSize. 849 /// @param Size New node size. 850 void setSize(unsigned Level, unsigned Size) { 851 path[Level].size = Size; 852 if (Level) 853 subtree(Level - 1).setSize(Size); 854 } 855 856 /// setRoot - Clear the path and set a new root node. 857 /// @param Node New root node. 858 /// @param Size New root size. 859 /// @param Offset Offset into root node. 860 void setRoot(void *Node, unsigned Size, unsigned Offset) { 861 path.clear(); 862 path.push_back(Entry(Node, Size, Offset)); 863 } 864 865 /// replaceRoot - Replace the current root node with two new entries after the 866 /// tree height has increased. 867 /// @param Root The new root node. 868 /// @param Size Number of entries in the new root. 869 /// @param Offsets Offsets into the root and first branch nodes. 870 void replaceRoot(void *Root, unsigned Size, IdxPair Offsets); 871 872 /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 873 /// @param Level Get the sibling to node(Level). 874 /// @return Left sibling, or NodeRef(). 875 NodeRef getLeftSibling(unsigned Level) const; 876 877 /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level 878 /// unaltered. 879 /// @param Level Move node(Level). 880 void moveLeft(unsigned Level); 881 882 /// fillLeft - Grow path to Height by taking leftmost branches. 883 /// @param Height The target height. 884 void fillLeft(unsigned Height) { 885 while (height() < Height) 886 push(subtree(height()), 0); 887 } 888 889 /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 890 /// @param Level Get the sinbling to node(Level). 891 /// @return Left sibling, or NodeRef(). 892 NodeRef getRightSibling(unsigned Level) const; 893 894 /// moveRight - Move path to the left sibling at Level. Leave nodes below 895 /// Level unaltered. 896 /// @param Level Move node(Level). 897 void moveRight(unsigned Level); 898 899 /// atBegin - Return true if path is at begin(). 900 bool atBegin() const { 901 for (unsigned i = 0, e = path.size(); i != e; ++i) 902 if (path[i].offset != 0) 903 return false; 904 return true; 905 } 906 907 /// atLastEntry - Return true if the path is at the last entry of the node at 908 /// Level. 909 /// @param Level Node to examine. 910 bool atLastEntry(unsigned Level) const { 911 return path[Level].offset == path[Level].size - 1; 912 } 913 914 /// legalizeForInsert - Prepare the path for an insertion at Level. When the 915 /// path is at end(), node(Level) may not be a legal node. legalizeForInsert 916 /// ensures that node(Level) is real by moving back to the last node at Level, 917 /// and setting offset(Level) to size(Level) if required. 918 /// @param Level The level where an insertion is about to take place. 919 void legalizeForInsert(unsigned Level) { 920 if (valid()) 921 return; 922 moveLeft(Level); 923 ++path[Level].offset; 924 } 925 926#ifndef NDEBUG 927 void dump() const { 928 for (unsigned l = 0, e = path.size(); l != e; ++l) 929 errs() << l << ": " << path[l].node << ' ' << path[l].size << ' ' 930 << path[l].offset << '\n'; 931 } 932#endif 933}; 934 935} // namespace IntervalMapImpl 936 937 938//===----------------------------------------------------------------------===// 939//--- IntervalMap ----// 940//===----------------------------------------------------------------------===// 941 942template <typename KeyT, typename ValT, 943 unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize, 944 typename Traits = IntervalMapInfo<KeyT> > 945class IntervalMap { 946 typedef IntervalMapImpl::NodeSizer<KeyT, ValT> Sizer; 947 typedef IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits> Leaf; 948 typedef IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits> 949 Branch; 950 typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf; 951 typedef IntervalMapImpl::IdxPair IdxPair; 952 953 // The RootLeaf capacity is given as a template parameter. We must compute the 954 // corresponding RootBranch capacity. 955 enum { 956 DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) / 957 (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)), 958 RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1 959 }; 960 961 typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits> 962 RootBranch; 963 964 // When branched, we store a global start key as well as the branch node. 965 struct RootBranchData { 966 KeyT start; 967 RootBranch node; 968 }; 969 970 enum { 971 RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ? 972 sizeof(RootBranchData) : sizeof(RootLeaf) 973 }; 974 975public: 976 typedef typename Sizer::Allocator Allocator; 977 978private: 979 // The root data is either a RootLeaf or a RootBranchData instance. 980 // We can't put them in a union since C++03 doesn't allow non-trivial 981 // constructors in unions. 982 // Instead, we use a char array with pointer alignment. The alignment is 983 // ensured by the allocator member in the class, but still verified in the 984 // constructor. We don't support keys or values that are more aligned than a 985 // pointer. 986 char data[RootDataSize]; 987 988 // Tree height. 989 // 0: Leaves in root. 990 // 1: Root points to leaf. 991 // 2: root->branch->leaf ... 992 unsigned height; 993 994 // Number of entries in the root node. 995 unsigned rootSize; 996 997 // Allocator used for creating external nodes. 998 Allocator &allocator; 999 1000 /// dataAs - Represent data as a node type without breaking aliasing rules. 1001 template <typename T> 1002 T &dataAs() const { 1003 union { 1004 const char *d; 1005 T *t; 1006 } u; 1007 u.d = data; 1008 return *u.t; 1009 } 1010 1011 const RootLeaf &rootLeaf() const { 1012 assert(!branched() && "Cannot acces leaf data in branched root"); 1013 return dataAs<RootLeaf>(); 1014 } 1015 RootLeaf &rootLeaf() { 1016 assert(!branched() && "Cannot acces leaf data in branched root"); 1017 return dataAs<RootLeaf>(); 1018 } 1019 RootBranchData &rootBranchData() const { 1020 assert(branched() && "Cannot access branch data in non-branched root"); 1021 return dataAs<RootBranchData>(); 1022 } 1023 RootBranchData &rootBranchData() { 1024 assert(branched() && "Cannot access branch data in non-branched root"); 1025 return dataAs<RootBranchData>(); 1026 } 1027 const RootBranch &rootBranch() const { return rootBranchData().node; } 1028 RootBranch &rootBranch() { return rootBranchData().node; } 1029 KeyT rootBranchStart() const { return rootBranchData().start; } 1030 KeyT &rootBranchStart() { return rootBranchData().start; } 1031 1032 template <typename NodeT> NodeT *newNode() { 1033 return new(allocator.template Allocate<NodeT>()) NodeT(); 1034 } 1035 1036 template <typename NodeT> void deleteNode(NodeT *P) { 1037 P->~NodeT(); 1038 allocator.Deallocate(P); 1039 } 1040 1041 IdxPair branchRoot(unsigned Position); 1042 IdxPair splitRoot(unsigned Position); 1043 1044 void switchRootToBranch() { 1045 rootLeaf().~RootLeaf(); 1046 height = 1; 1047 new (&rootBranchData()) RootBranchData(); 1048 } 1049 1050 void switchRootToLeaf() { 1051 rootBranchData().~RootBranchData(); 1052 height = 0; 1053 new(&rootLeaf()) RootLeaf(); 1054 } 1055 1056 bool branched() const { return height > 0; } 1057 1058 ValT treeSafeLookup(KeyT x, ValT NotFound) const; 1059 void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, 1060 unsigned Level)); 1061 void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level); 1062 1063public: 1064 explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) { 1065 assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 && 1066 "Insufficient alignment"); 1067 new(&rootLeaf()) RootLeaf(); 1068 } 1069 1070 ~IntervalMap() { 1071 clear(); 1072 rootLeaf().~RootLeaf(); 1073 } 1074 1075 /// empty - Return true when no intervals are mapped. 1076 bool empty() const { 1077 return rootSize == 0; 1078 } 1079 1080 /// start - Return the smallest mapped key in a non-empty map. 1081 KeyT start() const { 1082 assert(!empty() && "Empty IntervalMap has no start"); 1083 return !branched() ? rootLeaf().start(0) : rootBranchStart(); 1084 } 1085 1086 /// stop - Return the largest mapped key in a non-empty map. 1087 KeyT stop() const { 1088 assert(!empty() && "Empty IntervalMap has no stop"); 1089 return !branched() ? rootLeaf().stop(rootSize - 1) : 1090 rootBranch().stop(rootSize - 1); 1091 } 1092 1093 /// lookup - Return the mapped value at x or NotFound. 1094 ValT lookup(KeyT x, ValT NotFound = ValT()) const { 1095 if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x)) 1096 return NotFound; 1097 return branched() ? treeSafeLookup(x, NotFound) : 1098 rootLeaf().safeLookup(x, NotFound); 1099 } 1100 1101 /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals. 1102 /// It is assumed that no key in the interval is mapped to another value, but 1103 /// overlapping intervals already mapped to y will be coalesced. 1104 void insert(KeyT a, KeyT b, ValT y) { 1105 if (branched() || rootSize == RootLeaf::Capacity) 1106 return find(a).insert(a, b, y); 1107 1108 // Easy insert into root leaf. 1109 unsigned p = rootLeaf().findFrom(0, rootSize, a); 1110 rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y); 1111 } 1112 1113 /// clear - Remove all entries. 1114 void clear(); 1115 1116 class const_iterator; 1117 class iterator; 1118 friend class const_iterator; 1119 friend class iterator; 1120 1121 const_iterator begin() const { 1122 iterator I(*this); 1123 I.goToBegin(); 1124 return I; 1125 } 1126 1127 iterator begin() { 1128 iterator I(*this); 1129 I.goToBegin(); 1130 return I; 1131 } 1132 1133 const_iterator end() const { 1134 iterator I(*this); 1135 I.goToEnd(); 1136 return I; 1137 } 1138 1139 iterator end() { 1140 iterator I(*this); 1141 I.goToEnd(); 1142 return I; 1143 } 1144 1145 /// find - Return an iterator pointing to the first interval ending at or 1146 /// after x, or end(). 1147 const_iterator find(KeyT x) const { 1148 iterator I(*this); 1149 I.find(x); 1150 return I; 1151 } 1152 1153 iterator find(KeyT x) { 1154 iterator I(*this); 1155 I.find(x); 1156 return I; 1157 } 1158 1159#ifndef NDEBUG 1160 raw_ostream *OS; 1161 void dump(); 1162 void dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height); 1163#endif 1164}; 1165 1166/// treeSafeLookup - Return the mapped value at x or NotFound, assuming a 1167/// branched root. 1168template <typename KeyT, typename ValT, unsigned N, typename Traits> 1169ValT IntervalMap<KeyT, ValT, N, Traits>:: 1170treeSafeLookup(KeyT x, ValT NotFound) const { 1171 assert(branched() && "treeLookup assumes a branched root"); 1172 1173 IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x); 1174 for (unsigned h = height-1; h; --h) 1175 NR = NR.get<Branch>().safeLookup(x); 1176 return NR.get<Leaf>().safeLookup(x, NotFound); 1177} 1178 1179 1180// branchRoot - Switch from a leaf root to a branched root. 1181// Return the new (root offset, node offset) corresponding to Position. 1182template <typename KeyT, typename ValT, unsigned N, typename Traits> 1183IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 1184branchRoot(unsigned Position) { 1185 using namespace IntervalMapImpl; 1186 // How many external leaf nodes to hold RootLeaf+1? 1187 const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1; 1188 1189 // Compute element distribution among new nodes. 1190 unsigned size[Nodes]; 1191 IdxPair NewOffset(0, Position); 1192 1193 // Is is very common for the root node to be smaller than external nodes. 1194 if (Nodes == 1) 1195 size[0] = rootSize; 1196 else 1197 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, size, 1198 Position, true); 1199 1200 // Allocate new nodes. 1201 unsigned pos = 0; 1202 NodeRef node[Nodes]; 1203 for (unsigned n = 0; n != Nodes; ++n) { 1204 Leaf *L = newNode<Leaf>(); 1205 L->copy(rootLeaf(), pos, 0, size[n]); 1206 node[n] = NodeRef(L, size[n]); 1207 pos += size[n]; 1208 } 1209 1210 // Destroy the old leaf node, construct branch node instead. 1211 switchRootToBranch(); 1212 for (unsigned n = 0; n != Nodes; ++n) { 1213 rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1); 1214 rootBranch().subtree(n) = node[n]; 1215 } 1216 rootBranchStart() = node[0].template get<Leaf>().start(0); 1217 rootSize = Nodes; 1218 return NewOffset; 1219} 1220 1221// splitRoot - Split the current BranchRoot into multiple Branch nodes. 1222// Return the new (root offset, node offset) corresponding to Position. 1223template <typename KeyT, typename ValT, unsigned N, typename Traits> 1224IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 1225splitRoot(unsigned Position) { 1226 using namespace IntervalMapImpl; 1227 // How many external leaf nodes to hold RootBranch+1? 1228 const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1; 1229 1230 // Compute element distribution among new nodes. 1231 unsigned Size[Nodes]; 1232 IdxPair NewOffset(0, Position); 1233 1234 // Is is very common for the root node to be smaller than external nodes. 1235 if (Nodes == 1) 1236 Size[0] = rootSize; 1237 else 1238 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, Size, 1239 Position, true); 1240 1241 // Allocate new nodes. 1242 unsigned Pos = 0; 1243 NodeRef Node[Nodes]; 1244 for (unsigned n = 0; n != Nodes; ++n) { 1245 Branch *B = newNode<Branch>(); 1246 B->copy(rootBranch(), Pos, 0, Size[n]); 1247 Node[n] = NodeRef(B, Size[n]); 1248 Pos += Size[n]; 1249 } 1250 1251 for (unsigned n = 0; n != Nodes; ++n) { 1252 rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1); 1253 rootBranch().subtree(n) = Node[n]; 1254 } 1255 rootSize = Nodes; 1256 ++height; 1257 return NewOffset; 1258} 1259 1260/// visitNodes - Visit each external node. 1261template <typename KeyT, typename ValT, unsigned N, typename Traits> 1262void IntervalMap<KeyT, ValT, N, Traits>:: 1263visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) { 1264 if (!branched()) 1265 return; 1266 SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs; 1267 1268 // Collect level 0 nodes from the root. 1269 for (unsigned i = 0; i != rootSize; ++i) 1270 Refs.push_back(rootBranch().subtree(i)); 1271 1272 // Visit all branch nodes. 1273 for (unsigned h = height - 1; h; --h) { 1274 for (unsigned i = 0, e = Refs.size(); i != e; ++i) { 1275 for (unsigned j = 0, s = Refs[i].size(); j != s; ++j) 1276 NextRefs.push_back(Refs[i].subtree(j)); 1277 (this->*f)(Refs[i], h); 1278 } 1279 Refs.clear(); 1280 Refs.swap(NextRefs); 1281 } 1282 1283 // Visit all leaf nodes. 1284 for (unsigned i = 0, e = Refs.size(); i != e; ++i) 1285 (this->*f)(Refs[i], 0); 1286} 1287 1288template <typename KeyT, typename ValT, unsigned N, typename Traits> 1289void IntervalMap<KeyT, ValT, N, Traits>:: 1290deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) { 1291 if (Level) 1292 deleteNode(&Node.get<Branch>()); 1293 else 1294 deleteNode(&Node.get<Leaf>()); 1295} 1296 1297template <typename KeyT, typename ValT, unsigned N, typename Traits> 1298void IntervalMap<KeyT, ValT, N, Traits>:: 1299clear() { 1300 if (branched()) { 1301 visitNodes(&IntervalMap::deleteNode); 1302 switchRootToLeaf(); 1303 } 1304 rootSize = 0; 1305} 1306 1307#ifndef NDEBUG 1308template <typename KeyT, typename ValT, unsigned N, typename Traits> 1309void IntervalMap<KeyT, ValT, N, Traits>:: 1310dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height) { 1311 if (Height) 1312 Node.get<Branch>().dump(*OS, Node.size()); 1313 else 1314 Node.get<Leaf>().dump(*OS, Node.size()); 1315} 1316 1317template <typename KeyT, typename ValT, unsigned N, typename Traits> 1318void IntervalMap<KeyT, ValT, N, Traits>:: 1319dump() { 1320 std::string errors; 1321 raw_fd_ostream ofs("tree.dot", errors); 1322 OS = &ofs; 1323 ofs << "digraph {\n"; 1324 if (branched()) 1325 rootBranch().dump(ofs, rootSize); 1326 else 1327 rootLeaf().dump(ofs, rootSize); 1328 visitNodes(&IntervalMap::dumpNode); 1329 ofs << "}\n"; 1330} 1331#endif 1332 1333//===----------------------------------------------------------------------===// 1334//--- IntervalMap::const_iterator ----// 1335//===----------------------------------------------------------------------===// 1336 1337template <typename KeyT, typename ValT, unsigned N, typename Traits> 1338class IntervalMap<KeyT, ValT, N, Traits>::const_iterator : 1339 public std::iterator<std::bidirectional_iterator_tag, ValT> { 1340protected: 1341 friend class IntervalMap; 1342 1343 // The map referred to. 1344 IntervalMap *map; 1345 1346 // We store a full path from the root to the current position. 1347 // The path may be partially filled, but never between iterator calls. 1348 IntervalMapImpl::Path path; 1349 1350 explicit const_iterator(IntervalMap &map) : map(&map) {} 1351 1352 bool branched() const { 1353 assert(map && "Invalid iterator"); 1354 return map->branched(); 1355 } 1356 1357 void setRoot(unsigned Offset) { 1358 if (branched()) 1359 path.setRoot(&map->rootBranch(), map->rootSize, Offset); 1360 else 1361 path.setRoot(&map->rootLeaf(), map->rootSize, Offset); 1362 } 1363 1364 void pathFillFind(KeyT x); 1365 void treeFind(KeyT x); 1366 void treeAdvanceTo(KeyT x); 1367 1368 /// unsafeStart - Writable access to start() for iterator. 1369 KeyT &unsafeStart() const { 1370 assert(valid() && "Cannot access invalid iterator"); 1371 return branched() ? path.leaf<Leaf>().start(path.leafOffset()) : 1372 path.leaf<RootLeaf>().start(path.leafOffset()); 1373 } 1374 1375 /// unsafeStop - Writable access to stop() for iterator. 1376 KeyT &unsafeStop() const { 1377 assert(valid() && "Cannot access invalid iterator"); 1378 return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) : 1379 path.leaf<RootLeaf>().stop(path.leafOffset()); 1380 } 1381 1382 /// unsafeValue - Writable access to value() for iterator. 1383 ValT &unsafeValue() const { 1384 assert(valid() && "Cannot access invalid iterator"); 1385 return branched() ? path.leaf<Leaf>().value(path.leafOffset()) : 1386 path.leaf<RootLeaf>().value(path.leafOffset()); 1387 } 1388 1389public: 1390 /// const_iterator - Create an iterator that isn't pointing anywhere. 1391 const_iterator() : map(0) {} 1392 1393 /// valid - Return true if the current position is valid, false for end(). 1394 bool valid() const { return path.valid(); } 1395 1396 /// start - Return the beginning of the current interval. 1397 const KeyT &start() const { return unsafeStart(); } 1398 1399 /// stop - Return the end of the current interval. 1400 const KeyT &stop() const { return unsafeStop(); } 1401 1402 /// value - Return the mapped value at the current interval. 1403 const ValT &value() const { return unsafeValue(); } 1404 1405 const ValT &operator*() const { return value(); } 1406 1407 bool operator==(const const_iterator &RHS) const { 1408 assert(map == RHS.map && "Cannot compare iterators from different maps"); 1409 if (!valid()) 1410 return !RHS.valid(); 1411 if (path.leafOffset() != RHS.path.leafOffset()) 1412 return false; 1413 return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>(); 1414 } 1415 1416 bool operator!=(const const_iterator &RHS) const { 1417 return !operator==(RHS); 1418 } 1419 1420 /// goToBegin - Move to the first interval in map. 1421 void goToBegin() { 1422 setRoot(0); 1423 if (branched()) 1424 path.fillLeft(map->height); 1425 } 1426 1427 /// goToEnd - Move beyond the last interval in map. 1428 void goToEnd() { 1429 setRoot(map->rootSize); 1430 } 1431 1432 /// preincrement - move to the next interval. 1433 const_iterator &operator++() { 1434 assert(valid() && "Cannot increment end()"); 1435 if (++path.leafOffset() == path.leafSize() && branched()) 1436 path.moveRight(map->height); 1437 return *this; 1438 } 1439 1440 /// postincrement - Dont do that! 1441 const_iterator operator++(int) { 1442 const_iterator tmp = *this; 1443 operator++(); 1444 return tmp; 1445 } 1446 1447 /// predecrement - move to the previous interval. 1448 const_iterator &operator--() { 1449 if (path.leafOffset() && (valid() || !branched())) 1450 --path.leafOffset(); 1451 else 1452 path.moveLeft(map->height); 1453 return *this; 1454 } 1455 1456 /// postdecrement - Dont do that! 1457 const_iterator operator--(int) { 1458 const_iterator tmp = *this; 1459 operator--(); 1460 return tmp; 1461 } 1462 1463 /// find - Move to the first interval with stop >= x, or end(). 1464 /// This is a full search from the root, the current position is ignored. 1465 void find(KeyT x) { 1466 if (branched()) 1467 treeFind(x); 1468 else 1469 setRoot(map->rootLeaf().findFrom(0, map->rootSize, x)); 1470 } 1471 1472 /// advanceTo - Move to the first interval with stop >= x, or end(). 1473 /// The search is started from the current position, and no earlier positions 1474 /// can be found. This is much faster than find() for small moves. 1475 void advanceTo(KeyT x) { 1476 if (branched()) 1477 treeAdvanceTo(x); 1478 else 1479 path.leafOffset() = 1480 map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x); 1481 } 1482 1483}; 1484 1485/// pathFillFind - Complete path by searching for x. 1486/// @param x Key to search for. 1487template <typename KeyT, typename ValT, unsigned N, typename Traits> 1488void IntervalMap<KeyT, ValT, N, Traits>:: 1489const_iterator::pathFillFind(KeyT x) { 1490 IntervalMapImpl::NodeRef NR = path.subtree(path.height()); 1491 for (unsigned i = map->height - path.height() - 1; i; --i) { 1492 unsigned p = NR.get<Branch>().safeFind(0, x); 1493 path.push(NR, p); 1494 NR = NR.subtree(p); 1495 } 1496 path.push(NR, NR.get<Leaf>().safeFind(0, x)); 1497} 1498 1499/// treeFind - Find in a branched tree. 1500/// @param x Key to search for. 1501template <typename KeyT, typename ValT, unsigned N, typename Traits> 1502void IntervalMap<KeyT, ValT, N, Traits>:: 1503const_iterator::treeFind(KeyT x) { 1504 setRoot(map->rootBranch().findFrom(0, map->rootSize, x)); 1505 if (valid()) 1506 pathFillFind(x); 1507} 1508 1509/// treeAdvanceTo - Find position after the current one. 1510/// @param x Key to search for. 1511template <typename KeyT, typename ValT, unsigned N, typename Traits> 1512void IntervalMap<KeyT, ValT, N, Traits>:: 1513const_iterator::treeAdvanceTo(KeyT x) { 1514 // Can we stay on the same leaf node? 1515 if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) { 1516 path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x); 1517 return; 1518 } 1519 1520 // Drop the current leaf. 1521 path.pop(); 1522 1523 // Search towards the root for a usable subtree. 1524 if (path.height()) { 1525 for (unsigned l = path.height() - 1; l; --l) { 1526 if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) { 1527 // The branch node at l+1 is usable 1528 path.offset(l + 1) = 1529 path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x); 1530 return pathFillFind(x); 1531 } 1532 path.pop(); 1533 } 1534 // Is the level-1 Branch usable? 1535 if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) { 1536 path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x); 1537 return pathFillFind(x); 1538 } 1539 } 1540 1541 // We reached the root. 1542 setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x)); 1543 if (valid()) 1544 pathFillFind(x); 1545} 1546 1547//===----------------------------------------------------------------------===// 1548//--- IntervalMap::iterator ----// 1549//===----------------------------------------------------------------------===// 1550 1551template <typename KeyT, typename ValT, unsigned N, typename Traits> 1552class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator { 1553 friend class IntervalMap; 1554 typedef IntervalMapImpl::IdxPair IdxPair; 1555 1556 explicit iterator(IntervalMap &map) : const_iterator(map) {} 1557 1558 void setNodeStop(unsigned Level, KeyT Stop); 1559 bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop); 1560 template <typename NodeT> bool overflow(unsigned Level); 1561 void treeInsert(KeyT a, KeyT b, ValT y); 1562 void eraseNode(unsigned Level); 1563 void treeErase(bool UpdateRoot = true); 1564 bool canCoalesceLeft(KeyT Start, ValT x); 1565 bool canCoalesceRight(KeyT Stop, ValT x); 1566 1567public: 1568 /// iterator - Create null iterator. 1569 iterator() {} 1570 1571 /// setStart - Move the start of the current interval. 1572 /// This may cause coalescing with the previous interval. 1573 /// @param a New start key, must not overlap the previous interval. 1574 void setStart(KeyT a); 1575 1576 /// setStop - Move the end of the current interval. 1577 /// This may cause coalescing with the following interval. 1578 /// @param b New stop key, must not overlap the following interval. 1579 void setStop(KeyT b); 1580 1581 /// setValue - Change the mapped value of the current interval. 1582 /// This may cause coalescing with the previous and following intervals. 1583 /// @param x New value. 1584 void setValue(ValT x); 1585 1586 /// setStartUnchecked - Move the start of the current interval without 1587 /// checking for coalescing or overlaps. 1588 /// This should only be used when it is known that coalescing is not required. 1589 /// @param a New start key. 1590 void setStartUnchecked(KeyT a) { this->unsafeStart() = a; } 1591 1592 /// setStopUnchecked - Move the end of the current interval without checking 1593 /// for coalescing or overlaps. 1594 /// This should only be used when it is known that coalescing is not required. 1595 /// @param b New stop key. 1596 void setStopUnchecked(KeyT b) { 1597 this->unsafeStop() = b; 1598 // Update keys in branch nodes as well. 1599 if (this->path.atLastEntry(this->path.height())) 1600 setNodeStop(this->path.height(), b); 1601 } 1602 1603 /// setValueUnchecked - Change the mapped value of the current interval 1604 /// without checking for coalescing. 1605 /// @param x New value. 1606 void setValueUnchecked(ValT x) { this->unsafeValue() = x; } 1607 1608 /// insert - Insert mapping [a;b] -> y before the current position. 1609 void insert(KeyT a, KeyT b, ValT y); 1610 1611 /// erase - Erase the current interval. 1612 void erase(); 1613 1614 iterator &operator++() { 1615 const_iterator::operator++(); 1616 return *this; 1617 } 1618 1619 iterator operator++(int) { 1620 iterator tmp = *this; 1621 operator++(); 1622 return tmp; 1623 } 1624 1625 iterator &operator--() { 1626 const_iterator::operator--(); 1627 return *this; 1628 } 1629 1630 iterator operator--(int) { 1631 iterator tmp = *this; 1632 operator--(); 1633 return tmp; 1634 } 1635 1636}; 1637 1638/// canCoalesceLeft - Can the current interval coalesce to the left after 1639/// changing start or value? 1640/// @param Start New start of current interval. 1641/// @param Value New value for current interval. 1642/// @return True when updating the current interval would enable coalescing. 1643template <typename KeyT, typename ValT, unsigned N, typename Traits> 1644bool IntervalMap<KeyT, ValT, N, Traits>:: 1645iterator::canCoalesceLeft(KeyT Start, ValT Value) { 1646 using namespace IntervalMapImpl; 1647 Path &P = this->path; 1648 if (!this->branched()) { 1649 unsigned i = P.leafOffset(); 1650 RootLeaf &Node = P.leaf<RootLeaf>(); 1651 return i && Node.value(i-1) == Value && 1652 Traits::adjacent(Node.stop(i-1), Start); 1653 } 1654 // Branched. 1655 if (unsigned i = P.leafOffset()) { 1656 Leaf &Node = P.leaf<Leaf>(); 1657 return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start); 1658 } else if (NodeRef NR = P.getLeftSibling(P.height())) { 1659 unsigned i = NR.size() - 1; 1660 Leaf &Node = NR.get<Leaf>(); 1661 return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start); 1662 } 1663 return false; 1664} 1665 1666/// canCoalesceRight - Can the current interval coalesce to the right after 1667/// changing stop or value? 1668/// @param Stop New stop of current interval. 1669/// @param Value New value for current interval. 1670/// @return True when updating the current interval would enable coalescing. 1671template <typename KeyT, typename ValT, unsigned N, typename Traits> 1672bool IntervalMap<KeyT, ValT, N, Traits>:: 1673iterator::canCoalesceRight(KeyT Stop, ValT Value) { 1674 using namespace IntervalMapImpl; 1675 Path &P = this->path; 1676 unsigned i = P.leafOffset() + 1; 1677 if (!this->branched()) { 1678 if (i >= P.leafSize()) 1679 return false; 1680 RootLeaf &Node = P.leaf<RootLeaf>(); 1681 return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); 1682 } 1683 // Branched. 1684 if (i < P.leafSize()) { 1685 Leaf &Node = P.leaf<Leaf>(); 1686 return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); 1687 } else if (NodeRef NR = P.getRightSibling(P.height())) { 1688 Leaf &Node = NR.get<Leaf>(); 1689 return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0)); 1690 } 1691 return false; 1692} 1693 1694/// setNodeStop - Update the stop key of the current node at level and above. 1695template <typename KeyT, typename ValT, unsigned N, typename Traits> 1696void IntervalMap<KeyT, ValT, N, Traits>:: 1697iterator::setNodeStop(unsigned Level, KeyT Stop) { 1698 // There are no references to the root node, so nothing to update. 1699 if (!Level) 1700 return; 1701 IntervalMapImpl::Path &P = this->path; 1702 // Update nodes pointing to the current node. 1703 while (--Level) { 1704 P.node<Branch>(Level).stop(P.offset(Level)) = Stop; 1705 if (!P.atLastEntry(Level)) 1706 return; 1707 } 1708 // Update root separately since it has a different layout. 1709 P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop; 1710} 1711 1712template <typename KeyT, typename ValT, unsigned N, typename Traits> 1713void IntervalMap<KeyT, ValT, N, Traits>:: 1714iterator::setStart(KeyT a) { 1715 assert(Traits::stopLess(a, this->stop()) && "Cannot move start beyond stop"); 1716 KeyT &CurStart = this->unsafeStart(); 1717 if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) { 1718 CurStart = a; 1719 return; 1720 } 1721 // Coalesce with the interval to the left. 1722 --*this; 1723 a = this->start(); 1724 erase(); 1725 setStartUnchecked(a); 1726} 1727 1728template <typename KeyT, typename ValT, unsigned N, typename Traits> 1729void IntervalMap<KeyT, ValT, N, Traits>:: 1730iterator::setStop(KeyT b) { 1731 assert(Traits::stopLess(this->start(), b) && "Cannot move stop beyond start"); 1732 if (Traits::startLess(b, this->stop()) || 1733 !canCoalesceRight(b, this->value())) { 1734 setStopUnchecked(b); 1735 return; 1736 } 1737 // Coalesce with interval to the right. 1738 KeyT a = this->start(); 1739 erase(); 1740 setStartUnchecked(a); 1741} 1742 1743template <typename KeyT, typename ValT, unsigned N, typename Traits> 1744void IntervalMap<KeyT, ValT, N, Traits>:: 1745iterator::setValue(ValT x) { 1746 setValueUnchecked(x); 1747 if (canCoalesceRight(this->stop(), x)) { 1748 KeyT a = this->start(); 1749 erase(); 1750 setStartUnchecked(a); 1751 } 1752 if (canCoalesceLeft(this->start(), x)) { 1753 --*this; 1754 KeyT a = this->start(); 1755 erase(); 1756 setStartUnchecked(a); 1757 } 1758} 1759 1760/// insertNode - insert a node before the current path at level. 1761/// Leave the current path pointing at the new node. 1762/// @param Level path index of the node to be inserted. 1763/// @param Node The node to be inserted. 1764/// @param Stop The last index in the new node. 1765/// @return True if the tree height was increased. 1766template <typename KeyT, typename ValT, unsigned N, typename Traits> 1767bool IntervalMap<KeyT, ValT, N, Traits>:: 1768iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) { 1769 assert(Level && "Cannot insert next to the root"); 1770 bool SplitRoot = false; 1771 IntervalMap &IM = *this->map; 1772 IntervalMapImpl::Path &P = this->path; 1773 1774 if (Level == 1) { 1775 // Insert into the root branch node. 1776 if (IM.rootSize < RootBranch::Capacity) { 1777 IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop); 1778 P.setSize(0, ++IM.rootSize); 1779 P.reset(Level); 1780 return SplitRoot; 1781 } 1782 1783 // We need to split the root while keeping our position. 1784 SplitRoot = true; 1785 IdxPair Offset = IM.splitRoot(P.offset(0)); 1786 P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1787 1788 // Fall through to insert at the new higher level. 1789 ++Level; 1790 } 1791 1792 // When inserting before end(), make sure we have a valid path. 1793 P.legalizeForInsert(--Level); 1794 1795 // Insert into the branch node at Level-1. 1796 if (P.size(Level) == Branch::Capacity) { 1797 // Branch node is full, handle handle the overflow. 1798 assert(!SplitRoot && "Cannot overflow after splitting the root"); 1799 SplitRoot = overflow<Branch>(Level); 1800 Level += SplitRoot; 1801 } 1802 P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop); 1803 P.setSize(Level, P.size(Level) + 1); 1804 if (P.atLastEntry(Level)) 1805 setNodeStop(Level, Stop); 1806 P.reset(Level + 1); 1807 return SplitRoot; 1808} 1809 1810// insert 1811template <typename KeyT, typename ValT, unsigned N, typename Traits> 1812void IntervalMap<KeyT, ValT, N, Traits>:: 1813iterator::insert(KeyT a, KeyT b, ValT y) { 1814 if (this->branched()) 1815 return treeInsert(a, b, y); 1816 IntervalMap &IM = *this->map; 1817 IntervalMapImpl::Path &P = this->path; 1818 1819 // Try simple root leaf insert. 1820 unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y); 1821 1822 // Was the root node insert successful? 1823 if (Size <= RootLeaf::Capacity) { 1824 P.setSize(0, IM.rootSize = Size); 1825 return; 1826 } 1827 1828 // Root leaf node is full, we must branch. 1829 IdxPair Offset = IM.branchRoot(P.leafOffset()); 1830 P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1831 1832 // Now it fits in the new leaf. 1833 treeInsert(a, b, y); 1834} 1835 1836 1837template <typename KeyT, typename ValT, unsigned N, typename Traits> 1838void IntervalMap<KeyT, ValT, N, Traits>:: 1839iterator::treeInsert(KeyT a, KeyT b, ValT y) { 1840 using namespace IntervalMapImpl; 1841 Path &P = this->path; 1842 1843 if (!P.valid()) 1844 P.legalizeForInsert(this->map->height); 1845 1846 // Check if this insertion will extend the node to the left. 1847 if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) { 1848 // Node is growing to the left, will it affect a left sibling node? 1849 if (NodeRef Sib = P.getLeftSibling(P.height())) { 1850 Leaf &SibLeaf = Sib.get<Leaf>(); 1851 unsigned SibOfs = Sib.size() - 1; 1852 if (SibLeaf.value(SibOfs) == y && 1853 Traits::adjacent(SibLeaf.stop(SibOfs), a)) { 1854 // This insertion will coalesce with the last entry in SibLeaf. We can 1855 // handle it in two ways: 1856 // 1. Extend SibLeaf.stop to b and be done, or 1857 // 2. Extend a to SibLeaf, erase the SibLeaf entry and continue. 1858 // We prefer 1., but need 2 when coalescing to the right as well. 1859 Leaf &CurLeaf = P.leaf<Leaf>(); 1860 P.moveLeft(P.height()); 1861 if (Traits::stopLess(b, CurLeaf.start(0)) && 1862 (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) { 1863 // Easy, just extend SibLeaf and we're done. 1864 setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b); 1865 return; 1866 } else { 1867 // We have both left and right coalescing. Erase the old SibLeaf entry 1868 // and continue inserting the larger interval. 1869 a = SibLeaf.start(SibOfs); 1870 treeErase(/* UpdateRoot= */false); 1871 } 1872 } 1873 } else { 1874 // No left sibling means we are at begin(). Update cached bound. 1875 this->map->rootBranchStart() = a; 1876 } 1877 } 1878 1879 // When we are inserting at the end of a leaf node, we must update stops. 1880 unsigned Size = P.leafSize(); 1881 bool Grow = P.leafOffset() == Size; 1882 Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y); 1883 1884 // Leaf insertion unsuccessful? Overflow and try again. 1885 if (Size > Leaf::Capacity) { 1886 overflow<Leaf>(P.height()); 1887 Grow = P.leafOffset() == P.leafSize(); 1888 Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y); 1889 assert(Size <= Leaf::Capacity && "overflow() didn't make room"); 1890 } 1891 1892 // Inserted, update offset and leaf size. 1893 P.setSize(P.height(), Size); 1894 1895 // Insert was the last node entry, update stops. 1896 if (Grow) 1897 setNodeStop(P.height(), b); 1898} 1899 1900/// erase - erase the current interval and move to the next position. 1901template <typename KeyT, typename ValT, unsigned N, typename Traits> 1902void IntervalMap<KeyT, ValT, N, Traits>:: 1903iterator::erase() { 1904 IntervalMap &IM = *this->map; 1905 IntervalMapImpl::Path &P = this->path; 1906 assert(P.valid() && "Cannot erase end()"); 1907 if (this->branched()) 1908 return treeErase(); 1909 IM.rootLeaf().erase(P.leafOffset(), IM.rootSize); 1910 P.setSize(0, --IM.rootSize); 1911} 1912 1913/// treeErase - erase() for a branched tree. 1914template <typename KeyT, typename ValT, unsigned N, typename Traits> 1915void IntervalMap<KeyT, ValT, N, Traits>:: 1916iterator::treeErase(bool UpdateRoot) { 1917 IntervalMap &IM = *this->map; 1918 IntervalMapImpl::Path &P = this->path; 1919 Leaf &Node = P.leaf<Leaf>(); 1920 1921 // Nodes are not allowed to become empty. 1922 if (P.leafSize() == 1) { 1923 IM.deleteNode(&Node); 1924 eraseNode(IM.height); 1925 // Update rootBranchStart if we erased begin(). 1926 if (UpdateRoot && IM.branched() && P.valid() && P.atBegin()) 1927 IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1928 return; 1929 } 1930 1931 // Erase current entry. 1932 Node.erase(P.leafOffset(), P.leafSize()); 1933 unsigned NewSize = P.leafSize() - 1; 1934 P.setSize(IM.height, NewSize); 1935 // When we erase the last entry, update stop and move to a legal position. 1936 if (P.leafOffset() == NewSize) { 1937 setNodeStop(IM.height, Node.stop(NewSize - 1)); 1938 P.moveRight(IM.height); 1939 } else if (UpdateRoot && P.atBegin()) 1940 IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1941} 1942 1943/// eraseNode - Erase the current node at Level from its parent and move path to 1944/// the first entry of the next sibling node. 1945/// The node must be deallocated by the caller. 1946/// @param Level 1..height, the root node cannot be erased. 1947template <typename KeyT, typename ValT, unsigned N, typename Traits> 1948void IntervalMap<KeyT, ValT, N, Traits>:: 1949iterator::eraseNode(unsigned Level) { 1950 assert(Level && "Cannot erase root node"); 1951 IntervalMap &IM = *this->map; 1952 IntervalMapImpl::Path &P = this->path; 1953 1954 if (--Level == 0) { 1955 IM.rootBranch().erase(P.offset(0), IM.rootSize); 1956 P.setSize(0, --IM.rootSize); 1957 // If this cleared the root, switch to height=0. 1958 if (IM.empty()) { 1959 IM.switchRootToLeaf(); 1960 this->setRoot(0); 1961 return; 1962 } 1963 } else { 1964 // Remove node ref from branch node at Level. 1965 Branch &Parent = P.node<Branch>(Level); 1966 if (P.size(Level) == 1) { 1967 // Branch node became empty, remove it recursively. 1968 IM.deleteNode(&Parent); 1969 eraseNode(Level); 1970 } else { 1971 // Branch node won't become empty. 1972 Parent.erase(P.offset(Level), P.size(Level)); 1973 unsigned NewSize = P.size(Level) - 1; 1974 P.setSize(Level, NewSize); 1975 // If we removed the last branch, update stop and move to a legal pos. 1976 if (P.offset(Level) == NewSize) { 1977 setNodeStop(Level, Parent.stop(NewSize - 1)); 1978 P.moveRight(Level); 1979 } 1980 } 1981 } 1982 // Update path cache for the new right sibling position. 1983 if (P.valid()) { 1984 P.reset(Level + 1); 1985 P.offset(Level + 1) = 0; 1986 } 1987} 1988 1989/// overflow - Distribute entries of the current node evenly among 1990/// its siblings and ensure that the current node is not full. 1991/// This may require allocating a new node. 1992/// @param NodeT The type of node at Level (Leaf or Branch). 1993/// @param Level path index of the overflowing node. 1994/// @return True when the tree height was changed. 1995template <typename KeyT, typename ValT, unsigned N, typename Traits> 1996template <typename NodeT> 1997bool IntervalMap<KeyT, ValT, N, Traits>:: 1998iterator::overflow(unsigned Level) { 1999 using namespace IntervalMapImpl; 2000 Path &P = this->path; 2001 unsigned CurSize[4]; 2002 NodeT *Node[4]; 2003 unsigned Nodes = 0; 2004 unsigned Elements = 0; 2005 unsigned Offset = P.offset(Level); 2006 2007 // Do we have a left sibling? 2008 NodeRef LeftSib = P.getLeftSibling(Level); 2009 if (LeftSib) { 2010 Offset += Elements = CurSize[Nodes] = LeftSib.size(); 2011 Node[Nodes++] = &LeftSib.get<NodeT>(); 2012 } 2013 2014 // Current node. 2015 Elements += CurSize[Nodes] = P.size(Level); 2016 Node[Nodes++] = &P.node<NodeT>(Level); 2017 2018 // Do we have a right sibling? 2019 NodeRef RightSib = P.getRightSibling(Level); 2020 if (RightSib) { 2021 Elements += CurSize[Nodes] = RightSib.size(); 2022 Node[Nodes++] = &RightSib.get<NodeT>(); 2023 } 2024 2025 // Do we need to allocate a new node? 2026 unsigned NewNode = 0; 2027 if (Elements + 1 > Nodes * NodeT::Capacity) { 2028 // Insert NewNode at the penultimate position, or after a single node. 2029 NewNode = Nodes == 1 ? 1 : Nodes - 1; 2030 CurSize[Nodes] = CurSize[NewNode]; 2031 Node[Nodes] = Node[NewNode]; 2032 CurSize[NewNode] = 0; 2033 Node[NewNode] = this->map->newNode<NodeT>(); 2034 ++Nodes; 2035 } 2036 2037 // Compute the new element distribution. 2038 unsigned NewSize[4]; 2039 IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity, 2040 CurSize, NewSize, Offset, true); 2041 adjustSiblingSizes(Node, Nodes, CurSize, NewSize); 2042 2043 // Move current location to the leftmost node. 2044 if (LeftSib) 2045 P.moveLeft(Level); 2046 2047 // Elements have been rearranged, now update node sizes and stops. 2048 bool SplitRoot = false; 2049 unsigned Pos = 0; 2050 for (;;) { 2051 KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1); 2052 if (NewNode && Pos == NewNode) { 2053 SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop); 2054 Level += SplitRoot; 2055 } else { 2056 P.setSize(Level, NewSize[Pos]); 2057 setNodeStop(Level, Stop); 2058 } 2059 if (Pos + 1 == Nodes) 2060 break; 2061 P.moveRight(Level); 2062 ++Pos; 2063 } 2064 2065 // Where was I? Find NewOffset. 2066 while(Pos != NewOffset.first) { 2067 P.moveLeft(Level); 2068 --Pos; 2069 } 2070 P.offset(Level) = NewOffset.second; 2071 return SplitRoot; 2072} 2073 2074} // namespace llvm 2075 2076#endif 2077