~louis/ubuntu/trusty/clamav/lp799623_fix

libclamav/c++/llvm/include/llvm/ADT/ImmutableSet.h

//===--- ImmutableSet.h - Immutable (functional) set interface --*- C++ -*-===//

// The LLVM Compiler Infrastructure

// This file is distributed under the University of Illinois Open Source

// License. See LICENSE.TXT for details.

//===----------------------------------------------------------------------===//

// This file defines the ImutAVLTree and ImmutableSet classes.

//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_IMSET_H

#define LLVM_ADT_IMSET_H

#include "llvm/Support/Allocator.h"

#include "llvm/ADT/FoldingSet.h"

#include "llvm/System/DataTypes.h"

#include <cassert>

#include <functional>

namespace llvm {

//===----------------------------------------------------------------------===//

// Immutable AVL-Tree Definition.

//===----------------------------------------------------------------------===//

template <typename ImutInfo> class ImutAVLFactory;

template <typename ImutInfo> class ImutIntervalAVLFactory;

template <typename ImutInfo> class ImutAVLTreeInOrderIterator;

template <typename ImutInfo> class ImutAVLTreeGenericIterator;

template <typename ImutInfo >

class ImutAVLTree : public FoldingSetNode {

public:

typedef typename ImutInfo::key_type_ref key_type_ref;

typedef typename ImutInfo::value_type value_type;

typedef typename ImutInfo::value_type_ref value_type_ref;

typedef ImutAVLFactory<ImutInfo> Factory;

friend class ImutAVLFactory<ImutInfo>;

friend class ImutIntervalAVLFactory<ImutInfo>;

friend class ImutAVLTreeGenericIterator<ImutInfo>;

friend class FoldingSet<ImutAVLTree>;

typedef ImutAVLTreeInOrderIterator<ImutInfo> iterator;

//===----------------------------------------------------===//

// Public Interface.

//===----------------------------------------------------===//

/// getLeft - Returns a pointer to the left subtree. This value

/// is NULL if there is no left subtree.

ImutAVLTree *getLeft() const { return Left; }

/// getRight - Returns a pointer to the right subtree. This value is

/// NULL if there is no right subtree.

ImutAVLTree *getRight() const { return Right; }

/// getHeight - Returns the height of the tree. A tree with no subtrees

/// has a height of 1.

unsigned getHeight() const { return Height; }

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

const value_type& getValue() const { return Value; }

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

/// This method returns NULL if no matching subtree is found.

ImutAVLTree* find(key_type_ref K) {

ImutAVLTree *T = this;

while (T) {

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

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

return T;

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

T = T->getLeft();

else

T = T->getRight();

}

return NULL;

}

/// getMaxElement - Find the subtree associated with the highest ranged

/// key value.

ImutAVLTree* getMaxElement() {

ImutAVLTree *T = this;

ImutAVLTree *Right = T->getRight();

while (Right) { T = Right; Right = T->getRight(); }

return T;

}

/// size - Returns the number of nodes in the tree, which includes

/// both leaves and non-leaf nodes.

unsigned size() const {

100

unsigned n = 1;

101

102

if (const ImutAVLTree* L = getLeft()) n += L->size();

103

if (const ImutAVLTree* R = getRight()) n += R->size();

104

105

return n;

106

}

107

108

/// begin - Returns an iterator that iterates over the nodes of the tree

109

/// in an inorder traversal. The returned iterator thus refers to the

110

/// the tree node with the minimum data element.

111

iterator begin() const { return iterator(this); }

112

113

/// end - Returns an iterator for the tree that denotes the end of an

114

/// inorder traversal.

115

iterator end() const { return iterator(); }

116

117

bool ElementEqual(value_type_ref V) const {

118

// Compare the keys.

119

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

120

ImutInfo::KeyOfValue(V)))

121

return false;

122

123

// Also compare the data values.

124

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

125

ImutInfo::DataOfValue(V)))

126

return false;

127

128

return true;

129

}

130

131

bool ElementEqual(const ImutAVLTree* RHS) const {

132

return ElementEqual(RHS->getValue());

133

}

134

135

/// isEqual - Compares two trees for structural equality and returns true

