]>
git.proxmox.com Git - rustc.git/blob - src/llvm/include/llvm/ADT/ImmutableList.h
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_IMMUTABLELIST_H
15 #define LLVM_ADT_IMMUTABLELIST_H
17 #include "llvm/ADT/FoldingSet.h"
18 #include "llvm/Support/Allocator.h"
19 #include "llvm/Support/DataTypes.h"
24 template <typename T
> class ImmutableListFactory
;
27 class ImmutableListImpl
: public FoldingSetNode
{
29 const ImmutableListImpl
* Tail
;
31 ImmutableListImpl(const T
& head
, const ImmutableListImpl
* tail
= 0)
32 : Head(head
), Tail(tail
) {}
34 friend class ImmutableListFactory
<T
>;
36 void operator=(const ImmutableListImpl
&) LLVM_DELETED_FUNCTION
;
37 ImmutableListImpl(const ImmutableListImpl
&) LLVM_DELETED_FUNCTION
;
40 const T
& getHead() const { return Head
; }
41 const ImmutableListImpl
* getTail() const { return Tail
; }
43 static inline void Profile(FoldingSetNodeID
& ID
, const T
& H
,
44 const ImmutableListImpl
* L
){
49 void Profile(FoldingSetNodeID
& ID
) {
50 Profile(ID
, Head
, Tail
);
54 /// ImmutableList - This class represents an immutable (functional) list.
55 /// It is implemented as a smart pointer (wraps ImmutableListImpl), so it
56 /// it is intended to always be copied by value as if it were a pointer.
57 /// This interface matches ImmutableSet and ImmutableMap. ImmutableList
58 /// objects should almost never be created directly, and instead should
59 /// be created by ImmutableListFactory objects that manage the lifetime
60 /// of a group of lists. When the factory object is reclaimed, all lists
61 /// created by that factory are released as well.
66 typedef ImmutableListFactory
<T
> Factory
;
69 const ImmutableListImpl
<T
>* X
;
72 // This constructor should normally only be called by ImmutableListFactory<T>.
73 // There may be cases, however, when one needs to extract the internal pointer
74 // and reconstruct a list object from that pointer.
75 ImmutableList(const ImmutableListImpl
<T
>* x
= 0) : X(x
) {}
77 const ImmutableListImpl
<T
>* getInternalPointer() const {
82 const ImmutableListImpl
<T
>* L
;
85 iterator(ImmutableList l
) : L(l
.getInternalPointer()) {}
87 iterator
& operator++() { L
= L
->getTail(); return *this; }
88 bool operator==(const iterator
& I
) const { return L
== I
.L
; }
89 bool operator!=(const iterator
& I
) const { return L
!= I
.L
; }
90 const value_type
& operator*() const { return L
->getHead(); }
91 ImmutableList
getList() const { return L
; }
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
); }
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(); }
102 /// isEmpty - Returns true if the list is empty.
103 bool isEmpty() const { return !X
; }
105 bool contains(const T
& V
) const {
106 for (iterator I
= begin(), E
= end(); I
!= E
; ++I
) {
113 /// isEqual - Returns true if two lists are equal. Because all lists created
114 /// from the same ImmutableListFactory are uniqued, this has O(1) complexity
115 /// because it the contents of the list do not need to be compared. Note
116 /// that you should only compare two lists created from the same
117 /// ImmutableListFactory.
118 bool isEqual(const ImmutableList
& L
) const { return X
== L
.X
; }
120 bool operator==(const ImmutableList
& L
) const { return isEqual(L
); }
122 /// getHead - Returns the head of the list.
124 assert (!isEmpty() && "Cannot get the head of an empty list.");
128 /// getTail - Returns the tail of the list, which is another (possibly empty)
130 ImmutableList
getTail() {
131 return X
? X
->getTail() : 0;
134 void Profile(FoldingSetNodeID
& ID
) const {
139 template <typename T
>
140 class ImmutableListFactory
{
141 typedef ImmutableListImpl
<T
> ListTy
;
142 typedef FoldingSet
<ListTy
> CacheTy
;
147 bool ownsAllocator() const {
148 return Allocator
& 0x1 ? false : true;
151 BumpPtrAllocator
& getAllocator() const {
152 return *reinterpret_cast<BumpPtrAllocator
*>(Allocator
& ~0x1);
156 ImmutableListFactory()
157 : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
159 ImmutableListFactory(BumpPtrAllocator
& Alloc
)
160 : Allocator(reinterpret_cast<uintptr_t>(&Alloc
) | 0x1) {}
162 ~ImmutableListFactory() {
163 if (ownsAllocator()) delete &getAllocator();
166 ImmutableList
<T
> concat(const T
& Head
, ImmutableList
<T
> Tail
) {
167 // Profile the new list to see if it already exists in our cache.
171 const ListTy
* TailImpl
= Tail
.getInternalPointer();
172 ListTy::Profile(ID
, Head
, TailImpl
);
173 ListTy
* L
= Cache
.FindNodeOrInsertPos(ID
, InsertPos
);
176 // The list does not exist in our cache. Create it.
177 BumpPtrAllocator
& A
= getAllocator();
178 L
= (ListTy
*) A
.Allocate
<ListTy
>();
179 new (L
) ListTy(Head
, TailImpl
);
181 // Insert the new list into the cache.
182 Cache
.InsertNode(L
, InsertPos
);
188 ImmutableList
<T
> add(const T
& D
, ImmutableList
<T
> L
) {
192 ImmutableList
<T
> getEmptyList() const {
193 return ImmutableList
<T
>(0);
196 ImmutableList
<T
> create(const T
& X
) {
197 return Concat(X
, getEmptyList());
201 //===----------------------------------------------------------------------===//
202 // Partially-specialized Traits.
203 //===----------------------------------------------------------------------===//
205 template<typename T
> struct DenseMapInfo
;
206 template<typename T
> struct DenseMapInfo
<ImmutableList
<T
> > {
207 static inline ImmutableList
<T
> getEmptyKey() {
208 return reinterpret_cast<ImmutableListImpl
<T
>*>(-1);
210 static inline ImmutableList
<T
> getTombstoneKey() {
211 return reinterpret_cast<ImmutableListImpl
<T
>*>(-2);
213 static unsigned getHashValue(ImmutableList
<T
> X
) {
214 uintptr_t PtrVal
= reinterpret_cast<uintptr_t>(X
.getInternalPointer());
215 return (unsigned((uintptr_t)PtrVal
) >> 4) ^
216 (unsigned((uintptr_t)PtrVal
) >> 9);
218 static bool isEqual(ImmutableList
<T
> X1
, ImmutableList
<T
> X2
) {
223 template <typename T
> struct isPodLike
;
224 template <typename T
>
225 struct isPodLike
<ImmutableList
<T
> > { static const bool value
= true; };
227 } // end llvm namespace