IntervalMap.h Source File (original) (raw)

100

101

102

103

104#ifndef LLVM_ADT_INTERVALMAP_H

105#define LLVM_ADT_INTERVALMAP_H

106

112#include

113#include

114#include

115#include

116#include

117

118namespace llvm {

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140template

142

143

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

145 return x < a;

146 }

147

148

149

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

151 return b < x;

152 }

153

154

155

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

157 return a+1 == b;

158 }

159

160

161

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

163 return a <= b;

164 }

165};

166

167template

169

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

171 return x < a;

172 }

173

174

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

176 return b <= x;

177 }

178

179

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

181 return a == b;

182 }

183

184

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

186 return a < b;

187 }

188};

189

190

191

193

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

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

222

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

225public:

227

230

231

232

233

234

235

236 template

238 unsigned j, unsigned Count) {

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

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

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

244 }

245 }

246

247

248

249

250

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

254 }

255

256

257

258

259

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

263 while (Count--) {

266 }

267 }

268

269

270

271

272

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

275 }

276

277

278

279

283

284

285

286

290

291

292

293

294

295

301

302

303

304

305

306

308 unsigned Count) {

311 }

312

313

314

315

316

317

318

319

321 if (Add > 0) {

322

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

326 } else {

327

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

331 }

332 }

333};

334

335

336

337

338

339

340template

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

343

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

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

346 continue;

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

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

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

350 CurSize[m] -= d;

351 CurSize[n] += d;

352

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

354 break;

355 }

356 }

357

358 if (Nodes == 0)

359 return;

360

361

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

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

364 continue;

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

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

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

368 CurSize[m] += d;

369 CurSize[n] -= d;

370

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

372 break;

373 }

374 }

375

376#ifndef NDEBUG

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

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

379#endif

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

414

416 unsigned Capacity, const unsigned *CurSize,

417 unsigned NewSize[], unsigned Position, bool Grow);

418

419

420

421

422

423

424

425

426

427

428

429

430

431enum {

432

433

437};

438

439template <typename KeyT, typename ValT>

441 enum {

442

443

444

445

446

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

451 };

452

454

455 enum {

456

457

459

460

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

463 };

464

465

466

467

468

471};

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

495 struct CacheAlignedPointerTraits {

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

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

498 static constexpr int NumLowBitsAvailable = Log2CacheLine;

499 };

501

502public:

503

505

506

507 explicit operator bool() const { return pip.getOpaqueValue(); }

508

509

510 template

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

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

513 }

514

515

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

517

518

519 void setSize(unsigned n) { pip.setInt(n - 1); }

520

521

522

523

525 return reinterpret_cast<NodeRef*>(pip.getPointer())[i];

526 }

527

528

529 template

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

532 }

533

535 if (pip == RHS.pip)

536 return true;

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

538 return false;

539 }

540

544};

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

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

568public:

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

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

572

576

577

578

579

580

581

582

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

586 "Index is past the needed point");

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

588 return i;

589 }

590

591

592

593

594

595

596

597

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

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

601 "Index is past the needed point");

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

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

604 return i;

605 }

606

607

608

609

610

611

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

615 }

616

618};

619

620

621

622

623

624

625

626

627

628

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

632 unsigned i = Pos;

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

635

636

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

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

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

640

641

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

643 Pos = i - 1;

644

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

648 return Size - 1;

649 }

650 stop(i - 1) = b;

652 }

653

654

655 if (i == N)

656 return N + 1;

657

658

659 if (i == Size) {

663 return Size + 1;

664 }

665

666

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

670 }

671

672

674 return N + 1;

675

676

681 return Size + 1;

682}

683

684

685

686

687

688

689

690

691

692

693

694

695

696

697

698

699

700

701

702

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

705public:

708

711

712

713

714

715

716

717

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

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

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

723 return i;

724 }

725

726

727

728

729

730

731

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

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

735 "Index is past the needed point");

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

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

738 return i;

739 }

740

741

742

743

747

748

749

750

751

752

760};

761

762

763

764

765

766

767

768

769

770

771

772

773

775

776

777 struct Entry {

779 unsigned size;

781

784

787

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

790 }

791 };

792

793

795

796public:

797

798 template NodeT &node(unsigned Level) const {

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

800 }

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

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

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