136

/// if they are equal. This worst case performance of this operation is

137

// linear in the sizes of the trees.

138

bool isEqual(const ImutAVLTree& RHS) const {

139

if (&RHS == this)

140

return true;

141

142

iterator LItr = begin(), LEnd = end();

143

iterator RItr = RHS.begin(), REnd = RHS.end();

144

145

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

146

if (*LItr == *RItr) {

147

LItr.SkipSubTree();

148

RItr.SkipSubTree();

149

continue;

150

}

151

152

if (!LItr->ElementEqual(*RItr))

153

return false;

154

155

++LItr;

156

++RItr;

157

}

158

159

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

160

}

161

162

/// isNotEqual - Compares two trees for structural inequality. Performance

163

/// is the same is isEqual.

164

bool isNotEqual(const ImutAVLTree& RHS) const { return !isEqual(RHS); }

165

166

/// contains - Returns true if this tree contains a subtree (node) that

167

/// has an data element that matches the specified key. Complexity

168

/// is logarithmic in the size of the tree.

169

bool contains(key_type_ref K) { return (bool) find(K); }

170

171

/// foreach - A member template the accepts invokes operator() on a functor

172

/// object (specifed by Callback) for every node/subtree in the tree.

173

/// Nodes are visited using an inorder traversal.

174

template <typename Callback>

175

void foreach(Callback& C) {

176

if (ImutAVLTree* L = getLeft()) L->foreach(C);

177

178

C(Value);

179

180

if (ImutAVLTree* R = getRight()) R->foreach(C);

181

}

182

183

/// verify - A utility method that checks that the balancing and

184

/// ordering invariants of the tree are satisifed. It is a recursive

185

/// method that returns the height of the tree, which is then consumed

186

/// by the enclosing verify call. External callers should ignore the

187

/// return value. An invalid tree will cause an assertion to fire in

188

/// a debug build.

189

unsigned verify() const {

190

unsigned HL = getLeft() ? getLeft()->verify() : 0;

191

unsigned HR = getRight() ? getRight()->verify() : 0;

192

193

assert(getHeight() == ( HL > HR ? HL : HR ) + 1

194

&& "Height calculation wrong");

195

196

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

197

&& "Balancing invariant violated");

198

199

assert(!getLeft()

200

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

201

ImutInfo::KeyOfValue(getValue()))

202

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

203

204

205

assert(!getRight()

206

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

207

ImutInfo::KeyOfValue(getRight()->getValue()))

208

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

209

210

return getHeight();

211

}

212

213

/// Profile - Profiling for ImutAVLTree.

214

void Profile(llvm::FoldingSetNodeID& ID) {

215

ID.AddInteger(ComputeDigest());

216

}

217

218

//===----------------------------------------------------===//

219

// Internal Values.

220

//===----------------------------------------------------===//

221

222

private:

223

ImutAVLTree* Left;

224

ImutAVLTree* Right;

225

unsigned Height : 28;

226

unsigned Mutable : 1;

227

unsigned CachedDigest : 1;

228

value_type Value;

229

uint32_t Digest;

230

231

//===----------------------------------------------------===//

232

// Internal methods (node manipulation; used by Factory).

233

//===----------------------------------------------------===//

234

235

private:

236

/// ImutAVLTree - Internal constructor that is only called by

237

/// ImutAVLFactory.

238

ImutAVLTree(ImutAVLTree* l, ImutAVLTree* r, value_type_ref v,

239

unsigned height)

240

: Left(l), Right(r), Height(height), Mutable(true), CachedDigest(false),

241

Value(v), Digest(0) {}

242

243

/// isMutable - Returns true if the left and right subtree references

244

/// (as well as height) can be changed. If this method returns false,

245

/// the tree is truly immutable. Trees returned from an ImutAVLFactory

246

/// object should always have this method return true. Further, if this

247

/// method returns false for an instance of ImutAVLTree, all subtrees

248

/// will also have this method return false. The converse is not true.

249

bool isMutable() const { return Mutable; }

250

251

/// hasCachedDigest - Returns true if the digest for this tree is cached.

252

/// This can only be true if the tree is immutable.

253

