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_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/DebugInfo/MSF/StreamArray.h"
18 : #include "llvm/DebugInfo/MSF/StreamReader.h"
19 : #include "llvm/DebugInfo/MSF/StreamWriter.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 168 : class HashTable {
33 : friend class HashTableIterator;
34 5 : 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(msf::StreamReader &Stream);
46 :
47 : uint32_t calculateSerializedLength() const;
48 : Error commit(msf::StreamWriter &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 105 : bool isPresent(uint32_t K) const { return Present.test(K); }
65 53 : 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(msf::StreamReader &Stream,
75 : SparseBitVector<> &V);
76 : static Error writeSparseBitVector(msf::StreamWriter &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
|