RewriteRope.cpp Source File (original) (raw)

15#include

16#include

17#include

19using namespace llvm;

64namespace {

76class RopePieceBTreeNode {

77protected:

83 enum { WidthFactor = 8 };

87 unsigned Size = 0;

91 bool IsLeaf;

93 RopePieceBTreeNode(bool isLeaf) : IsLeaf(isLeaf) {}

94 ~RopePieceBTreeNode() = default;

96public:

97 bool isLeaf() const { return IsLeaf; }

98 unsigned size() const { return Size; }

100 void Destroy();

101

102

103

104

105

106

107

108 RopePieceBTreeNode *split(unsigned Offset);

109

110

111

112

113

114

115

116 RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);

117

118

119

120 void erase(unsigned Offset, unsigned NumBytes);

121};

122

123

124

125

126

127

128

129

130

131

132

133

134class RopePieceBTreeLeaf : public RopePieceBTreeNode {

135

136

137 unsigned char NumPieces = 0;

138

139

140 RopePiece Pieces[2 * WidthFactor];

141

142

143

144 RopePieceBTreeLeaf **PrevLeaf = nullptr;

145 RopePieceBTreeLeaf *NextLeaf = nullptr;

146

147public:

148 RopePieceBTreeLeaf() : RopePieceBTreeNode(true) {}

149

150 ~RopePieceBTreeLeaf() {

151 if (PrevLeaf || NextLeaf)

152 removeFromLeafInOrder();

153 clear();

154 }

155

156 bool isFull() const { return NumPieces == 2 * WidthFactor; }

157

158

159 void clear() {

160 while (NumPieces)

161 Pieces[--NumPieces] = RopePiece();

163 }

164

165 unsigned getNumPieces() const { return NumPieces; }

166

167 const RopePiece &getPiece(unsigned i) const {

168 assert(i < getNumPieces() && "Invalid piece ID");

169 return Pieces[i];

170 }

171

172 const RopePieceBTreeLeaf *getNextLeafInOrder() const { return NextLeaf; }

173

174 void insertAfterLeafInOrder(RopePieceBTreeLeaf *Node) {

175 assert(!PrevLeaf && !NextLeaf && "Already in ordering");

176

177 NextLeaf = Node->NextLeaf;

178 if (NextLeaf)

179 NextLeaf->PrevLeaf = &NextLeaf;

180 PrevLeaf = &Node->NextLeaf;

181 Node->NextLeaf = this;

182 }

183

184 void removeFromLeafInOrder() {

185 if (PrevLeaf) {

186 *PrevLeaf = NextLeaf;

187 if (NextLeaf)

188 NextLeaf->PrevLeaf = PrevLeaf;

189 } else if (NextLeaf) {

190 NextLeaf->PrevLeaf = nullptr;

191 }

192 }

193

194

195

196 void FullRecomputeSizeLocally() {

198 for (unsigned i = 0, e = getNumPieces(); i != e; ++i)

199 Size += getPiece(i).size();

200 }

201

202

203

204

205

206

207

208 RopePieceBTreeNode *split(unsigned Offset);

209

210

211

212

213

214

215

216 RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);

217

218

219

220 void erase(unsigned Offset, unsigned NumBytes);

221

222 static bool classof(const RopePieceBTreeNode *N) { return N->isLeaf(); }

223};

224

225}

226

227

228

229

230

231

232

233RopePieceBTreeNode *RopePieceBTreeLeaf::split(unsigned Offset) {

234

235

237

238 return nullptr;

239 }

240

241

242 unsigned PieceOffs = 0;

243 unsigned i = 0;

244 while (Offset >= PieceOffs + Pieces[i].size()) {

245 PieceOffs += Pieces[i].size();

246 ++i;

247 }

248

249

250

251 if (PieceOffs == Offset)

252 return nullptr;

253

254

255

256 unsigned IntraPieceOffset = Offset - PieceOffs;

257

258

259 RopePiece Tail(Pieces[i].StrData, Pieces[i].StartOffs + IntraPieceOffset,

260 Pieces[i].EndOffs);

264

266}

267

268

269

270

271

272

