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