Hashing.h Source File (original) (raw)

44#ifndef LLVM_ADT_HASHING_H

45#define LLVM_ADT_HASHING_H

48#include "llvm/Config/abi-breaking.h"

53#include

54#include

55#include

56#include

57#include

58#include

59#include

61namespace llvm {

62template <typename T, typename Enable> struct DenseMapInfo;

77 size_t value;

79public:

88 operator size_t() const { return value; }

91 return lhs.value == rhs.value;

92 }

94 return lhs.value != rhs.value;

95 }

99};

100

101

102

103

104

105

106

107

108template

109std::enable_if_t<is_integral_or_enum::value, hash_code> hash_value(T value);

110

111

112

113

114template hash_code hash_value(const T *ptr);

115

116

117template <typename T, typename U>

118hash_code hash_value(const std::pair<T, U> &arg);

119

120

121template <typename... Ts>

122hash_code hash_value(const std::tuple<Ts...> &arg);

123

124

125template

126hash_code hash_value(const std::basic_string &arg);

127

128

129template hash_code hash_value(const std::optional &arg);

130

131

132

133

136

139 std::memcpy(&result, p, sizeof(result));

142 return result;

143}

144

147 std::memcpy(&result, p, sizeof(result));

150 return result;

151}

152

153

154static constexpr uint64_t k0 = 0xc3a5c85c97cb3127ULL;

155static constexpr uint64_t k1 = 0xb492b66fbe98f273ULL;

156static constexpr uint64_t k2 = 0x9ae16a3b2f90404fULL;

157static constexpr uint64_t k3 = 0xc949d7c7509e6557ULL;

158

159

160

161

163

164 return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)));

165}

166

168 return val ^ (val >> 47);

169}

170

172

173 const uint64_t kMul = 0x9ddfea08eb382d69ULL;

174 uint64_t a = (low ^ high) * kMul;

175 a ^= (a >> 47);

176 uint64_t b = (high ^ a) * kMul;

177 b ^= (b >> 47);

178 b *= kMul;

179 return b;

180}

181

190

195

201

211

234

236 if (length >= 4 && length <= 8)

238 if (length > 8 && length <= 16)

240 if (length > 16 && length <= 32)

242 if (length > 32)

244 if (length != 0)

246

247 return k2 ^ seed;

248}

249

250

251

252

255

256

257

258

261 seed,

264 seed * k1,

266 0};

268 state.mix(s);

269 return state;

270 }

271

272

273

283

284

285

286

287 void mix(const char *s) {

300 }

301

302

303

308};

309

310

311

312

313

315#if LLVM_ENABLE_ABI_BREAKING_CHECKS

316 return static_cast<uint64_t>(

318#else

319 return 0xff51afd7ed558ccdULL;

320#endif

321}

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336template

337struct is_hashable_data : std::bool_constant<((is_integral_or_enum::value ||

338 std::is_pointer::value) &&

339 64 % sizeof(T) == 0)> {};

340

341

342

343

344

345template <typename T, typename U>

347 : std::bool_constant<(is_hashable_data::value &&

348 is_hashable_data::value &&

349 (sizeof(T) + sizeof(U)) == sizeof(std::pair<T, U>))> {

350};

351

352

355

356 return value;

357 } else {

358

359

361 return static_cast<size_t>(hash_value(value));

362 }

363}

364

365

366

367

368

369

370

371

372template

374 size_t offset = 0) {

375 size_t store_size = sizeof(value) - offset;

376 if (buffer_ptr + store_size > buffer_end)

377 return false;

378 const char *value_data = reinterpret_cast<const char *>(&value);

379 std::memcpy(buffer_ptr, value_data + offset, store_size);

380 buffer_ptr += store_size;

381 return true;

382}

383

384

385

386

387

388

389template

392 char buffer[64], *buffer_ptr = buffer;

393 char *const buffer_end = std::end(buffer);

394 while (first != last && store_and_advance(buffer_ptr, buffer_end,

396 ++first;

397 if (first == last)

398 return hash_short(buffer, buffer_ptr - buffer, seed);

399 assert(buffer_ptr == buffer_end);

400

402 size_t length = 64;

403 while (first != last) {

404

405

406 buffer_ptr = buffer;

407 while (first != last && store_and_advance(buffer_ptr, buffer_end,

409 ++first;

410

411

412

413

414 std::rotate(buffer, buffer_ptr, buffer_end);

415

416

417 state.mix(buffer);

418 length += buffer_ptr - buffer;

419 };

420

421 return state.finalize(length);

422}

423

424

425

426

427

428

429

430

431

432template

433std::enable_if_t<is_hashable_data::value, hash_code>

436 const char *s_begin = reinterpret_cast<const char *>(first);

437 const char *s_end = reinterpret_cast<const char *>(last);

438 const size_t length = std::distance(s_begin, s_end);

439 if (length <= 64)

440 return hash_short(s_begin, length, seed);

441

442 const char *s_aligned_end = s_begin + (length & ~63);

444 s_begin += 64;

445 while (s_begin != s_aligned_end) {

446 state.mix(s_begin);

447 s_begin += 64;

448 }

449 if (length & 63)

450 state.mix(s_end - 64);

451

452 return state.finalize(length);

453}

454

455}

456}

