LLVM  10.0.0svn
OnDiskHashTable.h
Go to the documentation of this file.
1 //===--- OnDiskHashTable.h - On-Disk Hash Table Implementation --*- C++ -*-===//
2 //
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
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// Defines facilities for reading and writing on-disk hash tables.
11 ///
12 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_SUPPORT_ONDISKHASHTABLE_H
14 #define LLVM_SUPPORT_ONDISKHASHTABLE_H
15 
16 #include "llvm/Support/Alignment.h"
17 #include "llvm/Support/Allocator.h"
18 #include "llvm/Support/DataTypes.h"
20 #include "llvm/Support/Host.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  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  Item(typename Info::key_type_ref Key, typename Info::data_type_ref Data,
69  Info &InfoObj)
70  : Key(Key), Data(Data), Next(nullptr), Hash(InfoObj.ComputeHash(Key)) {}
71  };
72 
73  typedef typename Info::offset_type offset_type;
74  offset_type NumBuckets;
75  offset_type NumEntries;
77 
78  /// A linked list of values in a particular hash bucket.
79  struct Bucket {
80  offset_type Off;
81  unsigned Length;
82  Item *Head;
83  };
84 
85  Bucket *Buckets;
86 
87 private:
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)];
91  E->Next = B.Head;
92  ++B.Length;
93  B.Head = E;
94  }
95 
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;) {
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  /// Insert an entry into the table.
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  /// Insert an entry into the table.
123  ///
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) {
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  /// 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))
138  return true;
139  return false;
140  }
141 
142  /// Emit the table to Out, which must not be at offset 0.
143  offset_type Emit(raw_ostream &Out) {
144  Info InfoObj;
145  return Emit(Out, InfoObj);
146  }
147 
148  /// Emit the table to Out, which must not be at offset 0.
149  ///
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);
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 =
212  llvm::offsetToAlignment(TableOff, llvm::Align(alignof(offset_type)));
213  TableOff += N;
214  while (N--)
215  LE.write<uint8_t>(0);
216 
217  // Emit the hashtable itself.
218  LE.write<offset_type>(NumBuckets);
219  LE.write<offset_type>(NumEntries);
220  for (offset_type I = 0; I < NumBuckets; ++I)
221  LE.write<offset_type>(Buckets[I].Off);
222 
223  return TableOff;
224  }
225 
227  NumEntries = 0;
228  NumBuckets = 64;
229  // Note that we do not need to run the constructors of the individual
230  // Bucket objects since 'calloc' returns bytes that are all 0.
231  Buckets = static_cast<Bucket *>(safe_calloc(NumBuckets, sizeof(Bucket)));
232  }
233 
234  ~OnDiskChainedHashTableGenerator() { std::free(Buckets); }
235 };
236 
237 /// Provides lookup on an on disk hash table.
238 ///
239 /// This needs an \c Info that handles reading values from the hash table's
240 /// payload and computes the hash for a given key. This should provide the
241 /// following interface:
242 ///
243 /// \code
244 /// class ExampleLookupInfo {
245 /// public:
246 /// typedef ExampleData data_type;
247 /// typedef ExampleInternalKey internal_key_type; // The stored key type.
248 /// typedef ExampleKey external_key_type; // The type to pass to find().
249 /// typedef uint32_t hash_value_type; // The type the hash function returns.
250 /// typedef uint32_t offset_type; // The type for offsets into the table.
251 ///
252 /// /// Compare two keys for equality.
253 /// static bool EqualKey(internal_key_type &Key1, internal_key_type &Key2);
254 /// /// Calculate the hash for the given key.
255 /// static hash_value_type ComputeHash(internal_key_type &IKey);
256 /// /// Translate from the semantic type of a key in the hash table to the
257 /// /// type that is actually stored and used for hashing and comparisons.
258 /// /// The internal and external types are often the same, in which case this
259 /// /// can simply return the passed in value.
260 /// static const internal_key_type &GetInternalKey(external_key_type &EKey);
261 /// /// Read the key and data length from Buffer, leaving it pointing at the
262 /// /// following byte.
263 /// static std::pair<offset_type, offset_type>
264 /// ReadKeyDataLength(const unsigned char *&Buffer);
265 /// /// Read the key from Buffer, given the KeyLen as reported from
266 /// /// ReadKeyDataLength.
267 /// const internal_key_type &ReadKey(const unsigned char *Buffer,
268 /// offset_type KeyLen);
269 /// /// Read the data for Key from Buffer, given the DataLen as reported from
270 /// /// ReadKeyDataLength.
271 /// data_type ReadData(StringRef Key, const unsigned char *Buffer,
272 /// offset_type DataLen);
273 /// };
274 /// \endcode
275 template <typename Info> class OnDiskChainedHashTable {
276  const typename Info::offset_type NumBuckets;
277  const typename Info::offset_type NumEntries;
278  const unsigned char *const Buckets;
279  const unsigned char *const Base;
280  Info InfoObj;
281 
282 public:
283  typedef Info InfoType;
284  typedef typename Info::internal_key_type internal_key_type;
285  typedef typename Info::external_key_type external_key_type;
286  typedef typename Info::data_type data_type;
287  typedef typename Info::hash_value_type hash_value_type;
288  typedef typename Info::offset_type offset_type;
289 
290  OnDiskChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
291  const unsigned char *Buckets,
292  const unsigned char *Base,
293  const Info &InfoObj = Info())
294  : NumBuckets(NumBuckets), NumEntries(NumEntries), Buckets(Buckets),
295  Base(Base), InfoObj(InfoObj) {
296  assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
297  "'buckets' must have a 4-byte alignment");
298  }
299 
300  /// Read the number of buckets and the number of entries from a hash table
301  /// produced by OnDiskHashTableGenerator::Emit, and advance the Buckets
302  /// pointer past them.
303  static std::pair<offset_type, offset_type>
304  readNumBucketsAndEntries(const unsigned char *&Buckets) {
305  assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
306  "buckets should be 4-byte aligned.");
307  using namespace llvm::support;
308  offset_type NumBuckets =
309  endian::readNext<offset_type, little, aligned>(Buckets);
310  offset_type NumEntries =
311  endian::readNext<offset_type, little, aligned>(Buckets);
312  return std::make_pair(NumBuckets, NumEntries);
313  }
314 
315  offset_type getNumBuckets() const { return NumBuckets; }
316  offset_type getNumEntries() const { return NumEntries; }
317  const unsigned char *getBase() const { return Base; }
318  const unsigned char *getBuckets() const { return Buckets; }
319 
320  bool isEmpty() const { return NumEntries == 0; }
321 
322  class iterator {
323  internal_key_type Key;
324  const unsigned char *const Data;
325  const offset_type Len;
326  Info *InfoObj;
327 
328  public:
329  iterator() : Key(), Data(nullptr), Len(0), InfoObj(nullptr) {}
330  iterator(const internal_key_type K, const unsigned char *D, offset_type L,
331  Info *InfoObj)
332  : Key(K), Data(D), Len(L), InfoObj(InfoObj) {}
333 
334  data_type operator*() const { return InfoObj->ReadData(Key, Data, Len); }
335 
336  const unsigned char *getDataPtr() const { return Data; }
337  offset_type getDataLen() const { return Len; }
338 
339  bool operator==(const iterator &X) const { return X.Data == Data; }
340  bool operator!=(const iterator &X) const { return X.Data != Data; }
341  };
342 
343  /// Look up the stored data for a particular key.
344  iterator find(const external_key_type &EKey, Info *InfoPtr = nullptr) {
345  const internal_key_type &IKey = InfoObj.GetInternalKey(EKey);
346  hash_value_type KeyHash = InfoObj.ComputeHash(IKey);
347  return find_hashed(IKey, KeyHash, InfoPtr);
348  }
349 
350  /// Look up the stored data for a particular key with a known hash.
351  iterator find_hashed(const internal_key_type &IKey, hash_value_type KeyHash,
352  Info *InfoPtr = nullptr) {
353  using namespace llvm::support;
354 
355  if (!InfoPtr)
356  InfoPtr = &InfoObj;
357 
358  // Each bucket is just an offset into the hash table file.
359  offset_type Idx = KeyHash & (NumBuckets - 1);
360  const unsigned char *Bucket = Buckets + sizeof(offset_type) * Idx;
361 
362  offset_type Offset = endian::readNext<offset_type, little, aligned>(Bucket);
363  if (Offset == 0)
364  return iterator(); // Empty bucket.
365  const unsigned char *Items = Base + Offset;
366 
367  // 'Items' starts with a 16-bit unsigned integer representing the
368  // number of items in this bucket.
369  unsigned Len = endian::readNext<uint16_t, little, unaligned>(Items);
370 
371  for (unsigned i = 0; i < Len; ++i) {
372  // Read the hash.
373  hash_value_type ItemHash =
374  endian::readNext<hash_value_type, little, unaligned>(Items);
375 
376  // Determine the length of the key and the data.
377  const std::pair<offset_type, offset_type> &L =
378  Info::ReadKeyDataLength(Items);
379  offset_type ItemLen = L.first + L.second;
380 
381  // Compare the hashes. If they are not the same, skip the entry entirely.
382  if (ItemHash != KeyHash) {
383  Items += ItemLen;
384  continue;
385  }
386 
387  // Read the key.
388  const internal_key_type &X =
389  InfoPtr->ReadKey((const unsigned char *const)Items, L.first);
390 
391  // If the key doesn't match just skip reading the value.
392  if (!InfoPtr->EqualKey(X, IKey)) {
393  Items += ItemLen;
394  continue;
395  }
396 
397  // The key matches!
398  return iterator(X, Items + L.first, L.second, InfoPtr);
399  }
400 
401  return iterator();
402  }
403 
404  iterator end() const { return iterator(); }
405 
406  Info &getInfoObj() { return InfoObj; }
407 
408  /// Create the hash table.
409  ///
410  /// \param Buckets is the beginning of the hash table itself, which follows
411  /// the payload of entire structure. This is the value returned by
412  /// OnDiskHashTableGenerator::Emit.
413  ///
414  /// \param Base is the point from which all offsets into the structure are
415  /// based. This is offset 0 in the stream that was used when Emitting the
416  /// table.
417  static OnDiskChainedHashTable *Create(const unsigned char *Buckets,
418  const unsigned char *const Base,
419  const Info &InfoObj = Info()) {
420  assert(Buckets > Base);
421  auto NumBucketsAndEntries = readNumBucketsAndEntries(Buckets);
422  return new OnDiskChainedHashTable<Info>(NumBucketsAndEntries.first,
423  NumBucketsAndEntries.second,
424  Buckets, Base, InfoObj);
425  }
426 };
427 
428 /// Provides lookup and iteration over an on disk hash table.
429 ///
430 /// \copydetails llvm::OnDiskChainedHashTable
431 template <typename Info>
433  const unsigned char *Payload;
434 
435 public:
439  typedef typename base_type::data_type data_type;
442 
443 private:
444  /// Iterates over all of the keys in the table.
445  class iterator_base {
446  const unsigned char *Ptr;
447  offset_type NumItemsInBucketLeft;
448  offset_type NumEntriesLeft;
449 
450  public:
451  typedef external_key_type value_type;
452 
453  iterator_base(const unsigned char *const Ptr, offset_type NumEntries)
454  : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries) {}
455  iterator_base()
456  : Ptr(nullptr), NumItemsInBucketLeft(0), NumEntriesLeft(0) {}
457 
458  friend bool operator==(const iterator_base &X, const iterator_base &Y) {
459  return X.NumEntriesLeft == Y.NumEntriesLeft;
460  }
461  friend bool operator!=(const iterator_base &X, const iterator_base &Y) {
462  return X.NumEntriesLeft != Y.NumEntriesLeft;
463  }
464 
465  /// Move to the next item.
466  void advance() {
467  using namespace llvm::support;
468  if (!NumItemsInBucketLeft) {
469  // 'Items' starts with a 16-bit unsigned integer representing the
470  // number of items in this bucket.
471  NumItemsInBucketLeft =
472  endian::readNext<uint16_t, little, unaligned>(Ptr);
473  }
474  Ptr += sizeof(hash_value_type); // Skip the hash.
475  // Determine the length of the key and the data.
476  const std::pair<offset_type, offset_type> &L =
477  Info::ReadKeyDataLength(Ptr);
478  Ptr += L.first + L.second;
479  assert(NumItemsInBucketLeft);
480  --NumItemsInBucketLeft;
481  assert(NumEntriesLeft);
482  --NumEntriesLeft;
483  }
484 
485  /// Get the start of the item as written by the trait (after the hash and
486  /// immediately before the key and value length).
487  const unsigned char *getItem() const {
488  return Ptr + (NumItemsInBucketLeft ? 0 : 2) + sizeof(hash_value_type);
489  }
490  };
491 
492 public:
493  OnDiskIterableChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
494  const unsigned char *Buckets,
495  const unsigned char *Payload,
496  const unsigned char *Base,
497  const Info &InfoObj = Info())
498  : base_type(NumBuckets, NumEntries, Buckets, Base, InfoObj),
499  Payload(Payload) {}
500 
501  /// Iterates over all of the keys in the table.
502  class key_iterator : public iterator_base {
503  Info *InfoObj;
504 
505  public:
506  typedef external_key_type value_type;
507 
508  key_iterator(const unsigned char *const Ptr, offset_type NumEntries,
509  Info *InfoObj)
510  : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
511  key_iterator() : iterator_base(), InfoObj() {}
512 
514  this->advance();
515  return *this;
516  }
517  key_iterator operator++(int) { // Postincrement
518  key_iterator tmp = *this;
519  ++*this;
520  return tmp;
521  }
522 
523  internal_key_type getInternalKey() const {
524  auto *LocalPtr = this->getItem();
525 
526  // Determine the length of the key and the data.
527  auto L = Info::ReadKeyDataLength(LocalPtr);
528 
529  // Read the key.
530  return InfoObj->ReadKey(LocalPtr, L.first);
531  }
532 
533  value_type operator*() const {
534  return InfoObj->GetExternalKey(getInternalKey());
535  }
536  };
537 
539  return key_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
540  }
542 
544  return make_range(key_begin(), key_end());
545  }
546 
547  /// Iterates over all the entries in the table, returning the data.
548  class data_iterator : public iterator_base {
549  Info *InfoObj;
550 
551  public:
552  typedef data_type value_type;
553 
554  data_iterator(const unsigned char *const Ptr, offset_type NumEntries,
555  Info *InfoObj)
556  : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
557  data_iterator() : iterator_base(), InfoObj() {}
558 
559  data_iterator &operator++() { // Preincrement
560  this->advance();
561  return *this;
562  }
563  data_iterator operator++(int) { // Postincrement
564  data_iterator tmp = *this;
565  ++*this;
566  return tmp;
567  }
568 
569  value_type operator*() const {
570  auto *LocalPtr = this->getItem();
571 
572  // Determine the length of the key and the data.
573  auto L = Info::ReadKeyDataLength(LocalPtr);
574 
575  // Read the key.
576  const internal_key_type &Key = InfoObj->ReadKey(LocalPtr, L.first);
577  return InfoObj->ReadData(Key, LocalPtr + L.first, L.second);
578  }
579  };
580 
582  return data_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
583  }
585 
587  return make_range(data_begin(), data_end());
588  }
589 
590  /// Create the hash table.
591  ///
592  /// \param Buckets is the beginning of the hash table itself, which follows
593  /// the payload of entire structure. This is the value returned by
594  /// OnDiskHashTableGenerator::Emit.
595  ///
596  /// \param Payload is the beginning of the data contained in the table. This
597  /// is Base plus any padding or header data that was stored, ie, the offset
598  /// that the stream was at when calling Emit.
599  ///
600  /// \param Base is the point from which all offsets into the structure are
601  /// based. This is offset 0 in the stream that was used when Emitting the
602  /// table.
604  Create(const unsigned char *Buckets, const unsigned char *const Payload,
605  const unsigned char *const Base, const Info &InfoObj = Info()) {
606  assert(Buckets > Base);
607  auto NumBucketsAndEntries =
610  NumBucketsAndEntries.first, NumBucketsAndEntries.second,
611  Buckets, Payload, Base, InfoObj);
612  }
613 };
614 
615 } // end namespace llvm
616 
617 #endif
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
OnDiskChainedHashTable(offset_type NumBuckets, offset_type NumEntries, const unsigned char *Buckets, const unsigned char *Base, const Info &InfoObj=Info())
offset_type getNumEntries() const
This class represents lattice values for constants.
Definition: AllocatorList.h:23
offset_type getNumBuckets() const
OnDiskChainedHashTable< Info > base_type
static std::pair< offset_type, offset_type > readNumBucketsAndEntries(const unsigned char *&Buckets)
Read the number of buckets and the number of entries from a hash table produced by OnDiskHashTableGen...
Info::external_key_type external_key_type
Iterates over all of the keys in the table.
InstrProfLookupTrait::offset_type offset_type
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
bool operator==(const iterator &X) const
Iterates over all the entries in the table, returning the data.
Key
PAL metadata keys.
iterator(const internal_key_type K, const unsigned char *D, offset_type L, Info *InfoObj)
base_type::external_key_type external_key_type
void insert(typename Info::key_type_ref Key, typename Info::data_type_ref Data)
Insert an entry into the table.
OnDiskIterableChainedHashTable(offset_type NumBuckets, offset_type NumEntries, const unsigned char *Buckets, const unsigned char *Payload, const unsigned char *Base, const Info &InfoObj=Info())
Analysis containing CSE Info
Definition: CSEInfo.cpp:20
static OnDiskIterableChainedHashTable * Create(const unsigned char *Buckets, const unsigned char *const Payload, const unsigned char *const Base, const Info &InfoObj=Info())
Create the hash table.
uint64_t offsetToAlignment(uint64_t Value, llvm::Align Align)
Returns the offset to the next integer (mod 2**64) that is greater than or equal to Value and is a mu...
Definition: Alignment.h:145
InstrProfLookupTrait::data_type data_type
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
bool contains(typename Info::key_type_ref Key, Info &InfoObj)
Determine whether an entry has been inserted.
void insert(typename Info::key_type_ref Key, typename Info::data_type_ref Data, Info &InfoObj)
Insert an entry into the table.
T * Allocate(size_t num=1)
Allocate space for an array of objects without constructing them.
Definition: Allocator.h:490
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:644
key_iterator(const unsigned char *const Ptr, offset_type NumEntries, Info *InfoObj)
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:40
iterator_range< data_iterator > data()
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
offset_type Emit(raw_ostream &Out)
Emit the table to Out, which must not be at offset 0.
void write(ArrayRef< value_type > Val)
Definition: EndianStream.h:55
iterator_range< key_iterator > keys()
Provides lookup on an on disk hash table.
const unsigned char * getBase() const
const unsigned char * getDataPtr() const
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
Info::hash_value_type hash_value_type
A range adaptor for a pair of iterators.
Info::internal_key_type internal_key_type
base_type::internal_key_type internal_key_type
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1977
Generates an on disk hash table.
Adapter to write values to a stream in a particular byte order.
Definition: EndianStream.h:51
iterator find(const external_key_type &EKey, Info *InfoPtr=nullptr)
Look up the stored data for a particular key.
const unsigned char * getBuckets() const
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
offset_type Emit(raw_ostream &Out, Info &InfoObj)
Emit the table to Out, which must not be at offset 0.
data_iterator(const unsigned char *const Ptr, offset_type NumEntries, Info *InfoObj)
uint32_t Size
Definition: Profile.cpp:46
bool operator!=(const iterator &X) const
static OnDiskChainedHashTable * Create(const unsigned char *Buckets, const unsigned char *const Base, const Info &InfoObj=Info())
Create the hash table.
iterator find_hashed(const internal_key_type &IKey, hash_value_type KeyHash, Info *InfoPtr=nullptr)
Look up the stored data for a particular key with a known hash.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
uint64_t tell() const
tell - Return the current offset with the file.
Definition: raw_ostream.h:111
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_calloc(size_t Count, size_t Sz)
Definition: MemAlloc.h:38
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1975
base_type::hash_value_type hash_value_type
Provides lookup and iteration over an on disk hash table.