273RopePieceBTreeNode *RopePieceBTreeLeaf::insert(unsigned Offset,

274 const RopePiece &R) {

275

276 if (!isFull()) {

277

278

279 unsigned i = 0, e = getNumPieces();

281

282 i = e;

283 } else {

284 unsigned SlotOffs = 0;

285 for (; Offset > SlotOffs; ++i)

286 SlotOffs += getPiece(i).size();

287 assert(SlotOffs == Offset && "Split didn't occur before insertion!");

288 }

289

290

291

292 for (; i != e; --e)

293 Pieces[e] = Pieces[e - 1];

294 Pieces[i] = R;

295 ++NumPieces;

296 Size += R.size();

297 return nullptr;

298 }

299

300

301

302

303

304

305

306 RopePieceBTreeLeaf *NewNode = new RopePieceBTreeLeaf();

307

308

309 std::copy(&Pieces[WidthFactor], &Pieces[2 * WidthFactor],

310 &NewNode->Pieces[0]);

311

312 std::fill(&Pieces[WidthFactor], &Pieces[2 * WidthFactor], RopePiece());

313

314

315 NewNode->NumPieces = NumPieces = WidthFactor;

316

317

318 NewNode->FullRecomputeSizeLocally();

319 FullRecomputeSizeLocally();

320

321

322 NewNode->insertAfterLeafInOrder(this);

323

324

326 this->insert(Offset, R);

327 else

328 NewNode->insert(Offset - this->size(), R);

329 return NewNode;

330}

331

332

333

334void RopePieceBTreeLeaf::erase(unsigned Offset, unsigned NumBytes) {

335

336

337 unsigned PieceOffs = 0;

338 unsigned i = 0;

339 for (; Offset > PieceOffs; ++i)

340 PieceOffs += getPiece(i).size();

341 assert(PieceOffs == Offset && "Split didn't occur before erase!");

342

343 unsigned StartPiece = i;

344

345

346

347 for (; Offset + NumBytes > PieceOffs + getPiece(i).size(); ++i)

348 PieceOffs += getPiece(i).size();

349

350

351 if (Offset + NumBytes == PieceOffs + getPiece(i).size()) {

352 PieceOffs += getPiece(i).size();

353 ++i;

354 }

355

356

357 if (i != StartPiece) {

358 unsigned NumDeleted = i - StartPiece;

359 for (; i != getNumPieces(); ++i)

360 Pieces[i - NumDeleted] = Pieces[i];

361

362

363 std::fill(&Pieces[getNumPieces() - NumDeleted], &Pieces[getNumPieces()],

364 RopePiece());

365 NumPieces -= NumDeleted;

366

367 unsigned CoverBytes = PieceOffs - Offset;

368 NumBytes -= CoverBytes;

369 Size -= CoverBytes;

370 }

371

372

373 if (NumBytes == 0)

374 return;

375

376

377

378 assert(getPiece(StartPiece).size() > NumBytes);

379 Pieces[StartPiece].StartOffs += NumBytes;

380

381

382 Size -= NumBytes;

383}

384

385

386

387

388

389namespace {

390

391

392

393class RopePieceBTreeInterior : public RopePieceBTreeNode {

394

395

396 unsigned char NumChildren = 0;

397

398 RopePieceBTreeNode *Children[2 * WidthFactor];

399

400public:

401 RopePieceBTreeInterior() : RopePieceBTreeNode(false) {}

402

403 RopePieceBTreeInterior(RopePieceBTreeNode *LHS, RopePieceBTreeNode *RHS)

404 : RopePieceBTreeNode(false) {

407 NumChildren = 2;

409 }

410

411 ~RopePieceBTreeInterior() {

412 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)

413 Children[i]->Destroy();

414 }

415

416 bool isFull() const { return NumChildren == 2 * WidthFactor; }

417

418 unsigned getNumChildren() const { return NumChildren; }

419

420 const RopePieceBTreeNode *getChild(unsigned i) const {

421 assert(i < NumChildren && "invalid child #");

423 }

424

425 RopePieceBTreeNode *getChild(unsigned i) {

426 assert(i < NumChildren && "invalid child #");

428 }

429

430

431

432 void FullRecomputeSizeLocally() {

434 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)

435 Size += getChild(i)->size();

436 }

437

438

439

440

441

442

443

444 RopePieceBTreeNode *split(unsigned Offset);

445

446

447

448

449

450

451

452 RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R);

453

454

455

456 RopePieceBTreeNode *HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS);

457

458

459

460 void erase(unsigned Offset, unsigned NumBytes);

461

462 static bool classof(const RopePieceBTreeNode *N) { return ->isLeaf(); }

463};

464

465}

466

467

468

