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

1

2

3

4

5

6

7

8

9

10

11

12

13

14#ifndef LLVM_ADT_IMMUTABLESET_H

15#define LLVM_ADT_IMMUTABLESET_H

16

27#include

28#include

29#include

30#include

31#include

32#include

33

34namespace llvm {

35

36

37

38

39

44

45template

46class ImutAVLTree {

47public:

49 using value_type = typename ImutInfo::value_type;

53

57

58

59

60

61

62

63

64 ImutAVLTree *getLeft() const { return left; }

65

66

67

68 ImutAVLTree *getRight() const { return right; }

69

70

71

72 unsigned getHeight() const { return height; }

73

74

76

77

78

80 ImutAVLTree *T = this;

81 while (T) {

82 key_type_ref CurrentKey = ImutInfo::KeyOfValue(T->getValue());

83 if (ImutInfo::isEqual(K,CurrentKey))

84 return T;

85 else if (ImutInfo::isLess(K,CurrentKey))

86 T = T->getLeft();

87 else

88 T = T->getRight();

89 }

90 return nullptr;

91 }

92

93

94

96 ImutAVLTree *T = this;

97 ImutAVLTree *Right = T->getRight();

99 return T;

100 }

101

102

103

105 unsigned n = 1;

106 if (const ImutAVLTree* L = getLeft())

107 n += L->size();

108 if (const ImutAVLTree* R = getRight())

109 n += R->size();

110 return n;

111 }

112

113

114

115

117

118

119

121

123

124 if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(getValue()),

125 ImutInfo::KeyOfValue(V)))

126 return false;

127

128

129 if (!ImutInfo::isDataEqual(ImutInfo::DataOfValue(getValue()),

130 ImutInfo::DataOfValue(V)))

131 return false;

132

133 return true;

134 }

135

139

140

141

142

144 if (&RHS == this)

145 return true;

146

149

150 while (LItr != LEnd && RItr != REnd) {

151 if (&*LItr == &*RItr) {

154 continue;

155 }

156

158 return false;

159

160 ++LItr;

161 ++RItr;

162 }

163

164 return LItr == LEnd && RItr == REnd;

165 }

166

167

168

170

171

172

173

175

176

177

178

179

180

181

185 (void) HL;

186 (void) HR;

187

189 && "Height calculation wrong");

190

191 assert((HL > HR ? HL-HR : HR-HL) <= 2

192 && "Balancing invariant violated");

193

195 ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()),

196 ImutInfo::KeyOfValue(getValue()))) &&

197 "Value in left child is not less that current value");

198

200 ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()),

202 "Current value is not less that value of right child");

203

205 }

206

207

208

209

210

211private:

217

218 unsigned height : 28;

220 unsigned IsMutable : 1;

222 unsigned IsDigestCached : 1;

224 unsigned IsCanonicalized : 1;

225

226 value_type value;

229

230

231

232

233

234private:

235

236

238 unsigned height)

239 : factory(f), left(l), right(r), height(height), IsMutable(true),

240 IsDigestCached(false), IsCanonicalized(false), value(v)

241 {

242 if (left) left->retain();

244 }

245

246

247

248

249

250

251

252 bool isMutable() const { return IsMutable; }

253

254

255

256 bool hasCachedDigest() const { return IsDigestCached; }

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271 void markImmutable() {

272 assert(isMutable() && "Mutable flag already removed.");

273 IsMutable = false;

274 }

275

276

277 void markedCachedDigest() {

278 assert(!hasCachedDigest() && "NoCachedDigest flag already removed.");

279 IsDigestCached = true;

280 }

281

282

283

284 void setHeight(unsigned h) {

285 assert(isMutable() && "Only a mutable tree can have its height changed.");

286 height = h;

287 }

288

289 static uint32_t computeDigest(ImutAVLTree *L, ImutAVLTree *R,

291 uint32_t digest = 0;

292

293 if (L)

294 digest += L->computeDigest();

295

296

297 FoldingSetNodeID ID;

298 ImutInfo::Profile(ID,V);

299 digest += ID.ComputeHash();

300

301 if (R)

302 digest += R->computeDigest();

303

304 return digest;

305 }

