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 ///
  43 ///   /// Calculate the hash for Key
  44 ///   static unsigned ComputeHash(key_type_ref Key);
  45 ///   /// Return the lengths, in bytes, of the given Key/Data pair.
  46 ///   static std::pair<unsigned, unsigned>
  47 ///   EmitKeyDataLength(raw_ostream &Out, key_type_ref Key, data_type_ref Data);
  48 ///   /// Write Key to Out.  KeyLen is the length from EmitKeyDataLength.
  49 ///   static void EmitKey(raw_ostream &Out, key_type_ref Key, unsigned KeyLen);
  50 ///   /// Write Data to Out.  DataLen is the length from EmitKeyDataLength.
  51 ///   static void EmitData(raw_ostream &Out, key_type_ref Key,
  52 ///                        data_type_ref Data, unsigned DataLen);
  53 /// };
  54 /// \endcode
  55 template <typename Info> class OnDiskChainedHashTableGenerator {
  56   unsigned NumBuckets;
  57   unsigned NumEntries;
  58   llvm::BumpPtrAllocator BA;
  59
  60   /// \brief 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 uint32_t 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(0), Hash(InfoObj.ComputeHash(Key)) {}
  71   };
  72
  73   /// \brief A linked list of values in a particular hash bucket.
  74   class Bucket {
  75   public:
  76     uint32_t Off;
  77     Item *Head;
  78     unsigned Length;
  79
  80     Bucket() {}
  81   };
  82
  83   Bucket *Buckets;
  84
  85 private:
  86   /// \brief Insert an item into the appropriate hash bucket.
  87   void insert(Bucket *Buckets, size_t Size, Item *E) {
  88     Bucket &B = Buckets[E->Hash & (Size - 1)];
  89     E->Next = B.Head;
  90     ++B.Length;
  91     B.Head = E;
  92   }
  93
  94   /// \brief Resize the hash table, moving the old entries into the new buckets.
  95   void resize(size_t NewSize) {
  96     Bucket *NewBuckets = (Bucket *)std::calloc(NewSize, sizeof(Bucket));
  97     // Populate NewBuckets with the old entries.
  98     for (unsigned I = 0; I < NumBuckets; ++I)
  99       for (Item *E = Buckets[I].Head; E;) {
 100         Item *N = E->Next;
 101         E->Next = 0;
 102         insert(NewBuckets, NewSize, E);
 103         E = N;
 104       }
 105
 106     free(Buckets);
 107     NumBuckets = NewSize;
 108     Buckets = NewBuckets;
 109   }
 110
 111 public:
 112   /// \brief Insert an entry into the table.
 113   void insert(typename Info::key_type_ref Key,
 114               typename Info::data_type_ref Data) {
 115     Info InfoObj;
 116     insert(Key, Data, InfoObj);
 117   }
 118
 119   /// \brief Insert an entry into the table.
 120   ///
 121   /// Uses the provided Info instead of a stack allocated one.
 122   void insert(typename Info::key_type_ref Key,
 123               typename Info::data_type_ref Data, Info &InfoObj) {
 124
 125     ++NumEntries;
 126     if (4 * NumEntries >= 3 * NumBuckets)
 127       resize(NumBuckets * 2);
 128     insert(Buckets, NumBuckets,
 129            new (BA.Allocate<Item>()) Item(Key, Data, InfoObj));
 130   }
 131
 132   /// \brief Emit the table to Out, which must not be at offset 0.
 133   uint32_t 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   uint32_t 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 (unsigned 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<uint32_t>(I->Hash);
 162         const std::pair<unsigned, unsigned> &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     uint32_t TableOff = Out.tell();
 171     uint64_t N = llvm::OffsetToAlignment(TableOff, alignOf<uint32_t>());
 172     TableOff += N;
 173     while (N--)
 174       LE.write<uint8_t>(0);
 175
 176     // Emit the hashtable itself.
 177     LE.write<uint32_t>(NumBuckets);
 178     LE.write<uint32_t>(NumEntries);
 179     for (unsigned I = 0; I < NumBuckets; ++I)
 180       LE.write<uint32_t>(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 ///
 209 ///   /// Compare two keys for equality.
 210 ///   static bool EqualKey(internal_key_type &Key1, internal_key_type &Key2);
 211 ///   /// Calculate the hash for the given key.
 212 ///   static unsigned ComputeHash(internal_key_type &IKey);
 213 ///   /// Translate from the semantic type of a key in the hash table to the
 214 ///   /// type that is actually stored and used for hashing and comparisons.
 215 ///   /// The internal and external types are often the same, in which case this
 216 ///   /// can simply return the passed in value.
 217 ///   static const internal_key_type &GetInternalKey(external_key_type &EKey);
 218 ///   /// Read the key and data length from Buffer, leaving it pointing at the
 219 ///   /// following byte.
 220 ///   static std::pair<unsigned, unsigned>
 221 ///   ReadKeyDataLength(const unsigned char *&Buffer);
 222 ///   /// Read the key from Buffer, given the KeyLen as reported from
 223 ///   /// ReadKeyDataLength.
 224 ///   const internal_key_type &ReadKey(const unsigned char *Buffer,
 225 ///                                    unsigned KeyLen);
 226 ///   /// Read the data for Key from Buffer, given the DataLen as reported from
 227 ///   /// ReadKeyDataLength.
 228 ///   data_type ReadData(StringRef Key, const unsigned char *Buffer,
 229 ///                      unsigned DataLen);
 230 /// };
 231 /// \endcode
 232 template <typename Info> class OnDiskChainedHashTable {
 233   const unsigned NumBuckets;
 234   const unsigned NumEntries;
 235   const unsigned char *const Buckets;
 236   const unsigned char *const Base;
 237   Info InfoObj;
 238
 239 public:
 240   typedef typename Info::internal_key_type internal_key_type;
 241   typedef typename Info::external_key_type external_key_type;
 242   typedef typename Info::data_type         data_type;
 243
 244   OnDiskChainedHashTable(unsigned NumBuckets, unsigned NumEntries,
 245                          const unsigned char *Buckets,
 246                          const unsigned char *Base,
 247                          const Info &InfoObj = Info())
 248       : NumBuckets(NumBuckets), NumEntries(NumEntries), Buckets(Buckets),
 249         Base(Base), InfoObj(InfoObj) {
 250     assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
 251            "'buckets' must have a 4-byte alignment");
 252   }
 253
 254   unsigned getNumBuckets() const { return NumBuckets; }
 255   unsigned getNumEntries() const { return NumEntries; }
 256   const unsigned char *getBase() const { return Base; }
 257   const unsigned char *getBuckets() const { return Buckets; }
 258
 259   bool isEmpty() const { return NumEntries == 0; }
 260
 261   class iterator {
 262     internal_key_type Key;
 263     const unsigned char *const Data;
 264     const unsigned Len;
 265     Info *InfoObj;
 266
 267   public:
 268     iterator() : Data(0), Len(0) {}
 269     iterator(const internal_key_type K, const unsigned char *D, unsigned L,
 270              Info *InfoObj)
 271         : Key(K), Data(D), Len(L), InfoObj(InfoObj) {}
 272
 273     data_type operator*() const { return InfoObj->ReadData(Key, Data, Len); }
 274     bool operator==(const iterator &X) const { return X.Data == Data; }
 275     bool operator!=(const iterator &X) const { return X.Data != Data; }
 276   };
 277
 278   /// \brief Look up the stored data for a particular key.
 279   iterator find(const external_key_type &EKey, Info *InfoPtr = 0) {
 280     if (!InfoPtr)
 281       InfoPtr = &InfoObj;
 282
 283     using namespace llvm::support;
 284     const internal_key_type &IKey = InfoObj.GetInternalKey(EKey);
 285     unsigned KeyHash = InfoObj.ComputeHash(IKey);
 286
 287     // Each bucket is just a 32-bit offset into the hash table file.
 288     unsigned Idx = KeyHash & (NumBuckets - 1);
 289     const unsigned char *Bucket = Buckets + sizeof(uint32_t) * Idx;
 290
 291     unsigned Offset = endian::readNext<uint32_t, little, aligned>(Bucket);
 292     if (Offset == 0)
 293       return iterator(); // Empty bucket.
 294     const unsigned char *Items = Base + Offset;
 295
 296     // 'Items' starts with a 16-bit unsigned integer representing the
 297     // number of items in this bucket.
 298     unsigned Len = endian::readNext<uint16_t, little, unaligned>(Items);
 299
 300     for (unsigned i = 0; i < Len; ++i) {
 301       // Read the hash.
 302       uint32_t ItemHash = endian::readNext<uint32_t, little, unaligned>(Items);
 303
 304       // Determine the length of the key and the data.
 305       const std::pair<unsigned, unsigned> &L = Info::ReadKeyDataLength(Items);
 306       unsigned ItemLen = L.first + L.second;
 307
 308       // Compare the hashes.  If they are not the same, skip the entry entirely.
 309       if (ItemHash != KeyHash) {
 310         Items += ItemLen;
 311         continue;
 312       }
 313
 314       // Read the key.
 315       const internal_key_type &X =
 316           InfoPtr->ReadKey((const unsigned char *const)Items, L.first);
 317
 318       // If the key doesn't match just skip reading the value.
 319       if (!InfoPtr->EqualKey(X, IKey)) {
 320         Items += ItemLen;
 321         continue;
 322       }
 323
 324       // The key matches!
 325       return iterator(X, Items + L.first, L.second, InfoPtr);
 326     }
 327
 328     return iterator();
 329   }
 330
 331   iterator end() const { return iterator(); }
 332
 333   Info &getInfoObj() { return InfoObj; }
 334
 335   /// \brief Create the hash table.
 336   ///
 337   /// \param Buckets is the beginning of the hash table itself, which follows
 338   /// the payload of entire structure. This is the value returned by
 339   /// OnDiskHashTableGenerator::Emit.
 340   ///
 341   /// \param Base is the point from which all offsets into the structure are
 342   /// based. This is offset 0 in the stream that was used when Emitting the
 343   /// table.
 344   static OnDiskChainedHashTable *Create(const unsigned char *Buckets,
 345                                         const unsigned char *const Base,
 346                                         const Info &InfoObj = Info()) {
 347     using namespace llvm::support;
 348     assert(Buckets > Base);
 349     assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
 350            "buckets should be 4-byte aligned.");
 351
 352     unsigned NumBuckets = endian::readNext<uint32_t, little, aligned>(Buckets);
 353     unsigned NumEntries = endian::readNext<uint32_t, little, aligned>(Buckets);
 354     return new OnDiskChainedHashTable<Info>(NumBuckets, NumEntries, Buckets,
 355                                             Base, InfoObj);
 356   }
 357 };
 358
 359 /// \brief Provides lookup and iteration over an on disk hash table.
 360 ///
 361 /// \copydetails llvm::OnDiskChainedHashTable
 362 template <typename Info>
 363 class OnDiskIterableChainedHashTable : public OnDiskChainedHashTable<Info> {
 364   const unsigned char *Payload;
 365
 366 public:
 367   typedef OnDiskChainedHashTable<Info>          base_type;
 368   typedef typename base_type::internal_key_type internal_key_type;
 369   typedef typename base_type::external_key_type external_key_type;
 370   typedef typename base_type::data_type         data_type;
 371
 372   OnDiskIterableChainedHashTable(unsigned NumBuckets, unsigned NumEntries,
 373                                  const unsigned char *Buckets,
 374                                  const unsigned char *Payload,
 375                                  const unsigned char *Base,
 376                                  const Info &InfoObj = Info())
 377       : base_type(NumBuckets, NumEntries, Buckets, Base, InfoObj),
 378         Payload(Payload) {}
 379
 380   /// \brief Iterates over all of the keys in the table.
 381   class key_iterator {
 382     const unsigned char *Ptr;
 383     unsigned NumItemsInBucketLeft;
 384     unsigned NumEntriesLeft;
 385     Info *InfoObj;
 386
 387   public:
 388     typedef external_key_type value_type;
 389
 390     key_iterator(const unsigned char *const Ptr, unsigned NumEntries,
 391                  Info *InfoObj)
 392         : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries),
 393           InfoObj(InfoObj) {}
 394     key_iterator()
 395         : Ptr(0), NumItemsInBucketLeft(0), NumEntriesLeft(0), InfoObj(0) {}
 396
 397     friend bool operator==(const key_iterator &X, const key_iterator &Y) {
 398       return X.NumEntriesLeft == Y.NumEntriesLeft;
 399     }
 400     friend bool operator!=(const key_iterator &X, const key_iterator &Y) {
 401       return X.NumEntriesLeft != Y.NumEntriesLeft;
 402     }
 403
 404     key_iterator &operator++() { // Preincrement
 405       using namespace llvm::support;
 406       if (!NumItemsInBucketLeft) {
 407         // 'Items' starts with a 16-bit unsigned integer representing the
 408         // number of items in this bucket.
 409         NumItemsInBucketLeft =
 410             endian::readNext<uint16_t, little, unaligned>(Ptr);
 411       }
 412       Ptr += 4; // Skip the hash.
 413       // Determine the length of the key and the data.
 414       const std::pair<unsigned, unsigned> &L = Info::ReadKeyDataLength(Ptr);
 415       Ptr += L.first + L.second;
 416       assert(NumItemsInBucketLeft);
 417       --NumItemsInBucketLeft;
 418       assert(NumEntriesLeft);
 419       --NumEntriesLeft;
 420       return *this;
 421     }
 422     key_iterator operator++(int) { // Postincrement
 423       key_iterator tmp = *this; ++*this; return tmp;
 424     }
 425
 426     value_type operator*() const {
 427       const unsigned char *LocalPtr = Ptr;
 428       if (!NumItemsInBucketLeft)
 429         LocalPtr += 2; // number of items in bucket
 430       LocalPtr += 4;   // Skip the hash.
 431
 432       // Determine the length of the key and the data.
 433       const std::pair<unsigned, unsigned> &L =
 434           Info::ReadKeyDataLength(LocalPtr);
 435
 436       // Read the key.
 437       const internal_key_type &Key = InfoObj->ReadKey(LocalPtr, L.first);
 438       return InfoObj->GetExternalKey(Key);
 439     }
 440   };
 441
 442   key_iterator key_begin() {
 443     return key_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
 444   }
 445   key_iterator key_end() { return key_iterator(); }
 446
 447   /// \brief Iterates over all the entries in the table, returning the data.
 448   class data_iterator {
 449     const unsigned char *Ptr;
 450     unsigned NumItemsInBucketLeft;
 451     unsigned NumEntriesLeft;
 452     Info *InfoObj;
 453
 454   public:
 455     typedef data_type value_type;
 456
 457     data_iterator(const unsigned char *const Ptr, unsigned NumEntries,
 458                   Info *InfoObj)
 459         : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries),
 460           InfoObj(InfoObj) {}
 461     data_iterator()
 462         : Ptr(0), NumItemsInBucketLeft(0), NumEntriesLeft(0), InfoObj(0) {}
 463
 464     bool operator==(const data_iterator &X) const {
 465       return X.NumEntriesLeft == NumEntriesLeft;
 466     }
 467     bool operator!=(const data_iterator &X) const {
 468       return X.NumEntriesLeft != NumEntriesLeft;
 469     }
 470
 471     data_iterator &operator++() { // Preincrement
 472       using namespace llvm::support;
 473       if (!NumItemsInBucketLeft) {
 474         // 'Items' starts with a 16-bit unsigned integer representing the
 475         // number of items in this bucket.
 476         NumItemsInBucketLeft =
 477             endian::readNext<uint16_t, little, unaligned>(Ptr);
 478       }
 479       Ptr += 4; // Skip the hash.
 480       // Determine the length of the key and the data.
 481       const std::pair<unsigned, unsigned> &L = Info::ReadKeyDataLength(Ptr);
 482       Ptr += L.first + L.second;
 483       assert(NumItemsInBucketLeft);
 484       --NumItemsInBucketLeft;
 485       assert(NumEntriesLeft);
 486       --NumEntriesLeft;
 487       return *this;
 488     }
 489     data_iterator operator++(int) { // Postincrement
 490       data_iterator tmp = *this; ++*this; return tmp;
 491     }
 492
 493     value_type operator*() const {
 494       const unsigned char *LocalPtr = Ptr;
 495       if (!NumItemsInBucketLeft)
 496         LocalPtr += 2; // number of items in bucket
 497       LocalPtr += 4;   // Skip the hash.
 498
 499       // Determine the length of the key and the data.
 500       const std::pair<unsigned, unsigned> &L =
 501           Info::ReadKeyDataLength(LocalPtr);
 502
 503       // Read the key.
 504       const internal_key_type &Key = InfoObj->ReadKey(LocalPtr, L.first);
 505       return InfoObj->ReadData(Key, LocalPtr + L.first, L.second);
 506     }
 507   };
 508
 509   data_iterator data_begin() {
 510     return data_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
 511   }
 512   data_iterator data_end() { return data_iterator(); }
 513
 514   /// \brief Create the hash table.
 515   ///
 516   /// \param Buckets is the beginning of the hash table itself, which follows
 517   /// the payload of entire structure. This is the value returned by
 518   /// OnDiskHashTableGenerator::Emit.
 519   ///
 520   /// \param Payload is the beginning of the data contained in the table.  This
 521   /// is Base plus any padding or header data that was stored, ie, the offset
 522   /// that the stream was at when calling Emit.
 523   ///
 524   /// \param Base is the point from which all offsets into the structure are
 525   /// based. This is offset 0 in the stream that was used when Emitting the
 526   /// table.
 527   static OnDiskIterableChainedHashTable *
 528   Create(const unsigned char *Buckets, const unsigned char *const Payload,
 529          const unsigned char *const Base, const Info &InfoObj = Info()) {
 530     using namespace llvm::support;
 531     assert(Buckets > Base);
 532     assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
 533            "buckets should be 4-byte aligned.");
 534
 535     unsigned NumBuckets = endian::readNext<uint32_t, little, aligned>(Buckets);
 536     unsigned NumEntries = endian::readNext<uint32_t, little, aligned>(Buckets);
 537     return new OnDiskIterableChainedHashTable<Info>(
 538         NumBuckets, NumEntries, Buckets, Payload, Base, InfoObj);
 539   }
 540 };
 541
 542 } // end namespace llvm
 543
 544 #endif // LLVM_SUPPORT_ON_DISK_HASH_TABLE_H