jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice, this
9 * list of conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
21 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
22 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
23 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#pragma once
28
29#include <AK/HashTable.h>
30#include <AK/Optional.h>
31#include <AK/StdLibExtras.h>
32#include <AK/Vector.h>
33
34namespace AK {
35
36template<typename K, typename V, typename KeyTraits>
37class HashMap {
38private:
39 struct Entry {
40 K key;
41 V value;
42 };
43
44 struct EntryTraits {
45 static unsigned hash(const Entry& entry) { return KeyTraits::hash(entry.key); }
46 static bool equals(const Entry& a, const Entry& b) { return KeyTraits::equals(a.key, b.key); }
47 };
48
49public:
50 HashMap() {}
51
52 bool is_empty() const { return m_table.is_empty(); }
53 size_t size() const { return m_table.size(); }
54 size_t capacity() const { return m_table.capacity(); }
55 void clear() { m_table.clear(); }
56
57 void set(const K& key, const V& value) { m_table.set({ key, value }); }
58 void set(const K& key, V&& value) { m_table.set({ key, move(value) }); }
59 void remove(const K& key)
60 {
61 auto it = find(key);
62 if (it != end())
63 m_table.remove(it);
64 }
65 void remove_one_randomly() { m_table.remove(m_table.begin()); }
66
67 typedef HashTable<Entry, EntryTraits> HashTableType;
68 typedef typename HashTableType::Iterator IteratorType;
69 typedef typename HashTableType::ConstIterator ConstIteratorType;
70
71 IteratorType begin() { return m_table.begin(); }
72 IteratorType end() { return m_table.end(); }
73 IteratorType find(const K& key)
74 {
75 return m_table.find(KeyTraits::hash(key), [&](auto& entry) { return KeyTraits::equals(key, entry.key); });
76 }
77 template<typename Finder>
78 IteratorType find(unsigned hash, Finder finder)
79 {
80 return m_table.find(hash, finder);
81 }
82
83 ConstIteratorType begin() const { return m_table.begin(); }
84 ConstIteratorType end() const { return m_table.end(); }
85 ConstIteratorType find(const K& key) const
86 {
87 return m_table.find(KeyTraits::hash(key), [&](auto& entry) { return KeyTraits::equals(key, entry.key); });
88 }
89 template<typename Finder>
90 ConstIteratorType find(unsigned hash, Finder finder) const
91 {
92 return m_table.find(hash, finder);
93 }
94
95 void ensure_capacity(size_t capacity) { m_table.ensure_capacity(capacity); }
96
97 Optional<typename Traits<V>::PeekType> get(const K& key) const
98 {
99 auto it = find(key);
100 if (it == end())
101 return {};
102 return (*it).value;
103 }
104
105 bool contains(const K& key) const
106 {
107 return find(key) != end();
108 }
109
110 void remove(IteratorType it)
111 {
112 m_table.remove(it);
113 }
114
115 V& ensure(const K& key)
116 {
117 auto it = find(key);
118 if (it == end())
119 set(key, V());
120 return find(key)->value;
121 }
122
123 Vector<K> keys() const
124 {
125 Vector<K> list;
126 list.ensure_capacity(size());
127 for (auto& it : *this)
128 list.unchecked_append(it.key);
129 return list;
130 }
131
132private:
133 HashTableType m_table;
134};
135
136}
137
138using AK::HashMap;