306

307 uint32_t computeDigest() {

308

309

310 if (hasCachedDigest())

311 return digest;

312

314 digest = X;

315 markedCachedDigest();

316 return X;

317 }

318

319

320

321

322

323public:

325

327 assert(refCount > 0);

328 if (--refCount == 0)

330 }

331

333 if (left)

334 left->release();

335 if (right)

336 right->release();

337 if (IsCanonicalized) {

338 if (next)

339 next->prev = prev;

340

341 if (prev)

342 prev->next = next;

343 else

344 factory->Cache[factory->maskCacheIndex(computeDigest())] = next;

345 }

346

347

348

349 IsMutable = false;

350 factory->freeNodes.push_back(this);

351 }

352};

353

354template

359

360

361

362

363

364template

367

372

373 CacheTy Cache;

374 uintptr_t Allocator;

375 std::vector<TreeTy*> createdNodes;

376 std::vector<TreeTy*> freeNodes;

377

378 bool ownsAllocator() const {

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

380 }

381

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

384 }

385

386

387

388

389

390public:

393

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

396

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

399 }

400

401 TreeTy* add(TreeTy* T, value_type_ref V) {

405 return T;

406 }

407

408 TreeTy* remove(TreeTy* T, key_type_ref V) {

412 return T;

413 }

414

416

417protected:

418

419

420

421

422

423

424

426 unsigned getHeight(TreeTy* T) const { return T ? T->getHeight() : 0; }

427 TreeTy* getLeft(TreeTy* T) const { return T->getLeft(); }

428 TreeTy* getRight(TreeTy* T) const { return T->getRight(); }

429 value_type_ref getValue(TreeTy* T) const { return T->value; }

430

431

433

437 return (hl > hr ? hl : hr) + 1;

438 }

439

444 for ( ; I!=E ; ++I, ++TI) {

445 if (TI == TE || I->isElementEqual(&*TI))

446 return false;

447 }

448 return true;

449 }

450

451

452

453

454

455

456

457

458

459

460

461 TreeTy* createNode(TreeTy* L, value_type_ref V, TreeTy* R) {

463 TreeTy* T;

464 if (!freeNodes.empty()) {

465 T = freeNodes.back();

466 freeNodes.pop_back();

469 } else {

470 T = (TreeTy*) A.Allocate();

471 }

473 createdNodes.push_back(T);

474 return T;

475 }

476

477 TreeTy* createNode(TreeTy* newLeft, TreeTy* oldTree, TreeTy* newRight) {

479 }

480

482 for (unsigned i = 0, n = createdNodes.size(); i < n; ++i) {

483 TreeTy *N = createdNodes[i];

484 if (N->isMutable() && N->refCount == 0)

485 N->destroy();

486 }

487 createdNodes.clear();

488 }

489

490

491

492 TreeTy* balanceTree(TreeTy* L, value_type_ref V, TreeTy* R) {

495

496 if (hl > hr + 2) {

497 assert(isEmpty(L) && "Left tree cannot be empty to have a height >= 2");

498

501

504

505 assert(isEmpty(LR) && "LR cannot be empty because it has a height >= 1");

506

507 TreeTy *LRL = getLeft(LR);

509

511 }

512

513 if (hr > hl + 2) {

514 assert(isEmpty(R) && "Right tree cannot be empty to have a height >= 2");

515

518

521

522 assert(isEmpty(RL) && "RL cannot be empty because it has a height >= 1");

523

524 TreeTy *RLL = getLeft(RL);

526

528 }

529

531 }

532

533

534

535

540

541 key_type_ref K = ImutInfo::KeyOfValue(V);

542 key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));

543

544 if (ImutInfo::isEqual(K, KCurrent)) {

545

546 if (ImutInfo::isDataEqual(ImutInfo::DataOfValue(V),

547 ImutInfo::DataOfValue(getValue(T))))

548 return T;

549

551 }