bool hasCachedDigest() const { return CachedDigest; }

254

255

//===----------------------------------------------------===//

256

// Mutating operations. A tree root can be manipulated as

257

// long as its reference has not "escaped" from internal

258

// methods of a factory object (see below). When a tree

259

// pointer is externally viewable by client code, the

260

// internal "mutable bit" is cleared to mark the tree

261

// immutable. Note that a tree that still has its mutable

262

// bit set may have children (subtrees) that are themselves

263

// immutable.

264

//===----------------------------------------------------===//

265

266

/// MarkImmutable - Clears the mutable flag for a tree. After this happens,

267

/// it is an error to call setLeft(), setRight(), and setHeight().

268

void MarkImmutable() {

269

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

270

Mutable = false;

271

}

272

273

/// MarkedCachedDigest - Clears the NoCachedDigest flag for a tree.

274

void MarkedCachedDigest() {

275

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

276

CachedDigest = true;

277

}

278

279

/// setLeft - Changes the reference of the left subtree. Used internally

280

/// by ImutAVLFactory.

281

void setLeft(ImutAVLTree* NewLeft) {

282

assert(isMutable() &&

283

"Only a mutable tree can have its left subtree changed.");

284

Left = NewLeft;

285

CachedDigest = false;

286

}

287

288

/// setRight - Changes the reference of the right subtree. Used internally

289

/// by ImutAVLFactory.

290

void setRight(ImutAVLTree* NewRight) {

291

assert(isMutable() &&

292

"Only a mutable tree can have its right subtree changed.");

293

294

Right = NewRight;

295

CachedDigest = false;

296

}

297

298

/// setHeight - Changes the height of the tree. Used internally by

299

/// ImutAVLFactory.

300

void setHeight(unsigned h) {

301

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

302

Height = h;

303

}

304

305

static inline

306

uint32_t ComputeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) {

307

uint32_t digest = 0;

308

309

if (L)

310

digest += L->ComputeDigest();

311

312

// Compute digest of stored data.

313

FoldingSetNodeID ID;

314

ImutInfo::Profile(ID,V);

315

digest += ID.ComputeHash();

316

317

if (R)

318

digest += R->ComputeDigest();

319

320

return digest;

321

}

322

323

inline uint32_t ComputeDigest() {

324

// Check the lowest bit to determine if digest has actually been

325

// pre-computed.

326

if (hasCachedDigest())

327

return Digest;

328

329

uint32_t X = ComputeDigest(getLeft(), getRight(), getValue());

330

Digest = X;

331

MarkedCachedDigest();

332

return X;

333

}

334

};

335

336

//===----------------------------------------------------------------------===//

337

// Immutable AVL-Tree Factory class.

338

//===----------------------------------------------------------------------===//

339

340

template <typename ImutInfo >

341

