contrib/llvm/include/llvm/ADT/ImmutableList.h

   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>
  28 class ImmutableListImpl : public FoldingSetNode {
  29   friend class ImmutableListFactory<T>;
  30
  31   T Head;
  32   const ImmutableListImpl* Tail;
  33
  34   ImmutableListImpl(const T& head, const ImmutableListImpl* tail = nullptr)
  35     : Head(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 private:
  70   const ImmutableListImpl<T>* X;
  71
  72 public:
  73   // This constructor should normally only be called by ImmutableListFactory<T>.
  74   // There may be cases, however, when one needs to extract the internal pointer
  75   // and reconstruct a list object from that pointer.
  76   ImmutableList(const ImmutableListImpl<T>* x = nullptr) : X(x) {}
  77
  78   const ImmutableListImpl<T>* getInternalPointer() const {
  79     return X;
  80   }
  81
  82   class iterator {
  83     const ImmutableListImpl<T>* L = nullptr;
  84
  85   public:
  86     iterator() = default;
  87     iterator(ImmutableList l) : L(l.getInternalPointer()) {}
  88
  89     iterator& operator++() { L = L->getTail(); return *this; }
  90     bool operator==(const iterator& I) const { return L == I.L; }
  91     bool operator!=(const iterator& I) const { return L != I.L; }
  92     const value_type& operator*() const { return L->getHead(); }
  93
  94     ImmutableList getList() const { return L; }
  95   };
  96
  97   /// begin - Returns an iterator referring to the head of the list, or
  98   ///  an iterator denoting the end of the list if the list is empty.
  99   iterator begin() const { return iterator(X); }
 100
 101   /// end - Returns an iterator denoting the end of the list.  This iterator
 102   ///  does not refer to a valid list element.
 103   iterator end() const { return iterator(); }
 104
 105   /// isEmpty - Returns true if the list is empty.
 106   bool isEmpty() const { return !X; }
 107
 108   bool contains(const T& V) const {
 109     for (iterator I = begin(), E = end(); I != E; ++I) {
 110       if (*I == V)
 111         return true;
 112     }
 113     return false;
 114   }
 115
 116   /// isEqual - Returns true if two lists are equal.  Because all lists created
 117   ///  from the same ImmutableListFactory are uniqued, this has O(1) complexity
 118   ///  because it the contents of the list do not need to be compared.  Note
 119   ///  that you should only compare two lists created from the same
 120   ///  ImmutableListFactory.
 121   bool isEqual(const ImmutableList& L) const { return X == L.X; }
 122
 123   bool operator==(const ImmutableList& L) const { return isEqual(L); }
 124
 125   /// getHead - Returns the head of the list.
 126   const T& getHead() {
 127     assert(!isEmpty() && "Cannot get the head of an empty list.");
 128     return X->getHead();
 129   }
 130
 131   /// getTail - Returns the tail of the list, which is another (possibly empty)
 132   ///  ImmutableList.
 133   ImmutableList getTail() {
 134     return X ? X->getTail() : nullptr;
 135   }
 136
 137   void Profile(FoldingSetNodeID& ID) const {
 138     ID.AddPointer(X);
 139   }
 140 };
 141
 142 template <typename T>
 143 class ImmutableListFactory {
 144   using ListTy = ImmutableListImpl<T>;
 145   using CacheTy = FoldingSet<ListTy>;
 146
 147   CacheTy Cache;
 148   uintptr_t Allocator;
 149
 150   bool ownsAllocator() const {
 151     return (Allocator & 0x1) == 0;
 152   }
 153
 154   BumpPtrAllocator& getAllocator() const {
 155     return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
 156   }
 157
 158 public:
 159   ImmutableListFactory()
 160     : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
 161
 162   ImmutableListFactory(BumpPtrAllocator& Alloc)
 163   : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
 164
 165   ~ImmutableListFactory() {
 166     if (ownsAllocator()) delete &getAllocator();
 167   }
 168
 169   ImmutableList<T> concat(const T& Head, ImmutableList<T> Tail) {
 170     // Profile the new list to see if it already exists in our cache.
 171     FoldingSetNodeID ID;
 172     void* InsertPos;
 173
 174     const ListTy* TailImpl = Tail.getInternalPointer();
 175     ListTy::Profile(ID, Head, TailImpl);
 176     ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
 177
 178     if (!L) {
 179       // The list does not exist in our cache.  Create it.
 180       BumpPtrAllocator& A = getAllocator();
 181       L = (ListTy*) A.Allocate<ListTy>();
 182       new (L) ListTy(Head, TailImpl);
 183
 184       // Insert the new list into the cache.
 185       Cache.InsertNode(L, InsertPos);
 186     }
 187
 188     return L;
 189   }
 190
 191   ImmutableList<T> add(const T& D, ImmutableList<T> L) {
 192     return concat(D, L);
 193   }
 194
 195   ImmutableList<T> getEmptyList() const {
 196     return ImmutableList<T>(nullptr);
 197   }
 198
 199   ImmutableList<T> create(const T& X) {
 200     return Concat(X, getEmptyList());
 201   }
 202 };
 203
 204 //===----------------------------------------------------------------------===//
 205 // Partially-specialized Traits.
 206 //===----------------------------------------------------------------------===//
 207
 208 template<typename T> struct DenseMapInfo;
 209 template<typename T> struct DenseMapInfo<ImmutableList<T>> {
 210   static inline ImmutableList<T> getEmptyKey() {
 211     return reinterpret_cast<ImmutableListImpl<T>*>(-1);
 212   }
 213
 214   static inline ImmutableList<T> getTombstoneKey() {
 215     return reinterpret_cast<ImmutableListImpl<T>*>(-2);
 216   }
 217
 218   static unsigned getHashValue(ImmutableList<T> X) {
 219     uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer());
 220     return (unsigned((uintptr_t)PtrVal) >> 4) ^
 221            (unsigned((uintptr_t)PtrVal) >> 9);
 222   }
 223
 224   static bool isEqual(ImmutableList<T> X1, ImmutableList<T> X2) {
 225     return X1 == X2;
 226   }
 227 };
 228
 229 template <typename T> struct isPodLike;
 230 template <typename T>
 231 struct isPodLike<ImmutableList<T>> { static const bool value = true; };
 232
 233 } // end namespace llvm
 234
 235 #endif // LLVM_ADT_IMMUTABLELIST_H