1// SPDX-License-Identifier: GPL-3.0-or-later
2
3#include "mos/lib/sync/spinlock.hpp"
4
5#include <mos/allocator.hpp>
6#include <mos/lib/structures/hashmap.hpp>
7#include <mos/moslib_global.hpp>
8#include <mos_stdlib.hpp>
9#include <mos_string.hpp>
10
11#define HASHMAP_MAGIC MOS_FOURCC('H', 'M', 'a', 'p')
12
13struct hashmap_entry_t : mos::NamedType<"Hashmap.Entry">
14{
15 ptr_t key;
16 void *value;
17 hashmap_entry_t *next;
18};
19
20void hashmap_init(hashmap_t *map, size_t capacity, hashmap_hash_t hash_func, hashmap_key_compare_t compare_func)
21{
22 MOS_LIB_ASSERT(map);
23 if (map->magic == HASHMAP_MAGIC)
24 {
25 mos_panic("hashmap_init: hashmap %p is already initialized", (void *) map);
26 return;
27 }
28 memzero(s: map, n: sizeof(hashmap_t));
29 map->magic = HASHMAP_MAGIC;
30 map->entries = kcalloc<hashmap_entry_t *>(n_members: capacity);
31 map->capacity = capacity;
32 map->size = 0;
33 map->hash_func = hash_func;
34 map->key_compare_func = compare_func;
35}
36
37/**
38 * @brief Deinitialize a hashmap.
39 * @pre The hashmap must be initialized.
40 * @pre The hashmap should be empty, otherwise the entries will be leaked.
41 * @warning This function does not free the hashmap itself, nor does it free the keys or values, but only the internal data structures.
42 *
43 * @param map The hashmap to deinitialize.
44 */
45void hashmap_deinit(hashmap_t *map)
46{
47 MOS_LIB_ASSERT_X(map && map->magic == HASHMAP_MAGIC, "hashmap_put: hashmap %p is not initialized", (void *) map);
48 spinlock_acquire(&map->lock);
49 map->magic = 0;
50 for (size_t i = 0; i < map->capacity; i++)
51 {
52 hashmap_entry_t *entry = map->entries[i];
53 while (entry != NULL)
54 {
55 hashmap_entry_t *next = entry->next;
56 delete entry;
57 entry = next;
58 }
59 }
60 kfree(ptr: map->entries);
61 spinlock_release(&map->lock);
62}
63
64void *hashmap_put(hashmap_t *map, uintn key, void *value)
65{
66 MOS_LIB_ASSERT_X(map && map->magic == HASHMAP_MAGIC, "hashmap_put: hashmap %p is not initialized", (void *) map);
67 spinlock_acquire(&map->lock);
68 size_t index = map->hash_func(key).hash % map->capacity;
69 hashmap_entry_t *entry = map->entries[index];
70 while (entry != NULL)
71 {
72 if (map->key_compare_func(entry->key, key))
73 {
74 // key already exists, replace value
75 auto old_value = entry->value;
76 entry->value = value;
77 spinlock_release(&map->lock);
78 return old_value;
79 }
80 entry = entry->next;
81 }
82 entry = mos::create<hashmap_entry_t>();
83 entry->key = key;
84 entry->value = value;
85 entry->next = map->entries[index];
86 map->entries[index] = entry;
87 map->size++;
88 spinlock_release(&map->lock);
89 return NULL;
90}
91
92void *hashmap_get(hashmap_t *map, uintn key)
93{
94 MOS_LIB_ASSERT_X(map && map->magic == HASHMAP_MAGIC, "hashmap_put: hashmap %p is not initialized", (void *) map);
95 spinlock_acquire(&map->lock);
96 size_t index = map->hash_func(key).hash % map->capacity;
97 hashmap_entry_t *entry = map->entries[index];
98 while (entry != NULL)
99 {
100 if (map->key_compare_func(entry->key, key))
101 {
102 const auto value = entry->value;
103 spinlock_release(&map->lock);
104 return value;
105 }
106 entry = entry->next;
107 }
108
109 spinlock_release(&map->lock);
110 return NULL;
111}
112
113void *hashmap_remove(hashmap_t *map, uintn key)
114{
115 MOS_LIB_ASSERT_X(map && map->magic == HASHMAP_MAGIC, "hashmap_put: hashmap %p is not initialized", (void *) map);
116 spinlock_acquire(&map->lock);
117 size_t index = map->hash_func(key).hash % map->capacity;
118 hashmap_entry_t *entry = map->entries[index];
119 hashmap_entry_t *prev = NULL;
120 while (entry != NULL)
121 {
122 if (map->key_compare_func(entry->key, key))
123 {
124 if (prev == NULL)
125 map->entries[index] = entry->next;
126 else
127 prev->next = entry->next;
128 void *value = entry->value;
129 delete entry;
130 map->size--;
131 spinlock_release(&map->lock);
132 return value;
133 }
134 prev = entry;
135 entry = entry->next;
136 }
137
138 spinlock_release(&map->lock);
139 return NULL;
140}
141
142void hashmap_foreach(hashmap_t *map, hashmap_foreach_func_t func, void *data)
143{
144 MOS_LIB_ASSERT_X(map && map->magic == HASHMAP_MAGIC, "hashmap_put: hashmap %p is not initialized", (void *) map);
145 for (size_t i = 0; i < map->capacity; i++)
146 {
147 hashmap_entry_t *entry = map->entries[i];
148 while (entry != NULL)
149 {
150 if (!func(entry->key, entry->value, data))
151 return;
152 entry = entry->next;
153 }
154 }
155}
156