class ImutAVLFactory {

342

typedef ImutAVLTree<ImutInfo> TreeTy;

343

typedef typename TreeTy::value_type_ref value_type_ref;

344

typedef typename TreeTy::key_type_ref key_type_ref;

345

346

typedef FoldingSet<TreeTy> CacheTy;

347

348

CacheTy Cache;

349

uintptr_t Allocator;

350

351

bool ownsAllocator() const {

352

return Allocator & 0x1 ? false : true;

353

}

354

355

BumpPtrAllocator& getAllocator() const {

356

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

357

}

358

359

//===--------------------------------------------------===//

360

// Public interface.

361

//===--------------------------------------------------===//

362

363

public:

364

ImutAVLFactory()

365

: Allocator(reinterpret_cast<uintptr_t>(new BumpPtrAllocator())) {}

366

367

ImutAVLFactory(BumpPtrAllocator& Alloc)

368

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

369

370

~ImutAVLFactory() {

371

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

372

}

373

374

TreeTy* Add(TreeTy* T, value_type_ref V) {

375

T = Add_internal(V,T);

376

MarkImmutable(T);

377

return T;

378

}

379

380

TreeTy* Remove(TreeTy* T, key_type_ref V) {

381

T = Remove_internal(V,T);

382

MarkImmutable(T);

383

return T;

384

}

385

386

TreeTy* GetEmptyTree() const { return NULL; }

387

388

//===--------------------------------------------------===//

389

// A bunch of quick helper functions used for reasoning

390

// about the properties of trees and their children.

391

// These have succinct names so that the balancing code

392

// is as terse (and readable) as possible.

393

//===--------------------------------------------------===//

394

protected:

395

396

bool isEmpty(TreeTy* T) const { return !T; }

397

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

398

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

399

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

400

value_type_ref Value(TreeTy* T) const { return T->Value; }

401

402

unsigned IncrementHeight(TreeTy* L, TreeTy* R) const {

403

unsigned hl = Height(L);

404

unsigned hr = Height(R);

405

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

406

}

407

408

static bool CompareTreeWithSection(TreeTy* T,

409

typename TreeTy::iterator& TI,

410

typename TreeTy::iterator& TE) {

411

412

typename TreeTy::iterator I = T->begin(), E = T->end();

413

414

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

415

if (TI == TE || !I->ElementEqual(*TI))

416

return false;

417

418

return true;

419

}

420

421

//===--------------------------------------------------===//

422

// "CreateNode" is used to generate new tree roots that link

423

// to other trees. The functon may also simply move links

424

// in an existing root if that root is still marked mutable.

425

// This is necessary because otherwise our balancing code

426

// would leak memory as it would create nodes that are

427

// then discarded later before the finished tree is

428

// returned to the caller.

429

//===--------------------------------------------------===//

430

431

TreeTy* CreateNode(TreeTy* L, value_type_ref V, TreeTy* R) {

432

BumpPtrAllocator& A = getAllocator();

433

TreeTy* T = (TreeTy*) A.Allocate<TreeTy>();

434

new (T) TreeTy(L, R, V, IncrementHeight(L,R));

435

return T;

436

}

437

438

TreeTy* CreateNode(TreeTy* L, TreeTy* OldTree, TreeTy* R) {

439

assert(!isEmpty(OldTree));

440

441

if (OldTree->isMutable()) {

442

OldTree->setLeft(L);

443

OldTree->setRight(R);

444

OldTree->setHeight(IncrementHeight(L, R));

445

return OldTree;

446

}

447

else

448

return CreateNode(L, Value(OldTree), R);

449

}

450

451

/// Balance - Used by Add_internal and Remove_internal to

452

/// balance a newly created tree.

453

TreeTy* Balance(TreeTy* L, value_type_ref V, TreeTy* R) {

454

455

unsigned hl = Height(L);

456

unsigned hr = Height(R);

457

458

if (hl > hr + 2) {

459

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

460

461

TreeTy* LL = Left(L);

462

TreeTy* LR = Right(L);

463

464

if (Height(LL) >= Height(LR))

465

return CreateNode(LL, L, CreateNode(LR,V,R));

466

467

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

468

469

TreeTy* LRL = Left(LR);

470

TreeTy* LRR = Right(LR);

471

472

return CreateNode(CreateNode(LL,L,LRL), LR, CreateNode(LRR,V,R));

473

}

474

else if (hr > hl + 2) {

475

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

476

477

TreeTy* RL = Left(R);

478

TreeTy* RR = Right(R);

479

480

if (Height(RR) >= Height(RL))

481

return CreateNode(CreateNode(L,V,RL), R, RR);

482

483

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

484

485

TreeTy* RLL = Left(RL);

486

TreeTy* RLR = Right(RL);

487

488

return CreateNode(CreateNode(L,V,RLL), RL, CreateNode(RLR,R,RR));

489

}

490

else

491

return CreateNode(L,V,R);

492

}

493

494

/// Add_internal - Creates a new tree that includes the specified

495

/// data and the data from the original tree. If the original tree

496

/// already contained the data item, the original tree is returned.

497

TreeTy* Add_internal(value_type_ref V, TreeTy* T) {

498

if (isEmpty(T))

499

return CreateNode(T, V, T);

500

501

assert(!T->isMutable());

502

503

key_type_ref K = ImutInfo::KeyOfValue(V);

504

key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));

505

506

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

507

return CreateNode(Left(T), V, Right(T));

508

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

509

