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