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/Assertions.h>
30#include <AK/SinglyLinkedList.h>
31#include <AK/StdLibExtras.h>
32#include <AK/TemporaryChange.h>
33#include <AK/Traits.h>
34
35namespace AK {
36
37template<typename T, typename>
38class HashTable;
39
40template<typename HashTableType, typename ElementType, typename BucketIteratorType>
41class HashTableIterator {
42public:
43 bool operator!=(const HashTableIterator& other) const
44 {
45 if (m_is_end && other.m_is_end)
46 return false;
47 return &m_table != &other.m_table
48 || m_is_end != other.m_is_end
49 || m_bucket_index != other.m_bucket_index
50 || m_bucket_iterator != other.m_bucket_iterator;
51 }
52 bool operator==(const HashTableIterator& other) const { return !(*this != other); }
53 ElementType& operator*() { return *m_bucket_iterator; }
54 ElementType* operator->() { return m_bucket_iterator.operator->(); }
55 HashTableIterator& operator++()
56 {
57 skip_to_next();
58 return *this;
59 }
60
61 void skip_to_next()
62 {
63 while (!m_is_end) {
64 if (m_bucket_iterator.is_end()) {
65 ++m_bucket_index;
66 if (m_bucket_index >= m_table.capacity()) {
67 m_is_end = true;
68 return;
69 }
70 m_bucket_iterator = m_table.bucket(m_bucket_index).begin();
71 } else {
72 ++m_bucket_iterator;
73 }
74 if (!m_bucket_iterator.is_end())
75 return;
76 }
77 }
78
79private:
80 friend HashTableType;
81
82 explicit HashTableIterator(HashTableType& table, bool is_end, BucketIteratorType bucket_iterator = {}, size_t bucket_index = 0)
83 : m_table(table)
84 , m_bucket_index(bucket_index)
85 , m_is_end(is_end)
86 , m_bucket_iterator(bucket_iterator)
87 {
88 ASSERT(!table.m_clearing);
89 ASSERT(!table.m_rehashing);
90 if (!is_end && !m_table.is_empty() && m_bucket_iterator.is_end()) {
91 m_bucket_iterator = m_table.bucket(0).begin();
92 if (m_bucket_iterator.is_end())
93 skip_to_next();
94 }
95 }
96
97 HashTableType& m_table;
98 size_t m_bucket_index { 0 };
99 bool m_is_end { false };
100 BucketIteratorType m_bucket_iterator;
101};
102
103template<typename T, typename TraitsForT>
104class HashTable {
105private:
106 using Bucket = SinglyLinkedList<T>;
107
108public:
109 HashTable() {}
110 HashTable(const HashTable& other)
111 {
112 ensure_capacity(other.size());
113 for (auto& it : other)
114 set(it);
115 }
116 HashTable& operator=(const HashTable& other)
117 {
118 if (this != &other) {
119 clear();
120 ensure_capacity(other.size());
121 for (auto& it : other)
122 set(it);
123 }
124 return *this;
125 }
126 HashTable(HashTable&& other)
127 : m_buckets(other.m_buckets)
128 , m_size(other.m_size)
129 , m_capacity(other.m_capacity)
130 {
131 other.m_size = 0;
132 other.m_capacity = 0;
133 other.m_buckets = nullptr;
134 }
135 HashTable& operator=(HashTable&& other)
136 {
137 if (this != &other) {
138 clear();
139 m_buckets = other.m_buckets;
140 m_size = other.m_size;
141 m_capacity = other.m_capacity;
142 other.m_size = 0;
143 other.m_capacity = 0;
144 other.m_buckets = nullptr;
145 }
146 return *this;
147 }
148
149 ~HashTable() { clear(); }
150 bool is_empty() const { return !m_size; }
151 size_t size() const { return m_size; }
152 size_t capacity() const { return m_capacity; }
153
154 void ensure_capacity(size_t capacity)
155 {
156 ASSERT(capacity >= size());
157 rehash(capacity);
158 }
159
160 void set(const T&);
161 void set(T&&);
162 bool contains(const T&) const;
163 void clear();
164
165 using Iterator = HashTableIterator<HashTable, T, typename Bucket::Iterator>;
166 friend Iterator;
167 Iterator begin() { return Iterator(*this, is_empty()); }
168 Iterator end() { return Iterator(*this, true); }
169
170 using ConstIterator = HashTableIterator<const HashTable, const T, typename Bucket::ConstIterator>;
171 friend ConstIterator;
172 ConstIterator begin() const { return ConstIterator(*this, is_empty()); }
173 ConstIterator end() const { return ConstIterator(*this, true); }
174
175 template<typename Finder>
176 Iterator find(unsigned hash, Finder finder)
177 {
178 if (is_empty())
179 return end();
180 size_t bucket_index;
181 auto& bucket = lookup_with_hash(hash, &bucket_index);
182 auto bucket_iterator = bucket.find(finder);
183 if (bucket_iterator != bucket.end())
184 return Iterator(*this, false, bucket_iterator, bucket_index);
185 return end();
186 }
187
188 template<typename Finder>
189 ConstIterator find(unsigned hash, Finder finder) const
190 {
191 if (is_empty())
192 return end();
193 size_t bucket_index;
194 auto& bucket = lookup_with_hash(hash, &bucket_index);
195 auto bucket_iterator = bucket.find(finder);
196 if (bucket_iterator != bucket.end())
197 return ConstIterator(*this, false, bucket_iterator, bucket_index);
198 return end();
199 }
200
201 Iterator find(const T& value)
202 {
203 return find(TraitsForT::hash(value), [&](auto& other) { return TraitsForT::equals(value, other); });
204 }
205
206 ConstIterator find(const T& value) const
207 {
208 return find(TraitsForT::hash(value), [&](auto& other) { return TraitsForT::equals(value, other); });
209 }
210
211 void remove(const T& value)
212 {
213 auto it = find(value);
214 if (it != end())
215 remove(it);
216 }
217
218 void remove(Iterator);
219
220private:
221 Bucket& lookup(const T&, size_t* bucket_index = nullptr);
222 const Bucket& lookup(const T&, size_t* bucket_index = nullptr) const;
223
224 Bucket& lookup_with_hash(unsigned hash, size_t* bucket_index)
225 {
226 if (bucket_index)
227 *bucket_index = hash % m_capacity;
228 return m_buckets[hash % m_capacity];
229 }
230
231 const Bucket& lookup_with_hash(unsigned hash, size_t* bucket_index) const
232 {
233 if (bucket_index)
234 *bucket_index = hash % m_capacity;
235 return m_buckets[hash % m_capacity];
236 }
237
238 void rehash(size_t capacity);
239 void insert(const T&);
240 void insert(T&&);
241
242 Bucket& bucket(size_t index) { return m_buckets[index]; }
243 const Bucket& bucket(size_t index) const { return m_buckets[index]; }
244
245 Bucket* m_buckets { nullptr };
246
247 size_t m_size { 0 };
248 size_t m_capacity { 0 };
249 bool m_clearing { false };
250 bool m_rehashing { false };
251};
252
253template<typename T, typename TraitsForT>
254void HashTable<T, TraitsForT>::set(T&& value)
255{
256 if (!m_capacity)
257 rehash(1);
258 auto& bucket = lookup(value);
259 for (auto& e : bucket) {
260 if (TraitsForT::equals(e, value)) {
261 e = move(value);
262 return;
263 }
264 }
265 if (size() >= capacity()) {
266 rehash(size() + 1);
267 insert(move(value));
268 } else {
269 bucket.append(move(value));
270 }
271 m_size++;
272}
273
274template<typename T, typename TraitsForT>
275void HashTable<T, TraitsForT>::set(const T& value)
276{
277 if (!m_capacity)
278 rehash(1);
279 auto& bucket = lookup(value);
280 for (auto& e : bucket) {
281 if (TraitsForT::equals(e, value)) {
282 e = value;
283 return;
284 }
285 }
286 if (size() >= capacity()) {
287 rehash(size() + 1);
288 insert(value);
289 } else {
290 bucket.append(value);
291 }
292 m_size++;
293}
294
295template<typename T, typename TraitsForT>
296void HashTable<T, TraitsForT>::rehash(size_t new_capacity)
297{
298 TemporaryChange<bool> change(m_rehashing, true);
299 new_capacity *= 2;
300 auto* new_buckets = new Bucket[new_capacity];
301 auto* old_buckets = m_buckets;
302 size_t old_capacity = m_capacity;
303 m_buckets = new_buckets;
304 m_capacity = new_capacity;
305
306 for (size_t i = 0; i < old_capacity; ++i) {
307 for (auto& value : old_buckets[i]) {
308 insert(move(value));
309 }
310 }
311
312 delete[] old_buckets;
313}
314
315template<typename T, typename TraitsForT>
316void HashTable<T, TraitsForT>::clear()
317{
318 TemporaryChange<bool> change(m_clearing, true);
319 if (m_buckets) {
320 delete[] m_buckets;
321 m_buckets = nullptr;
322 }
323 m_capacity = 0;
324 m_size = 0;
325}
326
327template<typename T, typename TraitsForT>
328void HashTable<T, TraitsForT>::insert(T&& value)
329{
330 auto& bucket = lookup(value);
331 bucket.append(move(value));
332}
333
334template<typename T, typename TraitsForT>
335void HashTable<T, TraitsForT>::insert(const T& value)
336{
337 auto& bucket = lookup(value);
338 bucket.append(value);
339}
340
341template<typename T, typename TraitsForT>
342bool HashTable<T, TraitsForT>::contains(const T& value) const
343{
344 if (is_empty())
345 return false;
346 auto& bucket = lookup(value);
347 for (auto& e : bucket) {
348 if (TraitsForT::equals(e, value))
349 return true;
350 }
351 return false;
352}
353
354template<typename T, typename TraitsForT>
355void HashTable<T, TraitsForT>::remove(Iterator it)
356{
357 ASSERT(!is_empty());
358 m_buckets[it.m_bucket_index].remove(it.m_bucket_iterator);
359 --m_size;
360}
361
362template<typename T, typename TraitsForT>
363auto HashTable<T, TraitsForT>::lookup(const T& value, size_t* bucket_index) -> Bucket&
364{
365 unsigned hash = TraitsForT::hash(value);
366 if (bucket_index)
367 *bucket_index = hash % m_capacity;
368 return m_buckets[hash % m_capacity];
369}
370
371template<typename T, typename TraitsForT>
372auto HashTable<T, TraitsForT>::lookup(const T& value, size_t* bucket_index) const -> const Bucket&
373{
374 unsigned hash = TraitsForT::hash(value);
375 if (bucket_index)
376 *bucket_index = hash % m_capacity;
377 return m_buckets[hash % m_capacity];
378}
379
380}
381
382using AK::HashTable;