return Balance(Add_internal(V,Left(T)), Value(T), Right(T));

510

else

511

return Balance(Left(T), Value(T), Add_internal(V,Right(T)));

512

}

513

514

/// Remove_internal - Creates a new tree that includes all the data

515

/// from the original tree except the specified data. If the

516

/// specified data did not exist in the original tree, the original

517

/// tree is returned.

518

TreeTy* Remove_internal(key_type_ref K, TreeTy* T) {

519

if (isEmpty(T))

520

return T;

521

522

assert(!T->isMutable());

523

524

key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));

525

526

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

527

return CombineLeftRightTrees(Left(T),Right(T));

528

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

529

return Balance(Remove_internal(K,Left(T)), Value(T), Right(T));

530

else

531

return Balance(Left(T), Value(T), Remove_internal(K,Right(T)));

532

}

533

534

TreeTy* CombineLeftRightTrees(TreeTy* L, TreeTy* R) {

535

if (isEmpty(L)) return R;

536

if (isEmpty(R)) return L;

537

538

TreeTy* OldNode;

539

TreeTy* NewRight = RemoveMinBinding(R,OldNode);

540

return Balance(L,Value(OldNode),NewRight);

541

}

542

543

TreeTy* RemoveMinBinding(TreeTy* T, TreeTy*& NodeRemoved) {

544

assert(!isEmpty(T));

545

546

if (isEmpty(Left(T))) {

547

NodeRemoved = T;

548

return Right(T);

549

}

550

551

return Balance(RemoveMinBinding(Left(T),NodeRemoved),Value(T),Right(T));

552

}

553

554

/// MarkImmutable - Clears the mutable bits of a root and all of its

555

/// descendants.

556

void MarkImmutable(TreeTy* T) {

557

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

558

return;

559

560

T->MarkImmutable();

561

MarkImmutable(Left(T));

562

MarkImmutable(Right(T));

563

}

564

565

public:

566

TreeTy *GetCanonicalTree(TreeTy *TNew) {

567

if (!TNew)

568

return NULL;

569

570

// Search the FoldingSet bucket for a Tree with the same digest.

571

FoldingSetNodeID ID;

572

unsigned digest = TNew->ComputeDigest();

573

ID.AddInteger(digest);

574

unsigned hash = ID.ComputeHash();

575

576

typename CacheTy::bucket_iterator I = Cache.bucket_begin(hash);

577

typename CacheTy::bucket_iterator E = Cache.bucket_end(hash);

578

579

for (; I != E; ++I) {

580

TreeTy *T = &*I;

581

582

if (T->ComputeDigest() != digest)

583

continue;

584

585

// We found a collision. Perform a comparison of Contents('T')

586

// with Contents('TNew')

587

typename TreeTy::iterator TI = T->begin(), TE = T->end();

588

589

if (!CompareTreeWithSection(TNew, TI, TE))

590

continue;

591

592

if (TI != TE)

593

continue; // T has more contents than TNew.

594

595

// Trees did match! Return 'T'.

596

return T;

597

}

598

599

// 'TNew' is the only tree of its kind. Return it.

600

Cache.InsertNode(TNew, (void*) &*Cache.bucket_end(hash));

601

return TNew;

602

}

603

};

604

605

606

//===----------------------------------------------------------------------===//

607

// Immutable AVL-Tree Iterators.

608

//===----------------------------------------------------------------------===//

609

610

template <typename ImutInfo>

611

class ImutAVLTreeGenericIterator {

612

SmallVector<uintptr_t,20> stack;

613

public:

614

enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,

615

Flags=0x3 };

616

617

typedef ImutAVLTree<ImutInfo> TreeTy;

618

typedef ImutAVLTreeGenericIterator<ImutInfo> _Self;

619

620

inline ImutAVLTreeGenericIterator() {}

621

inline ImutAVLTreeGenericIterator(const TreeTy* Root) {

622

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

623

}

624

625

TreeTy* operator*() const {

626

assert(!stack.empty());

627

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

628

}

629

630

uintptr_t getVisitState() {

631

assert(!stack.empty());

632

return stack.back() & Flags;

633

}

634

635

636

bool AtEnd() const { return stack.empty(); }