804

805

806 template NodeT &leaf() const {

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

808 }

809 unsigned leafSize() const { return path.back().size; }

810 unsigned leafOffset() const { return path.back().offset; }

811 unsigned &leafOffset() { return path.back().offset; }

812

813

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

816 }

817

818

819

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

821

822

823

824

828

829

830

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

833 }

834

835

836

837

841

842

844 path.pop_back();

845 }

846

847

848

849

850

852 path[Level].size = Size;

853 if (Level)

855 }

856

857

858

859

860

865

866

867

868

869

870

872

873

874

875

877

878

879

880

881 LLVM_ABI void moveLeft(unsigned Level);

882

883

884

886 while (height() < Height)

888 }

889

890

891

892

894

895

896

897

898 LLVM_ABI void moveRight(unsigned Level);

899

900

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

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

904 return false;

905 return true;

906 }

907

908

909

910

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

913 }

914

915

916

917

918

919

922 return;

924 ++path[Level].offset;

925 }

926};

927

928}

929

930

931

932

933

934template <typename KeyT, typename ValT,

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

936 typename Traits = IntervalMapInfo>

940 using Branch =

944

945

946

947 enum {

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

950 RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1

951 };

952

953 using RootBranch =

955

956

957 struct RootBranchData {

959 RootBranch node;

960 };

961

962public:

967

968private:

969

970 union {

973 };

974

975

976

977

978

979 unsigned height = 0;

980

981

982 unsigned rootSize = 0;

983

984

986

987 const RootLeaf &rootLeaf() const {

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

989 return leaf;

990 }

991 RootLeaf &rootLeaf() {

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

993 return leaf;

994 }

995

996 const RootBranchData &rootBranchData() const {

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

998 return branchData;

999 }

1000 RootBranchData &rootBranchData() {

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

1002 return branchData;

1003 }

1004

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

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

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

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

1009

1010 template NodeT *newNode() {

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

1012 }

1013

1014 template void deleteNode(NodeT *P) {

1015 P->~NodeT();

1017 }

1018

1019 IdxPair branchRoot(unsigned Position);

1020 IdxPair splitRoot(unsigned Position);

1021

1022 void switchRootToBranch() {

1023 rootLeaf().~RootLeaf();

1024 height = 1;

1025 new (&rootBranchData()) RootBranchData();

1026 }

1027

1028 void switchRootToLeaf() {

1029 rootBranchData().~RootBranchData();

1030 height = 0;

1031 new(&rootLeaf()) RootLeaf();

1032 }

1033

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

1035

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

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

1038 unsigned Level));

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

1040

1041public:

1043 new (&rootLeaf()) RootLeaf();

1044 }

1045

1046

1047

1048

1049

1051

1052

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

1054 *this = RHS;

1055 }

1058 allocator = RHS.allocator;

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

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

1061 return *this;

1062 }

1063

1065

1066

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

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

1069 }

1071

1073

1074 rootLeaf().~RootLeaf();

1075

1076 height = RHS.height;

1077 rootSize = RHS.rootSize;

1078 allocator = RHS.allocator;

1079

1080

1081

1082 if (RHS.branched()) {

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

1084

1085

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

1087 RHS.height = 0;

1088 new (&RHS.rootLeaf()) RootLeaf();

1089 } else {

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

1091 }

1092 return *this;

1093 }

1094

1095

1098 rootLeaf().~RootLeaf();

1099 }

1100

1101

1103 return rootSize == 0;

1104 }

1105

1106

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

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

1110 }

1111

1112

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

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

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

1117 }

1118

1119

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

1122 return NotFound;

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

1124 rootLeaf().safeLookup(x, NotFound);

1125 }

1126

1127

1128

1129

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

1133

1134

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

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

1137 }

1138

1139

1141

1142 class const_iterator;

1143 class iterator;

1144 friend class const_iterator;

1145 friend class iterator;

1146

1148 const_iterator I(*this);

1149 I.goToBegin();

1150 return I;

1151 }

1152

1154 iterator I(*this);

1155 I.goToBegin();

1156 return I;

1157 }

1158

1159 const_iterator end() const {

1160 const_iterator I(*this);

1161 I.goToEnd();

1162 return I;

1163 }

1164

