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