OXYGENHUB
◆ main openmsx / src / utils / hash_map.hh
3.7 KiB · C++ · last changed chore(): initial commit 1 month ago source blame history raw
1 
// hash_map
2 
//
3 
// Written by Wouter Vermaelen, based upon HashSet/HashMap
4 
// example code and ideas provided by Jacques Van Damme.
5
6 
#ifndef HASH_MAP_HH
7 
#define HASH_MAP_HH
8
9 
#include "hash_set.hh"
10
11 
namespace hash_set_impl {
12
13 
// Takes any (const or non-const) pair reference and returns a reference to
14 
// the first element of the pair.
15 
struct ExtractFirst {
16 
	template<typename Pair> [[nodiscard]] auto& operator()(Pair&& p) const { return p.first; }
17 
};
18
19 
} // namespace hash_set_impl
20
21
22 
// hash_map
23 
//
24 
// A hash-map implementation with an STL-like interface.
25 
//
26 
// It builds upon hash-set, see there for more details.
27 
template<typename Key,
28 
         typename Value,
29 
         typename Hasher = std::hash<Key>,
30 
         typename Equal = std::equal_to<>>
31 
class hash_map : public hash_set<std::pair<Key, Value>, hash_set_impl::ExtractFirst, Hasher, Equal>
32 
{
33 
	using BaseType = hash_set<std::pair<Key, Value>, hash_set_impl::ExtractFirst, Hasher, Equal>;
34 
public:
35 
	using key_type    = Key;
36 
	using mapped_type = Value;
37 
	using value_type  = std::pair<Key, Value>;
38 
	using       iterator = typename BaseType::      iterator;
39 
	using const_iterator = typename BaseType::const_iterator;
40
41 
	explicit hash_map(unsigned initialSize = 0,
42 
	         Hasher hasher_ = Hasher(),
43 
	         Equal equal_ = Equal())
44 
		: BaseType(initialSize, hash_set_impl::ExtractFirst(), hasher_, equal_)
45 
	{
46 
	}
47
48 
	explicit(false) hash_map(std::initializer_list<std::pair<Key, Value>> list)
49 
		: BaseType(list)
50 
	{
51 
	}
52
53 
	template<typename K>
54 
	[[nodiscard]] Value& operator[](K&& key)
55 
	{
56 
		auto it = this->find(key);
57 
		if (it == this->end()) {
58 
			auto p = this->insert(value_type(std::forward<K>(key), Value()));
59 
			it = p.first;
60 
		}
61 
		return it->second;
62 
	}
63
64 
	template<typename K, typename... Args>
65 
	std::pair<iterator, bool> try_emplace(K&& key, Args&& ...args)
66 
	{
67 
		auto hash = unsigned(this->hasher(key));
68 
		auto tableIdx = hash & this->allocMask;
69 
		auto primary = BaseType::invalidIndex;
70
71 
		if (this->elemCount > 0) {
72 
			primary = this->table[tableIdx];
73 
			for (auto elemIdx = primary; elemIdx != BaseType::invalidIndex; /**/) {
74 
				auto& elem = this->pool.get(elemIdx);
75 
				if ((elem.hash == hash) && this->equal(this->extract(elem.value), key)) {
76 
					// key already exists (possibly value is different)
77 
					return std::pair(iterator(this, elemIdx), false);
78 
				}
79 
				elemIdx = elem.nextIdx;
80 
			}
81 
		}
82
83 
		if (this->elemCount >= ((this->allocMask + 1) / 4 * 3)) {
84 
			this->grow();
85 
			tableIdx = hash & this->allocMask;
86 
			primary = this->table[tableIdx];
87 
		}
88
89 
		++this->elemCount;
90 
		auto poolIdx = this->pool.emplace(std::forward<K>(key), std::forward<Args>(args)...);
91 
		auto& poolElem = this->pool.get(poolIdx);
92 
		poolElem.hash = hash;
93 
		poolElem.nextIdx = primary;
94 
		this->table[tableIdx] = poolIdx;
95 
		return std::pair(iterator(this, poolIdx), true);
96 
	}
97
98 
	template<typename K, typename V>
99 
	std::pair<iterator, bool> insert_or_assign(K&& key, V&& value)
100 
	{
101 
		auto result = try_emplace(std::forward<K>(key), std::forward<V>(value));
102 
		if (!result.second) {
103 
			// was already present, also overwrite value
104 
			result.first->second = std::forward<V>(value);
105 
		}
106 
		return result;
107 
	}
108
109 
	template<typename K>
110 
	[[nodiscard]] bool contains(const K& k) const
111 
	{
112 
		return this->find(k) != this->end();
113 
	}
114 
};
115
116
117 
template<typename Key, typename Value, typename Hasher, typename Equal, typename Key2>
118 
[[nodiscard]] const Value* lookup(const hash_map<Key, Value, Hasher, Equal>& map, const Key2& key)
119 
{
120 
	auto it = map.find(key);
121 
	return (it != map.end()) ? &it->second : nullptr;
122 
}
123
124 
template<typename Key, typename Value, typename Hasher, typename Equal, typename Key2>
125 
[[nodiscard]] Value* lookup(hash_map<Key, Value, Hasher, Equal>& map, const Key2& key)
126 
{
127 
	auto it = map.find(key);
128 
	return (it != map.end()) ? &it->second : nullptr;
129 
}
130
131 
#endif