IntervalMap.h Source File (original) (raw)

100

101

102

103

104#ifndef LLVM_ADT_INTERVALMAP_H

105#define LLVM_ADT_INTERVALMAP_H

106

111#include

112#include

113#include

114#include

115#include

116

117namespace llvm {

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139template

141

142

143 static inline bool startLess(const T &x, const T &a) {

144 return x < a;

145 }

146

147

148

149 static inline bool stopLess(const T &b, const T &x) {

150 return b < x;

151 }

152

153

154

155 static inline bool adjacent(const T &a, const T &b) {

156 return a+1 == b;

157 }

158

159

160

161 static inline bool nonEmpty(const T &a, const T &b) {

162 return a <= b;

163 }

164};

165

166template

168

169 static inline bool startLess(const T &x, const T &a) {

170 return x < a;

171 }

172

173

174 static inline bool stopLess(const T &b, const T &x) {

175 return b <= x;

176 }

177

178

179 static inline bool adjacent(const T &a, const T &b) {

180 return a == b;

181 }

182

183

184 static inline bool nonEmpty(const T &a, const T &b) {

185 return a < b;

186 }

187};

188

189

190

191namespace IntervalMapImpl {

192

193using IdxPair = std::pair<unsigned,unsigned>;

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222template <typename T1, typename T2, unsigned N>

224public:

226

229

230

231

232

233

234

235 template

237 unsigned j, unsigned Count) {

238 assert(i + Count <= M && "Invalid source range");

239 assert(j + Count <= N && "Invalid dest range");

240 for (unsigned e = i + Count; i != e; ++i, ++j) {

243 }

244 }

245

246

247

248

249

250 void moveLeft(unsigned i, unsigned j, unsigned Count) {

251 assert(j <= i && "Use moveRight shift elements right");

252 copy(*this, i, j, Count);

253 }

254

255

256

257

258

259 void moveRight(unsigned i, unsigned j, unsigned Count) {

260 assert(i <= j && "Use moveLeft shift elements left");

261 assert(j + Count <= N && "Invalid range");

262 while (Count--) {

265 }

266 }

267

268

269

270

271

272 void erase(unsigned i, unsigned j, unsigned Size) {

274 }

275

276

277

278

281 }

282

283

284

285

288 }

289

290

291

292

293

294

296 unsigned Count) {

297 Sib.copy(*this, 0, SSize, Count);

299 }

300

301

302

303

304

305

307 unsigned Count) {

309 Sib.copy(*this, Size-Count, 0, Count);

310 }

311

312

313

314

315

316

317

318

320 if (Add > 0) {

321

322 unsigned Count = std::min(std::min(unsigned(Add), SSize), N - Size);

324 return Count;

325 } else {

326

327 unsigned Count = std::min(std::min(unsigned(-Add), Size), N - SSize);

329 return -Count;

330 }

331 }

332};

333

334

335

336

337

338

339template

341 unsigned CurSize[], const unsigned NewSize[]) {

342

343 for (int n = Nodes - 1; n; --n) {

344 if (CurSize[n] == NewSize[n])

345 continue;

346 for (int m = n - 1; m != -1; --m) {

347 int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m],

348 NewSize[n] - CurSize[n]);

349 CurSize[m] -= d;

350 CurSize[n] += d;

351

352 if (CurSize[n] >= NewSize[n])

353 break;

354 }

355 }

356

357 if (Nodes == 0)

358 return;

359

360

361 for (unsigned n = 0; n != Nodes - 1; ++n) {

362 if (CurSize[n] == NewSize[n])

363 continue;

364 for (unsigned m = n + 1; m != Nodes; ++m) {

365 int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n],

366 CurSize[n] - NewSize[n]);

367 CurSize[m] += d;

368 CurSize[n] -= d;

369

370 if (CurSize[n] >= NewSize[n])

371 break;

372 }

373 }

374

375#ifndef NDEBUG

376 for (unsigned n = 0; n != Nodes; n++)

377 assert(CurSize[n] == NewSize[n] && "Insufficient element shuffle");

378#endif

379}

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,

415 const unsigned *CurSize, unsigned NewSize[],

416 unsigned Position, bool Grow);

417

418

419

420

421

422

423

424

425

426

427

428

429

430enum {

431

432

437

438template <typename KeyT, typename ValT>

440 enum {

441

442

443

444

445

447 static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)),

450 };

451

453

454 enum {

455

456

458

459

461 static_cast<unsigned>(sizeof(KeyT) + sizeof(void*))

463

464

465

466

467

470};

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

494 struct CacheAlignedPointerTraits {

495 static inline void *getAsVoidPointer(void *P) { return P; }

496 static inline void *getFromVoidPointer(void *P) { return P; }

497 static constexpr int NumLowBitsAvailable = Log2CacheLine;

498 };

500

501public:

502

504

505

507

508

509 template

510 NodeRef(NodeT *p, unsigned n) : pip(p, n - 1) {

511 assert(n <= NodeT::Capacity && "Size too big for node");

512 }

513

514

515 unsigned size() const { return pip.getInt() + 1; }

516

517

519

520

521

522

525 }

526

527

528 template

530 return *reinterpret_cast<NodeT*>(pip.getPointer());

531 }

532

534 if (pip == RHS.pip)

535 return true;

536 assert(pip.getPointer() != RHS.pip.getPointer() && "Inconsistent NodeRefs");

537 return false;

538 }

539

542 }

543};

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565template <typename KeyT, typename ValT, unsigned N, typename Traits>

567public:

568 const KeyT &start(unsigned i) const { return this->first[i].first; }

569 const KeyT &stop(unsigned i) const { return this->first[i].second; }

571

575

576

577

578

579

580

581

584 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&

585 "Index is past the needed point");

586 while (i != Size && Traits::stopLess(stop(i), x)) ++i;

587 return i;

588 }

589

590

591

592

593

594

595

596

598 assert(i < N && "Bad index");

599 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&

600 "Index is past the needed point");

601 while (Traits::stopLess(stop(i), x)) ++i;

602 assert(i < N && "Unsafe intervals");

603 return i;

604 }

605

606

607

608

609

610

613 return Traits::startLess(x, start(i)) ? NotFound : value(i);

614 }

615

617};

618

619

620

621

622

623

624

625

626

627

628template <typename KeyT, typename ValT, unsigned N, typename Traits>