1166 iterator I(*this);

1167 I.goToEnd();

1168 return I;

1169 }

1170

1171

1172

1174 const_iterator I(*this);

1175 I.find(x);

1176 return I;

1177 }

1178

1180 iterator I(*this);

1181 I.find(x);

1182 return I;

1183 }

1184

1185

1186

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

1189 const_iterator I = find(a);

1190 if (.valid())

1191 return false;

1192

1193

1194

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

1196 }

1197};

1198

1199

1200

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

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

1203treeSafeLookup(KeyT x, ValT NotFound) const {

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

1205

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

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

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

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

1210}

1211

1212

1213

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

1216branchRoot(unsigned Position) {

1217 using namespace IntervalMapImpl;

1218

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

1220

1221

1222 unsigned size[Nodes];

1223 IdxPair NewOffset(0, Position);

1224

1225

1226 if (Nodes == 1)

1227 size[0] = rootSize;

1228 else

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

1230 Position, true);

1231

1232

1233 unsigned pos = 0;

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

1236 Leaf *L = newNode();

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

1239 pos += size[n];

1240 }

1241

1242

1243 switchRootToBranch();

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

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

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

1247 }

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

1249 rootSize = Nodes;

1250 return NewOffset;

1251}

1252

1253

1254

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

1257splitRoot(unsigned Position) {

1258 using namespace IntervalMapImpl;

1259

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

1261

1262

1263 unsigned Size[Nodes];

1264 IdxPair NewOffset(0, Position);

1265

1266

1267 if (Nodes == 1)

1268 Size[0] = rootSize;

1269 else

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

1271 Position, true);

1272

1273

1274 unsigned Pos = 0;

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

1277 Branch *B = newNode();

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

1280 Pos += Size[n];

1281 }

1282

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

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

1286 }

1287 rootSize = Nodes;

1288 ++height;

1289 return NewOffset;

1290}

1291

1292

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

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

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

1296 if (!branched())

1297 return;

1299

1300

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

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

1303

1304

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

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

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

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

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

1310 }

1311 Refs.clear();

1312 Refs.swap(NextRefs);

1313 }

1314

1315

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

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

1318}

1319

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

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

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

1323 if (Level)

1324 deleteNode(&Node.get());

1325 else

1326 deleteNode(&Node.get());

1327}

1328

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

1332 if (branched()) {

1333 visitNodes(&IntervalMap::deleteNode);

1334 switchRootToLeaf();

1335 }

1336 rootSize = 0;

1337}

1338

1339

1340

1341

1342

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

1346

1347public:

1353

1354protected:

1355

1357

1358

1359

1361

1364

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

1367 return map->branched();

1368 }

1369

1376

1380

1381

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

1386 }

1387

1388

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

1392 path.leaf().stop(path.leafOffset());

1393 }

1394

1395

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

1400 }

1401

1402public:

1403

1405

1406

1407

1409

1410

1412

1413

1415

1416

1418

1419

1421

1422

1424

1426

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

1430 return RHS .valid();

1431 if (path.leafOffset() != RHS.path.leafOffset())

1432 return false;

1434 }

1435

1439

1440

1444 path.fillLeft(map->height);

1445 }

1446

1447

1451

1452

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

1456 path.moveRight(map->height);

1457 return *this;

1458 }

1459

1460

1466

1467

1470 --path.leafOffset();

1471 else

1472 path.moveLeft(map->height);

1473 return *this;

1474 }

1475

1476

1482

1483

1484

1488 else

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

1490 }

1491

1492

1493

1494

1497 return;

1500 else

1501 path.leafOffset() =

1502 map->rootLeaf().findFrom(path.leafOffset(), map->rootSize, x);

1503 }

1504};

1505

1506

1507

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

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

1513 unsigned p = NR.get().safeFind(0, x);

1514 path.push(NR, p);

1516 }

1517 path.push(NR, NR.get().safeFind(0, x));

1518}

1519

1520

1521

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

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

1528}

1529

1530

1531

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

1535

1536 if (!Traits::stopLess(path.leaf().stop(path.leafSize() - 1), x)) {

1537 path.leafOffset() = path.leaf().safeFind(path.leafOffset(), x);

1538 return;

1539 }

1540

1541

1543

1544

