1 | #pragma once |
2 | |
3 | #include <Common/HashTable/Hash.h> |
4 | #include <Common/HashTable/HashTable.h> |
5 | #include <Common/HashTable/HashTableAllocator.h> |
6 | |
7 | #include <IO/WriteBuffer.h> |
8 | #include <IO/WriteHelpers.h> |
9 | #include <IO/ReadBuffer.h> |
10 | #include <IO/ReadHelpers.h> |
11 | #include <IO/VarInt.h> |
12 | |
13 | /** NOTE HashSet could only be used for memmoveable (position independent) types. |
14 | * Example: std::string is not position independent in libstdc++ with C++11 ABI or in libc++. |
15 | * Also, key must be of type, that zero bytes is compared equals to zero key. |
16 | */ |
17 | |
18 | |
19 | template |
20 | < |
21 | typename Key, |
22 | typename TCell, |
23 | typename Hash = DefaultHash<Key>, |
24 | typename Grower = HashTableGrower<>, |
25 | typename Allocator = HashTableAllocator |
26 | > |
27 | class HashSetTable : public HashTable<Key, TCell, Hash, Grower, Allocator> |
28 | { |
29 | public: |
30 | using Self = HashSetTable; |
31 | using Cell = TCell; |
32 | |
33 | using Base = HashTable<Key, TCell, Hash, Grower, Allocator>; |
34 | using typename Base::LookupResult; |
35 | |
36 | void merge(const Self & rhs) |
37 | { |
38 | if (!this->hasZero() && rhs.hasZero()) |
39 | { |
40 | this->setHasZero(); |
41 | ++this->m_size; |
42 | } |
43 | |
44 | for (size_t i = 0; i < rhs.grower.bufSize(); ++i) |
45 | if (!rhs.buf[i].isZero(*this)) |
46 | this->insert(Cell::getKey(rhs.buf[i].getValue())); |
47 | } |
48 | |
49 | |
50 | void readAndMerge(DB::ReadBuffer & rb) |
51 | { |
52 | Cell::State::read(rb); |
53 | |
54 | size_t new_size = 0; |
55 | DB::readVarUInt(new_size, rb); |
56 | |
57 | this->resize(new_size); |
58 | |
59 | for (size_t i = 0; i < new_size; ++i) |
60 | { |
61 | Cell x; |
62 | x.read(rb); |
63 | this->insert(Cell::getKey(x.getValue())); |
64 | } |
65 | } |
66 | }; |
67 | |
68 | |
69 | template <typename Key, typename Hash, typename TState = HashTableNoState> |
70 | struct HashSetCellWithSavedHash : public HashTableCell<Key, Hash, TState> |
71 | { |
72 | using Base = HashTableCell<Key, Hash, TState>; |
73 | |
74 | size_t saved_hash; |
75 | |
76 | HashSetCellWithSavedHash() : Base() {} |
77 | HashSetCellWithSavedHash(const Key & key_, const typename Base::State & state) : Base(key_, state) {} |
78 | |
79 | bool keyEquals(const Key & key_) const { return this->key == key_; } |
80 | bool keyEquals(const Key & key_, size_t hash_) const { return saved_hash == hash_ && this->key == key_; } |
81 | bool keyEquals(const Key & key_, size_t hash_, const typename Base::State &) const { return keyEquals(key_, hash_); } |
82 | |
83 | void setHash(size_t hash_value) { saved_hash = hash_value; } |
84 | size_t getHash(const Hash & /*hash_function*/) const { return saved_hash; } |
85 | }; |
86 | |
87 | template |
88 | < |
89 | typename Key, |
90 | typename Hash = DefaultHash<Key>, |
91 | typename Grower = HashTableGrower<>, |
92 | typename Allocator = HashTableAllocator |
93 | > |
94 | using HashSet = HashSetTable<Key, HashTableCell<Key, Hash>, Hash, Grower, Allocator>; |
95 | |
96 | |
97 | template |
98 | < |
99 | typename Key, |
100 | typename Hash = DefaultHash<Key>, |
101 | typename Grower = HashTableGrower<>, |
102 | typename Allocator = HashTableAllocator |
103 | > |
104 | using HashSetWithSavedHash = HashSetTable<Key, HashSetCellWithSavedHash<Key, Hash>, Hash, Grower, Allocator>; |
105 | |