LLVM: include/llvm/ADT/ImmutableMap.h Source File (original) (raw)

1

2

3

4

5

6

7

8

9

10

11

12

13

14#ifndef LLVM_ADT_IMMUTABLEMAP_H

15#define LLVM_ADT_IMMUTABLEMAP_H

16

20#include

21

22namespace llvm {

23

24

25

26

27template <typename T, typename S>

60

61template <typename KeyT, typename ValT,

62 typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>

64public:

65 using value_type = typename ValInfo::value_type;

67 using key_type = typename ValInfo::key_type;

69 using data_type = typename ValInfo::data_type;

72

73protected:

75

76public:

77

78

79

80

82

85 const bool Canonicalize;

86

87 public:

88 Factory(bool canonicalize = true) : Canonicalize(canonicalize) {}

89

91 : F(Alloc), Canonicalize(canonicalize) {}

92

95

97

100 TreeTy *T = F.add(Old.Root.get(), std::pair<key_type, data_type>(K, D));

101 return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);

102 }

103

106 return ImmutableMap(Canonicalize ? F.getCanonicalTree(T): T);

107 }

108

112 };

113

115 return Root ? Root->contains(K) : false;

116 }

117

121

126

128 if (Root) { Root->retain(); }

129 return Root.get();

130 }

131

133

137

141

143

144public:

145

146

147

148

150

151

152

153

154

157

158 iterator() = default;

160

161 public:

164 };

165

168

172 if (T) return &T->getValue().second;

173 }

174

175 return nullptr;

176 }

177

178

179

180

182 return Root ? &(Root->getMaxElement()->getValue()) : nullptr;

183 }

184

185

186

187

188

190 return Root ? Root->getHeight() : 0;

191 }

192

194 ID.AddPointer(M.Root.get());

195 }

196

200};

201

202

203template <typename KeyT, typename ValT,

204typename ValInfo = ImutKeyValueInfo<KeyT,ValT>>

206public:

209 using key_type = typename ValInfo::key_type;

211 using data_type = typename ValInfo::data_type;

215

216protected:

219

220public:

221

222

223

224

227

230 : Root(X.getRootWithoutRetain()), Factory(F.getTreeFactory()) {}

231

235

239

243

246 Factory->add(Root.get(), std::pair<key_type, data_type>(K, D));

248 }

249

254

256 return Root ? Root->contains(K) : false;

257 }

258

262

266

271

273

274

275

276

277

280 Root->verify();

281 }

282

283

284

285

286

289

290 iterator() = default;

292

293 public:

296 };

297

300

304 if (T) return &T->getValue().second;

305 }

306

307 return nullptr;

308 }

309

310

311

312

314 return Root ? &(Root->getMaxElement()->getValue()) : nullptr;

315 }

316

317

318

319

320

322 return Root ? Root->getHeight() : 0;

323 }

324

326 ID.AddPointer(M.Root.get());

327 }

328

330};

331

332}

333

334#endif

This file defines the BumpPtrAllocator interface.

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

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

This file defines the ImutAVLTree and ImmutableSet classes.

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.

Definition ImmutableMap.h:287

key_type_ref getKey() const

Definition ImmutableMap.h:294

data_type_ref getData() const

Definition ImmutableMap.h:295

friend class ImmutableMapRef

Definition ImmutableMap.h:288

void manualRetain()

Definition ImmutableMap.h:236

unsigned getHeight() const

Definition ImmutableMap.h:321

ImmutableMap< KeyT, ValT > asImmutableMap() const

Definition ImmutableMap.h:259

bool isEmpty() const

Definition ImmutableMap.h:272

FactoryTy * Factory

Definition ImmutableMap.h:218

static ImmutableMapRef getEmptyMap(FactoryTy *F)

Definition ImmutableMap.h:232

void Profile(FoldingSetNodeID &ID) const

Definition ImmutableMap.h:329

bool operator!=(const ImmutableMapRef &RHS) const

Definition ImmutableMap.h:267

bool contains(key_type_ref K) const

Definition ImmutableMap.h:255

static void Profile(FoldingSetNodeID &ID, const ImmutableMapRef &M)

Definition ImmutableMap.h:325

typename ValInfo::data_type data_type

Definition ImmutableMap.h:211

typename ValInfo::data_type_ref data_type_ref

Definition ImmutableMap.h:212

typename ValInfo::key_type key_type

Definition ImmutableMap.h:209

void verify() const

Definition ImmutableMap.h:278

IntrusiveRefCntPtr< TreeTy > Root

Definition ImmutableMap.h:217

ImutAVLTree< ValInfo > TreeTy

Definition ImmutableMap.h:213

typename ValInfo::value_type_ref value_type_ref

Definition ImmutableMap.h:208

bool operator==(const ImmutableMapRef &RHS) const

Definition ImmutableMap.h:263

ImmutableMapRef remove(key_type_ref K) const

Definition ImmutableMap.h:250

typename ValInfo::key_type_ref key_type_ref

Definition ImmutableMap.h:210

value_type * getMaxElement() const

getMaxElement - Returns the <key,value> pair in the ImmutableMap for which key is the highest in the ...

Definition ImmutableMap.h:313

ImmutableMapRef add(key_type_ref K, data_type_ref D) const

Definition ImmutableMap.h:244

typename ValInfo::value_type value_type

Definition ImmutableMap.h:207

iterator begin() const

Definition ImmutableMap.h:298

