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 "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)
Head(head)32     : Head(head), Tail(tail) {}
33 
34   friend class ImmutableListFactory<T>;
35 
36   void operator=(const ImmutableListImpl&) = delete;
37   ImmutableListImpl(const ImmutableListImpl&) = delete;
38 
39 public:
getHead()40   const T& getHead() const { return Head; }
getTail()41   const ImmutableListImpl* getTail() const { return Tail; }
42 
Profile(FoldingSetNodeID & ID,const T & H,const ImmutableListImpl * L)43   static inline void Profile(FoldingSetNodeID& ID, const T& H,
44                              const ImmutableListImpl* L){
45     ID.AddPointer(L);
46     ID.Add(H);
47   }
48 
Profile(FoldingSetNodeID & ID)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.
X(x)75   ImmutableList(const ImmutableListImpl<T>* x = 0) : X(x) {}
76 
getInternalPointer()77   const ImmutableListImpl<T>* getInternalPointer() const {
78     return X;
79   }
80 
81   class iterator {
82     const ImmutableListImpl<T>* L;
83   public:
iterator()84     iterator() : L(0) {}
iterator(ImmutableList l)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(); }
getList()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.
begin()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.
end()100   iterator end() const { return iterator(); }
101 
102   /// isEmpty - Returns true if the list is empty.
isEmpty()103   bool isEmpty() const { return !X; }
104 
contains(const T & V)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.
isEqual(const ImmutableList & L)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.
getHead()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.
getTail()130   ImmutableList getTail() {
131     return X ? X->getTail() : 0;
132   }
133 
Profile(FoldingSetNodeID & ID)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 
ownsAllocator()147   bool ownsAllocator() const {
148     return Allocator & 0x1 ? false : true;
149   }
150 
getAllocator()151   BumpPtrAllocator& getAllocator() const {
152     return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
153   }
154 
155 public:
ImmutableListFactory()156   ImmutableListFactory()
157     : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
158 
ImmutableListFactory(BumpPtrAllocator & Alloc)159   ImmutableListFactory(BumpPtrAllocator& Alloc)
160   : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
161 
~ImmutableListFactory()162   ~ImmutableListFactory() {
163     if (ownsAllocator()) delete &getAllocator();
164   }
165 
concat(const T & Head,ImmutableList<T> Tail)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 
add(const T & D,ImmutableList<T> L)188   ImmutableList<T> add(const T& D, ImmutableList<T> L) {
189     return concat(D, L);
190   }
191 
getEmptyList()192   ImmutableList<T> getEmptyList() const {
193     return ImmutableList<T>(0);
194   }
195 
create(const T & X)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
230