LLVM 20.0.0git
ImmutableList.h
Go to the documentation of this file.
1//==--- ImmutableList.h - Immutable (functional) list interface --*- C++ -*-==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file defines the ImmutableList class.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ADT_IMMUTABLELIST_H
15#define LLVM_ADT_IMMUTABLELIST_H
16
17#include "llvm/ADT/FoldingSet.h"
19#include <cassert>
20#include <cstdint>
21#include <new>
22
23namespace llvm {
24
25template <typename T> class ImmutableListFactory;
26
27template <typename T>
29 friend class ImmutableListFactory<T>;
30
31 T Head;
32 const ImmutableListImpl* Tail;
33
34 template <typename ElemT>
35 ImmutableListImpl(ElemT &&head, const ImmutableListImpl *tail = nullptr)
36 : Head(std::forward<ElemT>(head)), Tail(tail) {}
37
38public:
41
42 const T& getHead() const { return Head; }
43 const ImmutableListImpl* getTail() const { return Tail; }
44
45 static inline void Profile(FoldingSetNodeID& ID, const T& H,
46 const ImmutableListImpl* L){
47 ID.AddPointer(L);
48 ID.Add(H);
49 }
50
52 Profile(ID, Head, Tail);
53 }
54};
55
56/// ImmutableList - This class represents an immutable (functional) list.
57/// It is implemented as a smart pointer (wraps ImmutableListImpl), so it
58/// it is intended to always be copied by value as if it were a pointer.
59/// This interface matches ImmutableSet and ImmutableMap. ImmutableList
60/// objects should almost never be created directly, and instead should
61/// be created by ImmutableListFactory objects that manage the lifetime
62/// of a group of lists. When the factory object is reclaimed, all lists
63/// created by that factory are released as well.
64template <typename T>
66public:
67 using value_type = T;
69
70 static_assert(std::is_trivially_destructible<T>::value,
71 "T must be trivially destructible!");
72
73private:
74 const ImmutableListImpl<T>* X;
75
76public:
77 // This constructor should normally only be called by ImmutableListFactory<T>.
78 // There may be cases, however, when one needs to extract the internal pointer
79 // and reconstruct a list object from that pointer.
80 ImmutableList(const ImmutableListImpl<T>* x = nullptr) : X(x) {}
81
83 return X;
84 }
85
86 class iterator {
87 const ImmutableListImpl<T>* L = nullptr;
88
89 public:
90 iterator() = default;
92
93 iterator& operator++() { L = L->getTail(); return *this; }
94 bool operator==(const iterator& I) const { return L == I.L; }
95 bool operator!=(const iterator& I) const { return L != I.L; }
96 const value_type& operator*() const { return L->getHead(); }
97 const std::remove_reference_t<value_type> *operator->() const {
98 return &L->getHead();
99 }
100
101 ImmutableList getList() const { return L; }
102 };
103
104 /// begin - Returns an iterator referring to the head of the list, or
105 /// an iterator denoting the end of the list if the list is empty.
106 iterator begin() const { return iterator(X); }
107
108 /// end - Returns an iterator denoting the end of the list. This iterator
109 /// does not refer to a valid list element.
110 iterator end() const { return iterator(); }
111
112 /// isEmpty - Returns true if the list is empty.
113 bool isEmpty() const { return !X; }
114
115 bool contains(const T& V) const {
116 for (iterator I = begin(), E = end(); I != E; ++I) {
117 if (*I == V)
118 return true;
119 }
120 return false;
121 }
122
123 /// isEqual - Returns true if two lists are equal. Because all lists created
124 /// from the same ImmutableListFactory are uniqued, this has O(1) complexity
125 /// because it the contents of the list do not need to be compared. Note
126 /// that you should only compare two lists created from the same
127 /// ImmutableListFactory.
128 bool isEqual(const ImmutableList& L) const { return X == L.X; }
129
130 bool operator==(const ImmutableList& L) const { return isEqual(L); }
131
132 /// getHead - Returns the head of the list.
133 const T& getHead() const {
134 assert(!isEmpty() && "Cannot get the head of an empty list.");
135 return X->getHead();
136 }
137
138 /// getTail - Returns the tail of the list, which is another (possibly empty)
139 /// ImmutableList.
141 return X ? X->getTail() : nullptr;
142 }
143
145 ID.AddPointer(X);
146 }
147};
148
149template <typename T>
153
154 CacheTy Cache;
155 uintptr_t Allocator;
156
157 bool ownsAllocator() const {
158 return (Allocator & 0x1) == 0;
159 }
160
161 BumpPtrAllocator& getAllocator() const {
162 return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);
163 }
164
165public:
167 : Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}
168
170 : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}
171
173 if (ownsAllocator()) delete &getAllocator();
174 }
175
176 template <typename ElemT>
177 [[nodiscard]] ImmutableList<T> concat(ElemT &&Head, ImmutableList<T> Tail) {
178 // Profile the new list to see if it already exists in our cache.
180 void* InsertPos;
181
182 const ListTy* TailImpl = Tail.getInternalPointer();
183 ListTy::Profile(ID, Head, TailImpl);
184 ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);
185
186 if (!L) {
187 // The list does not exist in our cache. Create it.
188 BumpPtrAllocator& A = getAllocator();
189 L = (ListTy*) A.Allocate<ListTy>();
190 new (L) ListTy(std::forward<ElemT>(Head), TailImpl);
191
192 // Insert the new list into the cache.
193 Cache.InsertNode(L, InsertPos);
194 }
195
196 return L;
197 }
198
199 template <typename ElemT>
200 [[nodiscard]] ImmutableList<T> add(ElemT &&Data, ImmutableList<T> L) {
201 return concat(std::forward<ElemT>(Data), L);
202 }
203
204 template <typename... CtorArgs>
206 CtorArgs &&...Args) {
207 return concat(T(std::forward<CtorArgs>(Args)...), Tail);
208 }
209
211 return ImmutableList<T>(nullptr);
212 }
213
214 template <typename ElemT>
216 return concat(std::forward<ElemT>(Data), getEmptyList());
217 }
218};
219
220//===----------------------------------------------------------------------===//
221// Partially-specialized Traits.
222//===----------------------------------------------------------------------===//
223
224template <typename T> struct DenseMapInfo<ImmutableList<T>, void> {
226 return reinterpret_cast<ImmutableListImpl<T>*>(-1);
227 }
228
230 return reinterpret_cast<ImmutableListImpl<T>*>(-2);
231 }
232
233 static unsigned getHashValue(ImmutableList<T> X) {
234 uintptr_t PtrVal = reinterpret_cast<uintptr_t>(X.getInternalPointer());
235 return (unsigned((uintptr_t)PtrVal) >> 4) ^
236 (unsigned((uintptr_t)PtrVal) >> 9);
237 }
238
240 return X1 == X2;
241 }
242};
243
244} // end namespace llvm
245
246#endif // LLVM_ADT_IMMUTABLELIST_H
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This file defines a hash set that can be used to remove duplication of nodes in a graph.
#define I(x, y, z)
Definition: MD5.cpp:58
#define H(x, y, z)
Definition: MD5.cpp:57
Load MIR Sample Profile
#define T
Basic Register Allocator
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
Node - This class is used to maintain the singly linked bucket list in a folding set.
Definition: FoldingSet.h:138
void InsertNode(T *N, void *InsertPos)
InsertNode - Insert the specified node into the folding set, knowing that it is not already in the fo...
Definition: FoldingSet.h:513
T * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition: FoldingSet.h:505
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:327
ImmutableListFactory(BumpPtrAllocator &Alloc)
ImmutableList< T > create(ElemT &&Data)
ImmutableList< T > add(ElemT &&Data, ImmutableList< T > L)
ImmutableList< T > getEmptyList() const
ImmutableList< T > concat(ElemT &&Head, ImmutableList< T > Tail)
ImmutableList< T > emplace(ImmutableList< T > Tail, CtorArgs &&...Args)
static void Profile(FoldingSetNodeID &ID, const T &H, const ImmutableListImpl *L)
Definition: ImmutableList.h:45
ImmutableListImpl & operator=(const ImmutableListImpl &)=delete
const T & getHead() const
Definition: ImmutableList.h:42
ImmutableListImpl(const ImmutableListImpl &)=delete
const ImmutableListImpl * getTail() const
Definition: ImmutableList.h:43
void Profile(FoldingSetNodeID &ID)
Definition: ImmutableList.h:51
bool operator==(const iterator &I) const
Definition: ImmutableList.h:94
const std::remove_reference_t< value_type > * operator->() const
Definition: ImmutableList.h:97
const value_type & operator*() const
Definition: ImmutableList.h:96
ImmutableList getList() const
bool operator!=(const iterator &I) const
Definition: ImmutableList.h:95
ImmutableList - This class represents an immutable (functional) list.
Definition: ImmutableList.h:65
bool isEmpty() const
isEmpty - Returns true if the list is empty.
iterator end() const
end - Returns an iterator denoting the end of the list.
const T & getHead() const
getHead - Returns the head of the list.
ImmutableList getTail() const
getTail - Returns the tail of the list, which is another (possibly empty) ImmutableList.
const ImmutableListImpl< T > * getInternalPointer() const
Definition: ImmutableList.h:82
void Profile(FoldingSetNodeID &ID) const
bool contains(const T &V) const
bool operator==(const ImmutableList &L) const
ImmutableList(const ImmutableListImpl< T > *x=nullptr)
Definition: ImmutableList.h:80
iterator begin() const
begin - Returns an iterator referring to the head of the list, or an iterator denoting the end of the...
bool isEqual(const ImmutableList &L) const
isEqual - Returns true if two lists are equal.
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
Definition: CallingConv.h:76
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
static unsigned getHashValue(ImmutableList< T > X)
static bool isEqual(ImmutableList< T > X1, ImmutableList< T > X2)
static ImmutableList< T > getTombstoneKey()
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:52