StormByte 3.0.0
C++26 foundation of the StormByte suite
Loading...
Searching...
No Matches
unordered_map.txx
Go to the documentation of this file.
1/*
2 * Copyright (C) 2024-2026 David C. Manuelda (StormBytePP)
3 *
4 * This is the base for StormByte Suite libraries.
5 *
6 * StormByte original source is dual-licensed:
7 *
8 * 1. GNU Lesser General Public License v3.0 (or later)
9 * You may redistribute and/or modify this file under the terms of the
10 * GNU Lesser General Public License as published by the Free Software
11 * Foundation, either version 3 of the License, or (at your option)
12 * any later version.
13 *
14 * 2. Commercial license
15 * Alternatively, this file may be used under the terms of a commercial
16 * license agreement with the copyright holder
17 * (David C. Manuelda <StormByte@gmail.com>).
18 *
19 * Both licenses apply only to original StormByte source in this repository.
20 * They do not cover other StormByte modules or any third-party material
21 * shipped with this repository (including everything under thirdparty/),
22 * which remains under its own license.
23 *
24 * Neither license grants any patent rights. Any patent licenses required
25 * to use this software or third-party components must be obtained separately
26 * from the patent holders.
27 *
28 * StormByte is distributed in the hope that it will be useful,
29 * but WITHOUT ANY WARRANTY; without even the implied warranty of
30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 * GNU Lesser General Public License for more details.
32 *
33 * You should have received a copy of the GNU Lesser General Public License
34 * version 3 along with StormByte. If not, see
35 * <https://www.gnu.org/licenses/lgpl-3.0.html>.
36 *
37 * SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-StormByte-Commercial
38 */
39
40#pragma once
41
42namespace StormByte::Safe {
43 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
44 template<bool IsConst>
45 UnorderedMap<K, V, Hash, KeyEqual>::BasicIterator<IsConst>& UnorderedMap<K, V, Hash, KeyEqual>::BasicIterator<IsConst>::operator++() noexcept {
46 if (m_node->Next != nullptr) {
47 m_node = m_node->Next;
48 return *this;
49 }
50 const size_type slot = BucketSlot(m_node->Code, m_map->m_bucket_count);
51 m_node = m_map->NextBucket(slot);
52 return *this;
53 }
54
55 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
56 template<bool IsConst>
57 UnorderedMap<K, V, Hash, KeyEqual>::BasicIterator<IsConst> UnorderedMap<K, V, Hash, KeyEqual>::BasicIterator<IsConst>::operator++(int) noexcept {
58 BasicIterator previous(*this);
59 ++(*this);
60 return previous;
61 }
62
63 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
64 UnorderedMap<K, V, Hash, KeyEqual>::UnorderedMap() noexcept = default;
65
66 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
67 UnorderedMap<K, V, Hash, KeyEqual>::UnorderedMap(size_type buckets, const Hash& hash, const KeyEqual& equal): m_hash(hash), m_equal(equal) {
68 const size_type count = BucketCount(buckets);
69 m_buckets = AllocateBuckets(count);
70 m_bucket_count = count;
71 }
72
73 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
74 UnorderedMap<K, V, Hash, KeyEqual>::UnorderedMap(const UnorderedMap& other): UnorderedMap(other.m_bucket_count, other.m_hash, other.m_equal) {
75 for (const value_type& entry : other)
76 insert(entry);
77 }
78
79 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
80 UnorderedMap<K, V, Hash, KeyEqual>::UnorderedMap(UnorderedMap&& other) noexcept: m_buckets(other.m_buckets), m_bucket_count(other.m_bucket_count), m_size(other.m_size), m_max_load(other.m_max_load), m_hash(std::move(other.m_hash)), m_equal(std::move(other.m_equal)) {
81 other.m_buckets = nullptr;
82 other.m_bucket_count = 0;
83 other.m_size = 0;
84 }
85
86 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
87 UnorderedMap<K, V, Hash, KeyEqual>::~UnorderedMap() noexcept { Destroy(); }
88
89 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
90 UnorderedMap<K, V, Hash, KeyEqual>& UnorderedMap<K, V, Hash, KeyEqual>::operator=(const UnorderedMap& other) {
91 if (this != &other) {
92 UnorderedMap replacement(other);
93 swap(replacement);
94 }
95 return *this;
96 }
97
98 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
99 UnorderedMap<K, V, Hash, KeyEqual>& UnorderedMap<K, V, Hash, KeyEqual>::operator=(UnorderedMap&& other) noexcept {
100 if (this != &other) {
101 Destroy();
102 m_buckets = other.m_buckets;
103 m_bucket_count = other.m_bucket_count;
104 m_size = other.m_size;
105 m_max_load = other.m_max_load;
106 m_hash = std::move(other.m_hash);
107 m_equal = std::move(other.m_equal);
108 other.m_buckets = nullptr;
109 other.m_bucket_count = 0;
110 other.m_size = 0;
111 }
112 return *this;
113 }
114
115 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
116 UnorderedMap<K, V, Hash, KeyEqual>::UnorderedMap(std::initializer_list<value_type> values): UnorderedMap() {
117 insert(values);
118 }
119
120 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
121 UnorderedMap<K, V, Hash, KeyEqual>& UnorderedMap<K, V, Hash, KeyEqual>::operator=(std::initializer_list<value_type> values) {
122 UnorderedMap replacement(m_bucket_count, m_hash, m_equal);
123 replacement.max_load_factor(m_max_load);
124 replacement.insert(values);
125 swap(replacement);
126 return *this;
127 }
128
129 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
130 UnorderedMap<K, V, Hash, KeyEqual>::iterator UnorderedMap<K, V, Hash, KeyEqual>::begin() noexcept {
131 return iterator(FirstNode(), this);
132 }
133
134 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
135 UnorderedMap<K, V, Hash, KeyEqual>::const_iterator UnorderedMap<K, V, Hash, KeyEqual>::begin() const noexcept {
136 return const_iterator(FirstNode(), this);
137 }
138
139 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
140 void UnorderedMap<K, V, Hash, KeyEqual>::clear() noexcept {
141 for (size_type index = 0; index < m_bucket_count; ++index) {
142 Node* node = m_buckets[index];
143 while (node != nullptr) {
144 Node* next = node->Next;
145 node->Entry.~value_type();
146 Heap::Free(node);
147 node = next;
148 }
149 m_buckets[index] = nullptr;
150 }
151 m_size = 0;
152 }
153
154 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
155 UnorderedMap<K, V, Hash, KeyEqual>::insert_result UnorderedMap<K, V, Hash, KeyEqual>::insert(const value_type& value) {
156 return emplace(value);
157 }
158
159 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
160 UnorderedMap<K, V, Hash, KeyEqual>::insert_result UnorderedMap<K, V, Hash, KeyEqual>::insert(value_type&& value) {
161 return emplace(std::move(value));
162 }
163
164 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
165 void UnorderedMap<K, V, Hash, KeyEqual>::insert(std::initializer_list<value_type> values) {
166 for (const value_type& value : values)
167 insert(value);
168 }
169
170 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
171 template<class... Args>
172 UnorderedMap<K, V, Hash, KeyEqual>::insert_result UnorderedMap<K, V, Hash, KeyEqual>::emplace(Args&&... args) {
173 Node* storage = static_cast<Node*>(Heap::Allocate(sizeof(Node)));
174 if (storage == nullptr)
175 throw AllocationError();
176 Node* node = nullptr;
177 try {
178 node = new (storage) Node{nullptr, 0, value_type(std::forward<Args>(args)...)};
179 } catch (...) {
180 Heap::Free(storage);
181 throw;
182 }
183 node->Code = m_hash(node->Entry.first);
184 Node* existing = FindNode(node->Entry.first, node->Code);
185 if (existing != nullptr) {
186 node->Entry.~value_type();
187 Heap::Free(node);
188 return insert_result(iterator(existing, this), false);
189 }
190 try {
191 Link(node);
192 } catch (...) {
193 node->Entry.~value_type();
194 Heap::Free(node);
195 throw;
196 }
197 return insert_result(iterator(node, this), true);
198 }
199
200 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
201 template<class... Args>
202 UnorderedMap<K, V, Hash, KeyEqual>::insert_result UnorderedMap<K, V, Hash, KeyEqual>::try_emplace(const K& key, Args&&... args) {
203 const std::size_t code = m_hash(key);
204 Node* existing = FindNode(key, code);
205 if (existing != nullptr)
206 return insert_result(iterator(existing, this), false);
207 return emplace(key, V(std::forward<Args>(args)...));
208 }
209
210 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
211 UnorderedMap<K, V, Hash, KeyEqual>::insert_result UnorderedMap<K, V, Hash, KeyEqual>::insert_or_assign(const K& key, V mapped) {
212 const std::size_t code = m_hash(key);
213 Node* existing = FindNode(key, code);
214 if (existing != nullptr) {
215 existing->Entry.second = std::move(mapped);
216 return insert_result(iterator(existing, this), false);
217 }
218 return emplace(key, std::move(mapped));
219 }
220
221 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
222 UnorderedMap<K, V, Hash, KeyEqual>::iterator UnorderedMap<K, V, Hash, KeyEqual>::erase(const_iterator position) {
223 Node* node = const_cast<Node*>(position.m_node);
224 Node* next = Unlink(node);
225 const size_type slot = BucketSlot(node->Code, m_bucket_count);
226 node->Entry.~value_type();
227 Heap::Free(node);
228 if (next == nullptr)
229 next = NextBucket(slot);
230 return iterator(next, this);
231 }
232
233 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
234 UnorderedMap<K, V, Hash, KeyEqual>::size_type UnorderedMap<K, V, Hash, KeyEqual>::erase(const K& key) {
235 const_iterator found = find(key);
236 if (found == end())
237 return 0;
238 erase(found);
239 return 1;
240 }
241
242 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
243 UnorderedMap<K, V, Hash, KeyEqual>::node_type UnorderedMap<K, V, Hash, KeyEqual>::extract(const_iterator position) {
244 Unlink(const_cast<Node*>(position.m_node));
245 return node_type(const_cast<Node*>(position.m_node));
246 }
247
248 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
249 UnorderedMap<K, V, Hash, KeyEqual>::node_type UnorderedMap<K, V, Hash, KeyEqual>::extract(const K& key) {
250 const_iterator found = find(key);
251 if (found == end())
252 return node_type();
253 return extract(found);
254 }
255
256 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
257 UnorderedMap<K, V, Hash, KeyEqual>::insert_return_type UnorderedMap<K, V, Hash, KeyEqual>::insert(node_type&& node) {
258 insert_return_type result{end(), false, node_type()};
259 if (node.empty())
260 return result;
261 const std::size_t code = m_hash(node.m_node->Entry.first);
262 Node* existing = FindNode(node.m_node->Entry.first, code);
263 if (existing != nullptr) {
264 result.position = iterator(existing, this);
265 result.node = std::move(node);
266 return result;
267 }
268 Node* taken = node.m_node;
269 taken->Code = code;
270 taken->Next = nullptr;
271 Link(taken);
272 node.m_node = nullptr;
273 result.position = iterator(taken, this);
274 result.inserted = true;
275 return result;
276 }
277
278 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
279 void UnorderedMap<K, V, Hash, KeyEqual>::merge(UnorderedMap& other) {
280 if (this == &other)
281 return;
282 for (size_type index = 0; index < other.m_bucket_count; ++index) {
283 Node* node = other.m_buckets[index];
284 while (node != nullptr) {
285 Node* next = node->Next;
286 const std::size_t code = m_hash(node->Entry.first);
287 if (FindNode(node->Entry.first, code) == nullptr) {
288 other.Unlink(node);
289 node->Code = code;
290 node->Next = nullptr;
291 Link(node);
292 }
293 node = next;
294 }
295 }
296 }
297
298 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
299 void UnorderedMap<K, V, Hash, KeyEqual>::swap(UnorderedMap& other) noexcept {
300 std::swap(m_buckets, other.m_buckets);
301 std::swap(m_bucket_count, other.m_bucket_count);
302 std::swap(m_size, other.m_size);
303 std::swap(m_max_load, other.m_max_load);
304 std::swap(m_hash, other.m_hash);
305 std::swap(m_equal, other.m_equal);
306 }
307
308 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
309 V& UnorderedMap<K, V, Hash, KeyEqual>::at(const K& key) {
310 Node* node = FindNode(key, m_hash(key));
311 if (node == nullptr)
312 throw OutOfBoundsError();
313 return node->Entry.second;
314 }
315
316 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
317 const V& UnorderedMap<K, V, Hash, KeyEqual>::at(const K& key) const {
318 Node* node = FindNode(key, m_hash(key));
319 if (node == nullptr)
320 throw OutOfBoundsError();
321 return node->Entry.second;
322 }
323
324 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
325 V& UnorderedMap<K, V, Hash, KeyEqual>::operator[](const K& key) {
326 insert_result result = try_emplace(key);
327 return result.first->second;
328 }
329
330 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
331 UnorderedMap<K, V, Hash, KeyEqual>::iterator UnorderedMap<K, V, Hash, KeyEqual>::find(const K& key) {
332 return iterator(FindNode(key, m_hash(key)), this);
333 }
334
335 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
336 UnorderedMap<K, V, Hash, KeyEqual>::const_iterator UnorderedMap<K, V, Hash, KeyEqual>::find(const K& key) const {
337 return const_iterator(FindNode(key, m_hash(key)), this);
338 }
339
340 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
341 UnorderedMap<K, V, Hash, KeyEqual>::size_type UnorderedMap<K, V, Hash, KeyEqual>::count(const K& key) const {
342 return contains(key) ? 1 : 0;
343 }
344
345 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
346 bool UnorderedMap<K, V, Hash, KeyEqual>::contains(const K& key) const {
347 return FindNode(key, m_hash(key)) != nullptr;
348 }
349
350 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
351 UnorderedMap<K, V, Hash, KeyEqual>::size_type UnorderedMap<K, V, Hash, KeyEqual>::bucket_size(size_type index) const {
352 size_type count = 0;
353 for (Node* node = m_buckets[index]; node != nullptr; node = node->Next)
354 ++count;
355 return count;
356 }
357
358 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
359 UnorderedMap<K, V, Hash, KeyEqual>::size_type UnorderedMap<K, V, Hash, KeyEqual>::bucket(const K& key) const {
360 if (m_bucket_count == 0)
361 return 0;
362 return BucketSlot(m_hash(key), m_bucket_count);
363 }
364
365 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
366 float UnorderedMap<K, V, Hash, KeyEqual>::load_factor() const noexcept {
367 if (m_bucket_count == 0)
368 return 0.0f;
369 return static_cast<float>(m_size) / static_cast<float>(m_bucket_count);
370 }
371
372 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
373 void UnorderedMap<K, V, Hash, KeyEqual>::rehash(size_type buckets) {
374 const size_type count = BucketCount(buckets == 0 ? Size{1} : buckets);
375 Node** fresh = AllocateBuckets(count);
376 Node** previous = m_buckets;
377 const size_type previous_count = m_bucket_count;
378 m_buckets = fresh;
379 m_bucket_count = count;
380 for (size_type index = 0; index < previous_count; ++index) {
381 Node* node = previous[index];
382 while (node != nullptr) {
383 Node* next = node->Next;
384 const size_type slot = BucketSlot(node->Code, count);
385 node->Next = m_buckets[slot];
386 m_buckets[slot] = node;
387 node = next;
388 }
389 }
390 if (previous != nullptr)
391 Heap::Free(previous);
392 }
393
394 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
395 void UnorderedMap<K, V, Hash, KeyEqual>::reserve(size_type count) {
396 const float needed = static_cast<float>(count) / m_max_load;
397 if (needed > static_cast<float>(m_bucket_count))
398 rehash(Size{static_cast<std::size_t>(needed)} + 1);
399 }
400
401 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
402 bool UnorderedMap<K, V, Hash, KeyEqual>::operator==(const UnorderedMap& other) const {
403 if (m_size != other.m_size)
404 return false;
405 for (const value_type& entry : *this) {
406 const_iterator found = other.find(entry.first);
407 if (found == other.end() || !(found->second == entry.second))
408 return false;
409 }
410 return true;
411 }
412
413 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
414 UnorderedMap<K, V, Hash, KeyEqual>::size_type UnorderedMap<K, V, Hash, KeyEqual>::BucketCount(size_type count) noexcept {
415 if (count == 0)
416 return 0;
417 size_type rounded = 8;
418 while (rounded < count)
419 rounded *= 2;
420 return rounded;
421 }
422
423 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
424 UnorderedMap<K, V, Hash, KeyEqual>::Node** UnorderedMap<K, V, Hash, KeyEqual>::AllocateBuckets(size_type count) {
425 if (count == 0)
426 return nullptr;
427 void* block = Heap::Allocate(sizeof(Node*) * count);
428 if (block == nullptr)
429 throw AllocationError();
430 Node** buckets = static_cast<Node**>(block);
431 for (size_type index = 0; index < count; ++index)
432 buckets[index] = nullptr;
433 return buckets;
434 }
435
436 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
437 void UnorderedMap<K, V, Hash, KeyEqual>::FreeBuckets() noexcept {
438 if (m_buckets != nullptr)
439 Heap::Free(m_buckets);
440 m_buckets = nullptr;
441 m_bucket_count = 0;
442 }
443
444 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
445 void UnorderedMap<K, V, Hash, KeyEqual>::Destroy() noexcept {
446 clear();
447 FreeBuckets();
448 }
449
450 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
451 UnorderedMap<K, V, Hash, KeyEqual>::Node* UnorderedMap<K, V, Hash, KeyEqual>::FindNode(const K& key, std::size_t code) const noexcept {
452 if (m_bucket_count == 0)
453 return nullptr;
454 for (Node* node = m_buckets[static_cast<std::size_t>(BucketSlot(code, m_bucket_count))]; node != nullptr; node = node->Next) {
455 if (node->Code == code && m_equal(node->Entry.first, key))
456 return node;
457 }
458 return nullptr;
459 }
460
461 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
462 UnorderedMap<K, V, Hash, KeyEqual>::Node* UnorderedMap<K, V, Hash, KeyEqual>::FirstNode() const noexcept {
463 for (size_type index = 0; index < m_bucket_count; ++index) {
464 if (m_buckets[index] != nullptr)
465 return m_buckets[index];
466 }
467 return nullptr;
468 }
469
470 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
471 UnorderedMap<K, V, Hash, KeyEqual>::Node* UnorderedMap<K, V, Hash, KeyEqual>::NextBucket(size_type slot) const noexcept {
472 for (size_type index = slot + 1; index < m_bucket_count; ++index) {
473 if (m_buckets[index] != nullptr)
474 return m_buckets[index];
475 }
476 return nullptr;
477 }
478
479 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
480 void UnorderedMap<K, V, Hash, KeyEqual>::Link(Node* node) {
481 Ensure(1);
482 const size_type slot = BucketSlot(node->Code, m_bucket_count);
483 node->Next = m_buckets[slot];
484 m_buckets[slot] = node;
485 ++m_size;
486 }
487
488 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
489 UnorderedMap<K, V, Hash, KeyEqual>::Node* UnorderedMap<K, V, Hash, KeyEqual>::Unlink(Node* node) noexcept {
490 const size_type slot = BucketSlot(node->Code, m_bucket_count);
491 Node** link = &m_buckets[slot];
492 while (*link != node)
493 link = &(*link)->Next;
494 *link = node->Next;
495 --m_size;
496 return node->Next;
497 }
498
499 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
500 void UnorderedMap<K, V, Hash, KeyEqual>::Ensure(size_type extra) {
501 if (m_bucket_count == 0) {
502 rehash(8);
503 return;
504 }
505 if (static_cast<float>(m_size + extra) > m_max_load * static_cast<float>(m_bucket_count))
506 rehash(m_bucket_count * 2);
507 }
508}