LLVM  8.0.0svn
ImmutableList.h
Go to the documentation of this file.
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 
23 namespace llvm {
24 
25 template <typename T> class ImmutableListFactory;
26 
27 template <typename T>
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;
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 
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>
66 public:
67  using value_type = 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 
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.
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:
167  : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
168 
170  : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
171 
173  if (ownsAllocator()) delete &getAllocator();
174  }
175 
176  template <typename ElemT>
178  // Profile the new list to see if it already exists in our cache.
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>
201  return concat(std::forward<ElemT>(Data), L);
202  }
203 
204  template <typename ...CtorArgs>
206  CtorArgs &&...Args) {
207  return concat(T(std::forward<CtorArgs>(Args)...), Tail);
208  }
209 
211  return ImmutableList<T>(nullptr);
212  }
213 
214  template <typename ElemT>
216  return concat(std::forward<ElemT>(Data), getEmptyList());
217  }
218 };
219 
220 //===----------------------------------------------------------------------===//
221 // Partially-specialized Traits.
222 //===----------------------------------------------------------------------===//
223 
224 template<typename T> struct DenseMapInfo;
225 template<typename T> struct DenseMapInfo<ImmutableList<T>> {
226  static inline ImmutableList<T> getEmptyKey() {
227  return reinterpret_cast<ImmutableListImpl<T>*>(-1);
228  }
229 
231  return reinterpret_cast<ImmutableListImpl<T>*>(-2);
232  }
233 
234  static unsigned getHashValue(ImmutableList<T> X) {
235  uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer());
236  return (unsigned((uintptr_t)PtrVal) >> 4) ^
237  (unsigned((uintptr_t)PtrVal) >> 9);
238  }
239 
241  return X1 == X2;
242  }
243 };
244 
245 template <typename T> struct isPodLike;
246 template <typename T>
247 struct isPodLike<ImmutableList<T>> { static const bool value = true; };
248 
249 } // end namespace llvm
250 
251 #endif // LLVM_ADT_IMMUTABLELIST_H
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:803
void AddPointer(const void *Ptr)
Add* - Add various data types to Bit data.
Definition: FoldingSet.cpp:52
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:259
void Profile(FoldingSetNodeID &ID)
Definition: ImmutableList.h:51
bool operator==(const ImmutableList &L) const
ImmutableList< T > create(ElemT &&Data)
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:250
LLVM_NODISCARD ImmutableList< T > add(ElemT &&Data, ImmutableList< T > L)
iterator end() const
end - Returns an iterator denoting the end of the list.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
static ImmutableList< T > getEmptyKey()
ImmutableListImpl & operator=(const ImmutableListImpl &)=delete
const T & getHead() const
Definition: ImmutableList.h:42
const ImmutableListImpl * getTail() const
Definition: ImmutableList.h:43
static bool isEqual(ImmutableList< T > X1, ImmutableList< T > X2)
bool operator!=(const iterator &I) const
Definition: ImmutableList.h:95
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:129
Definition: BitVector.h:938
LLVM_NODISCARD ImmutableList< T > emplace(ImmutableList< T > Tail, CtorArgs &&...Args)
ImmutableList getList() const
const std::remove_reference< value_type >::type * operator->() const
Definition: ImmutableList.h:97
ImmutableList< T > getEmptyList() const
static ImmutableList< T > getTombstoneKey()
ImmutableList(const ImmutableListImpl< T > *x=nullptr)
Definition: ImmutableList.h:80
static bool isEqual(const Function &Caller, const Function &Callee)
bool isEmpty() const
isEmpty - Returns true if the list is empty.
#define T
void Profile(FoldingSetNodeID &ID) const
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:306
static void Profile(FoldingSetNodeID &ID, const T &H, const ImmutableListImpl *L)
Definition: ImmutableList.h:45
ImmutableList - This class represents an immutable (functional) list.
Definition: ImmutableList.h:65
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:141
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, size_t Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:215
#define H(x, y, z)
Definition: MD5.cpp:57
ImmutableListFactory(BumpPtrAllocator &Alloc)
const T & getHead() const
getHead - Returns the head of the list.
void Add(const T &x)
Definition: FoldingSet.h:330
Basic Register Allocator
isPodLike - This is a type trait that is used to determine whether a given type can be copied around ...
Definition: ArrayRef.h:530
const value_type & operator*() const
Definition: ImmutableList.h:96
bool operator==(const iterator &I) const
Definition: ImmutableList.h:94
bool isEqual(const ImmutableList &L) const
isEqual - Returns true if two lists are equal.
const ImmutableListImpl< T > * getInternalPointer() const
Definition: ImmutableList.h:82
iterator begin() const
begin - Returns an iterator referring to the head of the list, or an iterator denoting the end of the...
LLVM_NODISCARD ImmutableList< T > concat(ElemT &&Head, ImmutableList< T > Tail)
static unsigned getHashValue(ImmutableList< T > X)
Node - This class is used to maintain the singly linked bucket list in a folding set.
Definition: FoldingSet.h:136
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ImmutableList getTail() const
getTail - Returns the tail of the list, which is another (possibly empty) ImmutableList.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
bool contains(const T &V) const