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