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 22 namespace llvm { 23 24 template <typename T> class ImmutableListFactory; 25 26 template <typename T> 27 class 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) Head(std::forward<ElemT> (head))35 : Head(std::forward<ElemT>(head)), Tail(tail) {} 36 37 public: 38 ImmutableListImpl(const ImmutableListImpl &) = delete; 39 ImmutableListImpl &operator=(const ImmutableListImpl &) = delete; 40 getHead()41 const T& getHead() const { return Head; } getTail()42 const ImmutableListImpl* getTail() const { return Tail; } 43 Profile(FoldingSetNodeID & ID,const T & H,const ImmutableListImpl * L)44 static inline void Profile(FoldingSetNodeID& ID, const T& H, 45 const ImmutableListImpl* L){ 46 ID.AddPointer(L); 47 ID.Add(H); 48 } 49 Profile(FoldingSetNodeID & ID)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. 63 template <typename T> 64 class ImmutableList { 65 public: 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 72 private: 73 const ImmutableListImpl<T>* X; 74 75 public: 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. X(x)79 ImmutableList(const ImmutableListImpl<T>* x = nullptr) : X(x) {} 80 getInternalPointer()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; iterator(ImmutableList l)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 getList()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. begin()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. end()109 iterator end() const { return iterator(); } 110 111 /// isEmpty - Returns true if the list is empty. isEmpty()112 bool isEmpty() const { return !X; } 113 contains(const T & V)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. isEqual(const ImmutableList & L)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. getHead()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. getTail()139 ImmutableList getTail() const { 140 return X ? X->getTail() : nullptr; 141 } 142 Profile(FoldingSetNodeID & ID)143 void Profile(FoldingSetNodeID& ID) const { 144 ID.AddPointer(X); 145 } 146 }; 147 148 template <typename T> 149 class ImmutableListFactory { 150 using ListTy = ImmutableListImpl<T>; 151 using CacheTy = FoldingSet<ListTy>; 152 153 CacheTy Cache; 154 uintptr_t Allocator; 155 ownsAllocator()156 bool ownsAllocator() const { 157 return (Allocator & 0x1) == 0; 158 } 159 getAllocator()160 BumpPtrAllocator& getAllocator() const { 161 return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1); 162 } 163 164 public: ImmutableListFactory()165 ImmutableListFactory() 166 : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {} 167 ImmutableListFactory(BumpPtrAllocator & Alloc)168 ImmutableListFactory(BumpPtrAllocator& Alloc) 169 : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {} 170 ~ImmutableListFactory()171 ~ImmutableListFactory() { 172 if (ownsAllocator()) delete &getAllocator(); 173 } 174 175 template <typename ElemT> concat(ElemT && Head,ImmutableList<T> Tail)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> add(ElemT && Data,ImmutableList<T> L)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> emplace(ImmutableList<T> Tail,CtorArgs &&...Args)204 LLVM_NODISCARD ImmutableList<T> emplace(ImmutableList<T> Tail, 205 CtorArgs &&...Args) { 206 return concat(T(std::forward<CtorArgs>(Args)...), Tail); 207 } 208 getEmptyList()209 ImmutableList<T> getEmptyList() const { 210 return ImmutableList<T>(nullptr); 211 } 212 213 template <typename ElemT> create(ElemT && Data)214 ImmutableList<T> create(ElemT &&Data) { 215 return concat(std::forward<ElemT>(Data), getEmptyList()); 216 } 217 }; 218 219 //===----------------------------------------------------------------------===// 220 // Partially-specialized Traits. 221 //===----------------------------------------------------------------------===// 222 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); 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