631 unsigned i = Pos;

633 assert(!Traits::stopLess(b, a) && "Invalid interval");

634

635

636 assert((i == 0 || Traits::stopLess(stop(i - 1), a)));

637 assert((i == Size || !Traits::stopLess(stop(i), a)));

638 assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert");

639

640

641 if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) {

642 Pos = i - 1;

643

644 if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) {

645 stop(i - 1) = stop(i);

647 return Size - 1;

648 }

649 stop(i - 1) = b;

651 }

652

653

654 if (i == N)

655 return N + 1;

656

657

658 if (i == Size) {

659 start(i) = a;

660 stop(i) = b;

662 return Size + 1;

663 }

664

665

666 if (value(i) == y && Traits::adjacent(b, start(i))) {

667 start(i) = a;

669 }

670

671

673 return N + 1;

674

675

676 this->shift(i, Size);

677 start(i) = a;

678 stop(i) = b;

680 return Size + 1;

681}

682

683

684

685

686

687

688

689

690

691

692

693

694

695

696

697

698

699

700

701

702template <typename KeyT, typename ValT, unsigned N, typename Traits>

704public:

707

710

711

712

713

714

715

716

719 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&

720 "Index to findFrom is past the needed point");

721 while (i != Size && Traits::stopLess(stop(i), x)) ++i;

722 return i;

723 }

724

725

726

727

728

729

730

732 assert(i < N && "Bad index");

733 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&

734 "Index is past the needed point");

735 while (Traits::stopLess(stop(i), x)) ++i;

736 assert(i < N && "Unsafe intervals");

737 return i;

738 }

739

740

741

742

745 }

746

747

748

749

750

751

753 assert(Size < N && "branch node overflow");

754 assert(i <= Size && "Bad insert position");

757 stop(i) = Stop;

758 }

759};

760

761

762

763

764

765

766

767

768

769

770

771

772

774

775

776 struct Entry {

777 void *node;

778 unsigned size;

779 unsigned offset;

780

783

786

787 NodeRef &subtree(unsigned i) const {

788 return reinterpret_cast<NodeRef*>(node)[i];

789 }

790 };

791

792

794

795public:

796

797 template NodeT &node(unsigned Level) const {

798 return *reinterpret_cast<NodeT*>(path[Level].node);

799 }

800 unsigned size(unsigned Level) const { return path[Level].size; }

801 unsigned offset(unsigned Level) const { return path[Level].offset; }

802 unsigned &offset(unsigned Level) { return path[Level].offset; }

803

804

805 template NodeT &leaf() const {

806 return *reinterpret_cast<NodeT*>(path.back().node);

807 }

811

812

814 return !path.empty() && path.front().offset < path.front().size;

815 }

816

817

818

819 unsigned height() const { return path.size() - 1; }

820

821

822

823

825 return path[Level].subtree(path[Level].offset);

826 }

827

828

829

831 path[Level] = Entry(subtree(Level - 1), offset(Level));

832 }

833

834

835

836

839 }

840

841

844 }

845

846

847

848

849

852 if (Level)

854 }

855

856

857

858

859

863 }

864

865

866

867

868

869

871

872

873

874

876

877

878

879

880 void moveLeft(unsigned Level);

881

882

883

885 while (height() < Height)

887 }

888

889

890

891

893

894

895

896

898

899

901 for (unsigned i = 0, e = path.size(); i != e; ++i)

902 if (path[i].offset != 0)

903 return false;

904 return true;

905 }

906

907

908

909

911 return path[Level].offset == path[Level].size - 1;

912 }

913

914

915

916

917

918

921 return;

923 ++path[Level].offset;

924 }

925};

926

927}

928

929

930

931

932

933template <typename KeyT, typename ValT,

934 unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,

935 typename Traits = IntervalMapInfo>

943

944

945

946 enum {

947 DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) /

949 RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1

950 };

951

954

955

956 struct RootBranchData {

959 };

960

961public:

966

967private:

968

969 union {

972 };

973

974

975

976

977

978 unsigned height = 0;

979

980

981 unsigned rootSize = 0;

982

983

985

986 const RootLeaf &rootLeaf() const {

987 assert(!branched() && "Cannot acces leaf data in branched root");

989 }

990 RootLeaf &rootLeaf() {

991 assert(!branched() && "Cannot acces leaf data in branched root");

993 }

994

995 const RootBranchData &rootBranchData() const {

996 assert(branched() && "Cannot access branch data in non-branched root");

998 }

999 RootBranchData &rootBranchData() {

1000 assert(branched() && "Cannot access branch data in non-branched root");

1002 }

1003

1004 const RootBranch &rootBranch() const { return rootBranchData().node; }

1005 RootBranch &rootBranch() { return rootBranchData().node; }

1006 KeyT rootBranchStart() const { return rootBranchData().start; }

1007 KeyT &rootBranchStart() { return rootBranchData().start; }

1008

1009 template NodeT *newNode() {

1010 return new (allocator->template Allocate()) NodeT();

1011 }

1012

1013 template void deleteNode(NodeT *P) {

1014 P->~NodeT();

1016 }

1017

1018 IdxPair branchRoot(unsigned Position);

1019 IdxPair splitRoot(unsigned Position);

1020

1021 void switchRootToBranch() {

1022 rootLeaf().~RootLeaf();

1023 height = 1;

1024 new (&rootBranchData()) RootBranchData();

1025 }

1026

1027 void switchRootToLeaf() {

1028 rootBranchData().~RootBranchData();

1029 height = 0;

1030 new(&rootLeaf()) RootLeaf();

1031 }

1032

1033 bool branched() const { return height > 0; }

1034

1035 ValT treeSafeLookup(KeyT x, ValT NotFound) const;

1036 void visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef,

1037 unsigned Level));

1038 void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level);

1039

1040public:

1042 new (&rootLeaf()) RootLeaf();

1043 }

1044

1045

1046

1047

1048

1050

1051

1052 assert(empty() && "Expected emptry tree");

1053 *this = RHS;

1054 }

1058 for (auto It = RHS.begin(), End = RHS.end(); It != End; ++It)

1059 insert(It.start(), It.stop(), It.value());

1060 return *this;

1061 }

1062

1064

1065

1066 assert(empty() && "Expected emptry tree");

