1 //===--- ImmutableIntervalMap.h - Immutable (functional) map ---*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the ImmutableIntervalMap class.
12 //===----------------------------------------------------------------------===//
13 #include "llvm/ADT/ImmutableMap.h"
23 Interval(uint64_t S, uint64_t E) : Start(S), End(E) {}
25 uint64_t getStart() const { return Start; }
26 uint64_t getEnd() const { return End; }
30 struct ImutIntervalInfo {
31 typedef const std::pair<Interval, T> value_type;
32 typedef const value_type &value_type_ref;
33 typedef const Interval key_type;
34 typedef const Interval &key_type_ref;
35 typedef const T data_type;
36 typedef const T &data_type_ref;
38 static key_type_ref KeyOfValue(value_type_ref V) {
42 static data_type_ref DataOfValue(value_type_ref V) {
46 static bool isEqual(key_type_ref L, key_type_ref R) {
47 return L.getStart() == R.getStart() && L.getEnd() == R.getEnd();
50 static bool isDataEqual(data_type_ref L, data_type_ref R) {
51 return ImutContainerInfo<T>::isEqual(L,R);
54 static bool isLess(key_type_ref L, key_type_ref R) {
55 // Assume L and R does not overlap.
56 if (L.getStart() < R.getStart()) {
57 assert(L.getEnd() < R.getStart());
59 } else if (L.getStart() == R.getStart()) {
60 assert(L.getEnd() == R.getEnd());
63 assert(L.getStart() > R.getEnd());
68 static void Profile(FoldingSetNodeID &ID, value_type_ref V) {
69 ID.AddInteger(V.first.getStart());
70 ID.AddInteger(V.first.getEnd());
71 ImutProfileInfo<T>::Profile(ID, V.second);
75 template <typename ImutInfo> class ImutIntervalAVLFactory;
77 template <typename ImutInfo>
78 class ImutIntervalAVLFactory : public ImutAVLFactory<ImutInfo> {
79 typedef ImutAVLTree<ImutInfo> TreeTy;
80 typedef typename ImutInfo::value_type value_type;
81 typedef typename ImutInfo::value_type_ref value_type_ref;
82 typedef typename ImutInfo::key_type key_type;
83 typedef typename ImutInfo::key_type_ref key_type_ref;
84 typedef typename ImutInfo::data_type data_type;
85 typedef typename ImutInfo::data_type_ref data_type_ref;
88 TreeTy *Add(TreeTy* T, value_type_ref V) {
89 T = Add_internal(V,T);
95 TreeTy *Add_internal(value_type_ref V, TreeTy *T) {
96 key_type_ref K = ImutInfo::KeyOfValue(V);
97 T = RemoveAllOverlaps(T, K);
99 return CreateNode(NULL, V, NULL);
101 assert(!T->isMutable());
103 key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
105 if (ImutInfo::isLess(K, KCurrent))
106 return Balance(Add_internal(V, Left(T)), Value(T), Right(T));
108 return Balance(Left(T), Value(T), Add_internal(V, Right(T)));
111 // Remove all overlaps from T.
112 TreeTy *RemoveAllOverlaps(TreeTy *T, key_type_ref K) {
113 TreeTy *OldTree, *NewTree;
118 NewTree = RemoveOverlap(OldTree, K);
119 } while (NewTree != OldTree);
124 // Remove one overlap from T.
125 TreeTy *RemoveOverlap(TreeTy *T, key_type_ref K) {
128 Interval CurrentK = ImutInfo::KeyOfValue(Value(T));
130 // If current key does not overlap the inserted key.
131 if (CurrentK.getStart() > K.getEnd())
132 return RemoveOverlap(Left(T), K);
133 else if (CurrentK.getEnd() < K.getStart())
134 return RemoveOverlap(Right(T), K);
136 // Current key overlaps with the inserted key.
137 // Remove the current key.
139 T = Remove_internal(CurrentK, T);
140 // Add back the unoverlapped part of the current key.
141 if (CurrentK.getStart() < K.getStart()) {
142 if (CurrentK.getEnd() <= K.getEnd()) {
143 Interval NewK(CurrentK.getStart(), K.getStart()-1);
144 return Add_internal(std::make_pair<key_type, data_type>(NewK,
145 ImutInfo::DataOfValue(Value(OldNode))), T);
147 Interval NewK1(CurrentK.getStart(), K.getStart()-1);
148 T = Add_internal(std::make_pair<key_type, data_type>(NewK1,
149 ImutInfo::DataOfValue(Value(OldNode))), T);
151 Interval NewK2(K.getEnd()+1, CurrentK.getEnd());
152 return Add_internal(std::make_pair<key_type, data_type>(NewK2,
153 ImutInfo::DataOfValue(Value(OldNode))), T);
156 if (CurrentK.getEnd() > K.getEnd()) {
157 Interval NewK(K.getEnd()+1, CurrentK.getEnd());
158 return Add_internal(std::make_pair<key_type, data_type>(NewK,
159 ImutInfo::DataOfValue(Value(OldNode))), T);
165 /// ImmutableIntervalMap maps an interval [start, end] to a value. The intervals
166 /// in the map are guaranteed to be disjoint.
167 template <typename ValT>
168 class ImmutableIntervalMap
169 : public ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> > {
171 typedef typename ImutIntervalInfo<ValT>::value_type value_type;
172 typedef typename ImutIntervalInfo<ValT>::value_type_ref value_type_ref;
173 typedef typename ImutIntervalInfo<ValT>::key_type key_type;
174 typedef typename ImutIntervalInfo<ValT>::key_type_ref key_type_ref;
175 typedef typename ImutIntervalInfo<ValT>::data_type data_type;
176 typedef typename ImutIntervalInfo<ValT>::data_type_ref data_type_ref;
177 typedef ImutAVLTree<ImutIntervalInfo<ValT> > TreeTy;
180 explicit ImmutableIntervalMap(TreeTy *R)
181 : ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> >(R) {}
184 ImutIntervalAVLFactory<ImutIntervalInfo<ValT> > F;
187 ImmutableIntervalMap GetEmptyMap() {
188 return ImmutableIntervalMap(F.GetEmptyTree());
191 ImmutableIntervalMap Add(ImmutableIntervalMap Old,
192 key_type_ref K, data_type_ref D) {
193 TreeTy *T = F.Add(Old.Root, std::make_pair<key_type, data_type>(K, D));
194 return ImmutableIntervalMap(F.GetCanonicalTree(T));
197 ImmutableIntervalMap Remove(ImmutableIntervalMap Old, key_type_ref K) {
198 TreeTy *T = F.Remove(Old.Root, K);
199 return ImmutableIntervalMap(F.GetCanonicalTree(T));
204 } // end namespace llvm