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