1#pragma once
2
3#include <type_traits>
4#include <Common/HashTable/HashSet.h>
5
6
7/** A hash table that allows you to clear the table in O(1).
8 * Even simpler than HashSet: Key and Mapped must be POD-types.
9 *
10 * Instead of this class, you could just use the pair (version, key) in the HashSet as the key
11 * but then the table would accumulate all the keys that it ever stored, and it was unreasonably growing.
12 * This class goes a step further and considers the keys with the old version empty in the hash table.
13 */
14
15
16struct ClearableHashSetState
17{
18 UInt32 version = 1;
19
20 /// Serialization, in binary and text form.
21 void write(DB::WriteBuffer & wb) const { DB::writeBinary(version, wb); }
22 void writeText(DB::WriteBuffer & wb) const { DB::writeText(version, wb); }
23
24 /// Deserialization, in binary and text form.
25 void read(DB::ReadBuffer & rb) { DB::readBinary(version, rb); }
26 void readText(DB::ReadBuffer & rb) { DB::readText(version, rb); }
27};
28
29
30template <typename Key, typename BaseCell>
31struct ClearableHashTableCell : public BaseCell
32{
33 using State = ClearableHashSetState;
34 using value_type = typename BaseCell::value_type;
35
36 UInt32 version;
37
38 bool isZero(const State & state) const { return version != state.version; }
39 static bool isZero(const Key & /*key*/, const State & /*state*/) { return false; }
40
41 /// Set the key value to zero.
42 void setZero() { version = 0; }
43
44 /// Do I need to store the zero key separately (that is, can a zero key be inserted into the hash table).
45 static constexpr bool need_zero_value_storage = false;
46
47 ClearableHashTableCell() {}
48 ClearableHashTableCell(const Key & key_, const State & state) : BaseCell(key_, state), version(state.version) {}
49};
50
51template
52<
53 typename Key,
54 typename Hash = DefaultHash<Key>,
55 typename Grower = HashTableGrower<>,
56 typename Allocator = HashTableAllocator
57>
58class ClearableHashSet : public HashTable<Key, ClearableHashTableCell<Key, HashTableCell<Key, Hash, ClearableHashSetState>>, Hash, Grower, Allocator>
59{
60public:
61 using Base = HashTable<Key, ClearableHashTableCell<Key, HashTableCell<Key, Hash, ClearableHashSetState>>, Hash, Grower, Allocator>;
62 using typename Base::LookupResult;
63
64 void clear()
65 {
66 ++this->version;
67 this->m_size = 0;
68 }
69};
70
71template
72<
73 typename Key,
74 typename Hash = DefaultHash<Key>,
75 typename Grower = HashTableGrower<>,
76 typename Allocator = HashTableAllocator
77>
78class ClearableHashSetWithSavedHash: public HashTable<Key, ClearableHashTableCell<Key, HashSetCellWithSavedHash<Key, Hash, ClearableHashSetState>>, Hash, Grower, Allocator>
79{
80public:
81 void clear()
82 {
83 ++this->version;
84 this->m_size = 0;
85 }
86};
87