Home | History | Annotate | Download | only in ADT
      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&) LLVM_DELETED_FUNCTION;
     37   ImmutableListImpl(const ImmutableListImpl&) LLVM_DELETED_FUNCTION;
     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
    230