1 //===--- OnDiskHashTable.h - On-Disk Hash Table Implementation --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// \brief Defines facilities for reading and writing on-disk hash tables.
13 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_SUPPORT_ON_DISK_HASH_TABLE_H
15 #define LLVM_SUPPORT_ON_DISK_HASH_TABLE_H
17 #include "llvm/Support/Allocator.h"
18 #include "llvm/Support/AlignOf.h"
19 #include "llvm/Support/DataTypes.h"
20 #include "llvm/Support/EndianStream.h"
21 #include "llvm/Support/Host.h"
22 #include "llvm/Support/MathExtras.h"
23 #include "llvm/Support/raw_ostream.h"
29 /// \brief Generates an on disk hash table.
31 /// This needs an \c Info that handles storing values into the hash table's
32 /// payload and computes the hash for a given key. This should provide the
33 /// following interface:
36 /// class ExampleInfo {
38 /// typedef ExampleKey key_type; // Must be copy constructible
39 /// typedef ExampleKey &key_type_ref;
40 /// typedef ExampleData data_type; // Must be copy constructible
41 /// typedef ExampleData &data_type_ref;
42 /// typedef uint32_t hash_value_type; // The type the hash function returns.
43 /// typedef uint32_t offset_type; // The type for offsets into the table.
45 /// /// Calculate the hash for Key
46 /// static hash_value_type ComputeHash(key_type_ref Key);
47 /// /// Return the lengths, in bytes, of the given Key/Data pair.
48 /// static std::pair<offset_type, offset_type>
49 /// EmitKeyDataLength(raw_ostream &Out, key_type_ref Key, data_type_ref Data);
50 /// /// Write Key to Out. KeyLen is the length from EmitKeyDataLength.
51 /// static void EmitKey(raw_ostream &Out, key_type_ref Key,
52 /// offset_type KeyLen);
53 /// /// Write Data to Out. DataLen is the length from EmitKeyDataLength.
54 /// static void EmitData(raw_ostream &Out, key_type_ref Key,
55 /// data_type_ref Data, offset_type DataLen);
58 template <typename Info> class OnDiskChainedHashTableGenerator {
59 typedef typename Info::offset_type offset_type;
60 offset_type NumBuckets;
61 offset_type NumEntries;
62 llvm::BumpPtrAllocator BA;
64 /// \brief A single item in the hash table.
67 typename Info::key_type Key;
68 typename Info::data_type Data;
70 const typename Info::hash_value_type Hash;
72 Item(typename Info::key_type_ref Key, typename Info::data_type_ref Data,
74 : Key(Key), Data(Data), Next(0), Hash(InfoObj.ComputeHash(Key)) {}
77 /// \brief A linked list of values in a particular hash bucket.
90 /// \brief Insert an item into the appropriate hash bucket.
91 void insert(Bucket *Buckets, size_t Size, Item *E) {
92 Bucket &B = Buckets[E->Hash & (Size - 1)];
98 /// \brief Resize the hash table, moving the old entries into the new buckets.
99 void resize(size_t NewSize) {
100 Bucket *NewBuckets = (Bucket *)std::calloc(NewSize, sizeof(Bucket));
101 // Populate NewBuckets with the old entries.
102 for (size_t I = 0; I < NumBuckets; ++I)
103 for (Item *E = Buckets[I].Head; E;) {
106 insert(NewBuckets, NewSize, E);
111 NumBuckets = NewSize;
112 Buckets = NewBuckets;
116 /// \brief Insert an entry into the table.
117 void insert(typename Info::key_type_ref Key,
118 typename Info::data_type_ref Data) {
120 insert(Key, Data, InfoObj);
123 /// \brief Insert an entry into the table.
125 /// Uses the provided Info instead of a stack allocated one.
126 void insert(typename Info::key_type_ref Key,
127 typename Info::data_type_ref Data, Info &InfoObj) {
130 if (4 * NumEntries >= 3 * NumBuckets)
131 resize(NumBuckets * 2);
132 insert(Buckets, NumBuckets,
133 new (BA.Allocate<Item>()) Item(Key, Data, InfoObj));
136 /// \brief Emit the table to Out, which must not be at offset 0.
137 offset_type Emit(raw_ostream &Out) {
139 return Emit(Out, InfoObj);
142 /// \brief Emit the table to Out, which must not be at offset 0.
144 /// Uses the provided Info instead of a stack allocated one.
145 offset_type Emit(raw_ostream &Out, Info &InfoObj) {
146 using namespace llvm::support;
147 endian::Writer<little> LE(Out);
149 // Emit the payload of the table.
150 for (offset_type I = 0; I < NumBuckets; ++I) {
151 Bucket &B = Buckets[I];
155 // Store the offset for the data of this bucket.
157 assert(B.Off && "Cannot write a bucket at offset 0. Please add padding.");
159 // Write out the number of items in the bucket.
160 LE.write<uint16_t>(B.Length);
161 assert(B.Length != 0 && "Bucket has a head but zero length?");
163 // Write out the entries in the bucket.
164 for (Item *I = B.Head; I; I = I->Next) {
165 LE.write<typename Info::hash_value_type>(I->Hash);
166 const std::pair<offset_type, offset_type> &Len =
167 InfoObj.EmitKeyDataLength(Out, I->Key, I->Data);
168 InfoObj.EmitKey(Out, I->Key, Len.first);
169 InfoObj.EmitData(Out, I->Key, I->Data, Len.second);
173 // Pad with zeros so that we can start the hashtable at an aligned address.
174 offset_type TableOff = Out.tell();
175 uint64_t N = llvm::OffsetToAlignment(TableOff, alignOf<offset_type>());
178 LE.write<uint8_t>(0);
180 // Emit the hashtable itself.
181 LE.write<offset_type>(NumBuckets);
182 LE.write<offset_type>(NumEntries);
183 for (offset_type I = 0; I < NumBuckets; ++I)
184 LE.write<offset_type>(Buckets[I].Off);
189 OnDiskChainedHashTableGenerator() {
192 // Note that we do not need to run the constructors of the individual
193 // Bucket objects since 'calloc' returns bytes that are all 0.
194 Buckets = (Bucket *)std::calloc(NumBuckets, sizeof(Bucket));
197 ~OnDiskChainedHashTableGenerator() { std::free(Buckets); }
200 /// \brief Provides lookup on an on disk hash table.
202 /// This needs an \c Info that handles reading values from the hash table's
203 /// payload and computes the hash for a given key. This should provide the
204 /// following interface:
207 /// class ExampleLookupInfo {
209 /// typedef ExampleData data_type;
210 /// typedef ExampleInternalKey internal_key_type; // The stored key type.
211 /// typedef ExampleKey external_key_type; // The type to pass to find().
212 /// typedef uint32_t hash_value_type; // The type the hash function returns.
213 /// typedef uint32_t offset_type; // The type for offsets into the table.
215 /// /// Compare two keys for equality.
216 /// static bool EqualKey(internal_key_type &Key1, internal_key_type &Key2);
217 /// /// Calculate the hash for the given key.
218 /// static hash_value_type ComputeHash(internal_key_type &IKey);
219 /// /// Translate from the semantic type of a key in the hash table to the
220 /// /// type that is actually stored and used for hashing and comparisons.
221 /// /// The internal and external types are often the same, in which case this
222 /// /// can simply return the passed in value.
223 /// static const internal_key_type &GetInternalKey(external_key_type &EKey);
224 /// /// Read the key and data length from Buffer, leaving it pointing at the
225 /// /// following byte.
226 /// static std::pair<offset_type, offset_type>
227 /// ReadKeyDataLength(const unsigned char *&Buffer);
228 /// /// Read the key from Buffer, given the KeyLen as reported from
229 /// /// ReadKeyDataLength.
230 /// const internal_key_type &ReadKey(const unsigned char *Buffer,
231 /// offset_type KeyLen);
232 /// /// Read the data for Key from Buffer, given the DataLen as reported from
233 /// /// ReadKeyDataLength.
234 /// data_type ReadData(StringRef Key, const unsigned char *Buffer,
235 /// offset_type DataLen);
238 template <typename Info> class OnDiskChainedHashTable {
239 const typename Info::offset_type NumBuckets;
240 const typename Info::offset_type NumEntries;
241 const unsigned char *const Buckets;
242 const unsigned char *const Base;
246 typedef typename Info::internal_key_type internal_key_type;
247 typedef typename Info::external_key_type external_key_type;
248 typedef typename Info::data_type data_type;
249 typedef typename Info::hash_value_type hash_value_type;
250 typedef typename Info::offset_type offset_type;
252 OnDiskChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
253 const unsigned char *Buckets,
254 const unsigned char *Base,
255 const Info &InfoObj = Info())
256 : NumBuckets(NumBuckets), NumEntries(NumEntries), Buckets(Buckets),
257 Base(Base), InfoObj(InfoObj) {
258 assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
259 "'buckets' must have a 4-byte alignment");
262 offset_type getNumBuckets() const { return NumBuckets; }
263 offset_type getNumEntries() const { return NumEntries; }
264 const unsigned char *getBase() const { return Base; }
265 const unsigned char *getBuckets() const { return Buckets; }
267 bool isEmpty() const { return NumEntries == 0; }
270 internal_key_type Key;
271 const unsigned char *const Data;
272 const offset_type Len;
276 iterator() : Data(0), Len(0) {}
277 iterator(const internal_key_type K, const unsigned char *D, offset_type L,
279 : Key(K), Data(D), Len(L), InfoObj(InfoObj) {}
281 data_type operator*() const { return InfoObj->ReadData(Key, Data, Len); }
282 bool operator==(const iterator &X) const { return X.Data == Data; }
283 bool operator!=(const iterator &X) const { return X.Data != Data; }
286 /// \brief Look up the stored data for a particular key.
287 iterator find(const external_key_type &EKey, Info *InfoPtr = 0) {
291 using namespace llvm::support;
292 const internal_key_type &IKey = InfoObj.GetInternalKey(EKey);
293 hash_value_type KeyHash = InfoObj.ComputeHash(IKey);
295 // Each bucket is just an offset into the hash table file.
296 offset_type Idx = KeyHash & (NumBuckets - 1);
297 const unsigned char *Bucket = Buckets + sizeof(offset_type) * Idx;
299 offset_type Offset = endian::readNext<offset_type, little, aligned>(Bucket);
301 return iterator(); // Empty bucket.
302 const unsigned char *Items = Base + Offset;
304 // 'Items' starts with a 16-bit unsigned integer representing the
305 // number of items in this bucket.
306 unsigned Len = endian::readNext<uint16_t, little, unaligned>(Items);
308 for (unsigned i = 0; i < Len; ++i) {
310 hash_value_type ItemHash =
311 endian::readNext<hash_value_type, little, unaligned>(Items);
313 // Determine the length of the key and the data.
314 const std::pair<offset_type, offset_type> &L =
315 Info::ReadKeyDataLength(Items);
316 offset_type ItemLen = L.first + L.second;
318 // Compare the hashes. If they are not the same, skip the entry entirely.
319 if (ItemHash != KeyHash) {
325 const internal_key_type &X =
326 InfoPtr->ReadKey((const unsigned char *const)Items, L.first);
328 // If the key doesn't match just skip reading the value.
329 if (!InfoPtr->EqualKey(X, IKey)) {
335 return iterator(X, Items + L.first, L.second, InfoPtr);
341 iterator end() const { return iterator(); }
343 Info &getInfoObj() { return InfoObj; }
345 /// \brief Create the hash table.
347 /// \param Buckets is the beginning of the hash table itself, which follows
348 /// the payload of entire structure. This is the value returned by
349 /// OnDiskHashTableGenerator::Emit.
351 /// \param Base is the point from which all offsets into the structure are
352 /// based. This is offset 0 in the stream that was used when Emitting the
354 static OnDiskChainedHashTable *Create(const unsigned char *Buckets,
355 const unsigned char *const Base,
356 const Info &InfoObj = Info()) {
357 using namespace llvm::support;
358 assert(Buckets > Base);
359 assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
360 "buckets should be 4-byte aligned.");
362 offset_type NumBuckets =
363 endian::readNext<offset_type, little, aligned>(Buckets);
364 offset_type NumEntries =
365 endian::readNext<offset_type, little, aligned>(Buckets);
366 return new OnDiskChainedHashTable<Info>(NumBuckets, NumEntries, Buckets,
371 /// \brief Provides lookup and iteration over an on disk hash table.
373 /// \copydetails llvm::OnDiskChainedHashTable
374 template <typename Info>
375 class OnDiskIterableChainedHashTable : public OnDiskChainedHashTable<Info> {
376 const unsigned char *Payload;
379 typedef OnDiskChainedHashTable<Info> base_type;
380 typedef typename base_type::internal_key_type internal_key_type;
381 typedef typename base_type::external_key_type external_key_type;
382 typedef typename base_type::data_type data_type;
383 typedef typename base_type::hash_value_type hash_value_type;
384 typedef typename base_type::offset_type offset_type;
386 OnDiskIterableChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
387 const unsigned char *Buckets,
388 const unsigned char *Payload,
389 const unsigned char *Base,
390 const Info &InfoObj = Info())
391 : base_type(NumBuckets, NumEntries, Buckets, Base, InfoObj),
394 /// \brief Iterates over all of the keys in the table.
396 const unsigned char *Ptr;
397 offset_type NumItemsInBucketLeft;
398 offset_type NumEntriesLeft;
402 typedef external_key_type value_type;
404 key_iterator(const unsigned char *const Ptr, offset_type NumEntries,
406 : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries),
409 : Ptr(0), NumItemsInBucketLeft(0), NumEntriesLeft(0), InfoObj(0) {}
411 friend bool operator==(const key_iterator &X, const key_iterator &Y) {
412 return X.NumEntriesLeft == Y.NumEntriesLeft;
414 friend bool operator!=(const key_iterator &X, const key_iterator &Y) {
415 return X.NumEntriesLeft != Y.NumEntriesLeft;
418 key_iterator &operator++() { // Preincrement
419 using namespace llvm::support;
420 if (!NumItemsInBucketLeft) {
421 // 'Items' starts with a 16-bit unsigned integer representing the
422 // number of items in this bucket.
423 NumItemsInBucketLeft =
424 endian::readNext<uint16_t, little, unaligned>(Ptr);
426 Ptr += sizeof(hash_value_type); // Skip the hash.
427 // Determine the length of the key and the data.
428 const std::pair<offset_type, offset_type> &L =
429 Info::ReadKeyDataLength(Ptr);
430 Ptr += L.first + L.second;
431 assert(NumItemsInBucketLeft);
432 --NumItemsInBucketLeft;
433 assert(NumEntriesLeft);
437 key_iterator operator++(int) { // Postincrement
438 key_iterator tmp = *this; ++*this; return tmp;
441 value_type operator*() const {
442 const unsigned char *LocalPtr = Ptr;
443 if (!NumItemsInBucketLeft)
444 LocalPtr += 2; // number of items in bucket
445 LocalPtr += sizeof(hash_value_type); // Skip the hash.
447 // Determine the length of the key and the data.
448 const std::pair<offset_type, offset_type> &L =
449 Info::ReadKeyDataLength(LocalPtr);
452 const internal_key_type &Key = InfoObj->ReadKey(LocalPtr, L.first);
453 return InfoObj->GetExternalKey(Key);
457 key_iterator key_begin() {
458 return key_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
460 key_iterator key_end() { return key_iterator(); }
462 iterator_range<key_iterator> keys() {
463 return make_range(key_begin(), key_end());
466 /// \brief Iterates over all the entries in the table, returning the data.
467 class data_iterator {
468 const unsigned char *Ptr;
469 offset_type NumItemsInBucketLeft;
470 offset_type NumEntriesLeft;
474 typedef data_type value_type;
476 data_iterator(const unsigned char *const Ptr, offset_type NumEntries,
478 : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries),
481 : Ptr(0), NumItemsInBucketLeft(0), NumEntriesLeft(0), InfoObj(0) {}
483 bool operator==(const data_iterator &X) const {
484 return X.NumEntriesLeft == NumEntriesLeft;
486 bool operator!=(const data_iterator &X) const {
487 return X.NumEntriesLeft != NumEntriesLeft;
490 data_iterator &operator++() { // Preincrement
491 using namespace llvm::support;
492 if (!NumItemsInBucketLeft) {
493 // 'Items' starts with a 16-bit unsigned integer representing the
494 // number of items in this bucket.
495 NumItemsInBucketLeft =
496 endian::readNext<uint16_t, little, unaligned>(Ptr);
498 Ptr += sizeof(hash_value_type); // Skip the hash.
499 // Determine the length of the key and the data.
500 const std::pair<offset_type, offset_type> &L =
501 Info::ReadKeyDataLength(Ptr);
502 Ptr += L.first + L.second;
503 assert(NumItemsInBucketLeft);
504 --NumItemsInBucketLeft;
505 assert(NumEntriesLeft);
509 data_iterator operator++(int) { // Postincrement
510 data_iterator tmp = *this; ++*this; return tmp;
513 value_type operator*() const {
514 const unsigned char *LocalPtr = Ptr;
515 if (!NumItemsInBucketLeft)
516 LocalPtr += 2; // number of items in bucket
517 LocalPtr += sizeof(hash_value_type); // Skip the hash.
519 // Determine the length of the key and the data.
520 const std::pair<offset_type, offset_type> &L =
521 Info::ReadKeyDataLength(LocalPtr);
524 const internal_key_type &Key = InfoObj->ReadKey(LocalPtr, L.first);
525 return InfoObj->ReadData(Key, LocalPtr + L.first, L.second);
529 data_iterator data_begin() {
530 return data_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
532 data_iterator data_end() { return data_iterator(); }
534 iterator_range<data_iterator> data() {
535 return make_range(data_begin(), data_end());
538 /// \brief Create the hash table.
540 /// \param Buckets is the beginning of the hash table itself, which follows
541 /// the payload of entire structure. This is the value returned by
542 /// OnDiskHashTableGenerator::Emit.
544 /// \param Payload is the beginning of the data contained in the table. This
545 /// is Base plus any padding or header data that was stored, ie, the offset
546 /// that the stream was at when calling Emit.
548 /// \param Base is the point from which all offsets into the structure are
549 /// based. This is offset 0 in the stream that was used when Emitting the
551 static OnDiskIterableChainedHashTable *
552 Create(const unsigned char *Buckets, const unsigned char *const Payload,
553 const unsigned char *const Base, const Info &InfoObj = Info()) {
554 using namespace llvm::support;
555 assert(Buckets > Base);
556 assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
557 "buckets should be 4-byte aligned.");
559 offset_type NumBuckets =
560 endian::readNext<offset_type, little, aligned>(Buckets);
561 offset_type NumEntries =
562 endian::readNext<offset_type, little, aligned>(Buckets);
563 return new OnDiskIterableChainedHashTable<Info>(
564 NumBuckets, NumEntries, Buckets, Payload, Base, InfoObj);
568 } // end namespace llvm
570 #endif // LLVM_SUPPORT_ON_DISK_HASH_TABLE_H