void manualRelease()

Definition ImmutableMap.h:240

ImmutableMapRef(const TreeTy *R, FactoryTy *F)

Constructs a map from a pointer to a tree root.

Definition ImmutableMap.h:225

data_type * lookup(key_type_ref K) const

Definition ImmutableMap.h:301

iterator end() const

Definition ImmutableMap.h:299

ImmutableMapRef(const ImmutableMap< KeyT, ValT > &X, typename ImmutableMap< KeyT, ValT >::Factory &F)

Definition ImmutableMap.h:228

typename TreeTy::Factory FactoryTy

Definition ImmutableMap.h:214

Definition ImmutableMap.h:83

ImmutableMap getEmptyMap()

Definition ImmutableMap.h:96

ImmutableMap add(ImmutableMap Old, key_type_ref K, data_type_ref D)

Definition ImmutableMap.h:98

Factory(bool canonicalize=true)

Definition ImmutableMap.h:88

TreeTy::Factory * getTreeFactory() const

Definition ImmutableMap.h:109

Factory(const Factory &)=delete

Factory(BumpPtrAllocator &Alloc, bool canonicalize=true)

Definition ImmutableMap.h:90

Factory & operator=(const Factory &)=delete

ImmutableMap remove(ImmutableMap Old, key_type_ref K)

Definition ImmutableMap.h:104

Definition ImmutableMap.h:155

key_type_ref getKey() const

Definition ImmutableMap.h:162

friend class ImmutableMap

Definition ImmutableMap.h:156

data_type_ref getData() const

Definition ImmutableMap.h:163

Definition ImmutableMap.h:63

void verify() const

Definition ImmutableMap.h:149

bool operator==(const ImmutableMap &RHS) const

Definition ImmutableMap.h:118

typename ValInfo::data_type data_type

Definition ImmutableMap.h:69

typename ValInfo::value_type value_type

Definition ImmutableMap.h:65

ImmutableMap(const TreeTy *R)

Constructs a map from a pointer to a tree root.

Definition ImmutableMap.h:81

IntrusiveRefCntPtr< TreeTy > Root

Definition ImmutableMap.h:74

ImutAVLTree< ValInfo > TreeTy

Definition ImmutableMap.h:71

typename ValInfo::key_type key_type

Definition ImmutableMap.h:67

unsigned getHeight() const

Definition ImmutableMap.h:189

iterator begin() const

Definition ImmutableMap.h:166

static void Profile(FoldingSetNodeID &ID, const ImmutableMap &M)

Definition ImmutableMap.h:193

bool contains(key_type_ref K) const

Definition ImmutableMap.h:114

bool isEmpty() const

Definition ImmutableMap.h:142

data_type * lookup(key_type_ref K) const

Definition ImmutableMap.h:169

void manualRetain()

Definition ImmutableMap.h:134

TreeTy * getRootWithoutRetain() const

Definition ImmutableMap.h:132

typename ValInfo::key_type_ref key_type_ref

Definition ImmutableMap.h:68

void manualRelease()

Definition ImmutableMap.h:138

void Profile(FoldingSetNodeID &ID) const

Definition ImmutableMap.h:197

bool operator!=(const ImmutableMap &RHS) const

Definition ImmutableMap.h:122

typename ValInfo::data_type_ref data_type_ref

Definition ImmutableMap.h:70

iterator end() const

Definition ImmutableMap.h:167

typename ValInfo::value_type_ref value_type_ref

Definition ImmutableMap.h:66

TreeTy * getRoot() const

Definition ImmutableMap.h:127

value_type * getMaxElement() const

getMaxElement - Returns the <key,value> pair in the ImmutableMap for which key is the highest in the ...

Definition ImmutableMap.h:181

ImutAVLFactory< ValInfo > Factory

A smart pointer to a reference-counted object that inherits from RefCountedBase or ThreadSafeRefCount...

unsigned ID

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

This is an optimization pass for GlobalISel generic memory operations.

BumpPtrAllocatorImpl<> BumpPtrAllocator

The standard BumpPtrAllocator which just uses the default template parameters.

ImutAVLValueIterator()=default

static bool isLess(key_type_ref LHS, key_type_ref RHS)

static bool isEqual(key_type_ref LHS, key_type_ref RHS)

ImutKeyValueInfo -Traits class used by ImmutableMap.

Definition ImmutableMap.h:28

const value_type & value_type_ref

Definition ImmutableMap.h:30

const S data_type

Definition ImmutableMap.h:33

static void Profile(FoldingSetNodeID &ID, value_type_ref V)

Definition ImmutableMap.h:55

const S & data_type_ref

Definition ImmutableMap.h:34

const T key_type

Definition ImmutableMap.h:31

static bool isLess(key_type_ref L, key_type_ref R)

Definition ImmutableMap.h:47

static key_type_ref KeyOfValue(value_type_ref V)

Definition ImmutableMap.h:36

const std::pair< T, S > value_type

Definition ImmutableMap.h:29

static data_type_ref DataOfValue(value_type_ref V)

Definition ImmutableMap.h:40

static bool isDataEqual(data_type_ref L, data_type_ref R)

Definition ImmutableMap.h:51

static bool isEqual(key_type_ref L, key_type_ref R)

Definition ImmutableMap.h:44

const T & key_type_ref

Definition ImmutableMap.h:32

static void Profile(FoldingSetNodeID &ID, value_type_ref X)