552

555 if (ImutInfo::isLess(K, KCurrent))

557 else

559

560

561

563 ? T

565 }

566

567

568

569

570

573 return T;

574

576

577 key_type_ref KCurrent = ImutInfo::KeyOfValue(getValue(T));

578

579 if (ImutInfo::isEqual(K, KCurrent))

581

584 if (ImutInfo::isLess(K, KCurrent))

586 else

588

589

590

592 ? T

594 }

595

598 return R;

600 return L;

601 TreeTy* OldNode;

604 }

605

609 Noderemoved = T;

611 }

614 }

615

616

617

619 if (T || T->isMutable())

620 return;

621 T->markImmutable();

624 }

625

626public:

628 if (!TNew)

629 return nullptr;

630

631 if (TNew->IsCanonicalized)

632 return TNew;

633

634

635

636 unsigned digest = TNew->computeDigest();

638 if (entry) {

639 for (TreeTy *T = entry ; T != nullptr; T = T->next) {

640

643 continue;

644 if (TI != TE)

645 continue;

646

647 if (TNew->refCount == 0)

649 return T;

650 }

651 entry->prev = TNew;

652 TNew->next = entry;

653 }

654

655 entry = TNew;

656 TNew->IsCanonicalized = true;

657 return TNew;

658 }

659};

660

661

662

663

664

667

668public:

674

677

679

682 if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));

683 }

684

686 assert(!stack.empty());

687 return *reinterpret_cast<TreeTy *>(stack.back() & ~Flags);

688 }

690

692 assert(!stack.empty());

693 return stack.back() & Flags;

694 }

695

696 bool atEnd() const { return stack.empty(); }

697

701

703 assert(!stack.empty());

704 stack.pop_back();

705 if (stack.empty())

706 return;

710 break;

713 break;

714 default:

716 }

717 }

718

720 return stack == x.stack;

721 }

722

724 return !(*this == x);

725 }

726

728 assert(!stack.empty());

729 TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);

734 stack.push_back(reinterpret_cast<uintptr_t>(L));

735 else

737 break;

740 stack.push_back(reinterpret_cast<uintptr_t>(R));

741 else

743 break;

746 break;

747 default:

749 }

750 return *this;

751 }

752

754 assert(!stack.empty());

755 TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);

759 stack.pop_back();

760 break;

762 stack.back() &= ~Flags;

764 stack.push_back(reinterpret_cast<uintptr_t>(L) | VisitedRight);

765 break;

767 stack.back() &= ~Flags;

770 stack.push_back(reinterpret_cast<uintptr_t>(R) | VisitedRight);

771 break;

772 default:

774 }

775 return *this;

776 }

777};

778

781

782 InternalIteratorTy InternalItr;

783

784public:

790

792

794 if (Root)

795 ++*this;

796 }

797

799

801 return InternalItr == x.InternalItr;

802 }

803

805 return !(*this == x);

806 }

807

810

812 do ++InternalItr;

813 while (!InternalItr.atEnd() &&

814 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);

815

816 return *this;

817 }

818

820 do --InternalItr;

821 while (!InternalItr.atBeginning() &&

822 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);

823

824 return *this;

825 }

826

828 InternalItr.skipToParent();

829

830 while (!InternalItr.atEnd() &&

831 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)

832 ++InternalItr;

833 }

834};

835

836

837

838template

841 ImutAVLValueIterator, typename T::TreeTy::iterator,

842 typename std::iterator_traits<

843 typename T::TreeTy::iterator>::iterator_category,

844 const typename T::value_type> {

848

850 return this->I->getValue();

851 }

852};

853

854

855

856

857

858

859

860

861template

870

871

872template

876

878 ID.AddInteger(X);

879 }

880};

881

882#define PROFILE_INTEGER_INFO(X)\

883template<> struct ImutProfileInfo : ImutProfileInteger {};

884

895

896#undef PROFILE_INTEGER_INFO

897

898

899template <>

903

905 ID.AddBoolean(X);

906 }

907};

908

