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