1545 if (path.height()) {

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

1547 if (!Traits::stopLess(path.node(l).stop(path.offset(l)), x)) {

1548

1549 path.offset(l + 1) =

1550 path.node(l + 1).safeFind(path.offset(l + 1), x);

1552 }

1554 }

1555

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

1557 path.offset(1) = path.node(1).safeFind(path.offset(1), x);

1559 }

1560 }

1561

1562

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

1566}

1567

1568

1569

1570

1571

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

1575

1577

1579

1580 void setNodeStop(unsigned Level, KeyT Stop);

1582 template bool overflow(unsigned Level);

1584 void eraseNode(unsigned Level);

1585 void treeErase(bool UpdateRoot = true);

1586 bool canCoalesceLeft(KeyT Start, ValT x);

1587 bool canCoalesceRight(KeyT Stop, ValT x);

1588

1589public:

1590

1592

1593

1594

1595

1597

1598

1599

1600

1602

1603

1604

1605

1607

1608

1609

1610

1611

1613

1614

1615

1616

1617

1619 this->unsafeStop() = b;

1620

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

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

1623 }

1624

1625

1626

1627

1629

1630

1632

1633

1635

1638 return *this;

1639 }

1640

1642 iterator tmp = *this;

1644 return tmp;

1645 }

1646

1649 return *this;

1650 }

1651

1653 iterator tmp = *this;

1655 return tmp;

1656 }

1657};

1658

1659

1660

1661

1662

1663

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

1668 Path &P = this->path;

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

1670 unsigned i = P.leafOffset();

1671 RootLeaf &Node = P.leaf();

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

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

1674 }

1675

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

1677 Leaf &Node = P.leaf();

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

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

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

1681 Leaf &Node = NR.get();

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

1683 }

1684 return false;

1685}

1686

1687

1688

1689

1690

1691

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

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

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

1695 using namespace IntervalMapImpl;

1696 Path &P = this->path;

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

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

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

1700 return false;

1701 RootLeaf &Node = P.leaf();

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

1703 }

1704

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

1706 Leaf &Node = P.leaf();

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

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

1709 Leaf &Node = NR.get();

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

1711 }

1712 return false;

1713}

1714

1715

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

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

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

1719

1720 if (!Level)

1721 return;

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

1723

1724 while (--Level) {

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

1726 if (.atLastEntry(Level))

1727 return;

1728 }

1729

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

1731}

1732

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

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

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

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

1739 CurStart = a;

1740 return;

1741 }

1742

1743 --*this;

1744 a = this->start();

1747}

1748

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

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

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

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

1756 return;

1757 }

1758

1762}

1763

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

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

1772 }

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

1774 --*this;

1778 }

1779}

1780

1781

1782

1783

1784

1785

1786

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

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

1791 bool SplitRoot = false;

1794

1795 if (Level == 1) {

1796

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

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

1800 P.reset(Level);

1801 return SplitRoot;

1802 }

1803

1804

1805 SplitRoot = true;

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

1808

1809

1810 ++Level;

1811 }

1812

1813

1814 P.legalizeForInsert(--Level);

1815

1816

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

1818

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

1820 SplitRoot = overflow(Level);

1821 Level += SplitRoot;

1822 }

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

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

1825 if (P.atLastEntry(Level))

1826 setNodeStop(Level, Stop);

1827 P.reset(Level + 1);

1828 return SplitRoot;

1829}

1830

1831

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

1835 if (this->branched())

1836 return treeInsert(a, b, y);

1839

1840

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

1842

1843

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

1846 return;

1847 }

1848

1849

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

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

1852

1853

1854 treeInsert(a, b, y);

1855}

1856

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

1861 Path &P = this->path;

1862

1863 if (.valid())

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

1865

1866

1867 if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf().start(0))) {

1868

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

1870 Leaf &SibLeaf = Sib.get();

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

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

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

1874

1875

1876

1877

1878

1879 Leaf &CurLeaf = P.leaf();

1880 P.moveLeft(P.height());

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

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

1883

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

1885 return;

1886 } else {

1887

1888

1889 a = SibLeaf.start(SibOfs);

1890 treeErase(false);

1891 }

1892 }

1893 } else {

1894

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

1896 }

1897 }

1898

1899