909

910

911template

915

917 ID.AddPointer(X);

918 }

919};

920

921

922

923

924

925

926

927

928

929

930

938

941

943 return std::equal_to<key_type>()(LHS,RHS);

944 }

945

947 return std::less<key_type>()(LHS,RHS);

948 }

949

951};

952

953

954

955

973

974

975

976

977

978template <typename ValT, typename ValInfo = ImutContainerInfo>

980public:

984

985private:

987

988public:

989

990

991

992

994

997 const bool Canonicalize;

998

999 public:

1001 : Canonicalize(canonicalize) {}

1002

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

1005

1008

1009

1013

1014

1015

1016

1017

1018

1019

1020

1022 TreeTy *NewT = F.add(Old.Root.get(), V);

1023 return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);

1024 }

1025

1026

1027

1028

1029

1030

1031

1032

1034 TreeTy *NewT = F.remove(Old.Root.get(), V);

1035 return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);

1036 }

1037

1039

1043 };

1044

1046

1047

1049 return Root ? Root->contains(V) : false;

1050 }

1051

1053 return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root;

1054 }

1055

1057 return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get())

1058 : Root != RHS.Root;

1059 }

1060

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

1063 return Root.get();

1064 }

1065

1067

1068

1070

1071

1072

1074

1075

1076

1077

1078

1080

1083

1084

1085

1086

1087

1088 unsigned getHeight() const { return Root ? Root->getHeight() : 0; }

1089

1091 ID.AddPointer(S.Root.get());

1092 }

1093

1095

1096

1097

1098

1099

1100 void validateTree() const { if (Root) Root->validateTree(); }

1101};

1102

1103

1104template <typename ValT, typename ValInfo = ImutContainerInfo>

1106public:

1111

1112private:

1115

1116public:

1117

1118

1119

1120

1122

1126

1130

1132 return ImmutableSetRef(Factory->remove(Root.get(), V), Factory);

1133 }

1134

1135

1137 return Root ? Root->contains(V) : false;

1138 }

1139

1142 canonicalize ? Factory->getCanonicalTree(Root.get()) : Root.get());

1143 }

1144

1146

1148 return Root && RHS.Root ? Root->isEqual(*RHS.Root.get()) : Root == RHS.Root;

1149 }

1150

1152 return Root && RHS.Root ? Root->isNotEqual(*RHS.Root.get())

1153 : Root != RHS.Root;

1154 }

1155

1156

1158

1159

1160

1162

1163

1164

1165

1166

1168

1171

1172

1173

1174

1175

1176 unsigned getHeight() const { return Root ? Root->getHeight() : 0; }

1177

1179 ID.AddPointer(S.Root.get());

1180 }

1181

1183

1184

1185

1186

1187

1188 void validateTree() const { if (Root) Root->validateTree(); }

1189};

1190

1191}

1192

1193#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< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

#define LLVM_PREFERRED_TYPE(T)

\macro LLVM_PREFERRED_TYPE Adjust type of bit-field in debug info.

This file defines the DenseMap class.

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

#define PROFILE_INTEGER_INFO(X)

Definition ImmutableSet.h:882

This file defines the RefCountedBase, ThreadSafeRefCountedBase, and IntrusiveRefCntPtr classes.

This file defines the SmallVector class.

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.

static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S)

Definition ImmutableSet.h:1178

void Profile(FoldingSetNodeID &ID) const

Definition ImmutableSet.h:1182

ImmutableSetRef add(value_type_ref V)

Definition ImmutableSet.h:1127

ImutAVLTree< ValInfo > TreeTy

Definition ImmutableSet.h:1109

bool contains(value_type_ref V) const

Returns true if the set contains the specified value.

Definition ImmutableSet.h:1136

bool operator!=(const ImmutableSetRef &RHS) const

Definition ImmutableSet.h:1151

ImmutableSetRef remove(value_type_ref V)

Definition ImmutableSet.h:1131

ImutAVLValueIterator< ImmutableSetRef > iterator

Definition ImmutableSet.h:1167

