1 //===--- ImmutableSet.h - Immutable (functional) set interface --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Ted Kremenek and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the ImutAVLTree and ImmutableSet classes.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ADT_IMSET_H
15 #define LLVM_ADT_IMSET_H
17 #include "llvm/Support/Allocator.h"
18 #include "llvm/ADT/FoldingSet.h"
23 //===----------------------------------------------------------------------===//
24 // Immutable AVL-Tree Definition.
25 //===----------------------------------------------------------------------===//
27 template <typename ImutInfo> class ImutAVLFactory;
30 template <typename ImutInfo >
31 class ImutAVLTree : public FoldingSetNode {
32 struct ComputeIsEqual;
34 typedef typename ImutInfo::key_type_ref key_type_ref;
35 typedef typename ImutInfo::value_type value_type;
36 typedef typename ImutInfo::value_type_ref value_type_ref;
37 typedef ImutAVLFactory<ImutInfo> Factory;
39 friend class ImutAVLFactory<ImutInfo>;
41 //===----------------------------------------------------===//
43 //===----------------------------------------------------===//
45 ImutAVLTree* getLeft() const { return reinterpret_cast<ImutAVLTree*>(Left); }
47 ImutAVLTree* getRight() const { return Right; }
49 unsigned getHeight() const { return Height; }
51 const value_type& getValue() const { return Value; }
53 ImutAVLTree* find(key_type_ref K) {
54 ImutAVLTree *T = this;
57 key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue());
59 if (ImutInfo::isEqual(K,CurrentKey))
61 else if (ImutInfo::isLess(K,CurrentKey))
70 unsigned size() const {
73 if (const ImutAVLTree* L = getLeft()) n += L->size();
74 if (const ImutAVLTree* R = getRight()) n += R->size();
80 bool isEqual(const ImutAVLTree& RHS) const {
85 bool isNotEqual(const ImutAVLTree& RHS) const { return !isEqual(RHS); }
87 bool contains(const key_type_ref K) { return (bool) find(K); }
89 template <typename Callback>
90 void foreach(Callback& C) {
91 if (ImutAVLTree* L = getLeft()) L->foreach(C);
95 if (ImutAVLTree* R = getRight()) R->foreach(C);
98 unsigned verify() const {
99 unsigned HL = getLeft() ? getLeft()->verify() : 0;
100 unsigned HR = getRight() ? getRight()->verify() : 0;
102 assert (getHeight() == ( HL > HR ? HL : HR ) + 1
103 && "Height calculation wrong.");
105 assert ((HL > HR ? HL-HR : HR-HL) <= 2
106 && "Balancing invariant violated.");
110 || ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()),
111 ImutInfo::KeyOfValue(getValue()))
112 && "Value in left child is not less that current value.");
116 || ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()),
117 ImutInfo::KeyOfValue(getRight()->getValue()))
118 && "Current value is not less that value of right child.");
123 //===----------------------------------------------------===//
125 //===----------------------------------------------------===//
133 //===----------------------------------------------------===//
134 // Profiling or FoldingSet.
135 //===----------------------------------------------------===//
138 void Profile(FoldingSetNodeID& ID, ImutAVLTree* L, ImutAVLTree* R,
139 unsigned H, value_type_ref V) {
143 ImutInfo::Profile(ID,V);
148 void Profile(FoldingSetNodeID& ID) {
149 Profile(ID,getSafeLeft(),getRight(),getHeight(),getValue());
152 //===----------------------------------------------------===//
153 // Internal methods (node manipulation; used by Factory).
154 //===----------------------------------------------------===//
158 ImutAVLTree(ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, unsigned height)
159 : Left(reinterpret_cast<uintptr_t>(l) | 0x1),
160 Right(r), Height(height), Value(v) {}
162 bool isMutable() const { return Left & 0x1; }
164 ImutAVLTree* getSafeLeft() const {
165 return reinterpret_cast<ImutAVLTree*>(Left & ~0x1);
168 // Mutating operations. A tree root can be manipulated as long as
169 // its reference has not "escaped" from internal methods of a
170 // factory object (see below). When a tree pointer is externally
171 // viewable by client code, the internal "mutable bit" is cleared
172 // to mark the tree immutable. Note that a tree that still has
173 // its mutable bit set may have children (subtrees) that are themselves
176 void RemoveMutableFlag() {
177 assert (Left & 0x1 && "Mutable flag already removed.");
181 void setLeft(ImutAVLTree* NewLeft) {
182 assert (isMutable());
183 Left = reinterpret_cast<uintptr_t>(NewLeft) | 0x1;
186 void setRight(ImutAVLTree* NewRight) {
187 assert (isMutable());
191 void setHeight(unsigned h) {
192 assert (isMutable());
197 //===----------------------------------------------------------------------===//
198 // Immutable AVL-Tree Factory class.
199 //===----------------------------------------------------------------------===//
201 template <typename ImutInfo >
202 class ImutAVLFactory {
203 typedef ImutAVLTree<ImutInfo> TreeTy;
204 typedef typename TreeTy::value_type_ref value_type_ref;
205 typedef typename TreeTy::key_type_ref key_type_ref;
207 typedef FoldingSet<TreeTy> CacheTy;
210 BumpPtrAllocator Allocator;
212 //===--------------------------------------------------===//
214 //===--------------------------------------------------===//
219 TreeTy* Add(TreeTy* T, value_type_ref V) {
220 T = Add_internal(V,T);
225 TreeTy* Remove(TreeTy* T, key_type_ref V) {
226 T = Remove_internal(V,T);
231 TreeTy* GetEmptyTree() const { return NULL; }
233 //===--------------------------------------------------===//
234 // A bunch of quick helper functions used for reasoning
235 // about the properties of trees and their children.
236 // These have succinct names so that the balancing code
237 // is as terse (and readable) as possible.
238 //===--------------------------------------------------===//
241 bool isEmpty(TreeTy* T) const {
245 unsigned Height(TreeTy* T) const {
246 return T ? T->getHeight() : 0;
249 TreeTy* Left(TreeTy* T) const {
251 return T->getSafeLeft();
254 TreeTy* Right(TreeTy* T) const {
256 return T->getRight();
259 value_type_ref Value(TreeTy* T) const {
264 unsigned IncrementHeight(TreeTy* L, TreeTy* R) const {
265 unsigned hl = Height(L);
266 unsigned hr = Height(R);
267 return ( hl > hr ? hl : hr ) + 1;
270 //===--------------------------------------------------===//
271 // "CreateNode" is used to generate new tree roots that link
272 // to other trees. The functon may also simply move links
273 // in an existing root if that root is still marked mutable.
274 // This is necessary because otherwise our balancing code
275 // would leak memory as it would create nodes that are
276 // then discarded later before the finished tree is
277 // returned to the caller.
278 //===--------------------------------------------------===//
280 TreeTy* CreateNode(TreeTy* L, value_type_ref V, TreeTy* R) {
282 unsigned height = IncrementHeight(L,R);
284 TreeTy::Profile(ID,L,R,height,V);
287 if (TreeTy* T = Cache.FindNodeOrInsertPos(ID,InsertPos))
290 assert (InsertPos != NULL);
292 // FIXME: more intelligent calculation of alignment.
293 TreeTy* T = (TreeTy*) Allocator.Allocate(sizeof(*T),16);
294 new (T) TreeTy(L,R,V,height);
296 Cache.InsertNode(T,InsertPos);
300 TreeTy* CreateNode(TreeTy* L, TreeTy* OldTree, TreeTy* R) {
301 assert (!isEmpty(OldTree));
303 if (OldTree->isMutable()) {
305 OldTree->setRight(R);
306 OldTree->setHeight(IncrementHeight(L,R));
309 else return CreateNode(L, Value(OldTree), R);
312 /// Balance - Used by Add_internal and Remove_internal to
313 /// balance a newly created tree.
314 TreeTy* Balance(TreeTy* L, value_type_ref V, TreeTy* R) {
316 unsigned hl = Height(L);
317 unsigned hr = Height(R);
320 assert (!isEmpty(L) &&
321 "Left tree cannot be empty to have a height >= 2.");
323 TreeTy* LL = Left(L);
324 TreeTy* LR = Right(L);
326 if (Height(LL) >= Height(LR))
327 return CreateNode(LL, L, CreateNode(LR,V,R));
329 assert (!isEmpty(LR) &&
330 "LR cannot be empty because it has a height >= 1.");
332 TreeTy* LRL = Left(LR);
333 TreeTy* LRR = Right(LR);
335 return CreateNode(CreateNode(LL,L,LRL), LR, CreateNode(LRR,V,R));
337 else if (hr > hl + 2) {
338 assert (!isEmpty(R) &&
339 "Right tree cannot be empty to have a height >= 2.");
341 TreeTy* RL = Left(R);
342 TreeTy* RR = Right(R);
344 if (Height(RR) >= Height(RL))
345 return CreateNode(CreateNode(L,V,RL), R, RR);
347 assert (!isEmpty(RL) &&
348 "RL cannot be empty because it has a height >= 1.");
350 TreeTy* RLL = Left(RL);
351 TreeTy* RLR = Right(RL);
353 return CreateNode(CreateNode(L,V,RLL), RL, CreateNode(RLR,R,RR));
356 return CreateNode(L,V,R);
359 /// Add_internal - Creates a new tree that includes the specified
360 /// data and the data from the original tree. If the original tree
361 /// already contained the data item, the original tree is returned.
362 TreeTy* Add_internal(value_type_ref V, TreeTy* T) {
364 return CreateNode(T, V, T);
366 assert (!T->isMutable());
368 key_type_ref K = ImutInfo::KeyOfValue(V);
369 key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
371 if (ImutInfo::isEqual(K,KCurrent))
372 return CreateNode(Left(T), V, Right(T));
373 else if (ImutInfo::isLess(K,KCurrent))
374 return Balance(Add_internal(V,Left(T)), Value(T), Right(T));
376 return Balance(Left(T), Value(T), Add_internal(V,Right(T)));
379 /// Remove_interal - Creates a new tree that includes all the data
380 /// from the original tree except the specified data. If the
381 /// specified data did not exist in the original tree, the original
382 /// tree is returned.
383 TreeTy* Remove_internal(key_type_ref K, TreeTy* T) {
387 assert (!T->isMutable());
389 key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
391 if (ImutInfo::isEqual(K,KCurrent))
392 return CombineLeftRightTrees(Left(T),Right(T));
393 else if (ImutInfo::isLess(K,KCurrent))
394 return Balance(Remove_internal(K,Left(T)), Value(T), Right(T));
396 return Balance(Left(T), Value(T), Remove_internal(K,Right(T)));
399 TreeTy* CombineLeftRightTrees(TreeTy* L, TreeTy* R) {
400 if (isEmpty(L)) return R;
401 if (isEmpty(R)) return L;
404 TreeTy* NewRight = RemoveMinBinding(R,OldNode);
405 return Balance(L,Value(OldNode),NewRight);
408 TreeTy* RemoveMinBinding(TreeTy* T, TreeTy*& NodeRemoved) {
409 assert (!isEmpty(T));
411 if (isEmpty(Left(T))) {
416 return Balance(RemoveMinBinding(Left(T),NodeRemoved),Value(T),Right(T));
419 /// MarkImmutable - Clears the mutable bits of a root and all of its
421 void MarkImmutable(TreeTy* T) {
422 if (!T || !T->isMutable())
425 T->RemoveMutableFlag();
426 MarkImmutable(Left(T));
427 MarkImmutable(Right(T));
432 //===----------------------------------------------------------------------===//
433 // Trait classes for Profile information.
434 //===----------------------------------------------------------------------===//
436 /// Generic profile template. The default behavior is to invoke the
437 /// profile method of an object. Specializations for primitive integers
438 /// and generic handling of pointers is done below.
439 template <typename T>
440 struct ImutProfileInfo {
441 typedef const T value_type;
442 typedef const T& value_type_ref;
444 static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
449 /// Profile traits for integers.
450 template <typename T>
451 struct ImutProfileInteger {
452 typedef const T value_type;
453 typedef const T& value_type_ref;
455 static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
460 #define PROFILE_INTEGER_INFO(X)\
461 template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
463 PROFILE_INTEGER_INFO(char)
464 PROFILE_INTEGER_INFO(unsigned char)
465 PROFILE_INTEGER_INFO(short)
466 PROFILE_INTEGER_INFO(unsigned short)
467 PROFILE_INTEGER_INFO(unsigned)
468 PROFILE_INTEGER_INFO(signed)
469 PROFILE_INTEGER_INFO(long)
470 PROFILE_INTEGER_INFO(unsigned long)
471 PROFILE_INTEGER_INFO(long long)
472 PROFILE_INTEGER_INFO(unsigned long long)
474 #undef PROFILE_INTEGER_INFO
476 /// Generic profile trait for pointer types. We treat pointers as
477 /// references to unique objects.
478 template <typename T>
479 struct ImutProfileInfo<T*> {
480 typedef const T* value_type;
481 typedef value_type value_type_ref;
483 static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) {
488 //===----------------------------------------------------------------------===//
489 // Trait classes that contain element comparison operators and type
490 // definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap. These
491 // inherit from the profile traits (ImutProfileInfo) to include operations
492 // for element profiling.
493 //===----------------------------------------------------------------------===//
496 /// ImutContainerInfo - Generic definition of comparison operations for
497 /// elements of immutable containers that defaults to using
498 /// std::equal_to<> and std::less<> to perform comparison of elements.
499 template <typename T>
500 struct ImutContainerInfo : public ImutProfileInfo<T> {
501 typedef typename ImutProfileInfo<T>::value_type value_type;
502 typedef typename ImutProfileInfo<T>::value_type_ref value_type_ref;
503 typedef value_type key_type;
504 typedef value_type_ref key_type_ref;
506 static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
508 static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
509 return std::equal_to<key_type>()(LHS,RHS);
512 static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
513 return std::less<key_type>()(LHS,RHS);
517 /// ImutContainerInfo - Specialization for pointer values to treat pointers
518 /// as references to unique objects. Pointers are thus compared by
520 template <typename T>
521 struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {
522 typedef typename ImutProfileInfo<T*>::value_type value_type;
523 typedef typename ImutProfileInfo<T*>::value_type_ref value_type_ref;
524 typedef value_type key_type;
525 typedef value_type_ref key_type_ref;
527 static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
529 static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
533 static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
538 //===----------------------------------------------------------------------===//
540 //===----------------------------------------------------------------------===//
542 template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> >
545 typedef typename ValInfo::value_type value_type;
546 typedef typename ValInfo::value_type_ref value_type_ref;
549 typedef ImutAVLTree<ValInfo> TreeTy;
552 ImmutableSet(TreeTy* R) : Root(R) {}
557 typename TreeTy::Factory F;
562 ImmutableSet GetEmptySet() { return ImmutableSet(F.GetEmptyTree()); }
564 ImmutableSet Add(ImmutableSet Old, value_type_ref V) {
565 return ImmutableSet(F.Add(Old.Root,V));
568 ImmutableSet Remove(ImmutableSet Old, value_type_ref V) {
569 return ImmutableSet(F.Remove(Old.Root,V));
573 Factory(const Factory& RHS) {};
574 void operator=(const Factory& RHS) {};
577 friend class Factory;
579 bool contains(const value_type_ref V) const {
580 return Root ? Root->contains(V) : false;
583 bool operator==(ImmutableSet RHS) const {
584 return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
587 bool operator!=(ImmutableSet RHS) const {
588 return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
591 bool isEmpty() const { return !Root; }
593 template <typename Callback>
594 void foreach(Callback& C) { if (Root) Root->foreach(C); }
596 template <typename Callback>
597 void foreach() { if (Root) { Callback C; Root->foreach(C); } }
599 //===--------------------------------------------------===//
601 //===--------------------------------------------------===//
603 void verify() const { if (Root) Root->verify(); }
604 unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
607 } // end namespace llvm