1 /*
2 * COPYRIGHT (c) International Business Machines Corp. 2005-2017
3 *
4 * This program is provided under the terms of the Common Public License,
5 * version 1.0 (CPL-1.0). Any use, reproduction or distribution for this
6 * software constitutes recipient's acceptance of CPL-1.0 terms which can be
7 * found in the file LICENSE file or at
8 * https://opensource.org/licenses/cpl1.0.php
9 */
10
11 /*
12 * btree.c
13 * Author: Kent Yoder <yoder1@us.ibm.com>
14 *
15 * v1 Binary tree functions 4/5/2011
16 *
17 */
18
19
20 #include <stdio.h>
21 #include <stdlib.h>
22
23 #include "pkcs11types.h"
24 #include "local_types.h"
25 #include "trace.h"
26
27 #define GET_NODE_HANDLE(n) get_node_handle(n, 1)
28 #define TREE_DUMP(t) tree_dump((t)->top, 0)
29
30 /*
31 * bt_get_node
32 *
33 * Return a node of the tree @t with position @node_num. If the node has been
34 * freed or doesn't exist, return NULL
35 */
bt_get_node(struct btree * t,unsigned long node_num)36 struct btnode *bt_get_node(struct btree *t, unsigned long node_num)
37 {
38 __transaction_atomic { /* start transaction */
39 struct btnode *temp = t->top;
40 unsigned long i;
41
42 if (!node_num || node_num > t->size)
43 return NULL;
44 if (node_num == 1) {
45 temp = t->top;
46 goto done;
47 }
48
49 i = node_num;
50 while (i != 1) {
51 if (i & 1) {
52 /* If the bit is 1, traverse right */
53 temp = temp->right;
54 } else {
55 /* If the bit is 0, traverse left */
56 temp = temp->left;
57 }
58 i >>= 1;
59 }
60 done:
61 return ((temp->flags & BT_FLAG_FREE) ? NULL : temp);
62 } /* end transaction */
63 }
64
bt_get_node_value(struct btree * t,unsigned long node_num)65 void *bt_get_node_value(struct btree *t, unsigned long node_num)
66 {
67 struct btnode *n = bt_get_node(t, node_num);
68
69 return ((n) ? n->value : NULL);
70 }
71
72 /* create a new node and set @parent_ptr to its location */
node_create(struct btnode ** child_ptr,struct btnode * parent_ptr,void * value)73 static struct btnode *node_create(struct btnode **child_ptr,
74 struct btnode *parent_ptr, void *value)
75 {
76 struct btnode *node = malloc(sizeof(struct btnode));
77
78 if (!node)
79 return NULL;
80
81 node->left = node->right = NULL;
82 node->flags = 0;
83 node->value = value;
84 *child_ptr = node;
85 node->parent = parent_ptr;
86
87 return node;
88 }
89
90 /*
91 * get_node_handle
92 *
93 * Recursively construct a node's handle by tracing its path back to the root
94 * node
95 */
get_node_handle(struct btnode * node,unsigned long handle_so_far)96 static unsigned long get_node_handle(struct btnode *node,
97 unsigned long handle_so_far)
98 {
99 if (!node->parent)
100 return handle_so_far;
101 else if (node->parent->left == node)
102 return get_node_handle(node->parent, handle_so_far << 1);
103 else
104 return get_node_handle(node->parent, (handle_so_far << 1) + 1);
105 }
106
107 /* return node number (handle) of newly created node, or 0 for failure */
bt_node_add(struct btree * t,void * value)108 unsigned long bt_node_add(struct btree *t, void *value)
109 {
110 __transaction_atomic { /*start transaction */
111 struct btnode *temp = t->top;
112 unsigned long new_node_index;
113
114 if (!temp) { /* no root node yet exists, create it */
115 t->size = 1;
116 if (!node_create(&t->top, NULL, value)) {
117 return 0;
118 }
119
120 return 1;
121 } else if (t->free_list) {
122 /* there's a node on the free list,
123 * use it instead of mallocing new
124 */
125 temp = t->free_list;
126 t->free_list = temp->value;
127 temp->value = value;
128 temp->flags &= (~BT_FLAG_FREE);
129 t->free_nodes--;
130 new_node_index = GET_NODE_HANDLE(temp);
131 return new_node_index;
132 }
133
134 new_node_index = t->size + 1;
135
136 while (new_node_index != 1) {
137 if (new_node_index & 1) {
138 if (!temp->right) {
139 if (!(node_create(&temp->right, temp, value))) {
140 return 0;
141 }
142 break;
143 } else {
144 /* If the bit is 1, traverse right */
145 temp = temp->right;
146 }
147 } else {
148 if (!temp->left) {
149 if (!(node_create(&temp->left, temp, value))) {
150 return 0;
151 }
152 break;
153 } else {
154 /* If the bit is 0, traverse left */
155 temp = temp->left;
156 }
157 }
158
159 new_node_index >>= 1;
160 }
161
162 t->size++;
163
164 return t->size;
165 } /* end transaction */
166 }
167
tree_dump(struct btnode * n,int depth)168 void tree_dump(struct btnode *n, int depth)
169 {
170 int i;
171
172 if (!n)
173 return;
174
175 for (i = 0; i < depth; i++)
176 printf(" ");
177
178 if (n->flags & BT_FLAG_FREE)
179 printf("`- (deleted node)\n");
180 else
181 printf("`- %p\n", n->value);
182
183 tree_dump(n->left, depth + 1);
184 tree_dump(n->right, depth + 1);
185 }
186
187 /*
188 * bt_node_free
189 *
190 * Move @node_num in tree @t to the free list, calling @delete_func on its value
191 * first.
192 *
193 * Note that bt_get_node will return NULL if the node is already on the free
194 * list, so no double freeing can occur
195 */
bt_node_free(struct btree * t,unsigned long node_num,void (* delete_func)(void *))196 struct btnode *bt_node_free(struct btree *t, unsigned long node_num,
197 void (*delete_func) (void *))
198 {
199 struct btnode *node = bt_get_node(t, node_num);
200
201 if (node) {
202 if (delete_func)
203 (*delete_func) (node->value);
204
205 __transaction_atomic { /* start transaction */
206 node->flags |= BT_FLAG_FREE;
207
208 /* add node to the free list,
209 * which is chained by using
210 * the value pointer
211 */
212 node->value = t->free_list;
213 t->free_list = node;
214 t->free_nodes++;
215 } /* end transaction */
216 }
217
218 return node;
219 }
220
bt_node_free_(STDLL_TokData_t * tokdata,struct btree * t,unsigned long node_num,void (* delete_func)(STDLL_TokData_t * tokdata,void *))221 struct btnode *bt_node_free_(STDLL_TokData_t *tokdata, struct btree *t,
222 unsigned long node_num,
223 void (*delete_func) (STDLL_TokData_t *tokdata,
224 void *))
225 {
226 struct btnode *node = bt_get_node(t, node_num);
227
228 if (node) {
229 if (delete_func)
230 (*delete_func) (tokdata, node->value);
231
232 __transaction_atomic { /* start transaction */
233 node->flags |= BT_FLAG_FREE;
234
235 /* add node to the free list,
236 * which is chained by using
237 * the value pointer
238 */
239 node->value = t->free_list;
240 t->free_list = node;
241 t->free_nodes++;
242 } /* end transaction */
243 }
244
245 return node;
246 }
247
248 /* bt_is_empty
249 *
250 * return 0 if binary tree has at least 1 node in use, !0 otherwise
251 */
bt_is_empty(struct btree * t)252 int bt_is_empty(struct btree *t)
253 {
254 __transaction_atomic { /* start transaction */
255 return (t->free_nodes == t->size);
256 } /* end transaction */
257 }
258
259 /* bt_nodes_in_use
260 *
261 * return the number of nodes in the binary tree that are not free'd
262 */
bt_nodes_in_use(struct btree * t)263 unsigned long bt_nodes_in_use(struct btree *t)
264 {
265 __transaction_atomic { /* start transaction */
266 return (t->size - t->free_nodes);
267 } /* end transaction */
268 }
269
270 /* bt_for_each_node
271 *
272 * For each non-free'd node in the tree, run @func on it
273 *
274 * @func:
275 * p1 is the node's value
276 * p2 is the node's handle
277 * p3 is passed through this function for the caller
278 */
bt_for_each_node(STDLL_TokData_t * tokdata,struct btree * t,void (* func)(STDLL_TokData_t * tokdata,void * p1,unsigned long p2,void * p3),void * p3)279 void bt_for_each_node(STDLL_TokData_t *tokdata, struct btree *t, void (*func)
280 (STDLL_TokData_t *tokdata, void *p1, unsigned long p2,
281 void *p3), void *p3)
282 {
283 unsigned int i;
284 struct btnode *node;
285
286 for (i = 1; i < t->size + 1; i++) {
287 node = bt_get_node(t, i);
288
289 if (node) {
290 (*func) (tokdata, node->value, i, p3);
291 }
292 }
293 }
294
295 /* bt_destroy
296 *
297 * Walk a binary tree backwards (largest index to smallest), deleting nodes
298 * along the way.
299 * Call @func on node->value before freeing the node.
300 */
bt_destroy(struct btree * t,void (* func)(void *))301 void bt_destroy(struct btree *t, void (*func) (void *))
302 {
303 unsigned long i;
304 struct btnode *temp;
305
306 while (t->size) {
307 __transaction_atomic { /* start transaction */
308 temp = t->top;
309 i = t->size;
310 while (i != 1) {
311 if (i & 1) {
312 /* If the bit is 1, traverse right */
313 temp = temp->right;
314 } else {
315 /* If the bit is 0, traverse left */
316 temp = temp->left;
317 }
318 i >>= 1;
319 }
320 } /* end transaction */
321
322 /*
323 * The value pointed by value in a node marked as freed points
324 * to the next node element in free_list and it shouldn't be
325 * freed here because the loop will iterate through each node,
326 * freed or not.
327 */
328 if (func && !(temp->flags & BT_FLAG_FREE))
329 (*func) (temp->value);
330
331 __transaction_atomic { /* start transaction */
332 free(temp);
333 t->size--;
334 } /* end transaction */
335 }
336
337 __transaction_atomic { /* start transaction */
338 /* the tree is gone now, clear all the other variables */
339 t->top = NULL;
340 t->free_list = NULL;
341 t->free_nodes = 0;
342 } /* end transaction */
343 }
344