1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
/*
* Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
*
* SPDX-License-Identifier: BSD-2-Clause
*/
#pragma once
#include <AK/HashTable.h>
#include <AK/Optional.h>
#include <AK/Vector.h>
// NOTE: We can't include <initializer_list> during the toolchain bootstrap,
// since it's part of libstdc++, and libstdc++ depends on LibC.
// For this reason, we don't support HashMap(initializer_list) in LibC.
#ifndef SERENITY_LIBC_BUILD
# include <initializer_list>
#endif
namespace AK {
template<typename K, typename V, typename KeyTraits, bool IsOrdered>
class HashMap {
private:
struct Entry {
K key;
V value;
};
struct EntryTraits {
static unsigned hash(const Entry& entry) { return KeyTraits::hash(entry.key); }
static bool equals(const Entry& a, const Entry& b) { return KeyTraits::equals(a.key, b.key); }
};
public:
using KeyType = K;
using ValueType = V;
HashMap() = default;
#ifndef SERENITY_LIBC_BUILD
HashMap(std::initializer_list<Entry> list)
{
ensure_capacity(list.size());
for (auto& item : list)
set(item.key, item.value);
}
#endif
[[nodiscard]] bool is_empty() const
{
return m_table.is_empty();
}
[[nodiscard]] size_t size() const { return m_table.size(); }
[[nodiscard]] size_t capacity() const { return m_table.capacity(); }
void clear() { m_table.clear(); }
HashSetResult set(const K& key, const V& value) { return m_table.set({ key, value }); }
HashSetResult set(const K& key, V&& value) { return m_table.set({ key, move(value) }); }
bool remove(const K& key)
{
auto it = find(key);
if (it != end()) {
m_table.remove(it);
return true;
}
return false;
}
using HashTableType = HashTable<Entry, EntryTraits, IsOrdered>;
using IteratorType = typename HashTableType::Iterator;
using ConstIteratorType = typename HashTableType::ConstIterator;
[[nodiscard]] IteratorType begin() { return m_table.begin(); }
[[nodiscard]] IteratorType end() { return m_table.end(); }
[[nodiscard]] IteratorType find(const K& key)
{
return m_table.find(KeyTraits::hash(key), [&](auto& entry) { return KeyTraits::equals(key, entry.key); });
}
template<typename TUnaryPredicate>
[[nodiscard]] IteratorType find(unsigned hash, TUnaryPredicate predicate)
{
return m_table.find(hash, predicate);
}
[[nodiscard]] ConstIteratorType begin() const { return m_table.begin(); }
[[nodiscard]] ConstIteratorType end() const { return m_table.end(); }
[[nodiscard]] ConstIteratorType find(const K& key) const
{
return m_table.find(KeyTraits::hash(key), [&](auto& entry) { return KeyTraits::equals(key, entry.key); });
}
template<typename TUnaryPredicate>
[[nodiscard]] ConstIteratorType find(unsigned hash, TUnaryPredicate predicate) const
{
return m_table.find(hash, predicate);
}
void ensure_capacity(size_t capacity) { m_table.ensure_capacity(capacity); }
Optional<typename Traits<V>::PeekType> get(const K& key) const requires(!IsPointer<typename Traits<V>::PeekType>)
{
auto it = find(key);
if (it == end())
return {};
return (*it).value;
}
Optional<typename Traits<V>::ConstPeekType> get(const K& key) const requires(IsPointer<typename Traits<V>::PeekType>)
{
auto it = find(key);
if (it == end())
return {};
return (*it).value;
}
Optional<typename Traits<V>::PeekType> get(const K& key) requires(!IsConst<typename Traits<V>::PeekType>)
{
auto it = find(key);
if (it == end())
return {};
return (*it).value;
}
[[nodiscard]] bool contains(const K& key) const
{
return find(key) != end();
}
void remove(IteratorType it)
{
m_table.remove(it);
}
V& ensure(const K& key)
{
auto it = find(key);
if (it == end())
set(key, V());
return find(key)->value;
}
[[nodiscard]] Vector<K> keys() const
{
Vector<K> list;
list.ensure_capacity(size());
for (auto& it : *this)
list.unchecked_append(it.key);
return list;
}
private:
HashTableType m_table;
};
}
using AK::HashMap;
using AK::OrderedHashMap;
|
