10b57cec5SDimitry Andric //===- ContinuousRangeMap.h - Map with int range as key ---------*- C++ -*-===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // This file defines the ContinuousRangeMap class, which is a highly 100b57cec5SDimitry Andric // specialized container used by serialization. 110b57cec5SDimitry Andric // 120b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 130b57cec5SDimitry Andric 140b57cec5SDimitry Andric #ifndef LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H 150b57cec5SDimitry Andric #define LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H 160b57cec5SDimitry Andric 170b57cec5SDimitry Andric #include "clang/Basic/LLVM.h" 180b57cec5SDimitry Andric #include "llvm/ADT/STLExtras.h" 190b57cec5SDimitry Andric #include "llvm/ADT/SmallVector.h" 200b57cec5SDimitry Andric #include <algorithm> 210b57cec5SDimitry Andric #include <cassert> 220b57cec5SDimitry Andric #include <utility> 230b57cec5SDimitry Andric 240b57cec5SDimitry Andric namespace clang { 250b57cec5SDimitry Andric 260b57cec5SDimitry Andric /// A map from continuous integer ranges to some value, with a very 270b57cec5SDimitry Andric /// specialized interface. 280b57cec5SDimitry Andric /// 290b57cec5SDimitry Andric /// CRM maps from integer ranges to values. The ranges are continuous, i.e. 300b57cec5SDimitry Andric /// where one ends, the next one begins. So if the map contains the stops I0-3, 310b57cec5SDimitry Andric /// the first range is from I0 to I1, the second from I1 to I2, the third from 320b57cec5SDimitry Andric /// I2 to I3 and the last from I3 to infinity. 330b57cec5SDimitry Andric /// 340b57cec5SDimitry Andric /// Ranges must be inserted in order. Inserting a new stop I4 into the map will 350b57cec5SDimitry Andric /// shrink the fourth range to I3 to I4 and add the new range I4 to inf. 360b57cec5SDimitry Andric template <typename Int, typename V, unsigned InitialCapacity> 370b57cec5SDimitry Andric class ContinuousRangeMap { 380b57cec5SDimitry Andric public: 390b57cec5SDimitry Andric using value_type = std::pair<Int, V>; 400b57cec5SDimitry Andric using reference = value_type &; 410b57cec5SDimitry Andric using const_reference = const value_type &; 420b57cec5SDimitry Andric using pointer = value_type *; 430b57cec5SDimitry Andric using const_pointer = const value_type *; 440b57cec5SDimitry Andric 450b57cec5SDimitry Andric private: 460b57cec5SDimitry Andric using Representation = SmallVector<value_type, InitialCapacity>; 470b57cec5SDimitry Andric 480b57cec5SDimitry Andric Representation Rep; 490b57cec5SDimitry Andric 500b57cec5SDimitry Andric struct Compare { operatorCompare510b57cec5SDimitry Andric bool operator ()(const_reference L, Int R) const { 520b57cec5SDimitry Andric return L.first < R; 530b57cec5SDimitry Andric } operatorCompare540b57cec5SDimitry Andric bool operator ()(Int L, const_reference R) const { 550b57cec5SDimitry Andric return L < R.first; 560b57cec5SDimitry Andric } operatorCompare570b57cec5SDimitry Andric bool operator ()(Int L, Int R) const { 580b57cec5SDimitry Andric return L < R; 590b57cec5SDimitry Andric } operatorCompare600b57cec5SDimitry Andric bool operator ()(const_reference L, const_reference R) const { 610b57cec5SDimitry Andric return L.first < R.first; 620b57cec5SDimitry Andric } 630b57cec5SDimitry Andric }; 640b57cec5SDimitry Andric 650b57cec5SDimitry Andric public: insert(const value_type & Val)660b57cec5SDimitry Andric void insert(const value_type &Val) { 670b57cec5SDimitry Andric if (!Rep.empty() && Rep.back() == Val) 680b57cec5SDimitry Andric return; 690b57cec5SDimitry Andric 700b57cec5SDimitry Andric assert((Rep.empty() || Rep.back().first < Val.first) && 710b57cec5SDimitry Andric "Must insert keys in order."); 720b57cec5SDimitry Andric Rep.push_back(Val); 730b57cec5SDimitry Andric } 740b57cec5SDimitry Andric insertOrReplace(const value_type & Val)750b57cec5SDimitry Andric void insertOrReplace(const value_type &Val) { 760b57cec5SDimitry Andric iterator I = llvm::lower_bound(Rep, Val, Compare()); 770b57cec5SDimitry Andric if (I != Rep.end() && I->first == Val.first) { 780b57cec5SDimitry Andric I->second = Val.second; 790b57cec5SDimitry Andric return; 800b57cec5SDimitry Andric } 810b57cec5SDimitry Andric 820b57cec5SDimitry Andric Rep.insert(I, Val); 830b57cec5SDimitry Andric } 840b57cec5SDimitry Andric 850b57cec5SDimitry Andric using iterator = typename Representation::iterator; 860b57cec5SDimitry Andric using const_iterator = typename Representation::const_iterator; 870b57cec5SDimitry Andric begin()880b57cec5SDimitry Andric iterator begin() { return Rep.begin(); } end()890b57cec5SDimitry Andric iterator end() { return Rep.end(); } begin()900b57cec5SDimitry Andric const_iterator begin() const { return Rep.begin(); } end()910b57cec5SDimitry Andric const_iterator end() const { return Rep.end(); } 920b57cec5SDimitry Andric find(Int K)930b57cec5SDimitry Andric iterator find(Int K) { 940b57cec5SDimitry Andric iterator I = llvm::upper_bound(Rep, K, Compare()); 950b57cec5SDimitry Andric // I points to the first entry with a key > K, which is the range that 960b57cec5SDimitry Andric // follows the one containing K. 970b57cec5SDimitry Andric if (I == Rep.begin()) 980b57cec5SDimitry Andric return Rep.end(); 990b57cec5SDimitry Andric --I; 1000b57cec5SDimitry Andric return I; 1010b57cec5SDimitry Andric } find(Int K)1020b57cec5SDimitry Andric const_iterator find(Int K) const { 1030b57cec5SDimitry Andric return const_cast<ContinuousRangeMap*>(this)->find(K); 1040b57cec5SDimitry Andric } 1050b57cec5SDimitry Andric back()1060b57cec5SDimitry Andric reference back() { return Rep.back(); } back()1070b57cec5SDimitry Andric const_reference back() const { return Rep.back(); } 1080b57cec5SDimitry Andric 1090b57cec5SDimitry Andric /// An object that helps properly build a continuous range map 1100b57cec5SDimitry Andric /// from a set of values. 1110b57cec5SDimitry Andric class Builder { 1120b57cec5SDimitry Andric ContinuousRangeMap &Self; 1130b57cec5SDimitry Andric 1140b57cec5SDimitry Andric public: Builder(ContinuousRangeMap & Self)1150b57cec5SDimitry Andric explicit Builder(ContinuousRangeMap &Self) : Self(Self) {} 1160b57cec5SDimitry Andric Builder(const Builder&) = delete; 1170b57cec5SDimitry Andric Builder &operator=(const Builder&) = delete; 1180b57cec5SDimitry Andric ~Builder()1190b57cec5SDimitry Andric ~Builder() { 1200b57cec5SDimitry Andric llvm::sort(Self.Rep, Compare()); 1210b57cec5SDimitry Andric Self.Rep.erase( 1220b57cec5SDimitry Andric std::unique( 1230b57cec5SDimitry Andric Self.Rep.begin(), Self.Rep.end(), 1240b57cec5SDimitry Andric [](const_reference A, const_reference B) { 1250b57cec5SDimitry Andric // FIXME: we should not allow any duplicate keys, but there are 1260b57cec5SDimitry Andric // a lot of duplicate 0 -> 0 mappings to remove first. 1270b57cec5SDimitry Andric assert((A == B || A.first != B.first) && 1280b57cec5SDimitry Andric "ContinuousRangeMap::Builder given non-unique keys"); 1290b57cec5SDimitry Andric return A == B; 1300b57cec5SDimitry Andric }), 1310b57cec5SDimitry Andric Self.Rep.end()); 1320b57cec5SDimitry Andric } 1330b57cec5SDimitry Andric insert(const value_type & Val)1340b57cec5SDimitry Andric void insert(const value_type &Val) { 1350b57cec5SDimitry Andric Self.Rep.push_back(Val); 1360b57cec5SDimitry Andric } 1370b57cec5SDimitry Andric }; 1380b57cec5SDimitry Andric 1390b57cec5SDimitry Andric friend class Builder; 1400b57cec5SDimitry Andric }; 1410b57cec5SDimitry Andric 142 } // namespace clang 143 144 #endif // LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H 145