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_RAW_HASHTABLE_H
  11 #define LLVM_DEBUGINFO_PDB_RAW_HASHTABLE_H
  12
  13 #include "llvm/ADT/ArrayRef.h"
  14 #include "llvm/ADT/SparseBitVector.h"
  15 #include "llvm/ADT/StringRef.h"
  16 #include "llvm/ADT/iterator.h"
  17 #include "llvm/Support/BinaryStreamArray.h"
  18 #include "llvm/Support/BinaryStreamReader.h"
  19 #include "llvm/Support/BinaryStreamWriter.h"
  20 #include "llvm/Support/Endian.h"
  21 #include "llvm/Support/Error.h"
  22 #include "llvm/Support/MathExtras.h"
  23
  24 #include <cstdint>
  25 #include <utility>
  26
  27 namespace llvm {
  28 namespace pdb {
  29
  30 class HashTableIterator;
  31
  32 class HashTable {
  33   friend class HashTableIterator;
  34   struct Header {
  35     support::ulittle32_t Size;
  36     support::ulittle32_t Capacity;
  37   };
  38
  39   typedef std::vector<std::pair<uint32_t, uint32_t>> BucketList;
  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   BucketList Buckets;
  67   mutable SparseBitVector<> Present;
  68   mutable SparseBitVector<> Deleted;
  69
  70 private:
  71   static uint32_t maxLoad(uint32_t capacity);
  72   void grow();
  73
  74   static Error readSparseBitVector(BinaryStreamReader &Stream,
  75                                    SparseBitVector<> &V);
  76   static Error writeSparseBitVector(BinaryStreamWriter &Writer,
  77                                     SparseBitVector<> &Vec);
  78 };
  79
  80 class HashTableIterator
  81     : public iterator_facade_base<HashTableIterator, std::forward_iterator_tag,
  82                                   std::pair<uint32_t, uint32_t>> {
  83   friend class HashTable;
  84   HashTableIterator(const HashTable &Map, uint32_t Index, bool IsEnd);
  85
  86 public:
  87   HashTableIterator(const HashTable &Map);
  88
  89   HashTableIterator &operator=(const HashTableIterator &R);
  90   bool operator==(const HashTableIterator &R) const;
  91   const std::pair<uint32_t, uint32_t> &operator*() const;
  92   HashTableIterator &operator++();
  93
  94 private:
  95   bool isEnd() const { return IsEnd; }
  96   uint32_t index() const { return Index; }
  97
  98   const HashTable *Map;
  99   uint32_t Index;
 100   bool IsEnd;
 101 };
 102
 103 } // end namespace pdb
 104 } // end namespace llvm
 105
 106 #endif // LLVM_DEBUGINFO_PDB_RAW_HASHTABLE_H