1#pragma once
2
3#include <Common/HashTable/HashMap.h>
4#include <Common/HashTable/HashTableAllocator.h>
5#include <Common/HashTable/StringHashTable.h>
6
7template <typename Key, typename TMapped>
8struct 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
20template <typename TMapped>
21struct 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
37template <typename TMapped>
38struct 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
54template <typename TMapped>
55struct 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
67template <typename TMapped, typename Allocator>
68struct 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
77template <typename TMapped, typename Allocator = HashTableAllocator>
78class StringHashMap : public StringHashTable<StringHashMapSubMaps<TMapped, Allocator>>
79{
80public:
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