18dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===// 28dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 38dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The LLVM Compiler Infrastructure 48dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 58dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 68dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// License. See LICENSE.TXT for details. 78dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 88dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 98dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// This file implements a coalescing interval map for small objects. 118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// KeyT objects are mapped to ValT objects. Intervals of keys that map to the 138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// same value are represented in a compressed form. 148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Iterators provide ordered access to the compressed intervals rather than the 168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// individual keys, and insert and erase operations use key intervals as well. 178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Like SmallVector, IntervalMap will store the first N intervals in the map 198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// object itself without any allocations. When space is exhausted it switches to 208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// a B+-tree representation with very small overhead for small key and value 218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// objects. 228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// A Traits class specifies how keys are compared. It also allows IntervalMap to 248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// work with both closed and half-open intervals. 258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Keys and values are not stored next to each other in a std::pair, so we don't 278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// provide such a value_type. Dereferencing iterators only returns the mapped 288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// value. The interval bounds are accessible through the start() and stop() 298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// iterator methods. 308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// IntervalMap is optimized for small key and value objects, 4 or 8 bytes each 328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// is the optimal size. For large objects use std::map instead. 338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Synopsis: 378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// template <typename KeyT, typename ValT, unsigned N, typename Traits> 398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// class IntervalMap { 408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// public: 418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// typedef KeyT key_type; 428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// typedef ValT mapped_type; 438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// typedef RecyclingAllocator<...> Allocator; 448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// class iterator; 458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// class const_iterator; 468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// explicit IntervalMap(Allocator&); 488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// ~IntervalMap(): 498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// bool empty() const; 518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// KeyT start() const; 528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// KeyT stop() const; 538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// ValT lookup(KeyT x, Value NotFound = Value()) const; 548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// const_iterator begin() const; 568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// const_iterator end() const; 578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// iterator begin(); 588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// iterator end(); 598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// const_iterator find(KeyT x) const; 608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// iterator find(KeyT x); 618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// void insert(KeyT a, KeyT b, ValT y); 638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// void clear(); 648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// }; 658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// template <typename KeyT, typename ValT, unsigned N, typename Traits> 678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// class IntervalMap::const_iterator : 688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// public std::iterator<std::bidirectional_iterator_tag, ValT> { 698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// public: 708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// bool operator==(const const_iterator &) const; 718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// bool operator!=(const const_iterator &) const; 728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// bool valid() const; 738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// const KeyT &start() const; 758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// const KeyT &stop() const; 768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// const ValT &value() const; 778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// const ValT &operator*() const; 788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// const ValT *operator->() const; 798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// const_iterator &operator++(); 818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// const_iterator &operator++(int); 828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// const_iterator &operator--(); 838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// const_iterator &operator--(int); 848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// void goToBegin(); 858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// void goToEnd(); 868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// void find(KeyT x); 878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// void advanceTo(KeyT x); 888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// }; 898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// template <typename KeyT, typename ValT, unsigned N, typename Traits> 918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// class IntervalMap::iterator : public const_iterator { 928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// public: 938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// void insert(KeyT a, KeyT b, Value y); 948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// void erase(); 958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// }; 968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#ifndef LLVM_ADT_INTERVALMAP_H 1008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#define LLVM_ADT_INTERVALMAP_H 1018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#include "llvm/ADT/PointerIntPair.h" 103255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/ADT/SmallVector.h" 1048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#include "llvm/Support/Allocator.h" 1058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#include "llvm/Support/RecyclingAllocator.h" 1068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#include <iterator> 1078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesennamespace llvm { 1098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//--- Key traits ---// 1138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The IntervalMap works with closed or half-open intervals. 1168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Adjacent intervals that map to the same value are coalesced. 1178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The IntervalMapInfo traits class is used to determine if a key is contained 1198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// in an interval, and if two intervals are adjacent so they can be coalesced. 1208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The provided implementation works for closed integer intervals, other keys 1218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// probably need a specialized version. 1228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x). 1248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// It is assumed that (a;b] half-open intervals are not used, only [a;b) is 1268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// allowed. This is so that stopLess(a, b) can be used to determine if two 1278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// intervals overlap. 1288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename T> 1328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenstruct IntervalMapInfo { 1338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// startLess - Return true if x is not in [a;b]. 1358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is x < a both for closed intervals and for [a;b) half-open intervals. 1368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen static inline bool startLess(const T &x, const T &a) { 1378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return x < a; 1388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// stopLess - Return true if x is not in [a;b]. 1418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals. 1428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen static inline bool stopLess(const T &b, const T &x) { 1438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return b < x; 1448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce. 1478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is a+1 == b for closed intervals, a == b for half-open intervals. 1488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen static inline bool adjacent(const T &a, const T &b) { 1498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return a+1 == b; 1508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 1538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 154edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruthtemplate <typename T> 155edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruthstruct IntervalMapHalfOpenInfo { 156edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth 157edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth /// startLess - Return true if x is not in [a;b). 158edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth static inline bool startLess(const T &x, const T &a) { 159edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth return x < a; 160edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth } 161edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth 162edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth /// stopLess - Return true if x is not in [a;b). 163edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth static inline bool stopLess(const T &b, const T &x) { 164edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth return b <= x; 165edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth } 166edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth 167edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth /// adjacent - Return true when the intervals [x;a) and [b;y) can coalesce. 168edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth static inline bool adjacent(const T &a, const T &b) { 169edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth return a == b; 170edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth } 171edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth 172edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth}; 173edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth 1748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// IntervalMapImpl - Namespace used for IntervalMap implementation details. 1758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// It should be considered private to the implementation. 1768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesennamespace IntervalMapImpl { 1778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Forward declarations. 1798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename, typename, unsigned, typename> class LeafNode; 1808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename, typename, unsigned, typename> class BranchNode; 1818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentypedef std::pair<unsigned,unsigned> IdxPair; 1838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 186bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::NodeBase ---// 1878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 189a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen// Both leaf and branch nodes store vectors of pairs. 190a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen// Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT). 1918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Keys and values are stored in separate arrays to avoid padding caused by 1938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// different object alignments. This also helps improve locality of reference 1948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// when searching the keys. 1958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The nodes don't know how many elements they contain - that information is 1978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// stored elsewhere. Omitting the size field prevents padding and allows a node 1988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// to fill the allocated cache lines completely. 1998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 2008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// These are typical key and value sizes, the node branching factor (N), and 2018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// wasted space when nodes are sized to fit in three cache lines (192 bytes): 2028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 203a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen// T1 T2 N Waste Used by 2048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4 4 24 0 Branch<4> (32-bit pointers) 205a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen// 8 4 16 0 Leaf<4,4>, Branch<4> 2068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 8 8 12 0 Leaf<4,8>, Branch<8> 2078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 16 4 9 12 Leaf<8,4> 2088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 16 8 8 0 Leaf<8,8> 2098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 2108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 2118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 212a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesentemplate <typename T1, typename T2, unsigned N> 2138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass NodeBase { 2148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 2158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen enum { Capacity = N }; 2168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 217a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen T1 first[N]; 218a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen T2 second[N]; 2198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 2208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// copy - Copy elements from another node. 22133fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Other Node elements are copied from. 2228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Beginning of the source range in other. 2238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param j Beginning of the destination range in this. 22433fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Count Number of elements to copy. 2258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen template <unsigned M> 226a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen void copy(const NodeBase<T1, T2, M> &Other, unsigned i, 2278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned j, unsigned Count) { 2288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i + Count <= M && "Invalid source range"); 2298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(j + Count <= N && "Invalid dest range"); 23008d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen for (unsigned e = i + Count; i != e; ++i, ++j) { 23108d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen first[j] = Other.first[i]; 23208d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen second[j] = Other.second[i]; 23308d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen } 2348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 23633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// moveLeft - Move elements to the left. 2378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Beginning of the source range. 2388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param j Beginning of the destination range. 23933fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Count Number of elements to copy. 24033fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen void moveLeft(unsigned i, unsigned j, unsigned Count) { 24133fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen assert(j <= i && "Use moveRight shift elements right"); 2428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen copy(*this, i, j, Count); 2438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 24533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// moveRight - Move elements to the right. 2468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Beginning of the source range. 2478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param j Beginning of the destination range. 24833fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Count Number of elements to copy. 24933fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen void moveRight(unsigned i, unsigned j, unsigned Count) { 25033fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen assert(i <= j && "Use moveLeft shift elements left"); 2518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(j + Count <= N && "Invalid range"); 25208d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen while (Count--) { 25308d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen first[j + Count] = first[i + Count]; 25408d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen second[j + Count] = second[i + Count]; 25508d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen } 2568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 2588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// erase - Erase elements [i;j). 2598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Beginning of the range to erase. 2608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param j End of the range. (Exclusive). 26133fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in node. 2628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void erase(unsigned i, unsigned j, unsigned Size) { 26333fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen moveLeft(j, i, Size - j); 2648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 266b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen /// erase - Erase element at i. 267b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen /// @param i Index of element to erase. 268b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen /// @param Size Number of elements in node. 269b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen void erase(unsigned i, unsigned Size) { 270b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen erase(i, i+1, Size); 271b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 272b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 2738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// shift - Shift elements [i;size) 1 position to the right. 2748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Beginning of the range to move. 27533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in node. 2768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void shift(unsigned i, unsigned Size) { 27733fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen moveRight(i, i + 1, Size - i); 2788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 28033fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// transferToLeftSib - Transfer elements to a left sibling node. 28133fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in this. 28233fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Sib Left sibling node. 28333fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param SSize Number of elements in sib. 28433fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Count Number of elements to transfer. 28533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, 28633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen unsigned Count) { 2878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Sib.copy(*this, 0, SSize, Count); 2888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen erase(0, Count, Size); 2898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 29133fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// transferToRightSib - Transfer elements to a right sibling node. 29233fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in this. 29333fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Sib Right sibling node. 29433fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param SSize Number of elements in sib. 29533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Count Number of elements to transfer. 29633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize, 29733fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen unsigned Count) { 29833fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen Sib.moveRight(0, Count, SSize); 2998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Sib.copy(*this, Size-Count, 0, Count); 3008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 3018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 30233fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// adjustFromLeftSib - Adjust the number if elements in this node by moving 3038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// elements to or from a left sibling node. 30433fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in this. 30533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Sib Right sibling node. 30633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param SSize Number of elements in sib. 30733fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Add The number of elements to add to this node, possibly < 0. 3088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return Number of elements added to this node, possibly negative. 30933fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) { 3108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Add > 0) { 3118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We want to grow, copy from sib. 3128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size); 31333fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen Sib.transferToRightSib(SSize, *this, Size, Count); 3148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return Count; 3158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } else { 3168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We want to shrink, copy to sib. 3178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize); 31833fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen transferToLeftSib(Size, Sib, SSize, Count); 3198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return -Count; 3208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 3218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 3228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 3238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 324bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen/// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes. 325bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Node Array of pointers to sibling nodes. 326bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Nodes Number of nodes. 327bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param CurSize Array of current node sizes, will be overwritten. 328bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param NewSize Array of desired node sizes. 329bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesentemplate <typename NodeT> 330bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesenvoid adjustSiblingSizes(NodeT *Node[], unsigned Nodes, 331bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen unsigned CurSize[], const unsigned NewSize[]) { 332bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen // Move elements right. 333bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen for (int n = Nodes - 1; n; --n) { 334b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (CurSize[n] == NewSize[n]) 335bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen continue; 336bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen for (int m = n - 1; m != -1; --m) { 337bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m], 338bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen NewSize[n] - CurSize[n]); 339bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen CurSize[m] -= d; 340bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen CurSize[n] += d; 341bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen // Keep going if the current node was exhausted. 342bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen if (CurSize[n] >= NewSize[n]) 343bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen break; 344bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen } 345bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen } 346bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen 347bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen if (Nodes == 0) 348bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen return; 349bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen 350bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen // Move elements left. 351bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen for (unsigned n = 0; n != Nodes - 1; ++n) { 352bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen if (CurSize[n] == NewSize[n]) 353bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen continue; 354bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen for (unsigned m = n + 1; m != Nodes; ++m) { 355bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n], 356bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen CurSize[n] - NewSize[n]); 357bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen CurSize[m] += d; 358bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen CurSize[n] -= d; 359bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen // Keep going if the current node was exhausted. 360bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen if (CurSize[n] >= NewSize[n]) 361bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen break; 362bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen } 363bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen } 364bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen 365bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen#ifndef NDEBUG 366bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen for (unsigned n = 0; n != Nodes; n++) 367bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle"); 368bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen#endif 369bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen} 370bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen 371bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen/// IntervalMapImpl::distribute - Compute a new distribution of node elements 372bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen/// after an overflow or underflow. Reserve space for a new element at Position, 373bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen/// and compute the node that will hold Position after redistributing node 374bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen/// elements. 375bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 376bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// It is required that 377bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 378bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// Elements == sum(CurSize), and 379bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// Elements + Grow <= Nodes * Capacity. 380bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 381bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// NewSize[] will be filled in such that: 382bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 383bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// sum(NewSize) == Elements, and 384bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// NewSize[i] <= Capacity. 385bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 386bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// The returned index is the node where Position will go, so: 387bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 388bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// sum(NewSize[0..idx-1]) <= Position 389bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// sum(NewSize[0..idx]) >= Position 390bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 391bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// The last equality, sum(NewSize[0..idx]) == Position, can only happen when 392bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// Grow is set and NewSize[idx] == Capacity-1. The index points to the node 393bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// before the one holding the Position'th element where there is room for an 394bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// insertion. 395bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 396bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Nodes The number of nodes. 397bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Elements Total elements in all nodes. 398bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Capacity The capacity of each node. 399bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param CurSize Array[Nodes] of current node sizes, or NULL. 400bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param NewSize Array[Nodes] to receive the new node sizes. 401bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Position Insert position. 402bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Grow Reserve space for a new element at Position. 403bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @return (node, offset) for Position. 404bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund OlesenIdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, 405bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen const unsigned *CurSize, unsigned NewSize[], 406bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen unsigned Position, bool Grow); 407bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen 4088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 410bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::NodeSizer ---// 4118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Compute node sizes from key and value types. 4148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The branching factors are chosen to make nodes fit in three cache lines. 4168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// This may not be possible if keys or values are very large. Such large objects 4178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// are handled correctly, but a std::map would probably give better performance. 4188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenenum { 4228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Cache line size. Most architectures have 32 or 64 byte cache lines. 4238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We use 64 bytes here because it provides good branching factors. 4248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Log2CacheLine = 6, 4258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen CacheLineBytes = 1 << Log2CacheLine, 4268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen DesiredNodeBytes = 3 * CacheLineBytes 4278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 4288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT> 4308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenstruct NodeSizer { 4318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen enum { 4328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Compute the leaf node branching factor that makes a node fit in three 4338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // cache lines. The branching factor must be at least 3, or some B+-tree 4348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // balancing algorithms won't work. 4358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // LeafSize can't be larger than CacheLineBytes. This is required by the 4368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // PointerIntPair used by NodeRef. 4378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen DesiredLeafSize = DesiredNodeBytes / 4388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)), 4398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen MinLeafSize = 3, 440528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize 441528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen }; 442528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen 443528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen typedef NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize> LeafBase; 4448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 445528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen enum { 4468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Now that we have the leaf branching factor, compute the actual allocation 4478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // unit size by rounding up to a whole number of cache lines. 448528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1), 4498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Determine the branching factor for branch nodes. 4518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen BranchSize = AllocBytes / 4528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen static_cast<unsigned>(sizeof(KeyT) + sizeof(void*)) 4538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen }; 4548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// Allocator - The recycling allocator used for both branch and leaf nodes. 4568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This typedef is very likely to be identical for all IntervalMaps with 4578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// reasonably sized entries, so the same allocator can be shared among 4588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// different kinds of maps. 4598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen typedef RecyclingAllocator<BumpPtrAllocator, char, 4608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen AllocBytes, CacheLineBytes> Allocator; 4618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 4638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 466bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::NodeRef ---// 4678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// B+-tree nodes can be leaves or branches, so we need a polymorphic node 4708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// pointer that can point to both kinds. 4718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// All nodes are cache line aligned and the low 6 bits of a node pointer are 4738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// always 0. These bits are used to store the number of elements in the 4748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// referenced node. Besides saving space, placing node sizes in the parents 4758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// allow tree balancing algorithms to run without faulting cache lines for nodes 4768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// that may not need to be modified. 4778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// A NodeRef doesn't know whether it references a leaf node or a branch node. 4798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// It is the responsibility of the caller to use the correct types. 4808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Nodes are never supposed to be empty, and it is invalid to store a node size 4828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// of 0 in a NodeRef. The valid range of sizes is 1-64. 4838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass NodeRef { 487bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen struct CacheAlignedPointerTraits { 488bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen static inline void *getAsVoidPointer(void *P) { return P; } 489bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen static inline void *getFromVoidPointer(void *P) { return P; } 490bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen enum { NumLowBitsAvailable = Log2CacheLine }; 491bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen }; 4928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip; 4938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 4958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// NodeRef - Create a null ref. 4968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen NodeRef() {} 4978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// operator bool - Detect a null ref. 499453f4f01302f00651aae2fc7658f6e23a2beadb0David Blaikie LLVM_EXPLICIT operator bool() const { return pip.getOpaqueValue(); } 5008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 501ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen /// NodeRef - Create a reference to the node p with n elements. 502ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen template <typename NodeT> 503ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) { 504ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen assert(n <= NodeT::Capacity && "Size too big for node"); 505ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen } 5068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// size - Return the number of elements in the referenced node. 5088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned size() const { return pip.getInt() + 1; } 5098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// setSize - Update the node size. 5118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void setSize(unsigned n) { pip.setInt(n - 1); } 5128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 513ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen /// subtree - Access the i'th subtree reference in a branch node. 514ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen /// This depends on branch nodes storing the NodeRef array as their first 515ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen /// member. 516706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef &subtree(unsigned i) const { 517ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen return reinterpret_cast<NodeRef*>(pip.getPointer())[i]; 5188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 520ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen /// get - Dereference as a NodeT reference. 521ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen template <typename NodeT> 522ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NodeT &get() const { 523ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen return *reinterpret_cast<NodeT*>(pip.getPointer()); 5248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool operator==(const NodeRef &RHS) const { 5278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (pip == RHS.pip) 5288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return true; 5298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs"); 5308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return false; 5318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool operator!=(const NodeRef &RHS) const { 5348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return !operator==(RHS); 5358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 5378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 539bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::LeafNode ---// 5408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 5418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 5428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Leaf nodes store up to N disjoint intervals with corresponding values. 5438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 5448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The intervals are kept sorted and fully coalesced so there are no adjacent 5458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// intervals mapping to the same value. 5468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 5478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// These constraints are always satisfied: 5488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 549ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen// - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals. 5508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 551ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen// - Traits::stopLess(stop(i), start(i + 1) - Sorted. 5528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 553ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen// - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1)) 554ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen// - Fully coalesced. 5558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 5568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 5578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 5598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> { 5608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 561a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen const KeyT &start(unsigned i) const { return this->first[i].first; } 562a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen const KeyT &stop(unsigned i) const { return this->first[i].second; } 563a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen const ValT &value(unsigned i) const { return this->second[i]; } 5648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 565a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen KeyT &start(unsigned i) { return this->first[i].first; } 566a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen KeyT &stop(unsigned i) { return this->first[i].second; } 567a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen ValT &value(unsigned i) { return this->second[i]; } 5688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// findFrom - Find the first interval after i that may contain x. 5708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Starting index for the search. 57133fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in node. 5728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 5738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return First index with !stopLess(key[i].stop, x), or size. 5748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is the first interval that can possibly contain x. 5758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { 5768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i <= Size && Size <= N && "Bad indices"); 5778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 5788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen "Index is past the needed point"); 5798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen while (i != Size && Traits::stopLess(stop(i), x)) ++i; 5808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return i; 5818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// safeFind - Find an interval that is known to exist. This is the same as 5848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// findFrom except is it assumed that x is at least within range of the last 5858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// interval. 5868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Starting index for the search. 5878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 5888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return First index with !stopLess(key[i].stop, x), never size. 5898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is the first interval that can possibly contain x. 5908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned safeFind(unsigned i, KeyT x) const { 5918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i < N && "Bad index"); 5928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 5938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen "Index is past the needed point"); 5948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen while (Traits::stopLess(stop(i), x)) ++i; 5958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i < N && "Unsafe intervals"); 5968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return i; 5978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// safeLookup - Lookup mapped value for a safe key. 6008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// It is assumed that x is within range of the last entry. 6018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 6028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param NotFound Value to return if x is not in any interval. 6038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return The mapped value at x or NotFound. 6048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen ValT safeLookup(KeyT x, ValT NotFound) const { 6058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned i = safeFind(0, x); 6068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return Traits::startLess(x, start(i)) ? NotFound : value(i); 6078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 6088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6095f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y); 6108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 6118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as 6138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// possible. This may cause the node to grow by 1, or it may cause the node 6148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// to shrink because of coalescing. 61515658b290817d6f198ab08910a2d754ba11164d1Rafael Espindola/// @param Pos Starting index = insertFrom(0, size, a) 61633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen/// @param Size Number of elements in node. 6178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// @param a Interval start. 6188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// @param b Interval stop. 6198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// @param y Value be mapped. 6208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// @return (insert position, new size), or (i, Capacity+1) on overflow. 6218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 6225f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesenunsigned LeafNode<KeyT, ValT, N, Traits>:: 6235f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund OleseninsertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) { 6245f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen unsigned i = Pos; 6258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i <= Size && Size <= N && "Invalid index"); 6268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(!Traits::stopLess(b, a) && "Invalid interval"); 6278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Verify the findFrom invariant. 6298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == 0 || Traits::stopLess(stop(i - 1), a))); 6308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == Size || !Traits::stopLess(stop(i), a))); 6315f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert"); 6328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Coalesce with previous interval. 6345f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) { 6355f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen Pos = i - 1; 6365f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen // Also coalesce with next interval? 6375f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) { 6385f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen stop(i - 1) = stop(i); 6395f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen this->erase(i, Size); 6405f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return Size - 1; 6415f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen } 6425f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen stop(i - 1) = b; 6435f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return Size; 6445f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen } 6458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Detect overflow. 6478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (i == N) 6485f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return N + 1; 6498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Add new interval at end. 6518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (i == Size) { 6528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen start(i) = a; 6538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen stop(i) = b; 6548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen value(i) = y; 6555f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return Size + 1; 6568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 6578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Try to coalesce with following interval. 6598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (value(i) == y && Traits::adjacent(b, start(i))) { 6608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen start(i) = a; 6615f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return Size; 6628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 6638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We must insert before i. Detect overflow. 6658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Size == N) 6665f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return N + 1; 6678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Insert before i. 6698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen this->shift(i, Size); 6708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen start(i) = a; 6718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen stop(i) = b; 6728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen value(i) = y; 6735f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return Size + 1; 6748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 6758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 678bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::BranchNode ---// 6798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 6808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 6818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// A branch node stores references to 1--N subtrees all of the same height. 6828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 6838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The key array in a branch node holds the rightmost stop key of each subtree. 6848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// It is redundant to store the last stop key since it can be found in the 6858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// parent node, but doing so makes tree balancing a lot simpler. 6868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 6878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// It is unusual for a branch node to only have one subtree, but it can happen 6888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// in the root node if it is smaller than the normal nodes. 6898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 6908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// When all of the leaf nodes from all the subtrees are concatenated, they must 6918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// satisfy the same constraints as a single leaf node. They must be sorted, 6928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// sane, and fully coalesced. 6938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 6948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 6958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 697ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesenclass BranchNode : public NodeBase<NodeRef, KeyT, N> { 6988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 699a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen const KeyT &stop(unsigned i) const { return this->second[i]; } 700ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen const NodeRef &subtree(unsigned i) const { return this->first[i]; } 7018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 702a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen KeyT &stop(unsigned i) { return this->second[i]; } 703ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NodeRef &subtree(unsigned i) { return this->first[i]; } 7048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 7058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// findFrom - Find the first subtree after i that may contain x. 7068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Starting index for the search. 70733fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in node. 7088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 7098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return First index with !stopLess(key[i], x), or size. 7108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is the first subtree that can possibly contain x. 7118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { 7128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i <= Size && Size <= N && "Bad indices"); 7138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 7148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen "Index to findFrom is past the needed point"); 7158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen while (i != Size && Traits::stopLess(stop(i), x)) ++i; 7168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return i; 7178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 7188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 7198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// safeFind - Find a subtree that is known to exist. This is the same as 7208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// findFrom except is it assumed that x is in range. 7218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Starting index for the search. 7228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 7238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return First index with !stopLess(key[i], x), never size. 7248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is the first subtree that can possibly contain x. 7258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned safeFind(unsigned i, KeyT x) const { 7268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i < N && "Bad index"); 7278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 7288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen "Index is past the needed point"); 7298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen while (Traits::stopLess(stop(i), x)) ++i; 7308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i < N && "Unsafe intervals"); 7318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return i; 7328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 7338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 7348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// safeLookup - Get the subtree containing x, Assuming that x is in range. 7358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 7368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return Subtree containing x 737ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NodeRef safeLookup(KeyT x) const { 7388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return subtree(safeFind(0, x)); 7398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 7408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 7418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// insert - Insert a new (subtree, stop) pair. 7428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Insert position, following entries will be shifted. 74333fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in node. 74433fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Node Subtree to insert. 74533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Stop Last key in subtree. 746ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) { 7478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(Size < N && "branch node overflow"); 7488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i <= Size && "Bad insert position"); 7498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen this->shift(i, Size); 7508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen subtree(i) = Node; 7518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen stop(i) = Stop; 7528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 7538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 7548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 755706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 756bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::Path ---// 757706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 758706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// 759706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// A Path is used by iterators to represent a position in a B+-tree, and the 760706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// path to get there from the root. 761706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// 762ab26da9e679afb26b6af589c2d414d50bf4a6441Lang Hames// The Path class also contains the tree navigation code that doesn't have to 763706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// be templatized. 764706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// 765706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 766706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 767706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesenclass Path { 768706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// Entry - Each step in the path is a node pointer and an offset into that 769706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// node. 770706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen struct Entry { 771706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void *node; 772706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned size; 773706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned offset; 774706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 775706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen Entry(void *Node, unsigned Size, unsigned Offset) 776706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen : node(Node), size(Size), offset(Offset) {} 777706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 778706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen Entry(NodeRef Node, unsigned Offset) 779706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {} 780706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 781706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef &subtree(unsigned i) const { 782706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return reinterpret_cast<NodeRef*>(node)[i]; 783706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 784706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen }; 785706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 786706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// path - The path entries, path[0] is the root node, path.back() is a leaf. 787706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen SmallVector<Entry, 4> path; 788706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 789706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesenpublic: 790706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Node accessors. 791706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen template <typename NodeT> NodeT &node(unsigned Level) const { 792706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return *reinterpret_cast<NodeT*>(path[Level].node); 793706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 794706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned size(unsigned Level) const { return path[Level].size; } 795706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned offset(unsigned Level) const { return path[Level].offset; } 796706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned &offset(unsigned Level) { return path[Level].offset; } 797706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 798706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Leaf accessors. 799706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen template <typename NodeT> NodeT &leaf() const { 800706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return *reinterpret_cast<NodeT*>(path.back().node); 801706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 802706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned leafSize() const { return path.back().size; } 803706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned leafOffset() const { return path.back().offset; } 804706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned &leafOffset() { return path.back().offset; } 805706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 806706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// valid - Return true if path is at a valid node, not at end(). 807706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen bool valid() const { 808706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return !path.empty() && path.front().offset < path.front().size; 809706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 810706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 811706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// height - Return the height of the tree corresponding to this path. 812706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// This matches map->height in a full path. 813706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned height() const { return path.size() - 1; } 814706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 815706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// subtree - Get the subtree referenced from Level. When the path is 816706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// consistent, node(Level + 1) == subtree(Level). 817706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level 0..height-1. The leaves have no subtrees. 818706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef &subtree(unsigned Level) const { 819706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return path[Level].subtree(path[Level].offset); 820706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 821706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 82253bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen /// reset - Reset cached information about node(Level) from subtree(Level -1). 82353bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen /// @param Level 1..height. THe node to update after parent node changed. 82453bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen void reset(unsigned Level) { 82553bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen path[Level] = Entry(subtree(Level - 1), offset(Level)); 82653bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen } 82753bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen 828706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// push - Add entry to path. 829706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Node Node to add, should be subtree(path.size()-1). 830706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Offset Offset into Node. 831706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void push(NodeRef Node, unsigned Offset) { 832706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.push_back(Entry(Node, Offset)); 833706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 834706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 835180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen /// pop - Remove the last path entry. 836180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen void pop() { 837180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.pop_back(); 838180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 839180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen 840706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// setSize - Set the size of a node both in the path and in the tree. 841706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level 0..height. Note that setting the root size won't change 842706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// map->rootSize. 843706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Size New node size. 844706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void setSize(unsigned Level, unsigned Size) { 845706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path[Level].size = Size; 846706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (Level) 847706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen subtree(Level - 1).setSize(Size); 848706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 849706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 850706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// setRoot - Clear the path and set a new root node. 851706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Node New root node. 852706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Size New root size. 853706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Offset Offset into root node. 854706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void setRoot(void *Node, unsigned Size, unsigned Offset) { 855706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.clear(); 856706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.push_back(Entry(Node, Size, Offset)); 857706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 858706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 859706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// replaceRoot - Replace the current root node with two new entries after the 860706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// tree height has increased. 861706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Root The new root node. 862706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Size Number of entries in the new root. 863706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Offsets Offsets into the root and first branch nodes. 864706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void replaceRoot(void *Root, unsigned Size, IdxPair Offsets); 865706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 866706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 867706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level Get the sibling to node(Level). 868706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @return Left sibling, or NodeRef(). 869706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef getLeftSibling(unsigned Level) const; 870706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 871706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level 872706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// unaltered. 873706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level Move node(Level). 874706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void moveLeft(unsigned Level); 875706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 876706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// fillLeft - Grow path to Height by taking leftmost branches. 877706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Height The target height. 878706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void fillLeft(unsigned Height) { 879706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen while (height() < Height) 880706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen push(subtree(height()), 0); 881706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 882706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 883706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 884706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level Get the sinbling to node(Level). 885706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @return Left sibling, or NodeRef(). 886706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef getRightSibling(unsigned Level) const; 887706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 888706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// moveRight - Move path to the left sibling at Level. Leave nodes below 889706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// Level unaltered. 890706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level Move node(Level). 891706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void moveRight(unsigned Level); 892706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 893055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen /// atBegin - Return true if path is at begin(). 894055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen bool atBegin() const { 895055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen for (unsigned i = 0, e = path.size(); i != e; ++i) 896055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen if (path[i].offset != 0) 897055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return false; 898055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return true; 899055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } 900055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 9017a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// atLastEntry - Return true if the path is at the last entry of the node at 9027a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// Level. 903706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level Node to examine. 9047a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen bool atLastEntry(unsigned Level) const { 905706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return path[Level].offset == path[Level].size - 1; 906706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 907706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 908706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// legalizeForInsert - Prepare the path for an insertion at Level. When the 909706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// path is at end(), node(Level) may not be a legal node. legalizeForInsert 910706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// ensures that node(Level) is real by moving back to the last node at Level, 911706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// and setting offset(Level) to size(Level) if required. 912706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level The level where an insertion is about to take place. 913706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void legalizeForInsert(unsigned Level) { 914706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (valid()) 915706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return; 916706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen moveLeft(Level); 917706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen ++path[Level].offset; 918706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 919706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen}; 920706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 9218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} // namespace IntervalMapImpl 9228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 9258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//--- IntervalMap ----// 9268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 9278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, 9298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize, 9308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen typename Traits = IntervalMapInfo<KeyT> > 9318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass IntervalMap { 932ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen typedef IntervalMapImpl::NodeSizer<KeyT, ValT> Sizer; 933ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen typedef IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits> Leaf; 934ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen typedef IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits> 935ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen Branch; 9368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf; 9378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen typedef IntervalMapImpl::IdxPair IdxPair; 9388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // The RootLeaf capacity is given as a template parameter. We must compute the 9408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // corresponding RootBranch capacity. 9418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen enum { 9428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) / 943ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)), 9448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1 9458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen }; 9468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 947ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits> 948ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen RootBranch; 9498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // When branched, we store a global start key as well as the branch node. 9518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen struct RootBranchData { 9528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT start; 9538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootBranch node; 9548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen }; 9558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen enum { 9578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ? 9588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen sizeof(RootBranchData) : sizeof(RootLeaf) 9598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen }; 9608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 962ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen typedef typename Sizer::Allocator Allocator; 963ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen typedef KeyT KeyType; 964ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen typedef ValT ValueType; 965cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen typedef Traits KeyTraits; 9668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenprivate: 9688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // The root data is either a RootLeaf or a RootBranchData instance. 9698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We can't put them in a union since C++03 doesn't allow non-trivial 9708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // constructors in unions. 9718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Instead, we use a char array with pointer alignment. The alignment is 9728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // ensured by the allocator member in the class, but still verified in the 9738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // constructor. We don't support keys or values that are more aligned than a 9748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // pointer. 9758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen char data[RootDataSize]; 9768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Tree height. 9788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // 0: Leaves in root. 9798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // 1: Root points to leaf. 9808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // 2: root->branch->leaf ... 9818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned height; 9828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Number of entries in the root node. 9848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned rootSize; 9858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Allocator used for creating external nodes. 9878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Allocator &allocator; 9888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// dataAs - Represent data as a node type without breaking aliasing rules. 9908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen template <typename T> 9918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen T &dataAs() const { 9928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen union { 9938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const char *d; 9948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen T *t; 9958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } u; 9968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen u.d = data; 9978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return *u.t; 9988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 9998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const RootLeaf &rootLeaf() const { 10018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(!branched() && "Cannot acces leaf data in branched root"); 10028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return dataAs<RootLeaf>(); 10038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootLeaf &rootLeaf() { 10058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(!branched() && "Cannot acces leaf data in branched root"); 10068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return dataAs<RootLeaf>(); 10078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootBranchData &rootBranchData() const { 10098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(branched() && "Cannot access branch data in non-branched root"); 10108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return dataAs<RootBranchData>(); 10118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootBranchData &rootBranchData() { 10138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(branched() && "Cannot access branch data in non-branched root"); 10148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return dataAs<RootBranchData>(); 10158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const RootBranch &rootBranch() const { return rootBranchData().node; } 10178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootBranch &rootBranch() { return rootBranchData().node; } 10188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT rootBranchStart() const { return rootBranchData().start; } 10198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT &rootBranchStart() { return rootBranchData().start; } 10208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1021b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen template <typename NodeT> NodeT *newNode() { 1022b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen return new(allocator.template Allocate<NodeT>()) NodeT(); 10238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1025b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen template <typename NodeT> void deleteNode(NodeT *P) { 1026b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P->~NodeT(); 10278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen allocator.Deallocate(P); 10288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IdxPair branchRoot(unsigned Position); 10318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IdxPair splitRoot(unsigned Position); 10328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void switchRootToBranch() { 10348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootLeaf().~RootLeaf(); 10358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen height = 1; 10368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen new (&rootBranchData()) RootBranchData(); 10378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void switchRootToLeaf() { 10408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootBranchData().~RootBranchData(); 10418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen height = 0; 10428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen new(&rootLeaf()) RootLeaf(); 10438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool branched() const { return height > 0; } 10468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen ValT treeSafeLookup(KeyT x, ValT NotFound) const; 1048ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, 1049ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen unsigned Level)); 1050ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level); 10518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 10538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) { 10548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 && 10558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen "Insufficient alignment"); 10568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen new(&rootLeaf()) RootLeaf(); 10578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1059785ab18a054373f1a2f8d0f6f04db2d458878bd9Jakob Stoklund Olesen ~IntervalMap() { 1060785ab18a054373f1a2f8d0f6f04db2d458878bd9Jakob Stoklund Olesen clear(); 1061785ab18a054373f1a2f8d0f6f04db2d458878bd9Jakob Stoklund Olesen rootLeaf().~RootLeaf(); 1062785ab18a054373f1a2f8d0f6f04db2d458878bd9Jakob Stoklund Olesen } 1063785ab18a054373f1a2f8d0f6f04db2d458878bd9Jakob Stoklund Olesen 10648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// empty - Return true when no intervals are mapped. 10658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool empty() const { 10668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return rootSize == 0; 10678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// start - Return the smallest mapped key in a non-empty map. 10708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT start() const { 10718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(!empty() && "Empty IntervalMap has no start"); 10728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return !branched() ? rootLeaf().start(0) : rootBranchStart(); 10738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// stop - Return the largest mapped key in a non-empty map. 10768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT stop() const { 10778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(!empty() && "Empty IntervalMap has no stop"); 10788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return !branched() ? rootLeaf().stop(rootSize - 1) : 10798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootBranch().stop(rootSize - 1); 10808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// lookup - Return the mapped value at x or NotFound. 10838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen ValT lookup(KeyT x, ValT NotFound = ValT()) const { 10848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x)) 10858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return NotFound; 10868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return branched() ? treeSafeLookup(x, NotFound) : 10878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootLeaf().safeLookup(x, NotFound); 10888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals. 10918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// It is assumed that no key in the interval is mapped to another value, but 10928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// overlapping intervals already mapped to y will be coalesced. 10938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void insert(KeyT a, KeyT b, ValT y) { 109479283768a36746bcb5885746637752312af9e4acJakob Stoklund Olesen if (branched() || rootSize == RootLeaf::Capacity) 109579283768a36746bcb5885746637752312af9e4acJakob Stoklund Olesen return find(a).insert(a, b, y); 109679283768a36746bcb5885746637752312af9e4acJakob Stoklund Olesen 109779283768a36746bcb5885746637752312af9e4acJakob Stoklund Olesen // Easy insert into root leaf. 109879283768a36746bcb5885746637752312af9e4acJakob Stoklund Olesen unsigned p = rootLeaf().findFrom(0, rootSize, a); 10995f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y); 11008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1102655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen /// clear - Remove all entries. 1103655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen void clear(); 1104655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen 11058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen class const_iterator; 11068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen class iterator; 11078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen friend class const_iterator; 11088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen friend class iterator; 11098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator begin() const { 1111da2fdcbb639de168738c27089bafa9ca10b731bdJakob Stoklund Olesen const_iterator I(*this); 11128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.goToBegin(); 11138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator begin() { 11178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator I(*this); 11188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.goToBegin(); 11198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator end() const { 1123da2fdcbb639de168738c27089bafa9ca10b731bdJakob Stoklund Olesen const_iterator I(*this); 11248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.goToEnd(); 11258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator end() { 11298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator I(*this); 11308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.goToEnd(); 11318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// find - Return an iterator pointing to the first interval ending at or 11358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// after x, or end(). 11368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator find(KeyT x) const { 1137da2fdcbb639de168738c27089bafa9ca10b731bdJakob Stoklund Olesen const_iterator I(*this); 11388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.find(x); 11398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator find(KeyT x) { 11438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator I(*this); 11448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.find(x); 11458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 11488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// treeSafeLookup - Return the mapped value at x or NotFound, assuming a 11508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// branched root. 11518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 11528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesenValT IntervalMap<KeyT, ValT, N, Traits>:: 11538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesentreeSafeLookup(KeyT x, ValT NotFound) const { 11548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(branched() && "treeLookup assumes a branched root"); 11558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1156ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x); 11578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned h = height-1; h; --h) 1158ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NR = NR.get<Branch>().safeLookup(x); 1159ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen return NR.get<Leaf>().safeLookup(x, NotFound); 11608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 11618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// branchRoot - Switch from a leaf root to a branched root. 11648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Return the new (root offset, node offset) corresponding to Position. 11658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 11668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesenIntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 11678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesenbranchRoot(unsigned Position) { 1168ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen using namespace IntervalMapImpl; 11698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // How many external leaf nodes to hold RootLeaf+1? 11708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1; 11718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Compute element distribution among new nodes. 11738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned size[Nodes]; 11748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IdxPair NewOffset(0, Position); 11758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Is is very common for the root node to be smaller than external nodes. 11778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Nodes == 1) 11788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen size[0] = rootSize; 11798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1180dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, size, 11818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Position, true); 11828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Allocate new nodes. 11848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned pos = 0; 11858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen NodeRef node[Nodes]; 11868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned n = 0; n != Nodes; ++n) { 1187b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Leaf *L = newNode<Leaf>(); 1188b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen L->copy(rootLeaf(), pos, 0, size[n]); 1189b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen node[n] = NodeRef(L, size[n]); 11908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen pos += size[n]; 11918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Destroy the old leaf node, construct branch node instead. 11948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen switchRootToBranch(); 11958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned n = 0; n != Nodes; ++n) { 1196ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1); 11978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootBranch().subtree(n) = node[n]; 11988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1199ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen rootBranchStart() = node[0].template get<Leaf>().start(0); 12008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootSize = Nodes; 12018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return NewOffset; 12028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 12038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// splitRoot - Split the current BranchRoot into multiple Branch nodes. 12058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Return the new (root offset, node offset) corresponding to Position. 12068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 12078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesenIntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 12088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesensplitRoot(unsigned Position) { 1209ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen using namespace IntervalMapImpl; 12108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // How many external leaf nodes to hold RootBranch+1? 12118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1; 12128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Compute element distribution among new nodes. 12148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Size[Nodes]; 12158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IdxPair NewOffset(0, Position); 12168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Is is very common for the root node to be smaller than external nodes. 12188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Nodes == 1) 12198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Size[0] = rootSize; 12208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1221dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, Size, 12228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Position, true); 12238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Allocate new nodes. 12258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Pos = 0; 12268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen NodeRef Node[Nodes]; 12278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned n = 0; n != Nodes; ++n) { 1228b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Branch *B = newNode<Branch>(); 1229b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen B->copy(rootBranch(), Pos, 0, Size[n]); 1230b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Node[n] = NodeRef(B, Size[n]); 12318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Pos += Size[n]; 12328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 12338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned n = 0; n != Nodes; ++n) { 1235ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1); 12368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootBranch().subtree(n) = Node[n]; 12378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 12388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootSize = Nodes; 12396c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen ++height; 12408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return NewOffset; 12418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 12428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// visitNodes - Visit each external node. 12448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 12458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1246ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund OlesenvisitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) { 12478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (!branched()) 12488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return; 1249ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs; 12508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Collect level 0 nodes from the root. 12528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned i = 0; i != rootSize; ++i) 12538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Refs.push_back(rootBranch().subtree(i)); 12548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Visit all branch nodes. 12568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned h = height - 1; h; --h) { 12578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned i = 0, e = Refs.size(); i != e; ++i) { 12588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned j = 0, s = Refs[i].size(); j != s; ++j) 1259ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NextRefs.push_back(Refs[i].subtree(j)); 12608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen (this->*f)(Refs[i], h); 12618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 12628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Refs.clear(); 12638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Refs.swap(NextRefs); 12648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 12658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Visit all leaf nodes. 12678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned i = 0, e = Refs.size(); i != e; ++i) 12688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen (this->*f)(Refs[i], 0); 12698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 12708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1271655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1272655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1273ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund OlesendeleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) { 1274655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen if (Level) 1275b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen deleteNode(&Node.get<Branch>()); 1276655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen else 1277b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen deleteNode(&Node.get<Leaf>()); 1278655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen} 1279655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen 1280655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1281655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1282655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesenclear() { 1283655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen if (branched()) { 1284655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen visitNodes(&IntervalMap::deleteNode); 1285655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen switchRootToLeaf(); 1286655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen } 1287655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen rootSize = 0; 1288655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen} 1289655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen 12908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1291bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMap::const_iterator ----// 12928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 12938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 12958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass IntervalMap<KeyT, ValT, N, Traits>::const_iterator : 12968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen public std::iterator<std::bidirectional_iterator_tag, ValT> { 12978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenprotected: 12988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen friend class IntervalMap; 12998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // The map referred to. 13018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IntervalMap *map; 13028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We store a full path from the root to the current position. 13048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // The path may be partially filled, but never between iterator calls. 1305706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMapImpl::Path path; 13068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1307da2fdcbb639de168738c27089bafa9ca10b731bdJakob Stoklund Olesen explicit const_iterator(const IntervalMap &map) : 1308da2fdcbb639de168738c27089bafa9ca10b731bdJakob Stoklund Olesen map(const_cast<IntervalMap*>(&map)) {} 13098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool branched() const { 13118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(map && "Invalid iterator"); 13128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return map->branched(); 13138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1315706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void setRoot(unsigned Offset) { 1316706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (branched()) 1317706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.setRoot(&map->rootBranch(), map->rootSize, Offset); 13188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1319706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.setRoot(&map->rootLeaf(), map->rootSize, Offset); 13208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void pathFillFind(KeyT x); 13238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void treeFind(KeyT x); 1324180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen void treeAdvanceTo(KeyT x); 13258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13267a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// unsafeStart - Writable access to start() for iterator. 13277a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT &unsafeStart() const { 13288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(valid() && "Cannot access invalid iterator"); 1329706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return branched() ? path.leaf<Leaf>().start(path.leafOffset()) : 1330706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.leaf<RootLeaf>().start(path.leafOffset()); 13318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13337a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// unsafeStop - Writable access to stop() for iterator. 13347a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT &unsafeStop() const { 13358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(valid() && "Cannot access invalid iterator"); 1336706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) : 1337706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.leaf<RootLeaf>().stop(path.leafOffset()); 13388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13407a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// unsafeValue - Writable access to value() for iterator. 13417a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen ValT &unsafeValue() const { 13428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(valid() && "Cannot access invalid iterator"); 1343706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return branched() ? path.leaf<Leaf>().value(path.leafOffset()) : 1344706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.leaf<RootLeaf>().value(path.leafOffset()); 13458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13477a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenpublic: 13487a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// const_iterator - Create an iterator that isn't pointing anywhere. 1349dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const_iterator() : map(nullptr) {} 13507a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 13515907d863659eb972ebb2afe07bc863a4c616f0efJakob Stoklund Olesen /// setMap - Change the map iterated over. This call must be followed by a 13525907d863659eb972ebb2afe07bc863a4c616f0efJakob Stoklund Olesen /// call to goToBegin(), goToEnd(), or find() 13535907d863659eb972ebb2afe07bc863a4c616f0efJakob Stoklund Olesen void setMap(const IntervalMap &m) { map = const_cast<IntervalMap*>(&m); } 13545907d863659eb972ebb2afe07bc863a4c616f0efJakob Stoklund Olesen 13557a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// valid - Return true if the current position is valid, false for end(). 13567a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen bool valid() const { return path.valid(); } 13577a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 1358cafe614035c8db70eb5da96dba00696db381674fJakob Stoklund Olesen /// atBegin - Return true if the current position is the first map entry. 1359cafe614035c8db70eb5da96dba00696db381674fJakob Stoklund Olesen bool atBegin() const { return path.atBegin(); } 1360cafe614035c8db70eb5da96dba00696db381674fJakob Stoklund Olesen 13617a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// start - Return the beginning of the current interval. 13627a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen const KeyT &start() const { return unsafeStart(); } 13637a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 13647a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// stop - Return the end of the current interval. 13657a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen const KeyT &stop() const { return unsafeStop(); } 13667a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 13677a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// value - Return the mapped value at the current interval. 13687a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen const ValT &value() const { return unsafeValue(); } 13697a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 13707a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen const ValT &operator*() const { return value(); } 13718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool operator==(const const_iterator &RHS) const { 13738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(map == RHS.map && "Cannot compare iterators from different maps"); 1374706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (!valid()) 1375706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return !RHS.valid(); 1376706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (path.leafOffset() != RHS.path.leafOffset()) 1377706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return false; 1378706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>(); 13798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool operator!=(const const_iterator &RHS) const { 13828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return !operator==(RHS); 13838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// goToBegin - Move to the first interval in map. 13868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void goToBegin() { 1387706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen setRoot(0); 13888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (branched()) 1389706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.fillLeft(map->height); 13908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// goToEnd - Move beyond the last interval in map. 13938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void goToEnd() { 1394706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen setRoot(map->rootSize); 13958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// preincrement - move to the next interval. 13988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator &operator++() { 13998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(valid() && "Cannot increment end()"); 1400706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (++path.leafOffset() == path.leafSize() && branched()) 1401706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.moveRight(map->height); 14028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return *this; 14038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 14048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// postincrement - Dont do that! 14068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator operator++(int) { 14078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator tmp = *this; 14088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen operator++(); 14098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return tmp; 14108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 14118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// predecrement - move to the previous interval. 14138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator &operator--() { 1414706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (path.leafOffset() && (valid() || !branched())) 1415706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen --path.leafOffset(); 14168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1417706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.moveLeft(map->height); 14188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return *this; 14198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 14208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// postdecrement - Dont do that! 14228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator operator--(int) { 14238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator tmp = *this; 14248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen operator--(); 14258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return tmp; 14268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 14278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// find - Move to the first interval with stop >= x, or end(). 14298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is a full search from the root, the current position is ignored. 14308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void find(KeyT x) { 14318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (branched()) 14328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen treeFind(x); 14338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1434706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen setRoot(map->rootLeaf().findFrom(0, map->rootSize, x)); 14358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 14368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// advanceTo - Move to the first interval with stop >= x, or end(). 14388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// The search is started from the current position, and no earlier positions 14398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// can be found. This is much faster than find() for small moves. 14408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void advanceTo(KeyT x) { 14415049ee5b11fe55e5a553b5388406aab874717672Jakob Stoklund Olesen if (!valid()) 14425049ee5b11fe55e5a553b5388406aab874717672Jakob Stoklund Olesen return; 14438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (branched()) 14448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen treeAdvanceTo(x); 14458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1446706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.leafOffset() = 1447706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x); 14488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 14498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 14518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1452180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// pathFillFind - Complete path by searching for x. 1453180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// @param x Key to search for. 14548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 14558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 14568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenconst_iterator::pathFillFind(KeyT x) { 1457706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMapImpl::NodeRef NR = path.subtree(path.height()); 1458706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen for (unsigned i = map->height - path.height() - 1; i; --i) { 1459ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen unsigned p = NR.get<Branch>().safeFind(0, x); 1460706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.push(NR, p); 1461ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NR = NR.subtree(p); 14628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1463706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.push(NR, NR.get<Leaf>().safeFind(0, x)); 14648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 14658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1466180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// treeFind - Find in a branched tree. 1467180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// @param x Key to search for. 14688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 14698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 14708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenconst_iterator::treeFind(KeyT x) { 1471706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen setRoot(map->rootBranch().findFrom(0, map->rootSize, x)); 14728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (valid()) 14738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen pathFillFind(x); 14748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 14758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1476180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// treeAdvanceTo - Find position after the current one. 1477180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// @param x Key to search for. 1478180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1479180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1480180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesenconst_iterator::treeAdvanceTo(KeyT x) { 1481180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // Can we stay on the same leaf node? 1482180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) { 1483180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x); 1484180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen return; 1485180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 1486180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen 1487180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // Drop the current leaf. 1488180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.pop(); 1489180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen 1490180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // Search towards the root for a usable subtree. 1491180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen if (path.height()) { 1492180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen for (unsigned l = path.height() - 1; l; --l) { 1493180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) { 1494180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // The branch node at l+1 is usable 1495180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.offset(l + 1) = 1496180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x); 1497180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen return pathFillFind(x); 1498180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 1499180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.pop(); 1500180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 1501180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // Is the level-1 Branch usable? 1502180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) { 1503180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x); 1504180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen return pathFillFind(x); 1505180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 1506180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 1507180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen 1508180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // We reached the root. 1509180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x)); 1510180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen if (valid()) 1511180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen pathFillFind(x); 1512180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen} 15138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 15148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1515bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMap::iterator ----// 15168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 15178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 15188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 15198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator { 15208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen friend class IntervalMap; 15218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen typedef IntervalMapImpl::IdxPair IdxPair; 15228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 15238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen explicit iterator(IntervalMap &map) : const_iterator(map) {} 15248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 15258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void setNodeStop(unsigned Level, KeyT Stop); 15266c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop); 15276c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen template <typename NodeT> bool overflow(unsigned Level); 15288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void treeInsert(KeyT a, KeyT b, ValT y); 1529b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen void eraseNode(unsigned Level); 1530055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen void treeErase(bool UpdateRoot = true); 15317a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen bool canCoalesceLeft(KeyT Start, ValT x); 15327a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen bool canCoalesceRight(KeyT Stop, ValT x); 15337a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 15359a08ca318e63912e4c19977abc1173f30866b704Jakob Stoklund Olesen /// iterator - Create null iterator. 15369a08ca318e63912e4c19977abc1173f30866b704Jakob Stoklund Olesen iterator() {} 15379a08ca318e63912e4c19977abc1173f30866b704Jakob Stoklund Olesen 15387a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setStart - Move the start of the current interval. 15397a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// This may cause coalescing with the previous interval. 15407a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param a New start key, must not overlap the previous interval. 15417a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setStart(KeyT a); 15427a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15437a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setStop - Move the end of the current interval. 15447a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// This may cause coalescing with the following interval. 15457a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param b New stop key, must not overlap the following interval. 15467a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setStop(KeyT b); 15477a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15487a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setValue - Change the mapped value of the current interval. 15497a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// This may cause coalescing with the previous and following intervals. 15507a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param x New value. 15517a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setValue(ValT x); 15527a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15537a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setStartUnchecked - Move the start of the current interval without 15547a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// checking for coalescing or overlaps. 15557a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// This should only be used when it is known that coalescing is not required. 15567a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param a New start key. 15577a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setStartUnchecked(KeyT a) { this->unsafeStart() = a; } 15587a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15597a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setStopUnchecked - Move the end of the current interval without checking 15607a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// for coalescing or overlaps. 15617a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// This should only be used when it is known that coalescing is not required. 15627a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param b New stop key. 15637a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setStopUnchecked(KeyT b) { 15647a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen this->unsafeStop() = b; 15657a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen // Update keys in branch nodes as well. 15667a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (this->path.atLastEntry(this->path.height())) 15677a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setNodeStop(this->path.height(), b); 15687a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 15697a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15707a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setValueUnchecked - Change the mapped value of the current interval 15717a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// without checking for coalescing. 15727a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param x New value. 15737a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setValueUnchecked(ValT x) { this->unsafeValue() = x; } 15747a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// insert - Insert mapping [a;b] -> y before the current position. 15768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void insert(KeyT a, KeyT b, ValT y); 15778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1578b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen /// erase - Erase the current interval. 1579b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen void erase(); 1580055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 1581055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator &operator++() { 1582055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen const_iterator::operator++(); 1583055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return *this; 1584055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } 1585055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 1586055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator operator++(int) { 1587055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator tmp = *this; 1588055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen operator++(); 1589055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return tmp; 1590055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } 1591055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 1592055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator &operator--() { 1593055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen const_iterator::operator--(); 1594055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return *this; 1595055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } 1596055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 1597055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator operator--(int) { 1598055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator tmp = *this; 1599055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen operator--(); 1600055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return tmp; 1601055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } 1602055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 16038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 16048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 16057a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// canCoalesceLeft - Can the current interval coalesce to the left after 16067a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// changing start or value? 16077a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @param Start New start of current interval. 16087a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @param Value New value for current interval. 16097a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @return True when updating the current interval would enable coalescing. 16107a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 16117a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenbool IntervalMap<KeyT, ValT, N, Traits>:: 16127a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Oleseniterator::canCoalesceLeft(KeyT Start, ValT Value) { 16137a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen using namespace IntervalMapImpl; 16147a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Path &P = this->path; 16157a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (!this->branched()) { 16167a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen unsigned i = P.leafOffset(); 16177a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen RootLeaf &Node = P.leaf<RootLeaf>(); 16187a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return i && Node.value(i-1) == Value && 16197a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Traits::adjacent(Node.stop(i-1), Start); 16207a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16217a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen // Branched. 16227a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (unsigned i = P.leafOffset()) { 16237a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Leaf &Node = P.leaf<Leaf>(); 16247a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start); 16257a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } else if (NodeRef NR = P.getLeftSibling(P.height())) { 16267a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen unsigned i = NR.size() - 1; 16277a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Leaf &Node = NR.get<Leaf>(); 16287a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start); 16297a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16307a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return false; 16317a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen} 16327a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 16337a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// canCoalesceRight - Can the current interval coalesce to the right after 16347a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// changing stop or value? 16357a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @param Stop New stop of current interval. 16367a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @param Value New value for current interval. 16377a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @return True when updating the current interval would enable coalescing. 16387a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 16397a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenbool IntervalMap<KeyT, ValT, N, Traits>:: 16407a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Oleseniterator::canCoalesceRight(KeyT Stop, ValT Value) { 16417a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen using namespace IntervalMapImpl; 16427a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Path &P = this->path; 16437a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen unsigned i = P.leafOffset() + 1; 16447a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (!this->branched()) { 16457a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (i >= P.leafSize()) 16467a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return false; 16477a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen RootLeaf &Node = P.leaf<RootLeaf>(); 16487a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); 16497a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16507a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen // Branched. 16517a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (i < P.leafSize()) { 16527a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Leaf &Node = P.leaf<Leaf>(); 16537a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); 16547a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } else if (NodeRef NR = P.getRightSibling(P.height())) { 16557a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Leaf &Node = NR.get<Leaf>(); 16567a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0)); 16577a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16587a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return false; 16597a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen} 16607a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 16618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// setNodeStop - Update the stop key of the current node at level and above. 16628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 16638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 16648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Oleseniterator::setNodeStop(unsigned Level, KeyT Stop) { 1665706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // There are no references to the root node, so nothing to update. 1666706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (!Level) 1667706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return; 1668706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 1669706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Update nodes pointing to the current node. 1670706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen while (--Level) { 1671706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.node<Branch>(Level).stop(P.offset(Level)) = Stop; 16727a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (!P.atLastEntry(Level)) 16738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return; 16748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1675706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Update root separately since it has a different layout. 1676706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop; 16778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 16788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 16797a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 16807a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 16817a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Oleseniterator::setStart(KeyT a) { 16827a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen assert(Traits::stopLess(a, this->stop()) && "Cannot move start beyond stop"); 16837a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT &CurStart = this->unsafeStart(); 16847a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) { 16857a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen CurStart = a; 16867a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return; 16877a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16887a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen // Coalesce with the interval to the left. 16897a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen --*this; 16907a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen a = this->start(); 16917a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen erase(); 16927a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setStartUnchecked(a); 16937a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen} 16947a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 16957a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 16967a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 16977a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Oleseniterator::setStop(KeyT b) { 16987a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen assert(Traits::stopLess(this->start(), b) && "Cannot move stop beyond start"); 16997a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (Traits::startLess(b, this->stop()) || 17007a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen !canCoalesceRight(b, this->value())) { 17017a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setStopUnchecked(b); 17027a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return; 17037a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 17047a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen // Coalesce with interval to the right. 17057a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT a = this->start(); 17067a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen erase(); 17077a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setStartUnchecked(a); 17087a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen} 17097a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 17107a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 17117a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 17127a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Oleseniterator::setValue(ValT x) { 17137a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setValueUnchecked(x); 17147a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (canCoalesceRight(this->stop(), x)) { 17157a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT a = this->start(); 17167a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen erase(); 17177a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setStartUnchecked(a); 17187a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 17197a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (canCoalesceLeft(this->start(), x)) { 17207a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen --*this; 17217a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT a = this->start(); 17227a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen erase(); 17237a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setStartUnchecked(a); 17247a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 17257a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen} 17267a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 17278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// insertNode - insert a node before the current path at level. 17288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// Leave the current path pointing at the new node. 17296c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @param Level path index of the node to be inserted. 17306c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @param Node The node to be inserted. 17316c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @param Stop The last index in the new node. 17326c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @return True if the tree height was increased. 17338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 17346c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesenbool IntervalMap<KeyT, ValT, N, Traits>:: 1735ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Oleseniterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) { 1736706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen assert(Level && "Cannot insert next to the root"); 17376c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen bool SplitRoot = false; 1738706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMap &IM = *this->map; 1739706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 17406c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen 1741706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (Level == 1) { 17428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Insert into the root branch node. 17438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (IM.rootSize < RootBranch::Capacity) { 1744706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop); 1745706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.setSize(0, ++IM.rootSize); 174653bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen P.reset(Level); 17476c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen return SplitRoot; 17488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 17498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 17508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We need to split the root while keeping our position. 17516c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen SplitRoot = true; 1752706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IdxPair Offset = IM.splitRoot(P.offset(0)); 1753706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1754706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1755706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Fall through to insert at the new higher level. 1756706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen ++Level; 17578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 17588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 17598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // When inserting before end(), make sure we have a valid path. 1760706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.legalizeForInsert(--Level); 17618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1762706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Insert into the branch node at Level-1. 1763706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (P.size(Level) == Branch::Capacity) { 1764706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Branch node is full, handle handle the overflow. 17656c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen assert(!SplitRoot && "Cannot overflow after splitting the root"); 1766706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen SplitRoot = overflow<Branch>(Level); 17676c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen Level += SplitRoot; 17686c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen } 1769706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop); 1770706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.setSize(Level, P.size(Level) + 1); 17717a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (P.atLastEntry(Level)) 177253bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen setNodeStop(Level, Stop); 177353bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen P.reset(Level + 1); 17746c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen return SplitRoot; 17758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 17768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 17778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// insert 17788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 17798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 17808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Oleseniterator::insert(KeyT a, KeyT b, ValT y) { 17818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (this->branched()) 17828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return treeInsert(a, b, y); 1783706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMap &IM = *this->map; 1784706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 1785706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1786706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Try simple root leaf insert. 17875f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y); 1788706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1789706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Was the root node insert successful? 17905f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (Size <= RootLeaf::Capacity) { 17915f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen P.setSize(0, IM.rootSize = Size); 17928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return; 17938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1794706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1795706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Root leaf node is full, we must branch. 1796706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IdxPair Offset = IM.branchRoot(P.leafOffset()); 1797706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1798706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1799706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Now it fits in the new leaf. 18008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen treeInsert(a, b, y); 18018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 18028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 18038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 18048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 18058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 18068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Oleseniterator::treeInsert(KeyT a, KeyT b, ValT y) { 1807b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen using namespace IntervalMapImpl; 1808b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Path &P = this->path; 1809b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 18105f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (!P.valid()) 18115f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen P.legalizeForInsert(this->map->height); 18125f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen 1813b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Check if this insertion will extend the node to the left. 18145f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) { 1815b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Node is growing to the left, will it affect a left sibling node? 18165f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (NodeRef Sib = P.getLeftSibling(P.height())) { 1817b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Leaf &SibLeaf = Sib.get<Leaf>(); 1818b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen unsigned SibOfs = Sib.size() - 1; 1819b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (SibLeaf.value(SibOfs) == y && 1820b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Traits::adjacent(SibLeaf.stop(SibOfs), a)) { 1821b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // This insertion will coalesce with the last entry in SibLeaf. We can 1822b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // handle it in two ways: 1823b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // 1. Extend SibLeaf.stop to b and be done, or 1824b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // 2. Extend a to SibLeaf, erase the SibLeaf entry and continue. 1825b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // We prefer 1., but need 2 when coalescing to the right as well. 1826b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Leaf &CurLeaf = P.leaf<Leaf>(); 18275f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen P.moveLeft(P.height()); 1828b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (Traits::stopLess(b, CurLeaf.start(0)) && 1829b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) { 1830b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Easy, just extend SibLeaf and we're done. 18315f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b); 1832b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen return; 1833b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } else { 1834b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // We have both left and right coalescing. Erase the old SibLeaf entry 1835b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // and continue inserting the larger interval. 1836b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen a = SibLeaf.start(SibOfs); 1837055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen treeErase(/* UpdateRoot= */false); 1838b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1839b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1840b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } else { 1841b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // No left sibling means we are at begin(). Update cached bound. 18425f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen this->map->rootBranchStart() = a; 1843b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1844b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1845706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 18465f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen // When we are inserting at the end of a leaf node, we must update stops. 18475f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen unsigned Size = P.leafSize(); 18485f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen bool Grow = P.leafOffset() == Size; 18495f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y); 1850706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1851706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Leaf insertion unsuccessful? Overflow and try again. 18525f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (Size > Leaf::Capacity) { 18535f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen overflow<Leaf>(P.height()); 18545f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen Grow = P.leafOffset() == P.leafSize(); 18555f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y); 18565f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen assert(Size <= Leaf::Capacity && "overflow() didn't make room"); 18578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1858706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1859706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Inserted, update offset and leaf size. 18605f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen P.setSize(P.height(), Size); 1861706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1862706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Insert was the last node entry, update stops. 18635f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (Grow) 18645f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen setNodeStop(P.height(), b); 1865b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen} 18668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1867b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// erase - erase the current interval and move to the next position. 1868b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1869b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1870b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Oleseniterator::erase() { 1871b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMap &IM = *this->map; 1872b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 1873b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen assert(P.valid() && "Cannot erase end()"); 1874b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (this->branched()) 1875b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen return treeErase(); 1876b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IM.rootLeaf().erase(P.leafOffset(), IM.rootSize); 1877b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.setSize(0, --IM.rootSize); 1878b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen} 1879b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 1880b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// treeErase - erase() for a branched tree. 1881b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1882b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1883055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Oleseniterator::treeErase(bool UpdateRoot) { 1884b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMap &IM = *this->map; 1885b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 1886b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Leaf &Node = P.leaf<Leaf>(); 1887b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 1888b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Nodes are not allowed to become empty. 1889b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (P.leafSize() == 1) { 1890b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IM.deleteNode(&Node); 1891b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen eraseNode(IM.height); 1892055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen // Update rootBranchStart if we erased begin(). 1893055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen if (UpdateRoot && IM.branched() && P.valid() && P.atBegin()) 1894055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1895b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen return; 1896b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1897b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 1898b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Erase current entry. 1899b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Node.erase(P.leafOffset(), P.leafSize()); 1900b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen unsigned NewSize = P.leafSize() - 1; 1901b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.setSize(IM.height, NewSize); 1902b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // When we erase the last entry, update stop and move to a legal position. 1903b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (P.leafOffset() == NewSize) { 1904b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen setNodeStop(IM.height, Node.stop(NewSize - 1)); 1905b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.moveRight(IM.height); 1906055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } else if (UpdateRoot && P.atBegin()) 1907055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1908b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen} 1909b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 1910b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// eraseNode - Erase the current node at Level from its parent and move path to 1911b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// the first entry of the next sibling node. 1912b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// The node must be deallocated by the caller. 1913b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// @param Level 1..height, the root node cannot be erased. 1914b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1915b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1916b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Oleseniterator::eraseNode(unsigned Level) { 1917b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen assert(Level && "Cannot erase root node"); 1918b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMap &IM = *this->map; 1919b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 1920b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 1921b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (--Level == 0) { 1922b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IM.rootBranch().erase(P.offset(0), IM.rootSize); 1923b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.setSize(0, --IM.rootSize); 1924b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // If this cleared the root, switch to height=0. 1925b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (IM.empty()) { 1926b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IM.switchRootToLeaf(); 1927b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen this->setRoot(0); 1928b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen return; 1929b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1930b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } else { 1931b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Remove node ref from branch node at Level. 1932b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Branch &Parent = P.node<Branch>(Level); 1933b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (P.size(Level) == 1) { 1934b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Branch node became empty, remove it recursively. 1935b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IM.deleteNode(&Parent); 1936b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen eraseNode(Level); 1937b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } else { 1938b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Branch node won't become empty. 1939b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Parent.erase(P.offset(Level), P.size(Level)); 1940b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen unsigned NewSize = P.size(Level) - 1; 1941b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.setSize(Level, NewSize); 1942b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // If we removed the last branch, update stop and move to a legal pos. 1943b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (P.offset(Level) == NewSize) { 1944b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen setNodeStop(Level, Parent.stop(NewSize - 1)); 1945b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.moveRight(Level); 1946b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1947b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1948b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1949b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Update path cache for the new right sibling position. 1950b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (P.valid()) { 1951b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.reset(Level + 1); 1952b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.offset(Level + 1) = 0; 1953b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 19548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 19558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19566c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// overflow - Distribute entries of the current node evenly among 19576c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// its siblings and ensure that the current node is not full. 19586c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// This may require allocating a new node. 195915658b290817d6f198ab08910a2d754ba11164d1Rafael Espindola/// @tparam NodeT The type of node at Level (Leaf or Branch). 19606c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @param Level path index of the overflowing node. 19616c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @return True when the tree height was changed. 19628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 19636c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesentemplate <typename NodeT> 19646c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesenbool IntervalMap<KeyT, ValT, N, Traits>:: 19656c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Oleseniterator::overflow(unsigned Level) { 1966ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen using namespace IntervalMapImpl; 1967706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen Path &P = this->path; 19688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned CurSize[4]; 19696c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen NodeT *Node[4]; 19708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Nodes = 0; 19718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Elements = 0; 1972706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned Offset = P.offset(Level); 19738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Do we have a left sibling? 1975706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef LeftSib = P.getLeftSibling(Level); 19768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (LeftSib) { 19778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Offset += Elements = CurSize[Nodes] = LeftSib.size(); 19786c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen Node[Nodes++] = &LeftSib.get<NodeT>(); 19798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 19808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19816c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen // Current node. 1982706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen Elements += CurSize[Nodes] = P.size(Level); 1983706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen Node[Nodes++] = &P.node<NodeT>(Level); 19848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Do we have a right sibling? 1986706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef RightSib = P.getRightSibling(Level); 19878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (RightSib) { 1988b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Elements += CurSize[Nodes] = RightSib.size(); 19896c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen Node[Nodes++] = &RightSib.get<NodeT>(); 19908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 19918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Do we need to allocate a new node? 19938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned NewNode = 0; 19946c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen if (Elements + 1 > Nodes * NodeT::Capacity) { 19958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Insert NewNode at the penultimate position, or after a single node. 19968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen NewNode = Nodes == 1 ? 1 : Nodes - 1; 19978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen CurSize[Nodes] = CurSize[NewNode]; 19988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Node[Nodes] = Node[NewNode]; 19998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen CurSize[NewNode] = 0; 200087d8e60505b26960956996550c8b805c81e5b02bDouglas Gregor Node[NewNode] = this->map->template newNode<NodeT>(); 20018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen ++Nodes; 20028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 20038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 20048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Compute the new element distribution. 20058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned NewSize[4]; 20066c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity, 2007ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen CurSize, NewSize, Offset, true); 2008bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen adjustSiblingSizes(Node, Nodes, CurSize, NewSize); 20098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 20108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Move current location to the leftmost node. 20118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (LeftSib) 2012706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.moveLeft(Level); 20138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 20148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Elements have been rearranged, now update node sizes and stops. 20156c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen bool SplitRoot = false; 20168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Pos = 0; 20178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (;;) { 20188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1); 20196c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen if (NewNode && Pos == NewNode) { 20206c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop); 20216c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen Level += SplitRoot; 20226c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen } else { 2023706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.setSize(Level, NewSize[Pos]); 20246c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen setNodeStop(Level, Stop); 20258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 20268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Pos + 1 == Nodes) 20278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen break; 2028706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.moveRight(Level); 20298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen ++Pos; 20308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 20318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 20328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Where was I? Find NewOffset. 20338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen while(Pos != NewOffset.first) { 2034706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.moveLeft(Level); 20358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen --Pos; 20368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2037706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.offset(Level) = NewOffset.second; 20386c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen return SplitRoot; 20398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 20408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 2041cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 2042cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen//--- IntervalMapOverlaps ----// 2043cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 2044cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2045cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two 2046cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// IntervalMaps. The maps may be different, but the KeyT and Traits types 2047cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// should be the same. 2048cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 2049cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// Typical uses: 2050cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 2051cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 1. Test for overlap: 2052cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// bool overlap = IntervalMapOverlaps(a, b).valid(); 2053cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 2054cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 2. Enumerate overlaps: 2055cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... } 2056cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 2057cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesentemplate <typename MapA, typename MapB> 2058cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesenclass IntervalMapOverlaps { 2059ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen typedef typename MapA::KeyType KeyType; 2060cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen typedef typename MapA::KeyTraits Traits; 2061cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen typename MapA::const_iterator posA; 2062cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen typename MapB::const_iterator posB; 2063cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2064cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// advance - Move posA and posB forward until reaching an overlap, or until 2065cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// either meets end. 2066cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// Don't move the iterators if they are already overlapping. 2067cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen void advance() { 20684aec85ae01188f87e45e5e91baab4f303cbcd336Jakob Stoklund Olesen if (!valid()) 20694aec85ae01188f87e45e5e91baab4f303cbcd336Jakob Stoklund Olesen return; 2070d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen 2071d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (Traits::stopLess(posA.stop(), posB.start())) { 2072d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen // A ends before B begins. Catch up. 2073d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen posA.advanceTo(posB.start()); 2074d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start())) 2075d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen return; 2076d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen } else if (Traits::stopLess(posB.stop(), posA.start())) { 2077d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen // B ends before A begins. Catch up. 2078d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen posB.advanceTo(posA.start()); 2079d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start())) 2080d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen return; 2081d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen } else 2082d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen // Already overlapping. 2083d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen return; 2084d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen 2085cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen for (;;) { 2086cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen // Make a.end > b.start. 2087cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen posA.advanceTo(posB.start()); 2088460ee0fd19b13ba4c1410e43d8d253bf34673817Jakob Stoklund Olesen if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start())) 2089cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen return; 2090cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen // Make b.end > a.start. 2091cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen posB.advanceTo(posA.start()); 2092460ee0fd19b13ba4c1410e43d8d253bf34673817Jakob Stoklund Olesen if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start())) 2093cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen return; 2094cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2095cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2096cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2097cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesenpublic: 2098cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b. 2099cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen IntervalMapOverlaps(const MapA &a, const MapB &b) 2100cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen : posA(b.empty() ? a.end() : a.find(b.start())), 21014aec85ae01188f87e45e5e91baab4f303cbcd336Jakob Stoklund Olesen posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); } 2102cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2103cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// valid - Return true if iterator is at an overlap. 2104cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen bool valid() const { 2105cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen return posA.valid() && posB.valid(); 2106cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2107cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2108cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// a - access the left hand side in the overlap. 2109cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen const typename MapA::const_iterator &a() const { return posA; } 2110cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2111cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// b - access the right hand side in the overlap. 2112cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen const typename MapB::const_iterator &b() const { return posB; } 2113cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2114ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen /// start - Beginning of the overlapping interval. 2115ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType start() const { 2116ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType ak = a().start(); 2117ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType bk = b().start(); 2118ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen return Traits::startLess(ak, bk) ? bk : ak; 2119ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen } 2120ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen 2121d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen /// stop - End of the overlapping interval. 2122ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType stop() const { 2123ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType ak = a().stop(); 2124ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType bk = b().stop(); 2125ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen return Traits::startLess(ak, bk) ? ak : bk; 2126ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen } 2127ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen 2128cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// skipA - Move to the next overlap that doesn't involve a(). 2129cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen void skipA() { 2130cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen ++posA; 2131cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen advance(); 2132cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2133cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2134cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// skipB - Move to the next overlap that doesn't involve b(). 2135cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen void skipB() { 2136cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen ++posB; 2137cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen advance(); 2138cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2139cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2140cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// Preincrement - Move to the next overlap. 2141cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen IntervalMapOverlaps &operator++() { 2142cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen // Bump the iterator that ends first. The other one may have more overlaps. 2143460ee0fd19b13ba4c1410e43d8d253bf34673817Jakob Stoklund Olesen if (Traits::startLess(posB.stop(), posA.stop())) 2144cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen skipB(); 2145cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen else 2146cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen skipA(); 2147cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen return *this; 2148cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2149cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2150ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen /// advanceTo - Move to the first overlapping interval with 2151ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen /// stopLess(x, stop()). 2152ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen void advanceTo(KeyType x) { 2153d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (!valid()) 2154d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen return; 2155d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen // Make sure advanceTo sees monotonic keys. 2156d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (Traits::stopLess(posA.stop(), x)) 2157d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen posA.advanceTo(x); 2158d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (Traits::stopLess(posB.stop(), x)) 2159d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen posB.advanceTo(x); 2160ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen advance(); 2161ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen } 2162ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen}; 2163cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 21648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} // namespace llvm 21658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 21668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#endif 2167