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 #ifdef CHCORE
13 #include <mm/kmalloc.h>
14 #include <common/kprint.h>
15 #include <common/macro.h>
16 #include <common/radix.h>
17 #endif
18 #include <common/errno.h>
19
new_radix(void)20 struct radix *new_radix(void)
21 {
22 struct radix *radix;
23
24 radix = kzalloc(sizeof(*radix));
25 BUG_ON(!radix);
26
27 return radix;
28 }
29
init_radix(struct radix * radix)30 void init_radix(struct radix *radix)
31 {
32 radix->root = kzalloc(sizeof(*radix->root));
33 BUG_ON(!radix->root);
34 radix->value_deleter = NULL;
35
36 lock_init(&radix->radix_lock);
37 }
38
init_radix_w_deleter(struct radix * radix,void (* value_deleter)(void *))39 void init_radix_w_deleter(struct radix *radix, void (*value_deleter)(void *))
40 {
41 init_radix(radix);
42 radix->value_deleter = value_deleter;
43 }
44
new_radix_node(void)45 static struct radix_node *new_radix_node(void)
46 {
47 struct radix_node *n = kzalloc(sizeof(struct radix_node));
48
49 if (!n) {
50 kwarn(
51 "run-out-memoroy: cannot allocate radix_new_node whose size is %ld\n",
52 sizeof(struct radix_node));
53 return ERR_PTR(-ENOMEM);
54 }
55
56 return n;
57 }
58
59 #ifndef FBINFER
radix_add(struct radix * radix,u64 key,void * value)60 int radix_add(struct radix *radix, u64 key, void *value)
61 {
62 int ret;
63 struct radix_node *node;
64 struct radix_node *new;
65 u16 index[RADIX_LEVELS];
66 int i;
67 int k;
68
69 lock(&radix->radix_lock);
70 if (!radix->root) {
71 new = new_radix_node();
72 if (IS_ERR(new)) {
73 ret = -ENOMEM;
74 goto fail_out;
75 }
76 radix->root = new;
77 }
78 node = radix->root;
79
80 /* calculate index for each level */
81 for (i = 0; i < RADIX_LEVELS; ++i) {
82 index[i] = key & RADIX_NODE_MASK;
83 key >>= RADIX_NODE_BITS;
84 }
85
86 /* the intermediate levels */
87 for (i = RADIX_LEVELS - 1; i > 0; --i) {
88 k = index[i];
89 if (!node->children[k]) {
90 new = new_radix_node();
91 if (IS_ERR(new)) {
92 ret = -ENOMEM;
93 goto fail_out;
94 }
95 node->children[k] = new;
96 }
97 node = node->children[k];
98 }
99
100 /* the leaf level */
101 k = index[0];
102
103 if ((node->values[k] != NULL) && (value != NULL)) {
104 kwarn("Radix: add an existing key\n");
105 BUG_ON(1);
106 }
107
108 node->values[k] = value;
109
110 unlock(&radix->radix_lock);
111 return 0;
112
113 fail_out:
114 unlock(&radix->radix_lock);
115 return ret;
116 }
117
radix_get(struct radix * radix,u64 key)118 void *radix_get(struct radix *radix, u64 key)
119 {
120 void *ret;
121 struct radix_node *node;
122 u16 index[RADIX_LEVELS];
123 int i;
124 int k;
125
126 lock(&radix->radix_lock);
127 if (!radix->root) {
128 ret = NULL;
129 goto out;
130 }
131 node = radix->root;
132
133 /* calculate index for each level */
134 for (i = 0; i < RADIX_LEVELS; ++i) {
135 index[i] = key & RADIX_NODE_MASK;
136 key >>= RADIX_NODE_BITS;
137 }
138
139 /* the intermediate levels */
140 for (i = RADIX_LEVELS - 1; i > 0; --i) {
141 k = index[i];
142 if (!node->children[k]) {
143 ret = NULL;
144 goto out;
145 }
146 node = node->children[k];
147 }
148
149 /* the leaf level */
150 k = index[0];
151 ret = node->values[k];
152
153 out:
154 unlock(&radix->radix_lock);
155 return ret;
156 }
157
158
radix_del(struct radix * radix,u64 key)159 int radix_del(struct radix *radix, u64 key)
160 {
161 return radix_add(radix, key, NULL);
162 }
163
radix_free_node(struct radix_node * node,int node_level,void (* value_deleter)(void *))164 static void radix_free_node(struct radix_node *node, int node_level,
165 void (*value_deleter)(void *))
166 {
167 int i;
168
169 if (!node) {
170 BUG("should not try to free a node pointed by NULL");
171 }
172 if (node_level == RADIX_LEVELS - 1) {
173 if (value_deleter) {
174 for (i = 0; i < RADIX_NODE_SIZE; i++) {
175 if (node->values[i])
176 value_deleter(node->values[i]);
177 }
178 }
179 } else {
180 for (i = 0; i < RADIX_NODE_SIZE; i++) {
181 if (node->children[i])
182 radix_free_node(
183 node->children[i], node_level + 1, value_deleter);
184 }
185 }
186 kfree(node);
187 }
188 #endif
189
radix_free(struct radix * radix)190 int radix_free(struct radix *radix)
191 {
192 lock(&radix->radix_lock);
193 if (!radix || !radix->root) {
194 WARN("trying to free an empty radix tree");
195 return -EINVAL;
196 }
197
198 // recurssively free nodes and values (if value_deleter is not NULL)
199 radix_free_node(radix->root, 0, radix->value_deleter);
200 unlock(&radix->radix_lock);
201
202 kfree(radix);
203 return 0;
204 }
205