119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===- llvm/ADT/IntervalMap.h - A sorted interval map -----------*- C++ -*-===// 219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The LLVM Compiler Infrastructure 419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file is distributed under the University of Illinois Open Source 619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// License. See LICENSE.TXT for details. 719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This file implements a coalescing interval map for small objects. 1119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// KeyT objects are mapped to ValT objects. Intervals of keys that map to the 1319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// same value are represented in a compressed form. 1419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Iterators provide ordered access to the compressed intervals rather than the 1619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// individual keys, and insert and erase operations use key intervals as well. 1719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 1819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Like SmallVector, IntervalMap will store the first N intervals in the map 1919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// object itself without any allocations. When space is exhausted it switches to 2019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// a B+-tree representation with very small overhead for small key and value 2119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// objects. 2219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 2319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// A Traits class specifies how keys are compared. It also allows IntervalMap to 2419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// work with both closed and half-open intervals. 2519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Keys and values are not stored next to each other in a std::pair, so we don't 2719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// provide such a value_type. Dereferencing iterators only returns the mapped 2819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// value. The interval bounds are accessible through the start() and stop() 2919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// iterator methods. 3019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 3119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// IntervalMap is optimized for small key and value objects, 4 or 8 bytes each 3219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// is the optimal size. For large objects use std::map instead. 3319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 3419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 3519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 3619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Synopsis: 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// template <typename KeyT, typename ValT, unsigned N, typename Traits> 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// class IntervalMap { 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// public: 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// typedef KeyT key_type; 4219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// typedef ValT mapped_type; 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// typedef RecyclingAllocator<...> Allocator; 4419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// class iterator; 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// class const_iterator; 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// explicit IntervalMap(Allocator&); 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// ~IntervalMap(): 4919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 5019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// bool empty() const; 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// KeyT start() const; 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// KeyT stop() const; 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// ValT lookup(KeyT x, Value NotFound = Value()) const; 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 5519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// const_iterator begin() const; 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// const_iterator end() const; 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// iterator begin(); 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// iterator end(); 5919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// const_iterator find(KeyT x) const; 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// iterator find(KeyT x); 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// void insert(KeyT a, KeyT b, ValT y); 6319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// void clear(); 6419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// }; 6519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 6619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// template <typename KeyT, typename ValT, unsigned N, typename Traits> 6719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// class IntervalMap::const_iterator : 6819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// public std::iterator<std::bidirectional_iterator_tag, ValT> { 6919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// public: 7019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// bool operator==(const const_iterator &) const; 7119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// bool operator!=(const const_iterator &) const; 7219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// bool valid() const; 7319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 7419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// const KeyT &start() const; 7519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// const KeyT &stop() const; 7619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// const ValT &value() const; 7719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// const ValT &operator*() const; 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// const ValT *operator->() const; 7919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 8019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// const_iterator &operator++(); 8119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// const_iterator &operator++(int); 8219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// const_iterator &operator--(); 8319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// const_iterator &operator--(int); 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// void goToBegin(); 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// void goToEnd(); 8619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// void find(KeyT x); 8719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// void advanceTo(KeyT x); 8819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// }; 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 9019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// template <typename KeyT, typename ValT, unsigned N, typename Traits> 9119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// class IntervalMap::iterator : public const_iterator { 9219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// public: 9319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// void insert(KeyT a, KeyT b, Value y); 9419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// void erase(); 9519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// }; 9619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 9719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#ifndef LLVM_ADT_INTERVALMAP_H 10019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#define LLVM_ADT_INTERVALMAP_H 10119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/SmallVector.h" 10319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/PointerIntPair.h" 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/Allocator.h" 10519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/RecyclingAllocator.h" 10619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include <iterator> 10719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace llvm { 10919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 11219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//--- Key traits ---// 11319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 11419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 11519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The IntervalMap works with closed or half-open intervals. 11619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Adjacent intervals that map to the same value are coalesced. 11719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 11819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The IntervalMapInfo traits class is used to determine if a key is contained 11919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// in an interval, and if two intervals are adjacent so they can be coalesced. 12019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The provided implementation works for closed integer intervals, other keys 12119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// probably need a specialized version. 12219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 12319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The point x is contained in [a;b] when !startLess(x, a) && !stopLess(b, x). 12419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 12519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// It is assumed that (a;b] half-open intervals are not used, only [a;b) is 12619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// allowed. This is so that stopLess(a, b) can be used to determine if two 12719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// intervals overlap. 12819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 12919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename T> 13219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstruct IntervalMapInfo { 13319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// startLess - Return true if x is not in [a;b]. 13519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This is x < a both for closed intervals and for [a;b) half-open intervals. 13619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static inline bool startLess(const T &x, const T &a) { 13719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return x < a; 13819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 13919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// stopLess - Return true if x is not in [a;b]. 14119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This is b < x for a closed interval, b <= x for [a;b) half-open intervals. 14219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static inline bool stopLess(const T &b, const T &x) { 14319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return b < x; 14419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 14519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// adjacent - Return true when the intervals [x;a] and [b;y] can coalesce. 14719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This is a+1 == b for closed intervals, a == b for half-open intervals. 14819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static inline bool adjacent(const T &a, const T &b) { 14919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return a+1 == b; 15019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 15119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 15319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// IntervalMapImpl - Namespace used for IntervalMap implementation details. 15519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// It should be considered private to the implementation. 15619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace IntervalMapImpl { 15719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Forward declarations. 15919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename, typename, unsigned, typename> class LeafNode; 16019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename, typename, unsigned, typename> class BranchNode; 16119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantypedef std::pair<unsigned,unsigned> IdxPair; 16319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 16619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//--- IntervalMapImpl::NodeBase ---// 16719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 16819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 16919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Both leaf and branch nodes store vectors of pairs. 17019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT). 17119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 17219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Keys and values are stored in separate arrays to avoid padding caused by 17319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// different object alignments. This also helps improve locality of reference 17419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// when searching the keys. 17519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 17619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The nodes don't know how many elements they contain - that information is 17719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// stored elsewhere. Omitting the size field prevents padding and allows a node 17819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// to fill the allocated cache lines completely. 17919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 18019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// These are typical key and value sizes, the node branching factor (N), and 18119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// wasted space when nodes are sized to fit in three cache lines (192 bytes): 18219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 18319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// T1 T2 N Waste Used by 18419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 4 4 24 0 Branch<4> (32-bit pointers) 18519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 8 4 16 0 Leaf<4,4>, Branch<4> 18619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 8 8 12 0 Leaf<4,8>, Branch<8> 18719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 16 4 9 12 Leaf<8,4> 18819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 16 8 8 0 Leaf<8,8> 18919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 19019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 19119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename T1, typename T2, unsigned N> 19319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass NodeBase { 19419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 19519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman enum { Capacity = N }; 19619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman T1 first[N]; 19819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman T2 second[N]; 19919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// copy - Copy elements from another node. 20119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Other Node elements are copied from. 20219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param i Beginning of the source range in other. 20319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param j Beginning of the destination range in this. 20419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Count Number of elements to copy. 20519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman template <unsigned M> 20619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void copy(const NodeBase<T1, T2, M> &Other, unsigned i, 20719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned j, unsigned Count) { 20819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(i + Count <= M && "Invalid source range"); 20919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(j + Count <= N && "Invalid dest range"); 21019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned e = i + Count; i != e; ++i, ++j) { 21119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman first[j] = Other.first[i]; 21219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman second[j] = Other.second[i]; 21319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 21419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 21519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 21619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// moveLeft - Move elements to the left. 21719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param i Beginning of the source range. 21819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param j Beginning of the destination range. 21919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Count Number of elements to copy. 22019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void moveLeft(unsigned i, unsigned j, unsigned Count) { 22119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(j <= i && "Use moveRight shift elements right"); 22219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman copy(*this, i, j, Count); 22319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 22419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 22519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// moveRight - Move elements to the right. 22619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param i Beginning of the source range. 22719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param j Beginning of the destination range. 22819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Count Number of elements to copy. 22919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void moveRight(unsigned i, unsigned j, unsigned Count) { 23019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(i <= j && "Use moveLeft shift elements left"); 23119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(j + Count <= N && "Invalid range"); 23219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (Count--) { 23319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman first[j + Count] = first[i + Count]; 23419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman second[j + Count] = second[i + Count]; 23519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 23619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 23719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 23819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// erase - Erase elements [i;j). 23919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param i Beginning of the range to erase. 24019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param j End of the range. (Exclusive). 24119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Size Number of elements in node. 24219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void erase(unsigned i, unsigned j, unsigned Size) { 24319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman moveLeft(j, i, Size - j); 24419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 24519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 24619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// erase - Erase element at i. 24719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param i Index of element to erase. 24819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Size Number of elements in node. 24919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void erase(unsigned i, unsigned Size) { 25019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman erase(i, i+1, Size); 25119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 25219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 25319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// shift - Shift elements [i;size) 1 position to the right. 25419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param i Beginning of the range to move. 25519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Size Number of elements in node. 25619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void shift(unsigned i, unsigned Size) { 25719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman moveRight(i, i + 1, Size - i); 25819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 25919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// transferToLeftSib - Transfer elements to a left sibling node. 26119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Size Number of elements in this. 26219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Sib Left sibling node. 26319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param SSize Number of elements in sib. 26419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Count Number of elements to transfer. 26519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, 26619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Count) { 26719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Sib.copy(*this, 0, SSize, Count); 26819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman erase(0, Count, Size); 26919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 27019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 27119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// transferToRightSib - Transfer elements to a right sibling node. 27219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Size Number of elements in this. 27319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Sib Right sibling node. 27419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param SSize Number of elements in sib. 27519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Count Number of elements to transfer. 27619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize, 27719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Count) { 27819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Sib.moveRight(0, Count, SSize); 27919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Sib.copy(*this, Size-Count, 0, Count); 28019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 28119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 28219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// adjustFromLeftSib - Adjust the number if elements in this node by moving 28319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// elements to or from a left sibling node. 28419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Size Number of elements in this. 28519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Sib Right sibling node. 28619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param SSize Number of elements in sib. 28719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Add The number of elements to add to this node, possibly < 0. 28819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @return Number of elements added to this node, possibly negative. 28919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add) { 29019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Add > 0) { 29119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We want to grow, copy from sib. 29219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size); 29319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Sib.transferToRightSib(SSize, *this, Size, Count); 29419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Count; 29519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 29619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We want to shrink, copy to sib. 29719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize); 29819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman transferToLeftSib(Size, Sib, SSize, Count); 29919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return -Count; 30019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 30119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 30219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 30319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 30419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes. 30519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Node Array of pointers to sibling nodes. 30619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Nodes Number of nodes. 30719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param CurSize Array of current node sizes, will be overwritten. 30819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param NewSize Array of desired node sizes. 30919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename NodeT> 31019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid adjustSiblingSizes(NodeT *Node[], unsigned Nodes, 31119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned CurSize[], const unsigned NewSize[]) { 31219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Move elements right. 31319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (int n = Nodes - 1; n; --n) { 31419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CurSize[n] == NewSize[n]) 31519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 31619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (int m = n - 1; m != -1; --m) { 31719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m], 31819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewSize[n] - CurSize[n]); 31919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurSize[m] -= d; 32019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurSize[n] += d; 32119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Keep going if the current node was exhausted. 32219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CurSize[n] >= NewSize[n]) 32319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 32419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 32519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 32619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 32719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Nodes == 0) 32819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 32919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 33019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Move elements left. 33119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned n = 0; n != Nodes - 1; ++n) { 33219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CurSize[n] == NewSize[n]) 33319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 33419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned m = n + 1; m != Nodes; ++m) { 33519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n], 33619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurSize[n] - NewSize[n]); 33719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurSize[m] += d; 33819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurSize[n] -= d; 33919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Keep going if the current node was exhausted. 34019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CurSize[n] >= NewSize[n]) 34119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 34219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 34319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 34419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 34519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#ifndef NDEBUG 34619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned n = 0; n != Nodes; n++) 34719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle"); 34819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#endif 34919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 35019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 35119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// IntervalMapImpl::distribute - Compute a new distribution of node elements 35219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// after an overflow or underflow. Reserve space for a new element at Position, 35319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// and compute the node that will hold Position after redistributing node 35419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// elements. 35519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 35619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// It is required that 35719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 35819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Elements == sum(CurSize), and 35919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Elements + Grow <= Nodes * Capacity. 36019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 36119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// NewSize[] will be filled in such that: 36219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 36319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// sum(NewSize) == Elements, and 36419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// NewSize[i] <= Capacity. 36519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 36619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// The returned index is the node where Position will go, so: 36719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 36819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// sum(NewSize[0..idx-1]) <= Position 36919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// sum(NewSize[0..idx]) >= Position 37019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 37119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// The last equality, sum(NewSize[0..idx]) == Position, can only happen when 37219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Grow is set and NewSize[idx] == Capacity-1. The index points to the node 37319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// before the one holding the Position'th element where there is room for an 37419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// insertion. 37519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 37619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Nodes The number of nodes. 37719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Elements Total elements in all nodes. 37819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Capacity The capacity of each node. 37919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param CurSize Array[Nodes] of current node sizes, or NULL. 38019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param NewSize Array[Nodes] to receive the new node sizes. 38119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Position Insert position. 38219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Grow Reserve space for a new element at Position. 38319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @return (node, offset) for Position. 38419bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanIdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, 38519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const unsigned *CurSize, unsigned NewSize[], 38619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Position, bool Grow); 38719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 38819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 38919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 39019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//--- IntervalMapImpl::NodeSizer ---// 39119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 39219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 39319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Compute node sizes from key and value types. 39419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 39519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The branching factors are chosen to make nodes fit in three cache lines. 39619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This may not be possible if keys or values are very large. Such large objects 39719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// are handled correctly, but a std::map would probably give better performance. 39819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 39919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 40019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 40119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanenum { 40219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Cache line size. Most architectures have 32 or 64 byte cache lines. 40319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We use 64 bytes here because it provides good branching factors. 40419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Log2CacheLine = 6, 40519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CacheLineBytes = 1 << Log2CacheLine, 40619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DesiredNodeBytes = 3 * CacheLineBytes 40719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 40819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 40919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT> 41019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstruct NodeSizer { 41119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman enum { 41219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Compute the leaf node branching factor that makes a node fit in three 41319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // cache lines. The branching factor must be at least 3, or some B+-tree 41419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // balancing algorithms won't work. 41519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // LeafSize can't be larger than CacheLineBytes. This is required by the 41619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // PointerIntPair used by NodeRef. 41719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DesiredLeafSize = DesiredNodeBytes / 41819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)), 41919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MinLeafSize = 3, 42019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize 42119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 42219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 42319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize> LeafBase; 42419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 42519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman enum { 42619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Now that we have the leaf branching factor, compute the actual allocation 42719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // unit size by rounding up to a whole number of cache lines. 42819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AllocBytes = (sizeof(LeafBase) + CacheLineBytes-1) & ~(CacheLineBytes-1), 42919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 43019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Determine the branching factor for branch nodes. 43119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BranchSize = AllocBytes / 43219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static_cast<unsigned>(sizeof(KeyT) + sizeof(void*)) 43319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 43419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 43519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Allocator - The recycling allocator used for both branch and leaf nodes. 43619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This typedef is very likely to be identical for all IntervalMaps with 43719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// reasonably sized entries, so the same allocator can be shared among 43819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// different kinds of maps. 43919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef RecyclingAllocator<BumpPtrAllocator, char, 44019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AllocBytes, CacheLineBytes> Allocator; 44119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 44219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 44319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 44419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 44519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 44619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//--- IntervalMapImpl::NodeRef ---// 44719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 44819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 44919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// B+-tree nodes can be leaves or branches, so we need a polymorphic node 45019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// pointer that can point to both kinds. 45119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 45219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// All nodes are cache line aligned and the low 6 bits of a node pointer are 45319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// always 0. These bits are used to store the number of elements in the 45419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// referenced node. Besides saving space, placing node sizes in the parents 45519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// allow tree balancing algorithms to run without faulting cache lines for nodes 45619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// that may not need to be modified. 45719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 45819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// A NodeRef doesn't know whether it references a leaf node or a branch node. 45919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// It is the responsibility of the caller to use the correct types. 46019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 46119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Nodes are never supposed to be empty, and it is invalid to store a node size 46219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// of 0 in a NodeRef. The valid range of sizes is 1-64. 46319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 46419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 46519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 46619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass NodeRef { 46719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman struct CacheAlignedPointerTraits { 46819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static inline void *getAsVoidPointer(void *P) { return P; } 46919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static inline void *getFromVoidPointer(void *P) { return P; } 47019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman enum { NumLowBitsAvailable = Log2CacheLine }; 47119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 47219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PointerIntPair<void*, Log2CacheLine, unsigned, CacheAlignedPointerTraits> pip; 47319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 47419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 47519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// NodeRef - Create a null ref. 47619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeRef() {} 47719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 47819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// operator bool - Detect a null ref. 47919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman operator bool() const { return pip.getOpaqueValue(); } 48019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 48119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// NodeRef - Create a reference to the node p with n elements. 48219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman template <typename NodeT> 48319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) { 48419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(n <= NodeT::Capacity && "Size too big for node"); 48519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 48619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 48719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// size - Return the number of elements in the referenced node. 48819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned size() const { return pip.getInt() + 1; } 48919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 49019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// setSize - Update the node size. 49119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void setSize(unsigned n) { pip.setInt(n - 1); } 49219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 49319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// subtree - Access the i'th subtree reference in a branch node. 49419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This depends on branch nodes storing the NodeRef array as their first 49519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// member. 49619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeRef &subtree(unsigned i) const { 49719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return reinterpret_cast<NodeRef*>(pip.getPointer())[i]; 49819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 49919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 50019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// get - Dereference as a NodeT reference. 50119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman template <typename NodeT> 50219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeT &get() const { 50319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return *reinterpret_cast<NodeT*>(pip.getPointer()); 50419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 50519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 50619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool operator==(const NodeRef &RHS) const { 50719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (pip == RHS.pip) 50819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 50919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs"); 51019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 51119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 51219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 51319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool operator!=(const NodeRef &RHS) const { 51419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return !operator==(RHS); 51519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 51619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 51719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 51819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 51919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//--- IntervalMapImpl::LeafNode ---// 52019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 52119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 52219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Leaf nodes store up to N disjoint intervals with corresponding values. 52319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 52419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The intervals are kept sorted and fully coalesced so there are no adjacent 52519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// intervals mapping to the same value. 52619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 52719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// These constraints are always satisfied: 52819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 52919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// - Traits::stopLess(start(i), stop(i)) - Non-empty, sane intervals. 53019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 53119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// - Traits::stopLess(stop(i), start(i + 1) - Sorted. 53219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 53319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// - value(i) != value(i + 1) || !Traits::adjacent(stop(i), start(i + 1)) 53419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// - Fully coalesced. 53519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 53619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 53719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 53819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 53919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> { 54019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 54119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const KeyT &start(unsigned i) const { return this->first[i].first; } 54219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const KeyT &stop(unsigned i) const { return this->first[i].second; } 54319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const ValT &value(unsigned i) const { return this->second[i]; } 54419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 54519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyT &start(unsigned i) { return this->first[i].first; } 54619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyT &stop(unsigned i) { return this->first[i].second; } 54719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ValT &value(unsigned i) { return this->second[i]; } 54819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 54919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// findFrom - Find the first interval after i that may contain x. 55019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param i Starting index for the search. 55119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Size Number of elements in node. 55219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param x Key to search for. 55319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @return First index with !stopLess(key[i].stop, x), or size. 55419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This is the first interval that can possibly contain x. 55519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { 55619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(i <= Size && Size <= N && "Bad indices"); 55719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 55819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Index is past the needed point"); 55919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (i != Size && Traits::stopLess(stop(i), x)) ++i; 56019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return i; 56119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 56219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 56319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// safeFind - Find an interval that is known to exist. This is the same as 56419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// findFrom except is it assumed that x is at least within range of the last 56519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// interval. 56619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param i Starting index for the search. 56719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param x Key to search for. 56819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @return First index with !stopLess(key[i].stop, x), never size. 56919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This is the first interval that can possibly contain x. 57019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned safeFind(unsigned i, KeyT x) const { 57119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(i < N && "Bad index"); 57219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 57319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Index is past the needed point"); 57419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (Traits::stopLess(stop(i), x)) ++i; 57519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(i < N && "Unsafe intervals"); 57619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return i; 57719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 57819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 57919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// safeLookup - Lookup mapped value for a safe key. 58019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// It is assumed that x is within range of the last entry. 58119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param x Key to search for. 58219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param NotFound Value to return if x is not in any interval. 58319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @return The mapped value at x or NotFound. 58419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ValT safeLookup(KeyT x, ValT NotFound) const { 58519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned i = safeFind(0, x); 58619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Traits::startLess(x, start(i)) ? NotFound : value(i); 58719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 58819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 58919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y); 59019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 59119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 59219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as 59319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// possible. This may cause the node to grow by 1, or it may cause the node 59419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// to shrink because of coalescing. 59519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param i Starting index = insertFrom(0, size, a) 59619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Size Number of elements in node. 59719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param a Interval start. 59819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param b Interval stop. 59919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param y Value be mapped. 60019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @return (insert position, new size), or (i, Capacity+1) on overflow. 60119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 60219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanunsigned LeafNode<KeyT, ValT, N, Traits>:: 60319bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumaninsertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) { 60419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned i = Pos; 60519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(i <= Size && Size <= N && "Invalid index"); 60619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!Traits::stopLess(b, a) && "Invalid interval"); 60719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 60819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Verify the findFrom invariant. 60919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert((i == 0 || Traits::stopLess(stop(i - 1), a))); 61019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert((i == Size || !Traits::stopLess(stop(i), a))); 61119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert"); 61219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 61319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Coalesce with previous interval. 61419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) { 61519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Pos = i - 1; 61619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Also coalesce with next interval? 61719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) { 61819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman stop(i - 1) = stop(i); 61919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman this->erase(i, Size); 62019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Size - 1; 62119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 62219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman stop(i - 1) = b; 62319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Size; 62419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 62519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 62619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Detect overflow. 62719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (i == N) 62819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return N + 1; 62919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 63019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Add new interval at end. 63119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (i == Size) { 63219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman start(i) = a; 63319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman stop(i) = b; 63419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman value(i) = y; 63519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Size + 1; 63619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 63719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 63819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Try to coalesce with following interval. 63919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (value(i) == y && Traits::adjacent(b, start(i))) { 64019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman start(i) = a; 64119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Size; 64219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 64319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 64419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We must insert before i. Detect overflow. 64519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Size == N) 64619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return N + 1; 64719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 64819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Insert before i. 64919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman this->shift(i, Size); 65019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman start(i) = a; 65119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman stop(i) = b; 65219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman value(i) = y; 65319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Size + 1; 65419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 65519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 65619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 65719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 65819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//--- IntervalMapImpl::BranchNode ---// 65919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 66019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 66119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// A branch node stores references to 1--N subtrees all of the same height. 66219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 66319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The key array in a branch node holds the rightmost stop key of each subtree. 66419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// It is redundant to store the last stop key since it can be found in the 66519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// parent node, but doing so makes tree balancing a lot simpler. 66619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 66719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// It is unusual for a branch node to only have one subtree, but it can happen 66819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// in the root node if it is smaller than the normal nodes. 66919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 67019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// When all of the leaf nodes from all the subtrees are concatenated, they must 67119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// satisfy the same constraints as a single leaf node. They must be sorted, 67219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// sane, and fully coalesced. 67319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 67419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 67519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 67619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 67719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass BranchNode : public NodeBase<NodeRef, KeyT, N> { 67819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 67919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const KeyT &stop(unsigned i) const { return this->second[i]; } 68019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const NodeRef &subtree(unsigned i) const { return this->first[i]; } 68119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 68219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyT &stop(unsigned i) { return this->second[i]; } 68319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeRef &subtree(unsigned i) { return this->first[i]; } 68419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 68519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// findFrom - Find the first subtree after i that may contain x. 68619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param i Starting index for the search. 68719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Size Number of elements in node. 68819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param x Key to search for. 68919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @return First index with !stopLess(key[i], x), or size. 69019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This is the first subtree that can possibly contain x. 69119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned findFrom(unsigned i, unsigned Size, KeyT x) const { 69219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(i <= Size && Size <= N && "Bad indices"); 69319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 69419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Index to findFrom is past the needed point"); 69519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (i != Size && Traits::stopLess(stop(i), x)) ++i; 69619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return i; 69719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 69819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 69919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// safeFind - Find a subtree that is known to exist. This is the same as 70019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// findFrom except is it assumed that x is in range. 70119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param i Starting index for the search. 70219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param x Key to search for. 70319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @return First index with !stopLess(key[i], x), never size. 70419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This is the first subtree that can possibly contain x. 70519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned safeFind(unsigned i, KeyT x) const { 70619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(i < N && "Bad index"); 70719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert((i == 0 || Traits::stopLess(stop(i - 1), x)) && 70819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Index is past the needed point"); 70919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (Traits::stopLess(stop(i), x)) ++i; 71019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(i < N && "Unsafe intervals"); 71119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return i; 71219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 71319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 71419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// safeLookup - Get the subtree containing x, Assuming that x is in range. 71519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param x Key to search for. 71619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @return Subtree containing x 71719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeRef safeLookup(KeyT x) const { 71819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return subtree(safeFind(0, x)); 71919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 72019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 72119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// insert - Insert a new (subtree, stop) pair. 72219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param i Insert position, following entries will be shifted. 72319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Size Number of elements in node. 72419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Node Subtree to insert. 72519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Stop Last key in subtree. 72619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) { 72719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(Size < N && "branch node overflow"); 72819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(i <= Size && "Bad insert position"); 72919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman this->shift(i, Size); 73019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman subtree(i) = Node; 73119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman stop(i) = Stop; 73219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 73319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 73419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 73519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 73619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//--- IntervalMapImpl::Path ---// 73719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 73819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 73919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// A Path is used by iterators to represent a position in a B+-tree, and the 74019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// path to get there from the root. 74119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 74219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// The Path class also constains the tree navigation code that doesn't have to 74319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// be templatized. 74419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// 74519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 74619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 74719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass Path { 74819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Entry - Each step in the path is a node pointer and an offset into that 74919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// node. 75019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman struct Entry { 75119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void *node; 75219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned size; 75319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned offset; 75419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 75519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Entry(void *Node, unsigned Size, unsigned Offset) 75619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman : node(Node), size(Size), offset(Offset) {} 75719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 75819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Entry(NodeRef Node, unsigned Offset) 75919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman : node(&Node.subtree(0)), size(Node.size()), offset(Offset) {} 76019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 76119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeRef &subtree(unsigned i) const { 76219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return reinterpret_cast<NodeRef*>(node)[i]; 76319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 76419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 76519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 76619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// path - The path entries, path[0] is the root node, path.back() is a leaf. 76719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<Entry, 4> path; 76819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 76919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 77019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Node accessors. 77119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman template <typename NodeT> NodeT &node(unsigned Level) const { 77219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return *reinterpret_cast<NodeT*>(path[Level].node); 77319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 77419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned size(unsigned Level) const { return path[Level].size; } 77519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned offset(unsigned Level) const { return path[Level].offset; } 77619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned &offset(unsigned Level) { return path[Level].offset; } 77719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 77819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Leaf accessors. 77919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman template <typename NodeT> NodeT &leaf() const { 78019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return *reinterpret_cast<NodeT*>(path.back().node); 78119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 78219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned leafSize() const { return path.back().size; } 78319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned leafOffset() const { return path.back().offset; } 78419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned &leafOffset() { return path.back().offset; } 78519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 78619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// valid - Return true if path is at a valid node, not at end(). 78719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool valid() const { 78819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return !path.empty() && path.front().offset < path.front().size; 78919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 79019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 79119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// height - Return the height of the tree corresponding to this path. 79219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This matches map->height in a full path. 79319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned height() const { return path.size() - 1; } 79419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 79519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// subtree - Get the subtree referenced from Level. When the path is 79619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// consistent, node(Level + 1) == subtree(Level). 79719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Level 0..height-1. The leaves have no subtrees. 79819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeRef &subtree(unsigned Level) const { 79919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return path[Level].subtree(path[Level].offset); 80019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 80119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 80219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// reset - Reset cached information about node(Level) from subtree(Level -1). 80319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Level 1..height. THe node to update after parent node changed. 80419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void reset(unsigned Level) { 80519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path[Level] = Entry(subtree(Level - 1), offset(Level)); 80619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 80719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 80819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// push - Add entry to path. 80919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Node Node to add, should be subtree(path.size()-1). 81019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Offset Offset into Node. 81119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void push(NodeRef Node, unsigned Offset) { 81219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.push_back(Entry(Node, Offset)); 81319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 81419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 81519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// pop - Remove the last path entry. 81619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void pop() { 81719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.pop_back(); 81819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 81919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 82019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// setSize - Set the size of a node both in the path and in the tree. 82119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Level 0..height. Note that setting the root size won't change 82219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// map->rootSize. 82319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Size New node size. 82419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void setSize(unsigned Level, unsigned Size) { 82519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path[Level].size = Size; 82619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Level) 82719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman subtree(Level - 1).setSize(Size); 82819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 82919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 83019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// setRoot - Clear the path and set a new root node. 83119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Node New root node. 83219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Size New root size. 83319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Offset Offset into root node. 83419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void setRoot(void *Node, unsigned Size, unsigned Offset) { 83519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.clear(); 83619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.push_back(Entry(Node, Size, Offset)); 83719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 83819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 83919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// replaceRoot - Replace the current root node with two new entries after the 84019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// tree height has increased. 84119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Root The new root node. 84219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Size Number of entries in the new root. 84319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Offsets Offsets into the root and first branch nodes. 84419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void replaceRoot(void *Root, unsigned Size, IdxPair Offsets); 84519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 84619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 84719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Level Get the sibling to node(Level). 84819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @return Left sibling, or NodeRef(). 84919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeRef getLeftSibling(unsigned Level) const; 85019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 85119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// moveLeft - Move path to the left sibling at Level. Leave nodes below Level 85219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// unaltered. 85319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Level Move node(Level). 85419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void moveLeft(unsigned Level); 85519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 85619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// fillLeft - Grow path to Height by taking leftmost branches. 85719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Height The target height. 85819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void fillLeft(unsigned Height) { 85919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (height() < Height) 86019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman push(subtree(height()), 0); 86119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 86219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 86319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getLeftSibling - Get the left sibling node at Level, or a null NodeRef. 86419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Level Get the sinbling to node(Level). 86519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @return Left sibling, or NodeRef(). 86619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeRef getRightSibling(unsigned Level) const; 86719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 86819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// moveRight - Move path to the left sibling at Level. Leave nodes below 86919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Level unaltered. 87019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Level Move node(Level). 87119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void moveRight(unsigned Level); 87219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 87319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// atBegin - Return true if path is at begin(). 87419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool atBegin() const { 87519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = path.size(); i != e; ++i) 87619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (path[i].offset != 0) 87719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 87819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 87919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 88019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 88119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// atLastEntry - Return true if the path is at the last entry of the node at 88219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Level. 88319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Level Node to examine. 88419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool atLastEntry(unsigned Level) const { 88519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return path[Level].offset == path[Level].size - 1; 88619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 88719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 88819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// legalizeForInsert - Prepare the path for an insertion at Level. When the 88919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// path is at end(), node(Level) may not be a legal node. legalizeForInsert 89019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// ensures that node(Level) is real by moving back to the last node at Level, 89119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// and setting offset(Level) to size(Level) if required. 89219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param Level The level where an insertion is about to take place. 89319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void legalizeForInsert(unsigned Level) { 89419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (valid()) 89519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 89619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman moveLeft(Level); 89719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++path[Level].offset; 89819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 89919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 90019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 90119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} // namespace IntervalMapImpl 90219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 90319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 90419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 90519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//--- IntervalMap ----// 90619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 90719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 90819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, 90919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize, 91019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typename Traits = IntervalMapInfo<KeyT> > 91119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass IntervalMap { 91219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef IntervalMapImpl::NodeSizer<KeyT, ValT> Sizer; 91319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits> Leaf; 91419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits> 91519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Branch; 91619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf; 91719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef IntervalMapImpl::IdxPair IdxPair; 91819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 91919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The RootLeaf capacity is given as a template parameter. We must compute the 92019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // corresponding RootBranch capacity. 92119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman enum { 92219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) / 92319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)), 92419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1 92519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 92619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 92719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits> 92819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RootBranch; 92919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 93019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // When branched, we store a global start key as well as the branch node. 93119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman struct RootBranchData { 93219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyT start; 93319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RootBranch node; 93419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 93519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 93619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman enum { 93719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RootDataSize = sizeof(RootBranchData) > sizeof(RootLeaf) ? 93819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman sizeof(RootBranchData) : sizeof(RootLeaf) 93919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 94019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 94119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 94219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef typename Sizer::Allocator Allocator; 94319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef KeyT KeyType; 94419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef ValT ValueType; 94519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef Traits KeyTraits; 94619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 94719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanprivate: 94819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The root data is either a RootLeaf or a RootBranchData instance. 94919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We can't put them in a union since C++03 doesn't allow non-trivial 95019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // constructors in unions. 95119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Instead, we use a char array with pointer alignment. The alignment is 95219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // ensured by the allocator member in the class, but still verified in the 95319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // constructor. We don't support keys or values that are more aligned than a 95419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // pointer. 95519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman char data[RootDataSize]; 95619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 95719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Tree height. 95819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 0: Leaves in root. 95919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 1: Root points to leaf. 96019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 2: root->branch->leaf ... 96119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned height; 96219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 96319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Number of entries in the root node. 96419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned rootSize; 96519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 96619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Allocator used for creating external nodes. 96719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Allocator &allocator; 96819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 96919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// dataAs - Represent data as a node type without breaking aliasing rules. 97019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman template <typename T> 97119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman T &dataAs() const { 97219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman union { 97319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const char *d; 97419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman T *t; 97519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } u; 97619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman u.d = data; 97719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return *u.t; 97819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 97919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 98019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const RootLeaf &rootLeaf() const { 98119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!branched() && "Cannot acces leaf data in branched root"); 98219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return dataAs<RootLeaf>(); 98319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 98419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RootLeaf &rootLeaf() { 98519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!branched() && "Cannot acces leaf data in branched root"); 98619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return dataAs<RootLeaf>(); 98719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 98819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RootBranchData &rootBranchData() const { 98919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(branched() && "Cannot access branch data in non-branched root"); 99019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return dataAs<RootBranchData>(); 99119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 99219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RootBranchData &rootBranchData() { 99319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(branched() && "Cannot access branch data in non-branched root"); 99419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return dataAs<RootBranchData>(); 99519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 99619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const RootBranch &rootBranch() const { return rootBranchData().node; } 99719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RootBranch &rootBranch() { return rootBranchData().node; } 99819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyT rootBranchStart() const { return rootBranchData().start; } 99919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyT &rootBranchStart() { return rootBranchData().start; } 100019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 100119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman template <typename NodeT> NodeT *newNode() { 100219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return new(allocator.template Allocate<NodeT>()) NodeT(); 100319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 100419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 100519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman template <typename NodeT> void deleteNode(NodeT *P) { 100619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P->~NodeT(); 100719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman allocator.Deallocate(P); 100819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 100919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 101019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IdxPair branchRoot(unsigned Position); 101119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IdxPair splitRoot(unsigned Position); 101219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 101319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void switchRootToBranch() { 101419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rootLeaf().~RootLeaf(); 101519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman height = 1; 101619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman new (&rootBranchData()) RootBranchData(); 101719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 101819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 101919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void switchRootToLeaf() { 102019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rootBranchData().~RootBranchData(); 102119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman height = 0; 102219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman new(&rootLeaf()) RootLeaf(); 102319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 102419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 102519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool branched() const { return height > 0; } 102619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 102719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ValT treeSafeLookup(KeyT x, ValT NotFound) const; 102819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, 102919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Level)); 103019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level); 103119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 103219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 103319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) { 103419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert((uintptr_t(data) & (alignOf<RootLeaf>() - 1)) == 0 && 103519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Insufficient alignment"); 103619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman new(&rootLeaf()) RootLeaf(); 103719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 103819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 103919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ~IntervalMap() { 104019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman clear(); 104119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rootLeaf().~RootLeaf(); 104219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 104319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 104419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// empty - Return true when no intervals are mapped. 104519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool empty() const { 104619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return rootSize == 0; 104719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 104819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 104919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// start - Return the smallest mapped key in a non-empty map. 105019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyT start() const { 105119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!empty() && "Empty IntervalMap has no start"); 105219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return !branched() ? rootLeaf().start(0) : rootBranchStart(); 105319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 105419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 105519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// stop - Return the largest mapped key in a non-empty map. 105619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyT stop() const { 105719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!empty() && "Empty IntervalMap has no stop"); 105819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return !branched() ? rootLeaf().stop(rootSize - 1) : 105919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rootBranch().stop(rootSize - 1); 106019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 106119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 106219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// lookup - Return the mapped value at x or NotFound. 106319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ValT lookup(KeyT x, ValT NotFound = ValT()) const { 106419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x)) 106519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return NotFound; 106619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return branched() ? treeSafeLookup(x, NotFound) : 106719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rootLeaf().safeLookup(x, NotFound); 106819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 106919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 107019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals. 107119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// It is assumed that no key in the interval is mapped to another value, but 107219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// overlapping intervals already mapped to y will be coalesced. 107319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void insert(KeyT a, KeyT b, ValT y) { 107419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (branched() || rootSize == RootLeaf::Capacity) 107519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return find(a).insert(a, b, y); 107619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 107719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Easy insert into root leaf. 107819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned p = rootLeaf().findFrom(0, rootSize, a); 107919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y); 108019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 108119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 108219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// clear - Remove all entries. 108319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void clear(); 108419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 108519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman class const_iterator; 108619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman class iterator; 108719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman friend class const_iterator; 108819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman friend class iterator; 108919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 109019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const_iterator begin() const { 109119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const_iterator I(*this); 109219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I.goToBegin(); 109319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return I; 109419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 109519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 109619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator begin() { 109719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator I(*this); 109819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I.goToBegin(); 109919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return I; 110019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 110119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 110219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const_iterator end() const { 110319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const_iterator I(*this); 110419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I.goToEnd(); 110519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return I; 110619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 110719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 110819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator end() { 110919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator I(*this); 111019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I.goToEnd(); 111119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return I; 111219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 111319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 111419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// find - Return an iterator pointing to the first interval ending at or 111519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// after x, or end(). 111619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const_iterator find(KeyT x) const { 111719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const_iterator I(*this); 111819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I.find(x); 111919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return I; 112019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 112119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 112219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator find(KeyT x) { 112319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator I(*this); 112419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I.find(x); 112519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return I; 112619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 112719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 112819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 112919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// treeSafeLookup - Return the mapped value at x or NotFound, assuming a 113019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// branched root. 113119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 113219bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanValT IntervalMap<KeyT, ValT, N, Traits>:: 113319bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumantreeSafeLookup(KeyT x, ValT NotFound) const { 113419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(branched() && "treeLookup assumes a branched root"); 113519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 113619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x); 113719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned h = height-1; h; --h) 113819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NR = NR.get<Branch>().safeLookup(x); 113919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return NR.get<Leaf>().safeLookup(x, NotFound); 114019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 114119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 114219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 114319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// branchRoot - Switch from a leaf root to a branched root. 114419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Return the new (root offset, node offset) corresponding to Position. 114519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 114619bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanIntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 114719bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanbranchRoot(unsigned Position) { 114819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman using namespace IntervalMapImpl; 114919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // How many external leaf nodes to hold RootLeaf+1? 115019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1; 115119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 115219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Compute element distribution among new nodes. 115319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned size[Nodes]; 115419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IdxPair NewOffset(0, Position); 115519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 115619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Is is very common for the root node to be smaller than external nodes. 115719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Nodes == 1) 115819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman size[0] = rootSize; 115919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 116019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, size, 116119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Position, true); 116219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 116319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Allocate new nodes. 116419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned pos = 0; 116519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeRef node[Nodes]; 116619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned n = 0; n != Nodes; ++n) { 116719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Leaf *L = newNode<Leaf>(); 116819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman L->copy(rootLeaf(), pos, 0, size[n]); 116919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman node[n] = NodeRef(L, size[n]); 117019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman pos += size[n]; 117119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 117219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 117319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Destroy the old leaf node, construct branch node instead. 117419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman switchRootToBranch(); 117519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned n = 0; n != Nodes; ++n) { 117619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1); 117719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rootBranch().subtree(n) = node[n]; 117819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 117919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rootBranchStart() = node[0].template get<Leaf>().start(0); 118019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rootSize = Nodes; 118119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return NewOffset; 118219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 118319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 118419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// splitRoot - Split the current BranchRoot into multiple Branch nodes. 118519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Return the new (root offset, node offset) corresponding to Position. 118619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 118719bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanIntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>:: 118819bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumansplitRoot(unsigned Position) { 118919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman using namespace IntervalMapImpl; 119019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // How many external leaf nodes to hold RootBranch+1? 119119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1; 119219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 119319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Compute element distribution among new nodes. 119419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Size[Nodes]; 119519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IdxPair NewOffset(0, Position); 119619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 119719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Is is very common for the root node to be smaller than external nodes. 119819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Nodes == 1) 119919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Size[0] = rootSize; 120019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 120119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, Size, 120219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Position, true); 120319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 120419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Allocate new nodes. 120519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Pos = 0; 120619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeRef Node[Nodes]; 120719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned n = 0; n != Nodes; ++n) { 120819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Branch *B = newNode<Branch>(); 120919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman B->copy(rootBranch(), Pos, 0, Size[n]); 121019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Node[n] = NodeRef(B, Size[n]); 121119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Pos += Size[n]; 121219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 121319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 121419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned n = 0; n != Nodes; ++n) { 121519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1); 121619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rootBranch().subtree(n) = Node[n]; 121719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 121819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rootSize = Nodes; 121919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++height; 122019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return NewOffset; 122119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 122219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 122319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// visitNodes - Visit each external node. 122419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 122519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid IntervalMap<KeyT, ValT, N, Traits>:: 122619bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanvisitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) { 122719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!branched()) 122819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 122919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs; 123019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 123119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Collect level 0 nodes from the root. 123219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0; i != rootSize; ++i) 123319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Refs.push_back(rootBranch().subtree(i)); 123419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 123519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Visit all branch nodes. 123619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned h = height - 1; h; --h) { 123719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = Refs.size(); i != e; ++i) { 123819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned j = 0, s = Refs[i].size(); j != s; ++j) 123919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NextRefs.push_back(Refs[i].subtree(j)); 124019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (this->*f)(Refs[i], h); 124119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 124219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Refs.clear(); 124319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Refs.swap(NextRefs); 124419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 124519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 124619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Visit all leaf nodes. 124719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = Refs.size(); i != e; ++i) 124819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (this->*f)(Refs[i], 0); 124919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 125019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 125119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 125219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid IntervalMap<KeyT, ValT, N, Traits>:: 125319bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumandeleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) { 125419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Level) 125519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman deleteNode(&Node.get<Branch>()); 125619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 125719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman deleteNode(&Node.get<Leaf>()); 125819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 125919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 126019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 126119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid IntervalMap<KeyT, ValT, N, Traits>:: 126219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclear() { 126319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (branched()) { 126419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman visitNodes(&IntervalMap::deleteNode); 126519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman switchRootToLeaf(); 126619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 126719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman rootSize = 0; 126819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 126919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 127019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 127119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//--- IntervalMap::const_iterator ----// 127219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 127319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 127419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 127519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass IntervalMap<KeyT, ValT, N, Traits>::const_iterator : 127619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman public std::iterator<std::bidirectional_iterator_tag, ValT> { 127719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanprotected: 127819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman friend class IntervalMap; 127919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 128019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The map referred to. 128119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMap *map; 128219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 128319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We store a full path from the root to the current position. 128419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The path may be partially filled, but never between iterator calls. 128519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMapImpl::Path path; 128619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 128719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman explicit const_iterator(const IntervalMap &map) : 128819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman map(const_cast<IntervalMap*>(&map)) {} 128919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 129019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool branched() const { 129119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(map && "Invalid iterator"); 129219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return map->branched(); 129319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 129419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 129519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void setRoot(unsigned Offset) { 129619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (branched()) 129719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.setRoot(&map->rootBranch(), map->rootSize, Offset); 129819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 129919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.setRoot(&map->rootLeaf(), map->rootSize, Offset); 130019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 130119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 130219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void pathFillFind(KeyT x); 130319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void treeFind(KeyT x); 130419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void treeAdvanceTo(KeyT x); 130519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 130619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// unsafeStart - Writable access to start() for iterator. 130719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyT &unsafeStart() const { 130819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(valid() && "Cannot access invalid iterator"); 130919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return branched() ? path.leaf<Leaf>().start(path.leafOffset()) : 131019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.leaf<RootLeaf>().start(path.leafOffset()); 131119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 131219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 131319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// unsafeStop - Writable access to stop() for iterator. 131419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyT &unsafeStop() const { 131519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(valid() && "Cannot access invalid iterator"); 131619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return branched() ? path.leaf<Leaf>().stop(path.leafOffset()) : 131719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.leaf<RootLeaf>().stop(path.leafOffset()); 131819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 131919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 132019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// unsafeValue - Writable access to value() for iterator. 132119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ValT &unsafeValue() const { 132219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(valid() && "Cannot access invalid iterator"); 132319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return branched() ? path.leaf<Leaf>().value(path.leafOffset()) : 132419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.leaf<RootLeaf>().value(path.leafOffset()); 132519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 132619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 132719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 132819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// const_iterator - Create an iterator that isn't pointing anywhere. 132919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const_iterator() : map(0) {} 133019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 133119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// setMap - Change the map iterated over. This call must be followed by a 133219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// call to goToBegin(), goToEnd(), or find() 133319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void setMap(const IntervalMap &m) { map = const_cast<IntervalMap*>(&m); } 133419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 133519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// valid - Return true if the current position is valid, false for end(). 133619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool valid() const { return path.valid(); } 133719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 133819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// atBegin - Return true if the current position is the first map entry. 133919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool atBegin() const { return path.atBegin(); } 134019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 134119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// start - Return the beginning of the current interval. 134219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const KeyT &start() const { return unsafeStart(); } 134319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 134419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// stop - Return the end of the current interval. 134519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const KeyT &stop() const { return unsafeStop(); } 134619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 134719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// value - Return the mapped value at the current interval. 134819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const ValT &value() const { return unsafeValue(); } 134919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 135019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const ValT &operator*() const { return value(); } 135119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 135219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool operator==(const const_iterator &RHS) const { 135319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(map == RHS.map && "Cannot compare iterators from different maps"); 135419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!valid()) 135519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return !RHS.valid(); 135619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (path.leafOffset() != RHS.path.leafOffset()) 135719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 135819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return &path.template leaf<Leaf>() == &RHS.path.template leaf<Leaf>(); 135919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 136019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 136119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool operator!=(const const_iterator &RHS) const { 136219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return !operator==(RHS); 136319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 136419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 136519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// goToBegin - Move to the first interval in map. 136619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void goToBegin() { 136719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setRoot(0); 136819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (branched()) 136919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.fillLeft(map->height); 137019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 137119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 137219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// goToEnd - Move beyond the last interval in map. 137319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void goToEnd() { 137419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setRoot(map->rootSize); 137519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 137619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 137719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// preincrement - move to the next interval. 137819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const_iterator &operator++() { 137919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(valid() && "Cannot increment end()"); 138019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (++path.leafOffset() == path.leafSize() && branched()) 138119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.moveRight(map->height); 138219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return *this; 138319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 138419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 138519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// postincrement - Dont do that! 138619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const_iterator operator++(int) { 138719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const_iterator tmp = *this; 138819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman operator++(); 138919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return tmp; 139019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 139119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 139219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// predecrement - move to the previous interval. 139319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const_iterator &operator--() { 139419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (path.leafOffset() && (valid() || !branched())) 139519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman --path.leafOffset(); 139619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 139719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.moveLeft(map->height); 139819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return *this; 139919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 140019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 140119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// postdecrement - Dont do that! 140219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const_iterator operator--(int) { 140319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const_iterator tmp = *this; 140419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman operator--(); 140519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return tmp; 140619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 140719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 140819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// find - Move to the first interval with stop >= x, or end(). 140919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This is a full search from the root, the current position is ignored. 141019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void find(KeyT x) { 141119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (branched()) 141219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman treeFind(x); 141319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 141419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setRoot(map->rootLeaf().findFrom(0, map->rootSize, x)); 141519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 141619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 141719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// advanceTo - Move to the first interval with stop >= x, or end(). 141819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// The search is started from the current position, and no earlier positions 141919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// can be found. This is much faster than find() for small moves. 142019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void advanceTo(KeyT x) { 142119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!valid()) 142219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 142319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (branched()) 142419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman treeAdvanceTo(x); 142519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 142619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.leafOffset() = 142719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x); 142819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 142919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 143019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 143119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 143219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// pathFillFind - Complete path by searching for x. 143319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param x Key to search for. 143419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 143519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid IntervalMap<KeyT, ValT, N, Traits>:: 143619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanconst_iterator::pathFillFind(KeyT x) { 143719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMapImpl::NodeRef NR = path.subtree(path.height()); 143819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = map->height - path.height() - 1; i; --i) { 143919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned p = NR.get<Branch>().safeFind(0, x); 144019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.push(NR, p); 144119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NR = NR.subtree(p); 144219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 144319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.push(NR, NR.get<Leaf>().safeFind(0, x)); 144419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 144519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 144619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// treeFind - Find in a branched tree. 144719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param x Key to search for. 144819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 144919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid IntervalMap<KeyT, ValT, N, Traits>:: 145019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanconst_iterator::treeFind(KeyT x) { 145119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setRoot(map->rootBranch().findFrom(0, map->rootSize, x)); 145219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (valid()) 145319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman pathFillFind(x); 145419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 145519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 145619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// treeAdvanceTo - Find position after the current one. 145719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param x Key to search for. 145819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 145919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid IntervalMap<KeyT, ValT, N, Traits>:: 146019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanconst_iterator::treeAdvanceTo(KeyT x) { 146119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Can we stay on the same leaf node? 146219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) { 146319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x); 146419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 146519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 146619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 146719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Drop the current leaf. 146819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.pop(); 146919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 147019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Search towards the root for a usable subtree. 147119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (path.height()) { 147219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned l = path.height() - 1; l; --l) { 147319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) { 147419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The branch node at l+1 is usable 147519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.offset(l + 1) = 147619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x); 147719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return pathFillFind(x); 147819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 147919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.pop(); 148019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 148119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Is the level-1 Branch usable? 148219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) { 148319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x); 148419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return pathFillFind(x); 148519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 148619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 148719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 148819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We reached the root. 148919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x)); 149019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (valid()) 149119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman pathFillFind(x); 149219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 149319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 149419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 149519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//--- IntervalMap::iterator ----// 149619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 149719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 149819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 149919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator { 150019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman friend class IntervalMap; 150119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef IntervalMapImpl::IdxPair IdxPair; 150219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 150319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman explicit iterator(IntervalMap &map) : const_iterator(map) {} 150419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 150519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void setNodeStop(unsigned Level, KeyT Stop); 150619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop); 150719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman template <typename NodeT> bool overflow(unsigned Level); 150819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void treeInsert(KeyT a, KeyT b, ValT y); 150919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void eraseNode(unsigned Level); 151019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void treeErase(bool UpdateRoot = true); 151119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool canCoalesceLeft(KeyT Start, ValT x); 151219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool canCoalesceRight(KeyT Stop, ValT x); 151319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 151419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 151519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// iterator - Create null iterator. 151619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator() {} 151719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 151819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// setStart - Move the start of the current interval. 151919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This may cause coalescing with the previous interval. 152019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param a New start key, must not overlap the previous interval. 152119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void setStart(KeyT a); 152219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 152319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// setStop - Move the end of the current interval. 152419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This may cause coalescing with the following interval. 152519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param b New stop key, must not overlap the following interval. 152619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void setStop(KeyT b); 152719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 152819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// setValue - Change the mapped value of the current interval. 152919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This may cause coalescing with the previous and following intervals. 153019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param x New value. 153119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void setValue(ValT x); 153219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 153319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// setStartUnchecked - Move the start of the current interval without 153419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// checking for coalescing or overlaps. 153519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This should only be used when it is known that coalescing is not required. 153619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param a New start key. 153719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void setStartUnchecked(KeyT a) { this->unsafeStart() = a; } 153819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 153919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// setStopUnchecked - Move the end of the current interval without checking 154019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// for coalescing or overlaps. 154119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This should only be used when it is known that coalescing is not required. 154219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param b New stop key. 154319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void setStopUnchecked(KeyT b) { 154419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman this->unsafeStop() = b; 154519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Update keys in branch nodes as well. 154619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (this->path.atLastEntry(this->path.height())) 154719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setNodeStop(this->path.height(), b); 154819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 154919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 155019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// setValueUnchecked - Change the mapped value of the current interval 155119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// without checking for coalescing. 155219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// @param x New value. 155319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void setValueUnchecked(ValT x) { this->unsafeValue() = x; } 155419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 155519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// insert - Insert mapping [a;b] -> y before the current position. 155619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void insert(KeyT a, KeyT b, ValT y); 155719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 155819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// erase - Erase the current interval. 155919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void erase(); 156019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 156119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator &operator++() { 156219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const_iterator::operator++(); 156319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return *this; 156419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 156519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 156619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator operator++(int) { 156719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator tmp = *this; 156819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman operator++(); 156919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return tmp; 157019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 157119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 157219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator &operator--() { 157319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const_iterator::operator--(); 157419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return *this; 157519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 157619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 157719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator operator--(int) { 157819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator tmp = *this; 157919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman operator--(); 158019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return tmp; 158119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 158219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 158319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 158419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 158519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// canCoalesceLeft - Can the current interval coalesce to the left after 158619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// changing start or value? 158719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Start New start of current interval. 158819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Value New value for current interval. 158919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @return True when updating the current interval would enable coalescing. 159019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 159119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool IntervalMap<KeyT, ValT, N, Traits>:: 159219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumaniterator::canCoalesceLeft(KeyT Start, ValT Value) { 159319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman using namespace IntervalMapImpl; 159419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Path &P = this->path; 159519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!this->branched()) { 159619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned i = P.leafOffset(); 159719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RootLeaf &Node = P.leaf<RootLeaf>(); 159819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return i && Node.value(i-1) == Value && 159919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Traits::adjacent(Node.stop(i-1), Start); 160019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 160119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Branched. 160219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (unsigned i = P.leafOffset()) { 160319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Leaf &Node = P.leaf<Leaf>(); 160419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start); 160519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (NodeRef NR = P.getLeftSibling(P.height())) { 160619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned i = NR.size() - 1; 160719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Leaf &Node = NR.get<Leaf>(); 160819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start); 160919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 161019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 161119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 161219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 161319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// canCoalesceRight - Can the current interval coalesce to the right after 161419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// changing stop or value? 161519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Stop New stop of current interval. 161619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Value New value for current interval. 161719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @return True when updating the current interval would enable coalescing. 161819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 161919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool IntervalMap<KeyT, ValT, N, Traits>:: 162019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumaniterator::canCoalesceRight(KeyT Stop, ValT Value) { 162119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman using namespace IntervalMapImpl; 162219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Path &P = this->path; 162319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned i = P.leafOffset() + 1; 162419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!this->branched()) { 162519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (i >= P.leafSize()) 162619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 162719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RootLeaf &Node = P.leaf<RootLeaf>(); 162819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); 162919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 163019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Branched. 163119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (i < P.leafSize()) { 163219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Leaf &Node = P.leaf<Leaf>(); 163319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i)); 163419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (NodeRef NR = P.getRightSibling(P.height())) { 163519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Leaf &Node = NR.get<Leaf>(); 163619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0)); 163719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 163819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 163919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 164019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 164119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// setNodeStop - Update the stop key of the current node at level and above. 164219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 164319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid IntervalMap<KeyT, ValT, N, Traits>:: 164419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumaniterator::setNodeStop(unsigned Level, KeyT Stop) { 164519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // There are no references to the root node, so nothing to update. 164619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Level) 164719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 164819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMapImpl::Path &P = this->path; 164919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Update nodes pointing to the current node. 165019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (--Level) { 165119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.node<Branch>(Level).stop(P.offset(Level)) = Stop; 165219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!P.atLastEntry(Level)) 165319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 165419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 165519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Update root separately since it has a different layout. 165619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.node<RootBranch>(Level).stop(P.offset(Level)) = Stop; 165719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 165819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 165919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 166019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid IntervalMap<KeyT, ValT, N, Traits>:: 166119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumaniterator::setStart(KeyT a) { 166219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(Traits::stopLess(a, this->stop()) && "Cannot move start beyond stop"); 166319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyT &CurStart = this->unsafeStart(); 166419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) { 166519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurStart = a; 166619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 166719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 166819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Coalesce with the interval to the left. 166919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman --*this; 167019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman a = this->start(); 167119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman erase(); 167219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setStartUnchecked(a); 167319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 167419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 167519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 167619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid IntervalMap<KeyT, ValT, N, Traits>:: 167719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumaniterator::setStop(KeyT b) { 167819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(Traits::stopLess(this->start(), b) && "Cannot move stop beyond start"); 167919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Traits::startLess(b, this->stop()) || 168019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !canCoalesceRight(b, this->value())) { 168119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setStopUnchecked(b); 168219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 168319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 168419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Coalesce with interval to the right. 168519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyT a = this->start(); 168619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman erase(); 168719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setStartUnchecked(a); 168819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 168919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 169019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 169119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid IntervalMap<KeyT, ValT, N, Traits>:: 169219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumaniterator::setValue(ValT x) { 169319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setValueUnchecked(x); 169419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (canCoalesceRight(this->stop(), x)) { 169519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyT a = this->start(); 169619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman erase(); 169719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setStartUnchecked(a); 169819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 169919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (canCoalesceLeft(this->start(), x)) { 170019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman --*this; 170119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyT a = this->start(); 170219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman erase(); 170319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setStartUnchecked(a); 170419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 170519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 170619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 170719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// insertNode - insert a node before the current path at level. 170819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Leave the current path pointing at the new node. 170919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Level path index of the node to be inserted. 171019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Node The node to be inserted. 171119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Stop The last index in the new node. 171219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @return True if the tree height was increased. 171319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 171419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool IntervalMap<KeyT, ValT, N, Traits>:: 171519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumaniterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) { 171619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(Level && "Cannot insert next to the root"); 171719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool SplitRoot = false; 171819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMap &IM = *this->map; 171919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMapImpl::Path &P = this->path; 172019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 172119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Level == 1) { 172219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Insert into the root branch node. 172319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (IM.rootSize < RootBranch::Capacity) { 172419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop); 172519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.setSize(0, ++IM.rootSize); 172619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.reset(Level); 172719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return SplitRoot; 172819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 172919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 173019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We need to split the root while keeping our position. 173119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SplitRoot = true; 173219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IdxPair Offset = IM.splitRoot(P.offset(0)); 173319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 173419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 173519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Fall through to insert at the new higher level. 173619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++Level; 173719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 173819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 173919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // When inserting before end(), make sure we have a valid path. 174019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.legalizeForInsert(--Level); 174119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 174219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Insert into the branch node at Level-1. 174319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (P.size(Level) == Branch::Capacity) { 174419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Branch node is full, handle handle the overflow. 174519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!SplitRoot && "Cannot overflow after splitting the root"); 174619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SplitRoot = overflow<Branch>(Level); 174719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Level += SplitRoot; 174819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 174919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop); 175019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.setSize(Level, P.size(Level) + 1); 175119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (P.atLastEntry(Level)) 175219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setNodeStop(Level, Stop); 175319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.reset(Level + 1); 175419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return SplitRoot; 175519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 175619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 175719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// insert 175819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 175919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid IntervalMap<KeyT, ValT, N, Traits>:: 176019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumaniterator::insert(KeyT a, KeyT b, ValT y) { 176119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (this->branched()) 176219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return treeInsert(a, b, y); 176319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMap &IM = *this->map; 176419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMapImpl::Path &P = this->path; 176519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 176619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Try simple root leaf insert. 176719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y); 176819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 176919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Was the root node insert successful? 177019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Size <= RootLeaf::Capacity) { 177119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.setSize(0, IM.rootSize = Size); 177219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 177319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 177419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 177519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Root leaf node is full, we must branch. 177619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IdxPair Offset = IM.branchRoot(P.leafOffset()); 177719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset); 177819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 177919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Now it fits in the new leaf. 178019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman treeInsert(a, b, y); 178119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 178219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 178319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 178419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 178519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid IntervalMap<KeyT, ValT, N, Traits>:: 178619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumaniterator::treeInsert(KeyT a, KeyT b, ValT y) { 178719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman using namespace IntervalMapImpl; 178819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Path &P = this->path; 178919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 179019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!P.valid()) 179119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.legalizeForInsert(this->map->height); 179219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 179319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Check if this insertion will extend the node to the left. 179419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) { 179519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Node is growing to the left, will it affect a left sibling node? 179619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NodeRef Sib = P.getLeftSibling(P.height())) { 179719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Leaf &SibLeaf = Sib.get<Leaf>(); 179819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned SibOfs = Sib.size() - 1; 179919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SibLeaf.value(SibOfs) == y && 180019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Traits::adjacent(SibLeaf.stop(SibOfs), a)) { 180119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This insertion will coalesce with the last entry in SibLeaf. We can 180219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // handle it in two ways: 180319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 1. Extend SibLeaf.stop to b and be done, or 180419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 2. Extend a to SibLeaf, erase the SibLeaf entry and continue. 180519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We prefer 1., but need 2 when coalescing to the right as well. 180619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Leaf &CurLeaf = P.leaf<Leaf>(); 180719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.moveLeft(P.height()); 180819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Traits::stopLess(b, CurLeaf.start(0)) && 180919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) { 181019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Easy, just extend SibLeaf and we're done. 181119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b); 181219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 181319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 181419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We have both left and right coalescing. Erase the old SibLeaf entry 181519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // and continue inserting the larger interval. 181619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman a = SibLeaf.start(SibOfs); 181719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman treeErase(/* UpdateRoot= */false); 181819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 181919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 182019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 182119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // No left sibling means we are at begin(). Update cached bound. 182219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman this->map->rootBranchStart() = a; 182319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 182419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 182519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 182619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // When we are inserting at the end of a leaf node, we must update stops. 182719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Size = P.leafSize(); 182819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool Grow = P.leafOffset() == Size; 182919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y); 183019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 183119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Leaf insertion unsuccessful? Overflow and try again. 183219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Size > Leaf::Capacity) { 183319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman overflow<Leaf>(P.height()); 183419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Grow = P.leafOffset() == P.leafSize(); 183519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y); 183619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(Size <= Leaf::Capacity && "overflow() didn't make room"); 183719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 183819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 183919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Inserted, update offset and leaf size. 184019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.setSize(P.height(), Size); 184119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 184219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Insert was the last node entry, update stops. 184319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Grow) 184419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setNodeStop(P.height(), b); 184519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 184619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 184719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// erase - erase the current interval and move to the next position. 184819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 184919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid IntervalMap<KeyT, ValT, N, Traits>:: 185019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumaniterator::erase() { 185119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMap &IM = *this->map; 185219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMapImpl::Path &P = this->path; 185319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(P.valid() && "Cannot erase end()"); 185419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (this->branched()) 185519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return treeErase(); 185619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IM.rootLeaf().erase(P.leafOffset(), IM.rootSize); 185719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.setSize(0, --IM.rootSize); 185819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 185919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 186019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// treeErase - erase() for a branched tree. 186119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 186219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid IntervalMap<KeyT, ValT, N, Traits>:: 186319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumaniterator::treeErase(bool UpdateRoot) { 186419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMap &IM = *this->map; 186519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMapImpl::Path &P = this->path; 186619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Leaf &Node = P.leaf<Leaf>(); 186719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 186819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Nodes are not allowed to become empty. 186919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (P.leafSize() == 1) { 187019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IM.deleteNode(&Node); 187119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman eraseNode(IM.height); 187219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Update rootBranchStart if we erased begin(). 187319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (UpdateRoot && IM.branched() && P.valid() && P.atBegin()) 187419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IM.rootBranchStart() = P.leaf<Leaf>().start(0); 187519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 187619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 187719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 187819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Erase current entry. 187919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Node.erase(P.leafOffset(), P.leafSize()); 188019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned NewSize = P.leafSize() - 1; 188119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.setSize(IM.height, NewSize); 188219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // When we erase the last entry, update stop and move to a legal position. 188319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (P.leafOffset() == NewSize) { 188419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setNodeStop(IM.height, Node.stop(NewSize - 1)); 188519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.moveRight(IM.height); 188619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (UpdateRoot && P.atBegin()) 188719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IM.rootBranchStart() = P.leaf<Leaf>().start(0); 188819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 188919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 189019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// eraseNode - Erase the current node at Level from its parent and move path to 189119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// the first entry of the next sibling node. 189219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// The node must be deallocated by the caller. 189319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Level 1..height, the root node cannot be erased. 189419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 189519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid IntervalMap<KeyT, ValT, N, Traits>:: 189619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumaniterator::eraseNode(unsigned Level) { 189719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(Level && "Cannot erase root node"); 189819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMap &IM = *this->map; 189919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMapImpl::Path &P = this->path; 190019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 190119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (--Level == 0) { 190219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IM.rootBranch().erase(P.offset(0), IM.rootSize); 190319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.setSize(0, --IM.rootSize); 190419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this cleared the root, switch to height=0. 190519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (IM.empty()) { 190619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IM.switchRootToLeaf(); 190719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman this->setRoot(0); 190819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 190919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 191019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 191119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Remove node ref from branch node at Level. 191219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Branch &Parent = P.node<Branch>(Level); 191319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (P.size(Level) == 1) { 191419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Branch node became empty, remove it recursively. 191519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IM.deleteNode(&Parent); 191619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman eraseNode(Level); 191719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 191819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Branch node won't become empty. 191919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Parent.erase(P.offset(Level), P.size(Level)); 192019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned NewSize = P.size(Level) - 1; 192119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.setSize(Level, NewSize); 192219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If we removed the last branch, update stop and move to a legal pos. 192319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (P.offset(Level) == NewSize) { 192419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setNodeStop(Level, Parent.stop(NewSize - 1)); 192519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.moveRight(Level); 192619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 192719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 192819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 192919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Update path cache for the new right sibling position. 193019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (P.valid()) { 193119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.reset(Level + 1); 193219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.offset(Level + 1) = 0; 193319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 193419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 193519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 193619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// overflow - Distribute entries of the current node evenly among 193719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// its siblings and ensure that the current node is not full. 193819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// This may require allocating a new node. 193919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param NodeT The type of node at Level (Leaf or Branch). 194019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @param Level path index of the overflowing node. 194119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// @return True when the tree height was changed. 194219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename KeyT, typename ValT, unsigned N, typename Traits> 194319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename NodeT> 194419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool IntervalMap<KeyT, ValT, N, Traits>:: 194519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumaniterator::overflow(unsigned Level) { 194619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman using namespace IntervalMapImpl; 194719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Path &P = this->path; 194819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned CurSize[4]; 194919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeT *Node[4]; 195019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Nodes = 0; 195119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Elements = 0; 195219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Offset = P.offset(Level); 195319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 195419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Do we have a left sibling? 195519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeRef LeftSib = P.getLeftSibling(Level); 195619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LeftSib) { 195719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Offset += Elements = CurSize[Nodes] = LeftSib.size(); 195819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Node[Nodes++] = &LeftSib.get<NodeT>(); 195919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 196019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 196119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Current node. 196219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Elements += CurSize[Nodes] = P.size(Level); 196319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Node[Nodes++] = &P.node<NodeT>(Level); 196419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 196519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Do we have a right sibling? 196619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeRef RightSib = P.getRightSibling(Level); 196719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (RightSib) { 196819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Elements += CurSize[Nodes] = RightSib.size(); 196919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Node[Nodes++] = &RightSib.get<NodeT>(); 197019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 197119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 197219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Do we need to allocate a new node? 197319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned NewNode = 0; 197419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Elements + 1 > Nodes * NodeT::Capacity) { 197519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Insert NewNode at the penultimate position, or after a single node. 197619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewNode = Nodes == 1 ? 1 : Nodes - 1; 197719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurSize[Nodes] = CurSize[NewNode]; 197819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Node[Nodes] = Node[NewNode]; 197919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurSize[NewNode] = 0; 198066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Node[NewNode] = this->map->template newNode<NodeT>(); 198119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++Nodes; 198219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 198319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 198419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Compute the new element distribution. 198519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned NewSize[4]; 198619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity, 198719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurSize, NewSize, Offset, true); 198819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman adjustSiblingSizes(Node, Nodes, CurSize, NewSize); 198919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 199019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Move current location to the leftmost node. 199119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LeftSib) 199219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.moveLeft(Level); 199319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 199419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Elements have been rearranged, now update node sizes and stops. 199519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool SplitRoot = false; 199619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Pos = 0; 199719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (;;) { 199819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1); 199919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NewNode && Pos == NewNode) { 200019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop); 200119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Level += SplitRoot; 200219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 200319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.setSize(Level, NewSize[Pos]); 200419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman setNodeStop(Level, Stop); 200519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 200619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Pos + 1 == Nodes) 200719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 200819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.moveRight(Level); 200919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++Pos; 201019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 201119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 201219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Where was I? Find NewOffset. 201319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while(Pos != NewOffset.first) { 201419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.moveLeft(Level); 201519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman --Pos; 201619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 201719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman P.offset(Level) = NewOffset.second; 201819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return SplitRoot; 201919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 202019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 202119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 202219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//--- IntervalMapOverlaps ----// 202319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman//===----------------------------------------------------------------------===// 202419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 202519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two 202619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// IntervalMaps. The maps may be different, but the KeyT and Traits types 202719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// should be the same. 202819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 202919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Typical uses: 203019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 203119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 1. Test for overlap: 203219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// bool overlap = IntervalMapOverlaps(a, b).valid(); 203319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 203419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 2. Enumerate overlaps: 203519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// for (IntervalMapOverlaps I(a, b); I.valid() ; ++I) { ... } 203619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 203719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate <typename MapA, typename MapB> 203819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanclass IntervalMapOverlaps { 203919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef typename MapA::KeyType KeyType; 204019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef typename MapA::KeyTraits Traits; 204119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typename MapA::const_iterator posA; 204219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typename MapB::const_iterator posB; 204319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 204419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// advance - Move posA and posB forward until reaching an overlap, or until 204519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// either meets end. 204619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Don't move the iterators if they are already overlapping. 204719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void advance() { 204819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!valid()) 204919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 205019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 205119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Traits::stopLess(posA.stop(), posB.start())) { 205219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // A ends before B begins. Catch up. 205319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman posA.advanceTo(posB.start()); 205419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start())) 205519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 205619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (Traits::stopLess(posB.stop(), posA.start())) { 205719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // B ends before A begins. Catch up. 205819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman posB.advanceTo(posA.start()); 205919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start())) 206019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 206119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else 206219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Already overlapping. 206319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 206419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 206519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (;;) { 206619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Make a.end > b.start. 206719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman posA.advanceTo(posB.start()); 206819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start())) 206919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 207019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Make b.end > a.start. 207119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman posB.advanceTo(posA.start()); 207219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start())) 207319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 207419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 207519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 207619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 207719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 207819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// IntervalMapOverlaps - Create an iterator for the overlaps of a and b. 207919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMapOverlaps(const MapA &a, const MapB &b) 208019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman : posA(b.empty() ? a.end() : a.find(b.start())), 208119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); } 208219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 208319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// valid - Return true if iterator is at an overlap. 208419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool valid() const { 208519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return posA.valid() && posB.valid(); 208619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 208719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 208819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// a - access the left hand side in the overlap. 208919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const typename MapA::const_iterator &a() const { return posA; } 209019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 209119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// b - access the right hand side in the overlap. 209219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const typename MapB::const_iterator &b() const { return posB; } 209319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 209419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// start - Beginning of the overlapping interval. 209519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyType start() const { 209619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyType ak = a().start(); 209719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyType bk = b().start(); 209819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Traits::startLess(ak, bk) ? bk : ak; 209919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 210019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 210119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// stop - End of the overlapping interval. 210219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyType stop() const { 210319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyType ak = a().stop(); 210419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman KeyType bk = b().stop(); 210519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Traits::startLess(ak, bk) ? ak : bk; 210619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 210719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 210819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// skipA - Move to the next overlap that doesn't involve a(). 210919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void skipA() { 211019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++posA; 211119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman advance(); 211219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 211319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 211419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// skipB - Move to the next overlap that doesn't involve b(). 211519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void skipB() { 211619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++posB; 211719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman advance(); 211819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 211919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 212019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Preincrement - Move to the next overlap. 212119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntervalMapOverlaps &operator++() { 212219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Bump the iterator that ends first. The other one may have more overlaps. 212319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Traits::startLess(posB.stop(), posA.stop())) 212419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman skipB(); 212519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 212619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman skipA(); 212719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return *this; 212819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 212919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 213019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// advanceTo - Move to the first overlapping interval with 213119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// stopLess(x, stop()). 213219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void advanceTo(KeyType x) { 213319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!valid()) 213419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 213519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Make sure advanceTo sees monotonic keys. 213619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Traits::stopLess(posA.stop(), x)) 213719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman posA.advanceTo(x); 213819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Traits::stopLess(posB.stop(), x)) 213919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman posB.advanceTo(x); 214019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman advance(); 214119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 214219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman}; 214319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 214419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} // namespace llvm 214519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 214619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#endif 2147