2 * Copyright (C) 2024-2026 David C. Manuelda (StormBytePP)
4 * This is the base for StormByte Suite libraries.
6 * StormByte original source is dual-licensed:
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)
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>).
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.
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.
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.
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>.
37 * SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-StormByte-Commercial
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;
50 const size_type slot = BucketSlot(m_node->Code, m_map->m_bucket_count);
51 m_node = m_map->NextBucket(slot);
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);
63 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
64 UnorderedMap<K, V, Hash, KeyEqual>::UnorderedMap() noexcept = default;
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;
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)
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;
86 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
87 UnorderedMap<K, V, Hash, KeyEqual>::~UnorderedMap() noexcept { Destroy(); }
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) {
92 UnorderedMap replacement(other);
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) {
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;
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() {
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);
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);
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);
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();
149 m_buckets[index] = nullptr;
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);
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));
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)
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;
178 node = new (storage) Node{nullptr, 0, value_type(std::forward<Args>(args)...)};
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();
188 return insert_result(iterator(existing, this), false);
193 node->Entry.~value_type();
197 return insert_result(iterator(node, this), true);
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)...));
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);
218 return emplace(key, std::move(mapped));
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();
229 next = NextBucket(slot);
230 return iterator(next, this);
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);
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));
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);
253 return extract(found);
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()};
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);
268 Node* taken = node.m_node;
270 taken->Next = nullptr;
272 node.m_node = nullptr;
273 result.position = iterator(taken, this);
274 result.inserted = true;
278 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
279 void UnorderedMap<K, V, Hash, KeyEqual>::merge(UnorderedMap& other) {
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) {
290 node->Next = nullptr;
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);
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));
312 throw OutOfBoundsError();
313 return node->Entry.second;
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));
320 throw OutOfBoundsError();
321 return node->Entry.second;
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;
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);
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);
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;
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;
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 {
353 for (Node* node = m_buckets[index]; node != nullptr; node = node->Next)
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)
362 return BucketSlot(m_hash(key), m_bucket_count);
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)
369 return static_cast<float>(m_size) / static_cast<float>(m_bucket_count);
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;
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;
390 if (previous != nullptr)
391 Heap::Free(previous);
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);
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)
405 for (const value_type& entry : *this) {
406 const_iterator found = other.find(entry.first);
407 if (found == other.end() || !(found->second == entry.second))
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 {
417 size_type rounded = 8;
418 while (rounded < count)
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) {
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;
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);
444 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
445 void UnorderedMap<K, V, Hash, KeyEqual>::Destroy() noexcept {
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)
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))
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];
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];
479 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
480 void UnorderedMap<K, V, Hash, KeyEqual>::Link(Node* node) {
482 const size_type slot = BucketSlot(node->Code, m_bucket_count);
483 node->Next = m_buckets[slot];
484 m_buckets[slot] = node;
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;
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) {
505 if (static_cast<float>(m_size + extra) > m_max_load * static_cast<float>(m_bucket_count))
506 rehash(m_bucket_count * 2);