1900 unsigned Size = P.leafSize();

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

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

1903

1904

1905 if (Size > Leaf::Capacity) {

1906 overflow(P.height());

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

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

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

1910 }

1911

1912

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

1914

1915

1916 if (Grow)

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

1918}

1919

1920

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

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

1927 if (this->branched())

1928 return treeErase();

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

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

1931}

1932

1933

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

1939 Leaf &Node = P.leaf();

1940

1941

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

1943 IM.deleteNode(&Node);

1944 eraseNode(IM.height);

1945

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

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

1948 return;

1949 }

1950

1951

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

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

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

1955

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

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

1958 P.moveRight(IM.height);

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

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

1961}

1962

1963

1964

1965

1966

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

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

1969iterator::eraseNode(unsigned Level) {

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

1971 IntervalMap &IM = *this->map;

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

1973

1974 if (--Level == 0) {

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

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

1977

1978 if (IM.empty()) {

1979 IM.switchRootToLeaf();

1980 this->setRoot(0);

1981 return;

1982 }

1983 } else {

1984

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

1987

1988 IM.deleteNode(&Parent);

1989 eraseNode(Level);

1990 } else {

1991

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

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

1994 P.setSize(Level, NewSize);

1995

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

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

1998 P.moveRight(Level);

1999 }

2000 }

2001 }

2002

2003 if (P.valid()) {

2004 P.reset(Level + 1);

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

2006 }

2007}

2008

2009

2010

2011

2012

2013

2014

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

2016template

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

2018iterator::overflow(unsigned Level) {

2019 using namespace IntervalMapImpl;

2020 Path &P = this->path;

2021 unsigned CurSize[4];

2022 NodeT *Node[4];

2023 unsigned Nodes = 0;

2025 unsigned Offset = P.offset(Level);

2026

2027

2028 NodeRef LeftSib = P.getLeftSibling(Level);

2029 if (LeftSib) {

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

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

2032 }

2033

2034

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

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

2037

2038

2039 NodeRef RightSib = P.getRightSibling(Level);

2040 if (RightSib) {

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

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

2043 }

2044

2045

2046 unsigned NewNode = 0;

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

2048

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

2050 CurSize[Nodes] = CurSize[NewNode];

2051 Node[Nodes] = Node[NewNode];

2052 CurSize[NewNode] = 0;

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

2054 ++Nodes;

2055 }

2056

2057

2058 unsigned NewSize[4];

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

2060 CurSize, NewSize, Offset, true);

2062

2063

2064 if (LeftSib)

2065 P.moveLeft(Level);

2066

2067

2068 bool SplitRoot = false;

2069 unsigned Pos = 0;

2070 while (true) {

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

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

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

2074 Level += SplitRoot;

2075 } else {

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

2077 setNodeStop(Level, Stop);

2078 }

2079 if (Pos + 1 == Nodes)

2080 break;

2081 P.moveRight(Level);

2082 ++Pos;

2083 }

2084

2085

2086 while(Pos != NewOffset.first) {

2087 P.moveLeft(Level);

2088 --Pos;

2089 }

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

2091 return SplitRoot;

2092}

2093

2094

2095

2096

2097

2098

2099

2100

2101

2102

2103

2104

2105

2106

2107

2108

2109

2110template <typename MapA, typename MapB>

2112 using KeyType = typename MapA::KeyType;

2113 using Traits = typename MapA::KeyTraits;

2114

2115 typename MapA::const_iterator posA;

2116 typename MapB::const_iterator posB;

2117

2118

2119

2120

2121 void advance() {

2123 return;

2124

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

2126

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

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

2129 return;

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

2131

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

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

2134 return;

2135 } else {

2136

2137 return;

2138 }

2139

2140 while (true) {

2141

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

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

2144 return;

2145

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

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

2148 return;

2149 }

2150 }

2151

2152public:

2153

2157

2158

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

2161 }

2162

2163

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

2165

2166

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

2168

2169

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

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

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

2174 }

2175

2176

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

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

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

2181 }

2182

2183

2185 ++posA;

2186 advance();

2187 }

2188

2189

2191 ++posB;

2192 advance();

2193 }

2194

2195

2197

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

2200 else

2202 return *this;

2203 }

2204

2205

2206

2209 return;

2210

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