469

470

471

472

473RopePieceBTreeNode *RopePieceBTreeInterior::split(unsigned Offset) {

474

476 return nullptr;

477

478 unsigned ChildOffset = 0;

479 unsigned i = 0;

480 for (; Offset >= ChildOffset + getChild(i)->size(); ++i)

481 ChildOffset += getChild(i)->size();

482

483

484 if (ChildOffset == Offset)

485 return nullptr;

486

487

488 if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset - ChildOffset))

489 return HandleChildPiece(i, RHS);

490 return nullptr;

491}

492

493

494

495

496

497

498

499RopePieceBTreeNode *RopePieceBTreeInterior::insert(unsigned Offset,

500 const RopePiece &R) {

501

502

503 unsigned i = 0, e = getNumChildren();

504

505 unsigned ChildOffs = 0;

507

508 i = e - 1;

509 ChildOffs = size() - getChild(i)->size();

510 } else {

511 for (; Offset > ChildOffs + getChild(i)->size(); ++i)

512 ChildOffs += getChild(i)->size();

513 }

514

515 Size += R.size();

516

517

518 if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset - ChildOffs, R))

519 return HandleChildPiece(i, RHS);

520

521 return nullptr;

522}

523

524

525

526RopePieceBTreeNode *

527RopePieceBTreeInterior::HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS) {

528

529

530 if (!isFull()) {

531

532 if (i + 1 != getNumChildren())

533 memmove(&Children[i + 2], &Children[i + 1],

534 (getNumChildren() - i - 1) * sizeof(Children[0]));

536 ++NumChildren;

537 return nullptr;

538 }

539

540

541

542

543

544 RopePieceBTreeInterior *NewNode = new RopePieceBTreeInterior();

545

546

547 memcpy(&NewNode->Children[0], &Children[WidthFactor],

548 WidthFactor * sizeof(Children[0]));

549

550

551 NewNode->NumChildren = NumChildren = WidthFactor;

552

553

554

555 if (i < WidthFactor)

556 this->HandleChildPiece(i, RHS);

557 else

558 NewNode->HandleChildPiece(i - WidthFactor, RHS);

559

560

561 NewNode->FullRecomputeSizeLocally();

562 FullRecomputeSizeLocally();

563 return NewNode;

564}

565

566

567

568void RopePieceBTreeInterior::erase(unsigned Offset, unsigned NumBytes) {

569

570 Size -= NumBytes;

571

572

573 unsigned i = 0;

574 for (; Offset >= getChild(i)->size(); ++i)

575 Offset -= getChild(i)->size();

576

577

578

579 while (NumBytes) {

580 RopePieceBTreeNode *CurChild = getChild(i);

581

582

583

584 if (Offset + NumBytes < CurChild->size()) {

585 CurChild->erase(Offset, NumBytes);

586 return;

587 }

588

589

590

592 unsigned BytesFromChild = CurChild->size() - Offset;

593 CurChild->erase(Offset, BytesFromChild);

594 NumBytes -= BytesFromChild;

595

597 ++i;

598 continue;

599 }

600

601

602

603 NumBytes -= CurChild->size();

604 CurChild->Destroy();

605 --NumChildren;

606 if (i != getNumChildren())

607 memmove(&Children[i], &Children[i + 1],

608 (getNumChildren() - i) * sizeof(Children[0]));

609 }

610}

611

612

613

614

615

616void RopePieceBTreeNode::Destroy() {

618 delete Leaf;

619 else

621}

622

623

624

625

626

627

628

629RopePieceBTreeNode *RopePieceBTreeNode::split(unsigned Offset) {

632 return Leaf->split(Offset);

634}

635

636

637

638

639

640

641

642RopePieceBTreeNode *RopePieceBTreeNode::insert(unsigned Offset,

643 const RopePiece &R) {

646 return Leaf->insert(Offset, R);

648}

649

650

651

652void RopePieceBTreeNode::erase(unsigned Offset, unsigned NumBytes) {

653 assert(Offset + NumBytes <= size() && "Invalid offset to erase!");

655 return Leaf->erase(Offset, NumBytes);

657}

658

659

660

661

662

663static const RopePieceBTreeLeaf *getCN(const void *P) {

664 return static_cast<const RopePieceBTreeLeaf *>(P);

665}

666

667

669 const auto *N = static_cast<const RopePieceBTreeNode *>(n);

670

671

673 N = IN->getChild(0);

