• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===--- OnDiskHashTable.h - On-Disk Hash Table Implementation --*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief Defines facilities for reading and writing on-disk hash tables.
12 ///
13 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_SUPPORT_ONDISKHASHTABLE_H
15 #define LLVM_SUPPORT_ONDISKHASHTABLE_H
16 
17 #include "llvm/Support/AlignOf.h"
18 #include "llvm/Support/Allocator.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"
24 #include <cassert>
25 #include <cstdlib>
26 
27 namespace llvm {
28 
29 /// \brief Generates an on disk hash table.
30 ///
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:
34 ///
35 /// \code
36 /// class ExampleInfo {
37 /// public:
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.
44 ///
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);
56 ///   /// Determine if two keys are equal. Optional, only needed by contains.
57 ///   static bool EqualKey(key_type_ref Key1, key_type_ref Key2);
58 /// };
59 /// \endcode
60 template <typename Info> class OnDiskChainedHashTableGenerator {
61   /// \brief A single item in the hash table.
62   class Item {
63   public:
64     typename Info::key_type Key;
65     typename Info::data_type Data;
66     Item *Next;
67     const typename Info::hash_value_type Hash;
68 
Item(typename Info::key_type_ref Key,typename Info::data_type_ref Data,Info & InfoObj)69     Item(typename Info::key_type_ref Key, typename Info::data_type_ref Data,
70          Info &InfoObj)
71         : Key(Key), Data(Data), Next(nullptr), Hash(InfoObj.ComputeHash(Key)) {}
72   };
73 
74   typedef typename Info::offset_type offset_type;
75   offset_type NumBuckets;
76   offset_type NumEntries;
77   llvm::SpecificBumpPtrAllocator<Item> BA;
78 
79   /// \brief A linked list of values in a particular hash bucket.
80   struct Bucket {
81     offset_type Off;
82     unsigned Length;
83     Item *Head;
84   };
85 
86   Bucket *Buckets;
87 
88 private:
89   /// \brief Insert an item into the appropriate hash bucket.
insert(Bucket * Buckets,size_t Size,Item * E)90   void insert(Bucket *Buckets, size_t Size, Item *E) {
91     Bucket &B = Buckets[E->Hash & (Size - 1)];
92     E->Next = B.Head;
93     ++B.Length;
94     B.Head = E;
95   }
96 
97   /// \brief Resize the hash table, moving the old entries into the new buckets.
resize(size_t NewSize)98   void resize(size_t NewSize) {
99     Bucket *NewBuckets = (Bucket *)std::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;) {
103         Item *N = E->Next;
104         E->Next = nullptr;
105         insert(NewBuckets, NewSize, E);
106         E = N;
107       }
108 
109     free(Buckets);
110     NumBuckets = NewSize;
111     Buckets = NewBuckets;
112   }
113 
114 public:
115   /// \brief Insert an entry into the table.
insert(typename Info::key_type_ref Key,typename Info::data_type_ref Data)116   void insert(typename Info::key_type_ref Key,
117               typename Info::data_type_ref Data) {
118     Info InfoObj;
119     insert(Key, Data, InfoObj);
120   }
121 
122   /// \brief Insert an entry into the table.
123   ///
124   /// Uses the provided Info instead of a stack allocated one.
insert(typename Info::key_type_ref Key,typename Info::data_type_ref Data,Info & InfoObj)125   void insert(typename Info::key_type_ref Key,
126               typename Info::data_type_ref Data, Info &InfoObj) {
127     ++NumEntries;
128     if (4 * NumEntries >= 3 * NumBuckets)
129       resize(NumBuckets * 2);
130     insert(Buckets, NumBuckets, new (BA.Allocate()) Item(Key, Data, InfoObj));
131   }
132 
133   /// \brief Determine whether an entry has been inserted.
contains(typename Info::key_type_ref Key,Info & InfoObj)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))
138         return true;
139     return false;
140   }
141 
142   /// \brief Emit the table to Out, which must not be at offset 0.
Emit(raw_ostream & Out)143   offset_type Emit(raw_ostream &Out) {
144     Info InfoObj;
145     return Emit(Out, InfoObj);
146   }
147 
148   /// \brief Emit the table to Out, which must not be at offset 0.
149   ///
150   /// Uses the provided Info instead of a stack allocated one.
Emit(raw_ostream & Out,Info & InfoObj)151   offset_type Emit(raw_ostream &Out, Info &InfoObj) {
152     using namespace llvm::support;
153     endian::Writer<little> LE(Out);
154 
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).
159     //
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.
164     //
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);
170 
171     // Emit the payload of the table.
172     for (offset_type I = 0; I < NumBuckets; ++I) {
173       Bucket &B = Buckets[I];
174       if (!B.Head)
175         continue;
176 
177       // Store the offset for the data of this bucket.
178       B.Off = Out.tell();
179       assert(B.Off && "Cannot write a bucket at offset 0. Please add padding.");
180 
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?");
184 
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);
190 #ifdef NDEBUG
191         InfoObj.EmitKey(Out, I->Key, Len.first);
192         InfoObj.EmitData(Out, I->Key, I->Data, Len.second);
193 #else
194         // In asserts mode, check that the users length matches the data they
195         // wrote.
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");
205 #endif
206       }
207     }
208 
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 = llvm::OffsetToAlignment(TableOff, alignOf<offset_type>());
212     TableOff += N;
213     while (N--)
214       LE.write<uint8_t>(0);
215 
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);
221 
222     return TableOff;
223   }
224 
OnDiskChainedHashTableGenerator()225   OnDiskChainedHashTableGenerator() {
226     NumEntries = 0;
227     NumBuckets = 64;
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 = (Bucket *)std::calloc(NumBuckets, sizeof(Bucket));
231   }
232 
~OnDiskChainedHashTableGenerator()233   ~OnDiskChainedHashTableGenerator() { std::free(Buckets); }
234 };
235 
236 /// \brief Provides lookup on an on disk hash table.
237 ///
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:
241 ///
242 /// \code
243 /// class ExampleLookupInfo {
244 /// public:
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.
250 ///
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);
272 /// };
273 /// \endcode
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;
279   Info InfoObj;
280 
281 public:
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;
288 
289   OnDiskChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
290                          const unsigned char *Buckets,
291                          const unsigned char *Base,
292                          const Info &InfoObj = Info())
NumBuckets(NumBuckets)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");
297   }
298 
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>
readNumBucketsAndEntries(const unsigned char * & Buckets)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);
312   }
313 
getNumBuckets()314   offset_type getNumBuckets() const { return NumBuckets; }
getNumEntries()315   offset_type getNumEntries() const { return NumEntries; }
getBase()316   const unsigned char *getBase() const { return Base; }
getBuckets()317   const unsigned char *getBuckets() const { return Buckets; }
318 
isEmpty()319   bool isEmpty() const { return NumEntries == 0; }
320 
321   class iterator {
322     internal_key_type Key;
323     const unsigned char *const Data;
324     const offset_type Len;
325     Info *InfoObj;
326 
327   public:
iterator()328     iterator() : Key(), Data(nullptr), Len(0), InfoObj(nullptr) {}
iterator(const internal_key_type K,const unsigned char * D,offset_type L,Info * InfoObj)329     iterator(const internal_key_type K, const unsigned char *D, offset_type L,
330              Info *InfoObj)
331         : Key(K), Data(D), Len(L), InfoObj(InfoObj) {}
332 
333     data_type operator*() const { return InfoObj->ReadData(Key, Data, Len); }
334 
getDataPtr()335     const unsigned char *getDataPtr() const { return Data; }
getDataLen()336     offset_type getDataLen() const { return Len; }
337 
338     bool operator==(const iterator &X) const { return X.Data == Data; }
339     bool operator!=(const iterator &X) const { return X.Data != Data; }
340   };
341 
342   /// \brief 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);
347   }
348 
349   /// \brief 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;
353 
354     if (!InfoPtr)
355       InfoPtr = &InfoObj;
356 
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;
360 
361     offset_type Offset = endian::readNext<offset_type, little, aligned>(Bucket);
362     if (Offset == 0)
363       return iterator(); // Empty bucket.
364     const unsigned char *Items = Base + Offset;
365 
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);
369 
370     for (unsigned i = 0; i < Len; ++i) {
371       // Read the hash.
372       hash_value_type ItemHash =
373           endian::readNext<hash_value_type, little, unaligned>(Items);
374 
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;
379 
380       // Compare the hashes.  If they are not the same, skip the entry entirely.
381       if (ItemHash != KeyHash) {
382         Items += ItemLen;
383         continue;
384       }
385 
386       // Read the key.
387       const internal_key_type &X =
388           InfoPtr->ReadKey((const unsigned char *const)Items, L.first);
389 
390       // If the key doesn't match just skip reading the value.
391       if (!InfoPtr->EqualKey(X, IKey)) {
392         Items += ItemLen;
393         continue;
394       }
395 
396       // The key matches!
397       return iterator(X, Items + L.first, L.second, InfoPtr);
398     }
399 
400     return iterator();
401   }
402 
end()403   iterator end() const { return iterator(); }
404 
getInfoObj()405   Info &getInfoObj() { return InfoObj; }
406 
407   /// \brief Create the hash table.
408   ///
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.
412   ///
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
415   /// table.
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);
424   }
425 };
426 
427 /// \brief Provides lookup and iteration over an on disk hash table.
428 ///
429 /// \copydetails llvm::OnDiskChainedHashTable
430 template <typename Info>
431 class OnDiskIterableChainedHashTable : public OnDiskChainedHashTable<Info> {
432   const unsigned char *Payload;
433 
434 public:
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;
441 
442 private:
443   /// \brief 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;
448 
449   public:
450     typedef external_key_type value_type;
451 
iterator_base(const unsigned char * const Ptr,offset_type NumEntries)452     iterator_base(const unsigned char *const Ptr, offset_type NumEntries)
453         : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries) {}
iterator_base()454     iterator_base()
455         : Ptr(nullptr), NumItemsInBucketLeft(0), NumEntriesLeft(0) {}
456 
457     friend bool operator==(const iterator_base &X, const iterator_base &Y) {
458       return X.NumEntriesLeft == Y.NumEntriesLeft;
459     }
460     friend bool operator!=(const iterator_base &X, const iterator_base &Y) {
461       return X.NumEntriesLeft != Y.NumEntriesLeft;
462     }
463 
464     /// Move to the next item.
advance()465     void advance() {
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);
472       }
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);
481       --NumEntriesLeft;
482     }
483 
484     /// Get the start of the item as written by the trait (after the hash and
485     /// immediately before the key and value length).
getItem()486     const unsigned char *getItem() const {
487       return Ptr + (NumItemsInBucketLeft ? 0 : 2) + sizeof(hash_value_type);
488     }
489   };
490 
491 public:
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())
base_type(NumBuckets,NumEntries,Buckets,Base,InfoObj)497       : base_type(NumBuckets, NumEntries, Buckets, Base, InfoObj),
498         Payload(Payload) {}
499 
500   /// \brief Iterates over all of the keys in the table.
501   class key_iterator : public iterator_base {
502     Info *InfoObj;
503 
504   public:
505     typedef external_key_type value_type;
506 
key_iterator(const unsigned char * const Ptr,offset_type NumEntries,Info * InfoObj)507     key_iterator(const unsigned char *const Ptr, offset_type NumEntries,
508                  Info *InfoObj)
509         : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
key_iterator()510     key_iterator() : iterator_base(), InfoObj() {}
511 
512     key_iterator &operator++() {
513       this->advance();
514       return *this;
515     }
516     key_iterator operator++(int) { // Postincrement
517       key_iterator tmp = *this;
518       ++*this;
519       return tmp;
520     }
521 
getInternalKey()522     internal_key_type getInternalKey() const {
523       auto *LocalPtr = this->getItem();
524 
525       // Determine the length of the key and the data.
526       auto L = Info::ReadKeyDataLength(LocalPtr);
527 
528       // Read the key.
529       return InfoObj->ReadKey(LocalPtr, L.first);
530     }
531 
532     value_type operator*() const {
533       return InfoObj->GetExternalKey(getInternalKey());
534     }
535   };
536 
key_begin()537   key_iterator key_begin() {
538     return key_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
539   }
key_end()540   key_iterator key_end() { return key_iterator(); }
541 
keys()542   iterator_range<key_iterator> keys() {
543     return make_range(key_begin(), key_end());
544   }
545 
546   /// \brief Iterates over all the entries in the table, returning the data.
547   class data_iterator : public iterator_base {
548     Info *InfoObj;
549 
550   public:
551     typedef data_type value_type;
552 
data_iterator(const unsigned char * const Ptr,offset_type NumEntries,Info * InfoObj)553     data_iterator(const unsigned char *const Ptr, offset_type NumEntries,
554                   Info *InfoObj)
555         : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
data_iterator()556     data_iterator() : iterator_base(), InfoObj() {}
557 
558     data_iterator &operator++() { // Preincrement
559       this->advance();
560       return *this;
561     }
562     data_iterator operator++(int) { // Postincrement
563       data_iterator tmp = *this;
564       ++*this;
565       return tmp;
566     }
567 
568     value_type operator*() const {
569       auto *LocalPtr = this->getItem();
570 
571       // Determine the length of the key and the data.
572       auto L = Info::ReadKeyDataLength(LocalPtr);
573 
574       // Read the key.
575       const internal_key_type &Key = InfoObj->ReadKey(LocalPtr, L.first);
576       return InfoObj->ReadData(Key, LocalPtr + L.first, L.second);
577     }
578   };
579 
data_begin()580   data_iterator data_begin() {
581     return data_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
582   }
data_end()583   data_iterator data_end() { return data_iterator(); }
584 
data()585   iterator_range<data_iterator> data() {
586     return make_range(data_begin(), data_end());
587   }
588 
589   /// \brief Create the hash table.
590   ///
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.
594   ///
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.
598   ///
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
601   /// table.
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);
611   }
612 };
613 
614 } // end namespace llvm
615 
616 #endif
617