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