IntervalMap.h revision cafe614035c8db70eb5da96dba00696db381674f
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/SmallVector.h" 1038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#include "llvm/ADT/PointerIntPair.h" 1048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#include "llvm/Support/Allocator.h" 1058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#include "llvm/Support/RecyclingAllocator.h" 1068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#include <iterator> 1078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesennamespace llvm { 1098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//--- Key traits ---// 1138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The IntervalMap works with closed or half-open intervals. 1168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Adjacent intervals that map to the same value are coalesced. 1178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The IntervalMapInfo traits class is used to determine if a key is contained 1198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// in an interval, and if two intervals are adjacent so they can be coalesced. 1208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The provided implementation works for closed integer intervals, other keys 1218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// probably need a specialized version. 1228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x). 1248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// It is assumed that (a;b] half-open intervals are not used, only [a;b) is 1268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// allowed. This is so that stopLess(a, b) can be used to determine if two 1278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// intervals overlap. 1288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename T> 1328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenstruct IntervalMapInfo { 1338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// startLess - Return true if x is not in [a;b]. 1358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is x < a both for closed intervals and for [a;b) half-open intervals. 1368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen static inline bool startLess(const T &x, const T &a) { 1378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return x < a; 1388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// stopLess - Return true if x is not in [a;b]. 1418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals. 1428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen static inline bool stopLess(const T &b, const T &x) { 1438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return b < x; 1448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce. 1478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is a+1 == b for closed intervals, a == b for half-open intervals. 1488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen static inline bool adjacent(const T &a, const T &b) { 1498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return a+1 == b; 1508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 1538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// IntervalMapImpl - Namespace used for IntervalMap implementation details. 1558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// It should be considered private to the implementation. 1568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesennamespace IntervalMapImpl { 1578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Forward declarations. 1598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename, typename, unsigned, typename> class LeafNode; 1608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename, typename, unsigned, typename> class BranchNode; 1618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentypedef std::pair<unsigned,unsigned> IdxPair; 1638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 166bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::NodeBase ---// 1678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 169a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen// Both leaf and branch nodes store vectors of pairs. 170a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen// Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT). 1718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Keys and values are stored in separate arrays to avoid padding caused by 1738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// different object alignments. This also helps improve locality of reference 1748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// when searching the keys. 1758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The nodes don't know how many elements they contain - that information is 1778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// stored elsewhere. Omitting the size field prevents padding and allows a node 1788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// to fill the allocated cache lines completely. 1798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// These are typical key and value sizes, the node branching factor (N), and 1818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// wasted space when nodes are sized to fit in three cache lines (192 bytes): 1828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 183a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen// T1 T2 N Waste Used by 1848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4 4 24 0 Branch<4> (32-bit pointers) 185a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen// 8 4 16 0 Leaf<4,4>, Branch<4> 1868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 8 8 12 0 Leaf<4,8>, Branch<8> 1878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 16 4 9 12 Leaf<8,4> 1888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 16 8 8 0 Leaf<8,8> 1898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 1908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 192a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesentemplate <typename T1, typename T2, unsigned N> 1938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass NodeBase { 1948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 1958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen enum { Capacity = N }; 1968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 197a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen T1 first[N]; 198a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen T2 second[N]; 1998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 2008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// copy - Copy elements from another node. 20133fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Other Node elements are copied from. 2028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Beginning of the source range in other. 2038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param j Beginning of the destination range in this. 20433fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Count Number of elements to copy. 2058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen template <unsigned M> 206a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen void copy(const NodeBase<T1, T2, M> &Other, unsigned i, 2078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned j, unsigned Count) { 2088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i + Count <= M && "Invalid source range"); 2098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(j + Count <= N && "Invalid dest range"); 21008d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen for (unsigned e = i + Count; i != e; ++i, ++j) { 21108d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen first[j] = Other.first[i]; 21208d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen second[j] = Other.second[i]; 21308d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen } 2148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 21633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// moveLeft - Move elements to the left. 2178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Beginning of the source range. 2188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param j Beginning of the destination range. 21933fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Count Number of elements to copy. 22033fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen void moveLeft(unsigned i, unsigned j, unsigned Count) { 22133fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen assert(j <= i && "Use moveRight shift elements right"); 2228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen copy(*this, i, j, Count); 2238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 22533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// moveRight - Move elements to the right. 2268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Beginning of the source range. 2278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param j Beginning of the destination range. 22833fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Count Number of elements to copy. 22933fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen void moveRight(unsigned i, unsigned j, unsigned Count) { 23033fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen assert(i <= j && "Use moveLeft shift elements left"); 2318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(j + Count <= N && "Invalid range"); 23208d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen while (Count--) { 23308d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen first[j + Count] = first[i + Count]; 23408d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen second[j + Count] = second[i + Count]; 23508d55342e337fd4e80a68b81b8b0cbb100ea0a23Jakob Stoklund Olesen } 2368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 2388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// erase - Erase elements [i;j). 2398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Beginning of the range to erase. 2408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param j End of the range. (Exclusive). 24133fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in node. 2428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void erase(unsigned i, unsigned j, unsigned Size) { 24333fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen moveLeft(j, i, Size - j); 2448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 246b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen /// erase - Erase element at i. 247b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen /// @param i Index of element to erase. 248b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen /// @param Size Number of elements in node. 249b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen void erase(unsigned i, unsigned Size) { 250b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen erase(i, i+1, Size); 251b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 252b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 2538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// shift - Shift elements [i;size) 1 position to the right. 2548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Beginning of the range to move. 25533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in node. 2568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void shift(unsigned i, unsigned Size) { 25733fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen moveRight(i, i + 1, Size - i); 2588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 26033fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// transferToLeftSib - Transfer elements to a left sibling node. 26133fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in this. 26233fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Sib Left sibling node. 26333fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param SSize Number of elements in sib. 26433fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Count Number of elements to transfer. 26533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, 26633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen unsigned Count) { 2678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Sib.copy(*this, 0, SSize, Count); 2688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen erase(0, Count, Size); 2698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 27133fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// transferToRightSib - Transfer elements to a right sibling node. 27233fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in this. 27333fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Sib Right sibling node. 27433fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param SSize Number of elements in sib. 27533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Count Number of elements to transfer. 27633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize, 27733fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen unsigned Count) { 27833fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen Sib.moveRight(0, Count, SSize); 2798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Sib.copy(*this, Size-Count, 0, Count); 2808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 28233fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// adjustFromLeftSib - Adjust the number if elements in this node by moving 2838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// elements to or from a left sibling node. 28433fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in this. 28533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Sib Right sibling node. 28633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param SSize Number of elements in sib. 28733fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Add The number of elements to add to this node, possibly < 0. 2888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return Number of elements added to this node, possibly negative. 28933fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) { 2908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Add > 0) { 2918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We want to grow, copy from sib. 2928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size); 29333fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen Sib.transferToRightSib(SSize, *this, Size, Count); 2948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return Count; 2958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } else { 2968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We want to shrink, copy to sib. 2978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize); 29833fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen transferToLeftSib(Size, Sib, SSize, Count); 2998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return -Count; 3008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 3018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 3028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 3038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 304bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen/// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes. 305bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Node Array of pointers to sibling nodes. 306bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Nodes Number of nodes. 307bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param CurSize Array of current node sizes, will be overwritten. 308bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param NewSize Array of desired node sizes. 309bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesentemplate <typename NodeT> 310bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesenvoid adjustSiblingSizes(NodeT *Node[], unsigned Nodes, 311bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen unsigned CurSize[], const unsigned NewSize[]) { 312bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen // Move elements right. 313bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen for (int n = Nodes - 1; n; --n) { 314b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (CurSize[n] == NewSize[n]) 315bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen continue; 316bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen for (int m = n - 1; m != -1; --m) { 317bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m], 318bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen NewSize[n] - CurSize[n]); 319bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen CurSize[m] -= d; 320bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen CurSize[n] += d; 321bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen // Keep going if the current node was exhausted. 322bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen if (CurSize[n] >= NewSize[n]) 323bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen break; 324bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen } 325bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen } 326bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen 327bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen if (Nodes == 0) 328bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen return; 329bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen 330bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen // Move elements left. 331bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen for (unsigned n = 0; n != Nodes - 1; ++n) { 332bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen if (CurSize[n] == NewSize[n]) 333bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen continue; 334bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen for (unsigned m = n + 1; m != Nodes; ++m) { 335bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n], 336bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen CurSize[n] - NewSize[n]); 337bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen CurSize[m] += d; 338bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen CurSize[n] -= d; 339bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen // Keep going if the current node was exhausted. 340bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen if (CurSize[n] >= NewSize[n]) 341bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen break; 342bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen } 343bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen } 344bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen 345bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen#ifndef NDEBUG 346bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen for (unsigned n = 0; n != Nodes; n++) 347bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle"); 348bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen#endif 349bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen} 350bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen 351bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen/// IntervalMapImpl::distribute - Compute a new distribution of node elements 352bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen/// after an overflow or underflow. Reserve space for a new element at Position, 353bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen/// and compute the node that will hold Position after redistributing node 354bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen/// elements. 355bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 356bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// It is required that 357bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 358bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// Elements == sum(CurSize), and 359bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// Elements + Grow <= Nodes * Capacity. 360bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 361bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// NewSize[] will be filled in such that: 362bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 363bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// sum(NewSize) == Elements, and 364bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// NewSize[i] <= Capacity. 365bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 366bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// The returned index is the node where Position will go, so: 367bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 368bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// sum(NewSize[0..idx-1]) <= Position 369bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// sum(NewSize[0..idx]) >= Position 370bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 371bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// The last equality, sum(NewSize[0..idx]) == Position, can only happen when 372bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// Grow is set and NewSize[idx] == Capacity-1. The index points to the node 373bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// before the one holding the Position'th element where there is room for an 374bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// insertion. 375bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// 376bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Nodes The number of nodes. 377bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Elements Total elements in all nodes. 378bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Capacity The capacity of each node. 379bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param CurSize Array[Nodes] of current node sizes, or NULL. 380bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param NewSize Array[Nodes] to receive the new node sizes. 381bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Position Insert position. 382bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @param Grow Reserve space for a new element at Position. 383bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen/// @return (node, offset) for Position. 384bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund OlesenIdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, 385bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen const unsigned *CurSize, unsigned NewSize[], 386bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen unsigned Position, bool Grow); 387bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen 3888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 3898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 390bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::NodeSizer ---// 3918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 3928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 3938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Compute node sizes from key and value types. 3948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 3958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The branching factors are chosen to make nodes fit in three cache lines. 3968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// This may not be possible if keys or values are very large. Such large objects 3978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// are handled correctly, but a std::map would probably give better performance. 3988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 3998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenenum { 4028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Cache line size. Most architectures have 32 or 64 byte cache lines. 4038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We use 64 bytes here because it provides good branching factors. 4048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Log2CacheLine = 6, 4058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen CacheLineBytes = 1 << Log2CacheLine, 4068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen DesiredNodeBytes = 3 * CacheLineBytes 4078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 4088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT> 4108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenstruct NodeSizer { 4118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen enum { 4128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Compute the leaf node branching factor that makes a node fit in three 4138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // cache lines. The branching factor must be at least 3, or some B+-tree 4148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // balancing algorithms won't work. 4158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // LeafSize can't be larger than CacheLineBytes. This is required by the 4168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // PointerIntPair used by NodeRef. 4178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen DesiredLeafSize = DesiredNodeBytes / 4188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)), 4198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen MinLeafSize = 3, 420528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize 421528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen }; 422528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen 423528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen typedef NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize> LeafBase; 4248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 425528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen enum { 4268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Now that we have the leaf branching factor, compute the actual allocation 4278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // unit size by rounding up to a whole number of cache lines. 428528900d9a46cf4acde3a90494f286116159d5e59Jakob Stoklund Olesen AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1), 4298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Determine the branching factor for branch nodes. 4318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen BranchSize = AllocBytes / 4328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen static_cast<unsigned>(sizeof(KeyT) + sizeof(void*)) 4338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen }; 4348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// Allocator - The recycling allocator used for both branch and leaf nodes. 4368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This typedef is very likely to be identical for all IntervalMaps with 4378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// reasonably sized entries, so the same allocator can be shared among 4388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// different kinds of maps. 4398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen typedef RecyclingAllocator<BumpPtrAllocator, char, 4408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen AllocBytes, CacheLineBytes> Allocator; 4418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 4438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 446bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::NodeRef ---// 4478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// B+-tree nodes can be leaves or branches, so we need a polymorphic node 4508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// pointer that can point to both kinds. 4518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// All nodes are cache line aligned and the low 6 bits of a node pointer are 4538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// always 0. These bits are used to store the number of elements in the 4548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// referenced node. Besides saving space, placing node sizes in the parents 4558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// allow tree balancing algorithms to run without faulting cache lines for nodes 4568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// that may not need to be modified. 4578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// A NodeRef doesn't know whether it references a leaf node or a branch node. 4598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// It is the responsibility of the caller to use the correct types. 4608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Nodes are never supposed to be empty, and it is invalid to store a node size 4628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// of 0 in a NodeRef. The valid range of sizes is 1-64. 4638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 4648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 4658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass NodeRef { 467bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen struct CacheAlignedPointerTraits { 468bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen static inline void *getAsVoidPointer(void *P) { return P; } 469bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen static inline void *getFromVoidPointer(void *P) { return P; } 470bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen enum { NumLowBitsAvailable = Log2CacheLine }; 471bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen }; 4728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip; 4738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 4758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// NodeRef - Create a null ref. 4768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen NodeRef() {} 4778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// operator bool - Detect a null ref. 4798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen operator bool() const { return pip.getOpaqueValue(); } 4808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 481ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen /// NodeRef - Create a reference to the node p with n elements. 482ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen template <typename NodeT> 483ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) { 484ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen assert(n <= NodeT::Capacity && "Size too big for node"); 485ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen } 4868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// size - Return the number of elements in the referenced node. 4888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned size() const { return pip.getInt() + 1; } 4898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 4908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// setSize - Update the node size. 4918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void setSize(unsigned n) { pip.setInt(n - 1); } 4928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 493ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen /// subtree - Access the i'th subtree reference in a branch node. 494ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen /// This depends on branch nodes storing the NodeRef array as their first 495ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen /// member. 496706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef &subtree(unsigned i) const { 497ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen return reinterpret_cast<NodeRef*>(pip.getPointer())[i]; 4988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 4998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 500ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen /// get - Dereference as a NodeT reference. 501ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen template <typename NodeT> 502ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NodeT &get() const { 503ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen return *reinterpret_cast<NodeT*>(pip.getPointer()); 5048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool operator==(const NodeRef &RHS) const { 5078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (pip == RHS.pip) 5088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return true; 5098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs"); 5108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return false; 5118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool operator!=(const NodeRef &RHS) const { 5148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return !operator==(RHS); 5158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 5178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 519bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::LeafNode ---// 5208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 5218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 5228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Leaf nodes store up to N disjoint intervals with corresponding values. 5238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 5248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The intervals are kept sorted and fully coalesced so there are no adjacent 5258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// intervals mapping to the same value. 5268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 5278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// These constraints are always satisfied: 5288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 529ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen// - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals. 5308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 531ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen// - Traits::stopLess(stop(i), start(i + 1) - Sorted. 5328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 533ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen// - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1)) 534ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen// - Fully coalesced. 5358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 5368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 5378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 5398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> { 5408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 541a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen const KeyT &start(unsigned i) const { return this->first[i].first; } 542a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen const KeyT &stop(unsigned i) const { return this->first[i].second; } 543a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen const ValT &value(unsigned i) const { return this->second[i]; } 5448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 545a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen KeyT &start(unsigned i) { return this->first[i].first; } 546a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen KeyT &stop(unsigned i) { return this->first[i].second; } 547a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen ValT &value(unsigned i) { return this->second[i]; } 5488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// findFrom - Find the first interval after i that may contain x. 5508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Starting index for the search. 55133fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in node. 5528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 5538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return First index with !stopLess(key[i].stop, x), or size. 5548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is the first interval that can possibly contain x. 5558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { 5568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i <= Size && Size <= N && "Bad indices"); 5578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 5588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen "Index is past the needed point"); 5598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen while (i != Size && Traits::stopLess(stop(i), x)) ++i; 5608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return i; 5618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// safeFind - Find an interval that is known to exist. This is the same as 5648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// findFrom except is it assumed that x is at least within range of the last 5658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// interval. 5668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Starting index for the search. 5678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 5688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return First index with !stopLess(key[i].stop, x), never size. 5698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is the first interval that can possibly contain x. 5708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned safeFind(unsigned i, KeyT x) const { 5718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i < N && "Bad index"); 5728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 5738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen "Index is past the needed point"); 5748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen while (Traits::stopLess(stop(i), x)) ++i; 5758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i < N && "Unsafe intervals"); 5768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return i; 5778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// safeLookup - Lookup mapped value for a safe key. 5808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// It is assumed that x is within range of the last entry. 5818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 5828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param NotFound Value to return if x is not in any interval. 5838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return The mapped value at x or NotFound. 5848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen ValT safeLookup(KeyT x, ValT NotFound) const { 5858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned i = safeFind(0, x); 5868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return Traits::startLess(x, start(i)) ? NotFound : value(i); 5878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 5888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5895f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y); 5908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 5918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 5928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as 5938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// possible. This may cause the node to grow by 1, or it may cause the node 5948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// to shrink because of coalescing. 5958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// @param i Starting index = insertFrom(0, size, a) 59633fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen/// @param Size Number of elements in node. 5978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// @param a Interval start. 5988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// @param b Interval stop. 5998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// @param y Value be mapped. 6008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// @return (insert position, new size), or (i, Capacity+1) on overflow. 6018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 6025f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesenunsigned LeafNode<KeyT, ValT, N, Traits>:: 6035f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund OleseninsertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) { 6045f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen unsigned i = Pos; 6058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i <= Size && Size <= N && "Invalid index"); 6068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(!Traits::stopLess(b, a) && "Invalid interval"); 6078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Verify the findFrom invariant. 6098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == 0 || Traits::stopLess(stop(i - 1), a))); 6108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == Size || !Traits::stopLess(stop(i), a))); 6115f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert"); 6128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Coalesce with previous interval. 6145f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) { 6155f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen Pos = i - 1; 6165f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen // Also coalesce with next interval? 6175f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) { 6185f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen stop(i - 1) = stop(i); 6195f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen this->erase(i, Size); 6205f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return Size - 1; 6215f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen } 6225f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen stop(i - 1) = b; 6235f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return Size; 6245f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen } 6258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Detect overflow. 6278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (i == N) 6285f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return N + 1; 6298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Add new interval at end. 6318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (i == Size) { 6328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen start(i) = a; 6338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen stop(i) = b; 6348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen value(i) = y; 6355f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return Size + 1; 6368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 6378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Try to coalesce with following interval. 6398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (value(i) == y && Traits::adjacent(b, start(i))) { 6408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen start(i) = a; 6415f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return Size; 6428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 6438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We must insert before i. Detect overflow. 6458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Size == N) 6465f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return N + 1; 6478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Insert before i. 6498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen this->shift(i, Size); 6508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen start(i) = a; 6518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen stop(i) = b; 6528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen value(i) = y; 6535f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen return Size + 1; 6548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 6558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 658bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::BranchNode ---// 6598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 6608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 6618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// A branch node stores references to 1--N subtrees all of the same height. 6628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 6638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// The key array in a branch node holds the rightmost stop key of each subtree. 6648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// It is redundant to store the last stop key since it can be found in the 6658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// parent node, but doing so makes tree balancing a lot simpler. 6668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 6678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// It is unusual for a branch node to only have one subtree, but it can happen 6688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// in the root node if it is smaller than the normal nodes. 6698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 6708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// When all of the leaf nodes from all the subtrees are concatenated, they must 6718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// satisfy the same constraints as a single leaf node. They must be sorted, 6728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// sane, and fully coalesced. 6738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// 6748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 6758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 677ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesenclass BranchNode : public NodeBase<NodeRef, KeyT, N> { 6788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 679a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen const KeyT &stop(unsigned i) const { return this->second[i]; } 680ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen const NodeRef &subtree(unsigned i) const { return this->first[i]; } 6818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 682a3b1082bb1ec2340d61b91dd91dbdd3ce5fa0867Jakob Stoklund Olesen KeyT &stop(unsigned i) { return this->second[i]; } 683ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NodeRef &subtree(unsigned i) { return this->first[i]; } 6848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// findFrom - Find the first subtree after i that may contain x. 6868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Starting index for the search. 68733fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in node. 6888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 6898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return First index with !stopLess(key[i], x), or size. 6908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is the first subtree that can possibly contain x. 6918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { 6928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i <= Size && Size <= N && "Bad indices"); 6938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 6948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen "Index to findFrom is past the needed point"); 6958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen while (i != Size && Traits::stopLess(stop(i), x)) ++i; 6968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return i; 6978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 6988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 6998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// safeFind - Find a subtree that is known to exist. This is the same as 7008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// findFrom except is it assumed that x is in range. 7018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Starting index for the search. 7028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 7038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return First index with !stopLess(key[i], x), never size. 7048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is the first subtree that can possibly contain x. 7058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned safeFind(unsigned i, KeyT x) const { 7068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i < N && "Bad index"); 7078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 7088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen "Index is past the needed point"); 7098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen while (Traits::stopLess(stop(i), x)) ++i; 7108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i < N && "Unsafe intervals"); 7118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return i; 7128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 7138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 7148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// safeLookup - Get the subtree containing x, Assuming that x is in range. 7158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param x Key to search for. 7168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @return Subtree containing x 717ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NodeRef safeLookup(KeyT x) const { 7188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return subtree(safeFind(0, x)); 7198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 7208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 7218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// insert - Insert a new (subtree, stop) pair. 7228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// @param i Insert position, following entries will be shifted. 72333fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Size Number of elements in node. 72433fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Node Subtree to insert. 72533fa490c5011b610ccf7b1206bbabb85d9a8cbaaJakob Stoklund Olesen /// @param Stop Last key in subtree. 726ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) { 7278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(Size < N && "branch node overflow"); 7288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(i <= Size && "Bad insert position"); 7298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen this->shift(i, Size); 7308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen subtree(i) = Node; 7318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen stop(i) = Stop; 7328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 7338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 7348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 735706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 736bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMapImpl::Path ---// 737706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 738706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// 739706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// A Path is used by iterators to represent a position in a B+-tree, and the 740706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// path to get there from the root. 741706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// 742706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// The Path class also constains the tree navigation code that doesn't have to 743706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// be templatized. 744706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen// 745706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 746706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 747706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesenclass Path { 748706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// Entry - Each step in the path is a node pointer and an offset into that 749706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// node. 750706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen struct Entry { 751706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void *node; 752706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned size; 753706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned offset; 754706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 755706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen Entry(void *Node, unsigned Size, unsigned Offset) 756706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen : node(Node), size(Size), offset(Offset) {} 757706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 758706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen Entry(NodeRef Node, unsigned Offset) 759706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {} 760706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 761706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef &subtree(unsigned i) const { 762706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return reinterpret_cast<NodeRef*>(node)[i]; 763706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 764706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen }; 765706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 766706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// path - The path entries, path[0] is the root node, path.back() is a leaf. 767706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen SmallVector<Entry, 4> path; 768706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 769706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesenpublic: 770706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Node accessors. 771706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen template <typename NodeT> NodeT &node(unsigned Level) const { 772706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return *reinterpret_cast<NodeT*>(path[Level].node); 773706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 774706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned size(unsigned Level) const { return path[Level].size; } 775706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned offset(unsigned Level) const { return path[Level].offset; } 776706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned &offset(unsigned Level) { return path[Level].offset; } 777706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 778706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Leaf accessors. 779706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen template <typename NodeT> NodeT &leaf() const { 780706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return *reinterpret_cast<NodeT*>(path.back().node); 781706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 782706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned leafSize() const { return path.back().size; } 783706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned leafOffset() const { return path.back().offset; } 784706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned &leafOffset() { return path.back().offset; } 785706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 786706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// valid - Return true if path is at a valid node, not at end(). 787706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen bool valid() const { 788706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return !path.empty() && path.front().offset < path.front().size; 789706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 790706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 791706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// height - Return the height of the tree corresponding to this path. 792706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// This matches map->height in a full path. 793706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned height() const { return path.size() - 1; } 794706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 795706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// subtree - Get the subtree referenced from Level. When the path is 796706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// consistent, node(Level + 1) == subtree(Level). 797706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level 0..height-1. The leaves have no subtrees. 798706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef &subtree(unsigned Level) const { 799706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return path[Level].subtree(path[Level].offset); 800706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 801706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 80253bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen /// reset - Reset cached information about node(Level) from subtree(Level -1). 80353bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen /// @param Level 1..height. THe node to update after parent node changed. 80453bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen void reset(unsigned Level) { 80553bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen path[Level] = Entry(subtree(Level - 1), offset(Level)); 80653bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen } 80753bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen 808706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// push - Add entry to path. 809706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Node Node to add, should be subtree(path.size()-1). 810706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Offset Offset into Node. 811706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void push(NodeRef Node, unsigned Offset) { 812706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.push_back(Entry(Node, Offset)); 813706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 814706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 815180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen /// pop - Remove the last path entry. 816180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen void pop() { 817180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.pop_back(); 818180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 819180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen 820706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// setSize - Set the size of a node both in the path and in the tree. 821706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level 0..height. Note that setting the root size won't change 822706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// map->rootSize. 823706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Size New node size. 824706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void setSize(unsigned Level, unsigned Size) { 825706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path[Level].size = Size; 826706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (Level) 827706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen subtree(Level - 1).setSize(Size); 828706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 829706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 830706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// setRoot - Clear the path and set a new root node. 831706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Node New root node. 832706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Size New root size. 833706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Offset Offset into root node. 834706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void setRoot(void *Node, unsigned Size, unsigned Offset) { 835706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.clear(); 836706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.push_back(Entry(Node, Size, Offset)); 837706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 838706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 839706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// replaceRoot - Replace the current root node with two new entries after the 840706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// tree height has increased. 841706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Root The new root node. 842706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Size Number of entries in the new root. 843706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Offsets Offsets into the root and first branch nodes. 844706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void replaceRoot(void *Root, unsigned Size, IdxPair Offsets); 845706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 846706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 847706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level Get the sibling to node(Level). 848706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @return Left sibling, or NodeRef(). 849706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef getLeftSibling(unsigned Level) const; 850706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 851706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level 852706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// unaltered. 853706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level Move node(Level). 854706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void moveLeft(unsigned Level); 855706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 856706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// fillLeft - Grow path to Height by taking leftmost branches. 857706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Height The target height. 858706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void fillLeft(unsigned Height) { 859706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen while (height() < Height) 860706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen push(subtree(height()), 0); 861706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 862706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 863706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 864706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level Get the sinbling to node(Level). 865706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @return Left sibling, or NodeRef(). 866706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef getRightSibling(unsigned Level) const; 867706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 868706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// moveRight - Move path to the left sibling at Level. Leave nodes below 869706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// Level unaltered. 870706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level Move node(Level). 871706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void moveRight(unsigned Level); 872706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 873055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen /// atBegin - Return true if path is at begin(). 874055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen bool atBegin() const { 875055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen for (unsigned i = 0, e = path.size(); i != e; ++i) 876055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen if (path[i].offset != 0) 877055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return false; 878055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return true; 879055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } 880055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 8817a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// atLastEntry - Return true if the path is at the last entry of the node at 8827a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// Level. 883706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level Node to examine. 8847a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen bool atLastEntry(unsigned Level) const { 885706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return path[Level].offset == path[Level].size - 1; 886706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 887706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 888706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// legalizeForInsert - Prepare the path for an insertion at Level. When the 889706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// path is at end(), node(Level) may not be a legal node. legalizeForInsert 890706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// ensures that node(Level) is real by moving back to the last node at Level, 891706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// and setting offset(Level) to size(Level) if required. 892706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen /// @param Level The level where an insertion is about to take place. 893706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void legalizeForInsert(unsigned Level) { 894706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (valid()) 895706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return; 896706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen moveLeft(Level); 897706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen ++path[Level].offset; 898706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen } 899706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen}; 900706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 9018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} // namespace IntervalMapImpl 9028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 9058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//--- IntervalMap ----// 9068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 9078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, 9098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize, 9108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen typename Traits = IntervalMapInfo<KeyT> > 9118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass IntervalMap { 912ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen typedef IntervalMapImpl::NodeSizer<KeyT, ValT> Sizer; 913ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen typedef IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits> Leaf; 914ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen typedef IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits> 915ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen Branch; 9168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf; 9178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen typedef IntervalMapImpl::IdxPair IdxPair; 9188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // The RootLeaf capacity is given as a template parameter. We must compute the 9208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // corresponding RootBranch capacity. 9218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen enum { 9228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) / 923ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)), 9248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1 9258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen }; 9268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 927ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits> 928ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen RootBranch; 9298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // When branched, we store a global start key as well as the branch node. 9318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen struct RootBranchData { 9328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT start; 9338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootBranch node; 9348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen }; 9358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen enum { 9378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ? 9388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen sizeof(RootBranchData) : sizeof(RootLeaf) 9398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen }; 9408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 942ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen typedef typename Sizer::Allocator Allocator; 943ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen typedef KeyT KeyType; 944ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen typedef ValT ValueType; 945cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen typedef Traits KeyTraits; 9468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenprivate: 9488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // The root data is either a RootLeaf or a RootBranchData instance. 9498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We can't put them in a union since C++03 doesn't allow non-trivial 9508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // constructors in unions. 9518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Instead, we use a char array with pointer alignment. The alignment is 9528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // ensured by the allocator member in the class, but still verified in the 9538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // constructor. We don't support keys or values that are more aligned than a 9548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // pointer. 9558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen char data[RootDataSize]; 9568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Tree height. 9588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // 0: Leaves in root. 9598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // 1: Root points to leaf. 9608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // 2: root->branch->leaf ... 9618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned height; 9628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Number of entries in the root node. 9648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned rootSize; 9658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Allocator used for creating external nodes. 9678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Allocator &allocator; 9688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// dataAs - Represent data as a node type without breaking aliasing rules. 9708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen template <typename T> 9718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen T &dataAs() const { 9728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen union { 9738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const char *d; 9748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen T *t; 9758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } u; 9768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen u.d = data; 9778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return *u.t; 9788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 9798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 9808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const RootLeaf &rootLeaf() const { 9818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(!branched() && "Cannot acces leaf data in branched root"); 9828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return dataAs<RootLeaf>(); 9838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 9848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootLeaf &rootLeaf() { 9858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(!branched() && "Cannot acces leaf data in branched root"); 9868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return dataAs<RootLeaf>(); 9878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 9888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootBranchData &rootBranchData() const { 9898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(branched() && "Cannot access branch data in non-branched root"); 9908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return dataAs<RootBranchData>(); 9918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 9928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootBranchData &rootBranchData() { 9938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(branched() && "Cannot access branch data in non-branched root"); 9948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return dataAs<RootBranchData>(); 9958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 9968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const RootBranch &rootBranch() const { return rootBranchData().node; } 9978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen RootBranch &rootBranch() { return rootBranchData().node; } 9988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT rootBranchStart() const { return rootBranchData().start; } 9998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT &rootBranchStart() { return rootBranchData().start; } 10008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1001b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen template <typename NodeT> NodeT *newNode() { 1002b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen return new(allocator.template Allocate<NodeT>()) NodeT(); 10038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1005b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen template <typename NodeT> void deleteNode(NodeT *P) { 1006b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P->~NodeT(); 10078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen allocator.Deallocate(P); 10088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IdxPair branchRoot(unsigned Position); 10118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IdxPair splitRoot(unsigned Position); 10128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void switchRootToBranch() { 10148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootLeaf().~RootLeaf(); 10158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen height = 1; 10168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen new (&rootBranchData()) RootBranchData(); 10178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void switchRootToLeaf() { 10208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootBranchData().~RootBranchData(); 10218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen height = 0; 10228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen new(&rootLeaf()) RootLeaf(); 10238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool branched() const { return height > 0; } 10268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen ValT treeSafeLookup(KeyT x, ValT NotFound) const; 1028ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, 1029ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen unsigned Level)); 1030ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level); 10318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 10338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) { 10348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 && 10358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen "Insufficient alignment"); 10368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen new(&rootLeaf()) RootLeaf(); 10378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1039785ab18a054373f1a2f8d0f6f04db2d458878bd9Jakob Stoklund Olesen ~IntervalMap() { 1040785ab18a054373f1a2f8d0f6f04db2d458878bd9Jakob Stoklund Olesen clear(); 1041785ab18a054373f1a2f8d0f6f04db2d458878bd9Jakob Stoklund Olesen rootLeaf().~RootLeaf(); 1042785ab18a054373f1a2f8d0f6f04db2d458878bd9Jakob Stoklund Olesen } 1043785ab18a054373f1a2f8d0f6f04db2d458878bd9Jakob Stoklund Olesen 10448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// empty - Return true when no intervals are mapped. 10458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool empty() const { 10468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return rootSize == 0; 10478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// start - Return the smallest mapped key in a non-empty map. 10508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT start() const { 10518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(!empty() && "Empty IntervalMap has no start"); 10528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return !branched() ? rootLeaf().start(0) : rootBranchStart(); 10538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// stop - Return the largest mapped key in a non-empty map. 10568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT stop() const { 10578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(!empty() && "Empty IntervalMap has no stop"); 10588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return !branched() ? rootLeaf().stop(rootSize - 1) : 10598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootBranch().stop(rootSize - 1); 10608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// lookup - Return the mapped value at x or NotFound. 10638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen ValT lookup(KeyT x, ValT NotFound = ValT()) const { 10648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x)) 10658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return NotFound; 10668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return branched() ? treeSafeLookup(x, NotFound) : 10678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootLeaf().safeLookup(x, NotFound); 10688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10698dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals. 10718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// It is assumed that no key in the interval is mapped to another value, but 10728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// overlapping intervals already mapped to y will be coalesced. 10738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void insert(KeyT a, KeyT b, ValT y) { 107479283768a36746bcb5885746637752312af9e4acJakob Stoklund Olesen if (branched() || rootSize == RootLeaf::Capacity) 107579283768a36746bcb5885746637752312af9e4acJakob Stoklund Olesen return find(a).insert(a, b, y); 107679283768a36746bcb5885746637752312af9e4acJakob Stoklund Olesen 107779283768a36746bcb5885746637752312af9e4acJakob Stoklund Olesen // Easy insert into root leaf. 107879283768a36746bcb5885746637752312af9e4acJakob Stoklund Olesen unsigned p = rootLeaf().findFrom(0, rootSize, a); 10795f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y); 10808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1082655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen /// clear - Remove all entries. 1083655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen void clear(); 1084655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen 10858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen class const_iterator; 10868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen class iterator; 10878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen friend class const_iterator; 10888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen friend class iterator; 10898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator begin() const { 1091da2fdcbb639de168738c27089bafa9ca10b731bdJakob Stoklund Olesen const_iterator I(*this); 10928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.goToBegin(); 10938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 10948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 10958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 10968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator begin() { 10978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator I(*this); 10988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.goToBegin(); 10998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator end() const { 1103da2fdcbb639de168738c27089bafa9ca10b731bdJakob Stoklund Olesen const_iterator I(*this); 11048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.goToEnd(); 11058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator end() { 11098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator I(*this); 11108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.goToEnd(); 11118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// find - Return an iterator pointing to the first interval ending at or 11158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// after x, or end(). 11168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator find(KeyT x) const { 1117da2fdcbb639de168738c27089bafa9ca10b731bdJakob Stoklund Olesen const_iterator I(*this); 11188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.find(x); 11198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator find(KeyT x) { 11238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen iterator I(*this); 11248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen I.find(x); 11258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return I; 11268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 11288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// treeSafeLookup - Return the mapped value at x or NotFound, assuming a 11308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// branched root. 11318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 11328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesenValT IntervalMap<KeyT, ValT, N, Traits>:: 11338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesentreeSafeLookup(KeyT x, ValT NotFound) const { 11348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(branched() && "treeLookup assumes a branched root"); 11358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1136ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x); 11378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned h = height-1; h; --h) 1138ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NR = NR.get<Branch>().safeLookup(x); 1139ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen return NR.get<Leaf>().safeLookup(x, NotFound); 11408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 11418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// branchRoot - Switch from a leaf root to a branched root. 11448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Return the new (root offset, node offset) corresponding to Position. 11458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 11468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesenIntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 11478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesenbranchRoot(unsigned Position) { 1148ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen using namespace IntervalMapImpl; 11498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // How many external leaf nodes to hold RootLeaf+1? 11508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1; 11518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Compute element distribution among new nodes. 11538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned size[Nodes]; 11548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IdxPair NewOffset(0, Position); 11558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Is is very common for the root node to be smaller than external nodes. 11578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Nodes == 1) 11588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen size[0] = rootSize; 11598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 11608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, size, 11618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Position, true); 11628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Allocate new nodes. 11648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned pos = 0; 11658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen NodeRef node[Nodes]; 11668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned n = 0; n != Nodes; ++n) { 1167b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Leaf *L = newNode<Leaf>(); 1168b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen L->copy(rootLeaf(), pos, 0, size[n]); 1169b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen node[n] = NodeRef(L, size[n]); 11708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen pos += size[n]; 11718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 11728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Destroy the old leaf node, construct branch node instead. 11748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen switchRootToBranch(); 11758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned n = 0; n != Nodes; ++n) { 1176ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1); 11778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootBranch().subtree(n) = node[n]; 11788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1179ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen rootBranchStart() = node[0].template get<Leaf>().start(0); 11808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootSize = Nodes; 11818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return NewOffset; 11828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 11838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// splitRoot - Split the current BranchRoot into multiple Branch nodes. 11858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// Return the new (root offset, node offset) corresponding to Position. 11868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 11878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesenIntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 11888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund OlesensplitRoot(unsigned Position) { 1189ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen using namespace IntervalMapImpl; 11908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // How many external leaf nodes to hold RootBranch+1? 11918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1; 11928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Compute element distribution among new nodes. 11948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Size[Nodes]; 11958dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IdxPair NewOffset(0, Position); 11968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 11978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Is is very common for the root node to be smaller than external nodes. 11988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Nodes == 1) 11998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Size[0] = rootSize; 12008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 12018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, Size, 12028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Position, true); 12038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Allocate new nodes. 12058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Pos = 0; 12068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen NodeRef Node[Nodes]; 12078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned n = 0; n != Nodes; ++n) { 1208b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Branch *B = newNode<Branch>(); 1209b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen B->copy(rootBranch(), Pos, 0, Size[n]); 1210b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Node[n] = NodeRef(B, Size[n]); 12118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Pos += Size[n]; 12128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 12138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned n = 0; n != Nodes; ++n) { 1215ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1); 12168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootBranch().subtree(n) = Node[n]; 12178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 12188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen rootSize = Nodes; 12196c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen ++height; 12208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return NewOffset; 12218dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 12228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// visitNodes - Visit each external node. 12248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 12258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1226ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund OlesenvisitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) { 12278dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (!branched()) 12288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return; 1229ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs; 12308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Collect level 0 nodes from the root. 12328dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned i = 0; i != rootSize; ++i) 12338dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Refs.push_back(rootBranch().subtree(i)); 12348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Visit all branch nodes. 12368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned h = height - 1; h; --h) { 12378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned i = 0, e = Refs.size(); i != e; ++i) { 12388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned j = 0, s = Refs[i].size(); j != s; ++j) 1239ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NextRefs.push_back(Refs[i].subtree(j)); 12408dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen (this->*f)(Refs[i], h); 12418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 12428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Refs.clear(); 12438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Refs.swap(NextRefs); 12448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 12458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Visit all leaf nodes. 12478dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (unsigned i = 0, e = Refs.size(); i != e; ++i) 12488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen (this->*f)(Refs[i], 0); 12498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 12508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1251655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1252655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1253ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund OlesendeleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) { 1254655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen if (Level) 1255b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen deleteNode(&Node.get<Branch>()); 1256655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen else 1257b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen deleteNode(&Node.get<Leaf>()); 1258655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen} 1259655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen 1260655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1261655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1262655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesenclear() { 1263655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen if (branched()) { 1264655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen visitNodes(&IntervalMap::deleteNode); 1265655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen switchRootToLeaf(); 1266655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen } 1267655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen rootSize = 0; 1268655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen} 1269655fbb4f9b46ea93eddf0815eaed0020e9347416Jakob Stoklund Olesen 12708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1271bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMap::const_iterator ----// 12728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 12738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12748dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 12758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass IntervalMap<KeyT, ValT, N, Traits>::const_iterator : 12768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen public std::iterator<std::bidirectional_iterator_tag, ValT> { 12778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenprotected: 12788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen friend class IntervalMap; 12798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // The map referred to. 12818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen IntervalMap *map; 12828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We store a full path from the root to the current position. 12848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // The path may be partially filled, but never between iterator calls. 1285706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMapImpl::Path path; 12868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1287da2fdcbb639de168738c27089bafa9ca10b731bdJakob Stoklund Olesen explicit const_iterator(const IntervalMap &map) : 1288da2fdcbb639de168738c27089bafa9ca10b731bdJakob Stoklund Olesen map(const_cast<IntervalMap*>(&map)) {} 12898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 12908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool branched() const { 12918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(map && "Invalid iterator"); 12928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return map->branched(); 12938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 12948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1295706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen void setRoot(unsigned Offset) { 1296706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (branched()) 1297706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.setRoot(&map->rootBranch(), map->rootSize, Offset); 12988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1299706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.setRoot(&map->rootLeaf(), map->rootSize, Offset); 13008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void pathFillFind(KeyT x); 13038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void treeFind(KeyT x); 1304180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen void treeAdvanceTo(KeyT x); 13058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13067a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// unsafeStart - Writable access to start() for iterator. 13077a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT &unsafeStart() const { 13088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(valid() && "Cannot access invalid iterator"); 1309706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return branched() ? path.leaf<Leaf>().start(path.leafOffset()) : 1310706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.leaf<RootLeaf>().start(path.leafOffset()); 13118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13137a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// unsafeStop - Writable access to stop() for iterator. 13147a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT &unsafeStop() const { 13158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(valid() && "Cannot access invalid iterator"); 1316706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) : 1317706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.leaf<RootLeaf>().stop(path.leafOffset()); 13188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13207a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// unsafeValue - Writable access to value() for iterator. 13217a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen ValT &unsafeValue() const { 13228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(valid() && "Cannot access invalid iterator"); 1323706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return branched() ? path.leaf<Leaf>().value(path.leafOffset()) : 1324706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.leaf<RootLeaf>().value(path.leafOffset()); 13258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13268dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13277a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenpublic: 13287a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// const_iterator - Create an iterator that isn't pointing anywhere. 13297a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen const_iterator() : map(0) {} 13307a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 13315907d863659eb972ebb2afe07bc863a4c616f0efJakob Stoklund Olesen /// setMap - Change the map iterated over. This call must be followed by a 13325907d863659eb972ebb2afe07bc863a4c616f0efJakob Stoklund Olesen /// call to goToBegin(), goToEnd(), or find() 13335907d863659eb972ebb2afe07bc863a4c616f0efJakob Stoklund Olesen void setMap(const IntervalMap &m) { map = const_cast<IntervalMap*>(&m); } 13345907d863659eb972ebb2afe07bc863a4c616f0efJakob Stoklund Olesen 13357a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// valid - Return true if the current position is valid, false for end(). 13367a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen bool valid() const { return path.valid(); } 13377a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 1338cafe614035c8db70eb5da96dba00696db381674fJakob Stoklund Olesen /// atBegin - Return true if the current position is the first map entry. 1339cafe614035c8db70eb5da96dba00696db381674fJakob Stoklund Olesen bool atBegin() const { return path.atBegin(); } 1340cafe614035c8db70eb5da96dba00696db381674fJakob Stoklund Olesen 13417a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// start - Return the beginning of the current interval. 13427a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen const KeyT &start() const { return unsafeStart(); } 13437a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 13447a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// stop - Return the end of the current interval. 13457a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen const KeyT &stop() const { return unsafeStop(); } 13467a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 13477a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// value - Return the mapped value at the current interval. 13487a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen const ValT &value() const { return unsafeValue(); } 13497a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 13507a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen const ValT &operator*() const { return value(); } 13518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool operator==(const const_iterator &RHS) const { 13538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(map == RHS.map && "Cannot compare iterators from different maps"); 1354706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (!valid()) 1355706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return !RHS.valid(); 1356706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (path.leafOffset() != RHS.path.leafOffset()) 1357706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return false; 1358706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>(); 13598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen bool operator!=(const const_iterator &RHS) const { 13628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return !operator==(RHS); 13638dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// goToBegin - Move to the first interval in map. 13668dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void goToBegin() { 1367706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen setRoot(0); 13688dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (branched()) 1369706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.fillLeft(map->height); 13708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// goToEnd - Move beyond the last interval in map. 13738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void goToEnd() { 1374706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen setRoot(map->rootSize); 13758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// preincrement - move to the next interval. 13788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator &operator++() { 13798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen assert(valid() && "Cannot increment end()"); 1380706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (++path.leafOffset() == path.leafSize() && branched()) 1381706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.moveRight(map->height); 13828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return *this; 13838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// postincrement - Dont do that! 13868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator operator++(int) { 13878dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator tmp = *this; 13888dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen operator++(); 13898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return tmp; 13908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 13918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 13928dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// predecrement - move to the previous interval. 13938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator &operator--() { 1394706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (path.leafOffset() && (valid() || !branched())) 1395706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen --path.leafOffset(); 13968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1397706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.moveLeft(map->height); 13988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return *this; 13998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 14008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// postdecrement - Dont do that! 14028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator operator--(int) { 14038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen const_iterator tmp = *this; 14048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen operator--(); 14058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return tmp; 14068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 14078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// find - Move to the first interval with stop >= x, or end(). 14098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// This is a full search from the root, the current position is ignored. 14108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void find(KeyT x) { 14118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (branched()) 14128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen treeFind(x); 14138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1414706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen setRoot(map->rootLeaf().findFrom(0, map->rootSize, x)); 14158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 14168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14178dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// advanceTo - Move to the first interval with stop >= x, or end(). 14188dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// The search is started from the current position, and no earlier positions 14198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// can be found. This is much faster than find() for small moves. 14208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void advanceTo(KeyT x) { 14215049ee5b11fe55e5a553b5388406aab874717672Jakob Stoklund Olesen if (!valid()) 14225049ee5b11fe55e5a553b5388406aab874717672Jakob Stoklund Olesen return; 14238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (branched()) 14248dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen treeAdvanceTo(x); 14258dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen else 1426706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.leafOffset() = 1427706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x); 14288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 14298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 14318dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1432180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// pathFillFind - Complete path by searching for x. 1433180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// @param x Key to search for. 14348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 14358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 14368dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenconst_iterator::pathFillFind(KeyT x) { 1437706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMapImpl::NodeRef NR = path.subtree(path.height()); 1438706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen for (unsigned i = map->height - path.height() - 1; i; --i) { 1439ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen unsigned p = NR.get<Branch>().safeFind(0, x); 1440706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.push(NR, p); 1441ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen NR = NR.subtree(p); 14428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1443706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen path.push(NR, NR.get<Leaf>().safeFind(0, x)); 14448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 14458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1446180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// treeFind - Find in a branched tree. 1447180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// @param x Key to search for. 14488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 14498dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 14508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenconst_iterator::treeFind(KeyT x) { 1451706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen setRoot(map->rootBranch().findFrom(0, map->rootSize, x)); 14528dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (valid()) 14538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen pathFillFind(x); 14548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 14558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1456180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// treeAdvanceTo - Find position after the current one. 1457180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen/// @param x Key to search for. 1458180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1459180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1460180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesenconst_iterator::treeAdvanceTo(KeyT x) { 1461180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // Can we stay on the same leaf node? 1462180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) { 1463180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x); 1464180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen return; 1465180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 1466180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen 1467180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // Drop the current leaf. 1468180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.pop(); 1469180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen 1470180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // Search towards the root for a usable subtree. 1471180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen if (path.height()) { 1472180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen for (unsigned l = path.height() - 1; l; --l) { 1473180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) { 1474180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // The branch node at l+1 is usable 1475180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.offset(l + 1) = 1476180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x); 1477180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen return pathFillFind(x); 1478180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 1479180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.pop(); 1480180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 1481180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // Is the level-1 Branch usable? 1482180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) { 1483180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x); 1484180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen return pathFillFind(x); 1485180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 1486180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen } 1487180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen 1488180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen // We reached the root. 1489180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x)); 1490180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen if (valid()) 1491180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen pathFillFind(x); 1492180e1247ca330b047eabafbc72926ce9bfd8bf8eJakob Stoklund Olesen} 14938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1495bf953eaba3442f8e25926b8f41423d4d126960f6Jakob Stoklund Olesen//--- IntervalMap::iterator ----// 14968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 14978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 14988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 14998dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenclass IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator { 15008dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen friend class IntervalMap; 15018dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen typedef IntervalMapImpl::IdxPair IdxPair; 15028dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 15038dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen explicit iterator(IntervalMap &map) : const_iterator(map) {} 15048dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 15058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void setNodeStop(unsigned Level, KeyT Stop); 15066c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop); 15076c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen template <typename NodeT> bool overflow(unsigned Level); 15088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void treeInsert(KeyT a, KeyT b, ValT y); 1509b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen void eraseNode(unsigned Level); 1510055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen void treeErase(bool UpdateRoot = true); 15117a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen bool canCoalesceLeft(KeyT Start, ValT x); 15127a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen bool canCoalesceRight(KeyT Stop, ValT x); 15137a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15148dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenpublic: 15159a08ca318e63912e4c19977abc1173f30866b704Jakob Stoklund Olesen /// iterator - Create null iterator. 15169a08ca318e63912e4c19977abc1173f30866b704Jakob Stoklund Olesen iterator() {} 15179a08ca318e63912e4c19977abc1173f30866b704Jakob Stoklund Olesen 15187a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setStart - Move the start of the current interval. 15197a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// This may cause coalescing with the previous interval. 15207a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param a New start key, must not overlap the previous interval. 15217a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setStart(KeyT a); 15227a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15237a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setStop - Move the end of the current interval. 15247a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// This may cause coalescing with the following interval. 15257a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param b New stop key, must not overlap the following interval. 15267a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setStop(KeyT b); 15277a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15287a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setValue - Change the mapped value of the current interval. 15297a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// This may cause coalescing with the previous and following intervals. 15307a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param x New value. 15317a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setValue(ValT x); 15327a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15337a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setStartUnchecked - Move the start of the current interval without 15347a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// checking for coalescing or overlaps. 15357a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// This should only be used when it is known that coalescing is not required. 15367a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param a New start key. 15377a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setStartUnchecked(KeyT a) { this->unsafeStart() = a; } 15387a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15397a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setStopUnchecked - Move the end of the current interval without checking 15407a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// for coalescing or overlaps. 15417a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// This should only be used when it is known that coalescing is not required. 15427a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param b New stop key. 15437a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setStopUnchecked(KeyT b) { 15447a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen this->unsafeStop() = b; 15457a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen // Update keys in branch nodes as well. 15467a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (this->path.atLastEntry(this->path.height())) 15477a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setNodeStop(this->path.height(), b); 15487a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 15497a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15507a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// setValueUnchecked - Change the mapped value of the current interval 15517a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// without checking for coalescing. 15527a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen /// @param x New value. 15537a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen void setValueUnchecked(ValT x) { this->unsafeValue() = x; } 15547a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 15558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen /// insert - Insert mapping [a;b] -> y before the current position. 15568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen void insert(KeyT a, KeyT b, ValT y); 15578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1558b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen /// erase - Erase the current interval. 1559b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen void erase(); 1560055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 1561055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator &operator++() { 1562055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen const_iterator::operator++(); 1563055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return *this; 1564055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } 1565055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 1566055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator operator++(int) { 1567055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator tmp = *this; 1568055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen operator++(); 1569055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return tmp; 1570055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } 1571055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 1572055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator &operator--() { 1573055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen const_iterator::operator--(); 1574055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return *this; 1575055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } 1576055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 1577055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator operator--(int) { 1578055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen iterator tmp = *this; 1579055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen operator--(); 1580055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen return tmp; 1581055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } 1582055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen 15838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen}; 15848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 15857a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// canCoalesceLeft - Can the current interval coalesce to the left after 15867a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// changing start or value? 15877a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @param Start New start of current interval. 15887a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @param Value New value for current interval. 15897a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @return True when updating the current interval would enable coalescing. 15907a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 15917a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenbool IntervalMap<KeyT, ValT, N, Traits>:: 15927a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Oleseniterator::canCoalesceLeft(KeyT Start, ValT Value) { 15937a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen using namespace IntervalMapImpl; 15947a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Path &P = this->path; 15957a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (!this->branched()) { 15967a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen unsigned i = P.leafOffset(); 15977a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen RootLeaf &Node = P.leaf<RootLeaf>(); 15987a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return i && Node.value(i-1) == Value && 15997a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Traits::adjacent(Node.stop(i-1), Start); 16007a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16017a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen // Branched. 16027a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (unsigned i = P.leafOffset()) { 16037a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Leaf &Node = P.leaf<Leaf>(); 16047a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start); 16057a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } else if (NodeRef NR = P.getLeftSibling(P.height())) { 16067a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen unsigned i = NR.size() - 1; 16077a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Leaf &Node = NR.get<Leaf>(); 16087a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start); 16097a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16107a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return false; 16117a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen} 16127a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 16137a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// canCoalesceRight - Can the current interval coalesce to the right after 16147a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// changing stop or value? 16157a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @param Stop New stop of current interval. 16167a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @param Value New value for current interval. 16177a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen/// @return True when updating the current interval would enable coalescing. 16187a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 16197a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenbool IntervalMap<KeyT, ValT, N, Traits>:: 16207a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Oleseniterator::canCoalesceRight(KeyT Stop, ValT Value) { 16217a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen using namespace IntervalMapImpl; 16227a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Path &P = this->path; 16237a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen unsigned i = P.leafOffset() + 1; 16247a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (!this->branched()) { 16257a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (i >= P.leafSize()) 16267a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return false; 16277a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen RootLeaf &Node = P.leaf<RootLeaf>(); 16287a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); 16297a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16307a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen // Branched. 16317a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (i < P.leafSize()) { 16327a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Leaf &Node = P.leaf<Leaf>(); 16337a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); 16347a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } else if (NodeRef NR = P.getRightSibling(P.height())) { 16357a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen Leaf &Node = NR.get<Leaf>(); 16367a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0)); 16377a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16387a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return false; 16397a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen} 16407a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 16418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// setNodeStop - Update the stop key of the current node at level and above. 16428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 16438dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 16448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Oleseniterator::setNodeStop(unsigned Level, KeyT Stop) { 1645706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // There are no references to the root node, so nothing to update. 1646706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (!Level) 1647706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen return; 1648706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 1649706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Update nodes pointing to the current node. 1650706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen while (--Level) { 1651706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.node<Branch>(Level).stop(P.offset(Level)) = Stop; 16527a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (!P.atLastEntry(Level)) 16538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return; 16548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1655706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Update root separately since it has a different layout. 1656706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop; 16578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 16588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 16597a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 16607a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 16617a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Oleseniterator::setStart(KeyT a) { 16627a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen assert(Traits::stopLess(a, this->stop()) && "Cannot move start beyond stop"); 16637a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT &CurStart = this->unsafeStart(); 16647a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) { 16657a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen CurStart = a; 16667a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return; 16677a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16687a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen // Coalesce with the interval to the left. 16697a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen --*this; 16707a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen a = this->start(); 16717a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen erase(); 16727a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setStartUnchecked(a); 16737a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen} 16747a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 16757a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 16767a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 16777a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Oleseniterator::setStop(KeyT b) { 16787a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen assert(Traits::stopLess(this->start(), b) && "Cannot move stop beyond start"); 16797a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (Traits::startLess(b, this->stop()) || 16807a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen !canCoalesceRight(b, this->value())) { 16817a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setStopUnchecked(b); 16827a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen return; 16837a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16847a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen // Coalesce with interval to the right. 16857a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT a = this->start(); 16867a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen erase(); 16877a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setStartUnchecked(a); 16887a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen} 16897a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 16907a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 16917a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 16927a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Oleseniterator::setValue(ValT x) { 16937a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setValueUnchecked(x); 16947a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (canCoalesceRight(this->stop(), x)) { 16957a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT a = this->start(); 16967a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen erase(); 16977a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setStartUnchecked(a); 16987a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 16997a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (canCoalesceLeft(this->start(), x)) { 17007a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen --*this; 17017a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen KeyT a = this->start(); 17027a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen erase(); 17037a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen setStartUnchecked(a); 17047a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen } 17057a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen} 17067a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen 17078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// insertNode - insert a node before the current path at level. 17088dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen/// Leave the current path pointing at the new node. 17096c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @param Level path index of the node to be inserted. 17106c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @param Node The node to be inserted. 17116c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @param Stop The last index in the new node. 17126c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @return True if the tree height was increased. 17138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 17146c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesenbool IntervalMap<KeyT, ValT, N, Traits>:: 1715ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Oleseniterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) { 1716706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen assert(Level && "Cannot insert next to the root"); 17176c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen bool SplitRoot = false; 1718706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMap &IM = *this->map; 1719706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 17206c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen 1721706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (Level == 1) { 17228dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Insert into the root branch node. 17238dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (IM.rootSize < RootBranch::Capacity) { 1724706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop); 1725706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.setSize(0, ++IM.rootSize); 172653bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen P.reset(Level); 17276c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen return SplitRoot; 17288dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 17298dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 17308dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // We need to split the root while keeping our position. 17316c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen SplitRoot = true; 1732706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IdxPair Offset = IM.splitRoot(P.offset(0)); 1733706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1734706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1735706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Fall through to insert at the new higher level. 1736706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen ++Level; 17378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 17388dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 17398dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // When inserting before end(), make sure we have a valid path. 1740706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.legalizeForInsert(--Level); 17418dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1742706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Insert into the branch node at Level-1. 1743706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen if (P.size(Level) == Branch::Capacity) { 1744706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Branch node is full, handle handle the overflow. 17456c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen assert(!SplitRoot && "Cannot overflow after splitting the root"); 1746706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen SplitRoot = overflow<Branch>(Level); 17476c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen Level += SplitRoot; 17486c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen } 1749706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop); 1750706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.setSize(Level, P.size(Level) + 1); 17517a26aca73ff2c8c4cb3205a776cc6743949b1fb7Jakob Stoklund Olesen if (P.atLastEntry(Level)) 175253bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen setNodeStop(Level, Stop); 175353bb5c009b04f4a5dd2388b25efe88b5579b282cJakob Stoklund Olesen P.reset(Level + 1); 17546c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen return SplitRoot; 17558dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 17568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 17578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen// insert 17588dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 17598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 17608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Oleseniterator::insert(KeyT a, KeyT b, ValT y) { 17618dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (this->branched()) 17628dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return treeInsert(a, b, y); 1763706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMap &IM = *this->map; 1764706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 1765706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1766706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Try simple root leaf insert. 17675f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y); 1768706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1769706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Was the root node insert successful? 17705f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (Size <= RootLeaf::Capacity) { 17715f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen P.setSize(0, IM.rootSize = Size); 17728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen return; 17738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1774706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1775706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Root leaf node is full, we must branch. 1776706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen IdxPair Offset = IM.branchRoot(P.leafOffset()); 1777706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 1778706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1779706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Now it fits in the new leaf. 17808dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen treeInsert(a, b, y); 17818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 17828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 17838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 17848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 17858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 17868dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Oleseniterator::treeInsert(KeyT a, KeyT b, ValT y) { 1787b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen using namespace IntervalMapImpl; 1788b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Path &P = this->path; 1789b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 17905f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (!P.valid()) 17915f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen P.legalizeForInsert(this->map->height); 17925f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen 1793b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Check if this insertion will extend the node to the left. 17945f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) { 1795b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Node is growing to the left, will it affect a left sibling node? 17965f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (NodeRef Sib = P.getLeftSibling(P.height())) { 1797b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Leaf &SibLeaf = Sib.get<Leaf>(); 1798b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen unsigned SibOfs = Sib.size() - 1; 1799b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (SibLeaf.value(SibOfs) == y && 1800b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Traits::adjacent(SibLeaf.stop(SibOfs), a)) { 1801b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // This insertion will coalesce with the last entry in SibLeaf. We can 1802b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // handle it in two ways: 1803b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // 1. Extend SibLeaf.stop to b and be done, or 1804b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // 2. Extend a to SibLeaf, erase the SibLeaf entry and continue. 1805b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // We prefer 1., but need 2 when coalescing to the right as well. 1806b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Leaf &CurLeaf = P.leaf<Leaf>(); 18075f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen P.moveLeft(P.height()); 1808b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (Traits::stopLess(b, CurLeaf.start(0)) && 1809b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) { 1810b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Easy, just extend SibLeaf and we're done. 18115f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b); 1812b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen return; 1813b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } else { 1814b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // We have both left and right coalescing. Erase the old SibLeaf entry 1815b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // and continue inserting the larger interval. 1816b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen a = SibLeaf.start(SibOfs); 1817055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen treeErase(/* UpdateRoot= */false); 1818b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1819b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1820b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } else { 1821b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // No left sibling means we are at begin(). Update cached bound. 18225f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen this->map->rootBranchStart() = a; 1823b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1824b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1825706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 18265f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen // When we are inserting at the end of a leaf node, we must update stops. 18275f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen unsigned Size = P.leafSize(); 18285f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen bool Grow = P.leafOffset() == Size; 18295f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y); 1830706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1831706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Leaf insertion unsuccessful? Overflow and try again. 18325f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (Size > Leaf::Capacity) { 18335f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen overflow<Leaf>(P.height()); 18345f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen Grow = P.leafOffset() == P.leafSize(); 18355f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y); 18365f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen assert(Size <= Leaf::Capacity && "overflow() didn't make room"); 18378dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 1838706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1839706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Inserted, update offset and leaf size. 18405f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen P.setSize(P.height(), Size); 1841706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen 1842706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen // Insert was the last node entry, update stops. 18435f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen if (Grow) 18445f456cda98c57b6dea8bc716978b69776d0d0e8fJakob Stoklund Olesen setNodeStop(P.height(), b); 1845b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen} 18468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 1847b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// erase - erase the current interval and move to the next position. 1848b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1849b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1850b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Oleseniterator::erase() { 1851b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMap &IM = *this->map; 1852b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 1853b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen assert(P.valid() && "Cannot erase end()"); 1854b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (this->branched()) 1855b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen return treeErase(); 1856b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IM.rootLeaf().erase(P.leafOffset(), IM.rootSize); 1857b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.setSize(0, --IM.rootSize); 1858b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen} 1859b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 1860b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// treeErase - erase() for a branched tree. 1861b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1862b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1863055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Oleseniterator::treeErase(bool UpdateRoot) { 1864b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMap &IM = *this->map; 1865b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 1866b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Leaf &Node = P.leaf<Leaf>(); 1867b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 1868b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Nodes are not allowed to become empty. 1869b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (P.leafSize() == 1) { 1870b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IM.deleteNode(&Node); 1871b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen eraseNode(IM.height); 1872055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen // Update rootBranchStart if we erased begin(). 1873055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen if (UpdateRoot && IM.branched() && P.valid() && P.atBegin()) 1874055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1875b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen return; 1876b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1877b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 1878b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Erase current entry. 1879b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Node.erase(P.leafOffset(), P.leafSize()); 1880b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen unsigned NewSize = P.leafSize() - 1; 1881b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.setSize(IM.height, NewSize); 1882b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // When we erase the last entry, update stop and move to a legal position. 1883b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (P.leafOffset() == NewSize) { 1884b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen setNodeStop(IM.height, Node.stop(NewSize - 1)); 1885b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.moveRight(IM.height); 1886055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen } else if (UpdateRoot && P.atBegin()) 1887055942529bbc8487f86b47940dbd6a790516573eJakob Stoklund Olesen IM.rootBranchStart() = P.leaf<Leaf>().start(0); 1888b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen} 1889b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 1890b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// eraseNode - Erase the current node at Level from its parent and move path to 1891b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// the first entry of the next sibling node. 1892b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// The node must be deallocated by the caller. 1893b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen/// @param Level 1..height, the root node cannot be erased. 1894b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 1895b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesenvoid IntervalMap<KeyT, ValT, N, Traits>:: 1896b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Oleseniterator::eraseNode(unsigned Level) { 1897b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen assert(Level && "Cannot erase root node"); 1898b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMap &IM = *this->map; 1899b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IntervalMapImpl::Path &P = this->path; 1900b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen 1901b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (--Level == 0) { 1902b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IM.rootBranch().erase(P.offset(0), IM.rootSize); 1903b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.setSize(0, --IM.rootSize); 1904b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // If this cleared the root, switch to height=0. 1905b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (IM.empty()) { 1906b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IM.switchRootToLeaf(); 1907b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen this->setRoot(0); 1908b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen return; 1909b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1910b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } else { 1911b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Remove node ref from branch node at Level. 1912b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Branch &Parent = P.node<Branch>(Level); 1913b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (P.size(Level) == 1) { 1914b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Branch node became empty, remove it recursively. 1915b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen IM.deleteNode(&Parent); 1916b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen eraseNode(Level); 1917b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } else { 1918b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Branch node won't become empty. 1919b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Parent.erase(P.offset(Level), P.size(Level)); 1920b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen unsigned NewSize = P.size(Level) - 1; 1921b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.setSize(Level, NewSize); 1922b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // If we removed the last branch, update stop and move to a legal pos. 1923b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (P.offset(Level) == NewSize) { 1924b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen setNodeStop(Level, Parent.stop(NewSize - 1)); 1925b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.moveRight(Level); 1926b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1927b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1928b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 1929b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen // Update path cache for the new right sibling position. 1930b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen if (P.valid()) { 1931b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.reset(Level + 1); 1932b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen P.offset(Level + 1) = 0; 1933b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen } 19348dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 19358dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19366c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// overflow - Distribute entries of the current node evenly among 19376c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// its siblings and ensure that the current node is not full. 19386c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// This may require allocating a new node. 19396c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @param NodeT The type of node at Level (Leaf or Branch). 19406c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @param Level path index of the overflowing node. 19416c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen/// @return True when the tree height was changed. 19428dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesentemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 19436c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesentemplate <typename NodeT> 19446c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesenbool IntervalMap<KeyT, ValT, N, Traits>:: 19456c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Oleseniterator::overflow(unsigned Level) { 1946ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen using namespace IntervalMapImpl; 1947706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen Path &P = this->path; 19488dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned CurSize[4]; 19496c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen NodeT *Node[4]; 19508dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Nodes = 0; 19518dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Elements = 0; 1952706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen unsigned Offset = P.offset(Level); 19538dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19548dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Do we have a left sibling? 1955706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef LeftSib = P.getLeftSibling(Level); 19568dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (LeftSib) { 19578dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Offset += Elements = CurSize[Nodes] = LeftSib.size(); 19586c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen Node[Nodes++] = &LeftSib.get<NodeT>(); 19598dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 19608dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19616c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen // Current node. 1962706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen Elements += CurSize[Nodes] = P.size(Level); 1963706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen Node[Nodes++] = &P.node<NodeT>(Level); 19648dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19658dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Do we have a right sibling? 1966706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen NodeRef RightSib = P.getRightSibling(Level); 19678dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (RightSib) { 1968b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Elements += CurSize[Nodes] = RightSib.size(); 19696c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen Node[Nodes++] = &RightSib.get<NodeT>(); 19708dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 19718dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19728dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Do we need to allocate a new node? 19738dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned NewNode = 0; 19746c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen if (Elements + 1 > Nodes * NodeT::Capacity) { 19758dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Insert NewNode at the penultimate position, or after a single node. 19768dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen NewNode = Nodes == 1 ? 1 : Nodes - 1; 19778dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen CurSize[Nodes] = CurSize[NewNode]; 19788dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen Node[Nodes] = Node[NewNode]; 19798dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen CurSize[NewNode] = 0; 1980b0b7214fc90febbbe71e1e989130194ce2b70a36Jakob Stoklund Olesen Node[NewNode] = this->map->newNode<NodeT>(); 19818dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen ++Nodes; 19828dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 19838dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19848dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Compute the new element distribution. 19858dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned NewSize[4]; 19866c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity, 1987ddd0e65dba1de71eaa8901cd6f787754e34c3fe0Jakob Stoklund Olesen CurSize, NewSize, Offset, true); 1988bf77baf19cfbc7a8795d9683e9b9ec894b9ff8c9Jakob Stoklund Olesen adjustSiblingSizes(Node, Nodes, CurSize, NewSize); 19898dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19908dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Move current location to the leftmost node. 19918dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (LeftSib) 1992706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.moveLeft(Level); 19938dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 19948dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Elements have been rearranged, now update node sizes and stops. 19956c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen bool SplitRoot = false; 19968dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen unsigned Pos = 0; 19978dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen for (;;) { 19988dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1); 19996c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen if (NewNode && Pos == NewNode) { 20006c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop); 20016c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen Level += SplitRoot; 20026c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen } else { 2003706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.setSize(Level, NewSize[Pos]); 20046c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen setNodeStop(Level, Stop); 20058dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 20068dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen if (Pos + 1 == Nodes) 20078dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen break; 2008706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.moveRight(Level); 20098dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen ++Pos; 20108dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 20118dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 20128dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen // Where was I? Find NewOffset. 20138dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen while(Pos != NewOffset.first) { 2014706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.moveLeft(Level); 20158dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen --Pos; 20168dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen } 2017706da9d8ca207c93d38855ffd96cf9722996d706Jakob Stoklund Olesen P.offset(Level) = NewOffset.second; 20186c76f5fa2fb839c736c572f45c138e5b3f549530Jakob Stoklund Olesen return SplitRoot; 20198dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} 20208dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 2021cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 2022cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen//--- IntervalMapOverlaps ----// 2023cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 2024cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2025cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two 2026cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// IntervalMaps. The maps may be different, but the KeyT and Traits types 2027cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// should be the same. 2028cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 2029cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// Typical uses: 2030cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 2031cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 1. Test for overlap: 2032cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// bool overlap = IntervalMapOverlaps(a, b).valid(); 2033cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 2034cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 2. Enumerate overlaps: 2035cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... } 2036cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen/// 2037cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesentemplate <typename MapA, typename MapB> 2038cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesenclass IntervalMapOverlaps { 2039ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen typedef typename MapA::KeyType KeyType; 2040cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen typedef typename MapA::KeyTraits Traits; 2041cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen typename MapA::const_iterator posA; 2042cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen typename MapB::const_iterator posB; 2043cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2044cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// advance - Move posA and posB forward until reaching an overlap, or until 2045cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// either meets end. 2046cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// Don't move the iterators if they are already overlapping. 2047cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen void advance() { 20484aec85ae01188f87e45e5e91baab4f303cbcd336Jakob Stoklund Olesen if (!valid()) 20494aec85ae01188f87e45e5e91baab4f303cbcd336Jakob Stoklund Olesen return; 2050d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen 2051d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (Traits::stopLess(posA.stop(), posB.start())) { 2052d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen // A ends before B begins. Catch up. 2053d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen posA.advanceTo(posB.start()); 2054d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start())) 2055d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen return; 2056d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen } else if (Traits::stopLess(posB.stop(), posA.start())) { 2057d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen // B ends before A begins. Catch up. 2058d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen posB.advanceTo(posA.start()); 2059d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start())) 2060d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen return; 2061d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen } else 2062d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen // Already overlapping. 2063d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen return; 2064d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen 2065cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen for (;;) { 2066cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen // Make a.end > b.start. 2067cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen posA.advanceTo(posB.start()); 2068460ee0fd19b13ba4c1410e43d8d253bf34673817Jakob Stoklund Olesen if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start())) 2069cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen return; 2070cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen // Make b.end > a.start. 2071cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen posB.advanceTo(posA.start()); 2072460ee0fd19b13ba4c1410e43d8d253bf34673817Jakob Stoklund Olesen if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start())) 2073cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen return; 2074cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2075cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2076cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2077cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesenpublic: 2078cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b. 2079cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen IntervalMapOverlaps(const MapA &a, const MapB &b) 2080cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen : posA(b.empty() ? a.end() : a.find(b.start())), 20814aec85ae01188f87e45e5e91baab4f303cbcd336Jakob Stoklund Olesen posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); } 2082cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2083cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// valid - Return true if iterator is at an overlap. 2084cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen bool valid() const { 2085cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen return posA.valid() && posB.valid(); 2086cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2087cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2088cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// a - access the left hand side in the overlap. 2089cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen const typename MapA::const_iterator &a() const { return posA; } 2090cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2091cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// b - access the right hand side in the overlap. 2092cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen const typename MapB::const_iterator &b() const { return posB; } 2093cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2094ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen /// start - Beginning of the overlapping interval. 2095ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType start() const { 2096ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType ak = a().start(); 2097ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType bk = b().start(); 2098ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen return Traits::startLess(ak, bk) ? bk : ak; 2099ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen } 2100ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen 2101d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen /// stop - End of the overlapping interval. 2102ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType stop() const { 2103ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType ak = a().stop(); 2104ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen KeyType bk = b().stop(); 2105ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen return Traits::startLess(ak, bk) ? ak : bk; 2106ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen } 2107ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen 2108cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// skipA - Move to the next overlap that doesn't involve a(). 2109cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen void skipA() { 2110cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen ++posA; 2111cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen advance(); 2112cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2113cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2114cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// skipB - Move to the next overlap that doesn't involve b(). 2115cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen void skipB() { 2116cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen ++posB; 2117cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen advance(); 2118cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2119cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2120cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen /// Preincrement - Move to the next overlap. 2121cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen IntervalMapOverlaps &operator++() { 2122cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen // Bump the iterator that ends first. The other one may have more overlaps. 2123460ee0fd19b13ba4c1410e43d8d253bf34673817Jakob Stoklund Olesen if (Traits::startLess(posB.stop(), posA.stop())) 2124cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen skipB(); 2125cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen else 2126cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen skipA(); 2127cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen return *this; 2128cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen } 2129cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 2130ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen /// advanceTo - Move to the first overlapping interval with 2131ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen /// stopLess(x, stop()). 2132ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen void advanceTo(KeyType x) { 2133d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (!valid()) 2134d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen return; 2135d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen // Make sure advanceTo sees monotonic keys. 2136d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (Traits::stopLess(posA.stop(), x)) 2137d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen posA.advanceTo(x); 2138d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen if (Traits::stopLess(posB.stop(), x)) 2139d715e07efe29451afe2849abd4bd362d0f75a004Jakob Stoklund Olesen posB.advanceTo(x); 2140ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen advance(); 2141ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen } 2142ff2e9b4225ab55ee049b33158a9cce1ef138c2f7Jakob Stoklund Olesen}; 2143cb9e08f328892eaf46825d7426216995ca673a67Jakob Stoklund Olesen 21448dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen} // namespace llvm 21458dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen 21468dc926755f287e33765a8da0c4b3922a289a9d2dJakob Stoklund Olesen#endif 2147