1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
#pragma once
#include <Common/HashTable/Hash.h>
#include <Common/HashTable/HashTable.h>
#include <Common/HashTable/HashTableAllocator.h>
#include <Common/HashTable/TwoLevelHashTable.h>
#include <IO/WriteBuffer.h>
#include <IO/WriteHelpers.h>
#include <IO/ReadBuffer.h>
#include <IO/ReadHelpers.h>
#include <IO/VarInt.h>
namespace DB
{
namespace ErrorCodes
{
extern const int LOGICAL_ERROR;
extern const int TOO_LARGE_ARRAY_SIZE;
}
}
/** NOTE HashSet could only be used for memmoveable (position independent) types.
* Example: std::string is not position independent in libstdc++ with C++11 ABI or in libc++.
* Also, key must be of type, that zero bytes is compared equals to zero key.
*/
template <
typename Key,
typename TCell,
typename Hash = DefaultHash<Key>,
typename Grower = HashTableGrowerWithPrecalculation<>,
typename Allocator = HashTableAllocator>
class HashSetTable : public HashTable<Key, TCell, Hash, Grower, Allocator>
{
public:
using Self = HashSetTable;
using Cell = TCell;
using Base = HashTable<Key, TCell, Hash, Grower, Allocator>;
using typename Base::LookupResult;
using Base::Base;
void merge(const Self & rhs)
{
if (!this->hasZero() && rhs.hasZero())
{
this->setHasZero();
++this->m_size;
}
for (size_t i = 0; i < rhs.grower.bufSize(); ++i)
if (!rhs.buf[i].isZero(*this))
this->insert(rhs.buf[i].getValue());
}
void readAndMerge(DB::ReadBuffer & rb)
{
Cell::State::read(rb);
size_t new_size = 0;
DB::readVarUInt(new_size, rb);
if (new_size > 100'000'000'000)
throw DB::Exception(DB::ErrorCodes::TOO_LARGE_ARRAY_SIZE, "The size of serialized hash table is suspiciously large: {}", new_size);
this->resize(new_size);
for (size_t i = 0; i < new_size; ++i)
{
Cell x;
x.read(rb);
this->insert(x.getValue());
}
}
};
template <
typename Key,
typename TCell, /// Supposed to have no state (HashTableNoState)
typename Hash = DefaultHash<Key>,
typename Grower = TwoLevelHashTableGrower<>,
typename Allocator = HashTableAllocator>
class TwoLevelHashSetTable
: public TwoLevelHashTable<Key, TCell, Hash, Grower, Allocator, HashSetTable<Key, TCell, Hash, Grower, Allocator>>
{
public:
using Self = TwoLevelHashSetTable;
using Base = TwoLevelHashTable<Key, TCell, Hash, Grower, Allocator, HashSetTable<Key, TCell, Hash, Grower, Allocator>>;
using Base::Base;
/// Writes its content in a way that it will be correctly read by HashSetTable.
/// Used by uniqExact to preserve backward compatibility.
void writeAsSingleLevel(DB::WriteBuffer & wb) const
{
DB::writeVarUInt(this->size(), wb);
bool zero_written = false;
for (size_t i = 0; i < Base::NUM_BUCKETS; ++i)
{
if (this->impls[i].hasZero())
{
if (zero_written)
throw DB::Exception(DB::ErrorCodes::LOGICAL_ERROR, "No more than one zero value expected");
this->impls[i].zeroValue()->write(wb);
zero_written = true;
}
}
static constexpr HashTableNoState state;
for (auto ptr = this->begin(); ptr != this->end(); ++ptr)
if (!ptr.getPtr()->isZero(state))
ptr.getPtr()->write(wb);
}
};
template <typename Key, typename Hash, typename TState = HashTableNoState>
struct HashSetCellWithSavedHash : public HashTableCell<Key, Hash, TState>
{
using Base = HashTableCell<Key, Hash, TState>;
size_t saved_hash;
HashSetCellWithSavedHash() : Base() {}
HashSetCellWithSavedHash(const Key & key_, const typename Base::State & state) : Base(key_, state) {}
bool keyEquals(const Key & key_) const { return bitEquals(this->key, key_); }
bool keyEquals(const Key & key_, size_t hash_) const { return saved_hash == hash_ && bitEquals(this->key, key_); }
bool keyEquals(const Key & key_, size_t hash_, const typename Base::State &) const { return keyEquals(key_, hash_); }
void setHash(size_t hash_value) { saved_hash = hash_value; }
size_t getHash(const Hash & /*hash_function*/) const { return saved_hash; }
};
template <
typename Key,
typename Hash = DefaultHash<Key>,
typename Grower = HashTableGrowerWithPrecalculation<>,
typename Allocator = HashTableAllocator>
using HashSet = HashSetTable<Key, HashTableCell<Key, Hash>, Hash, Grower, Allocator>;
template <
typename Key,
typename Hash = DefaultHash<Key>,
typename Grower = TwoLevelHashTableGrower<>,
typename Allocator = HashTableAllocator>
using TwoLevelHashSet = TwoLevelHashSetTable<Key, HashTableCell<Key, Hash>, Hash, Grower, Allocator>;
template <typename Key, typename Hash, size_t initial_size_degree>
using HashSetWithStackMemory = HashSet<
Key,
Hash,
HashTableGrower<initial_size_degree>,
HashTableAllocatorWithStackMemory<
(1ULL << initial_size_degree)
* sizeof(HashTableCell<Key, Hash>)>>;
template <
typename Key,
typename Hash = DefaultHash<Key>,
typename Grower = HashTableGrowerWithPrecalculation<>,
typename Allocator = HashTableAllocator>
using HashSetWithSavedHash = HashSetTable<Key, HashSetCellWithSavedHash<Key, Hash>, Hash, Grower, Allocator>;
template <typename Key, typename Hash, size_t initial_size_degree>
using HashSetWithSavedHashWithStackMemory = HashSetWithSavedHash<
Key,
Hash,
HashTableGrower<initial_size_degree>,
HashTableAllocatorWithStackMemory<
(1ULL << initial_size_degree)
* sizeof(HashSetCellWithSavedHash<Key, Hash>)>>;
|
