1#pragma once
2
3#include <Common/HashTable/FixedHashTable.h>
4#include <Common/HashTable/HashMap.h>
5
6
7template <typename Key, typename TMapped, typename TState = HashTableNoState>
8struct FixedHashMapCell
9{
10 using Mapped = TMapped;
11 using State = TState;
12
13 using value_type = PairNoInit<Key, Mapped>;
14 using mapped_type = TMapped;
15
16 bool full;
17 Mapped mapped;
18
19 FixedHashMapCell() {}
20 FixedHashMapCell(const Key &, const State &) : full(true) {}
21 FixedHashMapCell(const value_type & value_, const State &) : full(true), mapped(value_.second) {}
22
23 const VoidKey getKey() const { return {}; }
24 Mapped & getMapped() { return mapped; }
25 const Mapped & getMapped() const { return mapped; }
26
27 bool isZero(const State &) const { return !full; }
28 void setZero() { full = false; }
29
30 /// Similar to FixedHashSetCell except that we need to contain a pointer to the Mapped field.
31 /// Note that we have to assemble a continuous layout for the value_type on each call of getValue().
32 struct CellExt
33 {
34 CellExt() {}
35 CellExt(Key && key_, const FixedHashMapCell * ptr_) : key(key_), ptr(const_cast<FixedHashMapCell *>(ptr_)) {}
36 void update(Key && key_, const FixedHashMapCell * ptr_)
37 {
38 key = key_;
39 ptr = const_cast<FixedHashMapCell *>(ptr_);
40 }
41 Key key;
42 FixedHashMapCell * ptr;
43
44 const Key & getKey() const { return key; }
45 Mapped & getMapped() { return ptr->mapped; }
46 const Mapped & getMapped() const { return ptr->mapped; }
47 const value_type getValue() const { return {key, ptr->mapped}; }
48 };
49};
50
51template <typename Key, typename Mapped, typename Cell = FixedHashMapCell<Key, Mapped>, typename Allocator = HashTableAllocator>
52class FixedHashMap : public FixedHashTable<Key, Cell, Allocator>
53{
54public:
55 using Base = FixedHashTable<Key, Cell, Allocator>;
56 using Self = FixedHashMap;
57 using LookupResult = typename Base::LookupResult;
58
59 using Base::Base;
60
61 template <typename Func>
62 void ALWAYS_INLINE mergeToViaEmplace(Self & that, Func && func)
63 {
64 for (auto it = this->begin(), end = this->end(); it != end; ++it)
65 {
66 typename Self::LookupResult res_it;
67 bool inserted;
68 that.emplace(it->getKey(), res_it, inserted, it.getHash());
69 func(res_it->getMapped(), it->getMapped(), inserted);
70 }
71 }
72
73 template <typename Func>
74 void ALWAYS_INLINE mergeToViaFind(Self & that, Func && func)
75 {
76 for (auto it = this->begin(), end = this->end(); it != end; ++it)
77 {
78 auto res_it = that.find(it->getKey(), it.getHash());
79 if (!res_it)
80 func(it->getMapped(), it->getMapped(), false);
81 else
82 func(res_it->getMapped(), it->getMapped(), true);
83 }
84 }
85
86 template <typename Func>
87 void forEachValue(Func && func)
88 {
89 for (auto & v : *this)
90 func(v.getKey(), v.getMapped());
91 }
92
93 template <typename Func>
94 void forEachMapped(Func && func)
95 {
96 for (auto & v : *this)
97 func(v.getMapped());
98 }
99
100 Mapped & ALWAYS_INLINE operator[](const Key & x)
101 {
102 LookupResult it;
103 bool inserted;
104 this->emplace(x, it, inserted);
105 if (inserted)
106 new (&it->getMapped()) Mapped();
107
108 return it->getMapped();
109 }
110};
111