637

638

bool AtBeginning() const {

639

return stack.size() == 1 && getVisitState() == VisitedNone;

640

}

641

642

void SkipToParent() {

643

assert(!stack.empty());

644

stack.pop_back();

645

646

if (stack.empty())

647

return;

648

649

switch (getVisitState()) {

650

case VisitedNone:

651

stack.back() |= VisitedLeft;

652

break;

653

case VisitedLeft:

654

stack.back() |= VisitedRight;

655

break;

656

default:

657

assert(false && "Unreachable.");

658

}

659

}

660

661

inline bool operator==(const _Self& x) const {

662

if (stack.size() != x.stack.size())

663

return false;

664

665

for (unsigned i = 0 ; i < stack.size(); i++)

666

if (stack[i] != x.stack[i])

667

return false;

668

669

return true;

670

}

671

672

inline bool operator!=(const _Self& x) const { return !operator==(x); }

673

674

_Self& operator++() {

675

assert(!stack.empty());

676

677

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

678

assert(Current);

679

680

switch (getVisitState()) {

681

case VisitedNone:

682

if (TreeTy* L = Current->getLeft())

683

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

684

else

685

stack.back() |= VisitedLeft;

686

687

break;

688

689

case VisitedLeft:

690

if (TreeTy* R = Current->getRight())

691

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

692

else

693

stack.back() |= VisitedRight;

694

695

break;

696

697

case VisitedRight:

698

SkipToParent();

699

break;

700

701

default:

702

assert(false && "Unreachable.");

703

}

704

705

return *this;

706

}

707

708

_Self& operator--() {

709

assert(!stack.empty());

710

711

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

712

assert(Current);

713

714

switch (getVisitState()) {

715

case VisitedNone:

716

stack.pop_back();

717

break;

718

719

case VisitedLeft:

720

stack.back() &= ~Flags; // Set state to "VisitedNone."

721

722

if (TreeTy* L = Current->getLeft())

723

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

724

725

break;

726

727

case VisitedRight:

728

stack.back() &= ~Flags;

729

stack.back() |= VisitedLeft;

730

731

if (TreeTy* R = Current->getRight())

732

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

733

734

break;

735

736

default:

737

assert(false && "Unreachable.");

738

}

739

740

return *this;

741

}

742

};

743

744

template <typename ImutInfo>

745