674

675

677

678

679

680 while (CurNode && getCN(CurNode)->getNumPieces() == 0)

681 CurNode = getCN(CurNode)->getNextLeafInOrder();

682

683 if (CurNode)

684 CurPiece = &getCN(CurNode)->getPiece(0);

685 else

686 CurPiece = nullptr;

687 CurChar = 0;

688}

689

691 if (CurPiece !=

692 &getCN(CurNode)->getPiece(getCN(CurNode)->getNumPieces() - 1)) {

693 CurChar = 0;

694 ++CurPiece;

695 return;

696 }

697

698

699 do

700 CurNode = getCN(CurNode)->getNextLeafInOrder();

701 while (CurNode && getCN(CurNode)->getNumPieces() == 0);

702

703 if (CurNode)

704 CurPiece = &getCN(CurNode)->getPiece(0);

705 else

706 CurPiece = nullptr;

707 CurChar = 0;

708}

709

710

711

712

713

714static RopePieceBTreeNode *getRoot(void *P) {

715 return static_cast<RopePieceBTreeNode *>(P);

716}

717

719

721 assert(RHS.empty() && "Can't copy non-empty tree yet");

722 Root = new RopePieceBTreeLeaf();

723}

724

726

728

731 Leaf->clear();

732 else {

733 getRoot(Root)->Destroy();

734 Root = new RopePieceBTreeLeaf();

735 }

736}

737

739

741 Root = new RopePieceBTreeInterior(getRoot(Root), RHS);

742

743

745 Root = new RopePieceBTreeInterior(getRoot(Root), RHS);

746}

747

749

751 Root = new RopePieceBTreeInterior(getRoot(Root), RHS);

752

753

755}

756

757

758

759

760

761

762

763

764

765RopePiece RewriteRope::MakeRopeString(const char *Start, const char *End) {

766 unsigned Len = End - Start;

767 assert(Len && "Zero length RopePiece is invalid!");

768

769

770 if (AllocOffs + Len <= AllocChunkSize) {

771 memcpy(AllocBuffer->Data + AllocOffs, Start, Len);

772 AllocOffs += Len;

773 return RopePiece(AllocBuffer, AllocOffs - Len, AllocOffs);

774 }

775

776

777

778 if (Len > AllocChunkSize) {

782 memcpy(Res->Data, Start, End - Start);

783 return RopePiece(Res, 0, End - Start);

784 }

785

786

787

788

789 unsigned AllocSize = offsetof(RopeRefCountString, Data) + AllocChunkSize;

790 auto *Res = reinterpret_cast<RopeRefCountString *>(new char[AllocSize]);

791 Res->RefCount = 0;

792 memcpy(Res->Data, Start, Len);

793 AllocBuffer = Res;

794 AllocOffs = Len;

795

796 return RopePiece(AllocBuffer, 0, Len);

797}

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

Function Alias Analysis false

static DeltaTreeNode * getRoot(void *Root)

#define offsetof(TYPE, MEMBER)

static const RopePieceBTreeLeaf * getCN(const void *P)

Definition RewriteRope.cpp:663

RopePieceBTreeIterator()=default

LLVM_ABI void MoveToNextPiece()

Definition RewriteRope.cpp:690

LLVM_ABI ~RopePieceBTree()

Definition RewriteRope.cpp:725

LLVM_ABI unsigned size() const

Definition RewriteRope.cpp:727

LLVM_ABI void insert(unsigned Offset, const RopePiece &R)

Definition RewriteRope.cpp:738

LLVM_ABI void erase(unsigned Offset, unsigned NumBytes)

Definition RewriteRope.cpp:748

LLVM_ABI void clear()

Definition RewriteRope.cpp:729

LLVM_ABI RopePieceBTree()

Definition RewriteRope.cpp:718

@ Tail

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

NodeAddr< NodeBase * > Node

This is an optimization pass for GlobalISel generic memory operations.

auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)

Get the size of a range.

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

void erase(Container &C, ValueType V)

Wrapper function to remove a value from a container:

iterator_range< SplittingIterator > split(StringRef Str, StringRef Separator)

Split the specified string over a separator and return a range-compatible iterable over its partition...

FunctionAddr VTableAddr uintptr_t uintptr_t Data

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

RopePiece - This class represents a view into a RopeRefCountString object.

RopeRefCountString - This struct is allocated with 'new char[]' from the heap, and represents a refer...