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