2212 posA.advanceTo(x);

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

2214 posB.advanceTo(x);

2215 advance();

2216 }

2217};

2218

2219}

2220

2221#endif

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

This file defines the BumpPtrAllocator interface.

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

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

This file defines the PointerIntPair class.

This file defines the SmallVector class.

static const BasicSubtargetSubTypeKV * find(StringRef S, ArrayRef< BasicSubtargetSubTypeKV > A)

Find KV in array using binary search.

Definition IntervalMap.h:704

const NodeRef & subtree(unsigned i) const

Definition IntervalMap.h:707

NodeRef & subtree(unsigned i)

Definition IntervalMap.h:710

unsigned safeFind(unsigned i, KeyT x) const

safeFind - Find a subtree that is known to exist.

Definition IntervalMap.h:732

const KeyT & stop(unsigned i) const

Definition IntervalMap.h:706

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

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

Definition IntervalMap.h:718

KeyT & stop(unsigned i)

Definition IntervalMap.h:709

NodeRef safeLookup(KeyT x) const

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

Definition IntervalMap.h:744

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

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

Definition IntervalMap.h:753

Definition IntervalMap.h:567

unsigned safeFind(unsigned i, KeyT x) const

safeFind - Find an interval that is known to exist.

Definition IntervalMap.h:598

const KeyT & stop(unsigned i) const

Definition IntervalMap.h:570

const ValT & value(unsigned i) const

Definition IntervalMap.h:571

ValT safeLookup(KeyT x, ValT NotFound) const

safeLookup - Lookup mapped value for a safe key.

Definition IntervalMap.h:612

ValT & value(unsigned i)

Definition IntervalMap.h:575

KeyT & stop(unsigned i)

Definition IntervalMap.h:574

KeyT & start(unsigned i)

Definition IntervalMap.h:573

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.

Definition IntervalMap.h:631

const KeyT & start(unsigned i) const

Definition IntervalMap.h:569

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

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

Definition IntervalMap.h:583

Definition IntervalMap.h:224

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

erase - Erase elements [i;j).

Definition IntervalMap.h:273

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

moveLeft - Move elements to the left.

Definition IntervalMap.h:251

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

transferToLeftSib - Transfer elements to a left sibling node.

Definition IntervalMap.h:296

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

copy - Copy elements from another node.

Definition IntervalMap.h:237

static constexpr unsigned Capacity

Definition IntervalMap.h:226

ValT second[N]

Definition IntervalMap.h:229

std::pair< KeyT, KeyT > first[N]

Definition IntervalMap.h:228

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...

Definition IntervalMap.h:320

void shift(unsigned i, unsigned Size)

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

Definition IntervalMap.h:287

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

transferToRightSib - Transfer elements to a right sibling node.

Definition IntervalMap.h:307

void erase(unsigned i, unsigned Size)

erase - Erase element at i.

Definition IntervalMap.h:280

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

moveRight - Move elements to the right.

Definition IntervalMap.h:260

Definition IntervalMap.h:494

unsigned size() const

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

Definition IntervalMap.h:516

bool operator!=(const NodeRef &RHS) const

Definition IntervalMap.h:541

void setSize(unsigned n)

setSize - Update the node size.

Definition IntervalMap.h:519

bool operator==(const NodeRef &RHS) const

Definition IntervalMap.h:534

NodeT & get() const

get - Dereference as a NodeT reference.

Definition IntervalMap.h:530

NodeRef(NodeT *p, unsigned n)

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

Definition IntervalMap.h:511

NodeRef & subtree(unsigned i) const

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

Definition IntervalMap.h:524

NodeRef()=default

NodeRef - Create a null ref.

Definition IntervalMap.h:774

unsigned & offset(unsigned Level)

Definition IntervalMap.h:803

bool valid() const

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

Definition IntervalMap.h:814

void reset(unsigned Level)

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

Definition IntervalMap.h:831

NodeT & leaf() const

Definition IntervalMap.h:806

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

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

Definition IntervalMap.h:861

unsigned offset(unsigned Level) const

Definition IntervalMap.h:802

unsigned leafOffset() const

Definition IntervalMap.h:810

NodeT & node(unsigned Level) const

Definition IntervalMap.h:798

bool atLastEntry(unsigned Level) const

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

