1 | #pragma once |
2 | |
3 | #include <Common/HashTable/HashMap.h> |
4 | #include <Common/HashTable/HashTableAllocator.h> |
5 | #include <Common/HashTable/StringHashTable.h> |
6 | |
7 | template <typename Key, typename TMapped> |
8 | struct StringHashMapCell : public HashMapCell<Key, TMapped, StringHashTableHash, HashTableNoState> |
9 | { |
10 | using Base = HashMapCell<Key, TMapped, StringHashTableHash, HashTableNoState>; |
11 | using value_type = typename Base::value_type; |
12 | using Base::Base; |
13 | static constexpr bool need_zero_value_storage = false; |
14 | // external |
15 | const StringRef getKey() const { return toStringRef(this->value.first); } |
16 | // internal |
17 | static const Key & getKey(const value_type & value_) { return value_.first; } |
18 | }; |
19 | |
20 | template <typename TMapped> |
21 | struct StringHashMapCell<StringKey16, TMapped> : public HashMapCell<StringKey16, TMapped, StringHashTableHash, HashTableNoState> |
22 | { |
23 | using Base = HashMapCell<StringKey16, TMapped, StringHashTableHash, HashTableNoState>; |
24 | using value_type = typename Base::value_type; |
25 | using Base::Base; |
26 | static constexpr bool need_zero_value_storage = false; |
27 | bool isZero(const HashTableNoState & state) const { return isZero(this->value.first, state); } |
28 | // Assuming String does not contain zero bytes. NOTE: Cannot be used in serialized method |
29 | static bool isZero(const StringKey16 & key, const HashTableNoState & /*state*/) { return key.low == 0; } |
30 | void setZero() { this->value.first.low = 0; } |
31 | // external |
32 | const StringRef getKey() const { return toStringRef(this->value.first); } |
33 | // internal |
34 | static const StringKey16 & getKey(const value_type & value_) { return value_.first; } |
35 | }; |
36 | |
37 | template <typename TMapped> |
38 | struct StringHashMapCell<StringKey24, TMapped> : public HashMapCell<StringKey24, TMapped, StringHashTableHash, HashTableNoState> |
39 | { |
40 | using Base = HashMapCell<StringKey24, TMapped, StringHashTableHash, HashTableNoState>; |
41 | using value_type = typename Base::value_type; |
42 | using Base::Base; |
43 | static constexpr bool need_zero_value_storage = false; |
44 | bool isZero(const HashTableNoState & state) const { return isZero(this->value.first, state); } |
45 | // Assuming String does not contain zero bytes. NOTE: Cannot be used in serialized method |
46 | static bool isZero(const StringKey24 & key, const HashTableNoState & /*state*/) { return key.a == 0; } |
47 | void setZero() { this->value.first.a = 0; } |
48 | // external |
49 | const StringRef getKey() const { return toStringRef(this->value.first); } |
50 | // internal |
51 | static const StringKey24 & getKey(const value_type & value_) { return value_.first; } |
52 | }; |
53 | |
54 | template <typename TMapped> |
55 | struct StringHashMapCell<StringRef, TMapped> : public HashMapCellWithSavedHash<StringRef, TMapped, StringHashTableHash, HashTableNoState> |
56 | { |
57 | using Base = HashMapCellWithSavedHash<StringRef, TMapped, StringHashTableHash, HashTableNoState>; |
58 | using value_type = typename Base::value_type; |
59 | using Base::Base; |
60 | static constexpr bool need_zero_value_storage = false; |
61 | // external |
62 | using Base::getKey; |
63 | // internal |
64 | static const StringRef & getKey(const value_type & value_) { return value_.first; } |
65 | }; |
66 | |
67 | template <typename TMapped, typename Allocator> |
68 | struct StringHashMapSubMaps |
69 | { |
70 | using T0 = StringHashTableEmpty<StringHashMapCell<StringRef, TMapped>>; |
71 | using T1 = HashMapTable<StringKey8, StringHashMapCell<StringKey8, TMapped>, StringHashTableHash, StringHashTableGrower<>, Allocator>; |
72 | using T2 = HashMapTable<StringKey16, StringHashMapCell<StringKey16, TMapped>, StringHashTableHash, StringHashTableGrower<>, Allocator>; |
73 | using T3 = HashMapTable<StringKey24, StringHashMapCell<StringKey24, TMapped>, StringHashTableHash, StringHashTableGrower<>, Allocator>; |
74 | using Ts = HashMapTable<StringRef, StringHashMapCell<StringRef, TMapped>, StringHashTableHash, StringHashTableGrower<>, Allocator>; |
75 | }; |
76 | |
77 | template <typename TMapped, typename Allocator = HashTableAllocator> |
78 | class StringHashMap : public StringHashTable<StringHashMapSubMaps<TMapped, Allocator>> |
79 | { |
80 | public: |
81 | using Key = StringRef; |
82 | using Base = StringHashTable<StringHashMapSubMaps<TMapped, Allocator>>; |
83 | using Self = StringHashMap; |
84 | using LookupResult = typename Base::LookupResult; |
85 | |
86 | using Base::Base; |
87 | |
88 | /// Merge every cell's value of current map into the destination map. |
89 | /// Func should have signature void(Mapped & dst, Mapped & src, bool emplaced). |
90 | /// Each filled cell in current map will invoke func once. If that map doesn't |
91 | /// have a key equals to the given cell, a new cell gets emplaced into that map, |
92 | /// and func is invoked with the third argument emplaced set to true. Otherwise |
93 | /// emplaced is set to false. |
94 | template <typename Func> |
95 | void ALWAYS_INLINE mergeToViaEmplace(Self & that, Func && func) |
96 | { |
97 | if (this->m0.hasZero() && that.m0.hasZero()) |
98 | func(that.m0.zeroValue()->getMapped(), this->m0.zeroValue()->getMapped(), false); |
99 | else if (this->m0.hasZero()) |
100 | { |
101 | that.m0.setHasZero(); |
102 | func(that.m0.zeroValue()->getMapped(), this->m0.zeroValue()->getMapped(), true); |
103 | } |
104 | this->m1.mergeToViaEmplace(that.m1, func); |
105 | this->m2.mergeToViaEmplace(that.m2, func); |
106 | this->m3.mergeToViaEmplace(that.m3, func); |
107 | this->ms.mergeToViaEmplace(that.ms, func); |
108 | } |
109 | |
110 | /// Merge every cell's value of current map into the destination map via find. |
111 | /// Func should have signature void(Mapped & dst, Mapped & src, bool exist). |
112 | /// Each filled cell in current map will invoke func once. If that map doesn't |
113 | /// have a key equals to the given cell, func is invoked with the third argument |
114 | /// exist set to false. Otherwise exist is set to true. |
115 | template <typename Func> |
116 | void ALWAYS_INLINE mergeToViaFind(Self & that, Func && func) |
117 | { |
118 | if (this->m0.size() && that.m0.size()) |
119 | func(that.m0.zeroValue()->getMapped(), this->m0.zeroValue()->getMapped(), true); |
120 | else if (this->m0.size()) |
121 | func(this->m0.zeroValue()->getMapped(), this->m0.zeroValue()->getMapped(), false); |
122 | this->m1.mergeToViaFind(that.m1, func); |
123 | this->m2.mergeToViaFind(that.m2, func); |
124 | this->m3.mergeToViaFind(that.m3, func); |
125 | this->ms.mergeToViaFind(that.ms, func); |
126 | } |
127 | |
128 | TMapped & ALWAYS_INLINE operator[](const Key & x) |
129 | { |
130 | LookupResult it; |
131 | bool inserted; |
132 | this->emplace(x, it, inserted); |
133 | if (inserted) |
134 | new (&it->getMapped()) TMapped(); |
135 | |
136 | return it->getMapped(); |
137 | } |
138 | |
139 | template <typename Func> |
140 | void ALWAYS_INLINE forEachValue(Func && func) |
141 | { |
142 | if (this->m0.size()) |
143 | { |
144 | func(StringRef{}, this->m0.zeroValue()->getMapped()); |
145 | } |
146 | |
147 | for (auto & v : this->m1) |
148 | { |
149 | func(v.getKey(), v.getMapped()); |
150 | } |
151 | |
152 | for (auto & v : this->m2) |
153 | { |
154 | func(v.getKey(), v.getMapped()); |
155 | } |
156 | |
157 | for (auto & v : this->m3) |
158 | { |
159 | func(v.getKey(), v.getMapped()); |
160 | } |
161 | |
162 | for (auto & v : this->ms) |
163 | { |
164 | func(v.getKey(), v.getMapped()); |
165 | } |
166 | } |
167 | |
168 | template <typename Func> |
169 | void ALWAYS_INLINE forEachMapped(Func && func) |
170 | { |
171 | if (this->m0.size()) |
172 | func(this->m0.zeroValue()->getMapped()); |
173 | for (auto & v : this->m1) |
174 | func(v.getMapped()); |
175 | for (auto & v : this->m2) |
176 | func(v.getMapped()); |
177 | for (auto & v : this->m3) |
178 | func(v.getMapped()); |
179 | for (auto & v : this->ms) |
180 | func(v.getMapped()); |
181 | } |
182 | }; |
183 | |