1 //==--- ImmutableList.h - Immutable (functional) list interface --*- C++ -*-==//
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
7 //===----------------------------------------------------------------------===//
9 // This file defines the ImmutableList class.
11 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_ADT_IMMUTABLELIST_H
14 #define LLVM_ADT_IMMUTABLELIST_H
16 #include "llvm/ADT/FoldingSet.h"
17 #include "llvm/Support/Allocator.h"
24 template <typename T> class ImmutableListFactory;
27 class ImmutableListImpl : public FoldingSetNode {
28 friend class ImmutableListFactory<T>;
31 const ImmutableListImpl* Tail;
33 template <typename ElemT>
34 ImmutableListImpl(ElemT &&head, const ImmutableListImpl *tail = nullptr)
35 : Head(std::forward<ElemT>(head)), Tail(tail) {}
38 ImmutableListImpl(const ImmutableListImpl &) = delete;
39 ImmutableListImpl &operator=(const ImmutableListImpl &) = delete;
41 const T& getHead() const { return Head; }
42 const ImmutableListImpl* getTail() const { return Tail; }
44 static inline void Profile(FoldingSetNodeID& ID, const T& H,
45 const ImmutableListImpl* L){
50 void Profile(FoldingSetNodeID& ID) {
51 Profile(ID, Head, Tail);
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.
67 using Factory = ImmutableListFactory<T>;
69 static_assert(std::is_trivially_destructible<T>::value,
70 "T must be trivially destructible!");
73 const ImmutableListImpl<T>* X;
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) {}
81 const ImmutableListImpl<T>* getInternalPointer() const {
86 const ImmutableListImpl<T>* L = nullptr;
90 iterator(ImmutableList l) : L(l.getInternalPointer()) {}
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 {
100 ImmutableList getList() const { return L; }
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); }
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(); }
111 /// isEmpty - Returns true if the list is empty.
112 bool isEmpty() const { return !X; }
114 bool contains(const T& V) const {
115 for (iterator I = begin(), E = end(); I != E; ++I) {
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; }
129 bool operator==(const ImmutableList& L) const { return isEqual(L); }
131 /// getHead - Returns the head of the list.
132 const T& getHead() const {
133 assert(!isEmpty() && "Cannot get the head of an empty list.");
137 /// getTail - Returns the tail of the list, which is another (possibly empty)
139 ImmutableList getTail() const {
140 return X ? X->getTail() : nullptr;
143 void Profile(FoldingSetNodeID& ID) const {
148 template <typename T>
149 class ImmutableListFactory {
150 using ListTy = ImmutableListImpl<T>;
151 using CacheTy = FoldingSet<ListTy>;
156 bool ownsAllocator() const {
157 return (Allocator & 0x1) == 0;
160 BumpPtrAllocator& getAllocator() const {
161 return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
165 ImmutableListFactory()
166 : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
168 ImmutableListFactory(BumpPtrAllocator& Alloc)
169 : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
171 ~ImmutableListFactory() {
172 if (ownsAllocator()) delete &getAllocator();
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.
181 const ListTy* TailImpl = Tail.getInternalPointer();
182 ListTy::Profile(ID, Head, TailImpl);
183 ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
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);
191 // Insert the new list into the cache.
192 Cache.InsertNode(L, InsertPos);
198 template <typename ElemT>
199 LLVM_NODISCARD ImmutableList<T> add(ElemT &&Data, ImmutableList<T> L) {
200 return concat(std::forward<ElemT>(Data), L);
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);
209 ImmutableList<T> getEmptyList() const {
210 return ImmutableList<T>(nullptr);
213 template <typename ElemT>
214 ImmutableList<T> create(ElemT &&Data) {
215 return concat(std::forward<ElemT>(Data), getEmptyList());
219 //===----------------------------------------------------------------------===//
220 // Partially-specialized Traits.
221 //===----------------------------------------------------------------------===//
223 template<typename T> struct DenseMapInfo;
224 template<typename T> struct DenseMapInfo<ImmutableList<T>> {
225 static inline ImmutableList<T> getEmptyKey() {
226 return reinterpret_cast<ImmutableListImpl<T>*>(-1);
229 static inline ImmutableList<T> getTombstoneKey() {
230 return reinterpret_cast<ImmutableListImpl<T>*>(-2);
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);
239 static bool isEqual(ImmutableList<T> X1, ImmutableList<T> X2) {
244 } // end namespace llvm
246 #endif // LLVM_ADT_IMMUTABLELIST_H