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