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
19template
20<
21 typename Key,
22 typename TCell,
23 typename Hash = DefaultHash<Key>,
24 typename Grower = HashTableGrower<>,
25 typename Allocator = HashTableAllocator
26>
27class HashSetTable : public HashTable<Key, TCell, Hash, Grower, Allocator>
28{
29public:
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
69template <typename Key, typename Hash, typename TState = HashTableNoState>
70struct 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
87template
88<
89 typename Key,
90 typename Hash = DefaultHash<Key>,
91 typename Grower = HashTableGrower<>,
92 typename Allocator = HashTableAllocator
93>
94using HashSet = HashSetTable<Key, HashTableCell<Key, Hash>, Hash, Grower, Allocator>;
95
96
97template
98<
99 typename Key,
100 typename Hash = DefaultHash<Key>,
101 typename Grower = HashTableGrower<>,
102 typename Allocator = HashTableAllocator
103>
104using HashSetWithSavedHash = HashSetTable<Key, HashSetCellWithSavedHash<Key, Hash>, Hash, Grower, Allocator>;
105