class ImutAVLTreeInOrderIterator {

746

typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy;

747

InternalIteratorTy InternalItr;

748

749

public:

750

typedef ImutAVLTree<ImutInfo> TreeTy;

751

typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self;

752

753

ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {

754

if (Root) operator++(); // Advance to first element.

755

}

756

757

ImutAVLTreeInOrderIterator() : InternalItr() {}

758

759

inline bool operator==(const _Self& x) const {

760

return InternalItr == x.InternalItr;

761

}

762

763

inline bool operator!=(const _Self& x) const { return !operator==(x); }

764

765

inline TreeTy* operator*() const { return *InternalItr; }

766

inline TreeTy* operator->() const { return *InternalItr; }

767

768

inline _Self& operator++() {

769

do ++InternalItr;

770

while (!InternalItr.AtEnd() &&

771

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

772

773

return *this;

774

}

775

776

inline _Self& operator--() {

777

do --InternalItr;

778

while (!InternalItr.AtBeginning() &&

779

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

780

781

return *this;

782

}

783

784

inline void SkipSubTree() {

785

InternalItr.SkipToParent();

786

787

while (!InternalItr.AtEnd() &&

788

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

789

++InternalItr;

790

}

791

};

792

793

//===----------------------------------------------------------------------===//

794

// Trait classes for Profile information.

795

//===----------------------------------------------------------------------===//

796

797

/// Generic profile template. The default behavior is to invoke the

798

/// profile method of an object. Specializations for primitive integers

799

/// and generic handling of pointers is done below.

800

template <typename T>

801

struct ImutProfileInfo {

802

typedef const T value_type;

803

typedef const T& value_type_ref;

804

805

static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {

806

FoldingSetTrait<T>::Profile(X,ID);

807

}

808

};

809

810

/// Profile traits for integers.

811

template <typename T>

812

struct ImutProfileInteger {

813

typedef const T value_type;

814

typedef const T& value_type_ref;

815

816

static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {

817

ID.AddInteger(X);

818

}

819

};

820

821

#define PROFILE_INTEGER_INFO(X)\

822

template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};

823

824

PROFILE_INTEGER_INFO(char)

825

PROFILE_INTEGER_INFO(unsigned char)

826

PROFILE_INTEGER_INFO(short)

827

PROFILE_INTEGER_INFO(unsigned short)

828

PROFILE_INTEGER_INFO(unsigned)

829

PROFILE_INTEGER_INFO(signed)

830

PROFILE_INTEGER_INFO(long)

831

PROFILE_INTEGER_INFO(unsigned long)

832

PROFILE_INTEGER_INFO(long long)

833

PROFILE_INTEGER_INFO(unsigned long long)

834

835

#undef PROFILE_INTEGER_INFO

836

837

/// Generic profile trait for pointer types. We treat pointers as

838

/// references to unique objects.

839

template <typename T>

840

struct ImutProfileInfo<T*> {

841

typedef const T* value_type;

842

typedef value_type value_type_ref;

843

844

static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) {

845

ID.AddPointer(X);

846

}

847

};

848

849

//===----------------------------------------------------------------------===//

850

// Trait classes that contain element comparison operators and type

851

// definitions used by ImutAVLTree, ImmutableSet, and ImmutableMap. These

852

// inherit from the profile traits (ImutProfileInfo) to include operations

853

// for element profiling.

854

//===----------------------------------------------------------------------===//

855

856

857

/// ImutContainerInfo - Generic definition of comparison operations for

858

/// elements of immutable containers that defaults to using

859

/// std::equal_to<> and std::less<> to perform comparison of elements.

860

template <typename T>

861

struct ImutContainerInfo : public ImutProfileInfo<T> {

862

typedef typename ImutProfileInfo<T>::value_type value_type;

863

typedef typename ImutProfileInfo<T>::value_type_ref value_type_ref;

864

typedef value_type key_type;

865

typedef value_type_ref key_type_ref;

866

typedef bool data_type;

867

typedef bool data_type_ref;

868

869

static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }

870

static inline data_type_ref DataOfValue(value_type_ref) { return true; }

871

872

static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {

873

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

874

}

875

876

static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {

877

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

878

}

879

880

static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }

881

};

882

883

/// ImutContainerInfo - Specialization for pointer values to treat pointers

884

/// as references to unique objects. Pointers are thus compared by

885

/// their addresses.

886

template <typename T>

887

struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {

888

typedef typename ImutProfileInfo<T*>::value_type value_type;

889

typedef typename ImutProfileInfo<T*>::value_type_ref value_type_ref;

890

typedef value_type key_type;

891

typedef value_type_ref key_type_ref;

892

typedef bool data_type;

893

typedef bool data_type_ref;

894

895

static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }

896

static inline data_type_ref DataOfValue(value_type_ref) { return true; }

897

898

static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {

899

return LHS == RHS;

900

}

901

902

static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {

903

return LHS < RHS;

904

}

905

906

static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }

907

};

908

909

//===----------------------------------------------------------------------===//

910

// Immutable Set

911

//===----------------------------------------------------------------------===//

912

913

template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> >

914

