include/llvm/Support/OnDiskHashTable.h

   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 /// };
  57 /// \endcode
  58 template <typename Info> class OnDiskChainedHashTableGenerator {
  59   /// \brief A single item in the hash table.
  60   class Item {
  61   public:
  62     typename Info::key_type Key;
  63     typename Info::data_type Data;
  64     Item *Next;
  65     const typename Info::hash_value_type Hash;
  66
  67     Item(typename Info::key_type_ref Key, typename Info::data_type_ref Data,
  68          Info &InfoObj)
  69         : Key(Key), Data(Data), Next(nullptr), Hash(InfoObj.ComputeHash(Key)) {}
  70   };
  71
  72   typedef typename Info::offset_type offset_type;
  73   offset_type NumBuckets;
  74   offset_type NumEntries;
  75   llvm::SpecificBumpPtrAllocator<Item> BA;
  76
  77   /// \brief A linked list of values in a particular hash bucket.
  78   struct Bucket {
  79     offset_type Off;
  80     unsigned Length;
  81     Item *Head;
  82   };
  83
  84   Bucket *Buckets;
  85
  86 private:
  87   /// \brief Insert an item into the appropriate hash bucket.
  88   void insert(Bucket *Buckets, size_t Size, Item *E) {
  89     Bucket &B = Buckets[E->Hash & (Size - 1)];
  90     E->Next = B.Head;
  91     ++B.Length;
  92     B.Head = E;
  93   }
  94
  95   /// \brief Resize the hash table, moving the old entries into the new buckets.
  96   void resize(size_t NewSize) {
  97     Bucket *NewBuckets = (Bucket *)std::calloc(NewSize, sizeof(Bucket));
  98     // Populate NewBuckets with the old entries.
  99     for (size_t I = 0; I < NumBuckets; ++I)
 100       for (Item *E = Buckets[I].Head; E;) {
 101         Item *N = E->Next;
 102         E->Next = nullptr;
 103         insert(NewBuckets, NewSize, E);
 104         E = N;
 105       }
 106
 107     free(Buckets);
 108     NumBuckets = NewSize;
 109     Buckets = NewBuckets;
 110   }
 111
 112 public:
 113   /// \brief Insert an entry into the table.
 114   void insert(typename Info::key_type_ref Key,
 115               typename Info::data_type_ref Data) {
 116     Info InfoObj;
 117     insert(Key, Data, InfoObj);
 118   }
 119
 120   /// \brief Insert an entry into the table.
 121   ///
 122   /// Uses the provided Info instead of a stack allocated one.
 123   void insert(typename Info::key_type_ref Key,
 124               typename Info::data_type_ref Data, Info &InfoObj) {
 125
 126     ++NumEntries;
 127     if (4 * NumEntries >= 3 * NumBuckets)
 128       resize(NumBuckets * 2);
 129     insert(Buckets, NumBuckets, new (BA.Allocate()) Item(Key, Data, InfoObj));
 130   }
 131
 132   /// \brief Emit the table to Out, which must not be at offset 0.
 133   offset_type Emit(raw_ostream &Out) {
 134     Info InfoObj;
 135     return Emit(Out, InfoObj);
 136   }
 137
 138   /// \brief Emit the table to Out, which must not be at offset 0.
 139   ///
 140   /// Uses the provided Info instead of a stack allocated one.
 141   offset_type Emit(raw_ostream &Out, Info &InfoObj) {
 142     using namespace llvm::support;
 143     endian::Writer<little> LE(Out);
 144
 145     // Emit the payload of the table.
 146     for (offset_type I = 0; I < NumBuckets; ++I) {
 147       Bucket &B = Buckets[I];
 148       if (!B.Head)
 149         continue;
 150
 151       // Store the offset for the data of this bucket.
 152       B.Off = Out.tell();
 153       assert(B.Off && "Cannot write a bucket at offset 0. Please add padding.");
 154
 155       // Write out the number of items in the bucket.
 156       LE.write<uint16_t>(B.Length);
 157       assert(B.Length != 0 && "Bucket has a head but zero length?");
 158
 159       // Write out the entries in the bucket.
 160       for (Item *I = B.Head; I; I = I->Next) {
 161         LE.write<typename Info::hash_value_type>(I->Hash);
 162         const std::pair<offset_type, offset_type> &Len =
 163             InfoObj.EmitKeyDataLength(Out, I->Key, I->Data);
 164         InfoObj.EmitKey(Out, I->Key, Len.first);
 165         InfoObj.EmitData(Out, I->Key, I->Data, Len.second);
 166       }
 167     }
 168
 169     // Pad with zeros so that we can start the hashtable at an aligned address.
 170     offset_type TableOff = Out.tell();
 171     uint64_t N = llvm::OffsetToAlignment(TableOff, alignOf<offset_type>());
 172     TableOff += N;
 173     while (N--)
 174       LE.write<uint8_t>(0);
 175
 176     // Emit the hashtable itself.
 177     LE.write<offset_type>(NumBuckets);
 178     LE.write<offset_type>(NumEntries);
 179     for (offset_type I = 0; I < NumBuckets; ++I)
 180       LE.write<offset_type>(Buckets[I].Off);
 181
 182     return TableOff;
 183   }
 184
 185   OnDiskChainedHashTableGenerator() {
 186     NumEntries = 0;
 187     NumBuckets = 64;
 188     // Note that we do not need to run the constructors of the individual
 189     // Bucket objects since 'calloc' returns bytes that are all 0.
 190     Buckets = (Bucket *)std::calloc(NumBuckets, sizeof(Bucket));
 191   }
 192
 193   ~OnDiskChainedHashTableGenerator() { std::free(Buckets); }
 194 };
 195
 196 /// \brief Provides lookup on an on disk hash table.
 197 ///
 198 /// This needs an \c Info that handles reading values from the hash table's
 199 /// payload and computes the hash for a given key. This should provide the
 200 /// following interface:
 201 ///
 202 /// \code
 203 /// class ExampleLookupInfo {
 204 /// public:
 205 ///   typedef ExampleData data_type;
 206 ///   typedef ExampleInternalKey internal_key_type; // The stored key type.
 207 ///   typedef ExampleKey external_key_type; // The type to pass to find().
 208 ///   typedef uint32_t hash_value_type; // The type the hash function returns.
 209 ///   typedef uint32_t offset_type; // The type for offsets into the table.
 210 ///
 211 ///   /// Compare two keys for equality.
 212 ///   static bool EqualKey(internal_key_type &Key1, internal_key_type &Key2);
 213 ///   /// Calculate the hash for the given key.
 214 ///   static hash_value_type ComputeHash(internal_key_type &IKey);
 215 ///   /// Translate from the semantic type of a key in the hash table to the
 216 ///   /// type that is actually stored and used for hashing and comparisons.
 217 ///   /// The internal and external types are often the same, in which case this
 218 ///   /// can simply return the passed in value.
 219 ///   static const internal_key_type &GetInternalKey(external_key_type &EKey);
 220 ///   /// Read the key and data length from Buffer, leaving it pointing at the
 221 ///   /// following byte.
 222 ///   static std::pair<offset_type, offset_type>
 223 ///   ReadKeyDataLength(const unsigned char *&Buffer);
 224 ///   /// Read the key from Buffer, given the KeyLen as reported from
 225 ///   /// ReadKeyDataLength.
 226 ///   const internal_key_type &ReadKey(const unsigned char *Buffer,
 227 ///                                    offset_type KeyLen);
 228 ///   /// Read the data for Key from Buffer, given the DataLen as reported from
 229 ///   /// ReadKeyDataLength.
 230 ///   data_type ReadData(StringRef Key, const unsigned char *Buffer,
 231 ///                      offset_type DataLen);
 232 /// };
 233 /// \endcode
 234 template <typename Info> class OnDiskChainedHashTable {
 235   const typename Info::offset_type NumBuckets;
 236   const typename Info::offset_type NumEntries;
 237   const unsigned char *const Buckets;
 238   const unsigned char *const Base;
 239   Info InfoObj;
 240
 241 public:
 242   typedef typename Info::internal_key_type internal_key_type;
 243   typedef typename Info::external_key_type external_key_type;
 244   typedef typename Info::data_type         data_type;
 245   typedef typename Info::hash_value_type   hash_value_type;
 246   typedef typename Info::offset_type       offset_type;
 247
 248   OnDiskChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
 249                          const unsigned char *Buckets,
 250                          const unsigned char *Base,
 251                          const Info &InfoObj = Info())
 252       : NumBuckets(NumBuckets), NumEntries(NumEntries), Buckets(Buckets),
 253         Base(Base), InfoObj(InfoObj) {
 254     assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
 255            "'buckets' must have a 4-byte alignment");
 256   }
 257
 258   /// Read the number of buckets and the number of entries from a hash table
 259   /// produced by OnDiskHashTableGenerator::Emit, and advance the Buckets
 260   /// pointer past them.
 261   static std::pair<offset_type, offset_type>
 262   readNumBucketsAndEntries(const unsigned char *&Buckets) {
 263     assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
 264            "buckets should be 4-byte aligned.");
 265     using namespace llvm::support;
 266     offset_type NumBuckets =
 267         endian::readNext<offset_type, little, aligned>(Buckets);
 268     offset_type NumEntries =
 269         endian::readNext<offset_type, little, aligned>(Buckets);
 270     return std::make_pair(NumBuckets, NumEntries);
 271   }
 272
 273   offset_type getNumBuckets() const { return NumBuckets; }
 274   offset_type getNumEntries() const { return NumEntries; }
 275   const unsigned char *getBase() const { return Base; }
 276   const unsigned char *getBuckets() const { return Buckets; }
 277
 278   bool isEmpty() const { return NumEntries == 0; }
 279
 280   class iterator {
 281     internal_key_type Key;
 282     const unsigned char *const Data;
 283     const offset_type Len;
 284     Info *InfoObj;
 285
 286   public:
 287     iterator() : Data(nullptr), Len(0) {}
 288     iterator(const internal_key_type K, const unsigned char *D, offset_type L,
 289              Info *InfoObj)
 290         : Key(K), Data(D), Len(L), InfoObj(InfoObj) {}
 291
 292     data_type operator*() const { return InfoObj->ReadData(Key, Data, Len); }
 293     bool operator==(const iterator &X) const { return X.Data == Data; }
 294     bool operator!=(const iterator &X) const { return X.Data != Data; }
 295   };
 296
 297   /// \brief Look up the stored data for a particular key.
 298   iterator find(const external_key_type &EKey, Info *InfoPtr = nullptr) {
 299     const internal_key_type &IKey = InfoObj.GetInternalKey(EKey);
 300     hash_value_type KeyHash = InfoObj.ComputeHash(IKey);
 301     return find_hashed(IKey, KeyHash, InfoPtr);
 302   }
 303
 304   /// \brief Look up the stored data for a particular key with a known hash.
 305   iterator find_hashed(const internal_key_type &IKey, hash_value_type KeyHash,
 306                        Info *InfoPtr = nullptr) {
 307     using namespace llvm::support;
 308
 309     if (!InfoPtr)
 310       InfoPtr = &InfoObj;
 311
 312     // Each bucket is just an offset into the hash table file.
 313     offset_type Idx = KeyHash & (NumBuckets - 1);
 314     const unsigned char *Bucket = Buckets + sizeof(offset_type) * Idx;
 315
 316     offset_type Offset = endian::readNext<offset_type, little, aligned>(Bucket);
 317     if (Offset == 0)
 318       return iterator(); // Empty bucket.
 319     const unsigned char *Items = Base + Offset;
 320
 321     // 'Items' starts with a 16-bit unsigned integer representing the
 322     // number of items in this bucket.
 323     unsigned Len = endian::readNext<uint16_t, little, unaligned>(Items);
 324
 325     for (unsigned i = 0; i < Len; ++i) {
 326       // Read the hash.
 327       hash_value_type ItemHash =
 328           endian::readNext<hash_value_type, little, unaligned>(Items);
 329
 330       // Determine the length of the key and the data.
 331       const std::pair<offset_type, offset_type> &L =
 332           Info::ReadKeyDataLength(Items);
 333       offset_type ItemLen = L.first + L.second;
 334
 335       // Compare the hashes.  If they are not the same, skip the entry entirely.
 336       if (ItemHash != KeyHash) {
 337         Items += ItemLen;
 338         continue;
 339       }
 340
 341       // Read the key.
 342       const internal_key_type &X =
 343           InfoPtr->ReadKey((const unsigned char *const)Items, L.first);
 344
 345       // If the key doesn't match just skip reading the value.
 346       if (!InfoPtr->EqualKey(X, IKey)) {
 347         Items += ItemLen;
 348         continue;
 349       }
 350
 351       // The key matches!
 352       return iterator(X, Items + L.first, L.second, InfoPtr);
 353     }
 354
 355     return iterator();
 356   }
 357
 358   iterator end() const { return iterator(); }
 359
 360   Info &getInfoObj() { return InfoObj; }
 361
 362   /// \brief Create the hash table.
 363   ///
 364   /// \param Buckets is the beginning of the hash table itself, which follows
 365   /// the payload of entire structure. This is the value returned by
 366   /// OnDiskHashTableGenerator::Emit.
 367   ///
 368   /// \param Base is the point from which all offsets into the structure are
 369   /// based. This is offset 0 in the stream that was used when Emitting the
 370   /// table.
 371   static OnDiskChainedHashTable *Create(const unsigned char *Buckets,
 372                                         const unsigned char *const Base,
 373                                         const Info &InfoObj = Info()) {
 374     assert(Buckets > Base);
 375     auto NumBucketsAndEntries = readNumBucketsAndEntries(Buckets);
 376     return new OnDiskChainedHashTable<Info>(NumBucketsAndEntries.first,
 377                                             NumBucketsAndEntries.second,
 378                                             Buckets, Base, InfoObj);
 379   }
 380 };
 381
 382 /// \brief Provides lookup and iteration over an on disk hash table.
 383 ///
 384 /// \copydetails llvm::OnDiskChainedHashTable
 385 template <typename Info>
 386 class OnDiskIterableChainedHashTable : public OnDiskChainedHashTable<Info> {
 387   const unsigned char *Payload;
 388
 389 public:
 390   typedef OnDiskChainedHashTable<Info>          base_type;
 391   typedef typename base_type::internal_key_type internal_key_type;
 392   typedef typename base_type::external_key_type external_key_type;
 393   typedef typename base_type::data_type         data_type;
 394   typedef typename base_type::hash_value_type   hash_value_type;
 395   typedef typename base_type::offset_type       offset_type;
 396
 397 private:
 398   /// \brief Iterates over all of the keys in the table.
 399   class iterator_base {
 400     const unsigned char *Ptr;
 401     offset_type NumItemsInBucketLeft;
 402     offset_type NumEntriesLeft;
 403
 404   public:
 405     typedef external_key_type value_type;
 406
 407     iterator_base(const unsigned char *const Ptr, offset_type NumEntries)
 408         : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries) {}
 409     iterator_base()
 410         : Ptr(nullptr), NumItemsInBucketLeft(0), NumEntriesLeft(0) {}
 411
 412     friend bool operator==(const iterator_base &X, const iterator_base &Y) {
 413       return X.NumEntriesLeft == Y.NumEntriesLeft;
 414     }
 415     friend bool operator!=(const iterator_base &X, const iterator_base &Y) {
 416       return X.NumEntriesLeft != Y.NumEntriesLeft;
 417     }
 418
 419     /// Move to the next item.
 420     void advance() {
 421       using namespace llvm::support;
 422       if (!NumItemsInBucketLeft) {
 423         // 'Items' starts with a 16-bit unsigned integer representing the
 424         // number of items in this bucket.
 425         NumItemsInBucketLeft =
 426             endian::readNext<uint16_t, little, unaligned>(Ptr);
 427       }
 428       Ptr += sizeof(hash_value_type); // Skip the hash.
 429       // Determine the length of the key and the data.
 430       const std::pair<offset_type, offset_type> &L =
 431           Info::ReadKeyDataLength(Ptr);
 432       Ptr += L.first + L.second;
 433       assert(NumItemsInBucketLeft);
 434       --NumItemsInBucketLeft;
 435       assert(NumEntriesLeft);
 436       --NumEntriesLeft;
 437     }
 438
 439     /// Get the start of the item as written by the trait (after the hash and
 440     /// immediately before the key and value length).
 441     const unsigned char *getItem() const {
 442       return Ptr + (NumItemsInBucketLeft ? 0 : 2) + sizeof(hash_value_type);
 443     }
 444   };
 445
 446 public:
 447   OnDiskIterableChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
 448                                  const unsigned char *Buckets,
 449                                  const unsigned char *Payload,
 450                                  const unsigned char *Base,
 451                                  const Info &InfoObj = Info())
 452       : base_type(NumBuckets, NumEntries, Buckets, Base, InfoObj),
 453         Payload(Payload) {}
 454
 455   /// \brief Iterates over all of the keys in the table.
 456   class key_iterator : public iterator_base {
 457     Info *InfoObj;
 458
 459   public:
 460     typedef external_key_type value_type;
 461
 462     key_iterator(const unsigned char *const Ptr, offset_type NumEntries,
 463                  Info *InfoObj)
 464         : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
 465     key_iterator() : iterator_base(), InfoObj() {}
 466
 467     key_iterator &operator++() {
 468       this->advance();
 469       return *this;
 470     }
 471     key_iterator operator++(int) { // Postincrement
 472       key_iterator tmp = *this;
 473       ++*this;
 474       return tmp;
 475     }
 476
 477     internal_key_type getInternalKey() const {
 478       auto *LocalPtr = this->getItem();
 479
 480       // Determine the length of the key and the data.
 481       auto L = Info::ReadKeyDataLength(LocalPtr);
 482
 483       // Read the key.
 484       return InfoObj->ReadKey(LocalPtr, L.first);
 485     }
 486
 487     value_type operator*() const {
 488       return InfoObj->GetExternalKey(getInternalKey());
 489     }
 490   };
 491
 492   key_iterator key_begin() {
 493     return key_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
 494   }
 495   key_iterator key_end() { return key_iterator(); }
 496
 497   iterator_range<key_iterator> keys() {
 498     return make_range(key_begin(), key_end());
 499   }
 500
 501   /// \brief Iterates over all the entries in the table, returning the data.
 502   class data_iterator : public iterator_base {
 503     Info *InfoObj;
 504
 505   public:
 506     typedef data_type value_type;
 507
 508     data_iterator(const unsigned char *const Ptr, offset_type NumEntries,
 509                   Info *InfoObj)
 510         : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
 511     data_iterator() : iterator_base(), InfoObj() {}
 512
 513     data_iterator &operator++() { // Preincrement
 514       this->advance();
 515       return *this;
 516     }
 517     data_iterator operator++(int) { // Postincrement
 518       data_iterator tmp = *this;
 519       ++*this;
 520       return tmp;
 521     }
 522
 523     value_type operator*() 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       const internal_key_type &Key = InfoObj->ReadKey(LocalPtr, L.first);
 531       return InfoObj->ReadData(Key, LocalPtr + L.first, L.second);
 532     }
 533   };
 534
 535   data_iterator data_begin() {
 536     return data_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
 537   }
 538   data_iterator data_end() { return data_iterator(); }
 539
 540   iterator_range<data_iterator> data() {
 541     return make_range(data_begin(), data_end());
 542   }
 543
 544   /// \brief Create the hash table.
 545   ///
 546   /// \param Buckets is the beginning of the hash table itself, which follows
 547   /// the payload of entire structure. This is the value returned by
 548   /// OnDiskHashTableGenerator::Emit.
 549   ///
 550   /// \param Payload is the beginning of the data contained in the table.  This
 551   /// is Base plus any padding or header data that was stored, ie, the offset
 552   /// that the stream was at when calling Emit.
 553   ///
 554   /// \param Base is the point from which all offsets into the structure are
 555   /// based. This is offset 0 in the stream that was used when Emitting the
 556   /// table.
 557   static OnDiskIterableChainedHashTable *
 558   Create(const unsigned char *Buckets, const unsigned char *const Payload,
 559          const unsigned char *const Base, const Info &InfoObj = Info()) {
 560     assert(Buckets > Base);
 561     auto NumBucketsAndEntries =
 562         OnDiskIterableChainedHashTable<Info>::readNumBucketsAndEntries(Buckets);
 563     return new OnDiskIterableChainedHashTable<Info>(
 564         NumBucketsAndEntries.first, NumBucketsAndEntries.second,
 565         Buckets, Payload, Base, InfoObj);
 566   }
 567 };
 568
 569 } // end namespace llvm
 570
 571 #endif