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