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