457

458

459

460

461

462

463

464

465template

467 return ::llvm::hashing::detail::hash_combine_range_impl(first, last);

468}

469

470

474

475

476namespace hashing {

478

479

480

481

482

483

484

485

490

491public:

492

493

494

495

498

499

500

501

502

503

504

505 template

506 char *combine_data(size_t &length, char *buffer_ptr, char *buffer_end, T data) {

508

509

510

511

512 size_t partial_store_size = buffer_end - buffer_ptr;

513 std::memcpy(buffer_ptr, &data, partial_store_size);

514

515

516

517

518

519 if (length == 0) {

521 length = 64;

522 } else {

523

525 length += 64;

526 }

527

528

530

531

532

534 partial_store_size))

536 }

537 return buffer_ptr;

538 }

539

540

541

542

543

544 template <typename T, typename ...Ts>

546 const T &arg, const Ts &...args) {

548

549

550 return combine(length, buffer_ptr, buffer_end, args...);

551 }

552

553

554

555

556

557

559

560

561 if (length == 0)

563

564

565

566

567

568 std::rotate(buffer, buffer_ptr, buffer_end);

569

570

572 length += buffer_ptr - buffer;

573

574 return state.finalize(length);

575 }

576};

577

578}

579}

580

581

582

583

584

585

586

587

588

589

590

591

597

598

599

600namespace hashing {

602

603

604

605

606

607

609

611 const char *s = reinterpret_cast<const char *>(&value);

614}

615

616}

617}

618

619

620

621template

623 return ::llvm::hashing::detail::hash_integer_value(

624 static_cast<uint64_t>(value));

625}

626

627

628

630 return ::llvm::hashing::detail::hash_integer_value(

631 reinterpret_cast<uintptr_t>(ptr));

632}

633

634

635

636template <typename T, typename U>

640

642 return std::apply([](const auto &...xs) { return hash_combine(xs...); }, arg);

643}

644

645

646

647template

651

655

660 return static_cast<unsigned>(size_t(val));

661 }

663};

664

665}

666

667

668namespace std {

669

670template<>

671struct hash<llvm::hash_code> {

675};

676

677}

678

679#endif

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

An opaque object representing a hash code.

Definition Hashing.h:76

friend size_t hash_value(const hash_code &code)

Allow a hash_code to be directly run through hash_value.

Definition Hashing.h:98

friend bool operator==(const hash_code &lhs, const hash_code &rhs)

Definition Hashing.h:90

friend bool operator!=(const hash_code &lhs, const hash_code &rhs)

Definition Hashing.h:93

hash_code(size_t value)

Form a hash code directly from a numerical value.

Definition Hashing.h:85

hash_code()=default

Default construct a hash_code.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

uint64_t hash_1to3_bytes(const char *s, size_t len, uint64_t seed)

Definition Hashing.h:182

bool store_and_advance(char *&buffer_ptr, char *buffer_end, const T &value, size_t offset=0)

Helper to store data from a value into a buffer and advance the pointer into that buffer.

Definition Hashing.h:373

uint64_t hash_9to16_bytes(const char *s, size_t len, uint64_t seed)

Definition Hashing.h:196

uint64_t hash_4to8_bytes(const char *s, size_t len, uint64_t seed)

Definition Hashing.h:191

hash_code hash_combine_range_impl(InputIteratorT first, InputIteratorT last)

Implement the combining of integral values into a hash_code.

Definition Hashing.h:390

hash_code hash_integer_value(uint64_t value)

Helper to hash the value of a single integer.

Definition Hashing.h:608

uint64_t rotate(uint64_t val, size_t shift)

Bitwise right rotate.

Definition Hashing.h:162

static constexpr uint64_t k2

Definition Hashing.h:156

auto get_hashable_data(const T &value)

Helper to get the hashable data representation for a type.

Definition Hashing.h:353

uint64_t fetch64(const char *p)

