IntervalMap.h revision 08d55342e337fd4e80a68b81b8b0cbb100ea0a23
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 /// atLastBranch - Return true if the path is at the last branch of the node 908 /// at Level. 909 /// @param Level Node to examine. 910 bool atLastBranch(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 1368public: 1369 /// const_iterator - Create an iterator that isn't pointing anywhere. 1370 const_iterator() : map(0) {} 1371 1372 /// valid - Return true if the current position is valid, false for end(). 1373 bool valid() const { return path.valid(); } 1374 1375 /// start - Return the beginning of the current interval. 1376 const KeyT &start() const { 1377 assert(valid() && "Cannot access invalid iterator"); 1378 return branched() ? path.leaf<Leaf>().start(path.leafOffset()) : 1379 path.leaf<RootLeaf>().start(path.leafOffset()); 1380 } 1381 1382 /// stop - Return the end of the current interval. 1383 const KeyT &stop() const { 1384 assert(valid() && "Cannot access invalid iterator"); 1385 return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) : 1386 path.leaf<RootLeaf>().stop(path.leafOffset()); 1387 } 1388 1389 /// value - Return the mapped value at the current interval. 1390 const ValT &value() const { 1391 assert(valid() && "Cannot access invalid iterator"); 1392 return branched() ? path.leaf<Leaf>().value(path.leafOffset()) : 1393 path.leaf<RootLeaf>().value(path.leafOffset()); 1394 } 1395 1396 const ValT &operator*() const { 1397 return value(); 1398 } 1399 1400 bool operator==(const const_iterator &RHS) const { 1401 assert(map == RHS.map && "Cannot compare iterators from different maps"); 1402 if (!valid()) 1403 return !RHS.valid(); 1404 if (path.leafOffset() != RHS.path.leafOffset()) 1405 return false; 1406 return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>(); 1407 } 1408 1409 bool operator!=(const const_iterator &RHS) const { 1410 return !operator==(RHS); 1411 } 1412 1413 /// goToBegin - Move to the first interval in map. 1414 void goToBegin() { 1415 setRoot(0); 1416 if (branched()) 1417 path.fillLeft(map->height); 1418 } 1419 1420 /// goToEnd - Move beyond the last interval in map. 1421 void goToEnd() { 1422 setRoot(map->rootSize); 1423 } 1424 1425 /// preincrement - move to the next interval. 1426 const_iterator &operator++() { 1427 assert(valid() && "Cannot increment end()"); 1428 if (++path.leafOffset() == path.leafSize() && branched()) 1429 path.moveRight(map->height); 1430 return *this; 1431 } 1432 1433 /// postincrement - Dont do that! 1434 const_iterator operator++(int) { 1435 const_iterator tmp = *this; 1436 operator++(); 1437 return tmp; 1438 } 1439 1440 /// predecrement - move to the previous interval. 1441 const_iterator &operator--() { 1442 if (path.leafOffset() && (valid() || !branched())) 1443 --path.leafOffset(); 1444 else 1445 path.moveLeft(map->height); 1446 return *this; 1447 } 1448 1449 /// postdecrement - Dont do that! 1450 const_iterator operator--(int) { 1451 const_iterator tmp = *this; 1452 operator--(); 1453 return tmp; 1454 } 1455 1456 /// find - Move to the first interval with stop >= x, or end(). 1457 /// This is a full search from the root, the current position is ignored. 1458 void find(KeyT x) { 1459 if (branched()) 1460 treeFind(x); 1461 else 1462 setRoot(map->rootLeaf().findFrom(0, map->rootSize, x)); 1463 } 1464 1465 /// advanceTo - Move to the first interval with stop >= x, or end(). 1466 /// The search is started from the current position, and no earlier positions 1467 /// can be found. This is much faster than find() for small moves. 1468 void advanceTo(KeyT x) { 1469 if (branched()) 1470 treeAdvanceTo(x); 1471 else 1472 path.leafOffset() = 1473 map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x); 1474 } 1475 1476}; 1477 1478/// pathFillFind - Complete path by searching for x. 1479/// @param x Key to search for. 1480template <typename KeyT, typename ValT, unsigned N, typename Traits> 1481void IntervalMap<KeyT, ValT, N, Traits>:: 1482const_iterator::pathFillFind(KeyT x) { 1483 IntervalMapImpl::NodeRef NR = path.subtree(path.height()); 1484 for (unsigned i = map->height - path.height() - 1; i; --i) { 1485 unsigned p = NR.get<Branch>().safeFind(0, x); 1486 path.push(NR, p); 1487 NR = NR.subtree(p); 1488 } 1489 path.push(NR, NR.get<Leaf>().safeFind(0, x)); 1490} 1491 1492/// treeFind - Find in a branched tree. 1493/// @param x Key to search for. 1494template <typename KeyT, typename ValT, unsigned N, typename Traits> 1495void IntervalMap<KeyT, ValT, N, Traits>:: 1496const_iterator::treeFind(KeyT x) { 1497 setRoot(map->rootBranch().findFrom(0, map->rootSize, x)); 1498 if (valid()) 1499 pathFillFind(x); 1500} 1501 1502/// treeAdvanceTo - Find position after the current one. 1503/// @param x Key to search for. 1504template <typename KeyT, typename ValT, unsigned N, typename Traits> 1505void IntervalMap<KeyT, ValT, N, Traits>:: 1506const_iterator::treeAdvanceTo(KeyT x) { 1507 // Can we stay on the same leaf node? 1508 if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) { 1509 path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x); 1510 return; 1511 } 1512 1513 // Drop the current leaf. 1514 path.pop(); 1515 1516 // Search towards the root for a usable subtree. 1517 if (path.height()) { 1518 for (unsigned l = path.height() - 1; l; --l) { 1519 if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) { 1520 // The branch node at l+1 is usable 1521 path.offset(l + 1) = 1522 path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x); 1523 return pathFillFind(x); 1524 } 1525 path.pop(); 1526 } 1527 // Is the level-1 Branch usable? 1528 if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) { 1529 path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x); 1530 return pathFillFind(x); 1531 } 1532 } 1533 1534 // We reached the root. 1535 setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x)); 1536 if (valid()) 1537 pathFillFind(x); 1538} 1539 1540//===----------------------------------------------------------------------===// 1541//--- IntervalMap::iterator ----// 1542//===----------------------------------------------------------------------===// 1543 1544template <typename KeyT, typename ValT, unsigned N, typename Traits> 1545class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator { 1546 friend class IntervalMap; 1547 typedef IntervalMapImpl::IdxPair IdxPair; 1548 1549 explicit iterator(IntervalMap &map) : const_iterator(map) {} 1550 1551 void setNodeStop(unsigned Level, KeyT Stop); 1552 bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop); 1553 template <typename NodeT> bool overflow(unsigned Level); 1554 void treeInsert(KeyT a, KeyT b, ValT y); 1555 void eraseNode(unsigned Level); 1556 void treeErase(bool UpdateRoot = true); 1557public: 1558 /// iterator - Create null iterator. 1559 iterator() {} 1560 1561 /// insert - Insert mapping [a;b] -> y before the current position. 1562 void insert(KeyT a, KeyT b, ValT y); 1563 1564 /// erase - Erase the current interval. 1565 void erase(); 1566 1567 iterator &operator++() { 1568 const_iterator::operator++(); 1569 return *this; 1570 } 1571 1572 iterator operator++(int) { 1573 iterator tmp = *this; 1574 operator++(); 1575 return tmp; 1576 } 1577 1578 iterator &operator--() { 1579 const_iterator::operator--(); 1580 return *this; 1581 } 1582 1583 iterator operator--(int) { 1584 iterator tmp = *this; 1585 operator--(); 1586 return tmp; 1587 } 1588 1589}; 1590 1591/// setNodeStop - Update the stop key of the current node at level and above. 1592template <typename KeyT, typename ValT, unsigned N, typename Traits> 1593void IntervalMap<KeyT, ValT, N, Traits>:: 1594iterator::setNodeStop(unsigned Level, KeyT Stop) { 1595 // There are no references to the root node, so nothing to update. 1596 if (!Level) 1597 return; 1598 IntervalMapImpl::Path &P = this->path; 1599 // Update nodes pointing to the current node. 1600 while (--Level) { 1601 P.node<Branch>(Level).stop(P.offset(Level)) = Stop; 1602 if (!P.atLastBranch(Level)) 1603 return; 1604 } 1605 // Update root separately since it has a different layout. 1606 P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop; 1607} 1608 1609/// insertNode - insert a node before the current path at level. 1610/// Leave the current path pointing at the new node. 1611/// @param Level path index of the node to be inserted. 1612/// @param Node The node to be inserted. 1613/// @param Stop The last index in the new node. 1614/// @return True if the tree height was increased. 1615template <typename KeyT, typename ValT, unsigned N, typename Traits> 1616bool IntervalMap<KeyT, ValT, N, Traits>:: 1617iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) { 1618 assert(Level && "Cannot insert next to the root"); 1619 bool SplitRoot = false; 1620 IntervalMap &IM = *this->map; 1621 IntervalMapImpl::Path &P = this->path; 1622 1623 if (Level == 1) { 1624 // Insert into the root branch node. 1625 if (IM.rootSize < RootBranch::Capacity) { 1626 IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop); 1627 P.setSize(0, ++IM.rootSize); 1628 P.reset(Level); 1629 return SplitRoot; 1630 } 1631 1632 // We need to split the root while keeping our position. 1633 SplitRoot = true; 1634 IdxPair Offset = IM.splitRoot(P.offset(0)); 1635 P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1636 1637 // Fall through to insert at the new higher level. 1638 ++Level; 1639 } 1640 1641 // When inserting before end(), make sure we have a valid path. 1642 P.legalizeForInsert(--Level); 1643 1644 // Insert into the branch node at Level-1. 1645 if (P.size(Level) == Branch::Capacity) { 1646 // Branch node is full, handle handle the overflow. 1647 assert(!SplitRoot && "Cannot overflow after splitting the root"); 1648 SplitRoot = overflow<Branch>(Level); 1649 Level += SplitRoot; 1650 } 1651 P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop); 1652 P.setSize(Level, P.size(Level) + 1); 1653 if (P.atLastBranch(Level)) 1654 setNodeStop(Level, Stop); 1655 P.reset(Level + 1); 1656 return SplitRoot; 1657} 1658 1659// insert 1660template <typename KeyT, typename ValT, unsigned N, typename Traits> 1661void IntervalMap<KeyT, ValT, N, Traits>:: 1662iterator::insert(KeyT a, KeyT b, ValT y) { 1663 if (this->branched()) 1664 return treeInsert(a, b, y); 1665 IntervalMap &IM = *this->map; 1666 IntervalMapImpl::Path &P = this->path; 1667 1668 // Try simple root leaf insert. 1669 unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y); 1670 1671 // Was the root node insert successful? 1672 if (Size <= RootLeaf::Capacity) { 1673 P.setSize(0, IM.rootSize = Size); 1674 return; 1675 } 1676 1677 // Root leaf node is full, we must branch. 1678 IdxPair Offset = IM.branchRoot(P.leafOffset()); 1679 P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1680 1681 // Now it fits in the new leaf. 1682 treeInsert(a, b, y); 1683} 1684 1685 1686template <typename KeyT, typename ValT, unsigned N, typename Traits> 1687void IntervalMap<KeyT, ValT, N, Traits>:: 1688iterator::treeInsert(KeyT a, KeyT b, ValT y) { 1689 using namespace IntervalMapImpl; 1690 Path &P = this->path; 1691 1692 if (!P.valid()) 1693 P.legalizeForInsert(this->map->height); 1694 1695 // Check if this insertion will extend the node to the left. 1696 if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) { 1697 // Node is growing to the left, will it affect a left sibling node? 1698 if (NodeRef Sib = P.getLeftSibling(P.height())) { 1699 Leaf &SibLeaf = Sib.get<Leaf>(); 1700 unsigned SibOfs = Sib.size() - 1; 1701 if (SibLeaf.value(SibOfs) == y && 1702 Traits::adjacent(SibLeaf.stop(SibOfs), a)) { 1703 // This insertion will coalesce with the last entry in SibLeaf. We can 1704 // handle it in two ways: 1705 // 1. Extend SibLeaf.stop to b and be done, or 1706 // 2. Extend a to SibLeaf, erase the SibLeaf entry and continue. 1707 // We prefer 1., but need 2 when coalescing to the right as well. 1708 Leaf &CurLeaf = P.leaf<Leaf>(); 1709 P.moveLeft(P.height()); 1710 if (Traits::stopLess(b, CurLeaf.start(0)) && 1711 (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) { 1712 // Easy, just extend SibLeaf and we're done. 1713 setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b); 1714 return; 1715 } else { 1716 // We have both left and right coalescing. Erase the old SibLeaf entry 1717 // and continue inserting the larger interval. 1718 a = SibLeaf.start(SibOfs); 1719 treeErase(/* UpdateRoot= */false); 1720 } 1721 } 1722 } else { 1723 // No left sibling means we are at begin(). Update cached bound. 1724 this->map->rootBranchStart() = a; 1725 } 1726 } 1727 1728 // When we are inserting at the end of a leaf node, we must update stops. 1729 unsigned Size = P.leafSize(); 1730 bool Grow = P.leafOffset() == Size; 1731 Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y); 1732 1733 // Leaf insertion unsuccessful? Overflow and try again. 1734 if (Size > Leaf::Capacity) { 1735 overflow<Leaf>(P.height()); 1736 Grow = P.leafOffset() == P.leafSize(); 1737 Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y); 1738 assert(Size <= Leaf::Capacity && "overflow() didn't make room"); 1739 } 1740 1741 // Inserted, update offset and leaf size. 1742 P.setSize(P.height(), Size); 1743 1744 // Insert was the last node entry, update stops. 1745 if (Grow) 1746 setNodeStop(P.height(), b); 1747} 1748 1749/// erase - erase the current interval and move to the next position. 1750template <typename KeyT, typename ValT, unsigned N, typename Traits> 1751void IntervalMap<KeyT, ValT, N, Traits>:: 1752iterator::erase() { 1753 IntervalMap &IM = *this->map; 1754 IntervalMapImpl::Path &P = this->path; 1755 assert(P.valid() && "Cannot erase end()"); 1756 if (this->branched()) 1757 return treeErase(); 1758 IM.rootLeaf().erase(P.leafOffset(), IM.rootSize); 1759 P.setSize(0, --IM.rootSize); 1760} 1761 1762/// treeErase - erase() for a branched tree. 1763template <typename KeyT, typename ValT, unsigned N, typename Traits> 1764void IntervalMap<KeyT, ValT, N, Traits>:: 1765iterator::treeErase(bool UpdateRoot) { 1766 IntervalMap &IM = *this->map; 1767 IntervalMapImpl::Path &P = this->path; 1768 Leaf &Node = P.leaf<Leaf>(); 1769 1770 // Nodes are not allowed to become empty. 1771 if (P.leafSize() == 1) { 1772 IM.deleteNode(&Node); 1773 eraseNode(IM.height); 1774 // Update rootBranchStart if we erased begin(). 1775 if (UpdateRoot && IM.branched() && P.valid() && P.atBegin()) 1776 IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1777 return; 1778 } 1779 1780 // Erase current entry. 1781 Node.erase(P.leafOffset(), P.leafSize()); 1782 unsigned NewSize = P.leafSize() - 1; 1783 P.setSize(IM.height, NewSize); 1784 // When we erase the last entry, update stop and move to a legal position. 1785 if (P.leafOffset() == NewSize) { 1786 setNodeStop(IM.height, Node.stop(NewSize - 1)); 1787 P.moveRight(IM.height); 1788 } else if (UpdateRoot && P.atBegin()) 1789 IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1790} 1791 1792/// eraseNode - Erase the current node at Level from its parent and move path to 1793/// the first entry of the next sibling node. 1794/// The node must be deallocated by the caller. 1795/// @param Level 1..height, the root node cannot be erased. 1796template <typename KeyT, typename ValT, unsigned N, typename Traits> 1797void IntervalMap<KeyT, ValT, N, Traits>:: 1798iterator::eraseNode(unsigned Level) { 1799 assert(Level && "Cannot erase root node"); 1800 IntervalMap &IM = *this->map; 1801 IntervalMapImpl::Path &P = this->path; 1802 1803 if (--Level == 0) { 1804 IM.rootBranch().erase(P.offset(0), IM.rootSize); 1805 P.setSize(0, --IM.rootSize); 1806 // If this cleared the root, switch to height=0. 1807 if (IM.empty()) { 1808 IM.switchRootToLeaf(); 1809 this->setRoot(0); 1810 return; 1811 } 1812 } else { 1813 // Remove node ref from branch node at Level. 1814 Branch &Parent = P.node<Branch>(Level); 1815 if (P.size(Level) == 1) { 1816 // Branch node became empty, remove it recursively. 1817 IM.deleteNode(&Parent); 1818 eraseNode(Level); 1819 } else { 1820 // Branch node won't become empty. 1821 Parent.erase(P.offset(Level), P.size(Level)); 1822 unsigned NewSize = P.size(Level) - 1; 1823 P.setSize(Level, NewSize); 1824 // If we removed the last branch, update stop and move to a legal pos. 1825 if (P.offset(Level) == NewSize) { 1826 setNodeStop(Level, Parent.stop(NewSize - 1)); 1827 P.moveRight(Level); 1828 } 1829 } 1830 } 1831 // Update path cache for the new right sibling position. 1832 if (P.valid()) { 1833 P.reset(Level + 1); 1834 P.offset(Level + 1) = 0; 1835 } 1836} 1837 1838/// overflow - Distribute entries of the current node evenly among 1839/// its siblings and ensure that the current node is not full. 1840/// This may require allocating a new node. 1841/// @param NodeT The type of node at Level (Leaf or Branch). 1842/// @param Level path index of the overflowing node. 1843/// @return True when the tree height was changed. 1844template <typename KeyT, typename ValT, unsigned N, typename Traits> 1845template <typename NodeT> 1846bool IntervalMap<KeyT, ValT, N, Traits>:: 1847iterator::overflow(unsigned Level) { 1848 using namespace IntervalMapImpl; 1849 Path &P = this->path; 1850 unsigned CurSize[4]; 1851 NodeT *Node[4]; 1852 unsigned Nodes = 0; 1853 unsigned Elements = 0; 1854 unsigned Offset = P.offset(Level); 1855 1856 // Do we have a left sibling? 1857 NodeRef LeftSib = P.getLeftSibling(Level); 1858 if (LeftSib) { 1859 Offset += Elements = CurSize[Nodes] = LeftSib.size(); 1860 Node[Nodes++] = &LeftSib.get<NodeT>(); 1861 } 1862 1863 // Current node. 1864 Elements += CurSize[Nodes] = P.size(Level); 1865 Node[Nodes++] = &P.node<NodeT>(Level); 1866 1867 // Do we have a right sibling? 1868 NodeRef RightSib = P.getRightSibling(Level); 1869 if (RightSib) { 1870 Elements += CurSize[Nodes] = RightSib.size(); 1871 Node[Nodes++] = &RightSib.get<NodeT>(); 1872 } 1873 1874 // Do we need to allocate a new node? 1875 unsigned NewNode = 0; 1876 if (Elements + 1 > Nodes * NodeT::Capacity) { 1877 // Insert NewNode at the penultimate position, or after a single node. 1878 NewNode = Nodes == 1 ? 1 : Nodes - 1; 1879 CurSize[Nodes] = CurSize[NewNode]; 1880 Node[Nodes] = Node[NewNode]; 1881 CurSize[NewNode] = 0; 1882 Node[NewNode] = this->map->newNode<NodeT>(); 1883 ++Nodes; 1884 } 1885 1886 // Compute the new element distribution. 1887 unsigned NewSize[4]; 1888 IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity, 1889 CurSize, NewSize, Offset, true); 1890 adjustSiblingSizes(Node, Nodes, CurSize, NewSize); 1891 1892 // Move current location to the leftmost node. 1893 if (LeftSib) 1894 P.moveLeft(Level); 1895 1896 // Elements have been rearranged, now update node sizes and stops. 1897 bool SplitRoot = false; 1898 unsigned Pos = 0; 1899 for (;;) { 1900 KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1); 1901 if (NewNode && Pos == NewNode) { 1902 SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop); 1903 Level += SplitRoot; 1904 } else { 1905 P.setSize(Level, NewSize[Pos]); 1906 setNodeStop(Level, Stop); 1907 } 1908 if (Pos + 1 == Nodes) 1909 break; 1910 P.moveRight(Level); 1911 ++Pos; 1912 } 1913 1914 // Where was I? Find NewOffset. 1915 while(Pos != NewOffset.first) { 1916 P.moveLeft(Level); 1917 --Pos; 1918 } 1919 P.offset(Level) = NewOffset.second; 1920 return SplitRoot; 1921} 1922 1923} // namespace llvm 1924 1925#endif 1926