contrib/llvm/tools/clang/include/clang/Basic/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_CLANG_BASIC_ON_DISK_HASH_TABLE_H
  15 #define LLVM_CLANG_BASIC_ON_DISK_HASH_TABLE_H
  16
  17 #include "llvm/Support/Allocator.h"
  18 #include "llvm/Support/DataTypes.h"
  19 #include "llvm/Support/MathExtras.h"
  20 #include "llvm/Support/raw_ostream.h"
  21 #include "llvm/Support/Host.h"
  22 #include <cassert>
  23 #include <cstdlib>
  24
  25 namespace clang {
  26
  27 namespace io {
  28
  29 typedef uint32_t Offset;
  30
  31 inline void Emit8(raw_ostream& Out, uint32_t V) {
  32   Out << (unsigned char)(V);
  33 }
  34
  35 inline void Emit16(raw_ostream& Out, uint32_t V) {
  36   Out << (unsigned char)(V);
  37   Out << (unsigned char)(V >>  8);
  38   assert((V >> 16) == 0);
  39 }
  40
  41 inline void Emit24(raw_ostream& Out, uint32_t V) {
  42   Out << (unsigned char)(V);
  43   Out << (unsigned char)(V >>  8);
  44   Out << (unsigned char)(V >> 16);
  45   assert((V >> 24) == 0);
  46 }
  47
  48 inline void Emit32(raw_ostream& Out, uint32_t V) {
  49   Out << (unsigned char)(V);
  50   Out << (unsigned char)(V >>  8);
  51   Out << (unsigned char)(V >> 16);
  52   Out << (unsigned char)(V >> 24);
  53 }
  54
  55 inline void Emit64(raw_ostream& Out, uint64_t V) {
  56   Out << (unsigned char)(V);
  57   Out << (unsigned char)(V >>  8);
  58   Out << (unsigned char)(V >> 16);
  59   Out << (unsigned char)(V >> 24);
  60   Out << (unsigned char)(V >> 32);
  61   Out << (unsigned char)(V >> 40);
  62   Out << (unsigned char)(V >> 48);
  63   Out << (unsigned char)(V >> 56);
  64 }
  65
  66 inline void Pad(raw_ostream& Out, unsigned A) {
  67   Offset off = (Offset) Out.tell();
  68   for (uint32_t n = llvm::OffsetToAlignment(off, A); n; --n)
  69     Emit8(Out, 0);
  70 }
  71
  72 inline uint16_t ReadUnalignedLE16(const unsigned char *&Data) {
  73   uint16_t V = ((uint16_t)Data[0]) |
  74                ((uint16_t)Data[1] <<  8);
  75   Data += 2;
  76   return V;
  77 }
  78
  79 inline uint32_t ReadUnalignedLE32(const unsigned char *&Data) {
  80   uint32_t V = ((uint32_t)Data[0])  |
  81                ((uint32_t)Data[1] << 8)  |
  82                ((uint32_t)Data[2] << 16) |
  83                ((uint32_t)Data[3] << 24);
  84   Data += 4;
  85   return V;
  86 }
  87
  88 inline uint64_t ReadUnalignedLE64(const unsigned char *&Data) {
  89   uint64_t V = ((uint64_t)Data[0])  |
  90     ((uint64_t)Data[1] << 8)  |
  91     ((uint64_t)Data[2] << 16) |
  92     ((uint64_t)Data[3] << 24) |
  93     ((uint64_t)Data[4] << 32) |
  94     ((uint64_t)Data[5] << 40) |
  95     ((uint64_t)Data[6] << 48) |
  96     ((uint64_t)Data[7] << 56);
  97   Data += 8;
  98   return V;
  99 }
 100
 101 inline uint32_t ReadLE32(const unsigned char *&Data) {
 102   // Hosts that directly support little-endian 32-bit loads can just
 103   // use them.  Big-endian hosts need a bswap.
 104   uint32_t V = *((const uint32_t*)Data);
 105   if (llvm::sys::isBigEndianHost())
 106     V = llvm::ByteSwap_32(V);
 107   Data += 4;
 108   return V;
 109 }
 110
 111 } // end namespace io
 112
 113 template<typename Info>
 114 class OnDiskChainedHashTableGenerator {
 115   unsigned NumBuckets;
 116   unsigned NumEntries;
 117   llvm::BumpPtrAllocator BA;
 118
 119   class Item {
 120   public:
 121     typename Info::key_type key;
 122     typename Info::data_type data;
 123     Item *next;
 124     const uint32_t hash;
 125
 126     Item(typename Info::key_type_ref k, typename Info::data_type_ref d,
 127          Info &InfoObj)
 128     : key(k), data(d), next(0), hash(InfoObj.ComputeHash(k)) {}
 129   };
 130
 131   class Bucket {
 132   public:
 133     io::Offset off;
 134     Item* head;
 135     unsigned length;
 136
 137     Bucket() {}
 138   };
 139
 140   Bucket* Buckets;
 141
 142 private:
 143   void insert(Bucket* b, size_t size, Item* E) {
 144     unsigned idx = E->hash & (size - 1);
 145     Bucket& B = b[idx];
 146     E->next = B.head;
 147     ++B.length;
 148     B.head = E;
 149   }
 150
 151   void resize(size_t newsize) {
 152     Bucket* newBuckets = (Bucket*) std::calloc(newsize, sizeof(Bucket));
 153     // Populate newBuckets with the old entries.
 154     for (unsigned i = 0; i < NumBuckets; ++i)
 155       for (Item* E = Buckets[i].head; E ; ) {
 156         Item* N = E->next;
 157         E->next = 0;
 158         insert(newBuckets, newsize, E);
 159         E = N;
 160       }
 161
 162     free(Buckets);
 163     NumBuckets = newsize;
 164     Buckets = newBuckets;
 165   }
 166
 167 public:
 168
 169   void insert(typename Info::key_type_ref key,
 170               typename Info::data_type_ref data) {
 171     Info InfoObj;
 172     insert(key, data, InfoObj);
 173   }
 174
 175   void insert(typename Info::key_type_ref key,
 176               typename Info::data_type_ref data, Info &InfoObj) {
 177
 178     ++NumEntries;
 179     if (4*NumEntries >= 3*NumBuckets) resize(NumBuckets*2);
 180     insert(Buckets, NumBuckets, new (BA.Allocate<Item>()) Item(key, data,
 181                                                                InfoObj));
 182   }
 183
 184   io::Offset Emit(raw_ostream &out) {
 185     Info InfoObj;
 186     return Emit(out, InfoObj);
 187   }
 188
 189   io::Offset Emit(raw_ostream &out, Info &InfoObj) {
 190     using namespace clang::io;
 191
 192     // Emit the payload of the table.
 193     for (unsigned i = 0; i < NumBuckets; ++i) {
 194       Bucket& B = Buckets[i];
 195       if (!B.head) continue;
 196
 197       // Store the offset for the data of this bucket.
 198       B.off = out.tell();
 199       assert(B.off && "Cannot write a bucket at offset 0. Please add padding.");
 200
 201       // Write out the number of items in the bucket.
 202       Emit16(out, B.length);
 203       assert(B.length != 0  && "Bucket has a head but zero length?");
 204
 205       // Write out the entries in the bucket.
 206       for (Item *I = B.head; I ; I = I->next) {
 207         Emit32(out, I->hash);
 208         const std::pair<unsigned, unsigned>& Len =
 209           InfoObj.EmitKeyDataLength(out, I->key, I->data);
 210         InfoObj.EmitKey(out, I->key, Len.first);
 211         InfoObj.EmitData(out, I->key, I->data, Len.second);
 212       }
 213     }
 214
 215     // Emit the hashtable itself.
 216     Pad(out, 4);
 217     io::Offset TableOff = out.tell();
 218     Emit32(out, NumBuckets);
 219     Emit32(out, NumEntries);
 220     for (unsigned i = 0; i < NumBuckets; ++i) Emit32(out, Buckets[i].off);
 221
 222     return TableOff;
 223   }
 224
 225   OnDiskChainedHashTableGenerator() {
 226     NumEntries = 0;
 227     NumBuckets = 64;
 228     // Note that we do not need to run the constructors of the individual
 229     // Bucket objects since 'calloc' returns bytes that are all 0.
 230     Buckets = (Bucket*) std::calloc(NumBuckets, sizeof(Bucket));
 231   }
 232
 233   ~OnDiskChainedHashTableGenerator() {
 234     std::free(Buckets);
 235   }
 236 };
 237
 238 template<typename Info>
 239 class OnDiskChainedHashTable {
 240   const unsigned NumBuckets;
 241   const unsigned NumEntries;
 242   const unsigned char* const Buckets;
 243   const unsigned char* const Base;
 244   Info InfoObj;
 245
 246 public:
 247   typedef typename Info::internal_key_type internal_key_type;
 248   typedef typename Info::external_key_type external_key_type;
 249   typedef typename Info::data_type         data_type;
 250
 251   OnDiskChainedHashTable(unsigned numBuckets, unsigned numEntries,
 252                          const unsigned char* buckets,
 253                          const unsigned char* base,
 254                          const Info &InfoObj = Info())
 255     : NumBuckets(numBuckets), NumEntries(numEntries),
 256       Buckets(buckets), Base(base), InfoObj(InfoObj) {
 257         assert((reinterpret_cast<uintptr_t>(buckets) & 0x3) == 0 &&
 258                "'buckets' must have a 4-byte alignment");
 259       }
 260
 261   unsigned getNumBuckets() const { return NumBuckets; }
 262   unsigned 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   public:
 274     iterator() : data(0), len(0) {}
 275     iterator(const internal_key_type k, const unsigned char* d, unsigned l,
 276              Info *InfoObj)
 277       : key(k), data(d), len(l), InfoObj(InfoObj) {}
 278
 279     data_type operator*() const { return InfoObj->ReadData(key, data, len); }
 280     bool operator==(const iterator& X) const { return X.data == data; }
 281     bool operator!=(const iterator& X) const { return X.data != data; }
 282   };
 283
 284   iterator find(const external_key_type& eKey, Info *InfoPtr = 0) {
 285     if (!InfoPtr)
 286       InfoPtr = &InfoObj;
 287
 288     using namespace io;
 289     const internal_key_type& iKey = InfoObj.GetInternalKey(eKey);
 290     unsigned key_hash = InfoObj.ComputeHash(iKey);
 291
 292     // Each bucket is just a 32-bit offset into the hash table file.
 293     unsigned idx = key_hash & (NumBuckets - 1);
 294     const unsigned char* Bucket = Buckets + sizeof(uint32_t)*idx;
 295
 296     unsigned offset = ReadLE32(Bucket);
 297     if (offset == 0) return iterator(); // Empty bucket.
 298     const unsigned char* Items = Base + offset;
 299
 300     // 'Items' starts with a 16-bit unsigned integer representing the
 301     // number of items in this bucket.
 302     unsigned len = ReadUnalignedLE16(Items);
 303
 304     for (unsigned i = 0; i < len; ++i) {
 305       // Read the hash.
 306       uint32_t item_hash = ReadUnalignedLE32(Items);
 307
 308       // Determine the length of the key and the data.
 309       const std::pair<unsigned, unsigned>& L = Info::ReadKeyDataLength(Items);
 310       unsigned item_len = L.first + L.second;
 311
 312       // Compare the hashes.  If they are not the same, skip the entry entirely.
 313       if (item_hash != key_hash) {
 314         Items += item_len;
 315         continue;
 316       }
 317
 318       // Read the key.
 319       const internal_key_type& X =
 320         InfoPtr->ReadKey((const unsigned char* const) Items, L.first);
 321
 322       // If the key doesn't match just skip reading the value.
 323       if (!InfoPtr->EqualKey(X, iKey)) {
 324         Items += item_len;
 325         continue;
 326       }
 327
 328       // The key matches!
 329       return iterator(X, Items + L.first, L.second, InfoPtr);
 330     }
 331
 332     return iterator();
 333   }
 334
 335   iterator end() const { return iterator(); }
 336
 337   /// \brief Iterates over all of the keys in the table.
 338   class key_iterator {
 339     const unsigned char* Ptr;
 340     unsigned NumItemsInBucketLeft;
 341     unsigned NumEntriesLeft;
 342     Info *InfoObj;
 343   public:
 344     typedef external_key_type value_type;
 345
 346     key_iterator(const unsigned char* const Ptr, unsigned NumEntries,
 347                   Info *InfoObj)
 348       : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries),
 349         InfoObj(InfoObj) { }
 350     key_iterator()
 351       : Ptr(0), NumItemsInBucketLeft(0), NumEntriesLeft(0), InfoObj(0) { }
 352
 353     friend bool operator==(const key_iterator &X, const key_iterator &Y) {
 354       return X.NumEntriesLeft == Y.NumEntriesLeft;
 355     }
 356     friend bool operator!=(const key_iterator& X, const key_iterator &Y) {
 357       return X.NumEntriesLeft != Y.NumEntriesLeft;
 358     }
 359
 360     key_iterator& operator++() {  // Preincrement
 361       if (!NumItemsInBucketLeft) {
 362         // 'Items' starts with a 16-bit unsigned integer representing the
 363         // number of items in this bucket.
 364         NumItemsInBucketLeft = io::ReadUnalignedLE16(Ptr);
 365       }
 366       Ptr += 4; // Skip the hash.
 367       // Determine the length of the key and the data.
 368       const std::pair<unsigned, unsigned>& L = Info::ReadKeyDataLength(Ptr);
 369       Ptr += L.first + L.second;
 370       assert(NumItemsInBucketLeft);
 371       --NumItemsInBucketLeft;
 372       assert(NumEntriesLeft);
 373       --NumEntriesLeft;
 374       return *this;
 375     }
 376     key_iterator operator++(int) {  // Postincrement
 377       key_iterator tmp = *this; ++*this; return tmp;
 378     }
 379
 380     value_type operator*() const {
 381       const unsigned char* LocalPtr = Ptr;
 382       if (!NumItemsInBucketLeft)
 383         LocalPtr += 2; // number of items in bucket
 384       LocalPtr += 4; // Skip the hash.
 385
 386       // Determine the length of the key and the data.
 387       const std::pair<unsigned, unsigned>& L
 388         = Info::ReadKeyDataLength(LocalPtr);
 389
 390       // Read the key.
 391       const internal_key_type& Key = InfoObj->ReadKey(LocalPtr, L.first);
 392       return InfoObj->GetExternalKey(Key);
 393     }
 394   };
 395
 396   key_iterator key_begin() {
 397     return key_iterator(Base + 4, getNumEntries(), &InfoObj);
 398   }
 399   key_iterator key_end() { return key_iterator(); }
 400
 401   /// \brief Iterates over all the entries in the table, returning the data.
 402   class data_iterator {
 403     const unsigned char* Ptr;
 404     unsigned NumItemsInBucketLeft;
 405     unsigned NumEntriesLeft;
 406     Info *InfoObj;
 407   public:
 408     typedef data_type value_type;
 409
 410     data_iterator(const unsigned char* const Ptr, unsigned NumEntries,
 411                   Info *InfoObj)
 412       : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries),
 413         InfoObj(InfoObj) { }
 414     data_iterator()
 415       : Ptr(0), NumItemsInBucketLeft(0), NumEntriesLeft(0), InfoObj(0) { }
 416
 417     bool operator==(const data_iterator& X) const {
 418       return X.NumEntriesLeft == NumEntriesLeft;
 419     }
 420     bool operator!=(const data_iterator& X) const {
 421       return X.NumEntriesLeft != NumEntriesLeft;
 422     }
 423
 424     data_iterator& operator++() {  // Preincrement
 425       if (!NumItemsInBucketLeft) {
 426         // 'Items' starts with a 16-bit unsigned integer representing the
 427         // number of items in this bucket.
 428         NumItemsInBucketLeft = io::ReadUnalignedLE16(Ptr);
 429       }
 430       Ptr += 4; // Skip the hash.
 431       // Determine the length of the key and the data.
 432       const std::pair<unsigned, unsigned>& L = Info::ReadKeyDataLength(Ptr);
 433       Ptr += L.first + L.second;
 434       assert(NumItemsInBucketLeft);
 435       --NumItemsInBucketLeft;
 436       assert(NumEntriesLeft);
 437       --NumEntriesLeft;
 438       return *this;
 439     }
 440     data_iterator operator++(int) {  // Postincrement
 441       data_iterator tmp = *this; ++*this; return tmp;
 442     }
 443
 444     value_type operator*() const {
 445       const unsigned char* LocalPtr = Ptr;
 446       if (!NumItemsInBucketLeft)
 447         LocalPtr += 2; // number of items in bucket
 448       LocalPtr += 4; // Skip the hash.
 449
 450       // Determine the length of the key and the data.
 451       const std::pair<unsigned, unsigned>& L =Info::ReadKeyDataLength(LocalPtr);
 452
 453       // Read the key.
 454       const internal_key_type& Key =
 455         InfoObj->ReadKey(LocalPtr, L.first);
 456       return InfoObj->ReadData(Key, LocalPtr + L.first, L.second);
 457     }
 458   };
 459
 460   data_iterator data_begin() {
 461     return data_iterator(Base + 4, getNumEntries(), &InfoObj);
 462   }
 463   data_iterator data_end() { return data_iterator(); }
 464
 465   Info &getInfoObj() { return InfoObj; }
 466
 467   static OnDiskChainedHashTable* Create(const unsigned char* buckets,
 468                                         const unsigned char* const base,
 469                                         const Info &InfoObj = Info()) {
 470     using namespace io;
 471     assert(buckets > base);
 472     assert((reinterpret_cast<uintptr_t>(buckets) & 0x3) == 0 &&
 473            "buckets should be 4-byte aligned.");
 474
 475     unsigned numBuckets = ReadLE32(buckets);
 476     unsigned numEntries = ReadLE32(buckets);
 477     return new OnDiskChainedHashTable<Info>(numBuckets, numEntries, buckets,
 478                                             base, InfoObj);
 479   }
 480 };
 481
 482 } // end namespace clang
 483
 484 #endif