1067 *this = std::move(RHS);

1068 }

1070

1072

1073 rootLeaf().~RootLeaf();

1074

1075 height = RHS.height;

1076 rootSize = RHS.rootSize;

1078

1079

1080

1081 if (RHS.branched()) {

1082 rootBranch() = std::move(RHS.rootBranch());

1083

1084

1085 RHS.rootBranch().~RootBranch();

1086 RHS.height = 0;

1088 } else {

1089 rootLeaf() = std::move(RHS.rootLeaf());

1090 }

1091 return *this;

1092 }

1093

1094

1097 rootLeaf().~RootLeaf();

1098 }

1099

1100

1102 return rootSize == 0;

1103 }

1104

1105

1107 assert( empty () && "Empty IntervalMap has no start");

1108 return !branched() ? rootLeaf().start(0) : rootBranchStart();

1109 }

1110

1111

1113 assert( empty () && "Empty IntervalMap has no stop");

1114 return !branched() ? rootLeaf().stop(rootSize - 1) :

1115 rootBranch().stop(rootSize - 1);

1116 }

1117

1118

1120 if (empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))

1121 return NotFound;

1122 return branched() ? treeSafeLookup(x, NotFound) :

1124 }

1125

1126

1127

1128

1131 return find(a).insert(a, b, y);

1132

1133

1134 unsigned p = rootLeaf().findFrom(0, rootSize, a);

1135 rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y);

1136 }

1137

1138

1140

1142 class iterator;

1145

1148 I.goToBegin();

1149 return I;

1150 }

1151

1154 I.goToBegin();

1155 return I;

1156 }

1157

1160 I.goToEnd();

1161 return I;

1162 }

1163

1166 I.goToEnd();

1167 return I;

1168 }

1169

1170

1171

1174 I.find(x);

1175 return I;

1176 }

1177

1180 I.find(x);

1181 return I;

1182 }

1183

1184

1185

1187 assert(Traits::nonEmpty(a, b));

1189 if (.valid())

1190 return false;

1191

1192

1193

1194 return !Traits::stopLess(b, I.start());

1195 }

1196};

1197

1198

1199

1200template <typename KeyT, typename ValT, unsigned N, typename Traits>

1201ValT IntervalMap<KeyT, ValT, N, Traits>::

1202treeSafeLookup(KeyT x, ValT NotFound) const {

1203 assert(branched() && "treeLookup assumes a branched root");

1204

1205 IntervalMapImpl::NodeRef NR = rootBranch().safeLookup(x);

1206 for (unsigned h = height-1; h; --h)

1207 NR = NR.get().safeLookup(x);

1208 return NR.get().safeLookup(x, NotFound);

1209}

1210

1211

1212

1213template <typename KeyT, typename ValT, unsigned N, typename Traits>

1215branchRoot(unsigned Position) {

1216 using namespace IntervalMapImpl;

1217

1218 const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1;

1219

1220

1221 unsigned size[Nodes];

1222 IdxPair NewOffset(0, Position);

1223

1224

1225 if (Nodes == 1)

1226 size[0] = rootSize;

1227 else

1228 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, size,

1229 Position, true);

1230

1231

1232 unsigned pos = 0;

1234 for (unsigned n = 0; n != Nodes; ++n) {

1235 Leaf *L = newNode();

1236 L->copy(rootLeaf(), pos, 0, size[n]);

1237 node[n] = NodeRef(L, size[n]);

1238 pos += size[n];

1239 }

1240

1241

1242 switchRootToBranch();

1243 for (unsigned n = 0; n != Nodes; ++n) {

1244 rootBranch().stop(n) = node[n].template get().stop(size[n]-1);

1245 rootBranch().subtree(n) = node[n];

1246 }

1247 rootBranchStart() = node[0].template get().start(0);

1248 rootSize = Nodes;

1249 return NewOffset;

1250}

1251

1252

1253

1254template <typename KeyT, typename ValT, unsigned N, typename Traits>

1256splitRoot(unsigned Position) {

1257 using namespace IntervalMapImpl;

1258

1259 const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1;

1260

1261

1262 unsigned Size[Nodes];

1263 IdxPair NewOffset(0, Position);

1264

1265

1266 if (Nodes == 1)

1267 Size[0] = rootSize;

1268 else

1269 NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, Size,

1270 Position, true);

1271

1272

1273 unsigned Pos = 0;

1275 for (unsigned n = 0; n != Nodes; ++n) {

1276 Branch *B = newNode();

1277 B->copy(rootBranch(), Pos, 0, Size[n]);

1279 Pos += Size[n];

1280 }

1281

1282 for (unsigned n = 0; n != Nodes; ++n) {

1283 rootBranch().stop(n) = Node[n].template get().stop(Size[n]-1);

1284 rootBranch().subtree(n) = Node[n];

1285 }

1286 rootSize = Nodes;

1287 ++height;

1288 return NewOffset;

1289}

1290

1291

1292template <typename KeyT, typename ValT, unsigned N, typename Traits>

1293void IntervalMap<KeyT, ValT, N, Traits>::

1294visitNodes(void (IntervalMap::*f)(IntervalMapImpl::NodeRef, unsigned Height)) {

1295 if (!branched())

1296 return;

1297 SmallVector<IntervalMapImpl::NodeRef, 4> Refs, NextRefs;

1298

1299

1300 for (unsigned i = 0; i != rootSize; ++i)

1301 Refs.push_back(rootBranch().subtree(i));

1302

1303

1304 for (unsigned h = height - 1; h; --h) {

1305 for (unsigned i = 0, e = Refs.size(); i != e; ++i) {

1306 for (unsigned j = 0, s = Refs[i].size(); j != s; ++j)

1307 NextRefs.push_back(Refs[i].subtree(j));

1308 (this->*f)(Refs[i], h);

1309 }

1310 Refs.clear();

1311 Refs.swap(NextRefs);

1312 }

1313

1314

1315 for (unsigned i = 0, e = Refs.size(); i != e; ++i)

1316 (this->*f)(Refs[i], 0);

1317}

1318

1319template <typename KeyT, typename ValT, unsigned N, typename Traits>

1320void IntervalMap<KeyT, ValT, N, Traits>::

1321deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level) {

1322 if (Level)

1323 deleteNode(&Node.get());

1324 else

1325 deleteNode(&Node.get());

1326}

