IntervalMap.h revision 9a08ca318e63912e4c19977abc1173f30866b704
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 /// pop - Remove the last path entry. 873 void pop() { 874 path.pop_back(); 875 } 876 877 /// setSize - Set the size of a node both in the path and in the tree. 878 /// @param Level 0..height. Note that setting the root size won't change 879 /// map->rootSize. 880 /// @param Size New node size. 881 void setSize(unsigned Level, unsigned Size) { 882 path[Level].size = Size; 883 if (Level) 884 subtree(Level - 1).setSize(Size); 885 } 886 887 /// setRoot - Clear the path and set a new root node. 888 /// @param Node New root node. 889 /// @param Size New root size. 890 /// @param Offset Offset into root node. 891 void setRoot(void *Node, unsigned Size, unsigned Offset) { 892 path.clear(); 893 path.push_back(Entry(Node, Size, Offset)); 894 } 895 896 /// replaceRoot - Replace the current root node with two new entries after the 897 /// tree height has increased. 898 /// @param Root The new root node. 899 /// @param Size Number of entries in the new root. 900 /// @param Offsets Offsets into the root and first branch nodes. 901 void replaceRoot(void *Root, unsigned Size, IdxPair Offsets); 902 903 /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 904 /// @param Level Get the sibling to node(Level). 905 /// @return Left sibling, or NodeRef(). 906 NodeRef getLeftSibling(unsigned Level) const; 907 908 /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level 909 /// unaltered. 910 /// @param Level Move node(Level). 911 void moveLeft(unsigned Level); 912 913 /// fillLeft - Grow path to Height by taking leftmost branches. 914 /// @param Height The target height. 915 void fillLeft(unsigned Height) { 916 while (height() < Height) 917 push(subtree(height()), 0); 918 } 919 920 /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 921 /// @param Level Get the sinbling to node(Level). 922 /// @return Left sibling, or NodeRef(). 923 NodeRef getRightSibling(unsigned Level) const; 924 925 /// moveRight - Move path to the left sibling at Level. Leave nodes below 926 /// Level unaltered. 927 /// @param Level Move node(Level). 928 void moveRight(unsigned Level); 929 930 /// atBegin - Return true if path is at begin(). 931 bool atBegin() const { 932 for (unsigned i = 0, e = path.size(); i != e; ++i) 933 if (path[i].offset != 0) 934 return false; 935 return true; 936 } 937 938 /// atLastBranch - Return true if the path is at the last branch of the node 939 /// at Level. 940 /// @param Level Node to examine. 941 bool atLastBranch(unsigned Level) const { 942 return path[Level].offset == path[Level].size - 1; 943 } 944 945 /// legalizeForInsert - Prepare the path for an insertion at Level. When the 946 /// path is at end(), node(Level) may not be a legal node. legalizeForInsert 947 /// ensures that node(Level) is real by moving back to the last node at Level, 948 /// and setting offset(Level) to size(Level) if required. 949 /// @param Level The level where an insertion is about to take place. 950 void legalizeForInsert(unsigned Level) { 951 if (valid()) 952 return; 953 moveLeft(Level); 954 ++path[Level].offset; 955 } 956 957#ifndef NDEBUG 958 void dump() const { 959 for (unsigned l = 0, e = path.size(); l != e; ++l) 960 errs() << l << ": " << path[l].node << ' ' << path[l].size << ' ' 961 << path[l].offset << '\n'; 962 } 963#endif 964}; 965 966} // namespace IntervalMapImpl 967 968 969//===----------------------------------------------------------------------===// 970//--- IntervalMap ----// 971//===----------------------------------------------------------------------===// 972 973template <typename KeyT, typename ValT, 974 unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize, 975 typename Traits = IntervalMapInfo<KeyT> > 976class IntervalMap { 977 typedef IntervalMapImpl::NodeSizer<KeyT, ValT> Sizer; 978 typedef IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits> Leaf; 979 typedef IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits> 980 Branch; 981 typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf; 982 typedef IntervalMapImpl::IdxPair IdxPair; 983 984 // The RootLeaf capacity is given as a template parameter. We must compute the 985 // corresponding RootBranch capacity. 986 enum { 987 DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) / 988 (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)), 989 RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1 990 }; 991 992 typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits> 993 RootBranch; 994 995 // When branched, we store a global start key as well as the branch node. 996 struct RootBranchData { 997 KeyT start; 998 RootBranch node; 999 }; 1000 1001 enum { 1002 RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ? 1003 sizeof(RootBranchData) : sizeof(RootLeaf) 1004 }; 1005 1006public: 1007 typedef typename Sizer::Allocator Allocator; 1008 1009private: 1010 // The root data is either a RootLeaf or a RootBranchData instance. 1011 // We can't put them in a union since C++03 doesn't allow non-trivial 1012 // constructors in unions. 1013 // Instead, we use a char array with pointer alignment. The alignment is 1014 // ensured by the allocator member in the class, but still verified in the 1015 // constructor. We don't support keys or values that are more aligned than a 1016 // pointer. 1017 char data[RootDataSize]; 1018 1019 // Tree height. 1020 // 0: Leaves in root. 1021 // 1: Root points to leaf. 1022 // 2: root->branch->leaf ... 1023 unsigned height; 1024 1025 // Number of entries in the root node. 1026 unsigned rootSize; 1027 1028 // Allocator used for creating external nodes. 1029 Allocator &allocator; 1030 1031 /// dataAs - Represent data as a node type without breaking aliasing rules. 1032 template <typename T> 1033 T &dataAs() const { 1034 union { 1035 const char *d; 1036 T *t; 1037 } u; 1038 u.d = data; 1039 return *u.t; 1040 } 1041 1042 const RootLeaf &rootLeaf() const { 1043 assert(!branched() && "Cannot acces leaf data in branched root"); 1044 return dataAs<RootLeaf>(); 1045 } 1046 RootLeaf &rootLeaf() { 1047 assert(!branched() && "Cannot acces leaf data in branched root"); 1048 return dataAs<RootLeaf>(); 1049 } 1050 RootBranchData &rootBranchData() const { 1051 assert(branched() && "Cannot access branch data in non-branched root"); 1052 return dataAs<RootBranchData>(); 1053 } 1054 RootBranchData &rootBranchData() { 1055 assert(branched() && "Cannot access branch data in non-branched root"); 1056 return dataAs<RootBranchData>(); 1057 } 1058 const RootBranch &rootBranch() const { return rootBranchData().node; } 1059 RootBranch &rootBranch() { return rootBranchData().node; } 1060 KeyT rootBranchStart() const { return rootBranchData().start; } 1061 KeyT &rootBranchStart() { return rootBranchData().start; } 1062 1063 template <typename NodeT> NodeT *newNode() { 1064 return new(allocator.template Allocate<NodeT>()) NodeT(); 1065 } 1066 1067 template <typename NodeT> void deleteNode(NodeT *P) { 1068 P->~NodeT(); 1069 allocator.Deallocate(P); 1070 } 1071 1072 IdxPair branchRoot(unsigned Position); 1073 IdxPair splitRoot(unsigned Position); 1074 1075 void switchRootToBranch() { 1076 rootLeaf().~RootLeaf(); 1077 height = 1; 1078 new (&rootBranchData()) RootBranchData(); 1079 } 1080 1081 void switchRootToLeaf() { 1082 rootBranchData().~RootBranchData(); 1083 height = 0; 1084 new(&rootLeaf()) RootLeaf(); 1085 } 1086 1087 bool branched() const { return height > 0; } 1088 1089 ValT treeSafeLookup(KeyT x, ValT NotFound) const; 1090 void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, 1091 unsigned Level)); 1092 void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level); 1093 1094public: 1095 explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) { 1096 assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 && 1097 "Insufficient alignment"); 1098 new(&rootLeaf()) RootLeaf(); 1099 } 1100 1101 ~IntervalMap() { 1102 clear(); 1103 rootLeaf().~RootLeaf(); 1104 } 1105 1106 /// empty - Return true when no intervals are mapped. 1107 bool empty() const { 1108 return rootSize == 0; 1109 } 1110 1111 /// start - Return the smallest mapped key in a non-empty map. 1112 KeyT start() const { 1113 assert(!empty() && "Empty IntervalMap has no start"); 1114 return !branched() ? rootLeaf().start(0) : rootBranchStart(); 1115 } 1116 1117 /// stop - Return the largest mapped key in a non-empty map. 1118 KeyT stop() const { 1119 assert(!empty() && "Empty IntervalMap has no stop"); 1120 return !branched() ? rootLeaf().stop(rootSize - 1) : 1121 rootBranch().stop(rootSize - 1); 1122 } 1123 1124 /// lookup - Return the mapped value at x or NotFound. 1125 ValT lookup(KeyT x, ValT NotFound = ValT()) const { 1126 if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x)) 1127 return NotFound; 1128 return branched() ? treeSafeLookup(x, NotFound) : 1129 rootLeaf().safeLookup(x, NotFound); 1130 } 1131 1132 /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals. 1133 /// It is assumed that no key in the interval is mapped to another value, but 1134 /// overlapping intervals already mapped to y will be coalesced. 1135 void insert(KeyT a, KeyT b, ValT y) { 1136 if (branched() || rootSize == RootLeaf::Capacity) 1137 return find(a).insert(a, b, y); 1138 1139 // Easy insert into root leaf. 1140 unsigned p = rootLeaf().findFrom(0, rootSize, a); 1141 rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y).second; 1142 } 1143 1144 /// clear - Remove all entries. 1145 void clear(); 1146 1147 class const_iterator; 1148 class iterator; 1149 friend class const_iterator; 1150 friend class iterator; 1151 1152 const_iterator begin() const { 1153 iterator I(*this); 1154 I.goToBegin(); 1155 return I; 1156 } 1157 1158 iterator begin() { 1159 iterator I(*this); 1160 I.goToBegin(); 1161 return I; 1162 } 1163 1164 const_iterator end() const { 1165 iterator I(*this); 1166 I.goToEnd(); 1167 return I; 1168 } 1169 1170 iterator end() { 1171 iterator I(*this); 1172 I.goToEnd(); 1173 return I; 1174 } 1175 1176 /// find - Return an iterator pointing to the first interval ending at or 1177 /// after x, or end(). 1178 const_iterator find(KeyT x) const { 1179 iterator I(*this); 1180 I.find(x); 1181 return I; 1182 } 1183 1184 iterator find(KeyT x) { 1185 iterator I(*this); 1186 I.find(x); 1187 return I; 1188 } 1189 1190#ifndef NDEBUG 1191 raw_ostream *OS; 1192 void dump(); 1193 void dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height); 1194#endif 1195}; 1196 1197/// treeSafeLookup - Return the mapped value at x or NotFound, assuming a 1198/// branched root. 1199template <typename KeyT, typename ValT, unsigned N, typename Traits> 1200ValT IntervalMap<KeyT, ValT, N, Traits>:: 1201treeSafeLookup(KeyT x, ValT NotFound) const { 1202 assert(branched() && "treeLookup assumes a branched root"); 1203 1204 IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x); 1205 for (unsigned h = height-1; h; --h) 1206 NR = NR.get<Branch>().safeLookup(x); 1207 return NR.get<Leaf>().safeLookup(x, NotFound); 1208} 1209 1210 1211// branchRoot - Switch from a leaf root to a branched root. 1212// Return the new (root offset, node offset) corresponding to Position. 1213template <typename KeyT, typename ValT, unsigned N, typename Traits> 1214IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 1215branchRoot(unsigned Position) { 1216 using namespace IntervalMapImpl; 1217 // How many external leaf nodes to hold RootLeaf+1? 1218 const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1; 1219 1220 // Compute element distribution among new nodes. 1221 unsigned size[Nodes]; 1222 IdxPair NewOffset(0, Position); 1223 1224 // Is is very common for the root node to be smaller than external nodes. 1225 if (Nodes == 1) 1226 size[0] = rootSize; 1227 else 1228 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, size, 1229 Position, true); 1230 1231 // Allocate new nodes. 1232 unsigned pos = 0; 1233 NodeRef node[Nodes]; 1234 for (unsigned n = 0; n != Nodes; ++n) { 1235 Leaf *L = newNode<Leaf>(); 1236 L->copy(rootLeaf(), pos, 0, size[n]); 1237 node[n] = NodeRef(L, size[n]); 1238 pos += size[n]; 1239 } 1240 1241 // Destroy the old leaf node, construct branch node instead. 1242 switchRootToBranch(); 1243 for (unsigned n = 0; n != Nodes; ++n) { 1244 rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1); 1245 rootBranch().subtree(n) = node[n]; 1246 } 1247 rootBranchStart() = node[0].template get<Leaf>().start(0); 1248 rootSize = Nodes; 1249 return NewOffset; 1250} 1251 1252// splitRoot - Split the current BranchRoot into multiple Branch nodes. 1253// Return the new (root offset, node offset) corresponding to Position. 1254template <typename KeyT, typename ValT, unsigned N, typename Traits> 1255IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 1256splitRoot(unsigned Position) { 1257 using namespace IntervalMapImpl; 1258 // How many external leaf nodes to hold RootBranch+1? 1259 const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1; 1260 1261 // Compute element distribution among new nodes. 1262 unsigned Size[Nodes]; 1263 IdxPair NewOffset(0, Position); 1264 1265 // Is is very common for the root node to be smaller than external nodes. 1266 if (Nodes == 1) 1267 Size[0] = rootSize; 1268 else 1269 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, Size, 1270 Position, true); 1271 1272 // Allocate new nodes. 1273 unsigned Pos = 0; 1274 NodeRef Node[Nodes]; 1275 for (unsigned n = 0; n != Nodes; ++n) { 1276 Branch *B = newNode<Branch>(); 1277 B->copy(rootBranch(), Pos, 0, Size[n]); 1278 Node[n] = NodeRef(B, Size[n]); 1279 Pos += Size[n]; 1280 } 1281 1282 for (unsigned n = 0; n != Nodes; ++n) { 1283 rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1); 1284 rootBranch().subtree(n) = Node[n]; 1285 } 1286 rootSize = Nodes; 1287 ++height; 1288 return NewOffset; 1289} 1290 1291/// visitNodes - Visit each external node. 1292template <typename KeyT, typename ValT, unsigned N, typename Traits> 1293void IntervalMap<KeyT, ValT, N, Traits>:: 1294visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) { 1295 if (!branched()) 1296 return; 1297 SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs; 1298 1299 // Collect level 0 nodes from the root. 1300 for (unsigned i = 0; i != rootSize; ++i) 1301 Refs.push_back(rootBranch().subtree(i)); 1302 1303 // Visit all branch nodes. 1304 for (unsigned h = height - 1; h; --h) { 1305 for (unsigned i = 0, e = Refs.size(); i != e; ++i) { 1306 for (unsigned j = 0, s = Refs[i].size(); j != s; ++j) 1307 NextRefs.push_back(Refs[i].subtree(j)); 1308 (this->*f)(Refs[i], h); 1309 } 1310 Refs.clear(); 1311 Refs.swap(NextRefs); 1312 } 1313 1314 // Visit all leaf nodes. 1315 for (unsigned i = 0, e = Refs.size(); i != e; ++i) 1316 (this->*f)(Refs[i], 0); 1317} 1318 1319template <typename KeyT, typename ValT, unsigned N, typename Traits> 1320void IntervalMap<KeyT, ValT, N, Traits>:: 1321deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) { 1322 if (Level) 1323 deleteNode(&Node.get<Branch>()); 1324 else 1325 deleteNode(&Node.get<Leaf>()); 1326} 1327 1328template <typename KeyT, typename ValT, unsigned N, typename Traits> 1329void IntervalMap<KeyT, ValT, N, Traits>:: 1330clear() { 1331 if (branched()) { 1332 visitNodes(&IntervalMap::deleteNode); 1333 switchRootToLeaf(); 1334 } 1335 rootSize = 0; 1336} 1337 1338#ifndef NDEBUG 1339template <typename KeyT, typename ValT, unsigned N, typename Traits> 1340void IntervalMap<KeyT, ValT, N, Traits>:: 1341dumpNode(IntervalMapImpl::NodeRef Node, unsigned Height) { 1342 if (Height) 1343 Node.get<Branch>().dump(*OS, Node.size()); 1344 else 1345 Node.get<Leaf>().dump(*OS, Node.size()); 1346} 1347 1348template <typename KeyT, typename ValT, unsigned N, typename Traits> 1349void IntervalMap<KeyT, ValT, N, Traits>:: 1350dump() { 1351 std::string errors; 1352 raw_fd_ostream ofs("tree.dot", errors); 1353 OS = &ofs; 1354 ofs << "digraph {\n"; 1355 if (branched()) 1356 rootBranch().dump(ofs, rootSize); 1357 else 1358 rootLeaf().dump(ofs, rootSize); 1359 visitNodes(&IntervalMap::dumpNode); 1360 ofs << "}\n"; 1361} 1362#endif 1363 1364//===----------------------------------------------------------------------===// 1365//--- const_iterator ----// 1366//===----------------------------------------------------------------------===// 1367 1368template <typename KeyT, typename ValT, unsigned N, typename Traits> 1369class IntervalMap<KeyT, ValT, N, Traits>::const_iterator : 1370 public std::iterator<std::bidirectional_iterator_tag, ValT> { 1371protected: 1372 friend class IntervalMap; 1373 1374 // The map referred to. 1375 IntervalMap *map; 1376 1377 // We store a full path from the root to the current position. 1378 // The path may be partially filled, but never between iterator calls. 1379 IntervalMapImpl::Path path; 1380 1381 explicit const_iterator(IntervalMap &map) : map(&map) {} 1382 1383 bool branched() const { 1384 assert(map && "Invalid iterator"); 1385 return map->branched(); 1386 } 1387 1388 void setRoot(unsigned Offset) { 1389 if (branched()) 1390 path.setRoot(&map->rootBranch(), map->rootSize, Offset); 1391 else 1392 path.setRoot(&map->rootLeaf(), map->rootSize, Offset); 1393 } 1394 1395 void pathFillFind(KeyT x); 1396 void treeFind(KeyT x); 1397 void treeAdvanceTo(KeyT x); 1398 1399public: 1400 /// const_iterator - Create an iterator that isn't pointing anywhere. 1401 const_iterator() : map(0) {} 1402 1403 /// valid - Return true if the current position is valid, false for end(). 1404 bool valid() const { return path.valid(); } 1405 1406 /// start - Return the beginning of the current interval. 1407 const KeyT &start() const { 1408 assert(valid() && "Cannot access invalid iterator"); 1409 return branched() ? path.leaf<Leaf>().start(path.leafOffset()) : 1410 path.leaf<RootLeaf>().start(path.leafOffset()); 1411 } 1412 1413 /// stop - Return the end of the current interval. 1414 const KeyT &stop() const { 1415 assert(valid() && "Cannot access invalid iterator"); 1416 return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) : 1417 path.leaf<RootLeaf>().stop(path.leafOffset()); 1418 } 1419 1420 /// value - Return the mapped value at the current interval. 1421 const ValT &value() const { 1422 assert(valid() && "Cannot access invalid iterator"); 1423 return branched() ? path.leaf<Leaf>().value(path.leafOffset()) : 1424 path.leaf<RootLeaf>().value(path.leafOffset()); 1425 } 1426 1427 const ValT &operator*() const { 1428 return value(); 1429 } 1430 1431 bool operator==(const const_iterator &RHS) const { 1432 assert(map == RHS.map && "Cannot compare iterators from different maps"); 1433 if (!valid()) 1434 return !RHS.valid(); 1435 if (path.leafOffset() != RHS.path.leafOffset()) 1436 return false; 1437 return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>(); 1438 } 1439 1440 bool operator!=(const const_iterator &RHS) const { 1441 return !operator==(RHS); 1442 } 1443 1444 /// goToBegin - Move to the first interval in map. 1445 void goToBegin() { 1446 setRoot(0); 1447 if (branched()) 1448 path.fillLeft(map->height); 1449 } 1450 1451 /// goToEnd - Move beyond the last interval in map. 1452 void goToEnd() { 1453 setRoot(map->rootSize); 1454 } 1455 1456 /// preincrement - move to the next interval. 1457 const_iterator &operator++() { 1458 assert(valid() && "Cannot increment end()"); 1459 if (++path.leafOffset() == path.leafSize() && branched()) 1460 path.moveRight(map->height); 1461 return *this; 1462 } 1463 1464 /// postincrement - Dont do that! 1465 const_iterator operator++(int) { 1466 const_iterator tmp = *this; 1467 operator++(); 1468 return tmp; 1469 } 1470 1471 /// predecrement - move to the previous interval. 1472 const_iterator &operator--() { 1473 if (path.leafOffset() && (valid() || !branched())) 1474 --path.leafOffset(); 1475 else 1476 path.moveLeft(map->height); 1477 return *this; 1478 } 1479 1480 /// postdecrement - Dont do that! 1481 const_iterator operator--(int) { 1482 const_iterator tmp = *this; 1483 operator--(); 1484 return tmp; 1485 } 1486 1487 /// find - Move to the first interval with stop >= x, or end(). 1488 /// This is a full search from the root, the current position is ignored. 1489 void find(KeyT x) { 1490 if (branched()) 1491 treeFind(x); 1492 else 1493 setRoot(map->rootLeaf().findFrom(0, map->rootSize, x)); 1494 } 1495 1496 /// advanceTo - Move to the first interval with stop >= x, or end(). 1497 /// The search is started from the current position, and no earlier positions 1498 /// can be found. This is much faster than find() for small moves. 1499 void advanceTo(KeyT x) { 1500 if (branched()) 1501 treeAdvanceTo(x); 1502 else 1503 path.leafOffset() = 1504 map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x); 1505 } 1506 1507}; 1508 1509/// pathFillFind - Complete path by searching for x. 1510/// @param x Key to search for. 1511template <typename KeyT, typename ValT, unsigned N, typename Traits> 1512void IntervalMap<KeyT, ValT, N, Traits>:: 1513const_iterator::pathFillFind(KeyT x) { 1514 IntervalMapImpl::NodeRef NR = path.subtree(path.height()); 1515 for (unsigned i = map->height - path.height() - 1; i; --i) { 1516 unsigned p = NR.get<Branch>().safeFind(0, x); 1517 path.push(NR, p); 1518 NR = NR.subtree(p); 1519 } 1520 path.push(NR, NR.get<Leaf>().safeFind(0, x)); 1521} 1522 1523/// treeFind - Find in a branched tree. 1524/// @param x Key to search for. 1525template <typename KeyT, typename ValT, unsigned N, typename Traits> 1526void IntervalMap<KeyT, ValT, N, Traits>:: 1527const_iterator::treeFind(KeyT x) { 1528 setRoot(map->rootBranch().findFrom(0, map->rootSize, x)); 1529 if (valid()) 1530 pathFillFind(x); 1531} 1532 1533/// treeAdvanceTo - Find position after the current one. 1534/// @param x Key to search for. 1535template <typename KeyT, typename ValT, unsigned N, typename Traits> 1536void IntervalMap<KeyT, ValT, N, Traits>:: 1537const_iterator::treeAdvanceTo(KeyT x) { 1538 // Can we stay on the same leaf node? 1539 if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) { 1540 path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x); 1541 return; 1542 } 1543 1544 // Drop the current leaf. 1545 path.pop(); 1546 1547 // Search towards the root for a usable subtree. 1548 if (path.height()) { 1549 for (unsigned l = path.height() - 1; l; --l) { 1550 if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) { 1551 // The branch node at l+1 is usable 1552 path.offset(l + 1) = 1553 path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x); 1554 return pathFillFind(x); 1555 } 1556 path.pop(); 1557 } 1558 // Is the level-1 Branch usable? 1559 if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) { 1560 path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x); 1561 return pathFillFind(x); 1562 } 1563 } 1564 1565 // We reached the root. 1566 setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x)); 1567 if (valid()) 1568 pathFillFind(x); 1569} 1570 1571//===----------------------------------------------------------------------===// 1572//--- iterator ----// 1573//===----------------------------------------------------------------------===// 1574 1575template <typename KeyT, typename ValT, unsigned N, typename Traits> 1576class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator { 1577 friend class IntervalMap; 1578 typedef IntervalMapImpl::IdxPair IdxPair; 1579 1580 explicit iterator(IntervalMap &map) : const_iterator(map) {} 1581 1582 void setNodeStop(unsigned Level, KeyT Stop); 1583 bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop); 1584 template <typename NodeT> bool overflow(unsigned Level); 1585 void treeInsert(KeyT a, KeyT b, ValT y); 1586 void eraseNode(unsigned Level); 1587 void treeErase(bool UpdateRoot = true); 1588public: 1589 /// iterator - Create null iterator. 1590 iterator() {} 1591 1592 /// insert - Insert mapping [a;b] -> y before the current position. 1593 void insert(KeyT a, KeyT b, ValT y); 1594 1595 /// erase - Erase the current interval. 1596 void erase(); 1597 1598 iterator &operator++() { 1599 const_iterator::operator++(); 1600 return *this; 1601 } 1602 1603 iterator operator++(int) { 1604 iterator tmp = *this; 1605 operator++(); 1606 return tmp; 1607 } 1608 1609 iterator &operator--() { 1610 const_iterator::operator--(); 1611 return *this; 1612 } 1613 1614 iterator operator--(int) { 1615 iterator tmp = *this; 1616 operator--(); 1617 return tmp; 1618 } 1619 1620}; 1621 1622/// setNodeStop - Update the stop key of the current node at level and above. 1623template <typename KeyT, typename ValT, unsigned N, typename Traits> 1624void IntervalMap<KeyT, ValT, N, Traits>:: 1625iterator::setNodeStop(unsigned Level, KeyT Stop) { 1626 // There are no references to the root node, so nothing to update. 1627 if (!Level) 1628 return; 1629 IntervalMapImpl::Path &P = this->path; 1630 // Update nodes pointing to the current node. 1631 while (--Level) { 1632 P.node<Branch>(Level).stop(P.offset(Level)) = Stop; 1633 if (!P.atLastBranch(Level)) 1634 return; 1635 } 1636 // Update root separately since it has a different layout. 1637 P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop; 1638} 1639 1640/// insertNode - insert a node before the current path at level. 1641/// Leave the current path pointing at the new node. 1642/// @param Level path index of the node to be inserted. 1643/// @param Node The node to be inserted. 1644/// @param Stop The last index in the new node. 1645/// @return True if the tree height was increased. 1646template <typename KeyT, typename ValT, unsigned N, typename Traits> 1647bool IntervalMap<KeyT, ValT, N, Traits>:: 1648iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) { 1649 assert(Level && "Cannot insert next to the root"); 1650 bool SplitRoot = false; 1651 IntervalMap &IM = *this->map; 1652 IntervalMapImpl::Path &P = this->path; 1653 1654 if (Level == 1) { 1655 // Insert into the root branch node. 1656 if (IM.rootSize < RootBranch::Capacity) { 1657 IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop); 1658 P.setSize(0, ++IM.rootSize); 1659 P.reset(Level); 1660 return SplitRoot; 1661 } 1662 1663 // We need to split the root while keeping our position. 1664 SplitRoot = true; 1665 IdxPair Offset = IM.splitRoot(P.offset(0)); 1666 P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1667 1668 // Fall through to insert at the new higher level. 1669 ++Level; 1670 } 1671 1672 // When inserting before end(), make sure we have a valid path. 1673 P.legalizeForInsert(--Level); 1674 1675 // Insert into the branch node at Level-1. 1676 if (P.size(Level) == Branch::Capacity) { 1677 // Branch node is full, handle handle the overflow. 1678 assert(!SplitRoot && "Cannot overflow after splitting the root"); 1679 SplitRoot = overflow<Branch>(Level); 1680 Level += SplitRoot; 1681 } 1682 P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop); 1683 P.setSize(Level, P.size(Level) + 1); 1684 if (P.atLastBranch(Level)) 1685 setNodeStop(Level, Stop); 1686 P.reset(Level + 1); 1687 return SplitRoot; 1688} 1689 1690// insert 1691template <typename KeyT, typename ValT, unsigned N, typename Traits> 1692void IntervalMap<KeyT, ValT, N, Traits>:: 1693iterator::insert(KeyT a, KeyT b, ValT y) { 1694 if (this->branched()) 1695 return treeInsert(a, b, y); 1696 IntervalMap &IM = *this->map; 1697 IntervalMapImpl::Path &P = this->path; 1698 1699 // Try simple root leaf insert. 1700 IdxPair IP = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y); 1701 1702 // Was the root node insert successful? 1703 if (IP.second <= RootLeaf::Capacity) { 1704 P.leafOffset() = IP.first; 1705 P.setSize(0, IM.rootSize = IP.second); 1706 return; 1707 } 1708 1709 // Root leaf node is full, we must branch. 1710 IdxPair Offset = IM.branchRoot(P.leafOffset()); 1711 P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1712 1713 // Now it fits in the new leaf. 1714 treeInsert(a, b, y); 1715} 1716 1717 1718template <typename KeyT, typename ValT, unsigned N, typename Traits> 1719void IntervalMap<KeyT, ValT, N, Traits>:: 1720iterator::treeInsert(KeyT a, KeyT b, ValT y) { 1721 using namespace IntervalMapImpl; 1722 IntervalMap &IM = *this->map; 1723 Path &P = this->path; 1724 1725 // Check if this insertion will extend the node to the left. 1726 if (P.valid() && P.leafOffset() == 0 && 1727 Traits::startLess(a, P.leaf<Leaf>().start(0))) { 1728 // Node is growing to the left, will it affect a left sibling node? 1729 if (NodeRef Sib = P.getLeftSibling(IM.height)) { 1730 Leaf &SibLeaf = Sib.get<Leaf>(); 1731 unsigned SibOfs = Sib.size() - 1; 1732 if (SibLeaf.value(SibOfs) == y && 1733 Traits::adjacent(SibLeaf.stop(SibOfs), a)) { 1734 // This insertion will coalesce with the last entry in SibLeaf. We can 1735 // handle it in two ways: 1736 // 1. Extend SibLeaf.stop to b and be done, or 1737 // 2. Extend a to SibLeaf, erase the SibLeaf entry and continue. 1738 // We prefer 1., but need 2 when coalescing to the right as well. 1739 Leaf &CurLeaf = P.leaf<Leaf>(); 1740 P.moveLeft(IM.height); 1741 if (Traits::stopLess(b, CurLeaf.start(0)) && 1742 (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) { 1743 // Easy, just extend SibLeaf and we're done. 1744 setNodeStop(IM.height, SibLeaf.stop(SibOfs) = b); 1745 return; 1746 } else { 1747 // We have both left and right coalescing. Erase the old SibLeaf entry 1748 // and continue inserting the larger interval. 1749 a = SibLeaf.start(SibOfs); 1750 treeErase(/* UpdateRoot= */false); 1751 } 1752 } 1753 } else { 1754 // No left sibling means we are at begin(). Update cached bound. 1755 IM.rootBranchStart() = a; 1756 } 1757 } 1758 1759 P.legalizeForInsert(IM.height); 1760 IdxPair IP = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y); 1761 1762 // Leaf insertion unsuccessful? Overflow and try again. 1763 if (IP.second > Leaf::Capacity) { 1764 overflow<Leaf>(IM.height); 1765 IP = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y); 1766 assert(IP.second <= Leaf::Capacity && "overflow() didn't make room"); 1767 } 1768 1769 // Inserted, update offset and leaf size. 1770 P.leafOffset() = IP.first; 1771 P.setSize(IM.height, IP.second); 1772 1773 // Insert was the last node entry, update stops. 1774 if (IP.first == IP.second - 1) 1775 setNodeStop(IM.height, P.leaf<Leaf>().stop(IP.first)); 1776} 1777 1778/// erase - erase the current interval and move to the next position. 1779template <typename KeyT, typename ValT, unsigned N, typename Traits> 1780void IntervalMap<KeyT, ValT, N, Traits>:: 1781iterator::erase() { 1782 IntervalMap &IM = *this->map; 1783 IntervalMapImpl::Path &P = this->path; 1784 assert(P.valid() && "Cannot erase end()"); 1785 if (this->branched()) 1786 return treeErase(); 1787 IM.rootLeaf().erase(P.leafOffset(), IM.rootSize); 1788 P.setSize(0, --IM.rootSize); 1789} 1790 1791/// treeErase - erase() for a branched tree. 1792template <typename KeyT, typename ValT, unsigned N, typename Traits> 1793void IntervalMap<KeyT, ValT, N, Traits>:: 1794iterator::treeErase(bool UpdateRoot) { 1795 IntervalMap &IM = *this->map; 1796 IntervalMapImpl::Path &P = this->path; 1797 Leaf &Node = P.leaf<Leaf>(); 1798 1799 // Nodes are not allowed to become empty. 1800 if (P.leafSize() == 1) { 1801 IM.deleteNode(&Node); 1802 eraseNode(IM.height); 1803 // Update rootBranchStart if we erased begin(). 1804 if (UpdateRoot && IM.branched() && P.valid() && P.atBegin()) 1805 IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1806 return; 1807 } 1808 1809 // Erase current entry. 1810 Node.erase(P.leafOffset(), P.leafSize()); 1811 unsigned NewSize = P.leafSize() - 1; 1812 P.setSize(IM.height, NewSize); 1813 // When we erase the last entry, update stop and move to a legal position. 1814 if (P.leafOffset() == NewSize) { 1815 setNodeStop(IM.height, Node.stop(NewSize - 1)); 1816 P.moveRight(IM.height); 1817 } else if (UpdateRoot && P.atBegin()) 1818 IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1819} 1820 1821/// eraseNode - Erase the current node at Level from its parent and move path to 1822/// the first entry of the next sibling node. 1823/// The node must be deallocated by the caller. 1824/// @param Level 1..height, the root node cannot be erased. 1825template <typename KeyT, typename ValT, unsigned N, typename Traits> 1826void IntervalMap<KeyT, ValT, N, Traits>:: 1827iterator::eraseNode(unsigned Level) { 1828 assert(Level && "Cannot erase root node"); 1829 IntervalMap &IM = *this->map; 1830 IntervalMapImpl::Path &P = this->path; 1831 1832 if (--Level == 0) { 1833 IM.rootBranch().erase(P.offset(0), IM.rootSize); 1834 P.setSize(0, --IM.rootSize); 1835 // If this cleared the root, switch to height=0. 1836 if (IM.empty()) { 1837 IM.switchRootToLeaf(); 1838 this->setRoot(0); 1839 return; 1840 } 1841 } else { 1842 // Remove node ref from branch node at Level. 1843 Branch &Parent = P.node<Branch>(Level); 1844 if (P.size(Level) == 1) { 1845 // Branch node became empty, remove it recursively. 1846 IM.deleteNode(&Parent); 1847 eraseNode(Level); 1848 } else { 1849 // Branch node won't become empty. 1850 Parent.erase(P.offset(Level), P.size(Level)); 1851 unsigned NewSize = P.size(Level) - 1; 1852 P.setSize(Level, NewSize); 1853 // If we removed the last branch, update stop and move to a legal pos. 1854 if (P.offset(Level) == NewSize) { 1855 setNodeStop(Level, Parent.stop(NewSize - 1)); 1856 P.moveRight(Level); 1857 } 1858 } 1859 } 1860 // Update path cache for the new right sibling position. 1861 if (P.valid()) { 1862 P.reset(Level + 1); 1863 P.offset(Level + 1) = 0; 1864 } 1865} 1866 1867/// overflow - Distribute entries of the current node evenly among 1868/// its siblings and ensure that the current node is not full. 1869/// This may require allocating a new node. 1870/// @param NodeT The type of node at Level (Leaf or Branch). 1871/// @param Level path index of the overflowing node. 1872/// @return True when the tree height was changed. 1873template <typename KeyT, typename ValT, unsigned N, typename Traits> 1874template <typename NodeT> 1875bool IntervalMap<KeyT, ValT, N, Traits>:: 1876iterator::overflow(unsigned Level) { 1877 using namespace IntervalMapImpl; 1878 Path &P = this->path; 1879 unsigned CurSize[4]; 1880 NodeT *Node[4]; 1881 unsigned Nodes = 0; 1882 unsigned Elements = 0; 1883 unsigned Offset = P.offset(Level); 1884 1885 // Do we have a left sibling? 1886 NodeRef LeftSib = P.getLeftSibling(Level); 1887 if (LeftSib) { 1888 Offset += Elements = CurSize[Nodes] = LeftSib.size(); 1889 Node[Nodes++] = &LeftSib.get<NodeT>(); 1890 } 1891 1892 // Current node. 1893 Elements += CurSize[Nodes] = P.size(Level); 1894 Node[Nodes++] = &P.node<NodeT>(Level); 1895 1896 // Do we have a right sibling? 1897 NodeRef RightSib = P.getRightSibling(Level); 1898 if (RightSib) { 1899 Elements += CurSize[Nodes] = RightSib.size(); 1900 Node[Nodes++] = &RightSib.get<NodeT>(); 1901 } 1902 1903 // Do we need to allocate a new node? 1904 unsigned NewNode = 0; 1905 if (Elements + 1 > Nodes * NodeT::Capacity) { 1906 // Insert NewNode at the penultimate position, or after a single node. 1907 NewNode = Nodes == 1 ? 1 : Nodes - 1; 1908 CurSize[Nodes] = CurSize[NewNode]; 1909 Node[Nodes] = Node[NewNode]; 1910 CurSize[NewNode] = 0; 1911 Node[NewNode] = this->map->newNode<NodeT>(); 1912 ++Nodes; 1913 } 1914 1915 // Compute the new element distribution. 1916 unsigned NewSize[4]; 1917 IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity, 1918 CurSize, NewSize, Offset, true); 1919 adjustSiblingSizes(Node, Nodes, CurSize, NewSize); 1920 1921 // Move current location to the leftmost node. 1922 if (LeftSib) 1923 P.moveLeft(Level); 1924 1925 // Elements have been rearranged, now update node sizes and stops. 1926 bool SplitRoot = false; 1927 unsigned Pos = 0; 1928 for (;;) { 1929 KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1); 1930 if (NewNode && Pos == NewNode) { 1931 SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop); 1932 Level += SplitRoot; 1933 } else { 1934 P.setSize(Level, NewSize[Pos]); 1935 setNodeStop(Level, Stop); 1936 } 1937 if (Pos + 1 == Nodes) 1938 break; 1939 P.moveRight(Level); 1940 ++Pos; 1941 } 1942 1943 // Where was I? Find NewOffset. 1944 while(Pos != NewOffset.first) { 1945 P.moveLeft(Level); 1946 --Pos; 1947 } 1948 P.offset(Level) = NewOffset.second; 1949 return SplitRoot; 1950} 1951 1952} // namespace llvm 1953 1954#endif 1955