1f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor//===--- ContinuousRangeMap.h - Map with int range as key -------*- C++ -*-===// 2f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor// 3f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor// The LLVM Compiler Infrastructure 4f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor// 5f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor// This file is distributed under the University of Illinois Open Source 6f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor// License. See LICENSE.TXT for details. 7f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor// 8f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor//===----------------------------------------------------------------------===// 9f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor// 10f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor// This file defines the ContinuousRangeMap class, which is a highly 11f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor// specialized container used by serialization. 12f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor// 13f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor//===----------------------------------------------------------------------===// 14f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor 15f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor#ifndef LLVM_CLANG_SERIALIZATION_CONTINUOUS_RANGE_MAP_H 16f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor#define LLVM_CLANG_SERIALIZATION_CONTINUOUS_RANGE_MAP_H 17f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor 189946fc735d7285f2195f89635370f534afd9877eDmitri Gribenko#include "clang/Basic/LLVM.h" 19f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor#include "llvm/ADT/SmallVector.h" 20f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor#include <algorithm> 21f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor#include <utility> 22f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor 23f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregornamespace clang { 24f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor 25f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor/// \brief A map from continuous integer ranges to some value, with a very 26f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor/// specialized interface. 27f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor/// 28f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor/// CRM maps from integer ranges to values. The ranges are continuous, i.e. 29f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor/// where one ends, the next one begins. So if the map contains the stops I0-3, 30f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor/// the first range is from I0 to I1, the second from I1 to I2, the third from 31f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor/// I2 to I3 and the last from I3 to infinity. 32f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor/// 33f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor/// Ranges must be inserted in order. Inserting a new stop I4 into the map will 34f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor/// shrink the fourth range to I3 to I4 and add the new range I4 to inf. 35f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregortemplate <typename Int, typename V, unsigned InitialCapacity> 36f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregorclass ContinuousRangeMap { 37f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregorpublic: 38a119da0761cb6b85f53857eaee50f6ad8c5ea0a0Douglas Gregor typedef std::pair<Int, V> value_type; 39f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor typedef value_type &reference; 40f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor typedef const value_type &const_reference; 41f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor typedef value_type *pointer; 42f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor typedef const value_type *const_pointer; 43f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor 44f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregorprivate: 45686775deca8b8685eb90801495880e3abdd844c2Chris Lattner typedef SmallVector<value_type, InitialCapacity> Representation; 46f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor Representation Rep; 47f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor 48f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor struct Compare { 49f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor bool operator ()(const_reference L, Int R) const { 50f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor return L.first < R; 51f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor } 52f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor bool operator ()(Int L, const_reference R) const { 53f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor return L < R.first; 54f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor } 5507e5f1a7047f82da14c3223d14435bee4e763369Douglas Gregor bool operator ()(Int L, Int R) const { 5607e5f1a7047f82da14c3223d14435bee4e763369Douglas Gregor return L < R; 5707e5f1a7047f82da14c3223d14435bee4e763369Douglas Gregor } 5807e5f1a7047f82da14c3223d14435bee4e763369Douglas Gregor bool operator ()(const_reference L, const_reference R) const { 5907e5f1a7047f82da14c3223d14435bee4e763369Douglas Gregor return L.first < R.first; 6007e5f1a7047f82da14c3223d14435bee4e763369Douglas Gregor } 61f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor }; 62f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor 63f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregorpublic: 64f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor void insert(const value_type &Val) { 65272b6bc6a6c8fc04f951ad850df68c44d137f513Douglas Gregor if (!Rep.empty() && Rep.back() == Val) 66272b6bc6a6c8fc04f951ad850df68c44d137f513Douglas Gregor return; 67272b6bc6a6c8fc04f951ad850df68c44d137f513Douglas Gregor 68f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor assert((Rep.empty() || Rep.back().first < Val.first) && 69f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor "Must insert keys in order."); 70f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor Rep.push_back(Val); 71f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor } 72adafc2edc0dc4fa25ea6f0a136f599a6ac279081Douglas Gregor 73adafc2edc0dc4fa25ea6f0a136f599a6ac279081Douglas Gregor void insertOrReplace(const value_type &Val) { 74adafc2edc0dc4fa25ea6f0a136f599a6ac279081Douglas Gregor iterator I = std::lower_bound(Rep.begin(), Rep.end(), Val, Compare()); 75adafc2edc0dc4fa25ea6f0a136f599a6ac279081Douglas Gregor if (I != Rep.end() && I->first == Val.first) { 76adafc2edc0dc4fa25ea6f0a136f599a6ac279081Douglas Gregor I->second = Val.second; 77adafc2edc0dc4fa25ea6f0a136f599a6ac279081Douglas Gregor return; 78adafc2edc0dc4fa25ea6f0a136f599a6ac279081Douglas Gregor } 79adafc2edc0dc4fa25ea6f0a136f599a6ac279081Douglas Gregor 80adafc2edc0dc4fa25ea6f0a136f599a6ac279081Douglas Gregor Rep.insert(I, Val); 81adafc2edc0dc4fa25ea6f0a136f599a6ac279081Douglas Gregor } 82f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor 83f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor typedef typename Representation::iterator iterator; 84f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor typedef typename Representation::const_iterator const_iterator; 85f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor 86f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor iterator begin() { return Rep.begin(); } 87f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor iterator end() { return Rep.end(); } 88f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor const_iterator begin() const { return Rep.begin(); } 89f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor const_iterator end() const { return Rep.end(); } 90f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor 91f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor iterator find(Int K) { 92f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor iterator I = std::upper_bound(Rep.begin(), Rep.end(), K, Compare()); 93f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor // I points to the first entry with a key > K, which is the range that 94f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor // follows the one containing K. 95f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor if (I == Rep.begin()) 96f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor return Rep.end(); 97f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor --I; 98f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor return I; 99f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor } 100f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor const_iterator find(Int K) const { 101f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor return const_cast<ContinuousRangeMap*>(this)->find(K); 102f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor } 103f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor 104f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor reference back() { return Rep.back(); } 105f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor const_reference back() const { return Rep.back(); } 106f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor 107f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor /// \brief An object that helps properly build a continuous range map 108f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor /// from a set of values. 109f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor class Builder { 110f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor ContinuousRangeMap &Self; 111f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor 112f56faa01936b9cf909623d7f06e3c2569ca4a78eDmitri Gribenko Builder(const Builder&) LLVM_DELETED_FUNCTION; 113f56faa01936b9cf909623d7f06e3c2569ca4a78eDmitri Gribenko Builder &operator=(const Builder&) LLVM_DELETED_FUNCTION; 114f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor 115f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor public: 116f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor explicit Builder(ContinuousRangeMap &Self) : Self(Self) { } 117f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor 118f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor ~Builder() { 119a119da0761cb6b85f53857eaee50f6ad8c5ea0a0Douglas Gregor std::sort(Self.Rep.begin(), Self.Rep.end(), Compare()); 120f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor } 121f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor 122f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor void insert(const value_type &Val) { 123a119da0761cb6b85f53857eaee50f6ad8c5ea0a0Douglas Gregor Self.Rep.push_back(Val); 124f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor } 125f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor }; 126f33740efdb2d836a96ba97ca3004d46404401439Douglas Gregor friend class Builder; 127f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor}; 128f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor 129f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor} 130f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor 131f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor#endif 132