1 | #pragma once |
2 | |
3 | #include <Common/HashTable/FixedHashTable.h> |
4 | #include <Common/HashTable/HashMap.h> |
5 | |
6 | |
7 | template <typename Key, typename TMapped, typename TState = HashTableNoState> |
8 | struct 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 | |
51 | template <typename Key, typename Mapped, typename Cell = FixedHashMapCell<Key, Mapped>, typename Allocator = HashTableAllocator> |
52 | class FixedHashMap : public FixedHashTable<Key, Cell, Allocator> |
53 | { |
54 | public: |
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 | |