OnDiskHashTable.h Source File (original) (raw)

13#ifndef LLVM_SUPPORT_ONDISKHASHTABLE_H

14#define LLVM_SUPPORT_ONDISKHASHTABLE_H

22#include

23#include

25namespace llvm {

60 class Item {

61 public:

62 typename Info::key_type Key;

63 typename Info::data_type Data;

65 const typename Info::hash_value_type Hash;

67 Item(typename Info::key_type_ref Key, typename Info::data_type_ref Data,

68 Info &InfoObj)

70 };

72 using offset_type = typename Info::offset_type;

73 offset_type NumBuckets;

74 offset_type NumEntries;

78 struct Bucket {

79 offset_type Off;

81 Item *Head;

82 };

84 Bucket *Buckets;

86private:

88 void insert(Bucket *Buckets, size_t Size, Item *E) {

89 Bucket &B = Buckets[E->Hash & (Size - 1)];

90 E->Next = B.Head;

91 ++B.Length;

92 B.Head = E;

93 }

96 void resize(size_t NewSize) {

97 Bucket *NewBuckets = static_cast<Bucket *>(

100 for (size_t I = 0; I < NumBuckets; ++I)

101 for (Item *E = Buckets[I].Head; E;) {

102 Item *N = E->Next;

103 E->Next = nullptr;

104 insert(NewBuckets, NewSize, E);

105 E = N;

106 }

107

108 free(Buckets);

109 NumBuckets = NewSize;

110 Buckets = NewBuckets;

111 }

112

113public:

114

116 typename Info::data_type_ref Data) {

117 Info InfoObj;

118 insert(Key, Data, InfoObj);

119 }

120

121

122

123

125 typename Info::data_type_ref Data, Info &InfoObj) {

126 ++NumEntries;

127 if (4 * NumEntries >= 3 * NumBuckets)

128 resize(NumBuckets * 2);

129 insert(Buckets, NumBuckets, new (BA.Allocate()) Item(Key, Data, InfoObj));

130 }

131

132

134 unsigned Hash = InfoObj.ComputeHash(Key);

135 for (Item *I = Buckets[Hash & (NumBuckets - 1)].Head; I; I = I->Next)

136 if (I->Hash == Hash && InfoObj.EqualKey(I->Key, Key))

137 return true;

138 return false;

139 }

140

141

143 Info InfoObj;

144 return Emit(Out, InfoObj);

145 }

146

147

148

149

153

154

155

156

157

158

159

160

161

162

163

164

165 unsigned TargetNumBuckets =

166 NumEntries <= 2 ? 1 : llvm::bit_ceil(NumEntries * 4 / 3 + 1);

167 if (TargetNumBuckets != NumBuckets)

168 resize(TargetNumBuckets);

169

170

171 for (offset_type I = 0; I < NumBuckets; ++I) {

172 Bucket &B = Buckets[I];

173 if (.Head)

174 continue;

175

176

177 B.Off = Out.tell();

178 assert(B.Off && "Cannot write a bucket at offset 0. Please add padding.");

179

180

182 assert(B.Length != 0 && "Bucket has a head but zero length?");

183

184

185 for (Item *I = B.Head; I; I = I->Next) {

186 LE.write<typename Info::hash_value_type>(I->Hash);

187 const std::pair<offset_type, offset_type> &Len =

188 InfoObj.EmitKeyDataLength(Out, I->Key, I->Data);

189#ifdef NDEBUG

190 InfoObj.EmitKey(Out, I->Key, Len.first);

191 InfoObj.EmitData(Out, I->Key, I->Data, Len.second);

192#else

193

194

196 InfoObj.EmitKey(Out, I->Key, Len.first);

198 InfoObj.EmitData(Out, I->Key, I->Data, Len.second);

201 "key length does not match bytes written");

203 "data length does not match bytes written");

204#endif

205 }

206 }

207

208

209 offset_type TableOff = Out.tell();

211 TableOff += N;

212 while (N--)

214

215

216 LE.write<offset_type>(NumBuckets);

217 LE.write<offset_type>(NumEntries);

218 for (offset_type I = 0; I < NumBuckets; ++I)

219 LE.write<offset_type>(Buckets[I].Off);

220

221 return TableOff;

222 }

223

225 NumEntries = 0;

226 NumBuckets = 64;

227

228

229 Buckets = static_cast<Bucket *>(safe_calloc(NumBuckets, sizeof(Bucket)));

230 }

231

233};

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

