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