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