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 | |
16 | struct 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 | |
30 | template <typename Key, typename BaseCell> |
31 | struct 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 | |
51 | template |
52 | < |
53 | typename Key, |
54 | typename Hash = DefaultHash<Key>, |
55 | typename Grower = HashTableGrower<>, |
56 | typename Allocator = HashTableAllocator |
57 | > |
58 | class ClearableHashSet : public HashTable<Key, ClearableHashTableCell<Key, HashTableCell<Key, Hash, ClearableHashSetState>>, Hash, Grower, Allocator> |
59 | { |
60 | public: |
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 | |
71 | template |
72 | < |
73 | typename Key, |
74 | typename Hash = DefaultHash<Key>, |
75 | typename Grower = HashTableGrower<>, |
76 | typename Allocator = HashTableAllocator |
77 | > |
78 | class ClearableHashSetWithSavedHash: public HashTable<Key, ClearableHashTableCell<Key, HashSetCellWithSavedHash<Key, Hash, ClearableHashSetState>>, Hash, Grower, Allocator> |
79 | { |
80 | public: |
81 | void clear() |
82 | { |
83 | ++this->version; |
84 | this->m_size = 0; |
85 | } |
86 | }; |
87 | |