LCOV - code coverage report
Current view: top level - lib/DebugInfo/PDB/Native - HashTable.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 127 159 79.9 %
Date: 2017-09-14 15:23:50 Functions: 23 24 95.8 %
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         285 : HashTable::HashTable() : HashTable(8) {}
      26             : 
      27        1148 : HashTable::HashTable(uint32_t Capacity) { Buckets.resize(Capacity); }
      28             : 
      29          69 : Error HashTable::load(BinaryStreamReader &Stream) {
      30             :   const Header *H;
      31         207 :   if (auto EC = Stream.readObject(H))
      32           0 :     return EC;
      33         138 :   if (H->Capacity == 0)
      34             :     return make_error<RawError>(raw_error_code::corrupt_file,
      35           0 :                                 "Invalid Hash Table Capacity");
      36         207 :   if (H->Size > maxLoad(H->Capacity))
      37             :     return make_error<RawError>(raw_error_code::corrupt_file,
      38           0 :                                 "Invalid Hash Table Size");
      39             : 
      40         138 :   Buckets.resize(H->Capacity);
      41             : 
      42         207 :   if (auto EC = readSparseBitVector(Stream, Present))
      43           0 :     return EC;
      44         207 :   if (Present.count() != H->Size)
      45             :     return make_error<RawError>(raw_error_code::corrupt_file,
      46           0 :                                 "Present bit vector does not match size!");
      47             : 
      48         207 :   if (auto EC = readSparseBitVector(Stream, Deleted))
      49           0 :     return EC;
      50          69 :   if (Present.intersects(Deleted))
      51             :     return make_error<RawError>(raw_error_code::corrupt_file,
      52           0 :                                 "Present bit vector interesects deleted!");
      53             : 
      54         311 :   for (uint32_t P : Present) {
      55         692 :     if (auto EC = Stream.readInteger(Buckets[P].first))
      56           0 :       return EC;
      57         692 :     if (auto EC = Stream.readInteger(Buckets[P].second))
      58           0 :       return EC;
      59             :   }
      60             : 
      61         207 :   return Error::success();
      62             : }
      63             : 
      64          61 : uint32_t HashTable::calculateSerializedLength() const {
      65          61 :   uint32_t Size = sizeof(Header);
      66             : 
      67          61 :   int NumBitsP = Present.find_last() + 1;
      68          61 :   int NumBitsD = Deleted.find_last() + 1;
      69             : 
      70             :   // Present bit set number of words, followed by that many actual words.
      71          61 :   Size += sizeof(uint32_t);
      72         122 :   Size += alignTo(NumBitsP, sizeof(uint32_t));
      73             : 
      74             :   // Deleted bit set number of words, followed by that many actual words.
      75          61 :   Size += sizeof(uint32_t);
      76         122 :   Size += alignTo(NumBitsD, sizeof(uint32_t));
      77             : 
      78             :   // One (Key, Value) pair for each entry Present.
      79          61 :   Size += 2 * sizeof(uint32_t) * size();
      80             : 
      81          61 :   return Size;
      82             : }
      83             : 
      84          61 : Error HashTable::commit(BinaryStreamWriter &Writer) const {
      85             :   Header H;
      86         122 :   H.Size = size();
      87         122 :   H.Capacity = capacity();
      88         183 :   if (auto EC = Writer.writeObject(H))
      89           0 :     return EC;
      90             : 
      91         183 :   if (auto EC = writeSparseBitVector(Writer, Present))
      92           0 :     return EC;
      93             : 
      94         183 :   if (auto EC = writeSparseBitVector(Writer, Deleted))
      95           0 :     return EC;
      96             : 
      97         378 :   for (const auto &Entry : *this) {
      98         384 :     if (auto EC = Writer.writeInteger(Entry.first))
      99           0 :       return EC;
     100         384 :     if (auto EC = Writer.writeInteger(Entry.second))
     101           0 :       return EC;
     102             :   }
     103         183 :   return Error::success();
     104             : }
     105             : 
     106         128 : void HashTable::clear() {
     107         128 :   Buckets.resize(8);
     108         256 :   Present.clear();
     109         256 :   Deleted.clear();
     110         128 : }
     111             : 
     112         892 : uint32_t HashTable::capacity() const { return Buckets.size(); }
     113             : 
     114         584 : uint32_t HashTable::size() const { return Present.count(); }
     115             : 
     116         133 : HashTableIterator HashTable::begin() const { return HashTableIterator(*this); }
     117             : 
     118         313 : HashTableIterator HashTable::end() const {
     119         313 :   return HashTableIterator(*this, 0, true);
     120             : }
     121             : 
     122         200 : HashTableIterator HashTable::find(uint32_t K) {
     123         200 :   uint32_t H = K % capacity();
     124         200 :   uint32_t I = H;
     125         200 :   Optional<uint32_t> FirstUnused;
     126             :   do {
     127         426 :     if (isPresent(I)) {
     128         104 :       if (Buckets[I].first == K)
     129          42 :         return HashTableIterator(*this, I, false);
     130             :     } else {
     131         161 :       if (!FirstUnused)
     132             :         FirstUnused = I;
     133             :       // Insertion occurs via linear probing from the slot hint, and will be
     134             :       // inserted at the first empty / deleted location.  Therefore, if we are
     135             :       // probing and find a location that is neither present nor deleted, then
     136             :       // nothing must have EVER been inserted at this location, and thus it is
     137             :       // not possible for a matching value to occur later.
     138         322 :       if (!isDeleted(I))
     139             :         break;
     140             :     }
     141          13 :     I = (I + 1) % capacity();
     142          13 :   } while (I != H);
     143             : 
     144             :   // The only way FirstUnused would not be set is if every single entry in the
     145             :   // table were Present.  But this would violate the load factor constraints
     146             :   // that we impose, so it should never happen.
     147             :   assert(FirstUnused);
     148         158 :   return HashTableIterator(*this, *FirstUnused, true);
     149             : }
     150             : 
     151         157 : void HashTable::set(uint32_t K, uint32_t V) {
     152         157 :   auto Entry = find(K);
     153         314 :   if (Entry != end()) {
     154             :     assert(isPresent(Entry.index()));
     155             :     assert(Buckets[Entry.index()].first == K);
     156             :     // We're updating, no need to do anything special.
     157           0 :     Buckets[Entry.index()].second = V;
     158           0 :     return;
     159             :   }
     160             : 
     161         314 :   auto &B = Buckets[Entry.index()];
     162             :   assert(!isPresent(Entry.index()));
     163             :   assert(Entry.isEnd());
     164         157 :   B.first = K;
     165         157 :   B.second = V;
     166         157 :   Present.set(Entry.index());
     167         157 :   Deleted.reset(Entry.index());
     168             : 
     169         157 :   grow();
     170             : 
     171             :   assert(find(K) != end());
     172             : }
     173             : 
     174           2 : void HashTable::remove(uint32_t K) {
     175           2 :   auto Iter = find(K);
     176             :   // It wasn't here to begin with, just exit.
     177           2 :   if (Iter == end())
     178           0 :     return;
     179             : 
     180             :   assert(Present.test(Iter.index()));
     181             :   assert(!Deleted.test(Iter.index()));
     182           2 :   Deleted.set(Iter.index());
     183           2 :   Present.reset(Iter.index());
     184             : }
     185             : 
     186          20 : uint32_t HashTable::get(uint32_t K) {
     187          20 :   auto I = find(K);
     188             :   assert(I != end());
     189          20 :   return (*I).second;
     190             : }
     191             : 
     192         226 : uint32_t HashTable::maxLoad(uint32_t capacity) { return capacity * 2 / 3 + 1; }
     193             : 
     194         157 : void HashTable::grow() {
     195         157 :   uint32_t S = size();
     196         157 :   if (S < maxLoad(capacity()))
     197         155 :     return;
     198             :   assert(capacity() != UINT32_MAX && "Can't grow Hash table!");
     199             : 
     200             :   uint32_t NewCapacity =
     201           2 :       (capacity() <= INT32_MAX) ? capacity() * 2 : UINT32_MAX;
     202             : 
     203             :   // Growing requires rebuilding the table and re-hashing every item.  Make a
     204             :   // copy with a larger capacity, insert everything into the copy, then swap
     205             :   // it in.
     206           4 :   HashTable NewMap(NewCapacity);
     207          16 :   for (auto I : Present) {
     208          24 :     NewMap.set(Buckets[I].first, Buckets[I].second);
     209             :   }
     210             : 
     211           4 :   Buckets.swap(NewMap.Buckets);
     212           2 :   std::swap(Present, NewMap.Present);
     213           2 :   std::swap(Deleted, NewMap.Deleted);
     214             :   assert(capacity() == NewCapacity);
     215             :   assert(size() == S);
     216             : }
     217             : 
     218         138 : Error HashTable::readSparseBitVector(BinaryStreamReader &Stream,
     219             :                                      SparseBitVector<> &V) {
     220             :   uint32_t NumWords;
     221         414 :   if (auto EC = Stream.readInteger(NumWords))
     222             :     return joinErrors(
     223           0 :         std::move(EC),
     224           0 :         make_error<RawError>(raw_error_code::corrupt_file,
     225           0 :                              "Expected hash table number of words"));
     226             : 
     227         210 :   for (uint32_t I = 0; I != NumWords; ++I) {
     228             :     uint32_t Word;
     229         216 :     if (auto EC = Stream.readInteger(Word))
     230           0 :       return joinErrors(std::move(EC),
     231           0 :                         make_error<RawError>(raw_error_code::corrupt_file,
     232           0 :                                              "Expected hash table word"));
     233        2376 :     for (unsigned Idx = 0; Idx < 32; ++Idx)
     234        2304 :       if (Word & (1U << Idx))
     235         173 :         V.set((I * 32) + Idx);
     236             :   }
     237         414 :   return Error::success();
     238             : }
     239             : 
     240         122 : Error HashTable::writeSparseBitVector(BinaryStreamWriter &Writer,
     241             :                                       SparseBitVector<> &Vec) {
     242         122 :   int ReqBits = Vec.find_last() + 1;
     243         244 :   uint32_t NumWords = alignTo(ReqBits, sizeof(uint32_t)) / sizeof(uint32_t);
     244         366 :   if (auto EC = Writer.writeInteger(NumWords))
     245             :     return joinErrors(
     246           0 :         std::move(EC),
     247           0 :         make_error<RawError>(raw_error_code::corrupt_file,
     248           0 :                              "Could not write linear map number of words"));
     249             : 
     250         122 :   uint32_t Idx = 0;
     251         186 :   for (uint32_t I = 0; I != NumWords; ++I) {
     252             :     uint32_t Word = 0;
     253        4160 :     for (uint32_t WordIdx = 0; WordIdx < 32; ++WordIdx, ++Idx) {
     254        2048 :       if (Vec.test(Idx))
     255         128 :         Word |= (1 << WordIdx);
     256             :     }
     257         192 :     if (auto EC = Writer.writeInteger(Word))
     258           0 :       return joinErrors(std::move(EC), make_error<RawError>(
     259             :                                            raw_error_code::corrupt_file,
     260           0 :                                            "Could not write linear map word"));
     261             :   }
     262         366 :   return Error::success();
     263             : }
     264             : 
     265         513 : HashTableIterator::HashTableIterator(const HashTable &Map, uint32_t Index,
     266         513 :                                      bool IsEnd)
     267         513 :     : Map(&Map), Index(Index), IsEnd(IsEnd) {}
     268             : 
     269         133 : HashTableIterator::HashTableIterator(const HashTable &Map) : Map(&Map) {
     270         262 :   int I = Map.Present.find_first();
     271         129 :   if (I == -1) {
     272           4 :     Index = 0;
     273           4 :     IsEnd = true;
     274             :   } else {
     275         129 :     Index = static_cast<uint32_t>(I);
     276         129 :     IsEnd = false;
     277             :   }
     278         133 : }
     279             : 
     280           0 : HashTableIterator &HashTableIterator::operator=(const HashTableIterator &R) {
     281           0 :   Map = R.Map;
     282           0 :   return *this;
     283             : }
     284             : 
     285         606 : bool HashTableIterator::operator==(const HashTableIterator &R) const {
     286         606 :   if (IsEnd && R.IsEnd)
     287             :     return true;
     288         315 :   if (IsEnd != R.IsEnd)
     289             :     return false;
     290             : 
     291           0 :   return (Map == R.Map) && (Index == R.Index);
     292             : }
     293             : 
     294         313 : const std::pair<uint32_t, uint32_t> &HashTableIterator::operator*() const {
     295             :   assert(Map->Present.test(Index));
     296         626 :   return Map->Buckets[Index];
     297             : }
     298             : 
     299         293 : HashTableIterator &HashTableIterator::operator++() {
     300        2152 :   while (Index < Map->Buckets.size()) {
     301         947 :     ++Index;
     302         947 :     if (Map->Present.test(Index))
     303             :       return *this;
     304             :   }
     305             : 
     306         129 :   IsEnd = true;
     307         129 :   return *this;
     308             : }

Generated by: LCOV version 1.13