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