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
22namespace llvm {
23
24template <typename T> class ImmutableListFactory;
25
26template <typename T>
27class 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
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
69  static_assert(std::is_trivially_destructible<T>::value,
70                "T must be trivially destructible!");
71
72private:
73  const ImmutableListImpl<T>* X;
74
75public:
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
148template <typename T>
149class 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
164public:
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
223template<typename T> struct DenseMapInfo;
224template<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