ContinuousRangeMap.h revision 686775deca8b8685eb90801495880e3abdd844c2 
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_CONTINUOUS_RANGE_MAP_H
16#define LLVM_CLANG_SERIALIZATION_CONTINUOUS_RANGE_MAP_H
17
18#include "llvm/ADT/SmallVector.h"
19#include <algorithm>
20#include <utility>
21
22namespace clang {
23
24/// \brief A map from continuous integer ranges to some value, with a very
25/// specialized interface.
26///
27/// CRM maps from integer ranges to values. The ranges are continuous, i.e.
28/// where one ends, the next one begins. So if the map contains the stops I0-3,
29/// the first range is from I0 to I1, the second from I1 to I2, the third from
30/// I2 to I3 and the last from I3 to infinity.
31///
32/// Ranges must be inserted in order. Inserting a new stop I4 into the map will
33/// shrink the fourth range to I3 to I4 and add the new range I4 to inf.
34template <typename Int, typename V, unsigned InitialCapacity>
35class ContinuousRangeMap {
36public:
37  typedef std::pair<const Int, V> value_type;
38  typedef value_type &reference;
39  typedef const value_type &const_reference;
40  typedef value_type *pointer;
41  typedef const value_type *const_pointer;
42
43private:
44  typedef SmallVector<value_type, InitialCapacity> Representation;
45  Representation Rep;
46
47  struct Compare {
48    bool operator ()(const_reference L, Int R) const {
49      return L.first < R;
50    }
51    bool operator ()(Int L, const_reference R) const {
52      return L < R.first;
53    }
54    bool operator ()(Int L, Int R) const {
55      return L < R;
56    }
57    bool operator ()(const_reference L, const_reference R) const {
58      return L.first < R.first;
59    }
60  };
61
62public:
63  void insert(const value_type &Val) {
64    assert((Rep.empty() || Rep.back().first < Val.first) &&
65           "Must insert keys in order.");
66    Rep.push_back(Val);
67  }
68
69  typedef typename Representation::iterator iterator;
70  typedef typename Representation::const_iterator const_iterator;
71
72  iterator begin() { return Rep.begin(); }
73  iterator end() { return Rep.end(); }
74  const_iterator begin() const { return Rep.begin(); }
75  const_iterator end() const { return Rep.end(); }
76
77  iterator find(Int K) {
78    iterator I = std::upper_bound(Rep.begin(), Rep.end(), K, Compare());
79    // I points to the first entry with a key > K, which is the range that
80    // follows the one containing K.
81    if (I == Rep.begin())
82      return Rep.end();
83    --I;
84    return I;
85  }
86  const_iterator find(Int K) const {
87    return const_cast<ContinuousRangeMap*>(this)->find(K);
88  }
89
90  reference back() { return Rep.back(); }
91  const_reference back() const { return Rep.back(); }
92};
93
94}
95
96#endif
97