1327

1328template <typename KeyT, typename ValT, unsigned N, typename Traits>

1331 if (branched()) {

1332 visitNodes(&IntervalMap::deleteNode);

1333 switchRootToLeaf();

1334 }

1335 rootSize = 0;

1336}

1337

1338

1339

1340

1341

1342template <typename KeyT, typename ValT, unsigned N, typename Traits>

1345

1346public:

1352

1353protected:

1354

1356

1357

1358

1360

1363

1365 assert(map && "Invalid iterator");

1366 return map->branched();

1367 }

1368

1370 if (branched())

1371 path.setRoot(&map->rootBranch(), map->rootSize, Offset);

1372 else

1373 path.setRoot(&map->rootLeaf(), map->rootSize, Offset);

1374 }

1375

1379

1380

1382 assert(valid() && "Cannot access invalid iterator");

1385 }

1386

1387

1389 assert(valid() && "Cannot access invalid iterator");

1392 }

1393

1394

1396 assert(valid() && "Cannot access invalid iterator");

1399 }

1400

1401public:

1402

1404

1405

1406

1408

1409

1411

1412

1414

1415

1416 const KeyT &start() const { return unsafeStart(); }

1417

1418

1419 const KeyT &stop() const { return unsafeStop(); }

1420

1421

1422 const ValT &value() const { return unsafeValue(); }

1423

1425

1427 assert(map == RHS.map && "Cannot compare iterators from different maps");

1428 if (!valid())

1429 return RHS .valid();

1431 return false;

1432 return &path.template leaf() == &RHS.path.template leaf();

1433 }

1434

1437 }

1438

1439

1441 setRoot(0);

1442 if (branched())

1444 }

1445

1446

1448 setRoot(map->rootSize);

1449 }

1450

1451

1453 assert(valid() && "Cannot increment end()");

1456 return *this;

1457 }

1458

1459

1462 operator++();

1463 return tmp;

1464 }

1465

1466

1468 if (path.leafOffset() && (valid() || !branched()))

1470 else

1472 return *this;

1473 }

1474

1475

1478 operator--();

1479 return tmp;

1480 }

1481

1482

1483

1485 if (branched())

1486 treeFind(x);

1487 else

1488 setRoot(map->rootLeaf().findFrom(0, map->rootSize, x));

1489 }

1490

1491

1492

1493

1495 if (!valid())

1496 return;

1497 if (branched())

1498 treeAdvanceTo(x);

1499 else

1502 }

1503};

1504

1505

1506

1507template <typename KeyT, typename ValT, unsigned N, typename Traits>

1511 for (unsigned i = map->height - path.height() - 1; i; --i) {

1512 unsigned p = NR.get<Branch>().safeFind(0, x);

1513 path.push(NR, p);

1515 }

1517}

1518

1519

1520

1521template <typename KeyT, typename ValT, unsigned N, typename Traits>

1524 setRoot(map->rootBranch().findFrom(0, map->rootSize, x));

1525 if (valid())

1526 pathFillFind(x);

1527}

1528

1529

1530

1531template <typename KeyT, typename ValT, unsigned N, typename Traits>

1534

1535 if (!Traits::stopLess(path.leaf<Leaf>().stop(path.leafSize() - 1), x)) {

1536 path.leafOffset() = path.leaf<Leaf>().safeFind(path.leafOffset(), x);

1537 return;

1538 }

1539

1540

1541 path.pop();

1542

1543

1544 if (path.height()) {

1545 for (unsigned l = path.height() - 1; l; --l) {

1546 if (!Traits::stopLess(path.node<Branch>(l).stop(path.offset(l)), x)) {

1547

1548 path.offset(l + 1) =

1549 path.node<Branch>(l + 1).safeFind(path.offset(l + 1), x);

1550 return pathFillFind(x);

1551 }

1552 path.pop();

1553 }

1554

1555 if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) {

1556 path.offset(1) = path.node<Branch>(1).safeFind(path.offset(1), x);

1557 return pathFillFind(x);

1558 }

1559 }

1560

1561

1562 setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x));

1563 if (valid())

1564 pathFillFind(x);

1565}

1566

1567

1568

1569

1570

1571template <typename KeyT, typename ValT, unsigned N, typename Traits>

1574

1576

1578

1579 void setNodeStop(unsigned Level, KeyT Stop);

1581 template bool overflow(unsigned Level);

1583 void eraseNode(unsigned Level);

1584 void treeErase(bool UpdateRoot = true);

1585 bool canCoalesceLeft(KeyT Start, ValT x);

1586 bool canCoalesceRight(KeyT Stop, ValT x);

1587

1588public:

1589

1591

1592

1593

1594

1596

1597

1598

1599

1601

1602

1603

1604

1606

1607

1608

1609

1610

1612

1613

1614

1615

1616

1618 this->unsafeStop() = b;

1619

1620 if (this->path.atLastEntry(this->path.height()))

1621 setNodeStop(this->path.height(), b);

1622 }

1623

1624

1625

1626

1628

1629

1631

1632

1634

1637 return *this;

1638 }

1639

1642 operator++();

1643 return tmp;

1644 }

1645

1648 return *this;

1649 }

1650

1653 operator--();

1654 return tmp;

1655 }

1656};

1657

1658

1659

1660

1661

1662

1663template <typename KeyT, typename ValT, unsigned N, typename Traits>

1666 using namespace IntervalMapImpl;

1667 Path &P = this->path;

1668 if (!this->branched()) {

1669 unsigned i = P.leafOffset();

1670 RootLeaf &Node = P.leaf();

1671 return i && Node.value(i-1) == Value &&

1672 Traits::adjacent(Node.stop(i-1), Start);

1673 }

1674

1675 if (unsigned i = P.leafOffset()) {

1676 Leaf &Node = P.leaf();

1677 return Node.value(i-1) == Value && Traits::adjacent(Node.stop(i-1), Start);

1678 } else if (NodeRef NR = P.getLeftSibling(P.height())) {

1679 unsigned i = NR.size() - 1;

1680 Leaf &Node = NR.get();

1681 return Node.value(i) == Value && Traits::adjacent(Node.stop(i), Start);

1682 }

1683 return false;

1684}

1685

1686

1687

1688

1689

1690

1691template <typename KeyT, typename ValT, unsigned N, typename Traits>

