1 //===--- OnDiskHashTable.h - On-Disk Hash Table Implementation --*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 /// Defines facilities for reading and writing on-disk hash tables.
12 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_SUPPORT_ONDISKHASHTABLE_H
14 #define LLVM_SUPPORT_ONDISKHASHTABLE_H
16 #include "llvm/Support/Alignment.h"
17 #include "llvm/Support/Allocator.h"
18 #include "llvm/Support/DataTypes.h"
19 #include "llvm/Support/EndianStream.h"
20 #include "llvm/Support/Host.h"
21 #include "llvm/Support/MathExtras.h"
22 #include "llvm/Support/raw_ostream.h"
28 /// Generates an on disk hash table.
30 /// This needs an \c Info that handles storing values into the hash table's
31 /// payload and computes the hash for a given key. This should provide the
32 /// following interface:
35 /// class ExampleInfo {
37 /// typedef ExampleKey key_type; // Must be copy constructible
38 /// typedef ExampleKey &key_type_ref;
39 /// typedef ExampleData data_type; // Must be copy constructible
40 /// typedef ExampleData &data_type_ref;
41 /// typedef uint32_t hash_value_type; // The type the hash function returns.
42 /// typedef uint32_t offset_type; // The type for offsets into the table.
44 /// /// Calculate the hash for Key
45 /// static hash_value_type ComputeHash(key_type_ref Key);
46 /// /// Return the lengths, in bytes, of the given Key/Data pair.
47 /// static std::pair<offset_type, offset_type>
48 /// EmitKeyDataLength(raw_ostream &Out, key_type_ref Key, data_type_ref Data);
49 /// /// Write Key to Out. KeyLen is the length from EmitKeyDataLength.
50 /// static void EmitKey(raw_ostream &Out, key_type_ref Key,
51 /// offset_type KeyLen);
52 /// /// Write Data to Out. DataLen is the length from EmitKeyDataLength.
53 /// static void EmitData(raw_ostream &Out, key_type_ref Key,
54 /// data_type_ref Data, offset_type DataLen);
55 /// /// Determine if two keys are equal. Optional, only needed by contains.
56 /// static bool EqualKey(key_type_ref Key1, key_type_ref Key2);
59 template <typename Info
> class OnDiskChainedHashTableGenerator
{
60 /// A single item in the hash table.
63 typename
Info::key_type Key
;
64 typename
Info::data_type Data
;
66 const typename
Info::hash_value_type Hash
;
68 Item(typename
Info::key_type_ref Key
, typename
Info::data_type_ref Data
,
70 : Key(Key
), Data(Data
), Next(nullptr), Hash(InfoObj
.ComputeHash(Key
)) {}
73 typedef typename
Info::offset_type offset_type
;
74 offset_type NumBuckets
;
75 offset_type NumEntries
;
76 llvm::SpecificBumpPtrAllocator
<Item
> BA
;
78 /// A linked list of values in a particular hash bucket.
88 /// Insert an item into the appropriate hash bucket.
89 void insert(Bucket
*Buckets
, size_t Size
, Item
*E
) {
90 Bucket
&B
= Buckets
[E
->Hash
& (Size
- 1)];
96 /// Resize the hash table, moving the old entries into the new buckets.
97 void resize(size_t NewSize
) {
98 Bucket
*NewBuckets
= static_cast<Bucket
*>(
99 safe_calloc(NewSize
, sizeof(Bucket
)));
100 // Populate NewBuckets with the old entries.
101 for (size_t I
= 0; I
< NumBuckets
; ++I
)
102 for (Item
*E
= Buckets
[I
].Head
; E
;) {
105 insert(NewBuckets
, NewSize
, E
);
110 NumBuckets
= NewSize
;
111 Buckets
= NewBuckets
;
115 /// Insert an entry into the table.
116 void insert(typename
Info::key_type_ref Key
,
117 typename
Info::data_type_ref Data
) {
119 insert(Key
, Data
, InfoObj
);
122 /// Insert an entry into the table.
124 /// Uses the provided Info instead of a stack allocated one.
125 void insert(typename
Info::key_type_ref Key
,
126 typename
Info::data_type_ref Data
, Info
&InfoObj
) {
128 if (4 * NumEntries
>= 3 * NumBuckets
)
129 resize(NumBuckets
* 2);
130 insert(Buckets
, NumBuckets
, new (BA
.Allocate()) Item(Key
, Data
, InfoObj
));
133 /// Determine whether an entry has been inserted.
134 bool contains(typename
Info::key_type_ref Key
, Info
&InfoObj
) {
135 unsigned Hash
= InfoObj
.ComputeHash(Key
);
136 for (Item
*I
= Buckets
[Hash
& (NumBuckets
- 1)].Head
; I
; I
= I
->Next
)
137 if (I
->Hash
== Hash
&& InfoObj
.EqualKey(I
->Key
, Key
))
142 /// Emit the table to Out, which must not be at offset 0.
143 offset_type
Emit(raw_ostream
&Out
) {
145 return Emit(Out
, InfoObj
);
148 /// Emit the table to Out, which must not be at offset 0.
150 /// Uses the provided Info instead of a stack allocated one.
151 offset_type
Emit(raw_ostream
&Out
, Info
&InfoObj
) {
152 using namespace llvm::support
;
153 endian::Writer
LE(Out
, little
);
155 // Now we're done adding entries, resize the bucket list if it's
156 // significantly too large. (This only happens if the number of
157 // entries is small and we're within our initial allocation of
158 // 64 buckets.) We aim for an occupancy ratio in [3/8, 3/4).
160 // As a special case, if there are two or fewer entries, just
161 // form a single bucket. A linear scan is fine in that case, and
162 // this is very common in C++ class lookup tables. This also
163 // guarantees we produce at least one bucket for an empty table.
165 // FIXME: Try computing a perfect hash function at this point.
166 unsigned TargetNumBuckets
=
167 NumEntries
<= 2 ? 1 : NextPowerOf2(NumEntries
* 4 / 3);
168 if (TargetNumBuckets
!= NumBuckets
)
169 resize(TargetNumBuckets
);
171 // Emit the payload of the table.
172 for (offset_type I
= 0; I
< NumBuckets
; ++I
) {
173 Bucket
&B
= Buckets
[I
];
177 // Store the offset for the data of this bucket.
179 assert(B
.Off
&& "Cannot write a bucket at offset 0. Please add padding.");
181 // Write out the number of items in the bucket.
182 LE
.write
<uint16_t>(B
.Length
);
183 assert(B
.Length
!= 0 && "Bucket has a head but zero length?");
185 // Write out the entries in the bucket.
186 for (Item
*I
= B
.Head
; I
; I
= I
->Next
) {
187 LE
.write
<typename
Info::hash_value_type
>(I
->Hash
);
188 const std::pair
<offset_type
, offset_type
> &Len
=
189 InfoObj
.EmitKeyDataLength(Out
, I
->Key
, I
->Data
);
191 InfoObj
.EmitKey(Out
, I
->Key
, Len
.first
);
192 InfoObj
.EmitData(Out
, I
->Key
, I
->Data
, Len
.second
);
194 // In asserts mode, check that the users length matches the data they
196 uint64_t KeyStart
= Out
.tell();
197 InfoObj
.EmitKey(Out
, I
->Key
, Len
.first
);
198 uint64_t DataStart
= Out
.tell();
199 InfoObj
.EmitData(Out
, I
->Key
, I
->Data
, Len
.second
);
200 uint64_t End
= Out
.tell();
201 assert(offset_type(DataStart
- KeyStart
) == Len
.first
&&
202 "key length does not match bytes written");
203 assert(offset_type(End
- DataStart
) == Len
.second
&&
204 "data length does not match bytes written");
209 // Pad with zeros so that we can start the hashtable at an aligned address.
210 offset_type TableOff
= Out
.tell();
211 uint64_t N
= offsetToAlignment(TableOff
, Align(alignof(offset_type
)));
214 LE
.write
<uint8_t>(0);
216 // Emit the hashtable itself.
217 LE
.write
<offset_type
>(NumBuckets
);
218 LE
.write
<offset_type
>(NumEntries
);
219 for (offset_type I
= 0; I
< NumBuckets
; ++I
)
220 LE
.write
<offset_type
>(Buckets
[I
].Off
);
225 OnDiskChainedHashTableGenerator() {
228 // Note that we do not need to run the constructors of the individual
229 // Bucket objects since 'calloc' returns bytes that are all 0.
230 Buckets
= static_cast<Bucket
*>(safe_calloc(NumBuckets
, sizeof(Bucket
)));
233 ~OnDiskChainedHashTableGenerator() { std::free(Buckets
); }
236 /// Provides lookup on an on disk hash table.
238 /// This needs an \c Info that handles reading values from the hash table's
239 /// payload and computes the hash for a given key. This should provide the
240 /// following interface:
243 /// class ExampleLookupInfo {
245 /// typedef ExampleData data_type;
246 /// typedef ExampleInternalKey internal_key_type; // The stored key type.
247 /// typedef ExampleKey external_key_type; // The type to pass to find().
248 /// typedef uint32_t hash_value_type; // The type the hash function returns.
249 /// typedef uint32_t offset_type; // The type for offsets into the table.
251 /// /// Compare two keys for equality.
252 /// static bool EqualKey(internal_key_type &Key1, internal_key_type &Key2);
253 /// /// Calculate the hash for the given key.
254 /// static hash_value_type ComputeHash(internal_key_type &IKey);
255 /// /// Translate from the semantic type of a key in the hash table to the
256 /// /// type that is actually stored and used for hashing and comparisons.
257 /// /// The internal and external types are often the same, in which case this
258 /// /// can simply return the passed in value.
259 /// static const internal_key_type &GetInternalKey(external_key_type &EKey);
260 /// /// Read the key and data length from Buffer, leaving it pointing at the
261 /// /// following byte.
262 /// static std::pair<offset_type, offset_type>
263 /// ReadKeyDataLength(const unsigned char *&Buffer);
264 /// /// Read the key from Buffer, given the KeyLen as reported from
265 /// /// ReadKeyDataLength.
266 /// const internal_key_type &ReadKey(const unsigned char *Buffer,
267 /// offset_type KeyLen);
268 /// /// Read the data for Key from Buffer, given the DataLen as reported from
269 /// /// ReadKeyDataLength.
270 /// data_type ReadData(StringRef Key, const unsigned char *Buffer,
271 /// offset_type DataLen);
274 template <typename Info
> class OnDiskChainedHashTable
{
275 const typename
Info::offset_type NumBuckets
;
276 const typename
Info::offset_type NumEntries
;
277 const unsigned char *const Buckets
;
278 const unsigned char *const Base
;
282 typedef Info InfoType
;
283 typedef typename
Info::internal_key_type internal_key_type
;
284 typedef typename
Info::external_key_type external_key_type
;
285 typedef typename
Info::data_type data_type
;
286 typedef typename
Info::hash_value_type hash_value_type
;
287 typedef typename
Info::offset_type offset_type
;
289 OnDiskChainedHashTable(offset_type NumBuckets
, offset_type NumEntries
,
290 const unsigned char *Buckets
,
291 const unsigned char *Base
,
292 const Info
&InfoObj
= Info())
293 : NumBuckets(NumBuckets
), NumEntries(NumEntries
), Buckets(Buckets
),
294 Base(Base
), InfoObj(InfoObj
) {
295 assert((reinterpret_cast<uintptr_t>(Buckets
) & 0x3) == 0 &&
296 "'buckets' must have a 4-byte alignment");
299 /// Read the number of buckets and the number of entries from a hash table
300 /// produced by OnDiskHashTableGenerator::Emit, and advance the Buckets
301 /// pointer past them.
302 static std::pair
<offset_type
, offset_type
>
303 readNumBucketsAndEntries(const unsigned char *&Buckets
) {
304 assert((reinterpret_cast<uintptr_t>(Buckets
) & 0x3) == 0 &&
305 "buckets should be 4-byte aligned.");
306 using namespace llvm::support
;
307 offset_type NumBuckets
=
308 endian::readNext
<offset_type
, little
, aligned
>(Buckets
);
309 offset_type NumEntries
=
310 endian::readNext
<offset_type
, little
, aligned
>(Buckets
);
311 return std::make_pair(NumBuckets
, NumEntries
);
314 offset_type
getNumBuckets() const { return NumBuckets
; }
315 offset_type
getNumEntries() const { return NumEntries
; }
316 const unsigned char *getBase() const { return Base
; }
317 const unsigned char *getBuckets() const { return Buckets
; }
319 bool isEmpty() const { return NumEntries
== 0; }
322 internal_key_type Key
;
323 const unsigned char *const Data
;
324 const offset_type Len
;
328 iterator() : Key(), Data(nullptr), Len(0), InfoObj(nullptr) {}
329 iterator(const internal_key_type K
, const unsigned char *D
, offset_type L
,
331 : Key(K
), Data(D
), Len(L
), InfoObj(InfoObj
) {}
333 data_type
operator*() const { return InfoObj
->ReadData(Key
, Data
, Len
); }
335 const unsigned char *getDataPtr() const { return Data
; }
336 offset_type
getDataLen() const { return Len
; }
338 bool operator==(const iterator
&X
) const { return X
.Data
== Data
; }
339 bool operator!=(const iterator
&X
) const { return X
.Data
!= Data
; }
342 /// Look up the stored data for a particular key.
343 iterator
find(const external_key_type
&EKey
, Info
*InfoPtr
= nullptr) {
344 const internal_key_type
&IKey
= InfoObj
.GetInternalKey(EKey
);
345 hash_value_type KeyHash
= InfoObj
.ComputeHash(IKey
);
346 return find_hashed(IKey
, KeyHash
, InfoPtr
);
349 /// Look up the stored data for a particular key with a known hash.
350 iterator
find_hashed(const internal_key_type
&IKey
, hash_value_type KeyHash
,
351 Info
*InfoPtr
= nullptr) {
352 using namespace llvm::support
;
357 // Each bucket is just an offset into the hash table file.
358 offset_type Idx
= KeyHash
& (NumBuckets
- 1);
359 const unsigned char *Bucket
= Buckets
+ sizeof(offset_type
) * Idx
;
361 offset_type Offset
= endian::readNext
<offset_type
, little
, aligned
>(Bucket
);
363 return iterator(); // Empty bucket.
364 const unsigned char *Items
= Base
+ Offset
;
366 // 'Items' starts with a 16-bit unsigned integer representing the
367 // number of items in this bucket.
368 unsigned Len
= endian::readNext
<uint16_t, little
, unaligned
>(Items
);
370 for (unsigned i
= 0; i
< Len
; ++i
) {
372 hash_value_type ItemHash
=
373 endian::readNext
<hash_value_type
, little
, unaligned
>(Items
);
375 // Determine the length of the key and the data.
376 const std::pair
<offset_type
, offset_type
> &L
=
377 Info::ReadKeyDataLength(Items
);
378 offset_type ItemLen
= L
.first
+ L
.second
;
380 // Compare the hashes. If they are not the same, skip the entry entirely.
381 if (ItemHash
!= KeyHash
) {
387 const internal_key_type
&X
=
388 InfoPtr
->ReadKey((const unsigned char *const)Items
, L
.first
);
390 // If the key doesn't match just skip reading the value.
391 if (!InfoPtr
->EqualKey(X
, IKey
)) {
397 return iterator(X
, Items
+ L
.first
, L
.second
, InfoPtr
);
403 iterator
end() const { return iterator(); }
405 Info
&getInfoObj() { return InfoObj
; }
407 /// Create the hash table.
409 /// \param Buckets is the beginning of the hash table itself, which follows
410 /// the payload of entire structure. This is the value returned by
411 /// OnDiskHashTableGenerator::Emit.
413 /// \param Base is the point from which all offsets into the structure are
414 /// based. This is offset 0 in the stream that was used when Emitting the
416 static OnDiskChainedHashTable
*Create(const unsigned char *Buckets
,
417 const unsigned char *const Base
,
418 const Info
&InfoObj
= Info()) {
419 assert(Buckets
> Base
);
420 auto NumBucketsAndEntries
= readNumBucketsAndEntries(Buckets
);
421 return new OnDiskChainedHashTable
<Info
>(NumBucketsAndEntries
.first
,
422 NumBucketsAndEntries
.second
,
423 Buckets
, Base
, InfoObj
);
427 /// Provides lookup and iteration over an on disk hash table.
429 /// \copydetails llvm::OnDiskChainedHashTable
430 template <typename Info
>
431 class OnDiskIterableChainedHashTable
: public OnDiskChainedHashTable
<Info
> {
432 const unsigned char *Payload
;
435 typedef OnDiskChainedHashTable
<Info
> base_type
;
436 typedef typename
base_type::internal_key_type internal_key_type
;
437 typedef typename
base_type::external_key_type external_key_type
;
438 typedef typename
base_type::data_type data_type
;
439 typedef typename
base_type::hash_value_type hash_value_type
;
440 typedef typename
base_type::offset_type offset_type
;
443 /// Iterates over all of the keys in the table.
444 class iterator_base
{
445 const unsigned char *Ptr
;
446 offset_type NumItemsInBucketLeft
;
447 offset_type NumEntriesLeft
;
450 typedef external_key_type value_type
;
452 iterator_base(const unsigned char *const Ptr
, offset_type NumEntries
)
453 : Ptr(Ptr
), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries
) {}
455 : Ptr(nullptr), NumItemsInBucketLeft(0), NumEntriesLeft(0) {}
457 friend bool operator==(const iterator_base
&X
, const iterator_base
&Y
) {
458 return X
.NumEntriesLeft
== Y
.NumEntriesLeft
;
460 friend bool operator!=(const iterator_base
&X
, const iterator_base
&Y
) {
461 return X
.NumEntriesLeft
!= Y
.NumEntriesLeft
;
464 /// Move to the next item.
466 using namespace llvm::support
;
467 if (!NumItemsInBucketLeft
) {
468 // 'Items' starts with a 16-bit unsigned integer representing the
469 // number of items in this bucket.
470 NumItemsInBucketLeft
=
471 endian::readNext
<uint16_t, little
, unaligned
>(Ptr
);
473 Ptr
+= sizeof(hash_value_type
); // Skip the hash.
474 // Determine the length of the key and the data.
475 const std::pair
<offset_type
, offset_type
> &L
=
476 Info::ReadKeyDataLength(Ptr
);
477 Ptr
+= L
.first
+ L
.second
;
478 assert(NumItemsInBucketLeft
);
479 --NumItemsInBucketLeft
;
480 assert(NumEntriesLeft
);
484 /// Get the start of the item as written by the trait (after the hash and
485 /// immediately before the key and value length).
486 const unsigned char *getItem() const {
487 return Ptr
+ (NumItemsInBucketLeft
? 0 : 2) + sizeof(hash_value_type
);
492 OnDiskIterableChainedHashTable(offset_type NumBuckets
, offset_type NumEntries
,
493 const unsigned char *Buckets
,
494 const unsigned char *Payload
,
495 const unsigned char *Base
,
496 const Info
&InfoObj
= Info())
497 : base_type(NumBuckets
, NumEntries
, Buckets
, Base
, InfoObj
),
500 /// Iterates over all of the keys in the table.
501 class key_iterator
: public iterator_base
{
505 typedef external_key_type value_type
;
507 key_iterator(const unsigned char *const Ptr
, offset_type NumEntries
,
509 : iterator_base(Ptr
, NumEntries
), InfoObj(InfoObj
) {}
510 key_iterator() : iterator_base(), InfoObj() {}
512 key_iterator
&operator++() {
516 key_iterator
operator++(int) { // Postincrement
517 key_iterator tmp
= *this;
522 internal_key_type
getInternalKey() const {
523 auto *LocalPtr
= this->getItem();
525 // Determine the length of the key and the data.
526 auto L
= Info::ReadKeyDataLength(LocalPtr
);
529 return InfoObj
->ReadKey(LocalPtr
, L
.first
);
532 value_type
operator*() const {
533 return InfoObj
->GetExternalKey(getInternalKey());
537 key_iterator
key_begin() {
538 return key_iterator(Payload
, this->getNumEntries(), &this->getInfoObj());
540 key_iterator
key_end() { return key_iterator(); }
542 iterator_range
<key_iterator
> keys() {
543 return make_range(key_begin(), key_end());
546 /// Iterates over all the entries in the table, returning the data.
547 class data_iterator
: public iterator_base
{
551 typedef data_type value_type
;
553 data_iterator(const unsigned char *const Ptr
, offset_type NumEntries
,
555 : iterator_base(Ptr
, NumEntries
), InfoObj(InfoObj
) {}
556 data_iterator() : iterator_base(), InfoObj() {}
558 data_iterator
&operator++() { // Preincrement
562 data_iterator
operator++(int) { // Postincrement
563 data_iterator tmp
= *this;
568 value_type
operator*() const {
569 auto *LocalPtr
= this->getItem();
571 // Determine the length of the key and the data.
572 auto L
= Info::ReadKeyDataLength(LocalPtr
);
575 const internal_key_type
&Key
= InfoObj
->ReadKey(LocalPtr
, L
.first
);
576 return InfoObj
->ReadData(Key
, LocalPtr
+ L
.first
, L
.second
);
580 data_iterator
data_begin() {
581 return data_iterator(Payload
, this->getNumEntries(), &this->getInfoObj());
583 data_iterator
data_end() { return data_iterator(); }
585 iterator_range
<data_iterator
> data() {
586 return make_range(data_begin(), data_end());
589 /// Create the hash table.
591 /// \param Buckets is the beginning of the hash table itself, which follows
592 /// the payload of entire structure. This is the value returned by
593 /// OnDiskHashTableGenerator::Emit.
595 /// \param Payload is the beginning of the data contained in the table. This
596 /// is Base plus any padding or header data that was stored, ie, the offset
597 /// that the stream was at when calling Emit.
599 /// \param Base is the point from which all offsets into the structure are
600 /// based. This is offset 0 in the stream that was used when Emitting the
602 static OnDiskIterableChainedHashTable
*
603 Create(const unsigned char *Buckets
, const unsigned char *const Payload
,
604 const unsigned char *const Base
, const Info
&InfoObj
= Info()) {
605 assert(Buckets
> Base
);
606 auto NumBucketsAndEntries
=
607 OnDiskIterableChainedHashTable
<Info
>::readNumBucketsAndEntries(Buckets
);
608 return new OnDiskIterableChainedHashTable
<Info
>(
609 NumBucketsAndEntries
.first
, NumBucketsAndEntries
.second
,
610 Buckets
, Payload
, Base
, InfoObj
);
614 } // end namespace llvm