Clang Project

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