class ImmutableSet {

915

public:

916

typedef typename ValInfo::value_type value_type;

917

typedef typename ValInfo::value_type_ref value_type_ref;

918

typedef ImutAVLTree<ValInfo> TreeTy;

919

920

private:

921

TreeTy *Root;

922

923

public:

924

/// Constructs a set from a pointer to a tree root. In general one

925

/// should use a Factory object to create sets instead of directly

926

/// invoking the constructor, but there are cases where make this

927

/// constructor public is useful.

928

explicit ImmutableSet(TreeTy* R) : Root(R) {}

929

930

class Factory {

931

typename TreeTy::Factory F;

932

const bool Canonicalize;

933

934

public:

935

Factory(bool canonicalize = true)

936

: Canonicalize(canonicalize) {}

937

938

Factory(BumpPtrAllocator& Alloc, bool canonicalize = true)

939

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

940

941

/// GetEmptySet - Returns an immutable set that contains no elements.

942

ImmutableSet GetEmptySet() {

943

return ImmutableSet(F.GetEmptyTree());

944

}

945

946

/// Add - Creates a new immutable set that contains all of the values

947

/// of the original set with the addition of the specified value. If

948

/// the original set already included the value, then the original set is

949

/// returned and no memory is allocated. The time and space complexity

950

/// of this operation is logarithmic in the size of the original set.

951

/// The memory allocated to represent the set is released when the

952

/// factory object that created the set is destroyed.

953

ImmutableSet Add(ImmutableSet Old, value_type_ref V) {

954

TreeTy *NewT = F.Add(Old.Root, V);

955

return ImmutableSet(Canonicalize ? F.GetCanonicalTree(NewT) : NewT);

956

}

957

958

/// Remove - Creates a new immutable set that contains all of the values

959

/// of the original set with the exception of the specified value. If

960

/// the original set did not contain the value, the original set is

961

/// returned and no memory is allocated. The time and space complexity

962

/// of this operation is logarithmic in the size of the original set.

963

/// The memory allocated to represent the set is released when the

964

/// factory object that created the set is destroyed.

965

ImmutableSet Remove(ImmutableSet Old, value_type_ref V) {

966

TreeTy *NewT = F.Remove(Old.Root, V);

967

return ImmutableSet(Canonicalize ? F.GetCanonicalTree(NewT) : NewT);

968

}

969

970

BumpPtrAllocator& getAllocator() { return F.getAllocator(); }

971

972

private:

973

Factory(const Factory& RHS); // DO NOT IMPLEMENT

974

void operator=(const Factory& RHS); // DO NOT IMPLEMENT

975

};

976

977

friend class Factory;

978

979

/// contains - Returns true if the set contains the specified value.

980

bool contains(value_type_ref V) const {

981

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

982

}

983

984

bool operator==(ImmutableSet RHS) const {

985

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

986

}

987

988

bool operator!=(ImmutableSet RHS) const {

989

return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;

990

}

991

992

TreeTy *getRoot() {

993

return Root;

994

}

995

996

/// isEmpty - Return true if the set contains no elements.

997

bool isEmpty() const { return !Root; }

998

999

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

1000

/// This method runs in constant time.

1001

bool isSingleton() const { return getHeight() == 1; }

1002

1003

template <typename Callback>

1004

void foreach(Callback& C) { if (Root) Root->foreach(C); }

1005

1006

template <typename Callback>

1007

void foreach() { if (Root) { Callback C; Root->foreach(C); } }

1008

1009

//===--------------------------------------------------===//

1010

// Iterators.

1011

//===--------------------------------------------------===//

1012

1013

class iterator {

1014

typename TreeTy::iterator itr;

1015

iterator(TreeTy* t) : itr(t) {}

1016

friend class ImmutableSet<ValT,ValInfo>;

1017

public:

1018

iterator() {}

1019

inline value_type_ref operator*() const { return itr->getValue(); }

1020

inline iterator& operator++() { ++itr; return *this; }

1021

inline iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; }

1022

inline iterator& operator--() { --itr; return *this; }

1023

inline iterator operator--(int) { iterator tmp(*this); --itr; return tmp; }

1024

inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; }

1025

inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }

1026

inline value_type *operator->() const { return &(operator*()); }

1027

};

1028

1029

iterator begin() const { return iterator(Root); }

1030

iterator end() const { return iterator(); }

1031

1032

//===--------------------------------------------------===//

1033

// Utility methods.

1034

//===--------------------------------------------------===//

1035

1036

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

1037

1038

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

1039

ID.AddPointer(S.Root);

1040

}

1041

1042

inline void Profile(FoldingSetNodeID& ID) const {

1043

return Profile(ID,*this);

1044

}

1045

1046

//===--------------------------------------------------===//

1047

// For testing.

1048

//===--------------------------------------------------===//

1049

1050

void verify() const { if (Root) Root->verify(); }

1051

};

1052

1053

} // end namespace llvm

1054

1055

#endif

Older »

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate