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