Definition IntervalMap.h:911

unsigned leafSize() const

Definition IntervalMap.h:809

bool atBegin() const

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

Definition IntervalMap.h:901

unsigned height() const

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

Definition IntervalMap.h:820

void pop()

pop - Remove the last path entry.

Definition IntervalMap.h:843

void setSize(unsigned Level, unsigned Size)

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

Definition IntervalMap.h:851

void fillLeft(unsigned Height)

fillLeft - Grow path to Height by taking leftmost branches.

Definition IntervalMap.h:885

void legalizeForInsert(unsigned Level)

legalizeForInsert - Prepare the path for an insertion at Level.

Definition IntervalMap.h:920

unsigned size(unsigned Level) const

Definition IntervalMap.h:801

LLVM_ABI void moveLeft(unsigned Level)

moveLeft - Move path to the left sibling at Level.

void push(NodeRef Node, unsigned Offset)

push - Add entry to path.

Definition IntervalMap.h:838

unsigned & leafOffset()

Definition IntervalMap.h:811

NodeRef & subtree(unsigned Level) const

subtree - Get the subtree referenced from Level.

Definition IntervalMap.h:825

IntervalMapOverlaps & operator++()

Preincrement - Move to the next overlap.

Definition IntervalMap.h:2196

void skipB()

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

Definition IntervalMap.h:2190

void skipA()

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

Definition IntervalMap.h:2184

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

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

Definition IntervalMap.h:2154

KeyType start() const

start - Beginning of the overlapping interval.

Definition IntervalMap.h:2170

const MapA::const_iterator & a() const

a - access the left hand side in the overlap.

Definition IntervalMap.h:2164

void advanceTo(KeyType x)

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

Definition IntervalMap.h:2207

bool valid() const

valid - Return true if iterator is at an overlap.

Definition IntervalMap.h:2159

const MapB::const_iterator & b() const

b - access the right hand side in the overlap.

Definition IntervalMap.h:2167

KeyType stop() const

stop - End of the overlapping interval.

Definition IntervalMap.h:2177

void setMap(const IntervalMap &m)

setMap - Change the map iterated over.

Definition IntervalMap.h:1408

const_iterator(const IntervalMap &map)

Definition IntervalMap.h:1362

IntervalMap * map

Definition IntervalMap.h:1356

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().

Definition IntervalMap.h:1495

ValT value_type

Definition IntervalMap.h:1349

void pathFillFind(IndexT x)

Definition IntervalMap.h:1510

bool operator==(const const_iterator &RHS) const

Definition IntervalMap.h:1427

bool operator!=(const const_iterator &RHS) const

Definition IntervalMap.h:1436

void goToEnd()

goToEnd - Move beyond the last interval in map.

Definition IntervalMap.h:1448

const KeyT & stop() const

stop - Return the end of the current interval.

Definition IntervalMap.h:1420

KeyT & unsafeStop() const

unsafeStop - Writable access to stop() for iterator.

Definition IntervalMap.h:1389

const_iterator & operator++()

preincrement - Move to the next interval.

Definition IntervalMap.h:1453

bool valid() const

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

Definition IntervalMap.h:1411

const KeyT & start() const

start - Return the beginning of the current interval.

Definition IntervalMap.h:1417

void treeAdvanceTo(IndexT x)

Definition IntervalMap.h:1534

ValT & unsafeValue() const

unsafeValue - Writable access to value() for iterator.

Definition IntervalMap.h:1396

const ValT & operator*() const

Definition IntervalMap.h:1425

std::bidirectional_iterator_tag iterator_category

Definition IntervalMap.h:1348

const ValT & value() const

value - Return the mapped value at the current interval.

Definition IntervalMap.h:1423

const_iterator operator--(int)

postdecrement - Don't do that!

Definition IntervalMap.h:1477

IntervalMapImpl::Path path

Definition IntervalMap.h:1360

void setRoot(unsigned Offset)

Definition IntervalMap.h:1370

void treeFind(IndexT x)

Definition IntervalMap.h:1524

bool atBegin() const

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

Definition IntervalMap.h:1414

std::ptrdiff_t difference_type

Definition IntervalMap.h:1350

void find(KeyT x)

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

Definition IntervalMap.h:1485

value_type * pointer

