contrib/llvm/include/llvm/DebugInfo/PDB/Native/HashTable.h

   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 HashTableIterator;
  30
  31 class HashTable {
  32   friend class HashTableIterator;
  33
  34   struct Header {
  35     support::ulittle32_t Size;
  36     support::ulittle32_t Capacity;
  37   };
  38
  39   using BucketList = std::vector<std::pair<uint32_t, uint32_t>>;
  40
  41 public:
  42   HashTable();
  43   explicit HashTable(uint32_t Capacity);
  44
  45   Error load(BinaryStreamReader &Stream);
  46
  47   uint32_t calculateSerializedLength() const;
  48   Error commit(BinaryStreamWriter &Writer) const;
  49
  50   void clear();
  51
  52   uint32_t capacity() const;
  53   uint32_t size() const;
  54
  55   HashTableIterator begin() const;
  56   HashTableIterator end() const;
  57   HashTableIterator find(uint32_t K);
  58
  59   void set(uint32_t K, uint32_t V);
  60   void remove(uint32_t K);
  61   uint32_t get(uint32_t K);
  62
  63 protected:
  64   bool isPresent(uint32_t K) const { return Present.test(K); }
  65   bool isDeleted(uint32_t K) const { return Deleted.test(K); }
  66
  67   BucketList Buckets;
  68   mutable SparseBitVector<> Present;
  69   mutable SparseBitVector<> Deleted;
  70
  71 private:
  72   static uint32_t maxLoad(uint32_t capacity);
  73   void grow();
  74
  75   static Error readSparseBitVector(BinaryStreamReader &Stream,
  76                                    SparseBitVector<> &V);
  77   static Error writeSparseBitVector(BinaryStreamWriter &Writer,
  78                                     SparseBitVector<> &Vec);
  79 };
  80
  81 class HashTableIterator
  82     : public iterator_facade_base<HashTableIterator, std::forward_iterator_tag,
  83                                   std::pair<uint32_t, uint32_t>> {
  84   friend class HashTable;
  85
  86   HashTableIterator(const HashTable &Map, uint32_t Index, bool IsEnd);
  87
  88 public:
  89   HashTableIterator(const HashTable &Map);
  90
  91   HashTableIterator &operator=(const HashTableIterator &R);
  92   bool operator==(const HashTableIterator &R) const;
  93   const std::pair<uint32_t, uint32_t> &operator*() const;
  94   HashTableIterator &operator++();
  95
  96 private:
  97   bool isEnd() const { return IsEnd; }
  98   uint32_t index() const { return Index; }
  99
 100   const HashTable *Map;
 101   uint32_t Index;
 102   bool IsEnd;
 103 };
 104
 105 } // end namespace pdb
 106
 107 } // end namespace llvm
 108
 109 #endif // LLVM_DEBUGINFO_PDB_NATIVE_HASHTABLE_H