274 const typename Info::offset_type NumBuckets;

275 const typename Info::offset_type NumEntries;

276 const unsigned char *const Buckets;

277 const unsigned char *const Base;

278 Info InfoObj;

279

280public:

287

289 const unsigned char *Buckets,

290 const unsigned char *Base,

291 const Info &InfoObj = Info())

292 : NumBuckets(NumBuckets), NumEntries(NumEntries), Buckets(Buckets),

293 Base(Base), InfoObj(InfoObj) {

294 assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&

295 "'buckets' must have a 4-byte alignment");

296 }

297

298

299

300

301 static std::pair<offset_type, offset_type>

303 assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&

304 "buckets should be 4-byte aligned.");

308 Buckets);

311 Buckets);

312 return {NumBuckets, NumEntries};

313 }

314

317 const unsigned char *getBase() const { return Base; }

318 const unsigned char *getBuckets() const { return Buckets; }

319

320 bool isEmpty() const { return NumEntries == 0; }

321

324 const unsigned char *const Data;

326 Info *InfoObj;

327

328 public:

329 iterator() : Key(), Data(nullptr), Len(0), InfoObj(nullptr) {}

331 Info *InfoObj)

332 : Key(K), Data(D), Len(L), InfoObj(InfoObj) {}

333

335

336 const unsigned char *getDataPtr() const { return Data; }

338

341 };

342

343

349

350

352 Info *InfoPtr = nullptr) {

354

355 if (!InfoPtr)

356 InfoPtr = &InfoObj;

357

358

359 offset_type Idx = KeyHash & (NumBuckets - 1);

360 const unsigned char *Bucket = Buckets + sizeof(offset_type) * Idx;

361

364 Bucket);

366 return iterator();

367 const unsigned char *Items = Base + Offset;

368

369

370

372

373 for (unsigned i = 0; i < Len; ++i) {

374

377

378

379 const std::pair<offset_type, offset_type> &L =

380 Info::ReadKeyDataLength(Items);

381 offset_type ItemLen = L.first + L.second;

382

383

384 if (ItemHash != KeyHash) {

385 Items += ItemLen;

386 continue;

387 }

388

389

391 InfoPtr->ReadKey((const unsigned char *const)Items, L.first);

392

393

394 if (!InfoPtr->EqualKey(X, IKey)) {

395 Items += ItemLen;

396 continue;

397 }

398

399

400 return iterator(X, Items + L.first, L.second, InfoPtr);

401 }

402

404 }

405

407

409

410

411

412

413

414

415

416

417

418

420 const unsigned char *const Base,

421 const Info &InfoObj = Info()) {

422 assert(Buckets > Base);

425 NumBucketsAndEntries.second,

426 Buckets, Base, InfoObj);

427 }

428};

429

430

431

432

433template

435 const unsigned char *Payload;

436

437public:

444

445private:

446

447 class iterator_base {

448 const unsigned char *Ptr;

451

452 public:

454

455 iterator_base(const unsigned char *const Ptr, offset_type NumEntries)

456 : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries) {}

457 iterator_base()

458 : Ptr(nullptr), NumItemsInBucketLeft(0), NumEntriesLeft(0) {}

459

460 friend bool operator==(const iterator_base &X, const iterator_base &Y) {

461 return X.NumEntriesLeft == Y.NumEntriesLeft;

462 }

463 friend bool operator!=(const iterator_base &X, const iterator_base &Y) {

464 return X.NumEntriesLeft != Y.NumEntriesLeft;

465 }

466

467

468 void advance() {

470 if (!NumItemsInBucketLeft) {

471

472

473 NumItemsInBucketLeft =

475 }

477

478 const std::pair<offset_type, offset_type> &L =

479 Info::ReadKeyDataLength(Ptr);

480 Ptr += L.first + L.second;

481 assert(NumItemsInBucketLeft);

482 --NumItemsInBucketLeft;

483 assert(NumEntriesLeft);

484 --NumEntriesLeft;

485 }

486

487

488

489 const unsigned char *getItem() const {

490 return Ptr + (NumItemsInBucketLeft ? 0 : 2) + sizeof(hash_value_type);

491 }

492 };

493

494public:

496 const unsigned char *Buckets,

497 const unsigned char *Payload,

498 const unsigned char *Base,

499 const Info &InfoObj = Info())

500 : base_type(NumBuckets, NumEntries, Buckets, Base, InfoObj),

501 Payload(Payload) {}

502

503

