ContinuousRangeMap.h revision 243830
1139749Simp//===--- ContinuousRangeMap.h - Map with int range as key -------*- C++ -*-===// 272017Scg// 372017Scg// The LLVM Compiler Infrastructure 472017Scg// 572017Scg// This file is distributed under the University of Illinois Open Source 672017Scg// License. See LICENSE.TXT for details. 772017Scg// 872017Scg//===----------------------------------------------------------------------===// 972017Scg// 1072017Scg// This file defines the ContinuousRangeMap class, which is a highly 1172017Scg// specialized container used by serialization. 1272017Scg// 1372017Scg//===----------------------------------------------------------------------===// 1472017Scg 1572017Scg#ifndef LLVM_CLANG_SERIALIZATION_CONTINUOUS_RANGE_MAP_H 1672017Scg#define LLVM_CLANG_SERIALIZATION_CONTINUOUS_RANGE_MAP_H 1772017Scg 1872017Scg#include "llvm/ADT/SmallVector.h" 1972017Scg#include <algorithm> 2072017Scg#include <utility> 2172017Scg 2272017Scgnamespace clang { 2372017Scg 2472017Scg/// \brief A map from continuous integer ranges to some value, with a very 2572017Scg/// specialized interface. 2672017Scg/// 2772017Scg/// CRM maps from integer ranges to values. The ranges are continuous, i.e. 2872017Scg/// where one ends, the next one begins. So if the map contains the stops I0-3, 2972017Scg/// the first range is from I0 to I1, the second from I1 to I2, the third from 3072017Scg/// I2 to I3 and the last from I3 to infinity. 3172017Scg/// 3272017Scg/// Ranges must be inserted in order. Inserting a new stop I4 into the map will 3372017Scg/// shrink the fourth range to I3 to I4 and add the new range I4 to inf. 3472017Scgtemplate <typename Int, typename V, unsigned InitialCapacity> 3572017Scgclass ContinuousRangeMap { 3672017Scgpublic: 3772017Scg typedef std::pair<Int, V> value_type; 3872017Scg typedef value_type &reference; 3972017Scg typedef const value_type &const_reference; 4072017Scg typedef value_type *pointer; 4172017Scg typedef const value_type *const_pointer; 4272017Scg 4372017Scgprivate: 4472017Scg typedef SmallVector<value_type, InitialCapacity> Representation; 4572017Scg Representation Rep; 4672017Scg 4772017Scg struct Compare { 4872017Scg bool operator ()(const_reference L, Int R) const { 4972017Scg return L.first < R; 5072017Scg } 5172017Scg bool operator ()(Int L, const_reference R) const { 5272455Scg return L < R.first; 5372017Scg } 5472017Scg bool operator ()(Int L, Int R) const { 5572017Scg return L < R; 5672017Scg } 5772017Scg bool operator ()(const_reference L, const_reference R) const { 5872017Scg return L.first < R.first; 5972017Scg } 6072017Scg }; 6172017Scg 6272017Scgpublic: 6372017Scg void insert(const value_type &Val) { 6472017Scg if (!Rep.empty() && Rep.back() == Val) 6572017Scg return; 6672017Scg 6772017Scg assert((Rep.empty() || Rep.back().first < Val.first) && 6872017Scg "Must insert keys in order."); 6972017Scg Rep.push_back(Val); 7072017Scg } 7172017Scg 7272017Scg void insertOrReplace(const value_type &Val) { 7372017Scg iterator I = std::lower_bound(Rep.begin(), Rep.end(), Val, Compare()); 7472017Scg if (I != Rep.end() && I->first == Val.first) { 7572017Scg I->second = Val.second; 7672017Scg return; 7772017Scg } 7872017Scg 7972017Scg Rep.insert(I, Val); 8072017Scg } 8172017Scg 8272017Scg typedef typename Representation::iterator iterator; 8372017Scg typedef typename Representation::const_iterator const_iterator; 8472017Scg 8572017Scg iterator begin() { return Rep.begin(); } 8672017Scg iterator end() { return Rep.end(); } 8772017Scg const_iterator begin() const { return Rep.begin(); } 8872017Scg const_iterator end() const { return Rep.end(); } 8972017Scg 9072017Scg iterator find(Int K) { 9172017Scg iterator I = std::upper_bound(Rep.begin(), Rep.end(), K, Compare()); 9272017Scg // I points to the first entry with a key > K, which is the range that 9372017Scg // follows the one containing K. 9472017Scg if (I == Rep.begin()) 9572017Scg return Rep.end(); 9672017Scg --I; 9772017Scg return I; 9872017Scg } 9972017Scg const_iterator find(Int K) const { 10072017Scg return const_cast<ContinuousRangeMap*>(this)->find(K); 10172017Scg } 10272017Scg 10372017Scg reference back() { return Rep.back(); } 10472455Scg const_reference back() const { return Rep.back(); } 10572455Scg 10675702Sorion /// \brief An object that helps properly build a continuous range map 10772017Scg /// from a set of values. 10872017Scg class Builder { 10972017Scg ContinuousRangeMap &Self; 11072017Scg 11172017Scg Builder(const Builder&) LLVM_DELETED_FUNCTION; 11272455Scg Builder &operator=(const Builder&) LLVM_DELETED_FUNCTION; 11372017Scg 11472017Scg public: 11572455Scg explicit Builder(ContinuousRangeMap &Self) : Self(Self) { } 11672017Scg 11772017Scg ~Builder() { 11872017Scg std::sort(Self.Rep.begin(), Self.Rep.end(), Compare()); 11972017Scg } 12072017Scg 12172017Scg void insert(const value_type &Val) { 12272017Scg Self.Rep.push_back(Val); 12372017Scg } 12472017Scg }; 12572017Scg friend class Builder; 12672017Scg}; 12772017Scg 12872017Scg} 12972017Scg 13072017Scg#endif 13172017Scg