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