505 Info *InfoObj;

506

507 public:

509

511 Info *InfoObj)

512 : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}

514

516 this->advance();

517 return *this;

518 }

521 ++*this;

522 return tmp;

523 }

524

526 auto *LocalPtr = this->getItem();

527

528

529 auto L = Info::ReadKeyDataLength(LocalPtr);

530

531

532 return InfoObj->ReadKey(LocalPtr, L.first);

533 }

534

538 };

539

543 key_iterator key_end() { return key_iterator(); }

544

548

549

551 Info *InfoObj;

552

553 public:

555

557 Info *InfoObj)

558 : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}

560

562 this->advance();

563 return *this;

564 }

567 ++*this;

568 return tmp;

569 }

570

572 auto *LocalPtr = this->getItem();

573

574

575 auto L = Info::ReadKeyDataLength(LocalPtr);

576

577

579 return InfoObj->ReadData(Key, LocalPtr + L.first, L.second);

580 }

581 };

582

586 data_iterator data_end() { return data_iterator(); }

587

591

592

593

594

595

596

597

598

599

600

601

602

603

604

606 Create(const unsigned char *Buckets, const unsigned char *const Payload,

607 const unsigned char *const Base, const Info &InfoObj = Info()) {

608 assert(Buckets > Base);

609 auto NumBucketsAndEntries =

612 NumBucketsAndEntries.first, NumBucketsAndEntries.second,

613 Buckets, Payload, Base, InfoObj);

614 }

615};

616

617}

618

619#endif

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

This file defines the BumpPtrAllocator interface.

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

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

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

Analysis containing CSE Info

InstrProfLookupTrait::offset_type offset_type

static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

~OnDiskChainedHashTableGenerator()

Definition OnDiskHashTable.h:232

offset_type Emit(raw_ostream &Out)

Emit the table to Out, which must not be at offset 0.

Definition OnDiskHashTable.h:142

void insert(typename Info::key_type_ref Key, typename Info::data_type_ref Data)

Insert an entry into the table.

Definition OnDiskHashTable.h:115

OnDiskChainedHashTableGenerator()

Definition OnDiskHashTable.h:224

bool contains(typename Info::key_type_ref Key, Info &InfoObj)

Determine whether an entry has been inserted.

Definition OnDiskHashTable.h:133

offset_type Emit(raw_ostream &Out, Info &InfoObj)

Emit the table to Out, which must not be at offset 0.

Definition OnDiskHashTable.h:150

void insert(typename Info::key_type_ref Key, typename Info::data_type_ref Data, Info &InfoObj)

Insert an entry into the table.

Definition OnDiskHashTable.h:124

Definition OnDiskHashTable.h:322

const unsigned char * getDataPtr() const

Definition OnDiskHashTable.h:336

offset_type getDataLen() const

Definition OnDiskHashTable.h:337

bool operator==(const iterator &X) const

Definition OnDiskHashTable.h:339

bool operator!=(const iterator &X) const

Definition OnDiskHashTable.h:340

data_type operator*() const

Definition OnDiskHashTable.h:334

iterator(const internal_key_type K, const unsigned char *D, offset_type L, Info *InfoObj)

Definition OnDiskHashTable.h:330

iterator()

Definition OnDiskHashTable.h:329

static std::pair< offset_type, offset_type > readNumBucketsAndEntries(const unsigned char *&Buckets)

Read the number of buckets and the number of entries from a hash table produced by OnDiskHashTableGen...

Definition OnDiskHashTable.h:302

Info & getInfoObj()

Definition OnDiskHashTable.h:408

static OnDiskChainedHashTable * Create(const unsigned char *Buckets, const unsigned char *const Base, const Info &InfoObj=Info())

Create the hash table.

Definition OnDiskHashTable.h:419

offset_type getNumEntries() const

Definition OnDiskHashTable.h:316

typename Info::hash_value_type hash_value_type

Definition OnDiskHashTable.h:285

typename Info::external_key_type external_key_type

Definition OnDiskHashTable.h:283

iterator end() const

Definition OnDiskHashTable.h:406

iterator find_hashed(const internal_key_type &IKey, hash_value_type KeyHash, Info *InfoPtr=nullptr)

Look up the stored data for a particular key with a known hash.

Definition OnDiskHashTable.h:351

offset_type getNumBuckets() const

Definition OnDiskHashTable.h:315

Info InfoType

Definition OnDiskHashTable.h:281

typename Info::offset_type offset_type

