LCOV - code coverage report
Current view: top level - include/llvm/Support - OnDiskHashTable.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 156 156 100.0 %
Date: 2017-09-14 15:23:50 Functions: 69 69 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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/Allocator.h"
      18             : #include "llvm/Support/DataTypes.h"
      19             : #include "llvm/Support/EndianStream.h"
      20             : #include "llvm/Support/Host.h"
      21             : #include "llvm/Support/MathExtras.h"
      22             : #include "llvm/Support/raw_ostream.h"
      23             : #include <cassert>
      24             : #include <cstdlib>
      25             : 
      26             : namespace llvm {
      27             : 
      28             : /// \brief 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             :   /// \brief A single item in the hash table.
      61      135222 :   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     2417652 :     Item(typename Info::key_type_ref Key, typename Info::data_type_ref Data,
      69             :          Info &InfoObj)
      70     2581470 :         : 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;
      76             :   llvm::SpecificBumpPtrAllocator<Item> BA;
      77             : 
      78             :   /// \brief 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             :   /// \brief Insert an item into the appropriate hash bucket.
      89             :   void insert(Bucket *Buckets, size_t Size, Item *E) {
      90     5160736 :     Bucket &B = Buckets[E->Hash & (Size - 1)];
      91     5160736 :     E->Next = B.Head;
      92     5160736 :     ++B.Length;
      93     5160736 :     B.Head = E;
      94             :   }
      95             : 
      96             :   /// \brief Resize the hash table, moving the old entries into the new buckets.
      97       14954 :   void resize(size_t NewSize) {
      98       14954 :     Bucket *NewBuckets = (Bucket *)std::calloc(NewSize, sizeof(Bucket));
      99             :     // Populate NewBuckets with the old entries.
     100     4247978 :     for (size_t I = 0; I < NumBuckets; ++I)
     101     4233024 :       for (Item *E = Buckets[I].Head; E;) {
     102     2743084 :         Item *N = E->Next;
     103     2742758 :         E->Next = nullptr;
     104     5486168 :         insert(NewBuckets, NewSize, E);
     105     2743084 :         E = N;
     106             :       }
     107             : 
     108       14954 :     free(Buckets);
     109       14954 :     NumBuckets = NewSize;
     110       14954 :     Buckets = NewBuckets;
     111       14954 :   }
     112             : 
     113             : public:
     114             :   /// \brief Insert an entry into the table.
     115             :   void insert(typename Info::key_type_ref Key,
     116             :               typename Info::data_type_ref Data) {
     117         326 :     Info InfoObj;
     118         344 :     insert(Key, Data, InfoObj);
     119             :   }
     120             : 
     121             :   /// \brief Insert an entry into the table.
     122             :   ///
     123             :   /// Uses the provided Info instead of a stack allocated one.
     124     2417652 :   void insert(typename Info::key_type_ref Key,
     125             :               typename Info::data_type_ref Data, Info &InfoObj) {
     126     2417652 :     ++NumEntries;
     127     2417652 :     if (4 * NumEntries >= 3 * NumBuckets)
     128        5279 :       resize(NumBuckets * 2);
     129     9602470 :     insert(Buckets, NumBuckets, new (BA.Allocate()) Item(Key, Data, InfoObj));
     130     2417652 :   }
     131             : 
     132             :   /// \brief Determine whether an entry has been inserted.
     133         128 :   bool contains(typename Info::key_type_ref Key, Info &InfoObj) {
     134         256 :     unsigned Hash = InfoObj.ComputeHash(Key);
     135         144 :     for (Item *I = Buckets[Hash & (NumBuckets - 1)].Head; I; I = I->Next)
     136         131 :       if (I->Hash == Hash && InfoObj.EqualKey(I->Key, Key))
     137             :         return true;
     138             :     return false;
     139             :   }
     140             : 
     141             :   /// \brief Emit the table to Out, which must not be at offset 0.
     142             :   offset_type Emit(raw_ostream &Out) {
     143             :     Info InfoObj;
     144          10 :     return Emit(Out, InfoObj);
     145             :   }
     146             : 
     147             :   /// \brief Emit the table to Out, which must not be at offset 0.
     148             :   ///
     149             :   /// Uses the provided Info instead of a stack allocated one.
     150       10852 :   offset_type Emit(raw_ostream &Out, Info &InfoObj) {
     151             :     using namespace llvm::support;
     152       10852 :     endian::Writer<little> LE(Out);
     153             : 
     154             :     // Now we're done adding entries, resize the bucket list if it's
     155             :     // significantly too large. (This only happens if the number of
     156             :     // entries is small and we're within our initial allocation of
     157             :     // 64 buckets.) We aim for an occupancy ratio in [3/8, 3/4).
     158             :     //
     159             :     // As a special case, if there are two or fewer entries, just
     160             :     // form a single bucket. A linear scan is fine in that case, and
     161             :     // this is very common in C++ class lookup tables. This also
     162             :     // guarantees we produce at least one bucket for an empty table.
     163             :     //
     164             :     // FIXME: Try computing a perfect hash function at this point.
     165       16375 :     unsigned TargetNumBuckets =
     166       21898 :         NumEntries <= 2 ? 1 : NextPowerOf2(NumEntries * 4 / 3);
     167       10852 :     if (TargetNumBuckets != NumBuckets)
     168        9675 :       resize(TargetNumBuckets);
     169             : 
     170             :     // Emit the payload of the table.
     171     7525110 :     for (offset_type I = 0; I < NumBuckets; ++I) {
     172     3757129 :       Bucket &B = Buckets[I];
     173     3757129 :       if (!B.Head)
     174     1915919 :         continue;
     175             : 
     176             :       // Store the offset for the data of this bucket.
     177     1764043 :       B.Off = Out.tell();
     178             :       assert(B.Off && "Cannot write a bucket at offset 0. Please add padding.");
     179             : 
     180             :       // Write out the number of items in the bucket.
     181     3528086 :       LE.write<uint16_t>(B.Length);
     182             :       assert(B.Length != 0 && "Bucket has a head but zero length?");
     183             : 
     184             :       // Write out the entries in the bucket.
     185     4181695 :       for (Item *I = B.Head; I; I = I->Next) {
     186     4835304 :         LE.write<typename Info::hash_value_type>(I->Hash);
     187     2417664 :         const std::pair<offset_type, offset_type> &Len =
     188         338 :             InfoObj.EmitKeyDataLength(Out, I->Key, I->Data);
     189             : #ifdef NDEBUG
     190     2485589 :         InfoObj.EmitKey(Out, I->Key, Len.first);
     191     2417664 :         InfoObj.EmitData(Out, I->Key, I->Data, Len.second);
     192             : #else
     193             :         // In asserts mode, check that the users length matches the data they
     194             :         // wrote.
     195             :         uint64_t KeyStart = Out.tell();
     196             :         InfoObj.EmitKey(Out, I->Key, Len.first);
     197             :         uint64_t DataStart = Out.tell();
     198             :         InfoObj.EmitData(Out, I->Key, I->Data, Len.second);
     199             :         uint64_t End = Out.tell();
     200             :         assert(offset_type(DataStart - KeyStart) == Len.first &&
     201             :                "key length does not match bytes written");
     202             :         assert(offset_type(End - DataStart) == Len.second &&
     203             :                "data length does not match bytes written");
     204             : #endif
     205             :       }
     206             :     }
     207             : 
     208             :     // Pad with zeros so that we can start the hashtable at an aligned address.
     209       10852 :     offset_type TableOff = Out.tell();
     210       21501 :     uint64_t N = llvm::OffsetToAlignment(TableOff, alignof(offset_type));
     211       10852 :     TableOff += N;
     212       25236 :     while (N--)
     213             :       LE.write<uint8_t>(0);
     214             : 
     215             :     // Emit the hashtable itself.
     216       21704 :     LE.write<offset_type>(NumBuckets);
     217       21704 :     LE.write<offset_type>(NumEntries);
     218     3767981 :     for (offset_type I = 0; I < NumBuckets; ++I)
     219     7514258 :       LE.write<offset_type>(Buckets[I].Off);
     220             : 
     221       10852 :     return TableOff;
     222             :   }
     223             : 
     224       21704 :   OnDiskChainedHashTableGenerator() {
     225       10852 :     NumEntries = 0;
     226       10852 :     NumBuckets = 64;
     227             :     // Note that we do not need to run the constructors of the individual
     228             :     // Bucket objects since 'calloc' returns bytes that are all 0.
     229       10852 :     Buckets = (Bucket *)std::calloc(NumBuckets, sizeof(Bucket));
     230       10852 :   }
     231             : 
     232       21704 :   ~OnDiskChainedHashTableGenerator() { std::free(Buckets); }
     233             : };
     234             : 
     235             : /// \brief Provides lookup on an on disk hash table.
     236             : ///
     237             : /// This needs an \c Info that handles reading values from the hash table's
     238             : /// payload and computes the hash for a given key. This should provide the
     239             : /// following interface:
     240             : ///
     241             : /// \code
     242             : /// class ExampleLookupInfo {
     243             : /// public:
     244             : ///   typedef ExampleData data_type;
     245             : ///   typedef ExampleInternalKey internal_key_type; // The stored key type.
     246             : ///   typedef ExampleKey external_key_type; // The type to pass to find().
     247             : ///   typedef uint32_t hash_value_type; // The type the hash function returns.
     248             : ///   typedef uint32_t offset_type; // The type for offsets into the table.
     249             : ///
     250             : ///   /// Compare two keys for equality.
     251             : ///   static bool EqualKey(internal_key_type &Key1, internal_key_type &Key2);
     252             : ///   /// Calculate the hash for the given key.
     253             : ///   static hash_value_type ComputeHash(internal_key_type &IKey);
     254             : ///   /// Translate from the semantic type of a key in the hash table to the
     255             : ///   /// type that is actually stored and used for hashing and comparisons.
     256             : ///   /// The internal and external types are often the same, in which case this
     257             : ///   /// can simply return the passed in value.
     258             : ///   static const internal_key_type &GetInternalKey(external_key_type &EKey);
     259             : ///   /// Read the key and data length from Buffer, leaving it pointing at the
     260             : ///   /// following byte.
     261             : ///   static std::pair<offset_type, offset_type>
     262             : ///   ReadKeyDataLength(const unsigned char *&Buffer);
     263             : ///   /// Read the key from Buffer, given the KeyLen as reported from
     264             : ///   /// ReadKeyDataLength.
     265             : ///   const internal_key_type &ReadKey(const unsigned char *Buffer,
     266             : ///                                    offset_type KeyLen);
     267             : ///   /// Read the data for Key from Buffer, given the DataLen as reported from
     268             : ///   /// ReadKeyDataLength.
     269             : ///   data_type ReadData(StringRef Key, const unsigned char *Buffer,
     270             : ///                      offset_type DataLen);
     271             : /// };
     272             : /// \endcode
     273         700 : template <typename Info> class OnDiskChainedHashTable {
     274             :   const typename Info::offset_type NumBuckets;
     275             :   const typename Info::offset_type NumEntries;
     276             :   const unsigned char *const Buckets;
     277             :   const unsigned char *const Base;
     278             :   Info InfoObj;
     279             : 
     280             : public:
     281             :   typedef Info InfoType;
     282             :   typedef typename Info::internal_key_type internal_key_type;
     283             :   typedef typename Info::external_key_type external_key_type;
     284             :   typedef typename Info::data_type data_type;
     285             :   typedef typename Info::hash_value_type hash_value_type;
     286             :   typedef typename Info::offset_type offset_type;
     287             : 
     288       18579 :   OnDiskChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
     289             :                          const unsigned char *Buckets,
     290             :                          const unsigned char *Base,
     291             :                          const Info &InfoObj = Info())
     292             :       : NumBuckets(NumBuckets), NumEntries(NumEntries), Buckets(Buckets),
     293       18931 :         Base(Base), InfoObj(InfoObj) {
     294             :     assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
     295             :            "'buckets' must have a 4-byte alignment");
     296             :   }
     297             : 
     298             :   /// Read the number of buckets and the number of entries from a hash table
     299             :   /// produced by OnDiskHashTableGenerator::Emit, and advance the Buckets
     300             :   /// pointer past them.
     301             :   static std::pair<offset_type, offset_type>
     302             :   readNumBucketsAndEntries(const unsigned char *&Buckets) {
     303             :     assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&
     304             :            "buckets should be 4-byte aligned.");
     305             :     using namespace llvm::support;
     306       18577 :     offset_type NumBuckets =
     307       18577 :         endian::readNext<offset_type, little, aligned>(Buckets);
     308       18577 :     offset_type NumEntries =
     309       18577 :         endian::readNext<offset_type, little, aligned>(Buckets);
     310       18577 :     return std::make_pair(NumBuckets, NumEntries);
     311             :   }
     312             : 
     313             :   offset_type getNumBuckets() const { return NumBuckets; }
     314             :   offset_type getNumEntries() const { return NumEntries; }
     315             :   const unsigned char *getBase() const { return Base; }
     316             :   const unsigned char *getBuckets() const { return Buckets; }
     317             : 
     318             :   bool isEmpty() const { return NumEntries == 0; }
     319             : 
     320             :   class iterator {
     321             :     internal_key_type Key;
     322             :     const unsigned char *const Data;
     323             :     const offset_type Len;
     324             :     Info *InfoObj;
     325             : 
     326             :   public:
     327     2767874 :     iterator() : Key(), Data(nullptr), Len(0), InfoObj(nullptr) {}
     328      365329 :     iterator(const internal_key_type K, const unsigned char *D, offset_type L,
     329             :              Info *InfoObj)
     330      365329 :         : Key(K), Data(D), Len(L), InfoObj(InfoObj) {}
     331             : 
     332      360051 :     data_type operator*() const { return InfoObj->ReadData(Key, Data, Len); }
     333             : 
     334             :     const unsigned char *getDataPtr() const { return Data; }
     335             :     offset_type getDataLen() const { return Len; }
     336             : 
     337             :     bool operator==(const iterator &X) const { return X.Data == Data; }
     338             :     bool operator!=(const iterator &X) const { return X.Data != Data; }
     339             :   };
     340             : 
     341             :   /// \brief Look up the stored data for a particular key.
     342      318837 :   iterator find(const external_key_type &EKey, Info *InfoPtr = nullptr) {
     343      319061 :     const internal_key_type &IKey = InfoObj.GetInternalKey(EKey);
     344      319073 :     hash_value_type KeyHash = InfoObj.ComputeHash(IKey);
     345      319055 :     return find_hashed(IKey, KeyHash, InfoPtr);
     346             :   }
     347             : 
     348             :   /// \brief Look up the stored data for a particular key with a known hash.
     349     1492778 :   iterator find_hashed(const internal_key_type &IKey, hash_value_type KeyHash,
     350             :                        Info *InfoPtr = nullptr) {
     351             :     using namespace llvm::support;
     352             : 
     353     1492778 :     if (!InfoPtr)
     354      339967 :       InfoPtr = &InfoObj;
     355             : 
     356             :     // Each bucket is just an offset into the hash table file.
     357     1492778 :     offset_type Idx = KeyHash & (NumBuckets - 1);
     358     1492778 :     const unsigned char *Bucket = Buckets + sizeof(offset_type) * Idx;
     359             : 
     360     1492778 :     offset_type Offset = endian::readNext<offset_type, little, aligned>(Bucket);
     361     1492778 :     if (Offset == 0)
     362             :       return iterator(); // Empty bucket.
     363      925758 :     const unsigned char *Items = Base + Offset;
     364             : 
     365             :     // 'Items' starts with a 16-bit unsigned integer representing the
     366             :     // number of items in this bucket.
     367      925758 :     unsigned Len = endian::readNext<uint16_t, little, unaligned>(Items);
     368             : 
     369     1742516 :     for (unsigned i = 0; i < Len; ++i) {
     370             :       // Read the hash.
     371     1182087 :       hash_value_type ItemHash =
     372             :           endian::readNext<hash_value_type, little, unaligned>(Items);
     373             : 
     374             :       // Determine the length of the key and the data.
     375     1182087 :       const std::pair<offset_type, offset_type> &L =
     376             :           Info::ReadKeyDataLength(Items);
     377     1182087 :       offset_type ItemLen = L.first + L.second;
     378             : 
     379             :       // Compare the hashes.  If they are not the same, skip the entry entirely.
     380     1989249 :       if (ItemHash != KeyHash) {
     381      807162 :         Items += ItemLen;
     382      807162 :         continue;
     383             :       }
     384             : 
     385             :       // Read the key.
     386      381572 :       const internal_key_type &X =
     387             :           InfoPtr->ReadKey((const unsigned char *const)Items, L.first);
     388             : 
     389             :       // If the key doesn't match just skip reading the value.
     390      384091 :       if (!InfoPtr->EqualKey(X, IKey)) {
     391        9596 :         Items += ItemLen;
     392        9596 :         continue;
     393             :       }
     394             : 
     395             :       // The key matches!
     396      365329 :       return iterator(X, Items + L.first, L.second, InfoPtr);
     397             :     }
     398             : 
     399             :     return iterator();
     400             :   }
     401             : 
     402     1492778 :   iterator end() const { return iterator(); }
     403             : 
     404       13658 :   Info &getInfoObj() { return InfoObj; }
     405             : 
     406             :   /// \brief Create the hash table.
     407             :   ///
     408             :   /// \param Buckets is the beginning of the hash table itself, which follows
     409             :   /// the payload of entire structure. This is the value returned by
     410             :   /// OnDiskHashTableGenerator::Emit.
     411             :   ///
     412             :   /// \param Base is the point from which all offsets into the structure are
     413             :   /// based. This is offset 0 in the stream that was used when Emitting the
     414             :   /// table.
     415        4458 :   static OnDiskChainedHashTable *Create(const unsigned char *Buckets,
     416             :                                         const unsigned char *const Base,
     417             :                                         const Info &InfoObj = Info()) {
     418             :     assert(Buckets > Base);
     419        4741 :     auto NumBucketsAndEntries = readNumBucketsAndEntries(Buckets);
     420        9482 :     return new OnDiskChainedHashTable<Info>(NumBucketsAndEntries.first,
     421             :                                             NumBucketsAndEntries.second,
     422        4458 :                                             Buckets, Base, InfoObj);
     423             :   }
     424             : };
     425             : 
     426             : /// \brief Provides lookup and iteration over an on disk hash table.
     427             : ///
     428             : /// \copydetails llvm::OnDiskChainedHashTable
     429             : template <typename Info>
     430         700 : class OnDiskIterableChainedHashTable : public OnDiskChainedHashTable<Info> {
     431             :   const unsigned char *Payload;
     432             : 
     433             : public:
     434             :   typedef OnDiskChainedHashTable<Info>          base_type;
     435             :   typedef typename base_type::internal_key_type internal_key_type;
     436             :   typedef typename base_type::external_key_type external_key_type;
     437             :   typedef typename base_type::data_type         data_type;
     438             :   typedef typename base_type::hash_value_type   hash_value_type;
     439             :   typedef typename base_type::offset_type       offset_type;
     440             : 
     441             : private:
     442             :   /// \brief Iterates over all of the keys in the table.
     443             :   class iterator_base {
     444             :     const unsigned char *Ptr;
     445             :     offset_type NumItemsInBucketLeft;
     446             :     offset_type NumEntriesLeft;
     447             : 
     448             :   public:
     449             :     typedef external_key_type value_type;
     450             : 
     451        1376 :     iterator_base(const unsigned char *const Ptr, offset_type NumEntries)
     452        1376 :         : Ptr(Ptr), NumItemsInBucketLeft(0), NumEntriesLeft(NumEntries) {}
     453         988 :     iterator_base()
     454        2554 :         : Ptr(nullptr), NumItemsInBucketLeft(0), NumEntriesLeft(0) {}
     455             : 
     456             :     friend bool operator==(const iterator_base &X, const iterator_base &Y) {
     457         190 :       return X.NumEntriesLeft == Y.NumEntriesLeft;
     458             :     }
     459             :     friend bool operator!=(const iterator_base &X, const iterator_base &Y) {
     460             :       return X.NumEntriesLeft != Y.NumEntriesLeft;
     461             :     }
     462             : 
     463             :     /// Move to the next item.
     464      272966 :     void advance() {
     465             :       using namespace llvm::support;
     466      272966 :       if (!NumItemsInBucketLeft) {
     467             :         // 'Items' starts with a 16-bit unsigned integer representing the
     468             :         // number of items in this bucket.
     469      199174 :         NumItemsInBucketLeft =
     470      398348 :             endian::readNext<uint16_t, little, unaligned>(Ptr);
     471             :       }
     472      272966 :       Ptr += sizeof(hash_value_type); // Skip the hash.
     473             :       // Determine the length of the key and the data.
     474      272966 :       const std::pair<offset_type, offset_type> &L =
     475      272966 :           Info::ReadKeyDataLength(Ptr);
     476      272966 :       Ptr += L.first + L.second;
     477             :       assert(NumItemsInBucketLeft);
     478      272966 :       --NumItemsInBucketLeft;
     479             :       assert(NumEntriesLeft);
     480      272966 :       --NumEntriesLeft;
     481      272966 :     }
     482             : 
     483             :     /// Get the start of the item as written by the trait (after the hash and
     484             :     /// immediately before the key and value length).
     485             :     const unsigned char *getItem() const {
     486      272967 :       return Ptr + (NumItemsInBucketLeft ? 0 : 2) + sizeof(hash_value_type);
     487             :     }
     488             :   };
     489             : 
     490             : public:
     491       13836 :   OnDiskIterableChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
     492             :                                  const unsigned char *Buckets,
     493             :                                  const unsigned char *Payload,
     494             :                                  const unsigned char *Base,
     495             :                                  const Info &InfoObj = Info())
     496             :       : base_type(NumBuckets, NumEntries, Buckets, Base, InfoObj),
     497       27672 :         Payload(Payload) {}
     498             : 
     499             :   /// \brief Iterates over all of the keys in the table.
     500             :   class key_iterator : public iterator_base {
     501             :     Info *InfoObj;
     502             : 
     503             :   public:
     504             :     typedef external_key_type value_type;
     505             : 
     506             :     key_iterator(const unsigned char *const Ptr, offset_type NumEntries,
     507             :                  Info *InfoObj)
     508         436 :         : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
     509        1708 :     key_iterator() : iterator_base(), InfoObj() {}
     510             : 
     511             :     key_iterator &operator++() {
     512      186957 :       this->advance();
     513             :       return *this;
     514             :     }
     515             :     key_iterator operator++(int) { // Postincrement
     516             :       key_iterator tmp = *this;
     517             :       ++*this;
     518             :       return tmp;
     519             :     }
     520             : 
     521      183219 :     internal_key_type getInternalKey() const {
     522      373914 :       auto *LocalPtr = this->getItem();
     523             : 
     524             :       // Determine the length of the key and the data.
     525      186957 :       auto L = Info::ReadKeyDataLength(LocalPtr);
     526             : 
     527             :       // Read the key.
     528      190695 :       return InfoObj->ReadKey(LocalPtr, L.first);
     529             :     }
     530             : 
     531             :     value_type operator*() const {
     532      186957 :       return InfoObj->GetExternalKey(getInternalKey());
     533             :     }
     534             :   };
     535             : 
     536             :   key_iterator key_begin() {
     537        1308 :     return key_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
     538             :   }
     539         436 :   key_iterator key_end() { return key_iterator(); }
     540             : 
     541             :   iterator_range<key_iterator> keys() {
     542           6 :     return make_range(key_begin(), key_end());
     543             :   }
     544             : 
     545             :   /// \brief Iterates over all the entries in the table, returning the data.
     546             :   class data_iterator : public iterator_base {
     547             :     Info *InfoObj;
     548             : 
     549             :   public:
     550             :     typedef data_type value_type;
     551             : 
     552        1376 :     data_iterator(const unsigned char *const Ptr, offset_type NumEntries,
     553             :                   Info *InfoObj)
     554        3104 :         : iterator_base(Ptr, NumEntries), InfoObj(InfoObj) {}
     555        3836 :     data_iterator() : iterator_base(), InfoObj() {}
     556             : 
     557             :     data_iterator &operator++() { // Preincrement
     558       86009 :       this->advance();
     559             :       return *this;
     560             :     }
     561             :     data_iterator operator++(int) { // Postincrement
     562         133 :       data_iterator tmp = *this;
     563         133 :       ++*this;
     564             :       return tmp;
     565             :     }
     566             : 
     567       83839 :     value_type operator*() const {
     568      167678 :       auto *LocalPtr = this->getItem();
     569             : 
     570             :       // Determine the length of the key and the data.
     571       83839 :       auto L = Info::ReadKeyDataLength(LocalPtr);
     572             : 
     573             :       // Read the key.
     574       83973 :       const internal_key_type &Key = InfoObj->ReadKey(LocalPtr, L.first);
     575      167544 :       return InfoObj->ReadData(Key, LocalPtr + L.first, L.second);
     576             :     }
     577             :   };
     578             : 
     579             :   data_iterator data_begin() {
     580        4930 :     return data_iterator(Payload, this->getNumEntries(), &this->getInfoObj());
     581             :   }
     582        1566 :   data_iterator data_end() { return data_iterator(); }
     583             : 
     584             :   iterator_range<data_iterator> data() {
     585             :     return make_range(data_begin(), data_end());
     586             :   }
     587             : 
     588             :   /// \brief Create the hash table.
     589             :   ///
     590             :   /// \param Buckets is the beginning of the hash table itself, which follows
     591             :   /// the payload of entire structure. This is the value returned by
     592             :   /// OnDiskHashTableGenerator::Emit.
     593             :   ///
     594             :   /// \param Payload is the beginning of the data contained in the table.  This
     595             :   /// is Base plus any padding or header data that was stored, ie, the offset
     596             :   /// that the stream was at when calling Emit.
     597             :   ///
     598             :   /// \param Base is the point from which all offsets into the structure are
     599             :   /// based. This is offset 0 in the stream that was used when Emitting the
     600             :   /// table.
     601             :   static OnDiskIterableChainedHashTable *
     602        4810 :   Create(const unsigned char *Buckets, const unsigned char *const Payload,
     603             :          const unsigned char *const Base, const Info &InfoObj = Info()) {
     604             :     assert(Buckets > Base);
     605        6106 :     auto NumBucketsAndEntries =
     606             :         OnDiskIterableChainedHashTable<Info>::readNumBucketsAndEntries(Buckets);
     607       12212 :     return new OnDiskIterableChainedHashTable<Info>(
     608             :         NumBucketsAndEntries.first, NumBucketsAndEntries.second,
     609        4810 :         Buckets, Payload, Base, InfoObj);
     610             :   }
     611             : };
     612             : 
     613             : } // end namespace llvm
     614             : 
     615             : #endif

Generated by: LCOV version 1.13