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 /// \file
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   ImmutableListImpl(ElemT &&head, const ImmutableListImpl *tail = nullptr)
36     : Head(std::forward<ElemT>(head)), Tail(tail) {}
37 
38 public:
39   ImmutableListImpl(const ImmutableListImpl &) = delete;
40   ImmutableListImpl &operator=(const ImmutableListImpl &) = delete;
41 
42   const T& getHead() const { return Head; }
43   const ImmutableListImpl* getTail() const { return Tail; }
44 
45   static inline void Profile(FoldingSetNodeID& ID, const T& H,
46                              const ImmutableListImpl* L){
47     ID.AddPointer(L);
48     ID.Add(H);
49   }
50 
51   void Profile(FoldingSetNodeID& ID) {
52     Profile(ID, Head, Tail);
53   }
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   ImmutableList(const ImmutableListImpl<T>* x = nullptr) : X(x) {}
81 
82   const ImmutableListImpl<T>* getInternalPointer() const {
83     return X;
84   }
85 
86   class iterator {
87     const ImmutableListImpl<T>* L = nullptr;
88 
89   public:
90     iterator() = default;
91     iterator(ImmutableList l) : L(l.getInternalPointer()) {}
92 
93     iterator& operator++() { L = L->getTail(); return *this; }
94     bool operator==(const iterator& I) const { return L == I.L; }
95     bool operator!=(const iterator& I) const { return L != I.L; }
96     const value_type& operator*() const { return L->getHead(); }
97     const typename std::remove_reference<value_type>::type* operator->() const {
98       return &L->getHead();
99     }
100 
101     ImmutableList getList() const { return L; }
102   };
103 
104   /// begin - Returns an iterator referring to the head of the list, or
105   ///  an iterator denoting the end of the list if the list is empty.
106   iterator begin() const { return iterator(X); }
107 
108   /// end - Returns an iterator denoting the end of the list.  This iterator
109   ///  does not refer to a valid list element.
110   iterator end() const { return iterator(); }
111 
112   /// isEmpty - Returns true if the list is empty.
113   bool isEmpty() const { return !X; }
114 
115   bool contains(const T& V) const {
116     for (iterator I = begin(), E = end(); I != E; ++I) {
117       if (*I == V)
118         return true;
119     }
120     return false;
121   }
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   ///  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   bool isEqual(const ImmutableList& L) const { return X == L.X; }
129 
130   bool operator==(const ImmutableList& L) const { return isEqual(L); }
131 
132   /// getHead - Returns the head of the list.
133   const T& getHead() const {
134     assert(!isEmpty() && "Cannot get the head of an empty list.");
135     return X->getHead();
136   }
137 
138   /// getTail - Returns the tail of the list, which is another (possibly empty)
139   ///  ImmutableList.
140   ImmutableList getTail() const {
141     return X ? X->getTail() : nullptr;
142   }
143 
144   void Profile(FoldingSetNodeID& ID) const {
145     ID.AddPointer(X);
146   }
147 };
148 
149 template <typename T>
150 class ImmutableListFactory {
151   using ListTy = ImmutableListImpl<T>;
152   using CacheTy = FoldingSet<ListTy>;
153 
154   CacheTy Cache;
155   uintptr_t Allocator;
156 
157   bool ownsAllocator() const {
158     return (Allocator & 0x1) == 0;
159   }
160 
161   BumpPtrAllocator& getAllocator() const {
162     return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
163   }
164 
165 public:
166   ImmutableListFactory()
167     : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
168 
169   ImmutableListFactory(BumpPtrAllocator& Alloc)
170   : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
171 
172   ~ImmutableListFactory() {
173     if (ownsAllocator()) delete &getAllocator();
174   }
175 
176   template <typename ElemT>
177   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     FoldingSetNodeID ID;
180     void* InsertPos;
181 
182     const ListTy* TailImpl = Tail.getInternalPointer();
183     ListTy::Profile(ID, Head, TailImpl);
184     ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
185 
186     if (!L) {
187       // The list does not exist in our cache.  Create it.
188       BumpPtrAllocator& A = getAllocator();
189       L = (ListTy*) A.Allocate<ListTy>();
190       new (L) ListTy(std::forward<ElemT>(Head), TailImpl);
191 
192       // Insert the new list into the cache.
193       Cache.InsertNode(L, InsertPos);
194     }
195 
196     return L;
197   }
198 
199   template <typename ElemT>
200   LLVM_NODISCARD ImmutableList<T> add(ElemT &&Data, ImmutableList<T> L) {
201     return concat(std::forward<ElemT>(Data), L);
202   }
203 
204   template <typename ...CtorArgs>
205   LLVM_NODISCARD ImmutableList<T> emplace(ImmutableList<T> Tail,
206                                           CtorArgs &&...Args) {
207     return concat(T(std::forward<CtorArgs>(Args)...), Tail);
208   }
209 
210   ImmutableList<T> getEmptyList() const {
211     return ImmutableList<T>(nullptr);
212   }
213 
214   template <typename ElemT>
215   ImmutableList<T> create(ElemT &&Data) {
216     return concat(std::forward<ElemT>(Data), getEmptyList());
217   }
218 };
219 
220 //===----------------------------------------------------------------------===//
221 // Partially-specialized Traits.
222 //===----------------------------------------------------------------------===//
223 
224 template <typename T> struct DenseMapInfo<ImmutableList<T>, void> {
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