ImmutableList.h Source File (original) (raw)

14#ifndef LLVM_ADT_IMMUTABLELIST_H

15#define LLVM_ADT_IMMUTABLELIST_H

19#include

20#include

21#include

23namespace llvm {

27template

31 T Head;

32 const ImmutableListImpl* Tail;

34 template

35 ImmutableListImpl(ElemT &&head, const ImmutableListImpl *tail = nullptr)

36 : Head(std::forward(head)), Tail(tail) {}

38public:

40 ImmutableListImpl &operator=(const ImmutableListImpl &) = delete;

42 const T& getHead() const { return Head; }

43 const ImmutableListImpl* getTail() const { return Tail; }

46 const ImmutableListImpl* L){

47 ID.AddPointer(L);

48 ID.Add(H);

49 }

54};

64template

66public:

70 static_assert(std::is_trivially_destructible::value,

71 "T must be trivially destructible!");

73private:

76public:

89 public:

97 const std::remove_reference_t<value_type> *operator->() const {

98 return &L->getHead();

99 }

100

102 };

103

104

105

107

108

109

111

112

114

117 if (*I == V)

118 return true;

119 }

120 return false;

121 }

122

123

124

125

126

127

129

131

132

134 assert( isEmpty () && "Cannot get the head of an empty list.");

135 return X->getHead();

136 }

137

138

139

141 return X ? X->getTail() : nullptr;

142 }

143

145 ID.AddPointer(X);

146 }

147};

148

149template

153

154 CacheTy Cache;

155 uintptr_t Allocator;

156

157 bool ownsAllocator() const {

158 return (Allocator & 0x1) == 0;

159 }

160

162 return *reinterpret_cast<BumpPtrAllocator*>(Allocator & ~0x1);

163 }

164

165public:

168

170 : Allocator(reinterpret_cast<uintptr_t>(&Alloc) | 0x1) {}

171

173 if (ownsAllocator()) delete &getAllocator();

174 }

175

176 template

178

180 void* InsertPos;

181

182 const ListTy* TailImpl = Tail.getInternalPointer();

184 ListTy* L = Cache.FindNodeOrInsertPos(ID, InsertPos);

185

186 if (!L) {

187

189 L = (ListTy*) A.Allocate();

190 new (L) ListTy(std::forward(Head), TailImpl);

191

192

193 Cache.InsertNode(L, InsertPos);

194 }

195

196 return L;

197 }

198

199 template

201 return concat(std::forward(Data), L);

202 }

203

204 template <typename... CtorArgs>

206 CtorArgs &&...Args) {

207 return concat(T(std::forward(Args)...), Tail);

208 }

209

213

214 template

218};

219

220

221

222

223

228

232

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}

245

246#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

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")

This file defines a hash set that can be used to remove duplication of nodes in a graph.

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

FoldingSetNodeID - This class is used to gather all the unique data bits of a node.

FoldingSet - This template class is used to instantiate a specialized implementation of the folding s...

Definition ImmutableList.h:150

ImmutableListFactory(BumpPtrAllocator &Alloc)

Definition ImmutableList.h:169

~ImmutableListFactory()

Definition ImmutableList.h:172

ImmutableList< T > create(ElemT &&Data)

Definition ImmutableList.h:215

ImmutableList< T > add(ElemT &&Data, ImmutableList< T > L)

Definition ImmutableList.h:200

ImmutableList< T > getEmptyList() const

Definition ImmutableList.h:210

ImmutableList< T > concat(ElemT &&Head, ImmutableList< T > Tail)

Definition ImmutableList.h:177

ImmutableList< T > emplace(ImmutableList< T > Tail, CtorArgs &&...Args)

Definition ImmutableList.h:205

ImmutableListFactory()

Definition ImmutableList.h:166

Definition ImmutableList.h:28

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

Definition ImmutableList.h:86

bool operator==(const iterator &I) const

Definition ImmutableList.h:94

iterator & operator++()

Definition ImmutableList.h:93

const std::remove_reference_t< value_type > * operator->() const

Definition ImmutableList.h:97

const value_type & operator*() const

Definition ImmutableList.h:96

iterator(ImmutableList l)

Definition ImmutableList.h:91

ImmutableList getList() const

Definition ImmutableList.h:101

bool operator!=(const iterator &I) const

Definition ImmutableList.h:95

ImmutableList - This class represents an immutable (functional) list.

Definition ImmutableList.h:65

ImmutableListFactory< T > Factory

Definition ImmutableList.h:68

bool isEmpty() const

isEmpty - Returns true if the list is empty.

Definition ImmutableList.h:113

iterator end() const

end - Returns an iterator denoting the end of the list.

Definition ImmutableList.h:110

const T & getHead() const

getHead - Returns the head of the list.

Definition ImmutableList.h:133

ImmutableList getTail() const

getTail - Returns the tail of the list, which is another (possibly empty) ImmutableList.

Definition ImmutableList.h:140

const ImmutableListImpl< T > * getInternalPointer() const

Definition ImmutableList.h:82

T value_type

Definition ImmutableList.h:67

void Profile(FoldingSetNodeID &ID) const

Definition ImmutableList.h:144

bool contains(const T &V) const

Definition ImmutableList.h:115

bool operator==(const ImmutableList &L) const

Definition ImmutableList.h:130

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...

Definition ImmutableList.h:106

bool isEqual(const ImmutableList &L) const

isEqual - Returns true if two lists are equal.

Definition ImmutableList.h:128

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

@ Tail

Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...

This is an optimization pass for GlobalISel generic memory operations.

FoldingSetBase::Node FoldingSetNode

FunctionAddr VTableAddr uintptr_t uintptr_t Data

BumpPtrAllocatorImpl<> BumpPtrAllocator

The standard BumpPtrAllocator which just uses the default template parameters.

static unsigned getHashValue(ImmutableList< T > X)

Definition ImmutableList.h:233

static bool isEqual(ImmutableList< T > X1, ImmutableList< T > X2)

Definition ImmutableList.h:239

static ImmutableList< T > getTombstoneKey()

Definition ImmutableList.h:229

static ImmutableList< T > getEmptyKey()

Definition ImmutableList.h:225

An information struct used to provide DenseMap with the various necessary components for a given valu...