include/llvm/ADT/ImmutableList.h

   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)
  35     : Head(std::forward<ElemT>(head)), Tail(tail) {}
  36
  37 public:
  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.
  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.
  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
 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
 156   bool ownsAllocator() const {
 157     return (Allocator & 0x1) == 0;
 158   }
 159
 160   BumpPtrAllocator& getAllocator() const {
 161     return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
 162   }
 163
 164 public:
 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
 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