bool isSingleton() const

isSingleton - Return true if the set contains exactly one element.

Definition ImmutableSet.h:1161

iterator begin() const

Definition ImmutableSet.h:1169

bool isEmpty() const

isEmpty - Return true if the set contains no elements.

Definition ImmutableSet.h:1157

typename ValInfo::value_type value_type

Definition ImmutableSet.h:1107

ImmutableSetRef(TreeTy *R, FactoryTy *F)

Constructs a set from a pointer to a tree root.

Definition ImmutableSet.h:1121

typename ValInfo::value_type_ref value_type_ref

Definition ImmutableSet.h:1108

iterator end() const

Definition ImmutableSet.h:1170

unsigned getHeight() const

Definition ImmutableSet.h:1176

ImmutableSet< ValT > asImmutableSet(bool canonicalize=true) const

Definition ImmutableSet.h:1140

typename TreeTy::Factory FactoryTy

Definition ImmutableSet.h:1110

static ImmutableSetRef getEmptySet(FactoryTy *F)

Definition ImmutableSet.h:1123

void validateTree() const

Definition ImmutableSet.h:1188

bool operator==(const ImmutableSetRef &RHS) const

Definition ImmutableSet.h:1147

TreeTy * getRootWithoutRetain() const

Definition ImmutableSet.h:1145

Definition ImmutableSet.h:995

Factory(const Factory &RHS)=delete

void operator=(const Factory &RHS)=delete

TreeTy::Factory * getTreeFactory() const

Definition ImmutableSet.h:1040

BumpPtrAllocator & getAllocator()

Definition ImmutableSet.h:1038

Factory(BumpPtrAllocator &Alloc, bool canonicalize=true)

Definition ImmutableSet.h:1003

ImmutableSet getEmptySet()

getEmptySet - Returns an immutable set that contains no elements.

Definition ImmutableSet.h:1010

Factory(bool canonicalize=true)

Definition ImmutableSet.h:1000

ImmutableSet remove(ImmutableSet Old, value_type_ref V)

remove - Creates a new immutable set that contains all of the values of the original set with the exc...

Definition ImmutableSet.h:1033

ImmutableSet add(ImmutableSet Old, value_type_ref V)

add - Creates a new immutable set that contains all of the values of the original set with the additi...

Definition ImmutableSet.h:1021

Definition ImmutableSet.h:979

bool operator!=(const ImmutableSet &RHS) const

Definition ImmutableSet.h:1056

typename ValInfo::value_type value_type

Definition ImmutableSet.h:981

bool operator==(const ImmutableSet &RHS) const

Definition ImmutableSet.h:1052

iterator end() const

Definition ImmutableSet.h:1082

bool isEmpty() const

isEmpty - Return true if the set contains no elements.

Definition ImmutableSet.h:1069

ImmutableSet(TreeTy *R)

Constructs a set from a pointer to a tree root.

Definition ImmutableSet.h:993

bool isSingleton() const

isSingleton - Return true if the set contains exactly one element.

Definition ImmutableSet.h:1073

TreeTy * getRootWithoutRetain() const

Definition ImmutableSet.h:1066

ImutAVLTree< ValInfo > TreeTy

Definition ImmutableSet.h:983

void validateTree() const

Definition ImmutableSet.h:1100

bool contains(value_type_ref V) const

Returns true if the set contains the specified value.

Definition ImmutableSet.h:1048

void Profile(FoldingSetNodeID &ID) const

Definition ImmutableSet.h:1094

iterator begin() const

Definition ImmutableSet.h:1081

unsigned getHeight() const

Definition ImmutableSet.h:1088

TreeTy * getRoot()

Definition ImmutableSet.h:1061

static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S)

Definition ImmutableSet.h:1090

ImutAVLValueIterator< ImmutableSet > iterator

Definition ImmutableSet.h:1079

typename ValInfo::value_type_ref value_type_ref

Definition ImmutableSet.h:982

Definition ImmutableSet.h:365

static unsigned maskCacheIndex(unsigned I)

