LCOV - code coverage report
Current view: top level - include/llvm/DebugInfo/PDB/Native - HashTable.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 42 45 93.3 %
Date: 2018-02-21 06:32:55 Functions: 8 8 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- HashTable.h - PDB Hash Table -----------------------------*- 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             : #ifndef LLVM_DEBUGINFO_PDB_NATIVE_HASHTABLE_H
      11             : #define LLVM_DEBUGINFO_PDB_NATIVE_HASHTABLE_H
      12             : 
      13             : #include "llvm/ADT/SparseBitVector.h"
      14             : #include "llvm/ADT/iterator.h"
      15             : #include "llvm/Support/Endian.h"
      16             : #include "llvm/Support/Error.h"
      17             : #include <cstdint>
      18             : #include <iterator>
      19             : #include <utility>
      20             : #include <vector>
      21             : 
      22             : namespace llvm {
      23             : 
      24             : class BinaryStreamReader;
      25             : class BinaryStreamWriter;
      26             : 
      27             : namespace pdb {
      28             : 
      29             : class HashTable;
      30             : 
      31             : class HashTableIterator
      32             :     : public iterator_facade_base<HashTableIterator, std::forward_iterator_tag,
      33             :                                   std::pair<uint32_t, uint32_t>> {
      34             :   friend HashTable;
      35             : 
      36             :   HashTableIterator(const HashTable &Map, uint32_t Index, bool IsEnd);
      37             : 
      38             : public:
      39             :   HashTableIterator(const HashTable &Map);
      40             : 
      41             :   HashTableIterator &operator=(const HashTableIterator &R);
      42             :   bool operator==(const HashTableIterator &R) const;
      43             :   const std::pair<uint32_t, uint32_t> &operator*() const;
      44             :   HashTableIterator &operator++();
      45             : 
      46             : private:
      47             :   bool isEnd() const { return IsEnd; }
      48             :   uint32_t index() const { return Index; }
      49             : 
      50             :   const HashTable *Map;
      51             :   uint32_t Index;
      52             :   bool IsEnd;
      53             : };
      54             : 
      55       12114 : class HashTable {
      56             :   friend class HashTableIterator;
      57             : 
      58             :   struct Header {
      59             :     support::ulittle32_t Size;
      60             :     support::ulittle32_t Capacity;
      61             :   };
      62             : 
      63             :   using BucketList = std::vector<std::pair<uint32_t, uint32_t>>;
      64             : 
      65             : public:
      66             :   HashTable();
      67             :   explicit HashTable(uint32_t Capacity);
      68             : 
      69             :   Error load(BinaryStreamReader &Stream);
      70             : 
      71             :   uint32_t calculateSerializedLength() const;
      72             :   Error commit(BinaryStreamWriter &Writer) const;
      73             : 
      74             :   void clear();
      75             : 
      76             :   uint32_t capacity() const;
      77             :   uint32_t size() const;
      78             : 
      79             :   HashTableIterator begin() const;
      80             :   HashTableIterator end() const;
      81             : 
      82             :   /// Find the entry with the specified key value.
      83             :   HashTableIterator find(uint32_t K) const;
      84             : 
      85             :   /// Find the entry whose key has the specified hash value, using the specified
      86             :   /// traits defining hash function and equality.
      87             :   template <typename Traits, typename Key, typename Context>
      88       58300 :   HashTableIterator find_as(const Key &K, const Context &Ctx) const {
      89       58300 :     uint32_t H = Traits::hash(K, Ctx) % capacity();
      90             :     uint32_t I = H;
      91             :     Optional<uint32_t> FirstUnused;
      92             :     do {
      93      109496 :       if (isPresent(I)) {
      94      143268 :         if (Traits::realKey(Buckets[I].first, Ctx) == K)
      95       20441 :           return HashTableIterator(*this, I, false);
      96             :       } else {
      97       37862 :         if (!FirstUnused)
      98             :           FirstUnused = I;
      99             :         // Insertion occurs via linear probing from the slot hint, and will be
     100             :         // inserted at the first empty / deleted location.  Therefore, if we are
     101             :         // probing and find a location that is neither present nor deleted, then
     102             :         // nothing must have EVER been inserted at this location, and thus it is
     103             :         // not possible for a matching value to occur later.
     104       37862 :         if (!isDeleted(I))
     105             :           break;
     106             :       }
     107       51196 :       I = (I + 1) % capacity();
     108       51196 :     } while (I != H);
     109             : 
     110             :     // The only way FirstUnused would not be set is if every single entry in the
     111             :     // table were Present.  But this would violate the load factor constraints
     112             :     // that we impose, so it should never happen.
     113             :     assert(FirstUnused);
     114       37859 :     return HashTableIterator(*this, *FirstUnused, true);
     115             :   }
     116             : 
     117             :   /// Set the entry with the specified key to the specified value.
     118             :   void set(uint32_t K, uint32_t V);
     119             : 
     120             :   /// Set the entry using a key type that the specified Traits can convert
     121             :   /// from a real key to an internal key.
     122             :   template <typename Traits, typename Key, typename Context>
     123             :   bool set_as(const Key &K, uint32_t V, Context &Ctx) {
     124       20464 :     return set_as_internal<Traits, Key, Context>(K, V, None, Ctx);
     125             :   }
     126             : 
     127             :   void remove(uint32_t K);
     128             : 
     129             :   template <typename Traits, typename Key, typename Context>
     130           2 :   void remove_as(const Key &K, Context &Ctx) {
     131           2 :     auto Iter = find_as<Traits, Key, Context>(K, Ctx);
     132             :     // It wasn't here to begin with, just exit.
     133           2 :     if (Iter == end())
     134           0 :       return;
     135             : 
     136             :     assert(Present.test(Iter.index()));
     137             :     assert(!Deleted.test(Iter.index()));
     138           2 :     Deleted.set(Iter.index());
     139           2 :     Present.reset(Iter.index());
     140             :   }
     141             : 
     142             :   uint32_t get(uint32_t K);
     143             : 
     144             : protected:
     145      109496 :   bool isPresent(uint32_t K) const { return Present.test(K); }
     146       37862 :   bool isDeleted(uint32_t K) const { return Deleted.test(K); }
     147             : 
     148             :   BucketList Buckets;
     149             :   mutable SparseBitVector<> Present;
     150             :   mutable SparseBitVector<> Deleted;
     151             : 
     152             : private:
     153             :   /// Set the entry using a key type that the specified Traits can convert
     154             :   /// from a real key to an internal key.
     155             :   template <typename Traits, typename Key, typename Context>
     156       37858 :   bool set_as_internal(const Key &K, uint32_t V, Optional<uint32_t> InternalKey,
     157             :                        Context &Ctx) {
     158       37858 :     auto Entry = find_as<Traits, Key, Context>(K, Ctx);
     159       75716 :     if (Entry != end()) {
     160             :       assert(isPresent(Entry.index()));
     161             :       assert(Traits::realKey(Buckets[Entry.index()].first, Ctx) == K);
     162             :       // We're updating, no need to do anything special.
     163           0 :       Buckets[Entry.index()].second = V;
     164           0 :       return false;
     165             :     }
     166             : 
     167       37858 :     auto &B = Buckets[Entry.index()];
     168             :     assert(!isPresent(Entry.index()));
     169             :     assert(Entry.isEnd());
     170       75679 :     B.first = InternalKey ? *InternalKey : Traits::lowerKey(K, Ctx);
     171       37858 :     B.second = V;
     172       37858 :     Present.set(Entry.index());
     173       37858 :     Deleted.reset(Entry.index());
     174             : 
     175       37858 :     grow<Traits, Key, Context>(Ctx);
     176             : 
     177             :     assert((find_as<Traits, Key, Context>(K, Ctx)) != end());
     178       37858 :     return true;
     179             :   }
     180             : 
     181             :   static uint32_t maxLoad(uint32_t capacity);
     182             : 
     183             :   template <typename Traits, typename Key, typename Context>
     184       37858 :   void grow(Context &Ctx) {
     185       37858 :     uint32_t S = size();
     186       37858 :     if (S < maxLoad(capacity()))
     187       34959 :       return;
     188             :     assert(capacity() != UINT32_MAX && "Can't grow Hash table!");
     189             : 
     190        5798 :     uint32_t NewCapacity =
     191        5798 :         (capacity() <= INT32_MAX) ? capacity() * 2 : UINT32_MAX;
     192             : 
     193             :     // Growing requires rebuilding the table and re-hashing every item.  Make a
     194             :     // copy with a larger capacity, insert everything into the copy, then swap
     195             :     // it in.
     196        5798 :     HashTable NewMap(NewCapacity);
     197       20293 :     for (auto I : Present) {
     198       52170 :       auto RealKey = Traits::realKey(Buckets[I].first, Ctx);
     199       17394 :       NewMap.set_as_internal<Traits, Key, Context>(RealKey, Buckets[I].second,
     200       17382 :                                                    Buckets[I].first, Ctx);
     201             :     }
     202             : 
     203             :     Buckets.swap(NewMap.Buckets);
     204        2899 :     std::swap(Present, NewMap.Present);
     205        2899 :     std::swap(Deleted, NewMap.Deleted);
     206             :     assert(capacity() == NewCapacity);
     207             :     assert(size() == S);
     208             :   }
     209             : 
     210             :   static Error readSparseBitVector(BinaryStreamReader &Stream,
     211             :                                    SparseBitVector<> &V);
     212             :   static Error writeSparseBitVector(BinaryStreamWriter &Writer,
     213             :                                     SparseBitVector<> &Vec);
     214             : };
     215             : 
     216             : } // end namespace pdb
     217             : 
     218             : } // end namespace llvm
     219             : 
     220             : #endif // LLVM_DEBUGINFO_PDB_NATIVE_HASHTABLE_H

Generated by: LCOV version 1.13