Definition Hashing.h:137

uint64_t hash_17to32_bytes(const char *s, size_t len, uint64_t seed)

Definition Hashing.h:202

static constexpr uint64_t k1

Definition Hashing.h:155

uint64_t get_execution_seed()

In LLVM_ENABLE_ABI_BREAKING_CHECKS builds, the seed is non-deterministic per process (address of a fu...

Definition Hashing.h:314

uint32_t fetch32(const char *p)

Definition Hashing.h:145

static constexpr uint64_t k3

Definition Hashing.h:157

uint64_t hash_short(const char *s, size_t length, uint64_t seed)

Definition Hashing.h:235

static constexpr uint64_t k0

Some primes between 2^63 and 2^64 for various uses.

Definition Hashing.h:154

uint64_t shift_mix(uint64_t val)

Definition Hashing.h:167

uint64_t hash_33to64_bytes(const char *s, size_t len, uint64_t seed)

Definition Hashing.h:212

uint64_t hash_16_bytes(uint64_t low, uint64_t high)

Definition Hashing.h:171

constexpr bool IsBigEndianHost

void swapByteOrder(T &Value)

This is an optimization pass for GlobalISel generic memory operations.

constexpr T rotr(T V, int R)

hash_code hash_value(const FixedPointSemantics &Val)

constexpr auto adl_begin(RangeT &&range) -> decltype(adl_detail::begin_impl(std::forward< RangeT >(range)))

Returns the begin iterator to range using std::begin and function found through Argument-Dependent Lo...

LLVM_ABI void install_fatal_error_handler(fatal_error_handler_t handler, void *user_data=nullptr)

install_fatal_error_handler - Installs a new error handler to be used whenever a serious (non-recover...

constexpr auto adl_end(RangeT &&range) -> decltype(adl_detail::end_impl(std::forward< RangeT >(range)))

Returns the end iterator to range using std::end and functions found through Argument-Dependent Looku...

hash_code hash_combine(const Ts &...args)

Combine values into a single hash_code.

Definition Hashing.h:592

hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)

Compute a hash_code for a sequence of values.

Definition Hashing.h:466

Implement std::hash so that hash_code can be used in STL containers.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

static bool isEqual(hash_code LHS, hash_code RHS)

Definition Hashing.h:662

static hash_code getEmptyKey()

Definition Hashing.h:657

static unsigned getHashValue(hash_code val)

Definition Hashing.h:659

static hash_code getTombstoneKey()

Definition Hashing.h:658

An information struct used to provide DenseMap with the various necessary components for a given valu...

Helper class to manage the recursive combining of hash_combine arguments.

Definition Hashing.h:486

hash_code combine(size_t length, char *buffer_ptr, char *buffer_end)

Base case for recursive, variadic combining.

Definition Hashing.h:558

char * combine_data(size_t &length, char *buffer_ptr, char *buffer_end, T data)

Combine one chunk of data into the current in-flight hash.

Definition Hashing.h:506

char buffer[64]

Definition Hashing.h:487

hash_state state

Definition Hashing.h:488

const uint64_t seed

Definition Hashing.h:489

hash_code combine(size_t length, char *buffer_ptr, char *buffer_end, const T &arg, const Ts &...args)

Recursive, variadic combining method.

Definition Hashing.h:545

hash_combine_recursive_helper()

Construct a recursive hash combining helper.

Definition Hashing.h:496

The intermediate state used during hashing.

Definition Hashing.h:253

uint64_t h1

Definition Hashing.h:254

static hash_state create(const char *s, uint64_t seed)

Create a new hash_state structure and initialize it based on the seed and the first 64-byte chunk.

Definition Hashing.h:259

uint64_t h3

Definition Hashing.h:254

uint64_t finalize(size_t length)

Compute the final 64-bit hash code value based on the current state and the length of bytes hashed.

Definition Hashing.h:304

static void mix_32_bytes(const char *s, uint64_t &a, uint64_t &b)

Mix 32-bytes from the input sequence into the 16-bytes of 'a' and 'b', including whatever is already ...

Definition Hashing.h:274

uint64_t h5

Definition Hashing.h:254

void mix(const char *s)

Mix in a 64-byte buffer of data.

Definition Hashing.h:287

uint64_t h2

Definition Hashing.h:254

uint64_t h6

Definition Hashing.h:254

uint64_t h4

Definition Hashing.h:254

uint64_t h0

Definition Hashing.h:254

Trait to indicate whether a type's bits can be hashed directly.

Definition Hashing.h:339

size_t operator()(llvm::hash_code const &Val) const

Definition Hashing.h:672