HashTable.h revision 317017 
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
27namespace llvm {
28namespace pdb {
29
30class HashTableIterator;
31
32class 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
41public:
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
63protected:
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
70private:
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
80class 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
86public:
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
94private:
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
107