1692bool IntervalMap<KeyT, ValT, N, Traits>::

1693iterator::canCoalesceRight(KeyT Stop, ValT Value) {

1694 using namespace IntervalMapImpl;

1695 Path &P = this->path;

1696 unsigned i = P.leafOffset() + 1;

1697 if (!this->branched()) {

1698 if (i >= P.leafSize())

1699 return false;

1700 RootLeaf &Node = P.leaf();

1701 return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));

1702 }

1703

1704 if (i < P.leafSize()) {

1705 Leaf &Node = P.leaf();

1706 return Node.value(i) == Value && Traits::adjacent(Stop, Node.start(i));

1707 } else if (NodeRef NR = P.getRightSibling(P.height())) {

1708 Leaf &Node = NR.get();

1709 return Node.value(0) == Value && Traits::adjacent(Stop, Node.start(0));

1710 }

1711 return false;

1712}

1713

1714

1715template <typename KeyT, typename ValT, unsigned N, typename Traits>

1716void IntervalMap<KeyT, ValT, N, Traits>::

1717iterator::setNodeStop(unsigned Level, KeyT Stop) {

1718

1719 if (!Level)

1720 return;

1721 IntervalMapImpl::Path &P = this->path;

1722

1723 while (--Level) {

1724 P.node<Branch>(Level).stop(P.offset(Level)) = Stop;

1725 if (.atLastEntry(Level))

1726 return;

1727 }

1728

1729 P.node(Level).stop(P.offset(Level)) = Stop;

1730}

1731

1732template <typename KeyT, typename ValT, unsigned N, typename Traits>

1735 assert(Traits::nonEmpty(a, this->stop()) && "Cannot move start beyond stop");

1736 KeyT &CurStart = this->unsafeStart();

1737 if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) {

1738 CurStart = a;

1739 return;

1740 }

1741

1742 --*this;

1743 a = this->start();

1745 setStartUnchecked(a);

1746}

1747

1748template <typename KeyT, typename ValT, unsigned N, typename Traits>

1751 assert(Traits::nonEmpty(this->start(), b) && "Cannot move stop beyond start");

1752 if (Traits::startLess(b, this->stop()) ||

1753 !canCoalesceRight(b, this->value())) {

1754 setStopUnchecked(b);

1755 return;

1756 }

1757

1758 KeyT a = this->start();

1760 setStartUnchecked(a);

1761}

1762

1763template <typename KeyT, typename ValT, unsigned N, typename Traits>

1766 setValueUnchecked(x);

1767 if (canCoalesceRight(this->stop(), x)) {

1768 KeyT a = this->start();

1770 setStartUnchecked(a);

1771 }

1772 if (canCoalesceLeft(this->start(), x)) {

1773 --*this;

1774 KeyT a = this->start();

1776 setStartUnchecked(a);

1777 }

1778}

1779

1780

1781

1782

1783

1784

1785

1786template <typename KeyT, typename ValT, unsigned N, typename Traits>

1789 assert(Level && "Cannot insert next to the root");

1790 bool SplitRoot = false;

1793

1794 if (Level == 1) {

1795

1796 if (IM.rootSize < RootBranch::Capacity) {

1797 IM.rootBranch().insert(P.offset(0), IM.rootSize, Node, Stop);

1798 P.setSize(0, ++IM.rootSize);

1799 P.reset(Level);

1800 return SplitRoot;

1801 }

1802

1803

1804 SplitRoot = true;

1805 IdxPair Offset = IM.splitRoot(P.offset(0));

1806 P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);

1807

1808

1809 ++Level;

1810 }

1811

1812

1813 P.legalizeForInsert(--Level);

1814

1815

1816 if (P.size(Level) == Branch::Capacity) {

1817

1818 assert(!SplitRoot && "Cannot overflow after splitting the root");

1819 SplitRoot = overflow(Level);

1820 Level += SplitRoot;

1821 }

1822 P.node<Branch>(Level).insert(P.offset(Level), P.size(Level), Node, Stop);

1823 P.setSize(Level, P.size(Level) + 1);

1824 if (P.atLastEntry(Level))

1825 setNodeStop(Level, Stop);

1826 P.reset(Level + 1);

1827 return SplitRoot;

1828}

1829

1830

1831template <typename KeyT, typename ValT, unsigned N, typename Traits>

1834 if (this->branched())

1835 return treeInsert(a, b, y);

1838

1839

1840 unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);

1841

1842

1843 if (Size <= RootLeaf::Capacity) {

1844 P.setSize(0, IM.rootSize = Size);

1845 return;

1846 }

1847

1848

1849 IdxPair Offset = IM.branchRoot(P.leafOffset());

1850 P.replaceRoot(&IM.rootBranch(), IM.rootSize, Offset);

1851

1852

1853 treeInsert(a, b, y);

1854}

1855

1856template <typename KeyT, typename ValT, unsigned N, typename Traits>

1859 using namespace IntervalMapImpl;

1860 Path &P = this->path;

1861

1862 if (.valid())

1863 P.legalizeForInsert(this->map->height);

1864

1865

1866 if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) {

1867

1868 if (NodeRef Sib = P.getLeftSibling(P.height())) {

1869 Leaf &SibLeaf = Sib.get<Leaf>();

1870 unsigned SibOfs = Sib.size() - 1;

1871 if (SibLeaf.value(SibOfs) == y &&

1872 Traits::adjacent(SibLeaf.stop(SibOfs), a)) {

1873

1874

1875

1876

1877

1879 P.moveLeft(P.height());

1880 if (Traits::stopLess(b, CurLeaf.start(0)) &&

1881 (y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) {

1882

1883 setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b);

1884 return;

1885 } else {

1886

1887

1888 a = SibLeaf.start(SibOfs);

1889 treeErase(false);

1890 }

1891 }

1892 } else {

1893

1894 this->map->rootBranchStart() = a;

1895 }

1896 }

1897

1898

1899 unsigned Size = P.leafSize();

1900 bool Grow = P.leafOffset() == Size;

1901 Size = P.leaf().insertFrom(P.leafOffset(), Size, a, b, y);

1902

1903

1904 if (Size > Leaf::Capacity) {

1905 overflow(P.height());

1906 Grow = P.leafOffset() == P.leafSize();

1907 Size = P.leaf().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);

