ImmutableList.h revision e06e91122fefcadd252ddd2f2591e181683fc2f1 
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
128template <typename T>
129class ImmutableListFactory {
130  typedef ImmutableListImpl<T> ListTy;
131  typedef FoldingSet<ListTy>   CacheTy;
132
133  CacheTy Cache;
134  uintptr_t Allocator;
135
136  bool ownsAllocator() const {
137    return Allocator & 0x1 ? false : true;
138  }
139
140  BumpPtrAllocator& getAllocator() const {
141    return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
142  }
143
144public:
145  ImmutableListFactory()
146    : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
147
148  ImmutableListFactory(BumpPtrAllocator& Alloc)
149  : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
150
151  ~ImmutableListFactory() {
152    if (ownsAllocator()) delete &getAllocator();
153  }
154
155  ImmutableList<T> Concat(const T& Head, ImmutableList<T> Tail) {
156    // Profile the new list to see if it already exists in our cache.
157    FoldingSetNodeID ID;
158    void* InsertPos;
159
160    const ListTy* TailImpl = Tail.getInternalPointer();
161    ListTy::Profile(ID, Head, TailImpl);
162    ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
163
164    if (!L) {
165      // The list does not exist in our cache.  Create it.
166      BumpPtrAllocator& A = getAllocator();
167      L = (ListTy*) A.Allocate<ListTy>();
168      new (L) ListTy(Head, TailImpl);
169
170      // Insert the new list into the cache.
171      Cache.InsertNode(L, InsertPos);
172    }
173
174    return L;
175  }
176
177  ImmutableList<T> Add(const T& D, ImmutableList<T> L) {
178    return Concat(D, L);
179  }
180
181  ImmutableList<T> GetEmptyList() const {
182    return ImmutableList<T>(0);
183  }
184
185  ImmutableList<T> Create(const T& X) {
186    return Concat(X, GetEmptyList());
187  }
188};
189
190//===----------------------------------------------------------------------===//
191// Partially-specialized Traits.
192//===----------------------------------------------------------------------===//
193
194template<typename T> struct DenseMapInfo;
195template<typename T> struct DenseMapInfo<ImmutableList<T> > {
196  static inline ImmutableList<T> getEmptyKey() {
197    return reinterpret_cast<ImmutableListImpl<T>*>(-1);
198  }
199  static inline ImmutableList<T> getTombstoneKey() {
200    return reinterpret_cast<ImmutableListImpl<T>*>(-2);
201  }
202  static unsigned getHashValue(ImmutableList<T> X) {
203    uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer());
204    return (unsigned((uintptr_t)PtrVal) >> 4) ^
205           (unsigned((uintptr_t)PtrVal) >> 9);
206  }
207  static bool isEqual(ImmutableList<T> X1, ImmutableList<T> X2) {
208    return X1 == X2;
209  }
210  static bool isPod() { return true; }
211};
212
213} // end llvm namespace
214
215#endif
216