1226586Sdim//===--- ContinuousRangeMap.h - Map with int range as key -------*- C++ -*-===// 2226586Sdim// 3226586Sdim// The LLVM Compiler Infrastructure 4226586Sdim// 5226586Sdim// This file is distributed under the University of Illinois Open Source 6226586Sdim// License. See LICENSE.TXT for details. 7226586Sdim// 8226586Sdim//===----------------------------------------------------------------------===// 9226586Sdim// 10226586Sdim// This file defines the ContinuousRangeMap class, which is a highly 11226586Sdim// specialized container used by serialization. 12226586Sdim// 13226586Sdim//===----------------------------------------------------------------------===// 14226586Sdim 15226586Sdim#ifndef LLVM_CLANG_SERIALIZATION_CONTINUOUS_RANGE_MAP_H 16226586Sdim#define LLVM_CLANG_SERIALIZATION_CONTINUOUS_RANGE_MAP_H 17226586Sdim 18252723Sdim#include "clang/Basic/LLVM.h" 19226586Sdim#include "llvm/ADT/SmallVector.h" 20226586Sdim#include <algorithm> 21226586Sdim#include <utility> 22226586Sdim 23226586Sdimnamespace clang { 24226586Sdim 25226586Sdim/// \brief A map from continuous integer ranges to some value, with a very 26226586Sdim/// specialized interface. 27226586Sdim/// 28226586Sdim/// CRM maps from integer ranges to values. The ranges are continuous, i.e. 29226586Sdim/// where one ends, the next one begins. So if the map contains the stops I0-3, 30226586Sdim/// the first range is from I0 to I1, the second from I1 to I2, the third from 31226586Sdim/// I2 to I3 and the last from I3 to infinity. 32226586Sdim/// 33226586Sdim/// Ranges must be inserted in order. Inserting a new stop I4 into the map will 34226586Sdim/// shrink the fourth range to I3 to I4 and add the new range I4 to inf. 35226586Sdimtemplate <typename Int, typename V, unsigned InitialCapacity> 36226586Sdimclass ContinuousRangeMap { 37226586Sdimpublic: 38226586Sdim typedef std::pair<Int, V> value_type; 39226586Sdim typedef value_type &reference; 40226586Sdim typedef const value_type &const_reference; 41226586Sdim typedef value_type *pointer; 42226586Sdim typedef const value_type *const_pointer; 43226586Sdim 44226586Sdimprivate: 45226586Sdim typedef SmallVector<value_type, InitialCapacity> Representation; 46226586Sdim Representation Rep; 47226586Sdim 48226586Sdim struct Compare { 49226586Sdim bool operator ()(const_reference L, Int R) const { 50226586Sdim return L.first < R; 51226586Sdim } 52226586Sdim bool operator ()(Int L, const_reference R) const { 53226586Sdim return L < R.first; 54226586Sdim } 55226586Sdim bool operator ()(Int L, Int R) const { 56226586Sdim return L < R; 57226586Sdim } 58226586Sdim bool operator ()(const_reference L, const_reference R) const { 59226586Sdim return L.first < R.first; 60226586Sdim } 61226586Sdim }; 62226586Sdim 63226586Sdimpublic: 64226586Sdim void insert(const value_type &Val) { 65226586Sdim if (!Rep.empty() && Rep.back() == Val) 66226586Sdim return; 67226586Sdim 68226586Sdim assert((Rep.empty() || Rep.back().first < Val.first) && 69226586Sdim "Must insert keys in order."); 70226586Sdim Rep.push_back(Val); 71226586Sdim } 72235633Sdim 73235633Sdim void insertOrReplace(const value_type &Val) { 74235633Sdim iterator I = std::lower_bound(Rep.begin(), Rep.end(), Val, Compare()); 75235633Sdim if (I != Rep.end() && I->first == Val.first) { 76235633Sdim I->second = Val.second; 77235633Sdim return; 78235633Sdim } 79235633Sdim 80235633Sdim Rep.insert(I, Val); 81235633Sdim } 82226586Sdim 83226586Sdim typedef typename Representation::iterator iterator; 84226586Sdim typedef typename Representation::const_iterator const_iterator; 85226586Sdim 86226586Sdim iterator begin() { return Rep.begin(); } 87226586Sdim iterator end() { return Rep.end(); } 88226586Sdim const_iterator begin() const { return Rep.begin(); } 89226586Sdim const_iterator end() const { return Rep.end(); } 90226586Sdim 91226586Sdim iterator find(Int K) { 92226586Sdim iterator I = std::upper_bound(Rep.begin(), Rep.end(), K, Compare()); 93226586Sdim // I points to the first entry with a key > K, which is the range that 94226586Sdim // follows the one containing K. 95226586Sdim if (I == Rep.begin()) 96226586Sdim return Rep.end(); 97226586Sdim --I; 98226586Sdim return I; 99226586Sdim } 100226586Sdim const_iterator find(Int K) const { 101226586Sdim return const_cast<ContinuousRangeMap*>(this)->find(K); 102226586Sdim } 103226586Sdim 104226586Sdim reference back() { return Rep.back(); } 105226586Sdim const_reference back() const { return Rep.back(); } 106226586Sdim 107226586Sdim /// \brief An object that helps properly build a continuous range map 108226586Sdim /// from a set of values. 109226586Sdim class Builder { 110226586Sdim ContinuousRangeMap &Self; 111226586Sdim 112245431Sdim Builder(const Builder&) LLVM_DELETED_FUNCTION; 113245431Sdim Builder &operator=(const Builder&) LLVM_DELETED_FUNCTION; 114226586Sdim 115226586Sdim public: 116226586Sdim explicit Builder(ContinuousRangeMap &Self) : Self(Self) { } 117226586Sdim 118226586Sdim ~Builder() { 119226586Sdim std::sort(Self.Rep.begin(), Self.Rep.end(), Compare()); 120226586Sdim } 121226586Sdim 122226586Sdim void insert(const value_type &Val) { 123226586Sdim Self.Rep.push_back(Val); 124226586Sdim } 125226586Sdim }; 126226586Sdim friend class Builder; 127226586Sdim}; 128226586Sdim 129226586Sdim} 130226586Sdim 131226586Sdim#endif 132