ImmutableList.h revision 30389141c9c7270b4733ec0b9bc5ad58541f39da
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 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 40public: 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. 63template <typename T> 64class ImmutableList { 65public: 66 typedef T value_type; 67 typedef ImmutableListFactory<T> Factory; 68 69private: 70 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(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 126template <typename T> 127class 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 142public: 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 191