1 //==--- ImmutableList.h - Immutable (functional) list interface --*- C++ -*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the ImmutableList class.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ADT_IMLIST_H
15 #define LLVM_ADT_IMLIST_H
17 #include "llvm/Support/Allocator.h"
18 #include "llvm/ADT/FoldingSet.h"
19 #include "llvm/Support/DataTypes.h"
24 template <typename T> class ImmutableListFactory;
27 class ImmutableListImpl : public FoldingSetNode {
29 ImmutableListImpl* Tail;
31 ImmutableListImpl(const T& head, ImmutableListImpl* tail = 0)
32 : Head(head), Tail(tail) {}
34 friend class ImmutableListFactory<T>;
37 void operator=(const ImmutableListImpl&);
38 ImmutableListImpl(const ImmutableListImpl&);
41 const T& getHead() const { return Head; }
42 ImmutableListImpl* getTail() const { return Tail; }
44 static inline void Profile(FoldingSetNodeID& ID, const T& H,
45 ImmutableListImpl* L){
50 void Profile(FoldingSetNodeID& ID) {
51 Profile(ID, Head, Tail);
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.
67 typedef ImmutableListFactory<T> Factory;
70 ImmutableListImpl<T>* X;
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) {}
78 ImmutableListImpl<T>* getInternalPointer() const {
83 ImmutableListImpl<T>* L;
86 iterator(ImmutableList l) : L(l.getInternalPointer()) {}
88 iterator& operator++() { L = L->Tail; }
89 bool operator==(const iterator& I) const { return L == I.L; }
90 ImmutableList operator*() const { return L; }
93 iterator begin() const { return iterator(X); }
94 iterator end() const { return iterator(); }
96 bool isEmpty() const { return !X; }
98 bool isEqual(const ImmutableList& L) const { return X == L.X; }
99 bool operator==(const ImmutableList& L) const { return isEqual(L); }
102 assert (!isEmpty() && "Cannot get the head of an empty list.");
106 ImmutableList getTail() {
107 return X ? X->getTail() : 0;
111 template <typename T>
112 class ImmutableListFactory {
113 typedef ImmutableListImpl<T> ListTy;
114 typedef FoldingSet<ListTy> CacheTy;
119 bool ownsAllocator() const {
120 return Allocator & 0x1 ? false : true;
123 BumpPtrAllocator& getAllocator() const {
124 return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
128 ImmutableListFactory()
129 : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
131 ImmutableListFactory(BumpPtrAllocator& Alloc)
132 : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
134 ~ImmutableListFactory() {
135 if (ownsAllocator()) delete &getAllocator();
138 ImmutableList<T> Concat(const T& Head, ImmutableList<T> Tail) {
139 // Profile the new list to see if it already exists in our cache.
143 ListTy* TailImpl = Tail.getInternalPointer();
144 ListTy::Profile(ID, Head, TailImpl);
145 ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
148 // The list does not exist in our cache. Create it.
149 BumpPtrAllocator& A = getAllocator();
150 L = (ListTy*) A.Allocate<ListTy>();
151 new (L) ListTy(Head, TailImpl);
153 // Insert the new list into the cache.
154 Cache.InsertNode(L, InsertPos);
160 ImmutableList<T> Add(const T& D, ImmutableList<T> L) {
164 ImmutableList<T> GetEmptyList() const {
165 return ImmutableList<T>(0);
168 ImmutableList<T> Create(const T& X) {
169 return Concat(X, GetEmptyList());
173 } // end llvm namespace