1 /*
2 * Copyright (c) 2023 Institute of Parallel And Distributed Systems (IPADS), Shanghai Jiao Tong University (SJTU)
3 * Licensed under the Mulan PSL v2.
4 * You can use this software according to the terms and conditions of the Mulan PSL v2.
5 * You may obtain a copy of Mulan PSL v2 at:
6 * http://license.coscl.org.cn/MulanPSL2
7 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR
8 * IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR
9 * PURPOSE.
10 * See the Mulan PSL v2 for more details.
11 */
12 #ifndef COMMON_HASHTABLE_H
13 #define COMMON_HASHTABLE_H
14
15 #include <common/types.h>
16 #include <common/list.h>
17 #ifdef CHCORE
18 #include <mm/kmalloc.h>
19 #endif
20
21 struct htable {
22 struct hlist_head *buckets;
23 int size;
24 };
25
init_htable(struct htable * ht,int size)26 static inline void init_htable(struct htable *ht, int size)
27 {
28 ht->size = size;
29 ht->buckets = kzalloc(sizeof(*ht->buckets) * size);
30 }
31
htable_add(struct htable * ht,u32 key,struct hlist_node * node)32 static inline void htable_add(struct htable *ht, u32 key,
33 struct hlist_node *node)
34 {
35 hlist_add(node, &ht->buckets[key % ht->size]);
36 }
37
htable_del(struct hlist_node * node)38 static inline void htable_del(struct hlist_node *node)
39 {
40 hlist_del(node);
41 }
42
htable_get_bucket(struct htable * ht,u32 key)43 static inline struct hlist_head *htable_get_bucket(struct htable *ht, u32 key)
44 {
45 return &ht->buckets[key % ht->size];
46 }
47
htable_empty(struct htable * ht)48 static inline bool htable_empty(struct htable *ht)
49 {
50 int i;
51
52 for (i = 0; i < ht->size; ++i)
53 if (!hlist_empty(&ht->buckets[i]))
54 return false;
55 return true;
56 }
57
htable_free(struct htable * ht)58 static inline int htable_free(struct htable *ht)
59 {
60 if (!ht || !ht->buckets) {
61 WARN("trying to free an empty htable");
62 return -EINVAL;
63 }
64
65 // we don't free individual buckets (i.e., the hlist) since their nodes
66 // a not allocated by htable_xxx or hlist_xxx
67
68 kfree(ht->buckets);
69
70 return 0;
71 }
72
73 #define for_each_in_htable(elem, b, field, ht) \
74 for ((b) = 0, (elem) = NULL; (elem) == NULL && (b) < (ht)->size; ++(b)) \
75 for_each_in_hlist (elem, field, &(ht)->buckets[b])
76
77 #define for_each_in_htable_safe(elem, tmp, b, field, ht) \
78 for ((b) = 0, (elem) = NULL; (elem) == NULL && (b) < (ht)->size; ++(b)) \
79 for_each_in_hlist_safe (elem, tmp, field, &(ht)->buckets[b])
80
81 #endif /* COMMON_HASHTABLE_H */