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
23namespace llvm {
24
25template <typename T> class ImmutableListFactory;
26
27template <typename T>
28class ImmutableListImpl : public FoldingSetNode {
29  friend class ImmutableListFactory<T>;
30
31  T Head;
32  const ImmutableListImpl* Tail;
33
34  ImmutableListImpl(const T& head, const ImmutableListImpl* tail = nullptr)
35    : Head(head), Tail(tail) {}
36
37public:
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.
63template <typename T>
64class ImmutableList {
65public:
66  using value_type = T;
67  using Factory = ImmutableListFactory<T>;
68
69private:
70  const ImmutableListImpl<T>* X;
71
72public:
73  // This constructor should normally only be called by ImmutableListFactory<T>.
74  // There may be cases, however, when one needs to extract the internal pointer
75  // and reconstruct a list object from that pointer.
76  ImmutableList(const ImmutableListImpl<T>* x = nullptr) : X(x) {}
77
78  const ImmutableListImpl<T>* getInternalPointer() const {
79    return X;
80  }
81
82  class iterator {
83    const ImmutableListImpl<T>* L = nullptr;
84
85  public:
86    iterator() = default;
87    iterator(ImmutableList l) : L(l.getInternalPointer()) {}
88
89    iterator& operator++() { L = L->getTail(); return *this; }
90    bool operator==(const iterator& I) const { return L == I.L; }
91    bool operator!=(const iterator& I) const { return L != I.L; }
92    const value_type& operator*() const { return L->getHead(); }
93
94    ImmutableList getList() const { return L; }
95  };
96
97  /// begin - Returns an iterator referring to the head of the list, or
98  ///  an iterator denoting the end of the list if the list is empty.
99  iterator begin() const { return iterator(X); }
100
101  /// end - Returns an iterator denoting the end of the list.  This iterator
102  ///  does not refer to a valid list element.
103  iterator end() const { return iterator(); }
104
105  /// isEmpty - Returns true if the list is empty.
106  bool isEmpty() const { return !X; }
107
108  bool contains(const T& V) const {
109    for (iterator I = begin(), E = end(); I != E; ++I) {
110      if (*I == V)
111        return true;
112    }
113    return false;
114  }
115
116  /// isEqual - Returns true if two lists are equal.  Because all lists created
117  ///  from the same ImmutableListFactory are uniqued, this has O(1) complexity
118  ///  because it the contents of the list do not need to be compared.  Note
119  ///  that you should only compare two lists created from the same
120  ///  ImmutableListFactory.
121  bool isEqual(const ImmutableList& L) const { return X == L.X; }
122
123  bool operator==(const ImmutableList& L) const { return isEqual(L); }
124
125  /// getHead - Returns the head of the list.
126  const T& getHead() {
127    assert(!isEmpty() && "Cannot get the head of an empty list.");
128    return X->getHead();
129  }
130
131  /// getTail - Returns the tail of the list, which is another (possibly empty)
132  ///  ImmutableList.
133  ImmutableList getTail() {
134    return X ? X->getTail() : nullptr;
135  }
136
137  void Profile(FoldingSetNodeID& ID) const {
138    ID.AddPointer(X);
139  }
140};
141
142template <typename T>
143class ImmutableListFactory {
144  using ListTy = ImmutableListImpl<T>;
145  using CacheTy = FoldingSet<ListTy>;
146
147  CacheTy Cache;
148  uintptr_t Allocator;
149
150  bool ownsAllocator() const {
151    return (Allocator & 0x1) == 0;
152  }
153
154  BumpPtrAllocator& getAllocator() const {
155    return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
156  }
157
158public:
159  ImmutableListFactory()
160    : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
161
162  ImmutableListFactory(BumpPtrAllocator& Alloc)
163  : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
164
165  ~ImmutableListFactory() {
166    if (ownsAllocator()) delete &getAllocator();
167  }
168
169  ImmutableList<T> concat(const T& Head, ImmutableList<T> Tail) {
170    // Profile the new list to see if it already exists in our cache.
171    FoldingSetNodeID ID;
172    void* InsertPos;
173
174    const ListTy* TailImpl = Tail.getInternalPointer();
175    ListTy::Profile(ID, Head, TailImpl);
176    ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
177
178    if (!L) {
179      // The list does not exist in our cache.  Create it.
180      BumpPtrAllocator& A = getAllocator();
181      L = (ListTy*) A.Allocate<ListTy>();
182      new (L) ListTy(Head, TailImpl);
183
184      // Insert the new list into the cache.
185      Cache.InsertNode(L, InsertPos);
186    }
187
188    return L;
189  }
190
191  ImmutableList<T> add(const T& D, ImmutableList<T> L) {
192    return concat(D, L);
193  }
194
195  ImmutableList<T> getEmptyList() const {
196    return ImmutableList<T>(nullptr);
197  }
198
199  ImmutableList<T> create(const T& X) {
200    return Concat(X, getEmptyList());
201  }
202};
203
204//===----------------------------------------------------------------------===//
205// Partially-specialized Traits.
206//===----------------------------------------------------------------------===//
207
208template<typename T> struct DenseMapInfo;
209template<typename T> struct DenseMapInfo<ImmutableList<T>> {
210  static inline ImmutableList<T> getEmptyKey() {
211    return reinterpret_cast<ImmutableListImpl<T>*>(-1);
212  }
213
214  static inline ImmutableList<T> getTombstoneKey() {
215    return reinterpret_cast<ImmutableListImpl<T>*>(-2);
216  }
217
218  static unsigned getHashValue(ImmutableList<T> X) {
219    uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer());
220    return (unsigned((uintptr_t)PtrVal) >> 4) ^
221           (unsigned((uintptr_t)PtrVal) >> 9);
222  }
223
224  static bool isEqual(ImmutableList<T> X1, ImmutableList<T> X2) {
225    return X1 == X2;
226  }
227};
228
229template <typename T> struct isPodLike;
230template <typename T>
231struct isPodLike<ImmutableList<T>> { static const bool value = true; };
232
233} // end namespace llvm
234
235#endif // LLVM_ADT_IMMUTABLELIST_H
236