Definition IntervalMap.h:1351

const_iterator & operator--()

predecrement - Move to the previous interval.

Definition IntervalMap.h:1468

KeyT & unsafeStart() const

unsafeStart - Writable access to start() for iterator.

Definition IntervalMap.h:1382

void goToBegin()

goToBegin - Move to the first interval in map.

Definition IntervalMap.h:1441

bool branched() const

Definition IntervalMap.h:1365

friend class IntervalMap

Definition IntervalMap.h:1345

const_iterator operator++(int)

postincrement - Don't do that!

Definition IntervalMap.h:1461

value_type & reference

Definition IntervalMap.h:1352

void insert(IndexT a, IndexT b, char y)

Definition IntervalMap.h:1834

void setValueUnchecked(ValT x)

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

Definition IntervalMap.h:1628

iterator()=default

iterator - Create null iterator.

void setStart(IndexT a)

Definition IntervalMap.h:1735

iterator operator--(int)

Definition IntervalMap.h:1652

void erase()

Definition IntervalMap.h:1923

void setValue(char x)

Definition IntervalMap.h:1766

iterator & operator++()

Definition IntervalMap.h:1636

void setStartUnchecked(KeyT a)

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

Definition IntervalMap.h:1612

iterator operator++(int)

Definition IntervalMap.h:1641

void setStop(IndexT b)

Definition IntervalMap.h:1751

friend class IntervalMap

Definition IntervalMap.h:1574

void setStopUnchecked(KeyT b)

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

Definition IntervalMap.h:1618

iterator & operator--()

Definition IntervalMap.h:1647

Definition IntervalMap.h:937

iterator begin()

Definition IntervalMap.h:1153

const_iterator begin() const

Definition IntervalMap.h:1147

void insert(IndexT a, IndexT b, char y)

Definition IntervalMap.h:1130

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

lookup - Return the mapped value at x or NotFound.

Definition IntervalMap.h:1120

KeyT stop() const

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

Definition IntervalMap.h:1113

IntervalMap & operator=(IntervalMap const &RHS)

Definition IntervalMap.h:1056

~IntervalMap()

Definition IntervalMap.h:1096

typename Sizer::Allocator Allocator

Definition IntervalMap.h:963

IntervalMap & operator=(IntervalMap &&RHS)

Definition IntervalMap.h:1070

IndexT KeyType

Definition IntervalMap.h:964

IntervalMap(IntervalMap &&RHS)

Definition IntervalMap.h:1064

IntervalMapInfo< IndexT > KeyTraits

Definition IntervalMap.h:966

char ValueType

Definition IntervalMap.h:965

const_iterator find(KeyT x) const

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

Definition IntervalMap.h:1173

iterator end()

Definition IntervalMap.h:1165

RootBranchData branchData

Definition IntervalMap.h:972

IntervalMap(IntervalMap const &RHS)

Definition IntervalMap.h:1050

bool overlaps(KeyT a, KeyT b) const

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

Definition IntervalMap.h:1187

bool empty() const

Definition IntervalMap.h:1102

const_iterator end() const

Definition IntervalMap.h:1159

RootLeaf leaf

Definition IntervalMap.h:971

KeyT start() const

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

Definition IntervalMap.h:1107

IntervalMap(Allocator &a)

Definition IntervalMap.h:1042

iterator find(KeyT x)

Definition IntervalMap.h:1179

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

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

SmallVectorSizeType< T > Size

typename SuperClass::const_iterator const_iterator

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

LLVM Value Representation.

IntervalMapImpl - Namespace used for IntervalMap implementation details.

Definition IntervalMap.h:192

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

IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.

Definition IntervalMap.h:341

@ CacheLineBytes

Definition IntervalMap.h:435

@ Log2CacheLine

Definition IntervalMap.h:434

@ DesiredNodeBytes

Definition IntervalMap.h:436

std::pair< unsigned, unsigned > IdxPair

Definition IntervalMap.h:194

LLVM_ABI 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...

NodeAddr< NodeBase * > Node

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

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.

void erase(Container &C, ValueType V)

Wrapper function to remove a value from a container:

decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)

FunctionAddr VTableAddr Count

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

Definition IntervalMap.h:168

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

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

Definition IntervalMap.h:170

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