Line data Source code
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 : /// 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/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"
23 : #include <cassert>
24 : #include <cstdlib>
25 :
26 : namespace llvm {
27 :
28 : /// Generates an on disk hash table.
29 : ///
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:
33 : ///
34 : /// \code
35 : /// class ExampleInfo {
36 : /// public:
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.
43 : ///
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);
57 : /// };
58 : /// \endcode
59 : template <typename Info> class OnDiskChainedHashTableGenerator {
60 : /// A single item in the hash table.
61 81205 : class Item {
62 : public:
63 : typename Info::key_type Key;
64 : typename Info::data_type Data;
65 : Item *Next;
66 : const typename Info::hash_value_type Hash;
67 :
68 403 : Item(typename Info::key_type_ref Key, typename Info::data_type_ref Data,
69 : Info &InfoObj)
70 403 : : Key(Key), Data(Data), Next(nullptr), Hash(InfoObj.ComputeHash(Key)) {}
71 0 : };
72 :
73 0 : typedef typename Info::offset_type offset_type;
74 0 : offset_type NumBuckets;
75 : offset_type NumEntries;
76 0 : llvm::SpecificBumpPtrAllocator<Item> BA;
77 0 :
78 : /// A linked list of values in a particular hash bucket.
79 0 : struct Bucket {
80 0 : offset_type Off;
81 : unsigned Length;
82 0 : Item *Head;
83 : };
84 :
85 : Bucket *Buckets;
86 :
87 : private:
88 : /// Insert an item into the appropriate hash bucket.
89 0 : void insert(Bucket *Buckets, size_t Size, Item *E) {
90 781 : Bucket &B = Buckets[E->Hash & (Size - 1)];
91 781 : E->Next = B.Head;
92 781 : ++B.Length;
93 781 : B.Head = E;
94 0 : }
95 0 :
96 0 : /// Resize the hash table, moving the old entries into the new buckets.
97 227 : void resize(size_t NewSize) {
98 0 : Bucket *NewBuckets = static_cast<Bucket *>(
99 227 : safe_calloc(NewSize, sizeof(Bucket)));
100 0 : // Populate NewBuckets with the old entries.
101 14755 : for (size_t I = 0; I < NumBuckets; ++I)
102 14906 : for (Item *E = Buckets[I].Head; E;) {
103 378 : Item *N = E->Next;
104 0 : E->Next = nullptr;
105 0 : insert(NewBuckets, NewSize, E);
106 0 : E = N;
107 0 : }
108 0 :
109 227 : free(Buckets);
110 227 : NumBuckets = NewSize;
111 227 : Buckets = NewBuckets;
112 227 : }
113 0 :
114 0 : public:
115 0 : /// Insert an entry into the table.
116 0 : void insert(typename Info::key_type_ref Key,
117 0 : typename Info::data_type_ref Data) {
118 0 : Info InfoObj;
119 403 : insert(Key, Data, InfoObj);
120 0 : }
121 0 :
122 0 : /// Insert an entry into the table.
123 0 : ///
124 0 : /// Uses the provided Info instead of a stack allocated one.
125 403 : void insert(typename Info::key_type_ref Key,
126 0 : typename Info::data_type_ref Data, Info &InfoObj) {
127 403 : ++NumEntries;
128 403 : if (4 * NumEntries >= 3 * NumBuckets)
129 0 : resize(NumBuckets * 2);
130 403 : insert(Buckets, NumBuckets, new (BA.Allocate()) Item(Key, Data, InfoObj));
131 403 : }
132 :
133 0 : /// Determine whether an entry has been inserted.
134 : bool contains(typename Info::key_type_ref Key, Info &InfoObj) {
135 0 : unsigned Hash = InfoObj.ComputeHash(Key);
136 0 : for (Item *I = Buckets[Hash & (NumBuckets - 1)].Head; I; I = I->Next)
137 0 : if (I->Hash == Hash && InfoObj.EqualKey(I->Key, Key))
138 0 : return true;
139 0 : return false;
140 0 : }
141 :
142 : /// Emit the table to Out, which must not be at offset 0.
143 0 : offset_type Emit(raw_ostream &Out) {
144 0 : Info InfoObj;
145 0 : return Emit(Out, InfoObj);
146 0 : }
147 0 :
148 0 : /// Emit the table to Out, which must not be at offset 0.
149 0 : ///
150 : /// Uses the provided Info instead of a stack allocated one.
151 228 : offset_type Emit(raw_ostream &Out, Info &InfoObj) {
152 0 : using namespace llvm::support;
153 0 : endian::Writer LE(Out, little);
154 0 :
155 0 : // Now we're done adding entries, resize the bucket list if it's
156 0 : // 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 0 : //
160 0 : // As a special case, if there are two or fewer entries, just
161 0 : // form a single bucket. A linear scan is fine in that case, and
162 0 : // this is very common in C++ class lookup tables. This also
163 0 : // guarantees we produce at least one bucket for an empty table.
164 0 : //
165 0 : // FIXME: Try computing a perfect hash function at this point.
166 45 : unsigned TargetNumBuckets =
167 228 : NumEntries <= 2 ? 1 : NextPowerOf2(NumEntries * 4 / 3);
168 228 : if (TargetNumBuckets != NumBuckets)
169 245 : resize(TargetNumBuckets);
170 0 :
171 0 : // Emit the payload of the table.
172 891 : for (offset_type I = 0; I < NumBuckets; ++I) {
173 663 : Bucket &B = Buckets[I];
174 663 : if (!B.Head)
175 0 : continue;
176 :
177 0 : // Store the offset for the data of this bucket.
178 333 : B.Off = Out.tell();
179 0 : assert(B.Off && "Cannot write a bucket at offset 0. Please add padding.");
180 0 :
181 0 : // Write out the number of items in the bucket.
182 333 : LE.write<uint16_t>(B.Length);
183 0 : assert(B.Length != 0 && "Bucket has a head but zero length?");
184 0 :
185 0 : // Write out the entries in the bucket.
186 736 : for (Item *I = B.Head; I; I = I->Next) {
187 403 : LE.write<typename Info::hash_value_type>(I->Hash);
188 403 : const std::pair<offset_type, offset_type> &Len =
189 403 : InfoObj.EmitKeyDataLength(Out, I->Key, I->Data);
190 : #ifdef NDEBUG
191 403 : InfoObj.EmitKey(Out, I->Key, Len.first);
192 403 : InfoObj.EmitData(Out, I->Key, I->Data, Len.second);
193 0 : #else
194 0 : // In asserts mode, check that the users length matches the data they
195 0 : // wrote.
196 0 : uint64_t KeyStart = Out.tell();
197 0 : InfoObj.EmitKey(Out, I->Key, Len.first);
198 : uint64_t DataStart = Out.tell();
199 0 : InfoObj.EmitData(Out, I->Key, I->Data, Len.second);
200 : uint64_t End = Out.tell();
201 0 : assert(offset_type(DataStart - KeyStart) == Len.first &&
202 0 : "key length does not match bytes written");
203 0 : assert(offset_type(End - DataStart) == Len.second &&
204 0 : "data length does not match bytes written");
205 : #endif
206 : }
207 : }
208 :
209 10 : // Pad with zeros so that we can start the hashtable at an aligned address.
210 0 : offset_type TableOff = Out.tell();
211 0 : uint64_t N = llvm::OffsetToAlignment(TableOff, alignof(offset_type));
212 0 : TableOff += N;
213 723 : while (N--)
214 : LE.write<uint8_t>(0);
215 0 :
216 : // Emit the hashtable itself.
217 228 : LE.write<offset_type>(NumBuckets);
218 228 : LE.write<offset_type>(NumEntries);
219 891 : for (offset_type I = 0; I < NumBuckets; ++I)
220 663 : LE.write<offset_type>(Buckets[I].Off);
221 :
222 228 : return TableOff;
223 : }
224 :
225 817 : OnDiskChainedHashTableGenerator() {
226 817 : NumEntries = 0;
227 817 : NumBuckets = 64;
228 0 : // Note that we do not need to run the constructors of the individual
229 0 : // Bucket objects since 'calloc' returns bytes that are all 0.
230 817 : Buckets = static_cast<Bucket *>(safe_calloc(NumBuckets, sizeof(Bucket)));
231 817 : }
232 0 :
233 817 : ~OnDiskChainedHashTableGenerator() { std::free(Buckets); }
234 0 : };
235 0 :
236 0 : /// Provides lookup on an on disk hash table.
237 0 : ///
238 0 : /// This needs an \c Info that handles reading values from the hash table's
239 0 : /// payload and computes the hash for a given key. This should provide the
240 : /// following interface:
241 0 : ///
242 0 : /// \code
243 0 : /// class ExampleLookupInfo {
244 0 : /// public:
245 0 : /// typedef ExampleData data_type;
246 0 : /// typedef ExampleInternalKey internal_key_type; // The stored key type.
247 : /// typedef ExampleKey external_key_type; // The type to pass to find().
248 0 : /// typedef uint32_t hash_value_type; // The type the hash function returns.
249 0 : /// typedef uint32_t offset_type; // The type for offsets into the table.
250 0 : ///
251 0 : /// /// Compare two keys for equality.
252 0 : /// static bool EqualKey(internal_key_type &Key1, internal_key_type &Key2);
253 0 : /// /// Calculate the hash for the given key.
254 : /// static hash_value_type ComputeHash(internal_key_type &IKey);
255 0 : /// /// Translate from the semantic type of a key in the hash table to the
256 0 : /// /// type that is actually stored and used for hashing and comparisons.
257 0 : /// /// The internal and external types are often the same, in which case this
258 0 : /// /// can simply return the passed in value.
259 0 : /// 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 0 : /// static std::pair<offset_type, offset_type>
263 0 : /// ReadKeyDataLength(const unsigned char *&Buffer);
264 0 : /// /// Read the key from Buffer, given the KeyLen as reported from
265 0 : /// /// ReadKeyDataLength.
266 0 : /// 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 0 : template <typename Info> class OnDiskChainedHashTable {
275 : const typename Info::offset_type NumBuckets;
276 0 : const typename Info::offset_type NumEntries;
277 0 : const unsigned char *const Buckets;
278 : const unsigned char *const Base;
279 24943 : Info InfoObj;
280 :
281 0 : public:
282 0 : typedef Info InfoType;
283 0 : typedef typename Info::internal_key_type internal_key_type;
284 0 : typedef typename Info::external_key_type external_key_type;
285 : typedef typename Info::data_type data_type;
286 0 : typedef typename Info::hash_value_type hash_value_type;
287 : typedef typename Info::offset_type offset_type;
288 0 :
289 26737 : 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 26325 : Base(Base), InfoObj(InfoObj) {
295 24943 : assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
296 24943 : "'buckets' must have a 4-byte alignment");
297 22445 : }
298 0 :
299 : /// Read the number of buckets and the number of entries from a hash table
300 13278154 : /// produced by OnDiskHashTableGenerator::Emit, and advance the Buckets
301 13253211 : /// pointer past them.
302 13253211 : static std::pair<offset_type, offset_type>
303 0 : readNumBucketsAndEntries(const unsigned char *&Buckets) {
304 0 : assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
305 0 : "buckets should be 4-byte aligned.");
306 4553570 : using namespace llvm::support;
307 0 : offset_type NumBuckets =
308 : endian::readNext<offset_type, little, aligned>(Buckets);
309 0 : offset_type NumEntries =
310 4553570 : endian::readNext<offset_type, little, aligned>(Buckets);
311 0 : return std::make_pair(NumBuckets, NumEntries);
312 0 : }
313 :
314 10212502 : offset_type getNumBuckets() const { return NumBuckets; }
315 5658932 : offset_type getNumEntries() const { return NumEntries; }
316 5658932 : const unsigned char *getBase() const { return Base; }
317 88059 : const unsigned char *getBuckets() const { return Buckets; }
318 :
319 5658932 : bool isEmpty() const { return NumEntries == 0; }
320 5658932 :
321 : class iterator {
322 : internal_key_type Key;
323 0 : const unsigned char *const Data;
324 0 : const offset_type Len;
325 0 : Info *InfoObj;
326 0 :
327 : public:
328 1044926 : iterator() : Key(), Data(nullptr), Len(0), InfoObj(nullptr) {}
329 439993 : iterator(const internal_key_type K, const unsigned char *D, offset_type L,
330 : Info *InfoObj)
331 439993 : : Key(K), Data(D), Len(L), InfoObj(InfoObj) {}
332 :
333 413289 : data_type operator*() const { return InfoObj->ReadData(Key, Data, Len); }
334 :
335 0 : const unsigned char *getDataPtr() const { return Data; }
336 0 : offset_type getDataLen() const { return Len; }
337 :
338 24943 : bool operator==(const iterator &X) const { return X.Data == Data; }
339 0 : bool operator!=(const iterator &X) const { return X.Data != Data; }
340 24943 : };
341 55393 :
342 : /// Look up the stored data for a particular key.
343 7208 : iterator find(const external_key_type &EKey, Info *InfoPtr = nullptr) {
344 790 : const internal_key_type &IKey = InfoObj.GetInternalKey(EKey);
345 32358 : hash_value_type KeyHash = InfoObj.ComputeHash(IKey);
346 310486 : return find_hashed(IKey, KeyHash, InfoPtr);
347 13284444 : }
348 13253223 :
349 6290 : /// Look up the stored data for a particular key with a known hash.
350 1497023 : iterator find_hashed(const internal_key_type &IKey, hash_value_type KeyHash,
351 12 : Info *InfoPtr = nullptr) {
352 17737 : using namespace llvm::support;
353 0 :
354 1472080 : if (!InfoPtr)
355 104796 : InfoPtr = &InfoObj;
356 0 :
357 0 : // Each bucket is just an offset into the hash table file.
358 1478486 : offset_type Idx = KeyHash & (NumBuckets - 1);
359 1472080 : const unsigned char *Bucket = Buckets + sizeof(offset_type) * Idx;
360 6406 :
361 290812 : offset_type Offset = endian::readNext<offset_type, little, aligned>(Bucket);
362 1472080 : if (Offset == 0)
363 : return iterator(); // Empty bucket.
364 1215482 : const unsigned char *Items = Base + Offset;
365 6424 :
366 : // 'Items' starts with a 16-bit unsigned integer representing the
367 8120 : // number of items in this bucket.
368 1233219 : unsigned Len = endian::readNext<uint16_t, little, unaligned>(Items);
369 24161 :
370 1648793 : for (unsigned i = 0; i < Len; ++i) {
371 : // Read the hash.
372 284406 : hash_value_type ItemHash =
373 455760 : endian::readNext<hash_value_type, little, unaligned>(Items);
374 153617 :
375 147193 : // Determine the length of the key and the data.
376 284406 : const std::pair<offset_type, offset_type> &L =
377 1423696 : Info::ReadKeyDataLength(Items);
378 1133794 : offset_type ItemLen = L.first + L.second;
379 64937 :
380 284406 : // Compare the hashes. If they are not the same, skip the entry entirely.
381 1133794 : if (ItemHash != KeyHash) {
382 830330 : Items += ItemLen;
383 749121 : continue;
384 0 : }
385 6149 :
386 146146 : // Read the key.
387 593080 : const internal_key_type &X =
388 397191 : InfoPtr->ReadKey((const unsigned char *const)Items, L.first);
389 81904 :
390 81904 : // If the key doesn't match just skip reading the value.
391 426876 : if (!InfoPtr->EqualKey(X, IKey)) {
392 91530 : Items += ItemLen;
393 95016 : continue;
394 : }
395 :
396 178917 : // The key matches!
397 443461 : return iterator(X, Items + L.first, L.second, InfoPtr);
398 3477 : }
399 175431 :
400 169140 : return iterator();
401 169140 : }
402 219 :
403 0 : iterator end() const { return iterator(); }
404 :
405 6708 : Info &getInfoObj() { return InfoObj; }
406 228 :
407 219 : /// Create the hash table.
408 0 : ///
409 6291 : /// \param Buckets is the beginning of the hash table itself, which follows
410 220 : /// the payload of entire structure. This is the value returned by
411 17957 : /// OnDiskHashTableGenerator::Emit.
412 9 : ///
413 17737 : /// \param Base is the point from which all offsets into the structure are
414 38003 : /// based. This is offset 0 in the stream that was used when Emitting the
415 6290 : /// table.
416 144 : static OnDiskChainedHashTable *Create(const unsigned char *Buckets,
417 12 : const unsigned char *const Base,
418 17737 : const Info &InfoObj = Info()) {
419 17737 : assert(Buckets > Base);
420 165074 : auto NumBucketsAndEntries = readNumBucketsAndEntries(Buckets);
421 147205 : return new OnDiskChainedHashTable<Info>(NumBucketsAndEntries.first,
422 248 : NumBucketsAndEntries.second,
423 18973 : Buckets, Base, InfoObj);
424 : }
425 3528 : };
426 12 :
427 0 : /// Provides lookup and iteration over an on disk hash table.
428 0 : ///
429 185 : /// \copydetails llvm::OnDiskChainedHashTable
430 173 : template <typename Info>
431 419 : class OnDiskIterableChainedHashTable : public OnDiskChainedHashTable<Info> {
432 0 : const unsigned char *Payload;
433 173 :
434 92 : public:
435 114 : typedef OnDiskChainedHashTable<Info> base_type;
436 10 : typedef typename base_type::internal_key_type internal_key_type;
437 36 : typedef typename base_type::external_key_type external_key_type;
438 : typedef typename base_type::data_type data_type;
439 81 : typedef typename base_type::hash_value_type hash_value_type;
440 3221 : typedef typename base_type::offset_type offset_type;
441 3526 :
442 3521 : private:
443 1365 : /// Iterates over all of the keys in the table.
444 5 : class iterator_base {
445 17 : const unsigned char *Ptr;
446 13101949 : offset_type NumItemsInBucketLeft;
447 13098438 : offset_type NumEntriesLeft;
448 13098455 :
449 100 : public:
450 19 : typedef external_key_type value_type;
451 5 :
452 4486203 : iterator_base(const unsigned char *const Ptr, offset_type NumEntries)
453 : : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries) {}
454 47125 : iterator_base()
455 414 : : Ptr(nullptr), NumItemsInBucketLeft(0), NumEntriesLeft(0) {}
456 4486203 :
457 10 : friend bool operator==(const iterator_base &X, const iterator_base &Y) {
458 46998 : return X.NumEntriesLeft == Y.NumEntriesLeft;
459 46711 : }
460 10057076 : friend bool operator!=(const iterator_base &X, const iterator_base &Y) {
461 5570873 : return X.NumEntriesLeft != Y.NumEntriesLeft;
462 5617584 : }
463 46711 :
464 3 : /// Move to the next item.
465 5571090 : void advance() {
466 5617584 : using namespace llvm::support;
467 217 : if (!NumItemsInBucketLeft) {
468 33224 : // 'Items' starts with a 16-bit unsigned integer representing the
469 6 : // number of items in this bucket.
470 1409 : NumItemsInBucketLeft =
471 1409 : endian::readNext<uint16_t, little, unaligned>(Ptr);
472 33252 : }
473 251 : Ptr += sizeof(hash_value_type); // Skip the hash.
474 53629 : // Determine the length of the key and the data.
475 0 : const std::pair<offset_type, offset_type> &L =
476 0 : Info::ReadKeyDataLength(Ptr);
477 223 : Ptr += L.first + L.second;
478 6 : assert(NumItemsInBucketLeft);
479 217 : --NumItemsInBucketLeft;
480 : assert(NumEntriesLeft);
481 42657 : --NumEntriesLeft;
482 42651 : }
483 102119 :
484 3516 : /// Get the start of the item as written by the trait (after the hash and
485 144547 : /// immediately before the key and value length).
486 23915 : const unsigned char *getItem() const {
487 29767 : return Ptr + (NumItemsInBucketLeft ? 0 : 2) + sizeof(hash_value_type);
488 76694 : }
489 76703 : };
490 :
491 127664 : public:
492 16497 : OnDiskIterableChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
493 13101949 : const unsigned char *Buckets,
494 13196797 : const unsigned char *Payload,
495 102113 : const unsigned char *Base,
496 3516 : const Info &InfoObj = Info())
497 102121 : : base_type(NumBuckets, NumEntries, Buckets, Base, InfoObj),
498 13155 : Payload(Payload) {}
499 102113 :
500 102121 : /// Iterates over all of the keys in the table.
501 25787 : class key_iterator : public iterator_base {
502 3 : Info *InfoObj;
503 3749 :
504 : public:
505 : typedef external_key_type value_type;
506 59847 :
507 2771 : key_iterator(const unsigned char *const Ptr, offset_type NumEntries,
508 : Info *InfoObj)
509 3749 : : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
510 57081 : key_iterator() : iterator_base(), InfoObj() {}
511 57076 :
512 0 : key_iterator &operator++() {
513 3817 : this->advance();
514 57250 : return *this;
515 60999 : }
516 179 : key_iterator operator++(int) { // Postincrement
517 3749 : key_iterator tmp = *this;
518 60825 : ++*this;
519 99403 : return tmp;
520 51134 : }
521 105635 :
522 : internal_key_type getInternalKey() const {
523 15 : auto *LocalPtr = this->getItem();
524 124192 :
525 80754 : // Determine the length of the key and the data.
526 131995 : auto L = Info::ReadKeyDataLength(LocalPtr);
527 98364 :
528 : // Read the key.
529 6831 : return InfoObj->ReadKey(LocalPtr, L.first);
530 104770 : }
531 98364 :
532 : value_type operator*() const {
533 185720 : return InfoObj->GetExternalKey(getInternalKey());
534 80525 : }
535 101560 : };
536 98906 :
537 79983 : key_iterator key_begin() {
538 66254 : return key_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
539 68900 : }
540 0 : key_iterator key_end() { return key_iterator(); }
541 9863 :
542 : iterator_range<key_iterator> keys() {
543 14279 : return make_range(key_begin(), key_end());
544 0 : }
545 :
546 0 : /// Iterates over all the entries in the table, returning the data.
547 14279 : class data_iterator : public iterator_base {
548 9616 : Info *InfoObj;
549 13077 :
550 : public:
551 : typedef data_type value_type;
552 4867 :
553 8123 : data_iterator(const unsigned char *const Ptr, offset_type NumEntries,
554 3460 : Info *InfoObj)
555 : : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
556 409 : data_iterator() : iterator_base(), InfoObj() {}
557 174 :
558 1367468 : data_iterator &operator++() { // Preincrement
559 376 : this->advance();
560 348 : return *this;
561 : }
562 1367285 : data_iterator operator++(int) { // Postincrement
563 0 : data_iterator tmp = *this;
564 174 : ++*this;
565 174 : return tmp;
566 1368323 : }
567 1368149 :
568 219 : value_type operator*() const {
569 392 : auto *LocalPtr = this->getItem();
570 1367284 :
571 3516 : // Determine the length of the key and the data.
572 846673 : auto L = Info::ReadKeyDataLength(LocalPtr);
573 :
574 0 : // Read the key.
575 218 : const internal_key_type &Key = InfoObj->ReadKey(LocalPtr, L.first);
576 846891 : return InfoObj->ReadData(Key, LocalPtr + L.first, L.second);
577 : }
578 1444443 : };
579 :
580 : data_iterator data_begin() {
581 409 : return data_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
582 : }
583 0 : data_iterator data_end() { return data_iterator(); }
584 42 :
585 1010276 : iterator_range<data_iterator> data() {
586 1010528 : return make_range(data_begin(), data_end());
587 7265 : }
588 3516 :
589 1013785 : /// Create the hash table.
590 597760 : ///
591 597760 : /// \param Buckets is the beginning of the hash table itself, which follows
592 10240 : /// the payload of entire structure. This is the value returned by
593 6720 : /// OnDiskHashTableGenerator::Emit.
594 6720 : ///
595 412516 : /// \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 3749 : /// that the stream was at when calling Emit.
598 4677 : ///
599 412516 : /// \param Base is the point from which all offsets into the structure are
600 10 : /// based. This is offset 0 in the stream that was used when Emitting the
601 10 : /// table.
602 4677 : static OnDiskIterableChainedHashTable *
603 409 : Create(const unsigned char *Buckets, const unsigned char *const Payload,
604 : const unsigned char *const Base, const Info &InfoObj = Info()) {
605 412506 : assert(Buckets > Base);
606 10290 : auto NumBucketsAndEntries =
607 5613 : OnDiskIterableChainedHashTable<Info>::readNumBucketsAndEntries(Buckets);
608 6022 : return new OnDiskIterableChainedHashTable<Info>(
609 5613 : NumBucketsAndEntries.first, NumBucketsAndEntries.second,
610 409 : Buckets, Payload, Base, InfoObj);
611 5613 : }
612 5627 : };
613 22035 :
614 0 : } // end namespace llvm
615 :
616 : #endif
|
