ImmutableList.h revision 445723bfb0d3c4cb7ecebb60710c669cf3dd2c8d
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->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 ImmutableList operator*() 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 /// isEqual - Returns true if two lists are equal. Because all lists created 106 /// from the same ImmutableListFactory are uniqued, this has O(1) complexity 107 /// because it the contents of the list do not need to be compared. Note 108 /// that you should only compare two lists created from the same 109 /// ImmutableListFactory. 110 bool isEqual(const ImmutableList& L) const { return X == L.X; } 111 112 bool operator==(const ImmutableList& L) const { return isEqual(L); } 113 114 /// getHead - Returns the head of the list. 115 const T& getHead() { 116 assert (!isEmpty() && "Cannot get the head of an empty list."); 117 return X->getHead(); 118 } 119 120 /// getTail - Returns the tail of the list, which is another (possibly empty) 121 /// ImmutableList. 122 ImmutableList getTail() { 123 return X ? X->getTail() : 0; 124 } 125}; 126 127template <typename T> 128class ImmutableListFactory { 129 typedef ImmutableListImpl<T> ListTy; 130 typedef FoldingSet<ListTy> CacheTy; 131 132 CacheTy Cache; 133 uintptr_t Allocator; 134 135 bool ownsAllocator() const { 136 return Allocator & 0x1 ? false : true; 137 } 138 139 BumpPtrAllocator& getAllocator() const { 140 return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1); 141 } 142 143public: 144 ImmutableListFactory() 145 : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {} 146 147 ImmutableListFactory(BumpPtrAllocator& Alloc) 148 : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {} 149 150 ~ImmutableListFactory() { 151 if (ownsAllocator()) delete &getAllocator(); 152 } 153 154 ImmutableList<T> Concat(const T& Head, ImmutableList<T> Tail) { 155 // Profile the new list to see if it already exists in our cache. 156 FoldingSetNodeID ID; 157 void* InsertPos; 158 159 ListTy* TailImpl = Tail.getInternalPointer(); 160 ListTy::Profile(ID, Head, TailImpl); 161 ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos); 162 163 if (!L) { 164 // The list does not exist in our cache. Create it. 165 BumpPtrAllocator& A = getAllocator(); 166 L = (ListTy*) A.Allocate<ListTy>(); 167 new (L) ListTy(Head, TailImpl); 168 169 // Insert the new list into the cache. 170 Cache.InsertNode(L, InsertPos); 171 } 172 173 return L; 174 } 175 176 ImmutableList<T> Add(const T& D, ImmutableList<T> L) { 177 return Concat(D, L); 178 } 179 180 ImmutableList<T> GetEmptyList() const { 181 return ImmutableList<T>(0); 182 } 183 184 ImmutableList<T> Create(const T& X) { 185 return Concat(X, GetEmptyList()); 186 } 187}; 188 189} // end llvm namespace 190 191#endif 192