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_IMLIST_H
  15 #define LLVM_ADT_IMLIST_H
  16
  17 #include "llvm/Support/Allocator.h"
  18 #include "llvm/ADT/FoldingSet.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   ImmutableListImpl* Tail;
  30
  31   ImmutableListImpl(const T& head, ImmutableListImpl* tail = 0)
  32     : Head(head), Tail(tail) {}
  33
  34   friend class ImmutableListFactory<T>;
  35
  36   // Do not implement.
  37   void operator=(const ImmutableListImpl&);
  38   ImmutableListImpl(const ImmutableListImpl&);
  39
  40 public:
  41   const T& getHead() const { return Head; }
  42   ImmutableListImpl* getTail() const { return Tail; }
  43
  44   static inline void Profile(FoldingSetNodeID& ID, const T& H,
  45                              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   typedef T value_type;
  67   typedef ImmutableListFactory<T> Factory;
  68
  69 private:
  70   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(ImmutableListImpl<T>* x) : X(x) {}
  77
  78   ImmutableListImpl<T>* getInternalPointer() const {
  79     return X;
  80   }
  81
  82   class iterator {
  83     ImmutableListImpl<T>* L;
  84   public:
  85     iterator() : L(0) {}
  86     iterator(ImmutableList l) : L(l.getInternalPointer()) {}
  87
  88     iterator& operator++() { L = L->Tail; return *this; }
  89     bool operator==(const iterator& I) const { return L == I.L; }
  90     ImmutableList operator*() const { return L; }
  91   };
  92
  93   /// begin - Returns an iterator referring to the head of the list, or
  94   ///  an iterator denoting the end of the list if the list is empty.
  95   iterator begin() const { return iterator(X); }
  96
  97   /// end - Returns an iterator denoting the end of the list.  This iterator
  98   ///  does not refer to a valid list element.
  99   iterator end() const { return iterator(); }
 100
 101   /// isEmpty - Returns true if the list is empty.
 102   bool isEmpty() const { return !X; }
 103
 104   /// isEqual - Returns true if two lists are equal.  Because all lists created
 105   ///  from the same ImmutableListFactory are uniqued, this has O(1) complexity
 106   ///  because it the contents of the list do not need to be compared.  Note
 107   ///  that you should only compare two lists created from the same
 108   ///  ImmutableListFactory.
 109   bool isEqual(const ImmutableList& L) const { return X == L.X; }
 110
 111   bool operator==(const ImmutableList& L) const { return isEqual(L); }
 112
 113   /// getHead - Returns the head of the list.
 114   const T& getHead() {
 115     assert (!isEmpty() && "Cannot get the head of an empty list.");
 116     return X->getHead();
 117   }
 118
 119   /// getTail - Returns the tail of the list, which is another (possibly empty)
 120   ///  ImmutableList.
 121   ImmutableList getTail() {
 122     return X ? X->getTail() : 0;
 123   }
 124 };
 125
 126 template <typename T>
 127 class ImmutableListFactory {
 128   typedef ImmutableListImpl<T> ListTy;
 129   typedef FoldingSet<ListTy>   CacheTy;
 130
 131   CacheTy Cache;
 132   uintptr_t Allocator;
 133
 134   bool ownsAllocator() const {
 135     return Allocator & 0x1 ? false : true;
 136   }
 137
 138   BumpPtrAllocator& getAllocator() const {
 139     return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
 140   }
 141
 142 public:
 143   ImmutableListFactory()
 144     : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
 145
 146   ImmutableListFactory(BumpPtrAllocator& Alloc)
 147   : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
 148
 149   ~ImmutableListFactory() {
 150     if (ownsAllocator()) delete &getAllocator();
 151   }
 152
 153   ImmutableList<T> Concat(const T& Head, ImmutableList<T> Tail) {
 154     // Profile the new list to see if it already exists in our cache.
 155     FoldingSetNodeID ID;
 156     void* InsertPos;
 157
 158     ListTy* TailImpl = Tail.getInternalPointer();
 159     ListTy::Profile(ID, Head, TailImpl);
 160     ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
 161
 162     if (!L) {
 163       // The list does not exist in our cache.  Create it.
 164       BumpPtrAllocator& A = getAllocator();
 165       L = (ListTy*) A.Allocate<ListTy>();
 166       new (L) ListTy(Head, TailImpl);
 167
 168       // Insert the new list into the cache.
 169       Cache.InsertNode(L, InsertPos);
 170     }
 171
 172     return L;
 173   }
 174
 175   ImmutableList<T> Add(const T& D, ImmutableList<T> L) {
 176     return Concat(D, L);
 177   }
 178
 179   ImmutableList<T> GetEmptyList() const {
 180     return ImmutableList<T>(0);
 181   }
 182
 183   ImmutableList<T> Create(const T& X) {
 184     return Concat(X, GetEmptyList());
 185   }
 186 };
 187
 188 } // end llvm namespace
 189
 190 #endif