Definition ImmutableSet.h:432

TreeTy * balanceTree(TreeTy *L, value_type_ref V, TreeTy *R)

balanceTree - Used by add_internal and remove_internal to balance a newly created tree.

Definition ImmutableSet.h:492

unsigned getHeight(TreeTy *T) const

Definition ImmutableSet.h:426

ImutAVLFactory(BumpPtrAllocator &Alloc)

Definition ImmutableSet.h:394

TreeTy * add_internal(value_type_ref V, TreeTy *T)

add_internal - Creates a new tree that includes the specified data and the data from the original tre...

Definition ImmutableSet.h:536

value_type_ref getValue(TreeTy *T) const

Definition ImmutableSet.h:429

static bool compareTreeWithSection(TreeTy *T, typename TreeTy::iterator &TI, typename TreeTy::iterator &TE)

Definition ImmutableSet.h:440

TreeTy * getLeft(TreeTy *T) const

Definition ImmutableSet.h:427

ImutAVLFactory()

Definition ImmutableSet.h:391

TreeTy * getCanonicalTree(TreeTy *TNew)

Definition ImmutableSet.h:627

TreeTy * add(TreeTy *T, value_type_ref V)

Definition ImmutableSet.h:401

TreeTy * getRight(TreeTy *T) const

Definition ImmutableSet.h:428

TreeTy * getEmptyTree() const

Definition ImmutableSet.h:415

TreeTy * removeMinBinding(TreeTy *T, TreeTy *&Noderemoved)

Definition ImmutableSet.h:606

TreeTy * createNode(TreeTy *newLeft, TreeTy *oldTree, TreeTy *newRight)

Definition ImmutableSet.h:477

TreeTy * combineTrees(TreeTy *L, TreeTy *R)

Definition ImmutableSet.h:596

TreeTy * remove_internal(key_type_ref K, TreeTy *T)

remove_internal - Creates a new tree that includes all the data from the original tree except the spe...

Definition ImmutableSet.h:571

TreeTy * createNode(TreeTy *L, value_type_ref V, TreeTy *R)

Definition ImmutableSet.h:461

unsigned incrementHeight(TreeTy *L, TreeTy *R) const

Definition ImmutableSet.h:434

TreeTy * remove(TreeTy *T, key_type_ref V)

Definition ImmutableSet.h:408

~ImutAVLFactory()

Definition ImmutableSet.h:397

void recoverNodes()

Definition ImmutableSet.h:481

void markImmutable(TreeTy *T)

markImmutable - Clears the mutable bits of a root and all of its descendants.

Definition ImmutableSet.h:618

bool isEmpty(TreeTy *T) const

Definition ImmutableSet.h:425

Definition ImmutableSet.h:665

ImutAVLTreeGenericIterator()=default

value_type * pointer

Definition ImmutableSet.h:672

ImutAVLTree< ImutInfo > value_type

Definition ImmutableSet.h:670

void skipToParent()

Definition ImmutableSet.h:702

std::ptrdiff_t difference_type

Definition ImmutableSet.h:671

bool operator==(const ImutAVLTreeGenericIterator &x) const

Definition ImmutableSet.h:719

std::bidirectional_iterator_tag iterator_category

Definition ImmutableSet.h:669

ImutAVLTreeGenericIterator(const TreeTy *Root)

Definition ImmutableSet.h:681

bool atEnd() const

Definition ImmutableSet.h:696

ImutAVLTree< ImutInfo > TreeTy

Definition ImmutableSet.h:678

ImutAVLTreeGenericIterator & operator--()

Definition ImmutableSet.h:753

VisitFlag

Definition ImmutableSet.h:675

@ VisitedRight

Definition ImmutableSet.h:675

@ VisitedNone

Definition ImmutableSet.h:675

@ Flags

Definition ImmutableSet.h:676

@ VisitedLeft

Definition ImmutableSet.h:675

TreeTy & operator*() const

Definition ImmutableSet.h:685

TreeTy * operator->() const

Definition ImmutableSet.h:689

