1193323Sed//==--- ImmutableList.h - Immutable (functional) list interface --*- C++ -*-==// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the ImmutableList class. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14249423Sdim#ifndef LLVM_ADT_IMMUTABLELIST_H 15249423Sdim#define LLVM_ADT_IMMUTABLELIST_H 16193323Sed 17249423Sdim#include "llvm/ADT/FoldingSet.h" 18193323Sed#include "llvm/Support/Allocator.h" 19218893Sdim#include "llvm/Support/DataTypes.h" 20193323Sed#include <cassert> 21193323Sed 22193323Sednamespace llvm { 23193323Sed 24193323Sedtemplate <typename T> class ImmutableListFactory; 25193323Sed 26193323Sedtemplate <typename T> 27193323Sedclass ImmutableListImpl : public FoldingSetNode { 28193323Sed T Head; 29193323Sed const ImmutableListImpl* Tail; 30193323Sed 31193323Sed ImmutableListImpl(const T& head, const ImmutableListImpl* tail = 0) 32193323Sed : Head(head), Tail(tail) {} 33193323Sed 34193323Sed friend class ImmutableListFactory<T>; 35193323Sed 36243830Sdim void operator=(const ImmutableListImpl&) LLVM_DELETED_FUNCTION; 37243830Sdim ImmutableListImpl(const ImmutableListImpl&) LLVM_DELETED_FUNCTION; 38193323Sed 39193323Sedpublic: 40193323Sed const T& getHead() const { return Head; } 41193323Sed const ImmutableListImpl* getTail() const { return Tail; } 42193323Sed 43193323Sed static inline void Profile(FoldingSetNodeID& ID, const T& H, 44193323Sed const ImmutableListImpl* L){ 45193323Sed ID.AddPointer(L); 46193323Sed ID.Add(H); 47193323Sed } 48193323Sed 49193323Sed void Profile(FoldingSetNodeID& ID) { 50193323Sed Profile(ID, Head, Tail); 51193323Sed } 52193323Sed}; 53193323Sed 54193323Sed/// ImmutableList - This class represents an immutable (functional) list. 55193323Sed/// It is implemented as a smart pointer (wraps ImmutableListImpl), so it 56193323Sed/// it is intended to always be copied by value as if it were a pointer. 57193323Sed/// This interface matches ImmutableSet and ImmutableMap. ImmutableList 58193323Sed/// objects should almost never be created directly, and instead should 59193323Sed/// be created by ImmutableListFactory objects that manage the lifetime 60193323Sed/// of a group of lists. When the factory object is reclaimed, all lists 61193323Sed/// created by that factory are released as well. 62193323Sedtemplate <typename T> 63193323Sedclass ImmutableList { 64193323Sedpublic: 65193323Sed typedef T value_type; 66193323Sed typedef ImmutableListFactory<T> Factory; 67193323Sed 68193323Sedprivate: 69193323Sed const ImmutableListImpl<T>* X; 70193323Sed 71193323Sedpublic: 72193323Sed // This constructor should normally only be called by ImmutableListFactory<T>. 73193323Sed // There may be cases, however, when one needs to extract the internal pointer 74193323Sed // and reconstruct a list object from that pointer. 75193323Sed ImmutableList(const ImmutableListImpl<T>* x = 0) : X(x) {} 76193323Sed 77193323Sed const ImmutableListImpl<T>* getInternalPointer() const { 78193323Sed return X; 79193323Sed } 80193323Sed 81193323Sed class iterator { 82193323Sed const ImmutableListImpl<T>* L; 83193323Sed public: 84193323Sed iterator() : L(0) {} 85193323Sed iterator(ImmutableList l) : L(l.getInternalPointer()) {} 86193323Sed 87193323Sed iterator& operator++() { L = L->getTail(); return *this; } 88193323Sed bool operator==(const iterator& I) const { return L == I.L; } 89193323Sed bool operator!=(const iterator& I) const { return L != I.L; } 90193323Sed const value_type& operator*() const { return L->getHead(); } 91193323Sed ImmutableList getList() const { return L; } 92193323Sed }; 93193323Sed 94193323Sed /// begin - Returns an iterator referring to the head of the list, or 95193323Sed /// an iterator denoting the end of the list if the list is empty. 96193323Sed iterator begin() const { return iterator(X); } 97193323Sed 98193323Sed /// end - Returns an iterator denoting the end of the list. This iterator 99193323Sed /// does not refer to a valid list element. 100193323Sed iterator end() const { return iterator(); } 101193323Sed 102193323Sed /// isEmpty - Returns true if the list is empty. 103193323Sed bool isEmpty() const { return !X; } 104193323Sed 105224145Sdim bool contains(const T& V) const { 106224145Sdim for (iterator I = begin(), E = end(); I != E; ++I) { 107224145Sdim if (*I == V) 108224145Sdim return true; 109224145Sdim } 110224145Sdim return false; 111224145Sdim } 112224145Sdim 113193323Sed /// isEqual - Returns true if two lists are equal. Because all lists created 114193323Sed /// from the same ImmutableListFactory are uniqued, this has O(1) complexity 115193323Sed /// because it the contents of the list do not need to be compared. Note 116193323Sed /// that you should only compare two lists created from the same 117193323Sed /// ImmutableListFactory. 118193323Sed bool isEqual(const ImmutableList& L) const { return X == L.X; } 119193323Sed 120193323Sed bool operator==(const ImmutableList& L) const { return isEqual(L); } 121193323Sed 122193323Sed /// getHead - Returns the head of the list. 123193323Sed const T& getHead() { 124193323Sed assert (!isEmpty() && "Cannot get the head of an empty list."); 125193323Sed return X->getHead(); 126193323Sed } 127193323Sed 128193323Sed /// getTail - Returns the tail of the list, which is another (possibly empty) 129193323Sed /// ImmutableList. 130193323Sed ImmutableList getTail() { 131193323Sed return X ? X->getTail() : 0; 132193323Sed } 133193323Sed 134193323Sed void Profile(FoldingSetNodeID& ID) const { 135193323Sed ID.AddPointer(X); 136193323Sed } 137193323Sed}; 138193323Sed 139193323Sedtemplate <typename T> 140193323Sedclass ImmutableListFactory { 141193323Sed typedef ImmutableListImpl<T> ListTy; 142193323Sed typedef FoldingSet<ListTy> CacheTy; 143193323Sed 144193323Sed CacheTy Cache; 145193323Sed uintptr_t Allocator; 146193323Sed 147193323Sed bool ownsAllocator() const { 148193323Sed return Allocator & 0x1 ? false : true; 149193323Sed } 150193323Sed 151193323Sed BumpPtrAllocator& getAllocator() const { 152193323Sed return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1); 153193323Sed } 154193323Sed 155193323Sedpublic: 156193323Sed ImmutableListFactory() 157193323Sed : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {} 158193323Sed 159193323Sed ImmutableListFactory(BumpPtrAllocator& Alloc) 160193323Sed : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {} 161193323Sed 162193323Sed ~ImmutableListFactory() { 163193323Sed if (ownsAllocator()) delete &getAllocator(); 164193323Sed } 165193323Sed 166218893Sdim ImmutableList<T> concat(const T& Head, ImmutableList<T> Tail) { 167193323Sed // Profile the new list to see if it already exists in our cache. 168193323Sed FoldingSetNodeID ID; 169193323Sed void* InsertPos; 170193323Sed 171193323Sed const ListTy* TailImpl = Tail.getInternalPointer(); 172193323Sed ListTy::Profile(ID, Head, TailImpl); 173193323Sed ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos); 174193323Sed 175193323Sed if (!L) { 176193323Sed // The list does not exist in our cache. Create it. 177193323Sed BumpPtrAllocator& A = getAllocator(); 178193323Sed L = (ListTy*) A.Allocate<ListTy>(); 179193323Sed new (L) ListTy(Head, TailImpl); 180193323Sed 181193323Sed // Insert the new list into the cache. 182193323Sed Cache.InsertNode(L, InsertPos); 183193323Sed } 184193323Sed 185193323Sed return L; 186193323Sed } 187193323Sed 188218893Sdim ImmutableList<T> add(const T& D, ImmutableList<T> L) { 189218893Sdim return concat(D, L); 190193323Sed } 191193323Sed 192218893Sdim ImmutableList<T> getEmptyList() const { 193193323Sed return ImmutableList<T>(0); 194193323Sed } 195193323Sed 196218893Sdim ImmutableList<T> create(const T& X) { 197218893Sdim return Concat(X, getEmptyList()); 198193323Sed } 199193323Sed}; 200193323Sed 201193323Sed//===----------------------------------------------------------------------===// 202193323Sed// Partially-specialized Traits. 203193323Sed//===----------------------------------------------------------------------===// 204193323Sed 205193323Sedtemplate<typename T> struct DenseMapInfo; 206193323Sedtemplate<typename T> struct DenseMapInfo<ImmutableList<T> > { 207193323Sed static inline ImmutableList<T> getEmptyKey() { 208193323Sed return reinterpret_cast<ImmutableListImpl<T>*>(-1); 209193323Sed } 210193323Sed static inline ImmutableList<T> getTombstoneKey() { 211193323Sed return reinterpret_cast<ImmutableListImpl<T>*>(-2); 212193323Sed } 213193323Sed static unsigned getHashValue(ImmutableList<T> X) { 214193323Sed uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer()); 215193323Sed return (unsigned((uintptr_t)PtrVal) >> 4) ^ 216193323Sed (unsigned((uintptr_t)PtrVal) >> 9); 217193323Sed } 218193323Sed static bool isEqual(ImmutableList<T> X1, ImmutableList<T> X2) { 219193323Sed return X1 == X2; 220193323Sed } 221193323Sed}; 222193323Sed 223200581Srdivackytemplate <typename T> struct isPodLike; 224200581Srdivackytemplate <typename T> 225200581Srdivackystruct isPodLike<ImmutableList<T> > { static const bool value = true; }; 226200581Srdivacky 227193323Sed} // end llvm namespace 228193323Sed 229193323Sed#endif 230