1327952Sdim//===- ContinuousRangeMap.h - Map with int range as key ---------*- C++ -*-===// 2226586Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6226586Sdim// 7226586Sdim//===----------------------------------------------------------------------===// 8226586Sdim// 9226586Sdim// This file defines the ContinuousRangeMap class, which is a highly 10226586Sdim// specialized container used by serialization. 11226586Sdim// 12226586Sdim//===----------------------------------------------------------------------===// 13226586Sdim 14280031Sdim#ifndef LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H 15280031Sdim#define LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H 16226586Sdim 17249423Sdim#include "clang/Basic/LLVM.h" 18341825Sdim#include "llvm/ADT/STLExtras.h" 19226586Sdim#include "llvm/ADT/SmallVector.h" 20226586Sdim#include <algorithm> 21327952Sdim#include <cassert> 22226586Sdim#include <utility> 23226586Sdim 24226586Sdimnamespace clang { 25226586Sdim 26341825Sdim/// A map from continuous integer ranges to some value, with a very 27226586Sdim/// specialized interface. 28226586Sdim/// 29226586Sdim/// CRM maps from integer ranges to values. The ranges are continuous, i.e. 30226586Sdim/// where one ends, the next one begins. So if the map contains the stops I0-3, 31226586Sdim/// the first range is from I0 to I1, the second from I1 to I2, the third from 32226586Sdim/// I2 to I3 and the last from I3 to infinity. 33226586Sdim/// 34226586Sdim/// Ranges must be inserted in order. Inserting a new stop I4 into the map will 35226586Sdim/// shrink the fourth range to I3 to I4 and add the new range I4 to inf. 36226586Sdimtemplate <typename Int, typename V, unsigned InitialCapacity> 37226586Sdimclass ContinuousRangeMap { 38226586Sdimpublic: 39327952Sdim using value_type = std::pair<Int, V>; 40327952Sdim using reference = value_type &; 41327952Sdim using const_reference = const value_type &; 42327952Sdim using pointer = value_type *; 43327952Sdim using const_pointer = const value_type *; 44226586Sdim 45226586Sdimprivate: 46327952Sdim using Representation = SmallVector<value_type, InitialCapacity>; 47327952Sdim 48226586Sdim Representation Rep; 49226586Sdim 50226586Sdim struct Compare { 51226586Sdim bool operator ()(const_reference L, Int R) const { 52226586Sdim return L.first < R; 53226586Sdim } 54226586Sdim bool operator ()(Int L, const_reference R) const { 55226586Sdim return L < R.first; 56226586Sdim } 57327952Sdim bool operator ()(Int L, Int R) const { 58226586Sdim return L < R; 59226586Sdim } 60226586Sdim bool operator ()(const_reference L, const_reference R) const { 61226586Sdim return L.first < R.first; 62226586Sdim } 63226586Sdim }; 64226586Sdim 65226586Sdimpublic: 66226586Sdim void insert(const value_type &Val) { 67226586Sdim if (!Rep.empty() && Rep.back() == Val) 68226586Sdim return; 69226586Sdim 70226586Sdim assert((Rep.empty() || Rep.back().first < Val.first) && 71226586Sdim "Must insert keys in order."); 72226586Sdim Rep.push_back(Val); 73226586Sdim } 74341825Sdim 75234353Sdim void insertOrReplace(const value_type &Val) { 76353358Sdim iterator I = llvm::lower_bound(Rep, Val, Compare()); 77234353Sdim if (I != Rep.end() && I->first == Val.first) { 78234353Sdim I->second = Val.second; 79234353Sdim return; 80234353Sdim } 81341825Sdim 82234353Sdim Rep.insert(I, Val); 83234353Sdim } 84226586Sdim 85327952Sdim using iterator = typename Representation::iterator; 86327952Sdim using const_iterator = typename Representation::const_iterator; 87226586Sdim 88226586Sdim iterator begin() { return Rep.begin(); } 89226586Sdim iterator end() { return Rep.end(); } 90226586Sdim const_iterator begin() const { return Rep.begin(); } 91226586Sdim const_iterator end() const { return Rep.end(); } 92226586Sdim 93226586Sdim iterator find(Int K) { 94353358Sdim iterator I = llvm::upper_bound(Rep, K, Compare()); 95226586Sdim // I points to the first entry with a key > K, which is the range that 96226586Sdim // follows the one containing K. 97226586Sdim if (I == Rep.begin()) 98226586Sdim return Rep.end(); 99226586Sdim --I; 100226586Sdim return I; 101226586Sdim } 102226586Sdim const_iterator find(Int K) const { 103226586Sdim return const_cast<ContinuousRangeMap*>(this)->find(K); 104226586Sdim } 105226586Sdim 106226586Sdim reference back() { return Rep.back(); } 107226586Sdim const_reference back() const { return Rep.back(); } 108341825Sdim 109341825Sdim /// An object that helps properly build a continuous range map 110226586Sdim /// from a set of values. 111226586Sdim class Builder { 112226586Sdim ContinuousRangeMap &Self; 113327952Sdim 114327952Sdim public: 115327952Sdim explicit Builder(ContinuousRangeMap &Self) : Self(Self) {} 116288943Sdim Builder(const Builder&) = delete; 117288943Sdim Builder &operator=(const Builder&) = delete; 118341825Sdim 119226586Sdim ~Builder() { 120344779Sdim llvm::sort(Self.Rep, Compare()); 121360784Sdim Self.Rep.erase( 122360784Sdim std::unique( 123360784Sdim Self.Rep.begin(), Self.Rep.end(), 124360784Sdim [](const_reference A, const_reference B) { 125360784Sdim // FIXME: we should not allow any duplicate keys, but there are 126360784Sdim // a lot of duplicate 0 -> 0 mappings to remove first. 127360784Sdim assert((A == B || A.first != B.first) && 128360784Sdim "ContinuousRangeMap::Builder given non-unique keys"); 129360784Sdim return A == B; 130360784Sdim }), 131360784Sdim Self.Rep.end()); 132226586Sdim } 133341825Sdim 134226586Sdim void insert(const value_type &Val) { 135226586Sdim Self.Rep.push_back(Val); 136226586Sdim } 137226586Sdim }; 138327952Sdim 139226586Sdim friend class Builder; 140226586Sdim}; 141226586Sdim 142327952Sdim} // namespace clang 143226586Sdim 144327952Sdim#endif // LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H 145