]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //==--- ImmutableList.h - Immutable (functional) list interface --*- 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 ImmutableList class. | |
11 | // | |
12 | //===----------------------------------------------------------------------===// | |
13 | ||
970d7e83 LB |
14 | #ifndef LLVM_ADT_IMMUTABLELIST_H |
15 | #define LLVM_ADT_IMMUTABLELIST_H | |
223e47cc | 16 | |
223e47cc | 17 | #include "llvm/ADT/FoldingSet.h" |
970d7e83 | 18 | #include "llvm/Support/Allocator.h" |
223e47cc LB |
19 | #include "llvm/Support/DataTypes.h" |
20 | #include <cassert> | |
21 | ||
22 | namespace llvm { | |
23 | ||
24 | template <typename T> class ImmutableListFactory; | |
25 | ||
26 | template <typename T> | |
27 | class ImmutableListImpl : public FoldingSetNode { | |
28 | T Head; | |
29 | const ImmutableListImpl* Tail; | |
30 | ||
31 | ImmutableListImpl(const T& head, const ImmutableListImpl* tail = 0) | |
32 | : Head(head), Tail(tail) {} | |
33 | ||
34 | friend class ImmutableListFactory<T>; | |
35 | ||
36 | void operator=(const ImmutableListImpl&) LLVM_DELETED_FUNCTION; | |
37 | ImmutableListImpl(const ImmutableListImpl&) LLVM_DELETED_FUNCTION; | |
38 | ||
39 | public: | |
40 | const T& getHead() const { return Head; } | |
41 | const ImmutableListImpl* getTail() const { return Tail; } | |
42 | ||
43 | static inline void Profile(FoldingSetNodeID& ID, const T& H, | |
44 | const ImmutableListImpl* L){ | |
45 | ID.AddPointer(L); | |
46 | ID.Add(H); | |
47 | } | |
48 | ||
49 | void Profile(FoldingSetNodeID& ID) { | |
50 | Profile(ID, Head, Tail); | |
51 | } | |
52 | }; | |
53 | ||
54 | /// ImmutableList - This class represents an immutable (functional) list. | |
55 | /// It is implemented as a smart pointer (wraps ImmutableListImpl), so it | |
56 | /// it is intended to always be copied by value as if it were a pointer. | |
57 | /// This interface matches ImmutableSet and ImmutableMap. ImmutableList | |
58 | /// objects should almost never be created directly, and instead should | |
59 | /// be created by ImmutableListFactory objects that manage the lifetime | |
60 | /// of a group of lists. When the factory object is reclaimed, all lists | |
61 | /// created by that factory are released as well. | |
62 | template <typename T> | |
63 | class ImmutableList { | |
64 | public: | |
65 | typedef T value_type; | |
66 | typedef ImmutableListFactory<T> Factory; | |
67 | ||
68 | private: | |
69 | const ImmutableListImpl<T>* X; | |
70 | ||
71 | public: | |
72 | // This constructor should normally only be called by ImmutableListFactory<T>. | |
73 | // There may be cases, however, when one needs to extract the internal pointer | |
74 | // and reconstruct a list object from that pointer. | |
75 | ImmutableList(const ImmutableListImpl<T>* x = 0) : X(x) {} | |
76 | ||
77 | const ImmutableListImpl<T>* getInternalPointer() const { | |
78 | return X; | |
79 | } | |
80 | ||
81 | class iterator { | |
82 | const ImmutableListImpl<T>* L; | |
83 | public: | |
84 | iterator() : L(0) {} | |
85 | iterator(ImmutableList l) : L(l.getInternalPointer()) {} | |
86 | ||
87 | iterator& operator++() { L = L->getTail(); return *this; } | |
88 | bool operator==(const iterator& I) const { return L == I.L; } | |
89 | bool operator!=(const iterator& I) const { return L != I.L; } | |
90 | const value_type& operator*() const { return L->getHead(); } | |
91 | ImmutableList getList() const { return L; } | |
92 | }; | |
93 | ||
94 | /// begin - Returns an iterator referring to the head of the list, or | |
95 | /// an iterator denoting the end of the list if the list is empty. | |
96 | iterator begin() const { return iterator(X); } | |
97 | ||
98 | /// end - Returns an iterator denoting the end of the list. This iterator | |
99 | /// does not refer to a valid list element. | |
100 | iterator end() const { return iterator(); } | |
101 | ||
102 | /// isEmpty - Returns true if the list is empty. | |
103 | bool isEmpty() const { return !X; } | |
104 | ||
105 | bool contains(const T& V) const { | |
106 | for (iterator I = begin(), E = end(); I != E; ++I) { | |
107 | if (*I == V) | |
108 | return true; | |
109 | } | |
110 | return false; | |
111 | } | |
112 | ||
113 | /// isEqual - Returns true if two lists are equal. Because all lists created | |
114 | /// from the same ImmutableListFactory are uniqued, this has O(1) complexity | |
115 | /// because it the contents of the list do not need to be compared. Note | |
116 | /// that you should only compare two lists created from the same | |
117 | /// ImmutableListFactory. | |
118 | bool isEqual(const ImmutableList& L) const { return X == L.X; } | |
119 | ||
120 | bool operator==(const ImmutableList& L) const { return isEqual(L); } | |
121 | ||
122 | /// getHead - Returns the head of the list. | |
123 | const T& getHead() { | |
124 | assert (!isEmpty() && "Cannot get the head of an empty list."); | |
125 | return X->getHead(); | |
126 | } | |
127 | ||
128 | /// getTail - Returns the tail of the list, which is another (possibly empty) | |
129 | /// ImmutableList. | |
130 | ImmutableList getTail() { | |
131 | return X ? X->getTail() : 0; | |
132 | } | |
133 | ||
134 | void Profile(FoldingSetNodeID& ID) const { | |
135 | ID.AddPointer(X); | |
136 | } | |
137 | }; | |
138 | ||
139 | template <typename T> | |
140 | class ImmutableListFactory { | |
141 | typedef ImmutableListImpl<T> ListTy; | |
142 | typedef FoldingSet<ListTy> CacheTy; | |
143 | ||
144 | CacheTy Cache; | |
145 | uintptr_t Allocator; | |
146 | ||
147 | bool ownsAllocator() const { | |
148 | return Allocator & 0x1 ? false : true; | |
149 | } | |
150 | ||
151 | BumpPtrAllocator& getAllocator() const { | |
152 | return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1); | |
153 | } | |
154 | ||
155 | public: | |
156 | ImmutableListFactory() | |
157 | : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {} | |
158 | ||
159 | ImmutableListFactory(BumpPtrAllocator& Alloc) | |
160 | : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {} | |
161 | ||
162 | ~ImmutableListFactory() { | |
163 | if (ownsAllocator()) delete &getAllocator(); | |
164 | } | |
165 | ||
166 | ImmutableList<T> concat(const T& Head, ImmutableList<T> Tail) { | |
167 | // Profile the new list to see if it already exists in our cache. | |
168 | FoldingSetNodeID ID; | |
169 | void* InsertPos; | |
170 | ||
171 | const ListTy* TailImpl = Tail.getInternalPointer(); | |
172 | ListTy::Profile(ID, Head, TailImpl); | |
173 | ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos); | |
174 | ||
175 | if (!L) { | |
176 | // The list does not exist in our cache. Create it. | |
177 | BumpPtrAllocator& A = getAllocator(); | |
178 | L = (ListTy*) A.Allocate<ListTy>(); | |
179 | new (L) ListTy(Head, TailImpl); | |
180 | ||
181 | // Insert the new list into the cache. | |
182 | Cache.InsertNode(L, InsertPos); | |
183 | } | |
184 | ||
185 | return L; | |
186 | } | |
187 | ||
188 | ImmutableList<T> add(const T& D, ImmutableList<T> L) { | |
189 | return concat(D, L); | |
190 | } | |
191 | ||
192 | ImmutableList<T> getEmptyList() const { | |
193 | return ImmutableList<T>(0); | |
194 | } | |
195 | ||
196 | ImmutableList<T> create(const T& X) { | |
197 | return Concat(X, getEmptyList()); | |
198 | } | |
199 | }; | |
200 | ||
201 | //===----------------------------------------------------------------------===// | |
202 | // Partially-specialized Traits. | |
203 | //===----------------------------------------------------------------------===// | |
204 | ||
205 | template<typename T> struct DenseMapInfo; | |
206 | template<typename T> struct DenseMapInfo<ImmutableList<T> > { | |
207 | static inline ImmutableList<T> getEmptyKey() { | |
208 | return reinterpret_cast<ImmutableListImpl<T>*>(-1); | |
209 | } | |
210 | static inline ImmutableList<T> getTombstoneKey() { | |
211 | return reinterpret_cast<ImmutableListImpl<T>*>(-2); | |
212 | } | |
213 | static unsigned getHashValue(ImmutableList<T> X) { | |
214 | uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer()); | |
215 | return (unsigned((uintptr_t)PtrVal) >> 4) ^ | |
216 | (unsigned((uintptr_t)PtrVal) >> 9); | |
217 | } | |
218 | static bool isEqual(ImmutableList<T> X1, ImmutableList<T> X2) { | |
219 | return X1 == X2; | |
220 | } | |
221 | }; | |
222 | ||
223 | template <typename T> struct isPodLike; | |
224 | template <typename T> | |
225 | struct isPodLike<ImmutableList<T> > { static const bool value = true; }; | |
226 | ||
227 | } // end llvm namespace | |
228 | ||
229 | #endif |