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" 1044c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Support/AlignOf.h" 1058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#include "llvm/Support/Allocator.h" 1068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#include "llvm/Support/RecyclingAllocator.h" 1078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#include <iterator> 1088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesennamespace llvm { 1108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//--- Key traits ---// 1148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The IntervalMap works with closed or half-open intervals. 1178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Adjacent intervals that map to the same value are coalesced. 1188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The IntervalMapInfo traits class is used to determine if a key is contained 1208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// in an interval, and if two intervals are adjacent so they can be coalesced. 1218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The provided implementation works for closed integer intervals, other keys 1228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// probably need a specialized version. 1238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x). 1258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// It is assumed that (a;b] half-open intervals are not used, only [a;b) is 1278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// allowed. This is so that stopLess(a, b) can be used to determine if two 1288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// intervals overlap. 1298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename T> 1338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenstruct IntervalMapInfo { 1348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// startLess - Return true if x is not in [a;b]. 1368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is x < a both for closed intervals and for [a;b) half-open intervals. 1378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen static inline bool startLess(const T &x, const T &a) { 1388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return x < a; 1398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// stopLess - Return true if x is not in [a;b]. 1428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals. 1438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen static inline bool stopLess(const T &b, const T &x) { 1448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return b < x; 1458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce. 1488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is a+1 == b for closed intervals, a == b for half-open intervals. 1498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen static inline bool adjacent(const T &a, const T &b) { 1508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return a+1 == b; 1518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 1548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 155edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruthtemplate <typename T> 156edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruthstruct IntervalMapHalfOpenInfo { 157edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth 158edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth /// startLess - Return true if x is not in [a;b). 159edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth static inline bool startLess(const T &x, const T &a) { 160edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth return x < a; 161edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth } 162edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth 163edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth /// stopLess - Return true if x is not in [a;b). 164edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth static inline bool stopLess(const T &b, const T &x) { 165edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth return b <= x; 166edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth } 167edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth 168edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth /// adjacent - Return true when the intervals [x;a) and [b;y) can coalesce. 169edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth static inline bool adjacent(const T &a, const T &b) { 170edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth return a == b; 171edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth } 172edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth 173edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth}; 174edf315cd71334d5a7af31f4b882235d03b06f24dChandler Carruth 1758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// IntervalMapImpl - Namespace used for IntervalMap implementation details. 1768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// It should be considered private to the implementation. 1778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesennamespace IntervalMapImpl { 1788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Forward declarations. 1808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename, typename, unsigned, typename> class LeafNode; 1818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename, typename, unsigned, typename> class BranchNode; 1828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentypedef std::pair<unsigned,unsigned> IdxPair; 1848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 187bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::NodeBase ---// 1888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 190a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen// Both leaf and branch nodes store vectors of pairs. 191a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen// Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT). 1928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Keys and values are stored in separate arrays to avoid padding caused by 1948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// different object alignments. This also helps improve locality of reference 1958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// when searching the keys. 1968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The nodes don't know how many elements they contain - that information is 1988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// stored elsewhere. Omitting the size field prevents padding and allows a node 1998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// to fill the allocated cache lines completely. 2008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 2018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// These are typical key and value sizes, the node branching factor (N), and 2028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// wasted space when nodes are sized to fit in three cache lines (192 bytes): 2038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 204a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen// T1 T2 N Waste Used by 2058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4 4 24 0 Branch<4> (32-bit pointers) 206a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen// 8 4 16 0 Leaf<4,4>, Branch<4> 2078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 8 8 12 0 Leaf<4,8>, Branch<8> 2088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 16 4 9 12 Leaf<8,4> 2098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 16 8 8 0 Leaf<8,8> 2108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 2118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 2128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 213a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesentemplate <typename T1, typename T2, unsigned N> 2148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass NodeBase { 2158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 2168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen enum { Capacity = N }; 2178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 218a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen T1 first[N]; 219a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen T2 second[N]; 2208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 2218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// copy - Copy elements from another node. 22233fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Other Node elements are copied from. 2238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Beginning of the source range in other. 2248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param j Beginning of the destination range in this. 22533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Count Number of elements to copy. 2268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen template <unsigned M> 227a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen void copy(const NodeBase<T1, T2, M> &Other, unsigned i, 2288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned j, unsigned Count) { 2298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i + Count <= M && "Invalid source range"); 2308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(j + Count <= N && "Invalid dest range"); 23108d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen for (unsigned e = i + Count; i != e; ++i, ++j) { 23208d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen first[j] = Other.first[i]; 23308d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen second[j] = Other.second[i]; 23408d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen } 2358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 23733fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// moveLeft - Move elements to the left. 2388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Beginning of the source range. 2398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param j Beginning of the destination range. 24033fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Count Number of elements to copy. 24133fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen void moveLeft(unsigned i, unsigned j, unsigned Count) { 24233fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen assert(j <= i && "Use moveRight shift elements right"); 2438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen copy(*this, i, j, Count); 2448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 24633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// moveRight - Move elements to the right. 2478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Beginning of the source range. 2488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param j Beginning of the destination range. 24933fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Count Number of elements to copy. 25033fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen void moveRight(unsigned i, unsigned j, unsigned Count) { 25133fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen assert(i <= j && "Use moveLeft shift elements left"); 2528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(j + Count <= N && "Invalid range"); 25308d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen while (Count--) { 25408d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen first[j + Count] = first[i + Count]; 25508d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen second[j + Count] = second[i + Count]; 25608d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen } 2578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 2598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// erase - Erase elements [i;j). 2608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Beginning of the range to erase. 2618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param j End of the range. (Exclusive). 26233fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in node. 2638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void erase(unsigned i, unsigned j, unsigned Size) { 26433fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen moveLeft(j, i, Size - j); 2658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 267b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen /// erase - Erase element at i. 268b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen /// @param i Index of element to erase. 269b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen /// @param Size Number of elements in node. 270b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen void erase(unsigned i, unsigned Size) { 271b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen erase(i, i+1, Size); 272b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 273b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 2748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// shift - Shift elements [i;size) 1 position to the right. 2758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Beginning of the range to move. 27633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in node. 2778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void shift(unsigned i, unsigned Size) { 27833fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen moveRight(i, i + 1, Size - i); 2798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 28133fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// transferToLeftSib - Transfer elements to a left sibling node. 28233fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in this. 28333fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Sib Left sibling node. 28433fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param SSize Number of elements in sib. 28533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Count Number of elements to transfer. 28633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, 28733fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen unsigned Count) { 2888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Sib.copy(*this, 0, SSize, Count); 2898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen erase(0, Count, Size); 2908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 29233fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// transferToRightSib - Transfer elements to a right sibling node. 29333fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in this. 29433fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Sib Right sibling node. 29533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param SSize Number of elements in sib. 29633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Count Number of elements to transfer. 29733fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize, 29833fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen unsigned Count) { 29933fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen Sib.moveRight(0, Count, SSize); 3008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Sib.copy(*this, Size-Count, 0, Count); 3018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 3028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 30333fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// adjustFromLeftSib - Adjust the number if elements in this node by moving 3048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// elements to or from a left sibling node. 30533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in this. 30633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Sib Right sibling node. 30733fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param SSize Number of elements in sib. 30833fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Add The number of elements to add to this node, possibly < 0. 3098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return Number of elements added to this node, possibly negative. 31033fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) { 3118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Add > 0) { 3128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We want to grow, copy from sib. 3138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size); 31433fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen Sib.transferToRightSib(SSize, *this, Size, Count); 3158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return Count; 3168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } else { 3178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We want to shrink, copy to sib. 3188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize); 31933fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen transferToLeftSib(Size, Sib, SSize, Count); 3208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return -Count; 3218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 3228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 3238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 3248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 325bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen/// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes. 326bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Node Array of pointers to sibling nodes. 327bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Nodes Number of nodes. 328bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param CurSize Array of current node sizes, will be overwritten. 329bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param NewSize Array of desired node sizes. 330bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesentemplate <typename NodeT> 331bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesenvoid adjustSiblingSizes(NodeT *Node[], unsigned Nodes, 332bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen unsigned CurSize[], const unsigned NewSize[]) { 333bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen // Move elements right. 334bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen for (int n = Nodes - 1; n; --n) { 335b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (CurSize[n] == NewSize[n]) 336bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen continue; 337bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen for (int m = n - 1; m != -1; --m) { 338bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m], 339bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen NewSize[n] - CurSize[n]); 340bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen CurSize[m] -= d; 341bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen CurSize[n] += d; 342bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen // Keep going if the current node was exhausted. 343bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen if (CurSize[n] >= NewSize[n]) 344bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen break; 345bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen } 346bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen } 347bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen 348bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen if (Nodes == 0) 349bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen return; 350bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen 351bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen // Move elements left. 352bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen for (unsigned n = 0; n != Nodes - 1; ++n) { 353bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen if (CurSize[n] == NewSize[n]) 354bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen continue; 355bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen for (unsigned m = n + 1; m != Nodes; ++m) { 356bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n], 357bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen CurSize[n] - NewSize[n]); 358bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen CurSize[m] += d; 359bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen CurSize[n] -= d; 360bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen // Keep going if the current node was exhausted. 361bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen if (CurSize[n] >= NewSize[n]) 362bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen break; 363bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen } 364bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen } 365bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen 366bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen#ifndef NDEBUG 367bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen for (unsigned n = 0; n != Nodes; n++) 368bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle"); 369bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen#endif 370bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen} 371bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen 372bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen/// IntervalMapImpl::distribute - Compute a new distribution of node elements 373bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen/// after an overflow or underflow. Reserve space for a new element at Position, 374bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen/// and compute the node that will hold Position after redistributing node 375bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen/// elements. 376bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 377bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// It is required that 378bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 379bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// Elements == sum(CurSize), and 380bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// Elements + Grow <= Nodes * Capacity. 381bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 382bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// NewSize[] will be filled in such that: 383bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 384bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// sum(NewSize) == Elements, and 385bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// NewSize[i] <= Capacity. 386bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 387bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// The returned index is the node where Position will go, so: 388bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 389bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// sum(NewSize[0..idx-1]) <= Position 390bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// sum(NewSize[0..idx]) >= Position 391bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 392bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// The last equality, sum(NewSize[0..idx]) == Position, can only happen when 393bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// Grow is set and NewSize[idx] == Capacity-1. The index points to the node 394bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// before the one holding the Position'th element where there is room for an 395bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// insertion. 396bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 397bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Nodes The number of nodes. 398bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Elements Total elements in all nodes. 399bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Capacity The capacity of each node. 400bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param CurSize Array[Nodes] of current node sizes, or NULL. 401bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param NewSize Array[Nodes] to receive the new node sizes. 402bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Position Insert position. 403bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Grow Reserve space for a new element at Position. 404bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @return (node, offset) for Position. 405bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund OlesenIdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, 406bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen const unsigned *CurSize, unsigned NewSize[], 407bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen unsigned Position, bool Grow); 408bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen 4098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 411bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::NodeSizer ---// 4128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Compute node sizes from key and value types. 4158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The branching factors are chosen to make nodes fit in three cache lines. 4178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// This may not be possible if keys or values are very large. Such large objects 4188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// are handled correctly, but a std::map would probably give better performance. 4198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenenum { 4238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Cache line size. Most architectures have 32 or 64 byte cache lines. 4248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We use 64 bytes here because it provides good branching factors. 4258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Log2CacheLine = 6, 4268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen CacheLineBytes = 1 << Log2CacheLine, 4278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen DesiredNodeBytes = 3 * CacheLineBytes 4288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 4298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT> 4318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenstruct NodeSizer { 4328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen enum { 4338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Compute the leaf node branching factor that makes a node fit in three 4348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // cache lines. The branching factor must be at least 3, or some B+-tree 4358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // balancing algorithms won't work. 4368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // LeafSize can't be larger than CacheLineBytes. This is required by the 4378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // PointerIntPair used by NodeRef. 4388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen DesiredLeafSize = DesiredNodeBytes / 4398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)), 4408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen MinLeafSize = 3, 441528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize 442528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen }; 443528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen 444528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen typedef NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize> LeafBase; 4458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 446528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen enum { 4478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Now that we have the leaf branching factor, compute the actual allocation 4488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // unit size by rounding up to a whole number of cache lines. 449528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1), 4508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Determine the branching factor for branch nodes. 4528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen BranchSize = AllocBytes / 4538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen static_cast<unsigned>(sizeof(KeyT) + sizeof(void*)) 4548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen }; 4558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// Allocator - The recycling allocator used for both branch and leaf nodes. 4578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This typedef is very likely to be identical for all IntervalMaps with 4588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// reasonably sized entries, so the same allocator can be shared among 4598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// different kinds of maps. 4608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen typedef RecyclingAllocator<BumpPtrAllocator, char, 4618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen AllocBytes, CacheLineBytes> Allocator; 4628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 4648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 467bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::NodeRef ---// 4688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// B+-tree nodes can be leaves or branches, so we need a polymorphic node 4718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// pointer that can point to both kinds. 4728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// All nodes are cache line aligned and the low 6 bits of a node pointer are 4748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// always 0. These bits are used to store the number of elements in the 4758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// referenced node. Besides saving space, placing node sizes in the parents 4768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// allow tree balancing algorithms to run without faulting cache lines for nodes 4778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// that may not need to be modified. 4788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// A NodeRef doesn't know whether it references a leaf node or a branch node. 4808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// It is the responsibility of the caller to use the correct types. 4818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Nodes are never supposed to be empty, and it is invalid to store a node size 4838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// of 0 in a NodeRef. The valid range of sizes is 1-64. 4848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass NodeRef { 488bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen struct CacheAlignedPointerTraits { 489bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen static inline void *getAsVoidPointer(void *P) { return P; } 490bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen static inline void *getFromVoidPointer(void *P) { return P; } 491bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen enum { NumLowBitsAvailable = Log2CacheLine }; 492bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen }; 4938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip; 4948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 4968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// NodeRef - Create a null ref. 4978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen NodeRef() {} 4988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// operator bool - Detect a null ref. 500ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines explicit operator bool() const { return pip.getOpaqueValue(); } 5018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 502ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen /// NodeRef - Create a reference to the node p with n elements. 503ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen template <typename NodeT> 504ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) { 505ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen assert(n <= NodeT::Capacity && "Size too big for node"); 506ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen } 5078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// size - Return the number of elements in the referenced node. 5098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned size() const { return pip.getInt() + 1; } 5108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// setSize - Update the node size. 5128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void setSize(unsigned n) { pip.setInt(n - 1); } 5138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 514ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen /// subtree - Access the i'th subtree reference in a branch node. 515ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen /// This depends on branch nodes storing the NodeRef array as their first 516ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen /// member. 517706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef &subtree(unsigned i) const { 518ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen return reinterpret_cast<NodeRef*>(pip.getPointer())[i]; 5198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 521ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen /// get - Dereference as a NodeT reference. 522ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen template <typename NodeT> 523ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NodeT &get() const { 524ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen return *reinterpret_cast<NodeT*>(pip.getPointer()); 5258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool operator==(const NodeRef &RHS) const { 5288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (pip == RHS.pip) 5298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return true; 5308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs"); 5318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return false; 5328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool operator!=(const NodeRef &RHS) const { 5358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return !operator==(RHS); 5368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 5388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 540bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::LeafNode ---// 5418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 5428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 5438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Leaf nodes store up to N disjoint intervals with corresponding values. 5448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 5458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The intervals are kept sorted and fully coalesced so there are no adjacent 5468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// intervals mapping to the same value. 5478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 5488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// These constraints are always satisfied: 5498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 550ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen// - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals. 5518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 552ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen// - Traits::stopLess(stop(i), start(i + 1) - Sorted. 5538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 554ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen// - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1)) 555ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen// - Fully coalesced. 5568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 5578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 5588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 5608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> { 5618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 562a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen const KeyT &start(unsigned i) const { return this->first[i].first; } 563a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen const KeyT &stop(unsigned i) const { return this->first[i].second; } 564a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen const ValT &value(unsigned i) const { return this->second[i]; } 5658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 566a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen KeyT &start(unsigned i) { return this->first[i].first; } 567a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen KeyT &stop(unsigned i) { return this->first[i].second; } 568a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen ValT &value(unsigned i) { return this->second[i]; } 5698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// findFrom - Find the first interval after i that may contain x. 5718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Starting index for the search. 57233fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in node. 5738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 5748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return First index with !stopLess(key[i].stop, x), or size. 5758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is the first interval that can possibly contain x. 5768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { 5778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i <= Size && Size <= N && "Bad indices"); 5788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 5798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen "Index is past the needed point"); 5808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen while (i != Size && Traits::stopLess(stop(i), x)) ++i; 5818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return i; 5828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// safeFind - Find an interval that is known to exist. This is the same as 5858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// findFrom except is it assumed that x is at least within range of the last 5868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// interval. 5878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Starting index for the search. 5888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 5898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return First index with !stopLess(key[i].stop, x), never size. 5908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is the first interval that can possibly contain x. 5918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned safeFind(unsigned i, KeyT x) const { 5928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i < N && "Bad index"); 5938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 5948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen "Index is past the needed point"); 5958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen while (Traits::stopLess(stop(i), x)) ++i; 5968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i < N && "Unsafe intervals"); 5978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return i; 5988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// safeLookup - Lookup mapped value for a safe key. 6018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// It is assumed that x is within range of the last entry. 6028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 6038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param NotFound Value to return if x is not in any interval. 6048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return The mapped value at x or NotFound. 6058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen ValT safeLookup(KeyT x, ValT NotFound) const { 6068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned i = safeFind(0, x); 6078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return Traits::startLess(x, start(i)) ? NotFound : value(i); 6088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 6098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6105f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y); 6118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 6128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as 6148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// possible. This may cause the node to grow by 1, or it may cause the node 6158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// to shrink because of coalescing. 61615658b290817d6f198ab08910a2d754ba11164d1Rafael Espindola/// @param Pos Starting index = insertFrom(0, size, a) 61733fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen/// @param Size Number of elements in node. 6188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// @param a Interval start. 6198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// @param b Interval stop. 6208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// @param y Value be mapped. 6218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// @return (insert position, new size), or (i, Capacity+1) on overflow. 6228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 6235f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesenunsigned LeafNode<KeyT, ValT, N, Traits>:: 6245f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund OleseninsertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) { 6255f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen unsigned i = Pos; 6268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i <= Size && Size <= N && "Invalid index"); 6278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(!Traits::stopLess(b, a) && "Invalid interval"); 6288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Verify the findFrom invariant. 6308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == 0 || Traits::stopLess(stop(i - 1), a))); 6318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == Size || !Traits::stopLess(stop(i), a))); 6325f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert"); 6338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Coalesce with previous interval. 6355f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) { 6365f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen Pos = i - 1; 6375f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen // Also coalesce with next interval? 6385f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) { 6395f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen stop(i - 1) = stop(i); 6405f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen this->erase(i, Size); 6415f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return Size - 1; 6425f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen } 6435f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen stop(i - 1) = b; 6445f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return Size; 6455f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen } 6468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Detect overflow. 6488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (i == N) 6495f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return N + 1; 6508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Add new interval at end. 6528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (i == Size) { 6538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen start(i) = a; 6548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen stop(i) = b; 6558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen value(i) = y; 6565f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return Size + 1; 6578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 6588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Try to coalesce with following interval. 6608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (value(i) == y && Traits::adjacent(b, start(i))) { 6618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen start(i) = a; 6625f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return Size; 6638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 6648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We must insert before i. Detect overflow. 6668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Size == N) 6675f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return N + 1; 6688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Insert before i. 6708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen this->shift(i, Size); 6718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen start(i) = a; 6728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen stop(i) = b; 6738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen value(i) = y; 6745f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return Size + 1; 6758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 6768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 679bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::BranchNode ---// 6808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 6818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 6828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// A branch node stores references to 1--N subtrees all of the same height. 6838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 6848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The key array in a branch node holds the rightmost stop key of each subtree. 6858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// It is redundant to store the last stop key since it can be found in the 6868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// parent node, but doing so makes tree balancing a lot simpler. 6878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 6888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// It is unusual for a branch node to only have one subtree, but it can happen 6898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// in the root node if it is smaller than the normal nodes. 6908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 6918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// When all of the leaf nodes from all the subtrees are concatenated, they must 6928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// satisfy the same constraints as a single leaf node. They must be sorted, 6938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// sane, and fully coalesced. 6948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 6958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 6968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 698ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesenclass BranchNode : public NodeBase<NodeRef, KeyT, N> { 6998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 700a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen const KeyT &stop(unsigned i) const { return this->second[i]; } 701ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen const NodeRef &subtree(unsigned i) const { return this->first[i]; } 7028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 703a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen KeyT &stop(unsigned i) { return this->second[i]; } 704ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NodeRef &subtree(unsigned i) { return this->first[i]; } 7058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 7068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// findFrom - Find the first subtree after i that may contain x. 7078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Starting index for the search. 70833fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in node. 7098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 7108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return First index with !stopLess(key[i], x), or size. 7118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is the first subtree that can possibly contain x. 7128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { 7138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i <= Size && Size <= N && "Bad indices"); 7148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 7158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen "Index to findFrom is past the needed point"); 7168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen while (i != Size && Traits::stopLess(stop(i), x)) ++i; 7178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return i; 7188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 7198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 7208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// safeFind - Find a subtree that is known to exist. This is the same as 7218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// findFrom except is it assumed that x is in range. 7228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Starting index for the search. 7238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 7248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return First index with !stopLess(key[i], x), never size. 7258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is the first subtree that can possibly contain x. 7268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned safeFind(unsigned i, KeyT x) const { 7278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i < N && "Bad index"); 7288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 7298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen "Index is past the needed point"); 7308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen while (Traits::stopLess(stop(i), x)) ++i; 7318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i < N && "Unsafe intervals"); 7328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return i; 7338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 7348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 7358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// safeLookup - Get the subtree containing x, Assuming that x is in range. 7368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 7378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return Subtree containing x 738ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NodeRef safeLookup(KeyT x) const { 7398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return subtree(safeFind(0, x)); 7408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 7418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 7428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// insert - Insert a new (subtree, stop) pair. 7438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Insert position, following entries will be shifted. 74433fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in node. 74533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Node Subtree to insert. 74633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Stop Last key in subtree. 747ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) { 7488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(Size < N && "branch node overflow"); 7498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i <= Size && "Bad insert position"); 7508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen this->shift(i, Size); 7518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen subtree(i) = Node; 7528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen stop(i) = Stop; 7538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 7548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 7558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 756706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 757bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::Path ---// 758706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 759706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// 760706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// A Path is used by iterators to represent a position in a B+-tree, and the 761706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// path to get there from the root. 762706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// 763ab26da9e679afb26b6af589c2d414d50bf4a6441Lang Hames// The Path class also contains the tree navigation code that doesn't have to 764706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// be templatized. 765706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// 766706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 767706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 768706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesenclass Path { 769706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// Entry - Each step in the path is a node pointer and an offset into that 770706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// node. 771706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen struct Entry { 772706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void *node; 773706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned size; 774706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned offset; 775706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 776706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen Entry(void *Node, unsigned Size, unsigned Offset) 777706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen : node(Node), size(Size), offset(Offset) {} 778706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 779706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen Entry(NodeRef Node, unsigned Offset) 780706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {} 781706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 782706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef &subtree(unsigned i) const { 783706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return reinterpret_cast<NodeRef*>(node)[i]; 784706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 785706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen }; 786706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 787706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// path - The path entries, path[0] is the root node, path.back() is a leaf. 788706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen SmallVector<Entry, 4> path; 789706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 790706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesenpublic: 791706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Node accessors. 792706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen template <typename NodeT> NodeT &node(unsigned Level) const { 793706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return *reinterpret_cast<NodeT*>(path[Level].node); 794706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 795706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned size(unsigned Level) const { return path[Level].size; } 796706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned offset(unsigned Level) const { return path[Level].offset; } 797706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned &offset(unsigned Level) { return path[Level].offset; } 798706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 799706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Leaf accessors. 800706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen template <typename NodeT> NodeT &leaf() const { 801706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return *reinterpret_cast<NodeT*>(path.back().node); 802706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 803706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned leafSize() const { return path.back().size; } 804706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned leafOffset() const { return path.back().offset; } 805706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned &leafOffset() { return path.back().offset; } 806706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 807706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// valid - Return true if path is at a valid node, not at end(). 808706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen bool valid() const { 809706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return !path.empty() && path.front().offset < path.front().size; 810706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 811706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 812706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// height - Return the height of the tree corresponding to this path. 813706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// This matches map->height in a full path. 814706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned height() const { return path.size() - 1; } 815706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 816706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// subtree - Get the subtree referenced from Level. When the path is 817706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// consistent, node(Level + 1) == subtree(Level). 818706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level 0..height-1. The leaves have no subtrees. 819706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef &subtree(unsigned Level) const { 820706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return path[Level].subtree(path[Level].offset); 821706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 822706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 82353bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen /// reset - Reset cached information about node(Level) from subtree(Level -1). 82453bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen /// @param Level 1..height. THe node to update after parent node changed. 82553bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen void reset(unsigned Level) { 82653bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen path[Level] = Entry(subtree(Level - 1), offset(Level)); 82753bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen } 82853bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen 829706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// push - Add entry to path. 830706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Node Node to add, should be subtree(path.size()-1). 831706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Offset Offset into Node. 832706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void push(NodeRef Node, unsigned Offset) { 833706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.push_back(Entry(Node, Offset)); 834706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 835706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 836180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen /// pop - Remove the last path entry. 837180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen void pop() { 838180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.pop_back(); 839180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 840180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen 841706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// setSize - Set the size of a node both in the path and in the tree. 842706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level 0..height. Note that setting the root size won't change 843706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// map->rootSize. 844706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Size New node size. 845706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void setSize(unsigned Level, unsigned Size) { 846706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path[Level].size = Size; 847706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (Level) 848706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen subtree(Level - 1).setSize(Size); 849706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 850706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 851706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// setRoot - Clear the path and set a new root node. 852706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Node New root node. 853706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Size New root size. 854706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Offset Offset into root node. 855706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void setRoot(void *Node, unsigned Size, unsigned Offset) { 856706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.clear(); 857706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.push_back(Entry(Node, Size, Offset)); 858706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 859706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 860706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// replaceRoot - Replace the current root node with two new entries after the 861706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// tree height has increased. 862706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Root The new root node. 863706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Size Number of entries in the new root. 864706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Offsets Offsets into the root and first branch nodes. 865706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void replaceRoot(void *Root, unsigned Size, IdxPair Offsets); 866706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 867706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 868706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level Get the sibling to node(Level). 869706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @return Left sibling, or NodeRef(). 870706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef getLeftSibling(unsigned Level) const; 871706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 872706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level 873706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// unaltered. 874706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level Move node(Level). 875706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void moveLeft(unsigned Level); 876706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 877706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// fillLeft - Grow path to Height by taking leftmost branches. 878706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Height The target height. 879706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void fillLeft(unsigned Height) { 880706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen while (height() < Height) 881706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen push(subtree(height()), 0); 882706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 883706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 884706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 885706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level Get the sinbling to node(Level). 886706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @return Left sibling, or NodeRef(). 887706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef getRightSibling(unsigned Level) const; 888706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 889706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// moveRight - Move path to the left sibling at Level. Leave nodes below 890706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// Level unaltered. 891706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level Move node(Level). 892706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void moveRight(unsigned Level); 893706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 894055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen /// atBegin - Return true if path is at begin(). 895055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen bool atBegin() const { 896055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen for (unsigned i = 0, e = path.size(); i != e; ++i) 897055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen if (path[i].offset != 0) 898055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return false; 899055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return true; 900055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } 901055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 9027a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// atLastEntry - Return true if the path is at the last entry of the node at 9037a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// Level. 904706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level Node to examine. 9057a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen bool atLastEntry(unsigned Level) const { 906706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return path[Level].offset == path[Level].size - 1; 907706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 908706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 909706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// legalizeForInsert - Prepare the path for an insertion at Level. When the 910706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// path is at end(), node(Level) may not be a legal node. legalizeForInsert 911706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// ensures that node(Level) is real by moving back to the last node at Level, 912706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// and setting offset(Level) to size(Level) if required. 913706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level The level where an insertion is about to take place. 914706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void legalizeForInsert(unsigned Level) { 915706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (valid()) 916706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return; 917706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen moveLeft(Level); 918706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen ++path[Level].offset; 919706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 920706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen}; 921706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 9228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} // namespace IntervalMapImpl 9238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 9268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//--- IntervalMap ----// 9278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 9288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, 9308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize, 9318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen typename Traits = IntervalMapInfo<KeyT> > 9328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass IntervalMap { 933ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen typedef IntervalMapImpl::NodeSizer<KeyT, ValT> Sizer; 934ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen typedef IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits> Leaf; 935ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen typedef IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits> 936ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen Branch; 9378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf; 9388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen typedef IntervalMapImpl::IdxPair IdxPair; 9398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // The RootLeaf capacity is given as a template parameter. We must compute the 9418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // corresponding RootBranch capacity. 9428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen enum { 9438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) / 944ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)), 9458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1 9468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen }; 9478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 948ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits> 949ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen RootBranch; 9508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // When branched, we store a global start key as well as the branch node. 9528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen struct RootBranchData { 9538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT start; 9548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootBranch node; 9558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen }; 9568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 958ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen typedef typename Sizer::Allocator Allocator; 959ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen typedef KeyT KeyType; 960ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen typedef ValT ValueType; 961cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen typedef Traits KeyTraits; 9628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenprivate: 9648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // The root data is either a RootLeaf or a RootBranchData instance. 9654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar AlignedCharArrayUnion<RootLeaf, RootBranchData> data; 9668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Tree height. 9688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // 0: Leaves in root. 9698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // 1: Root points to leaf. 9708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // 2: root->branch->leaf ... 9718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned height; 9728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Number of entries in the root node. 9748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned rootSize; 9758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Allocator used for creating external nodes. 9778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Allocator &allocator; 9788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// dataAs - Represent data as a node type without breaking aliasing rules. 9808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen template <typename T> 9818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen T &dataAs() const { 9828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen union { 9838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const char *d; 9848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen T *t; 9858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } u; 9864c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar u.d = data.buffer; 9878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return *u.t; 9888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 9898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const RootLeaf &rootLeaf() const { 9918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(!branched() && "Cannot acces leaf data in branched root"); 9928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return dataAs<RootLeaf>(); 9938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 9948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootLeaf &rootLeaf() { 9958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(!branched() && "Cannot acces leaf data in branched root"); 9968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return dataAs<RootLeaf>(); 9978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 9988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootBranchData &rootBranchData() const { 9998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(branched() && "Cannot access branch data in non-branched root"); 10008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return dataAs<RootBranchData>(); 10018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootBranchData &rootBranchData() { 10038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(branched() && "Cannot access branch data in non-branched root"); 10048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return dataAs<RootBranchData>(); 10058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const RootBranch &rootBranch() const { return rootBranchData().node; } 10078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootBranch &rootBranch() { return rootBranchData().node; } 10088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT rootBranchStart() const { return rootBranchData().start; } 10098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT &rootBranchStart() { return rootBranchData().start; } 10108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1011b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen template <typename NodeT> NodeT *newNode() { 1012b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen return new(allocator.template Allocate<NodeT>()) NodeT(); 10138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1015b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen template <typename NodeT> void deleteNode(NodeT *P) { 1016b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P->~NodeT(); 10178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen allocator.Deallocate(P); 10188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IdxPair branchRoot(unsigned Position); 10218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IdxPair splitRoot(unsigned Position); 10228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void switchRootToBranch() { 10248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootLeaf().~RootLeaf(); 10258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen height = 1; 10268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen new (&rootBranchData()) RootBranchData(); 10278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void switchRootToLeaf() { 10308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootBranchData().~RootBranchData(); 10318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen height = 0; 10328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen new(&rootLeaf()) RootLeaf(); 10338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool branched() const { return height > 0; } 10368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen ValT treeSafeLookup(KeyT x, ValT NotFound) const; 1038ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, 1039ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen unsigned Level)); 1040ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level); 10418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 10438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) { 10444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar assert((uintptr_t(data.buffer) & (alignOf<RootLeaf>() - 1)) == 0 && 10458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen "Insufficient alignment"); 10468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen new(&rootLeaf()) RootLeaf(); 10478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1049785ab18a054373f1a2f8d0f6f04db2d458878bd9Jakob Stoklund Olesen ~IntervalMap() { 1050785ab18a054373f1a2f8d0f6f04db2d458878bd9Jakob Stoklund Olesen clear(); 1051785ab18a054373f1a2f8d0f6f04db2d458878bd9Jakob Stoklund Olesen rootLeaf().~RootLeaf(); 1052785ab18a054373f1a2f8d0f6f04db2d458878bd9Jakob Stoklund Olesen } 1053785ab18a054373f1a2f8d0f6f04db2d458878bd9Jakob Stoklund Olesen 10548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// empty - Return true when no intervals are mapped. 10558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool empty() const { 10568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return rootSize == 0; 10578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// start - Return the smallest mapped key in a non-empty map. 10608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT start() const { 10618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(!empty() && "Empty IntervalMap has no start"); 10628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return !branched() ? rootLeaf().start(0) : rootBranchStart(); 10638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// stop - Return the largest mapped key in a non-empty map. 10668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT stop() const { 10678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(!empty() && "Empty IntervalMap has no stop"); 10688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return !branched() ? rootLeaf().stop(rootSize - 1) : 10698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootBranch().stop(rootSize - 1); 10708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// lookup - Return the mapped value at x or NotFound. 10738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen ValT lookup(KeyT x, ValT NotFound = ValT()) const { 10748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x)) 10758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return NotFound; 10768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return branched() ? treeSafeLookup(x, NotFound) : 10778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootLeaf().safeLookup(x, NotFound); 10788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals. 10818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// It is assumed that no key in the interval is mapped to another value, but 10828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// overlapping intervals already mapped to y will be coalesced. 10838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void insert(KeyT a, KeyT b, ValT y) { 108479283768a36746bcb5885746637752312af9e4acJakob Stoklund Olesen if (branched() || rootSize == RootLeaf::Capacity) 108579283768a36746bcb5885746637752312af9e4acJakob Stoklund Olesen return find(a).insert(a, b, y); 108679283768a36746bcb5885746637752312af9e4acJakob Stoklund Olesen 108779283768a36746bcb5885746637752312af9e4acJakob Stoklund Olesen // Easy insert into root leaf. 108879283768a36746bcb5885746637752312af9e4acJakob Stoklund Olesen unsigned p = rootLeaf().findFrom(0, rootSize, a); 10895f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y); 10908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1092655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen /// clear - Remove all entries. 1093655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen void clear(); 1094655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen 10958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen class const_iterator; 10968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen class iterator; 10978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen friend class const_iterator; 10988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen friend class iterator; 10998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator begin() const { 1101da2fdcbb639de168738c27089bafa9ca10b731bdJakob Stoklund Olesen const_iterator I(*this); 11028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.goToBegin(); 11038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator begin() { 11078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator I(*this); 11088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.goToBegin(); 11098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator end() const { 1113da2fdcbb639de168738c27089bafa9ca10b731bdJakob Stoklund Olesen const_iterator I(*this); 11148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.goToEnd(); 11158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator end() { 11198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator I(*this); 11208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.goToEnd(); 11218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// find - Return an iterator pointing to the first interval ending at or 11258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// after x, or end(). 11268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator find(KeyT x) const { 1127da2fdcbb639de168738c27089bafa9ca10b731bdJakob Stoklund Olesen const_iterator I(*this); 11288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.find(x); 11298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator find(KeyT x) { 11338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator I(*this); 11348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.find(x); 11358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 11388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// treeSafeLookup - Return the mapped value at x or NotFound, assuming a 11408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// branched root. 11418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 11428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesenValT IntervalMap<KeyT, ValT, N, Traits>:: 11438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesentreeSafeLookup(KeyT x, ValT NotFound) const { 11448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(branched() && "treeLookup assumes a branched root"); 11458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1146ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x); 11478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned h = height-1; h; --h) 1148ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NR = NR.get<Branch>().safeLookup(x); 1149ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen return NR.get<Leaf>().safeLookup(x, NotFound); 11508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 11518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// branchRoot - Switch from a leaf root to a branched root. 11548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Return the new (root offset, node offset) corresponding to Position. 11558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 11568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesenIntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 11578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesenbranchRoot(unsigned Position) { 1158ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen using namespace IntervalMapImpl; 11598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // How many external leaf nodes to hold RootLeaf+1? 11608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1; 11618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Compute element distribution among new nodes. 11638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned size[Nodes]; 11648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IdxPair NewOffset(0, Position); 11658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Is is very common for the root node to be smaller than external nodes. 11678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Nodes == 1) 11688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen size[0] = rootSize; 11698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1170dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, size, 11718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Position, true); 11728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Allocate new nodes. 11748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned pos = 0; 11758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen NodeRef node[Nodes]; 11768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned n = 0; n != Nodes; ++n) { 1177b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Leaf *L = newNode<Leaf>(); 1178b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen L->copy(rootLeaf(), pos, 0, size[n]); 1179b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen node[n] = NodeRef(L, size[n]); 11808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen pos += size[n]; 11818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Destroy the old leaf node, construct branch node instead. 11848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen switchRootToBranch(); 11858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned n = 0; n != Nodes; ++n) { 1186ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1); 11878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootBranch().subtree(n) = node[n]; 11888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1189ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen rootBranchStart() = node[0].template get<Leaf>().start(0); 11908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootSize = Nodes; 11918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return NewOffset; 11928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 11938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// splitRoot - Split the current BranchRoot into multiple Branch nodes. 11958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Return the new (root offset, node offset) corresponding to Position. 11968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 11978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesenIntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 11988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesensplitRoot(unsigned Position) { 1199ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen using namespace IntervalMapImpl; 12008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // How many external leaf nodes to hold RootBranch+1? 12018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1; 12028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Compute element distribution among new nodes. 12048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Size[Nodes]; 12058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IdxPair NewOffset(0, Position); 12068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Is is very common for the root node to be smaller than external nodes. 12088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Nodes == 1) 12098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Size[0] = rootSize; 12108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1211dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, Size, 12128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Position, true); 12138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Allocate new nodes. 12158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Pos = 0; 12168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen NodeRef Node[Nodes]; 12178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned n = 0; n != Nodes; ++n) { 1218b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Branch *B = newNode<Branch>(); 1219b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen B->copy(rootBranch(), Pos, 0, Size[n]); 1220b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Node[n] = NodeRef(B, Size[n]); 12218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Pos += Size[n]; 12228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 12238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned n = 0; n != Nodes; ++n) { 1225ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1); 12268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootBranch().subtree(n) = Node[n]; 12278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 12288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootSize = Nodes; 12296c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen ++height; 12308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return NewOffset; 12318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 12328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// visitNodes - Visit each external node. 12348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 12358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1236ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund OlesenvisitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) { 12378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (!branched()) 12388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return; 1239ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs; 12408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Collect level 0 nodes from the root. 12428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned i = 0; i != rootSize; ++i) 12438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Refs.push_back(rootBranch().subtree(i)); 12448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Visit all branch nodes. 12468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned h = height - 1; h; --h) { 12478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned i = 0, e = Refs.size(); i != e; ++i) { 12488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned j = 0, s = Refs[i].size(); j != s; ++j) 1249ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NextRefs.push_back(Refs[i].subtree(j)); 12508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen (this->*f)(Refs[i], h); 12518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 12528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Refs.clear(); 12538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Refs.swap(NextRefs); 12548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 12558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Visit all leaf nodes. 12578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned i = 0, e = Refs.size(); i != e; ++i) 12588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen (this->*f)(Refs[i], 0); 12598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 12608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1261655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1262655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1263ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund OlesendeleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) { 1264655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen if (Level) 1265b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen deleteNode(&Node.get<Branch>()); 1266655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen else 1267b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen deleteNode(&Node.get<Leaf>()); 1268655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen} 1269655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen 1270655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1271655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1272655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesenclear() { 1273655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen if (branched()) { 1274655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen visitNodes(&IntervalMap::deleteNode); 1275655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen switchRootToLeaf(); 1276655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen } 1277655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen rootSize = 0; 1278655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen} 1279655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen 12808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1281bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMap::const_iterator ----// 12828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 12838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 12858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass IntervalMap<KeyT, ValT, N, Traits>::const_iterator : 12868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen public std::iterator<std::bidirectional_iterator_tag, ValT> { 12878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenprotected: 12888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen friend class IntervalMap; 12898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // The map referred to. 12918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IntervalMap *map; 12928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We store a full path from the root to the current position. 12948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // The path may be partially filled, but never between iterator calls. 1295706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMapImpl::Path path; 12968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1297da2fdcbb639de168738c27089bafa9ca10b731bdJakob Stoklund Olesen explicit const_iterator(const IntervalMap &map) : 1298da2fdcbb639de168738c27089bafa9ca10b731bdJakob Stoklund Olesen map(const_cast<IntervalMap*>(&map)) {} 12998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool branched() const { 13018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(map && "Invalid iterator"); 13028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return map->branched(); 13038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1305706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void setRoot(unsigned Offset) { 1306706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (branched()) 1307706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.setRoot(&map->rootBranch(), map->rootSize, Offset); 13088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1309706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.setRoot(&map->rootLeaf(), map->rootSize, Offset); 13108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void pathFillFind(KeyT x); 13138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void treeFind(KeyT x); 1314180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen void treeAdvanceTo(KeyT x); 13158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13167a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// unsafeStart - Writable access to start() for iterator. 13177a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT &unsafeStart() const { 13188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(valid() && "Cannot access invalid iterator"); 1319706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return branched() ? path.leaf<Leaf>().start(path.leafOffset()) : 1320706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.leaf<RootLeaf>().start(path.leafOffset()); 13218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13237a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// unsafeStop - Writable access to stop() for iterator. 13247a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT &unsafeStop() const { 13258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(valid() && "Cannot access invalid iterator"); 1326706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) : 1327706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.leaf<RootLeaf>().stop(path.leafOffset()); 13288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13307a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// unsafeValue - Writable access to value() for iterator. 13317a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen ValT &unsafeValue() const { 13328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(valid() && "Cannot access invalid iterator"); 1333706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return branched() ? path.leaf<Leaf>().value(path.leafOffset()) : 1334706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.leaf<RootLeaf>().value(path.leafOffset()); 13358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13377a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenpublic: 13387a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// const_iterator - Create an iterator that isn't pointing anywhere. 1339dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const_iterator() : map(nullptr) {} 13407a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 13415907d863659eb972ebb2afe07bc863a4c616f0efJakob Stoklund Olesen /// setMap - Change the map iterated over. This call must be followed by a 13425907d863659eb972ebb2afe07bc863a4c616f0efJakob Stoklund Olesen /// call to goToBegin(), goToEnd(), or find() 13435907d863659eb972ebb2afe07bc863a4c616f0efJakob Stoklund Olesen void setMap(const IntervalMap &m) { map = const_cast<IntervalMap*>(&m); } 13445907d863659eb972ebb2afe07bc863a4c616f0efJakob Stoklund Olesen 13457a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// valid - Return true if the current position is valid, false for end(). 13467a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen bool valid() const { return path.valid(); } 13477a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 1348cafe614035c8db70eb5da96dba00696db381674fJakob Stoklund Olesen /// atBegin - Return true if the current position is the first map entry. 1349cafe614035c8db70eb5da96dba00696db381674fJakob Stoklund Olesen bool atBegin() const { return path.atBegin(); } 1350cafe614035c8db70eb5da96dba00696db381674fJakob Stoklund Olesen 13517a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// start - Return the beginning of the current interval. 13527a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen const KeyT &start() const { return unsafeStart(); } 13537a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 13547a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// stop - Return the end of the current interval. 13557a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen const KeyT &stop() const { return unsafeStop(); } 13567a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 13577a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// value - Return the mapped value at the current interval. 13587a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen const ValT &value() const { return unsafeValue(); } 13597a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 13607a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen const ValT &operator*() const { return value(); } 13618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool operator==(const const_iterator &RHS) const { 13638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(map == RHS.map && "Cannot compare iterators from different maps"); 1364706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (!valid()) 1365706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return !RHS.valid(); 1366706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (path.leafOffset() != RHS.path.leafOffset()) 1367706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return false; 1368706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>(); 13698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool operator!=(const const_iterator &RHS) const { 13728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return !operator==(RHS); 13738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// goToBegin - Move to the first interval in map. 13768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void goToBegin() { 1377706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen setRoot(0); 13788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (branched()) 1379706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.fillLeft(map->height); 13808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// goToEnd - Move beyond the last interval in map. 13838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void goToEnd() { 1384706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen setRoot(map->rootSize); 13858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// preincrement - move to the next interval. 13888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator &operator++() { 13898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(valid() && "Cannot increment end()"); 1390706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (++path.leafOffset() == path.leafSize() && branched()) 1391706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.moveRight(map->height); 13928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return *this; 13938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// postincrement - Dont do that! 13968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator operator++(int) { 13978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator tmp = *this; 13988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen operator++(); 13998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return tmp; 14008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 14018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// predecrement - move to the previous interval. 14038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator &operator--() { 1404706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (path.leafOffset() && (valid() || !branched())) 1405706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen --path.leafOffset(); 14068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1407706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.moveLeft(map->height); 14088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return *this; 14098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 14108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// postdecrement - Dont do that! 14128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator operator--(int) { 14138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator tmp = *this; 14148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen operator--(); 14158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return tmp; 14168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 14178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// find - Move to the first interval with stop >= x, or end(). 14198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is a full search from the root, the current position is ignored. 14208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void find(KeyT x) { 14218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (branched()) 14228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen treeFind(x); 14238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1424706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen setRoot(map->rootLeaf().findFrom(0, map->rootSize, x)); 14258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 14268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// advanceTo - Move to the first interval with stop >= x, or end(). 14288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// The search is started from the current position, and no earlier positions 14298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// can be found. This is much faster than find() for small moves. 14308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void advanceTo(KeyT x) { 14315049ee5b11fe55e5a553b5388406aab874717672Jakob Stoklund Olesen if (!valid()) 14325049ee5b11fe55e5a553b5388406aab874717672Jakob Stoklund Olesen return; 14338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (branched()) 14348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen treeAdvanceTo(x); 14358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1436706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.leafOffset() = 1437706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x); 14388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 14398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 14418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1442180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// pathFillFind - Complete path by searching for x. 1443180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// @param x Key to search for. 14448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 14458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 14468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenconst_iterator::pathFillFind(KeyT x) { 1447706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMapImpl::NodeRef NR = path.subtree(path.height()); 1448706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen for (unsigned i = map->height - path.height() - 1; i; --i) { 1449ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen unsigned p = NR.get<Branch>().safeFind(0, x); 1450706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.push(NR, p); 1451ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NR = NR.subtree(p); 14528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1453706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.push(NR, NR.get<Leaf>().safeFind(0, x)); 14548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 14558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1456180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// treeFind - Find in a branched tree. 1457180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// @param x Key to search for. 14588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 14598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 14608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenconst_iterator::treeFind(KeyT x) { 1461706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen setRoot(map->rootBranch().findFrom(0, map->rootSize, x)); 14628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (valid()) 14638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen pathFillFind(x); 14648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 14658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1466180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// treeAdvanceTo - Find position after the current one. 1467180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// @param x Key to search for. 1468180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1469180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1470180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesenconst_iterator::treeAdvanceTo(KeyT x) { 1471180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // Can we stay on the same leaf node? 1472180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) { 1473180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x); 1474180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen return; 1475180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 1476180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen 1477180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // Drop the current leaf. 1478180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.pop(); 1479180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen 1480180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // Search towards the root for a usable subtree. 1481180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen if (path.height()) { 1482180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen for (unsigned l = path.height() - 1; l; --l) { 1483180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) { 1484180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // The branch node at l+1 is usable 1485180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.offset(l + 1) = 1486180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x); 1487180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen return pathFillFind(x); 1488180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 1489180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.pop(); 1490180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 1491180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // Is the level-1 Branch usable? 1492180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) { 1493180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x); 1494180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen return pathFillFind(x); 1495180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 1496180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 1497180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen 1498180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // We reached the root. 1499180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x)); 1500180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen if (valid()) 1501180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen pathFillFind(x); 1502180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen} 15038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 15048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1505bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMap::iterator ----// 15068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 15078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 15088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 15098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator { 15108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen friend class IntervalMap; 15118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen typedef IntervalMapImpl::IdxPair IdxPair; 15128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 15138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen explicit iterator(IntervalMap &map) : const_iterator(map) {} 15148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 15158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void setNodeStop(unsigned Level, KeyT Stop); 15166c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop); 15176c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen template <typename NodeT> bool overflow(unsigned Level); 15188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void treeInsert(KeyT a, KeyT b, ValT y); 1519b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen void eraseNode(unsigned Level); 1520055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen void treeErase(bool UpdateRoot = true); 15217a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen bool canCoalesceLeft(KeyT Start, ValT x); 15227a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen bool canCoalesceRight(KeyT Stop, ValT x); 15237a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 15259a08ca318e63912e4c19977abc1173f30866b704Jakob Stoklund Olesen /// iterator - Create null iterator. 15269a08ca318e63912e4c19977abc1173f30866b704Jakob Stoklund Olesen iterator() {} 15279a08ca318e63912e4c19977abc1173f30866b704Jakob Stoklund Olesen 15287a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setStart - Move the start of the current interval. 15297a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// This may cause coalescing with the previous interval. 15307a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param a New start key, must not overlap the previous interval. 15317a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setStart(KeyT a); 15327a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15337a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setStop - Move the end of the current interval. 15347a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// This may cause coalescing with the following interval. 15357a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param b New stop key, must not overlap the following interval. 15367a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setStop(KeyT b); 15377a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15387a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setValue - Change the mapped value of the current interval. 15397a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// This may cause coalescing with the previous and following intervals. 15407a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param x New value. 15417a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setValue(ValT x); 15427a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15437a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setStartUnchecked - Move the start of the current interval without 15447a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// checking for coalescing or overlaps. 15457a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// This should only be used when it is known that coalescing is not required. 15467a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param a New start key. 15477a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setStartUnchecked(KeyT a) { this->unsafeStart() = a; } 15487a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15497a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setStopUnchecked - Move the end of the current interval without checking 15507a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// for coalescing or overlaps. 15517a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// This should only be used when it is known that coalescing is not required. 15527a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param b New stop key. 15537a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setStopUnchecked(KeyT b) { 15547a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen this->unsafeStop() = b; 15557a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen // Update keys in branch nodes as well. 15567a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (this->path.atLastEntry(this->path.height())) 15577a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setNodeStop(this->path.height(), b); 15587a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 15597a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15607a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setValueUnchecked - Change the mapped value of the current interval 15617a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// without checking for coalescing. 15627a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param x New value. 15637a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setValueUnchecked(ValT x) { this->unsafeValue() = x; } 15647a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// insert - Insert mapping [a;b] -> y before the current position. 15668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void insert(KeyT a, KeyT b, ValT y); 15678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1568b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen /// erase - Erase the current interval. 1569b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen void erase(); 1570055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 1571055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator &operator++() { 1572055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen const_iterator::operator++(); 1573055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return *this; 1574055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } 1575055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 1576055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator operator++(int) { 1577055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator tmp = *this; 1578055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen operator++(); 1579055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return tmp; 1580055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } 1581055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 1582055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator &operator--() { 1583055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen const_iterator::operator--(); 1584055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return *this; 1585055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } 1586055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 1587055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator operator--(int) { 1588055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator tmp = *this; 1589055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen operator--(); 1590055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return tmp; 1591055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } 1592055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 15938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 15948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 15957a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// canCoalesceLeft - Can the current interval coalesce to the left after 15967a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// changing start or value? 15977a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @param Start New start of current interval. 15987a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @param Value New value for current interval. 15997a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @return True when updating the current interval would enable coalescing. 16007a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 16017a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenbool IntervalMap<KeyT, ValT, N, Traits>:: 16027a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Oleseniterator::canCoalesceLeft(KeyT Start, ValT Value) { 16037a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen using namespace IntervalMapImpl; 16047a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Path &P = this->path; 16057a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (!this->branched()) { 16067a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen unsigned i = P.leafOffset(); 16077a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen RootLeaf &Node = P.leaf<RootLeaf>(); 16087a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return i && Node.value(i-1) == Value && 16097a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Traits::adjacent(Node.stop(i-1), Start); 16107a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16117a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen // Branched. 16127a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (unsigned i = P.leafOffset()) { 16137a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Leaf &Node = P.leaf<Leaf>(); 16147a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start); 16157a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } else if (NodeRef NR = P.getLeftSibling(P.height())) { 16167a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen unsigned i = NR.size() - 1; 16177a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Leaf &Node = NR.get<Leaf>(); 16187a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start); 16197a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16207a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return false; 16217a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen} 16227a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 16237a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// canCoalesceRight - Can the current interval coalesce to the right after 16247a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// changing stop or value? 16257a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @param Stop New stop of current interval. 16267a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @param Value New value for current interval. 16277a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @return True when updating the current interval would enable coalescing. 16287a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 16297a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenbool IntervalMap<KeyT, ValT, N, Traits>:: 16307a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Oleseniterator::canCoalesceRight(KeyT Stop, ValT Value) { 16317a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen using namespace IntervalMapImpl; 16327a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Path &P = this->path; 16337a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen unsigned i = P.leafOffset() + 1; 16347a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (!this->branched()) { 16357a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (i >= P.leafSize()) 16367a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return false; 16377a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen RootLeaf &Node = P.leaf<RootLeaf>(); 16387a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); 16397a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16407a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen // Branched. 16417a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (i < P.leafSize()) { 16427a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Leaf &Node = P.leaf<Leaf>(); 16437a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); 16447a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } else if (NodeRef NR = P.getRightSibling(P.height())) { 16457a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Leaf &Node = NR.get<Leaf>(); 16467a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0)); 16477a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16487a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return false; 16497a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen} 16507a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 16518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// setNodeStop - Update the stop key of the current node at level and above. 16528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 16538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 16548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Oleseniterator::setNodeStop(unsigned Level, KeyT Stop) { 1655706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // There are no references to the root node, so nothing to update. 1656706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (!Level) 1657706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return; 1658706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 1659706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Update nodes pointing to the current node. 1660706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen while (--Level) { 1661706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.node<Branch>(Level).stop(P.offset(Level)) = Stop; 16627a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (!P.atLastEntry(Level)) 16638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return; 16648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1665706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Update root separately since it has a different layout. 1666706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop; 16678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 16688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 16697a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 16707a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 16717a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Oleseniterator::setStart(KeyT a) { 16727a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen assert(Traits::stopLess(a, this->stop()) && "Cannot move start beyond stop"); 16737a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT &CurStart = this->unsafeStart(); 16747a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) { 16757a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen CurStart = a; 16767a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return; 16777a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16787a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen // Coalesce with the interval to the left. 16797a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen --*this; 16807a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen a = this->start(); 16817a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen erase(); 16827a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setStartUnchecked(a); 16837a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen} 16847a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 16857a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 16867a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 16877a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Oleseniterator::setStop(KeyT b) { 16887a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen assert(Traits::stopLess(this->start(), b) && "Cannot move stop beyond start"); 16897a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (Traits::startLess(b, this->stop()) || 16907a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen !canCoalesceRight(b, this->value())) { 16917a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setStopUnchecked(b); 16927a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return; 16937a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16947a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen // Coalesce with interval to the right. 16957a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT a = this->start(); 16967a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen erase(); 16977a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setStartUnchecked(a); 16987a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen} 16997a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 17007a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 17017a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 17027a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Oleseniterator::setValue(ValT x) { 17037a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setValueUnchecked(x); 17047a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (canCoalesceRight(this->stop(), x)) { 17057a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT a = this->start(); 17067a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen erase(); 17077a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setStartUnchecked(a); 17087a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 17097a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (canCoalesceLeft(this->start(), x)) { 17107a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen --*this; 17117a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT a = this->start(); 17127a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen erase(); 17137a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setStartUnchecked(a); 17147a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 17157a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen} 17167a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 17178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// insertNode - insert a node before the current path at level. 17188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// Leave the current path pointing at the new node. 17196c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @param Level path index of the node to be inserted. 17206c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @param Node The node to be inserted. 17216c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @param Stop The last index in the new node. 17226c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @return True if the tree height was increased. 17238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 17246c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesenbool IntervalMap<KeyT, ValT, N, Traits>:: 1725ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Oleseniterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) { 1726706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen assert(Level && "Cannot insert next to the root"); 17276c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen bool SplitRoot = false; 1728706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMap &IM = *this->map; 1729706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 17306c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen 1731706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (Level == 1) { 17328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Insert into the root branch node. 17338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (IM.rootSize < RootBranch::Capacity) { 1734706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop); 1735706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.setSize(0, ++IM.rootSize); 173653bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen P.reset(Level); 17376c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen return SplitRoot; 17388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 17398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 17408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We need to split the root while keeping our position. 17416c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen SplitRoot = true; 1742706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IdxPair Offset = IM.splitRoot(P.offset(0)); 1743706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1744706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1745706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Fall through to insert at the new higher level. 1746706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen ++Level; 17478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 17488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 17498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // When inserting before end(), make sure we have a valid path. 1750706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.legalizeForInsert(--Level); 17518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1752706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Insert into the branch node at Level-1. 1753706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (P.size(Level) == Branch::Capacity) { 1754706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Branch node is full, handle handle the overflow. 17556c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen assert(!SplitRoot && "Cannot overflow after splitting the root"); 1756706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen SplitRoot = overflow<Branch>(Level); 17576c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen Level += SplitRoot; 17586c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen } 1759706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop); 1760706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.setSize(Level, P.size(Level) + 1); 17617a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (P.atLastEntry(Level)) 176253bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen setNodeStop(Level, Stop); 176353bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen P.reset(Level + 1); 17646c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen return SplitRoot; 17658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 17668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 17678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// insert 17688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 17698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 17708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Oleseniterator::insert(KeyT a, KeyT b, ValT y) { 17718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (this->branched()) 17728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return treeInsert(a, b, y); 1773706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMap &IM = *this->map; 1774706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 1775706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1776706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Try simple root leaf insert. 17775f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y); 1778706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1779706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Was the root node insert successful? 17805f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (Size <= RootLeaf::Capacity) { 17815f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen P.setSize(0, IM.rootSize = Size); 17828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return; 17838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1784706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1785706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Root leaf node is full, we must branch. 1786706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IdxPair Offset = IM.branchRoot(P.leafOffset()); 1787706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1788706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1789706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Now it fits in the new leaf. 17908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen treeInsert(a, b, y); 17918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 17928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 17938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 17948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 17958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 17968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Oleseniterator::treeInsert(KeyT a, KeyT b, ValT y) { 1797b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen using namespace IntervalMapImpl; 1798b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Path &P = this->path; 1799b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 18005f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (!P.valid()) 18015f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen P.legalizeForInsert(this->map->height); 18025f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen 1803b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Check if this insertion will extend the node to the left. 18045f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) { 1805b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Node is growing to the left, will it affect a left sibling node? 18065f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (NodeRef Sib = P.getLeftSibling(P.height())) { 1807b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Leaf &SibLeaf = Sib.get<Leaf>(); 1808b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen unsigned SibOfs = Sib.size() - 1; 1809b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (SibLeaf.value(SibOfs) == y && 1810b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Traits::adjacent(SibLeaf.stop(SibOfs), a)) { 1811b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // This insertion will coalesce with the last entry in SibLeaf. We can 1812b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // handle it in two ways: 1813b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // 1. Extend SibLeaf.stop to b and be done, or 1814b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // 2. Extend a to SibLeaf, erase the SibLeaf entry and continue. 1815b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // We prefer 1., but need 2 when coalescing to the right as well. 1816b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Leaf &CurLeaf = P.leaf<Leaf>(); 18175f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen P.moveLeft(P.height()); 1818b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (Traits::stopLess(b, CurLeaf.start(0)) && 1819b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) { 1820b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Easy, just extend SibLeaf and we're done. 18215f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b); 1822b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen return; 1823b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } else { 1824b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // We have both left and right coalescing. Erase the old SibLeaf entry 1825b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // and continue inserting the larger interval. 1826b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen a = SibLeaf.start(SibOfs); 1827055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen treeErase(/* UpdateRoot= */false); 1828b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1829b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1830b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } else { 1831b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // No left sibling means we are at begin(). Update cached bound. 18325f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen this->map->rootBranchStart() = a; 1833b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1834b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1835706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 18365f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen // When we are inserting at the end of a leaf node, we must update stops. 18375f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen unsigned Size = P.leafSize(); 18385f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen bool Grow = P.leafOffset() == Size; 18395f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y); 1840706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1841706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Leaf insertion unsuccessful? Overflow and try again. 18425f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (Size > Leaf::Capacity) { 18435f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen overflow<Leaf>(P.height()); 18445f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen Grow = P.leafOffset() == P.leafSize(); 18455f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y); 18465f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen assert(Size <= Leaf::Capacity && "overflow() didn't make room"); 18478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1848706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1849706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Inserted, update offset and leaf size. 18505f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen P.setSize(P.height(), Size); 1851706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1852706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Insert was the last node entry, update stops. 18535f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (Grow) 18545f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen setNodeStop(P.height(), b); 1855b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen} 18568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1857b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// erase - erase the current interval and move to the next position. 1858b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1859b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1860b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Oleseniterator::erase() { 1861b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMap &IM = *this->map; 1862b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 1863b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen assert(P.valid() && "Cannot erase end()"); 1864b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (this->branched()) 1865b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen return treeErase(); 1866b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IM.rootLeaf().erase(P.leafOffset(), IM.rootSize); 1867b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.setSize(0, --IM.rootSize); 1868b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen} 1869b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 1870b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// treeErase - erase() for a branched tree. 1871b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1872b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1873055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Oleseniterator::treeErase(bool UpdateRoot) { 1874b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMap &IM = *this->map; 1875b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 1876b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Leaf &Node = P.leaf<Leaf>(); 1877b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 1878b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Nodes are not allowed to become empty. 1879b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (P.leafSize() == 1) { 1880b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IM.deleteNode(&Node); 1881b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen eraseNode(IM.height); 1882055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen // Update rootBranchStart if we erased begin(). 1883055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen if (UpdateRoot && IM.branched() && P.valid() && P.atBegin()) 1884055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1885b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen return; 1886b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1887b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 1888b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Erase current entry. 1889b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Node.erase(P.leafOffset(), P.leafSize()); 1890b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen unsigned NewSize = P.leafSize() - 1; 1891b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.setSize(IM.height, NewSize); 1892b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // When we erase the last entry, update stop and move to a legal position. 1893b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (P.leafOffset() == NewSize) { 1894b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen setNodeStop(IM.height, Node.stop(NewSize - 1)); 1895b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.moveRight(IM.height); 1896055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } else if (UpdateRoot && P.atBegin()) 1897055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1898b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen} 1899b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 1900b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// eraseNode - Erase the current node at Level from its parent and move path to 1901b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// the first entry of the next sibling node. 1902b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// The node must be deallocated by the caller. 1903b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// @param Level 1..height, the root node cannot be erased. 1904b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1905b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1906b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Oleseniterator::eraseNode(unsigned Level) { 1907b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen assert(Level && "Cannot erase root node"); 1908b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMap &IM = *this->map; 1909b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 1910b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 1911b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (--Level == 0) { 1912b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IM.rootBranch().erase(P.offset(0), IM.rootSize); 1913b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.setSize(0, --IM.rootSize); 1914b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // If this cleared the root, switch to height=0. 1915b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (IM.empty()) { 1916b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IM.switchRootToLeaf(); 1917b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen this->setRoot(0); 1918b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen return; 1919b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1920b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } else { 1921b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Remove node ref from branch node at Level. 1922b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Branch &Parent = P.node<Branch>(Level); 1923b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (P.size(Level) == 1) { 1924b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Branch node became empty, remove it recursively. 1925b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IM.deleteNode(&Parent); 1926b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen eraseNode(Level); 1927b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } else { 1928b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Branch node won't become empty. 1929b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Parent.erase(P.offset(Level), P.size(Level)); 1930b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen unsigned NewSize = P.size(Level) - 1; 1931b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.setSize(Level, NewSize); 1932b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // If we removed the last branch, update stop and move to a legal pos. 1933b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (P.offset(Level) == NewSize) { 1934b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen setNodeStop(Level, Parent.stop(NewSize - 1)); 1935b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.moveRight(Level); 1936b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1937b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1938b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1939b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Update path cache for the new right sibling position. 1940b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (P.valid()) { 1941b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.reset(Level + 1); 1942b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.offset(Level + 1) = 0; 1943b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 19448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 19458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19466c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// overflow - Distribute entries of the current node evenly among 19476c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// its siblings and ensure that the current node is not full. 19486c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// This may require allocating a new node. 194915658b290817d6f198ab08910a2d754ba11164d1Rafael Espindola/// @tparam NodeT The type of node at Level (Leaf or Branch). 19506c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @param Level path index of the overflowing node. 19516c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @return True when the tree height was changed. 19528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 19536c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesentemplate <typename NodeT> 19546c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesenbool IntervalMap<KeyT, ValT, N, Traits>:: 19556c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Oleseniterator::overflow(unsigned Level) { 1956ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen using namespace IntervalMapImpl; 1957706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen Path &P = this->path; 19588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned CurSize[4]; 19596c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen NodeT *Node[4]; 19608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Nodes = 0; 19618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Elements = 0; 1962706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned Offset = P.offset(Level); 19638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Do we have a left sibling? 1965706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef LeftSib = P.getLeftSibling(Level); 19668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (LeftSib) { 19678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Offset += Elements = CurSize[Nodes] = LeftSib.size(); 19686c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen Node[Nodes++] = &LeftSib.get<NodeT>(); 19698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 19708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19716c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen // Current node. 1972706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen Elements += CurSize[Nodes] = P.size(Level); 1973706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen Node[Nodes++] = &P.node<NodeT>(Level); 19748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Do we have a right sibling? 1976706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef RightSib = P.getRightSibling(Level); 19778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (RightSib) { 1978b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Elements += CurSize[Nodes] = RightSib.size(); 19796c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen Node[Nodes++] = &RightSib.get<NodeT>(); 19808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 19818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Do we need to allocate a new node? 19838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned NewNode = 0; 19846c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen if (Elements + 1 > Nodes * NodeT::Capacity) { 19858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Insert NewNode at the penultimate position, or after a single node. 19868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen NewNode = Nodes == 1 ? 1 : Nodes - 1; 19878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen CurSize[Nodes] = CurSize[NewNode]; 19888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Node[Nodes] = Node[NewNode]; 19898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen CurSize[NewNode] = 0; 199087d8e60505b26960956996550c8b805c81e5b02bDouglas Gregor Node[NewNode] = this->map->template newNode<NodeT>(); 19918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen ++Nodes; 19928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 19938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Compute the new element distribution. 19958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned NewSize[4]; 19966c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity, 1997ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen CurSize, NewSize, Offset, true); 1998bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen adjustSiblingSizes(Node, Nodes, CurSize, NewSize); 19998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 20008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Move current location to the leftmost node. 20018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (LeftSib) 2002706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.moveLeft(Level); 20038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 20048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Elements have been rearranged, now update node sizes and stops. 20056c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen bool SplitRoot = false; 20068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Pos = 0; 20078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (;;) { 20088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1); 20096c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen if (NewNode && Pos == NewNode) { 20106c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop); 20116c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen Level += SplitRoot; 20126c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen } else { 2013706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.setSize(Level, NewSize[Pos]); 20146c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen setNodeStop(Level, Stop); 20158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 20168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Pos + 1 == Nodes) 20178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen break; 2018706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.moveRight(Level); 20198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen ++Pos; 20208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 20218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 20228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Where was I? Find NewOffset. 20238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen while(Pos != NewOffset.first) { 2024706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.moveLeft(Level); 20258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen --Pos; 20268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2027706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.offset(Level) = NewOffset.second; 20286c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen return SplitRoot; 20298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 20308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 2031cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 2032cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen//--- IntervalMapOverlaps ----// 2033cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 2034cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2035cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two 2036cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// IntervalMaps. The maps may be different, but the KeyT and Traits types 2037cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// should be the same. 2038cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 2039cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// Typical uses: 2040cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 2041cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 1. Test for overlap: 2042cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// bool overlap = IntervalMapOverlaps(a, b).valid(); 2043cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 2044cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 2. Enumerate overlaps: 2045cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... } 2046cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 2047cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesentemplate <typename MapA, typename MapB> 2048cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesenclass IntervalMapOverlaps { 2049ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen typedef typename MapA::KeyType KeyType; 2050cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen typedef typename MapA::KeyTraits Traits; 2051cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen typename MapA::const_iterator posA; 2052cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen typename MapB::const_iterator posB; 2053cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2054cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// advance - Move posA and posB forward until reaching an overlap, or until 2055cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// either meets end. 2056cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// Don't move the iterators if they are already overlapping. 2057cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen void advance() { 20584aec85ae01188f87e45e5e91baab4f303cbcd336Jakob Stoklund Olesen if (!valid()) 20594aec85ae01188f87e45e5e91baab4f303cbcd336Jakob Stoklund Olesen return; 2060d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen 2061d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (Traits::stopLess(posA.stop(), posB.start())) { 2062d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen // A ends before B begins. Catch up. 2063d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen posA.advanceTo(posB.start()); 2064d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start())) 2065d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen return; 2066d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen } else if (Traits::stopLess(posB.stop(), posA.start())) { 2067d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen // B ends before A begins. Catch up. 2068d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen posB.advanceTo(posA.start()); 2069d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start())) 2070d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen return; 2071d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen } else 2072d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen // Already overlapping. 2073d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen return; 2074d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen 2075cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen for (;;) { 2076cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen // Make a.end > b.start. 2077cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen posA.advanceTo(posB.start()); 2078460ee0fd19b13ba4c1410e43d8d253bf34673817Jakob Stoklund Olesen if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start())) 2079cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen return; 2080cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen // Make b.end > a.start. 2081cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen posB.advanceTo(posA.start()); 2082460ee0fd19b13ba4c1410e43d8d253bf34673817Jakob Stoklund Olesen if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start())) 2083cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen return; 2084cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2085cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2086cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2087cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesenpublic: 2088cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b. 2089cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen IntervalMapOverlaps(const MapA &a, const MapB &b) 2090cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen : posA(b.empty() ? a.end() : a.find(b.start())), 20914aec85ae01188f87e45e5e91baab4f303cbcd336Jakob Stoklund Olesen posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); } 2092cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2093cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// valid - Return true if iterator is at an overlap. 2094cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen bool valid() const { 2095cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen return posA.valid() && posB.valid(); 2096cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2097cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2098cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// a - access the left hand side in the overlap. 2099cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen const typename MapA::const_iterator &a() const { return posA; } 2100cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2101cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// b - access the right hand side in the overlap. 2102cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen const typename MapB::const_iterator &b() const { return posB; } 2103cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2104ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen /// start - Beginning of the overlapping interval. 2105ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType start() const { 2106ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType ak = a().start(); 2107ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType bk = b().start(); 2108ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen return Traits::startLess(ak, bk) ? bk : ak; 2109ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen } 2110ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen 2111d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen /// stop - End of the overlapping interval. 2112ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType stop() const { 2113ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType ak = a().stop(); 2114ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType bk = b().stop(); 2115ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen return Traits::startLess(ak, bk) ? ak : bk; 2116ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen } 2117ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen 2118cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// skipA - Move to the next overlap that doesn't involve a(). 2119cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen void skipA() { 2120cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen ++posA; 2121cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen advance(); 2122cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2123cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2124cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// skipB - Move to the next overlap that doesn't involve b(). 2125cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen void skipB() { 2126cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen ++posB; 2127cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen advance(); 2128cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2129cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2130cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// Preincrement - Move to the next overlap. 2131cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen IntervalMapOverlaps &operator++() { 2132cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen // Bump the iterator that ends first. The other one may have more overlaps. 2133460ee0fd19b13ba4c1410e43d8d253bf34673817Jakob Stoklund Olesen if (Traits::startLess(posB.stop(), posA.stop())) 2134cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen skipB(); 2135cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen else 2136cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen skipA(); 2137cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen return *this; 2138cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2139cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2140ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen /// advanceTo - Move to the first overlapping interval with 2141ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen /// stopLess(x, stop()). 2142ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen void advanceTo(KeyType x) { 2143d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (!valid()) 2144d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen return; 2145d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen // Make sure advanceTo sees monotonic keys. 2146d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (Traits::stopLess(posA.stop(), x)) 2147d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen posA.advanceTo(x); 2148d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (Traits::stopLess(posB.stop(), x)) 2149d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen posB.advanceTo(x); 2150ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen advance(); 2151ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen } 2152ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen}; 2153cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 21548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} // namespace llvm 21558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 21568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#endif 2157