1908 assert(Size <= Leaf::Capacity && "overflow() didn't make room");

1909 }

1910

1911

1912 P.setSize(P.height(), Size);

1913

1914

1915 if (Grow)

1916 setNodeStop(P.height(), b);

1917}

1918

1919

1920template <typename KeyT, typename ValT, unsigned N, typename Traits>

1925 assert(P.valid() && "Cannot erase end()");

1926 if (this->branched())

1927 return treeErase();

1928 IM.rootLeaf().erase(P.leafOffset(), IM.rootSize);

1929 P.setSize(0, --IM.rootSize);

1930}

1931

1932

1933template <typename KeyT, typename ValT, unsigned N, typename Traits>

1939

1940

1941 if (P.leafSize() == 1) {

1942 IM.deleteNode(&Node);

1943 eraseNode(IM.height);

1944

1945 if (UpdateRoot && IM.branched() && P.valid() && P.atBegin())

1946 IM.rootBranchStart() = P.leaf<Leaf>().start(0);

1947 return;

1948 }

1949

1950

1951 Node.erase(P.leafOffset(), P.leafSize());

1952 unsigned NewSize = P.leafSize() - 1;

1953 P.setSize(IM.height, NewSize);

1954

1955 if (P.leafOffset() == NewSize) {

1956 setNodeStop(IM.height, Node.stop(NewSize - 1));

1957 P.moveRight(IM.height);

1958 } else if (UpdateRoot && P.atBegin())

1959 IM.rootBranchStart() = P.leaf().start(0);

1960}

1961

1962

1963

1964

1965

1966template <typename KeyT, typename ValT, unsigned N, typename Traits>

1967void IntervalMap<KeyT, ValT, N, Traits>::

1968iterator::eraseNode(unsigned Level) {

1969 assert(Level && "Cannot erase root node");

1970 IntervalMap &IM = *this->map;

1971 IntervalMapImpl::Path &P = this->path;

1972

1973 if (--Level == 0) {

1974 IM.rootBranch().erase(P.offset(0), IM.rootSize);

1975 P.setSize(0, --IM.rootSize);

1976

1977 if (IM.empty()) {

1978 IM.switchRootToLeaf();

1979 this->setRoot(0);

1980 return;

1981 }

1982 } else {

1983

1985 if (P.size(Level) == 1) {

1986

1987 IM.deleteNode(&Parent);

1988 eraseNode(Level);

1989 } else {

1990

1991 Parent.erase(P.offset(Level), P.size(Level));

1992 unsigned NewSize = P.size(Level) - 1;

1993 P.setSize(Level, NewSize);

1994

1995 if (P.offset(Level) == NewSize) {

1996 setNodeStop(Level, Parent.stop(NewSize - 1));

1997 P.moveRight(Level);

1998 }

1999 }

2000 }

2001

2002 if (P.valid()) {

2003 P.reset(Level + 1);

2004 P.offset(Level + 1) = 0;

2005 }

2006}

2007

2008

2009

2010

2011

2012

2013

2014template <typename KeyT, typename ValT, unsigned N, typename Traits>

2015template

2016bool IntervalMap<KeyT, ValT, N, Traits>::

2017iterator::overflow(unsigned Level) {

2018 using namespace IntervalMapImpl;

2019 Path &P = this->path;

2020 unsigned CurSize[4];

2021 NodeT *Node[4];

2022 unsigned Nodes = 0;

2024 unsigned Offset = P.offset(Level);

2025

2026

2027 NodeRef LeftSib = P.getLeftSibling(Level);

2028 if (LeftSib) {

2029 Offset += Elements = CurSize[Nodes] = LeftSib.size();

2030 Node[Nodes++] = &LeftSib.get();

2031 }

2032

2033

2034 Elements += CurSize[Nodes] = P.size(Level);

2035 Node[Nodes++] = &P.node(Level);

2036

2037

2038 NodeRef RightSib = P.getRightSibling(Level);

2039 if (RightSib) {

2040 Elements += CurSize[Nodes] = RightSib.size();

2041 Node[Nodes++] = &RightSib.get();

2042 }

2043

2044

2045 unsigned NewNode = 0;

2046 if (Elements + 1 > Nodes * NodeT::Capacity) {

2047

2048 NewNode = Nodes == 1 ? 1 : Nodes - 1;

2049 CurSize[Nodes] = CurSize[NewNode];

2050 Node[Nodes] = Node[NewNode];

2051 CurSize[NewNode] = 0;

2052 Node[NewNode] = this->map->template newNode();

2053 ++Nodes;

2054 }

2055

2056

2057 unsigned NewSize[4];

2058 IdxPair NewOffset = distribute(Nodes, Elements, NodeT::Capacity,

2059 CurSize, NewSize, Offset, true);

2061

2062

2063 if (LeftSib)

2064 P.moveLeft(Level);

2065

2066

2067 bool SplitRoot = false;

2068 unsigned Pos = 0;

2069 while (true) {

2070 KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);

2071 if (NewNode && Pos == NewNode) {

2072 SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop);

2073 Level += SplitRoot;

2074 } else {

2075 P.setSize(Level, NewSize[Pos]);

2076 setNodeStop(Level, Stop);

2077 }

2078 if (Pos + 1 == Nodes)

2079 break;

2080 P.moveRight(Level);

2081 ++Pos;

2082 }

2083

2084

2085 while(Pos != NewOffset.first) {

2086 P.moveLeft(Level);

2087 --Pos;

2088 }

2089 P.offset(Level) = NewOffset.second;

2090 return SplitRoot;

2091}

2092

2093

2094

2095

2096

2097

2098

2099

2100

2101

2102

2103

2104

2105

2106

2107

2108

2109template <typename MapA, typename MapB>

2111 using KeyType = typename MapA::KeyType;

2112 using Traits = typename MapA::KeyTraits;

2113

2114 typename MapA::const_iterator posA;

2115 typename MapB::const_iterator posB;

2116

2117

2118

2119

2120 void advance() {

2122 return;

2123

2124 if (Traits::stopLess(posA.stop(), posB.start())) {

2125

2127 if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))

2128 return;

2129 } else if (Traits::stopLess(posB.stop(), posA.start())) {

2130

2131 posB.advanceTo(posA.start());

2132 if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))

2133 return;

2134 } else

2135

2136 return;

2137

