1 /*
2 * Copyright (c) 2022 Meta
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 */
6
7 #include <errno.h>
8 #include <stdbool.h>
9 #include <stddef.h>
10 #include <stdint.h>
11 #include <stdlib.h>
12 #include <string.h>
13
14 #include <zephyr/sys/hash_map.h>
15 #include <zephyr/sys/hash_map_oa_lp.h>
16 #include <zephyr/sys/util.h>
17
18 enum bucket_state {
19 UNUSED,
20 USED,
21 TOMBSTONE,
22 };
23
24 struct oalp_entry {
25 uint64_t key;
26 uint64_t value;
27 enum bucket_state state;
28 };
29
30 BUILD_ASSERT(offsetof(struct sys_hashmap_oa_lp_data, buckets) ==
31 offsetof(struct sys_hashmap_data, buckets));
32 BUILD_ASSERT(offsetof(struct sys_hashmap_oa_lp_data, n_buckets) ==
33 offsetof(struct sys_hashmap_data, n_buckets));
34 BUILD_ASSERT(offsetof(struct sys_hashmap_oa_lp_data, size) ==
35 offsetof(struct sys_hashmap_data, size));
36
sys_hashmap_oa_lp_find(const struct sys_hashmap * map,uint64_t key,bool used_ok,bool unused_ok,bool tombstone_ok)37 static struct oalp_entry *sys_hashmap_oa_lp_find(const struct sys_hashmap *map, uint64_t key,
38 bool used_ok, bool unused_ok, bool tombstone_ok)
39 {
40 struct oalp_entry *entry = NULL;
41 const size_t n_buckets = map->data->n_buckets;
42 uint32_t hash = map->hash_func(&key, sizeof(key));
43 struct oalp_entry *const buckets = map->data->buckets;
44
45 for (size_t i = 0, j = hash; i < n_buckets; ++i, ++j) {
46 j &= (n_buckets - 1);
47 __ASSERT_NO_MSG(j < n_buckets);
48
49 entry = &buckets[j];
50
51 switch (entry->state) {
52 case USED:
53 if (used_ok && entry->key == key) {
54 return entry;
55 }
56 break;
57 case UNUSED:
58 if (unused_ok) {
59 return entry;
60 }
61 break;
62 case TOMBSTONE:
63 if (tombstone_ok) {
64 return entry;
65 }
66 break;
67 default:
68 __ASSERT(false, "Invalid entry state. Memory has been corrupted");
69 break;
70 }
71 }
72
73 return NULL;
74 }
75
sys_hashmap_oa_lp_insert_no_rehash(struct sys_hashmap * map,uint64_t key,uint64_t value,uint64_t * old_value)76 static int sys_hashmap_oa_lp_insert_no_rehash(struct sys_hashmap *map, uint64_t key, uint64_t value,
77 uint64_t *old_value)
78 {
79 int ret;
80 struct oalp_entry *entry = NULL;
81 struct sys_hashmap_oa_lp_data *data = (struct sys_hashmap_oa_lp_data *)map->data;
82
83 entry = sys_hashmap_oa_lp_find(map, key, true, true, true);
84 __ASSERT_NO_MSG(entry != NULL);
85
86 switch (entry->state) {
87 case UNUSED:
88 ++data->size;
89 ret = 1;
90 break;
91 case TOMBSTONE:
92 --data->n_tombstones;
93 ++data->size;
94 ret = 0;
95 break;
96 case USED:
97 default:
98 ret = 0;
99 break;
100 }
101
102 if (old_value != NULL) {
103 *old_value = entry->value;
104 }
105
106 entry->state = USED;
107 entry->key = key;
108 entry->value = value;
109
110 return ret;
111 }
112
sys_hashmap_oa_lp_rehash(struct sys_hashmap * map,bool grow)113 static int sys_hashmap_oa_lp_rehash(struct sys_hashmap *map, bool grow)
114 {
115 size_t old_size;
116 size_t old_n_buckets;
117 size_t new_n_buckets = 0;
118 struct oalp_entry *entry;
119 struct oalp_entry *old_buckets;
120 struct oalp_entry *new_buckets;
121 struct sys_hashmap_oa_lp_data *data = (struct sys_hashmap_oa_lp_data *)map->data;
122
123 if (!sys_hashmap_should_rehash(map, grow, data->n_tombstones, &new_n_buckets)) {
124 return 0;
125 }
126
127 if (map->data->size != SIZE_MAX && map->data->size == map->config->max_size) {
128 return -ENOSPC;
129 }
130
131 /* extract all entries from the hashmap */
132 old_size = data->size;
133 old_n_buckets = data->n_buckets;
134 old_buckets = (struct oalp_entry *)data->buckets;
135
136 new_buckets = (struct oalp_entry *)map->alloc_func(NULL, new_n_buckets * sizeof(*entry));
137 if (new_buckets == NULL && new_n_buckets != 0) {
138 return -ENOMEM;
139 }
140
141 if (new_buckets != NULL) {
142 /* ensure all buckets are empty / initialized */
143 memset(new_buckets, 0, new_n_buckets * sizeof(*new_buckets));
144 }
145
146 data->size = 0;
147 data->buckets = new_buckets;
148 data->n_buckets = new_n_buckets;
149
150 /* re-insert all entries into the hashmap */
151 for (size_t i = 0, j = 0; i < old_n_buckets && j < old_size; ++i) {
152 entry = &old_buckets[i];
153
154 if (entry->state == USED) {
155 sys_hashmap_oa_lp_insert_no_rehash(map, entry->key, entry->value, NULL);
156 ++j;
157 }
158 }
159
160 /* free the old Hashmap */
161 map->alloc_func(old_buckets, 0);
162
163 return 0;
164 }
165
sys_hashmap_oa_lp_iter_next(struct sys_hashmap_iterator * it)166 static void sys_hashmap_oa_lp_iter_next(struct sys_hashmap_iterator *it)
167 {
168 size_t i;
169 struct oalp_entry *entry;
170 const struct sys_hashmap *map = (const struct sys_hashmap *)it->map;
171 struct oalp_entry *buckets = map->data->buckets;
172
173 __ASSERT(it->size == map->data->size, "Concurrent modification!");
174 __ASSERT(sys_hashmap_iterator_has_next(it), "Attempt to access beyond current bound!");
175
176 if (it->pos == 0) {
177 it->state = buckets;
178 }
179
180 i = (struct oalp_entry *)it->state - buckets;
181 __ASSERT(i < map->data->n_buckets, "Invalid iterator state %p", it->state);
182
183 for (; i < map->data->n_buckets; ++i) {
184 entry = &buckets[i];
185 if (entry->state == USED) {
186 it->state = &buckets[i + 1];
187 it->key = entry->key;
188 it->value = entry->value;
189 ++it->pos;
190 return;
191 }
192 }
193
194 __ASSERT(false, "Entire Hashmap traversed and no entry was found");
195 }
196
197 /*
198 * Open Addressing / Linear Probe Hashmap API
199 */
200
sys_hashmap_oa_lp_iter(const struct sys_hashmap * map,struct sys_hashmap_iterator * it)201 static void sys_hashmap_oa_lp_iter(const struct sys_hashmap *map, struct sys_hashmap_iterator *it)
202 {
203 it->map = map;
204 it->next = sys_hashmap_oa_lp_iter_next;
205 it->pos = 0;
206 *((size_t *)&it->size) = map->data->size;
207 }
208
sys_hashmap_oa_lp_clear(struct sys_hashmap * map,sys_hashmap_callback_t cb,void * cookie)209 static void sys_hashmap_oa_lp_clear(struct sys_hashmap *map, sys_hashmap_callback_t cb,
210 void *cookie)
211 {
212 struct oalp_entry *entry;
213 struct sys_hashmap_oa_lp_data *data = (struct sys_hashmap_oa_lp_data *)map->data;
214 struct oalp_entry *buckets = data->buckets;
215
216 for (size_t i = 0, j = 0; cb != NULL && i < data->n_buckets && j < data->size; ++i) {
217 entry = &buckets[i];
218 if (entry->state == USED) {
219 cb(entry->key, entry->value, cookie);
220 ++j;
221 }
222 }
223
224 if (data->buckets != NULL) {
225 map->alloc_func(data->buckets, 0);
226 data->buckets = NULL;
227 }
228
229 data->n_buckets = 0;
230 data->size = 0;
231 data->n_tombstones = 0;
232 }
233
sys_hashmap_oa_lp_insert(struct sys_hashmap * map,uint64_t key,uint64_t value,uint64_t * old_value)234 static inline int sys_hashmap_oa_lp_insert(struct sys_hashmap *map, uint64_t key, uint64_t value,
235 uint64_t *old_value)
236 {
237 int ret;
238
239 ret = sys_hashmap_oa_lp_rehash(map, true);
240 if (ret < 0) {
241 return ret;
242 }
243
244 return sys_hashmap_oa_lp_insert_no_rehash(map, key, value, old_value);
245 }
246
sys_hashmap_oa_lp_remove(struct sys_hashmap * map,uint64_t key,uint64_t * value)247 static bool sys_hashmap_oa_lp_remove(struct sys_hashmap *map, uint64_t key, uint64_t *value)
248 {
249 struct oalp_entry *entry;
250 struct sys_hashmap_oa_lp_data *data = (struct sys_hashmap_oa_lp_data *)map->data;
251
252 entry = sys_hashmap_oa_lp_find(map, key, true, true, false);
253 if (entry == NULL || entry->state == UNUSED) {
254 return false;
255 }
256
257 if (value != NULL) {
258 *value = entry->value;
259 }
260
261 entry->state = TOMBSTONE;
262 --data->size;
263 ++data->n_tombstones;
264
265 /* ignore a possible -ENOMEM since the table will remain intact */
266 (void)sys_hashmap_oa_lp_rehash(map, false);
267
268 return true;
269 }
270
sys_hashmap_oa_lp_get(const struct sys_hashmap * map,uint64_t key,uint64_t * value)271 static bool sys_hashmap_oa_lp_get(const struct sys_hashmap *map, uint64_t key, uint64_t *value)
272 {
273 struct oalp_entry *entry;
274
275 entry = sys_hashmap_oa_lp_find(map, key, true, true, false);
276 if (entry == NULL || entry->state == UNUSED) {
277 return false;
278 }
279
280 if (value != NULL) {
281 *value = entry->value;
282 }
283
284 return true;
285 }
286
287 const struct sys_hashmap_api sys_hashmap_oa_lp_api = {
288 .iter = sys_hashmap_oa_lp_iter,
289 .clear = sys_hashmap_oa_lp_clear,
290 .insert = sys_hashmap_oa_lp_insert,
291 .remove = sys_hashmap_oa_lp_remove,
292 .get = sys_hashmap_oa_lp_get,
293 };
294
