contrib/llvm/lib/DebugInfo/PDB/Native/HashTable.cpp

   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 HashTable::HashTable() : HashTable(8) {}
  26
  27 HashTable::HashTable(uint32_t Capacity) { Buckets.resize(Capacity); }
  28
  29 Error HashTable::load(BinaryStreamReader &Stream) {
  30   const Header *H;
  31   if (auto EC = Stream.readObject(H))
  32     return EC;
  33   if (H->Capacity == 0)
  34     return make_error<RawError>(raw_error_code::corrupt_file,
  35                                 "Invalid Hash Table Capacity");
  36   if (H->Size > maxLoad(H->Capacity))
  37     return make_error<RawError>(raw_error_code::corrupt_file,
  38                                 "Invalid Hash Table Size");
  39
  40   Buckets.resize(H->Capacity);
  41
  42   if (auto EC = readSparseBitVector(Stream, Present))
  43     return EC;
  44   if (Present.count() != H->Size)
  45     return make_error<RawError>(raw_error_code::corrupt_file,
  46                                 "Present bit vector does not match size!");
  47
  48   if (auto EC = readSparseBitVector(Stream, Deleted))
  49     return EC;
  50   if (Present.intersects(Deleted))
  51     return make_error<RawError>(raw_error_code::corrupt_file,
  52                                 "Present bit vector interesects deleted!");
  53
  54   for (uint32_t P : Present) {
  55     if (auto EC = Stream.readInteger(Buckets[P].first))
  56       return EC;
  57     if (auto EC = Stream.readInteger(Buckets[P].second))
  58       return EC;
  59   }
  60
  61   return Error::success();
  62 }
  63
  64 uint32_t HashTable::calculateSerializedLength() const {
  65   uint32_t Size = sizeof(Header);
  66
  67   int NumBitsP = Present.find_last() + 1;
  68   int NumBitsD = Deleted.find_last() + 1;
  69
  70   // Present bit set number of words, followed by that many actual words.
  71   Size += sizeof(uint32_t);
  72   Size += alignTo(NumBitsP, sizeof(uint32_t));
  73
  74   // Deleted bit set number of words, followed by that many actual words.
  75   Size += sizeof(uint32_t);
  76   Size += alignTo(NumBitsD, sizeof(uint32_t));
  77
  78   // One (Key, Value) pair for each entry Present.
  79   Size += 2 * sizeof(uint32_t) * size();
  80
  81   return Size;
  82 }
  83
  84 Error HashTable::commit(BinaryStreamWriter &Writer) const {
  85   Header H;
  86   H.Size = size();
  87   H.Capacity = capacity();
  88   if (auto EC = Writer.writeObject(H))
  89     return EC;
  90
  91   if (auto EC = writeSparseBitVector(Writer, Present))
  92     return EC;
  93
  94   if (auto EC = writeSparseBitVector(Writer, Deleted))
  95     return EC;
  96
  97   for (const auto &Entry : *this) {
  98     if (auto EC = Writer.writeInteger(Entry.first))
  99       return EC;
 100     if (auto EC = Writer.writeInteger(Entry.second))
 101       return EC;
 102   }
 103   return Error::success();
 104 }
 105
 106 void HashTable::clear() {
 107   Buckets.resize(8);
 108   Present.clear();
 109   Deleted.clear();
 110 }
 111
 112 uint32_t HashTable::capacity() const { return Buckets.size(); }
 113
 114 uint32_t HashTable::size() const { return Present.count(); }
 115
 116 HashTableIterator HashTable::begin() const { return HashTableIterator(*this); }
 117
 118 HashTableIterator HashTable::end() const {
 119   return HashTableIterator(*this, 0, true);
 120 }
 121
 122 HashTableIterator HashTable::find(uint32_t K) {
 123   uint32_t H = K % capacity();
 124   uint32_t I = H;
 125   Optional<uint32_t> FirstUnused;
 126   do {
 127     if (isPresent(I)) {
 128       if (Buckets[I].first == K)
 129         return HashTableIterator(*this, I, false);
 130     } else {
 131       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       if (!isDeleted(I))
 139         break;
 140     }
 141     I = (I + 1) % capacity();
 142   } 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   return HashTableIterator(*this, *FirstUnused, true);
 149 }
 150
 151 void HashTable::set(uint32_t K, uint32_t V) {
 152   auto Entry = find(K);
 153   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     Buckets[Entry.index()].second = V;
 158     return;
 159   }
 160
 161   auto &B = Buckets[Entry.index()];
 162   assert(!isPresent(Entry.index()));
 163   assert(Entry.isEnd());
 164   B.first = K;
 165   B.second = V;
 166   Present.set(Entry.index());
 167   Deleted.reset(Entry.index());
 168
 169   grow();
 170
 171   assert(find(K) != end());
 172 }
 173
 174 void HashTable::remove(uint32_t K) {
 175   auto Iter = find(K);
 176   // It wasn't here to begin with, just exit.
 177   if (Iter == end())
 178     return;
 179
 180   assert(Present.test(Iter.index()));
 181   assert(!Deleted.test(Iter.index()));
 182   Deleted.set(Iter.index());
 183   Present.reset(Iter.index());
 184 }
 185
 186 uint32_t HashTable::get(uint32_t K) {
 187   auto I = find(K);
 188   assert(I != end());
 189   return (*I).second;
 190 }
 191
 192 uint32_t HashTable::maxLoad(uint32_t capacity) { return capacity * 2 / 3 + 1; }
 193
 194 void HashTable::grow() {
 195   uint32_t S = size();
 196   if (S < maxLoad(capacity()))
 197     return;
 198   assert(capacity() != UINT32_MAX && "Can't grow Hash table!");
 199
 200   uint32_t NewCapacity =
 201       (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   HashTable NewMap(NewCapacity);
 207   for (auto I : Present) {
 208     NewMap.set(Buckets[I].first, Buckets[I].second);
 209   }
 210
 211   Buckets.swap(NewMap.Buckets);
 212   std::swap(Present, NewMap.Present);
 213   std::swap(Deleted, NewMap.Deleted);
 214   assert(capacity() == NewCapacity);
 215   assert(size() == S);
 216 }
 217
 218 Error HashTable::readSparseBitVector(BinaryStreamReader &Stream,
 219                                      SparseBitVector<> &V) {
 220   uint32_t NumWords;
 221   if (auto EC = Stream.readInteger(NumWords))
 222     return joinErrors(
 223         std::move(EC),
 224         make_error<RawError>(raw_error_code::corrupt_file,
 225                              "Expected hash table number of words"));
 226
 227   for (uint32_t I = 0; I != NumWords; ++I) {
 228     uint32_t Word;
 229     if (auto EC = Stream.readInteger(Word))
 230       return joinErrors(std::move(EC),
 231                         make_error<RawError>(raw_error_code::corrupt_file,
 232                                              "Expected hash table word"));
 233     for (unsigned Idx = 0; Idx < 32; ++Idx)
 234       if (Word & (1U << Idx))
 235         V.set((I * 32) + Idx);
 236   }
 237   return Error::success();
 238 }
 239
 240 Error HashTable::writeSparseBitVector(BinaryStreamWriter &Writer,
 241                                       SparseBitVector<> &Vec) {
 242   int ReqBits = Vec.find_last() + 1;
 243   uint32_t NumWords = alignTo(ReqBits, sizeof(uint32_t)) / sizeof(uint32_t);
 244   if (auto EC = Writer.writeInteger(NumWords))
 245     return joinErrors(
 246         std::move(EC),
 247         make_error<RawError>(raw_error_code::corrupt_file,
 248                              "Could not write linear map number of words"));
 249
 250   uint32_t Idx = 0;
 251   for (uint32_t I = 0; I != NumWords; ++I) {
 252     uint32_t Word = 0;
 253     for (uint32_t WordIdx = 0; WordIdx < 32; ++WordIdx, ++Idx) {
 254       if (Vec.test(Idx))
 255         Word |= (1 << WordIdx);
 256     }
 257     if (auto EC = Writer.writeInteger(Word))
 258       return joinErrors(std::move(EC), make_error<RawError>(
 259                                            raw_error_code::corrupt_file,
 260                                            "Could not write linear map word"));
 261   }
 262   return Error::success();
 263 }
 264
 265 HashTableIterator::HashTableIterator(const HashTable &Map, uint32_t Index,
 266                                      bool IsEnd)
 267     : Map(&Map), Index(Index), IsEnd(IsEnd) {}
 268
 269 HashTableIterator::HashTableIterator(const HashTable &Map) : Map(&Map) {
 270   int I = Map.Present.find_first();
 271   if (I == -1) {
 272     Index = 0;
 273     IsEnd = true;
 274   } else {
 275     Index = static_cast<uint32_t>(I);
 276     IsEnd = false;
 277   }
 278 }
 279
 280 HashTableIterator &HashTableIterator::operator=(const HashTableIterator &R) {
 281   Map = R.Map;
 282   return *this;
 283 }
 284
 285 bool HashTableIterator::operator==(const HashTableIterator &R) const {
 286   if (IsEnd && R.IsEnd)
 287     return true;
 288   if (IsEnd != R.IsEnd)
 289     return false;
 290
 291   return (Map == R.Map) && (Index == R.Index);
 292 }
 293
 294 const std::pair<uint32_t, uint32_t> &HashTableIterator::operator*() const {
 295   assert(Map->Present.test(Index));
 296   return Map->Buckets[Index];
 297 }
 298
 299 HashTableIterator &HashTableIterator::operator++() {
 300   while (Index < Map->Buckets.size()) {
 301     ++Index;
 302     if (Map->Present.test(Index))
 303       return *this;
 304   }
 305
 306   IsEnd = true;
 307   return *this;
 308 }