Definition OnDiskHashTable.h:286

typename Info::internal_key_type internal_key_type

Definition OnDiskHashTable.h:282

bool isEmpty() const

Definition OnDiskHashTable.h:320

const unsigned char * getBase() const

Definition OnDiskHashTable.h:317

typename Info::data_type data_type

Definition OnDiskHashTable.h:284

const unsigned char * getBuckets() const

Definition OnDiskHashTable.h:318

iterator find(const external_key_type &EKey, Info *InfoPtr=nullptr)

Look up the stored data for a particular key.

Definition OnDiskHashTable.h:344

OnDiskChainedHashTable(offset_type NumBuckets, offset_type NumEntries, const unsigned char *Buckets, const unsigned char *Base, const Info &InfoObj=Info())

Definition OnDiskHashTable.h:288

data_iterator & operator++()

Definition OnDiskHashTable.h:561

value_type operator*() const

Definition OnDiskHashTable.h:571

data_type value_type

Definition OnDiskHashTable.h:554

data_iterator(const unsigned char *const Ptr, offset_type NumEntries, Info *InfoObj)

Definition OnDiskHashTable.h:556

data_iterator operator++(int)

Definition OnDiskHashTable.h:565

data_iterator()

Definition OnDiskHashTable.h:559

internal_key_type getInternalKey() const

Definition OnDiskHashTable.h:525

key_iterator()

Definition OnDiskHashTable.h:513

key_iterator operator++(int)

Definition OnDiskHashTable.h:519

value_type operator*() const

Definition OnDiskHashTable.h:535

external_key_type value_type

Definition OnDiskHashTable.h:508

key_iterator(const unsigned char *const Ptr, offset_type NumEntries, Info *InfoObj)

Definition OnDiskHashTable.h:510

key_iterator & operator++()

Definition OnDiskHashTable.h:515

Provides lookup and iteration over an on disk hash table.

Definition OnDiskHashTable.h:434

iterator_range< key_iterator > keys()

Definition OnDiskHashTable.h:545

typename base_type::hash_value_type hash_value_type

Definition OnDiskHashTable.h:442

data_iterator data_end()

Definition OnDiskHashTable.h:586

static OnDiskIterableChainedHashTable * Create(const unsigned char *Buckets, const unsigned char *const Payload, const unsigned char *const Base, const Info &InfoObj=Info())

Create the hash table.

Definition OnDiskHashTable.h:606

OnDiskChainedHashTable< InstrProfLookupTrait > base_type

Definition OnDiskHashTable.h:438

typename base_type::data_type data_type

Definition OnDiskHashTable.h:441

key_iterator key_end()

Definition OnDiskHashTable.h:543

typename base_type::internal_key_type internal_key_type

Definition OnDiskHashTable.h:439

iterator_range< data_iterator > data()

Definition OnDiskHashTable.h:588

typename base_type::offset_type offset_type

Definition OnDiskHashTable.h:443

key_iterator key_begin()

Definition OnDiskHashTable.h:540

data_iterator data_begin()

Definition OnDiskHashTable.h:583

OnDiskIterableChainedHashTable(offset_type NumBuckets, offset_type NumEntries, const unsigned char *Buckets, const unsigned char *Payload, const unsigned char *Base, const Info &InfoObj=Info())

Definition OnDiskHashTable.h:495

typename base_type::external_key_type external_key_type

Definition OnDiskHashTable.h:440

A BumpPtrAllocator that allows only elements of a specific type to be allocated.

A range adaptor for a pair of iterators.

This class implements an extremely fast bulk output stream that can only output to a stream.

uint64_t tell() const

tell - Return the current offset with the file.

value_type readNext(const CharT *&memory, endianness endian)

Read a value of a particular endianness from a buffer, and increment the buffer past that value.

This is an optimization pass for GlobalISel generic memory operations.

bool operator!=(uint64_t V1, const APInt &V2)

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

T bit_ceil(T Value)

Returns the smallest integral power of two no smaller than Value if Value is nonzero.

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

LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_calloc(size_t Count, size_t Sz)

LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key

uint64_t offsetToAlignment(uint64_t Value, Align Alignment)

Returns the offset to the next integer (mod 2**64) that is greater than or equal to Value and is a mu...

FunctionAddr VTableAddr uintptr_t uintptr_t Data

FunctionAddr VTableAddr Next

This struct is a compact representation of a valid (non-zero power of two) alignment.

Adapter to write values to a stream in a particular byte order.