LCOV - code coverage report
Current view: top level - lib/DebugInfo/PDB/Native - HashTable.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 82 97 84.5 %
Date: 2018-02-22 16:16:46 Functions: 21 23 91.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- HashTable.cpp - PDB Hash Table -------------------------------------===//
       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             : #include "llvm/DebugInfo/PDB/Native/HashTable.h"
      11             : #include "llvm/ADT/Optional.h"
      12             : #include "llvm/DebugInfo/PDB/Native/RawError.h"
      13             : #include "llvm/Support/BinaryStreamReader.h"
      14             : #include "llvm/Support/BinaryStreamWriter.h"
      15             : #include "llvm/Support/Error.h"
      16             : #include "llvm/Support/MathExtras.h"
      17             : #include <algorithm>
      18             : #include <cassert>
      19             : #include <cstdint>
      20             : #include <utility>
      21             : 
      22             : using namespace llvm;
      23             : using namespace llvm::pdb;
      24             : 
      25             : namespace {
      26             : struct IdentityTraits {
      27             :   static uint32_t hash(uint32_t K, const HashTable &Ctx) { return K; }
      28             :   static uint32_t realKey(uint32_t K, const HashTable &Ctx) { return K; }
      29             :   static uint32_t lowerKey(uint32_t K, const HashTable &Ctx) { return K; }
      30             : };
      31             : } // namespace
      32             : 
      33        3158 : HashTable::HashTable() : HashTable(8) {}
      34             : 
      35       12114 : HashTable::HashTable(uint32_t Capacity) { Buckets.resize(Capacity); }
      36             : 
      37          77 : Error HashTable::load(BinaryStreamReader &Stream) {
      38             :   const Header *H;
      39         154 :   if (auto EC = Stream.readObject(H))
      40             :     return EC;
      41         154 :   if (H->Capacity == 0)
      42             :     return make_error<RawError>(raw_error_code::corrupt_file,
      43             :                                 "Invalid Hash Table Capacity");
      44          77 :   if (H->Size > maxLoad(H->Capacity))
      45             :     return make_error<RawError>(raw_error_code::corrupt_file,
      46             :                                 "Invalid Hash Table Size");
      47             : 
      48         154 :   Buckets.resize(H->Capacity);
      49             : 
      50         154 :   if (auto EC = readSparseBitVector(Stream, Present))
      51             :     return EC;
      52         154 :   if (Present.count() != H->Size)
      53             :     return make_error<RawError>(raw_error_code::corrupt_file,
      54             :                                 "Present bit vector does not match size!");
      55             : 
      56         154 :   if (auto EC = readSparseBitVector(Stream, Deleted))
      57             :     return EC;
      58          77 :   if (Present.intersects(Deleted))
      59             :     return make_error<RawError>(raw_error_code::corrupt_file,
      60             :                                 "Present bit vector interesects deleted!");
      61             : 
      62         188 :   for (uint32_t P : Present) {
      63         564 :     if (auto EC = Stream.readInteger(Buckets[P].first))
      64             :       return EC;
      65         564 :     if (auto EC = Stream.readInteger(Buckets[P].second))
      66             :       return EC;
      67             :   }
      68             : 
      69             :   return Error::success();
      70             : }
      71             : 
      72          81 : uint32_t HashTable::calculateSerializedLength() const {
      73             :   uint32_t Size = sizeof(Header);
      74             : 
      75          81 :   int NumBitsP = Present.find_last() + 1;
      76          81 :   int NumBitsD = Deleted.find_last() + 1;
      77             : 
      78             :   // Present bit set number of words, followed by that many actual words.
      79             :   Size += sizeof(uint32_t);
      80         162 :   Size += alignTo(NumBitsP, sizeof(uint32_t));
      81             : 
      82             :   // Deleted bit set number of words, followed by that many actual words.
      83          81 :   Size += sizeof(uint32_t);
      84         162 :   Size += alignTo(NumBitsD, sizeof(uint32_t));
      85             : 
      86             :   // One (Key, Value) pair for each entry Present.
      87          81 :   Size += 2 * sizeof(uint32_t) * size();
      88             : 
      89          81 :   return Size;
      90             : }
      91             : 
      92          81 : Error HashTable::commit(BinaryStreamWriter &Writer) const {
      93             :   Header H;
      94          81 :   H.Size = size();
      95          81 :   H.Capacity = capacity();
      96          81 :   if (auto EC = Writer.writeObject(H))
      97             :     return EC;
      98             : 
      99         162 :   if (auto EC = writeSparseBitVector(Writer, Present))
     100             :     return EC;
     101             : 
     102         162 :   if (auto EC = writeSparseBitVector(Writer, Deleted))
     103             :     return EC;
     104             : 
     105         498 :   for (const auto &Entry : *this) {
     106         336 :     if (auto EC = Writer.writeInteger(Entry.first))
     107             :       return EC;
     108         336 :     if (auto EC = Writer.writeInteger(Entry.second))
     109             :       return EC;
     110             :   }
     111             :   return Error::success();
     112             : }
     113             : 
     114           0 : void HashTable::clear() {
     115           0 :   Buckets.resize(8);
     116             :   Present.clear();
     117             :   Deleted.clear();
     118           0 : }
     119             : 
     120      306488 : uint32_t HashTable::capacity() const { return Buckets.size(); }
     121             : 
     122       81860 : uint32_t HashTable::size() const { return Present.count(); }
     123             : 
     124          98 : HashTableIterator HashTable::begin() const { return HashTableIterator(*this); }
     125             : 
     126       58378 : HashTableIterator HashTable::end() const {
     127       58378 :   return HashTableIterator(*this, 0, true);
     128             : }
     129             : 
     130          41 : HashTableIterator HashTable::find(uint32_t K) const {
     131          41 :   return find_as<IdentityTraits>(K, *this);
     132             : }
     133             : 
     134          25 : void HashTable::set(uint32_t K, uint32_t V) {
     135             :   set_as<IdentityTraits, uint32_t>(K, V, *this);
     136          25 : }
     137             : 
     138           2 : void HashTable::remove(uint32_t K) { remove_as<IdentityTraits>(K, *this); }
     139             : 
     140          20 : uint32_t HashTable::get(uint32_t K) {
     141          20 :   auto I = find(K);
     142             :   assert(I != end());
     143          20 :   return (*I).second;
     144             : }
     145             : 
     146       37935 : uint32_t HashTable::maxLoad(uint32_t capacity) { return capacity * 2 / 3 + 1; }
     147             : 
     148         154 : Error HashTable::readSparseBitVector(BinaryStreamReader &Stream,
     149             :                                      SparseBitVector<> &V) {
     150             :   uint32_t NumWords;
     151         308 :   if (auto EC = Stream.readInteger(NumWords))
     152             :     return joinErrors(
     153             :         std::move(EC),
     154           0 :         make_error<RawError>(raw_error_code::corrupt_file,
     155           0 :                              "Expected hash table number of words"));
     156             : 
     157         404 :   for (uint32_t I = 0; I != NumWords; ++I) {
     158             :     uint32_t Word;
     159         250 :     if (auto EC = Stream.readInteger(Word))
     160             :       return joinErrors(std::move(EC),
     161           0 :                         make_error<RawError>(raw_error_code::corrupt_file,
     162           0 :                                              "Expected hash table word"));
     163        8125 :     for (unsigned Idx = 0; Idx < 32; ++Idx)
     164        4000 :       if (Word & (1U << Idx))
     165         188 :         V.set((I * 32) + Idx);
     166             :   }
     167             :   return Error::success();
     168             : }
     169             : 
     170         162 : Error HashTable::writeSparseBitVector(BinaryStreamWriter &Writer,
     171             :                                       SparseBitVector<> &Vec) {
     172         162 :   int ReqBits = Vec.find_last() + 1;
     173         324 :   uint32_t NumWords = alignTo(ReqBits, sizeof(uint32_t)) / sizeof(uint32_t);
     174         324 :   if (auto EC = Writer.writeInteger(NumWords))
     175             :     return joinErrors(
     176             :         std::move(EC),
     177           0 :         make_error<RawError>(raw_error_code::corrupt_file,
     178           0 :                              "Could not write linear map number of words"));
     179             : 
     180             :   uint32_t Idx = 0;
     181         490 :   for (uint32_t I = 0; I != NumWords; ++I) {
     182             :     uint32_t Word = 0;
     183       10660 :     for (uint32_t WordIdx = 0; WordIdx < 32; ++WordIdx, ++Idx) {
     184        5248 :       if (Vec.test(Idx))
     185         168 :         Word |= (1 << WordIdx);
     186             :     }
     187         328 :     if (auto EC = Writer.writeInteger(Word))
     188           0 :       return joinErrors(std::move(EC), make_error<RawError>(
     189             :                                            raw_error_code::corrupt_file,
     190           0 :                                            "Could not write linear map word"));
     191             :   }
     192             :   return Error::success();
     193             : }
     194             : 
     195      116678 : HashTableIterator::HashTableIterator(const HashTable &Map, uint32_t Index,
     196      116678 :                                      bool IsEnd)
     197      116678 :     : Map(&Map), Index(Index), IsEnd(IsEnd) {}
     198             : 
     199          98 : HashTableIterator::HashTableIterator(const HashTable &Map) : Map(&Map) {
     200             :   int I = Map.Present.find_first();
     201          94 :   if (I == -1) {
     202           4 :     Index = 0;
     203           4 :     IsEnd = true;
     204             :   } else {
     205          94 :     Index = static_cast<uint32_t>(I);
     206          94 :     IsEnd = false;
     207             :   }
     208          98 : }
     209             : 
     210           0 : HashTableIterator &HashTableIterator::operator=(const HashTableIterator &R) {
     211           0 :   Map = R.Map;
     212           0 :   return *this;
     213             : }
     214             : 
     215       58581 : bool HashTableIterator::operator==(const HashTableIterator &R) const {
     216       58581 :   if (IsEnd && R.IsEnd)
     217             :     return true;
     218       20624 :   if (IsEnd != R.IsEnd)
     219             :     return false;
     220             : 
     221           0 :   return (Map == R.Map) && (Index == R.Index);
     222             : }
     223             : 
     224       20622 : const std::pair<uint32_t, uint32_t> &HashTableIterator::operator*() const {
     225             :   assert(Map->Present.test(Index));
     226       41244 :   return Map->Buckets[Index];
     227             : }
     228             : 
     229         203 : HashTableIterator &HashTableIterator::operator++() {
     230        1468 :   while (Index < Map->Buckets.size()) {
     231         640 :     ++Index;
     232         640 :     if (Map->Present.test(Index))
     233             :       return *this;
     234             :   }
     235             : 
     236          94 :   IsEnd = true;
     237          94 :   return *this;
     238             : }

Generated by: LCOV version 1.13