value_type & reference

Definition ImmutableSet.h:673

uintptr_t getVisitState() const

Definition ImmutableSet.h:691

bool atBeginning() const

Definition ImmutableSet.h:698

bool operator!=(const ImutAVLTreeGenericIterator &x) const

Definition ImmutableSet.h:723

ImutAVLTreeGenericIterator & operator++()

Definition ImmutableSet.h:727

Definition ImmutableSet.h:779

void skipSubTree()

Definition ImmutableSet.h:827

bool operator!=(const ImutAVLTreeInOrderIterator &x) const

Definition ImmutableSet.h:804

TreeTy * operator->() const

Definition ImmutableSet.h:809

ImutAVLTreeInOrderIterator & operator++()

Definition ImmutableSet.h:811

value_type * pointer

Definition ImmutableSet.h:788

ImutAVLTree< ImutInfo > TreeTy

Definition ImmutableSet.h:791

ImutAVLTreeInOrderIterator & operator--()

Definition ImmutableSet.h:819

std::bidirectional_iterator_tag iterator_category

Definition ImmutableSet.h:785

ImutAVLTreeInOrderIterator()

Definition ImmutableSet.h:798

TreeTy & operator*() const

Definition ImmutableSet.h:808

ImutAVLTreeInOrderIterator(const TreeTy *Root)

Definition ImmutableSet.h:793

bool operator==(const ImutAVLTreeInOrderIterator &x) const

Definition ImmutableSet.h:800

ImutAVLTree< ImutInfo > value_type

Definition ImmutableSet.h:786

value_type & reference

Definition ImmutableSet.h:789

std::ptrdiff_t difference_type

Definition ImmutableSet.h:787

Definition ImmutableSet.h:46

unsigned size() const

size - Returns the number of nodes in the tree, which includes both leaves and non-leaf nodes.

Definition ImmutableSet.h:104

iterator end() const

end - Returns an iterator for the tree that denotes the end of an inorder traversal.

Definition ImmutableSet.h:120

const value_type & getValue() const

getValue - Returns the data value associated with the tree node.

Definition ImmutableSet.h:75

void destroy()

Definition ImmutableSet.h:332

unsigned getHeight() const

getHeight - Returns the height of the tree.

Definition ImmutableSet.h:72

typename ValInfo::key_type_ref key_type_ref

Definition ImmutableSet.h:48

void retain()

Definition ImmutableSet.h:324

ImutAVLFactory< ValInfo > Factory

Definition ImmutableSet.h:51

ImutAVLTree * find(key_type_ref K)

find - Finds the subtree associated with the specified key value.

Definition ImmutableSet.h:79

typename ValInfo::value_type_ref value_type_ref

Definition ImmutableSet.h:50

unsigned validateTree() const

validateTree - A utility method that checks that the balancing and ordering invariants of the tree ar...

Definition ImmutableSet.h:182

bool isNotEqual(const ImutAVLTree &RHS) const

isNotEqual - Compares two trees for structural inequality.

Definition ImmutableSet.h:169

bool isEqual(const ImutAVLTree &RHS) const

isEqual - Compares two trees for structural equality and returns true if they are equal.

Definition ImmutableSet.h:143

ImutAVLTree * getLeft() const

Return a pointer to the left subtree.

Definition ImmutableSet.h:64

ImutAVLTreeInOrderIterator< ValInfo > iterator

Definition ImmutableSet.h:52

typename ValInfo::value_type value_type

Definition ImmutableSet.h:49

ImutAVLTree * getRight() const

Return a pointer to the right subtree.

Definition ImmutableSet.h:68

bool isElementEqual(const ImutAVLTree *RHS) const

Definition ImmutableSet.h:136

bool contains(key_type_ref K)

contains - Returns true if this tree contains a subtree (node) that has an data element that matches ...

Definition ImmutableSet.h:174

void release()

Definition ImmutableSet.h:326

ImutAVLTree * getMaxElement()

getMaxElement - Find the subtree associated with the highest ranged key value.