2138 while (true) {

2139

2140 posA.advanceTo(posB.start());

2141 if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))

2142 return;

2143

2144 posB.advanceTo(posA.start());

2145 if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))

2146 return;

2147 }

2148 }

2149

2150public:

2151

2153 : posA(b.empty() ? a.end() : a.find(b.start())),

2154 posB(posA.valid() ? b.find(posA.start()) : b.end()) { advance(); }

2155

2156

2158 return posA.valid() && posB.valid();

2159 }

2160

2161

2162 const typename MapA::const_iterator &a() const { return posA; }

2163

2164

2165 const typename MapB::const_iterator &b() const { return posB; }

2166

2167

2169 KeyType ak = a().start();

2170 KeyType bk = b().start();

2171 return Traits::startLess(ak, bk) ? bk : ak;

2172 }

2173

2174

2176 KeyType ak = a().stop();

2177 KeyType bk = b().stop();

2178 return Traits::startLess(ak, bk) ? ak : bk;

2179 }

2180

2181

2183 ++posA;

2184 advance();

2185 }

2186

2187

2189 ++posB;

2190 advance();

2191 }

2192

2193

2195

2196 if (Traits::startLess(posB.stop(), posA.stop()))

2198 else

2200 return *this;

2201 }

2202

2203

2204

2207 return;

2208

2209 if (Traits::stopLess(posA.stop(), x))

2210 posA.advanceTo(x);

2211 if (Traits::stopLess(posB.stop(), x))

2212 posB.advanceTo(x);

2213 advance();

2214 }

2215};

2216

2217}

2218

2219#endif

This file defines the BumpPtrAllocator interface.

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

Given that RA is a live value

This file defines the PointerIntPair class.

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

This file defines the SmallVector class.

const NodeRef & subtree(unsigned i) const

NodeRef & subtree(unsigned i)

unsigned safeFind(unsigned i, KeyT x) const

safeFind - Find a subtree that is known to exist.

const KeyT & stop(unsigned i) const

unsigned findFrom(unsigned i, unsigned Size, KeyT x) const

findFrom - Find the first subtree after i that may contain x.

NodeRef safeLookup(KeyT x) const

safeLookup - Get the subtree containing x, Assuming that x is in range.

void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop)

insert - Insert a new (subtree, stop) pair.

unsigned safeFind(unsigned i, KeyT x) const

safeFind - Find an interval that is known to exist.

const KeyT & stop(unsigned i) const

const ValT & value(unsigned i) const

ValT safeLookup(KeyT x, ValT NotFound) const

safeLookup - Lookup mapped value for a safe key.

unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y)

insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as possible.

const KeyT & start(unsigned i) const

unsigned findFrom(unsigned i, unsigned Size, KeyT x) const

findFrom - Find the first interval after i that may contain x.

void erase(unsigned i, unsigned j, unsigned Size)

erase - Erase elements [i;j).

void moveLeft(unsigned i, unsigned j, unsigned Count)

moveLeft - Move elements to the left.

void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count)

transferToLeftSib - Transfer elements to a left sibling node.

void copy(const NodeBase< T1, T2, M > &Other, unsigned i, unsigned j, unsigned Count)

copy - Copy elements from another node.

static constexpr unsigned Capacity

int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add)

adjustFromLeftSib - Adjust the number if elements in this node by moving elements to or from a left s...

void shift(unsigned i, unsigned Size)

shift - Shift elements [i;size) 1 position to the right.

void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count)

transferToRightSib - Transfer elements to a right sibling node.

void erase(unsigned i, unsigned Size)

erase - Erase element at i.

void moveRight(unsigned i, unsigned j, unsigned Count)

moveRight - Move elements to the right.

unsigned size() const

size - Return the number of elements in the referenced node.

bool operator!=(const NodeRef &RHS) const

void setSize(unsigned n)

setSize - Update the node size.

bool operator==(const NodeRef &RHS) const

NodeT & get() const

get - Dereference as a NodeT reference.

NodeRef(NodeT *p, unsigned n)

NodeRef - Create a reference to the node p with n elements.

NodeRef & subtree(unsigned i) const

subtree - Access the i'th subtree reference in a branch node.

NodeRef()=default

NodeRef - Create a null ref.

void replaceRoot(void *Root, unsigned Size, IdxPair Offsets)

replaceRoot - Replace the current root node with two new entries after the tree height has increased.

unsigned & offset(unsigned Level)

bool valid() const

valid - Return true if path is at a valid node, not at end().

void reset(unsigned Level)

reset - Reset cached information about node(Level) from subtree(Level -1).

NodeRef getLeftSibling(unsigned Level) const

getLeftSibling - Get the left sibling node at Level, or a null NodeRef.

void setRoot(void *Node, unsigned Size, unsigned Offset)

setRoot - Clear the path and set a new root node.

unsigned offset(unsigned Level) const

unsigned leafOffset() const

NodeT & node(unsigned Level) const

bool atLastEntry(unsigned Level) const

atLastEntry - Return true if the path is at the last entry of the node at Level.

unsigned leafSize() const

bool atBegin() const

atBegin - Return true if path is at begin().

unsigned height() const

height - Return the height of the tree corresponding to this path.

void moveRight(unsigned Level)

moveRight - Move path to the left sibling at Level.

void pop()

pop - Remove the last path entry.

void setSize(unsigned Level, unsigned Size)

setSize - Set the size of a node both in the path and in the tree.

NodeRef getRightSibling(unsigned Level) const

getLeftSibling - Get the left sibling node at Level, or a null NodeRef.

void fillLeft(unsigned Height)

fillLeft - Grow path to Height by taking leftmost branches.

void legalizeForInsert(unsigned Level)

legalizeForInsert - Prepare the path for an insertion at Level.

unsigned size(unsigned Level) const

void moveLeft(unsigned Level)

moveLeft - Move path to the left sibling at Level.

void push(NodeRef Node, unsigned Offset)

push - Add entry to path.

NodeRef & subtree(unsigned Level) const

subtree - Get the subtree referenced from Level.

IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two IntervalMaps.

IntervalMapOverlaps & operator++()

Preincrement - Move to the next overlap.

void skipB()

skipB - Move to the next overlap that doesn't involve b().

void skipA()

skipA - Move to the next overlap that doesn't involve a().

IntervalMapOverlaps(const MapA &a, const MapB &b)

IntervalMapOverlaps - Create an iterator for the overlaps of a and b.

KeyType start() const

start - Beginning of the overlapping interval.

const MapA::const_iterator & a() const

a - access the left hand side in the overlap.

void advanceTo(KeyType x)

advanceTo - Move to the first overlapping interval with stopLess(x, stop()).

bool valid() const

valid - Return true if iterator is at an overlap.

const MapB::const_iterator & b() const

b - access the right hand side in the overlap.

KeyType stop() const

stop - End of the overlapping interval.

void setMap(const IntervalMap &m)

setMap - Change the map iterated over.

const_iterator(const IntervalMap &map)

const_iterator()=default

const_iterator - Create an iterator that isn't pointing anywhere.

void advanceTo(KeyT x)

advanceTo - Move to the first interval with stop >= x, or end().

void pathFillFind(KeyT x)

pathFillFind - Complete path by searching for x.

bool operator==(const const_iterator &RHS) const

bool operator!=(const const_iterator &RHS) const

void goToEnd()

goToEnd - Move beyond the last interval in map.

const KeyT & stop() const

stop - Return the end of the current interval.

KeyT & unsafeStop() const

unsafeStop - Writable access to stop() for iterator.

const_iterator & operator++()

preincrement - Move to the next interval.

bool valid() const

valid - Return true if the current position is valid, false for end().

const KeyT & start() const

start - Return the beginning of the current interval.

void treeAdvanceTo(KeyT x)

treeAdvanceTo - Find position after the current one.

ValT & unsafeValue() const

unsafeValue - Writable access to value() for iterator.

const ValT & operator*() const

std::bidirectional_iterator_tag iterator_category

const ValT & value() const

value - Return the mapped value at the current interval.

const_iterator operator--(int)

postdecrement - Don't do that!

IntervalMapImpl::Path path

void setRoot(unsigned Offset)

void treeFind(KeyT x)

treeFind - Find in a branched tree.

bool atBegin() const

atBegin - Return true if the current position is the first map entry.

std::ptrdiff_t difference_type

void find(KeyT x)

find - Move to the first interval with stop >= x, or end().

const_iterator & operator--()

predecrement - Move to the previous interval.

KeyT & unsafeStart() const

unsafeStart - Writable access to start() for iterator.

void goToBegin()

goToBegin - Move to the first interval in map.

const_iterator operator++(int)

postincrement - Don't do that!

void insert(KeyT a, KeyT b, ValT y)

insert - Insert mapping [a;b] -> y before the current position.

void setValueUnchecked(ValT x)

setValueUnchecked - Change the mapped value of the current interval without checking for coalescing.

iterator()=default

iterator - Create null iterator.

void setStart(KeyT a)

setStart - Move the start of the current interval.

void erase()

erase - Erase the current interval.

void setValue(ValT x)

setValue - Change the mapped value of the current interval.

void setStartUnchecked(KeyT a)

setStartUnchecked - Move the start of the current interval without checking for coalescing or overlap...

void setStop(KeyT b)

setStop - Move the end of the current interval.

void setStopUnchecked(KeyT b)

setStopUnchecked - Move the end of the current interval without checking for coalescing or overlaps.

const_iterator begin() const

void insert(KeyT a, KeyT b, ValT y)

insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.

ValT lookup(KeyT x, ValT NotFound=ValT()) const

lookup - Return the mapped value at x or NotFound.

KeyT stop() const

stop - Return the largest mapped key in a non-empty map.

IntervalMap & operator=(IntervalMap const &RHS)

typename Sizer::Allocator Allocator

IntervalMap & operator=(IntervalMap &&RHS)

IntervalMap(IntervalMap &&RHS)

const_iterator find(KeyT x) const

find - Return an iterator pointing to the first interval ending at or after x, or end().

RootBranchData branchData

IntervalMap(IntervalMap const &RHS)

bool overlaps(KeyT a, KeyT b) const

overlaps(a, b) - Return true if the intervals in this map overlap with the interval [a;b].

bool empty() const

empty - Return true when no intervals are mapped.

const_iterator end() const

KeyT start() const

start - Return the smallest mapped key in a non-empty map.

void clear()

clear - Remove all entries.

IntervalMap(Allocator &a)

PointerIntPair - This class implements a pair of a pointer and small integer.

void setInt(IntType IntVal) &

void * getOpaqueValue() const

PointerTy getPointer() const

RecyclingAllocator - This class wraps an Allocator, adding the functionality of recycling deleted obj...

void push_back(const T &Elt)

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

LLVM Value Representation.

std::pair< unsigned, unsigned > IdxPair

void adjustSiblingSizes(NodeT *Node[], unsigned Nodes, unsigned CurSize[], const unsigned NewSize[])

IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.

IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, const unsigned *CurSize, unsigned NewSize[], unsigned Position, bool Grow)

IntervalMapImpl::distribute - Compute a new distribution of node elements after an overflow or underf...

std::pair< NodeId, LaneBitmask > NodeRef

This is an optimization pass for GlobalISel generic memory operations.

auto find(R &&Range, const T &Val)

Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.

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.

bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)

void erase(Container &C, ValueType V)

Wrapper function to remove a value from a container:

static bool startLess(const T &x, const T &a)

startLess - Return true if x is not in [a;b).

static bool adjacent(const T &a, const T &b)

adjacent - Return true when the intervals [x;a) and [b;y) can coalesce.

static bool stopLess(const T &b, const T &x)

stopLess - Return true if x is not in [a;b).

static bool nonEmpty(const T &a, const T &b)

nonEmpty - Return true if [a;b) is non-empty.

NodeBase< std::pair< KeyT, KeyT >, ValT, LeafSize > LeafBase

RecyclingAllocator< BumpPtrAllocator, char, AllocBytes, CacheLineBytes > Allocator

Allocator - The recycling allocator used for both branch and leaf nodes.

static bool startLess(const T &x, const T &a)

startLess - Return true if x is not in [a;b].

static bool adjacent(const T &a, const T &b)

adjacent - Return true when the intervals [x;a] and [b;y] can coalesce.

static bool nonEmpty(const T &a, const T &b)

nonEmpty - Return true if [a;b] is non-empty.

static bool stopLess(const T &b, const T &x)

stopLess - Return true if x is not in [a;b].