Definition ImmutableSet.h:95

iterator begin() const

begin - Returns an iterator that iterates over the nodes of the tree in an inorder traversal.

Definition ImmutableSet.h:116

bool isElementEqual(value_type_ref V) const

Definition ImmutableSet.h:122

Definition ImmutableSet.h:41

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

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

iterator_adaptor_base()=default

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

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.

static void Profile(const T &X, FoldingSetNodeID &ID)

Generic iterator that wraps a T::TreeTy::iterator and exposes iterator::getValue() on dereference.

Definition ImmutableSet.h:844

ImutAVLValueIterator()=default

ImutAVLValueIterator::reference operator*() const

Definition ImmutableSet.h:849

ImutAVLValueIterator(typename T::TreeTy *Tree)

Definition ImmutableSet.h:846

static bool isDataEqual(data_type_ref, data_type_ref)

Definition ImmutableSet.h:971

value_type_ref key_type_ref

Definition ImmutableSet.h:960

bool data_type

Definition ImmutableSet.h:961

static key_type_ref KeyOfValue(value_type_ref D)

Definition ImmutableSet.h:964

static bool isEqual(key_type_ref LHS, key_type_ref RHS)

Definition ImmutableSet.h:967

typename ImutProfileInfo< T * >::value_type_ref value_type_ref

Definition ImmutableSet.h:958

typename ImutProfileInfo< T * >::value_type value_type

Definition ImmutableSet.h:957

value_type key_type

Definition ImmutableSet.h:959

static data_type_ref DataOfValue(value_type_ref)

Definition ImmutableSet.h:965

bool data_type_ref

Definition ImmutableSet.h:962

static bool isLess(key_type_ref LHS, key_type_ref RHS)

Definition ImmutableSet.h:969

ImutContainerInfo - Generic definition of comparison operations for elements of immutable containers ...

Definition ImmutableSet.h:931

static bool isLess(key_type_ref LHS, key_type_ref RHS)

Definition ImmutableSet.h:946

typename ImutProfileInfo< T >::value_type value_type

Definition ImmutableSet.h:932

value_type key_type

Definition ImmutableSet.h:934

static bool isEqual(key_type_ref LHS, key_type_ref RHS)

Definition ImmutableSet.h:942

static bool isDataEqual(data_type_ref, data_type_ref)

Definition ImmutableSet.h:950

static data_type_ref DataOfValue(value_type_ref)

Definition ImmutableSet.h:940

bool data_type

Definition ImmutableSet.h:936

static key_type_ref KeyOfValue(value_type_ref D)

Definition ImmutableSet.h:939

bool data_type_ref

Definition ImmutableSet.h:937

value_type_ref key_type_ref

Definition ImmutableSet.h:935

typename ImutProfileInfo< T >::value_type_ref value_type_ref

Definition ImmutableSet.h:933

static void Profile(FoldingSetNodeID &ID, value_type_ref X)

Definition ImmutableSet.h:916

value_type value_type_ref

Definition ImmutableSet.h:914

const T * value_type

Definition ImmutableSet.h:913

const bool value_type

Definition ImmutableSet.h:901

const bool & value_type_ref

Definition ImmutableSet.h:902

static void Profile(FoldingSetNodeID &ID, value_type_ref X)

Definition ImmutableSet.h:904

Generic profile template.

Definition ImmutableSet.h:862

const T value_type

Definition ImmutableSet.h:863

static void Profile(FoldingSetNodeID &ID, value_type_ref X)

Definition ImmutableSet.h:866

const T & value_type_ref

Definition ImmutableSet.h:864

Profile traits for integers.

Definition ImmutableSet.h:873

static void Profile(FoldingSetNodeID &ID, value_type_ref X)

Definition ImmutableSet.h:877

const T value_type

Definition ImmutableSet.h:874

const T & value_type_ref

Definition ImmutableSet.h:875

static void retain(ImutAVLTree< ImutInfo > *Tree)

Definition ImmutableSet.h:356

Class you can specialize to provide custom retain/release functionality for a type.