Debian Codegraph @

xpp/oct612x/apilib/bt/octapi_bt0.c

raw
1 /*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\
2
3 File: octapi_bt0.c
4
5 Copyright (c) 2001-2007 Octasic Inc.
6
7 Description:
8
9 Library used to manage a binary tree of variable max size. Library is
10 made to use one block of contiguous memory to manage the tree.
11
12 This file is part of the Octasic OCT6100 GPL API . The OCT6100 GPL API is
13 free software; you can redistribute it and/or modify it under the terms of
14 the GNU General Public License as published by the Free Software Foundation;
15 either version 2 of the License, or (at your option) any later version.
16
17 The OCT6100 GPL API is distributed in the hope that it will be useful, but
18 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
19 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 for more details.
21
22 You should have received a copy of the GNU General Public License
23 along with the OCT6100 GPL API; if not, write to the Free Software
24 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
25
26 $Octasic_Release: OCT612xAPI-01.00-PR49 $
27
28 $Octasic_Revision: 18 $
29
30 \*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*/
31 #include "apilib/octapi_bt0.h"
32 #include "octapi_bt0_private.h"
33
34
35
36 #if !SKIP_OctApiBt0GetSize
37 UINT32 OctApiBt0GetSize(UINT32 number_of_items,UINT32 key_size, UINT32 data_size, UINT32 * b_size)
38 {
39 if ((key_size % 4) != 0) return(OCTAPI_BT0_KEY_SIZE_NOT_MUTLIPLE_OF_UINT32);
40 if ((data_size % 4) != 0) return(OCTAPI_BT0_DATA_SIZE_NOT_MUTLIPLE_OF_UINT32);
41
42 *b_size = 0;
43 *b_size += sizeof(OCTAPI_BT0);
44 *b_size += sizeof(OCTAPI_BT0_NODE) * number_of_items;
45 *b_size += key_size * number_of_items;
46 *b_size += data_size * number_of_items;
47
48 return(GENERIC_OK);
49 }
50 #endif
51
52 #if !SKIP_OctApiBt0Init
53 UINT32 OctApiBt0Init(void ** b,UINT32 number_of_items,UINT32 key_size, UINT32 data_size)
54 {
55 UINT32 i;
56 OCTAPI_BT0 * bb;
57
58 /* Check input parameters.*/
59 if ((key_size % 4) != 0) return(OCTAPI_BT0_KEY_SIZE_NOT_MUTLIPLE_OF_UINT32);
60 if ((data_size % 4) != 0) return(OCTAPI_BT0_DATA_SIZE_NOT_MUTLIPLE_OF_UINT32);
61
62 /* If b is not already allocated.*/
63 if (*b == NULL) return(OCTAPI_BT0_MALLOC_FAILED);
64
65 bb = (OCTAPI_BT0 *)(*b);
66
67 /* Initialize the tree to an empty one!*/
68 bb->root_link.node_number = 0xFFFFFFFF;
69 bb->root_link.depth = 0;
70
71 /* Initialize tree parameters.*/
72 bb->number_of_items = number_of_items;
73 bb->key_size = key_size / 4;
74 bb->data_size = data_size / 4;
75
76 /* Initialize the next free node pointer.*/
77 if (number_of_items != 0)
78 bb->next_free_node = 0;
79 else
80 bb->next_free_node = 0xFFFFFFFF;
81
82 /* Setup the arrays.*/
83 OctApiBt0CorrectPointers(bb);
84
85 /* Initialize the Nodes to unused!*/
86 for(i=0;i<number_of_items;i++)
87 {
88 bb->node[i].next_free_node = i + 1;
89 }
90
91 /* Last empty node points to invalid node.*/
92 bb->node[number_of_items-1].next_free_node = 0xFFFFFFFF;
93
94 bb->invalid_value = 0xFFFFFFFF;
95 bb->no_smaller_key = OCTAPI_BT0_NO_SMALLER_KEY;
96
97 return(GENERIC_OK);
98 }
99 #endif
100
101
102 #if !SKIP_OctApiBt0CorrectPointers
103 void OctApiBt0CorrectPointers(OCTAPI_BT0 * bb)
104 {
105 bb->node = (OCTAPI_BT0_NODE *)(((BYTE *)bb) + sizeof(OCTAPI_BT0));
106 bb->key = (UINT32 *)(((BYTE *)bb->node) + (sizeof(OCTAPI_BT0_NODE) * bb->number_of_items));
107 bb->data = (UINT32 *)(((BYTE *)bb->key) + (sizeof(UINT32) * bb->number_of_items * bb->key_size));
108 }
109 #endif
110
111
112 #if !SKIP_OctApiBt0AddNode
113 UINT32 OctApiBt0AddNode(void * b,void * key,void ** data)
114 {
115 OCTAPI_BT0 * bb;
116 OCTAPI_BT0_NODE * new_node;
117 UINT32 * lkey;
118 UINT32 * nkey;
119 UINT32 i;
120 UINT32 new_node_number;
121 UINT32 result;
122
123 /* Load all!*/
124 bb = (OCTAPI_BT0 *)(b);
125 OctApiBt0CorrectPointers(bb);
126
127 /* Check that there is at least one block left.*/
128 if (bb->next_free_node == 0xFFFFFFFF) return(OCTAPI_BT0_NO_NODES_AVAILABLE);
129
130 /* Seize the node!*/
131 new_node_number = bb->next_free_node;
132 new_node = &(bb->node[new_node_number]);
133 bb->next_free_node = new_node->next_free_node;
134
135 /* Register in the key and the data.*/
136 lkey = ((UINT32 *)key);
137
138 /* Find the first UINT32 of the key.*/
139 nkey = &(bb->key[bb->key_size * new_node_number]);
140
141 /* Copy the key.*/
142 for(i=0;i<bb->key_size;i++)
143 nkey[i] = lkey[i];
144
145 /* Attempt to place the node. Only a "multiple hit" will cause an error.*/
146 result = OctApiBt0AddNode2(bb,&(bb->root_link), lkey, new_node_number);
147 if (result != GENERIC_OK)
148 {
149 /* This attempt failed. Refree the node!*/
150 bb->next_free_node = new_node_number;
151
152 /* Return the error code.*/
153 return(result);
154 }
155
156 /* Return the address of the data to the user.*/
157 if ( bb->data_size > 0 )
158 *data = (void *)(&(bb->data[bb->data_size * new_node_number]));
159
160 return(GENERIC_OK);
161 }
162 #endif
163
164 #if !SKIP_OctApiBt0AddNode2
165 UINT32 OctApiBt0AddNode2(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link,UINT32 * lkey,UINT32 new_node_number)
166 {
167 UINT32 result;
168
169 if (link->node_number == 0xFFFFFFFF) /* We have an empty node. Here, we shall place the new node.*/
170 {
171 bb->node[new_node_number].l[0].node_number = 0xFFFFFFFF;
172 bb->node[new_node_number].l[0].depth = 0;
173 bb->node[new_node_number].l[1].node_number = 0xFFFFFFFF;
174 bb->node[new_node_number].l[1].depth = 0;
175
176 /* OCTAPI_BT0_LINK to parent!*/
177 link->node_number = new_node_number;
178 link->depth = 1; /* We are a leaf, last OCTAPI_BT0_LINK depth is 1.*/
179
180 return(GENERIC_OK);
181 }
182 else /* Current node is used, check for a match and a direction.*/
183 {
184 OCTAPI_BT0_NODE * this_node;
185 UINT32 compare;
186
187 /* Get a pointer to this node.*/
188 this_node = &(bb->node[link->node_number]);
189
190 /* Compare this node to the lkey.*/
191 compare = OctApiBt0KeyCompare(bb,link,lkey);
192
193 if (compare == OCTAPI_BT0_LKEY_SMALLER) /* Go left.*/
194 {
195 result = OctApiBt0AddNode2(bb,&(this_node->l[0]), lkey, new_node_number);
196 if (result != GENERIC_OK) return(result);
197 }
198 else if (compare == OCTAPI_BT0_LKEY_LARGER) /* Go right.*/
199 {
200 result = OctApiBt0AddNode2(bb,&(this_node->l[1]), lkey, new_node_number);
201 if (result != GENERIC_OK) return(result);
202 }
203 else
204 {
205 return(OCTAPI_BT0_KEY_ALREADY_IN_TREE);
206 }
207
208 /* Check if this node is unbalanced by 2. If so, rebalance it:*/
209 if (this_node->l[0].depth > (this_node->l[1].depth + 1) ||
210 this_node->l[1].depth > (this_node->l[0].depth + 1))
211 {
212 OctApiBt0Rebalance(bb,link);
213 }
214
215 /* Always update the OCTAPI_BT0_LINK depth before exiting.*/
216 OctApiBt0UpdateLinkDepth(bb,link);
217
218 return(GENERIC_OK);
219 }
220 }
221 #endif
222
223
224 #if !SKIP_OctApiBt0AddNode3
225 UINT32 OctApiBt0AddNode3(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link,UINT32 * lkey,UINT32 *p_new_node_number)
226 {
227 UINT32 result;
228
229 if (link->node_number == 0xFFFFFFFF) /* We have an empty node. Here, we shall place the new node.*/
230 {
231 if ( *p_new_node_number == 0xFFFFFFFF )
232 return(OCTAPI_BT0_NO_NODES_AVAILABLE);
233
234 bb->node[*p_new_node_number].l[0].node_number = 0xFFFFFFFF;
235 bb->node[*p_new_node_number].l[0].depth = 0;
236 bb->node[*p_new_node_number].l[1].node_number = 0xFFFFFFFF;
237 bb->node[*p_new_node_number].l[1].depth = 0;
238
239 /* OCTAPI_BT0_LINK to parent!*/
240 link->node_number = *p_new_node_number;
241 link->depth = 1; /* We are a leaf, last OCTAPI_BT0_LINK depth is 1.*/
242
243 return(GENERIC_OK);
244 }
245 else /* Current node is used, check for a match and a direction.*/
246 {
247 OCTAPI_BT0_NODE * this_node;
248 UINT32 compare;
249
250 /* Get a pointer to this node.*/
251 this_node = &(bb->node[link->node_number]);
252
253 /* Compare this node to the lkey.*/
254 compare = OctApiBt0KeyCompare(bb,link,lkey);
255
256 if (compare == OCTAPI_BT0_LKEY_SMALLER) /* Go left.*/
257 {
258 result = OctApiBt0AddNode3(bb,&(this_node->l[0]), lkey, p_new_node_number);
259 if (result != GENERIC_OK) return(result);
260 }
261 else if (compare == OCTAPI_BT0_LKEY_LARGER) /* Go right.*/
262 {
263 result = OctApiBt0AddNode3(bb,&(this_node->l[1]), lkey, p_new_node_number);
264 if (result != GENERIC_OK) return(result);
265 }
266 else
267 {
268 *p_new_node_number = link->node_number;
269 return(OCTAPI_BT0_KEY_ALREADY_IN_TREE);
270 }
271
272 /* Check if this node is unbalanced by 2. If so, rebalance it:*/
273 if (this_node->l[0].depth > (this_node->l[1].depth + 1) ||
274 this_node->l[1].depth > (this_node->l[0].depth + 1))
275 {
276 OctApiBt0Rebalance(bb,link);
277 }
278
279 /* Always update the OCTAPI_BT0_LINK depth before exiting.*/
280 OctApiBt0UpdateLinkDepth(bb,link);
281
282 return(GENERIC_OK);
283 }
284 }
285 #endif
286
287 /* state
288 0 -> first call to the function.
289 1 -> recursive call.*/
290 #if !SKIP_OctApiBt0AddNode4
291 UINT32 OctApiBt0AddNode4(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link,UINT32 * lkey,UINT32 *p_new_node_number, UINT32 *p_prev_node_number, UINT32 state )
292 {
293 UINT32 result;
294 UINT32 *nkey;
295 UINT32 *okey;
296
297 if (link->node_number == 0xFFFFFFFF) /* We have an empty node. Here, we shall place the new node.*/
298 {
299 bb->node[*p_new_node_number].l[0].node_number = 0xFFFFFFFF;
300 bb->node[*p_new_node_number].l[0].depth = 0;
301 bb->node[*p_new_node_number].l[1].node_number = 0xFFFFFFFF;
302 bb->node[*p_new_node_number].l[1].depth = 0;
303
304 /* OCTAPI_BT0_LINK to parent!*/
305 link->node_number = *p_new_node_number;
306 link->depth = 1; /* We are a leaf, last OCTAPI_BT0_LINK depth is 1.*/
307
308 if ( state == 0 )
309 *p_prev_node_number = 0xFFFFFFFF;
310
311 return(GENERIC_OK);
312 }
313 else /* Current node is used, check for a match and a direction.*/
314 {
315 OCTAPI_BT0_NODE * this_node;
316 UINT32 compare;
317
318 /* Get a pointer to this node.*/
319 this_node = &(bb->node[link->node_number]);
320
321 /* Compare this node to the lkey.*/
322 compare = OctApiBt0KeyCompare(bb,link,lkey);
323
324 if (compare == OCTAPI_BT0_LKEY_SMALLER) /* Go left.*/
325 {
326 if ( state == 0 )
327 *p_prev_node_number = OCTAPI_BT0_NO_SMALLER_KEY;
328
329 if ( *p_prev_node_number != OCTAPI_BT0_NO_SMALLER_KEY )
330 {
331 /* Check if the key is the smallest one encountered yet.*/
332 okey = &(bb->key[bb->key_size * (*p_prev_node_number)]);
333 nkey = &(bb->key[bb->key_size * link->node_number]);
334 /* If the node is key smaller then the old small one, change the value.*/
335 if ( *nkey > *okey )
336 {
337 if ( *nkey < *lkey )
338 *p_prev_node_number = link->node_number;
339 }
340 }
341
342 result = OctApiBt0AddNode4(bb,&(this_node->l[0]), lkey, p_new_node_number, p_prev_node_number, 1);
343 if (result != GENERIC_OK) return(result);
344 }
345 else if (compare == OCTAPI_BT0_LKEY_LARGER) /* Go right.*/
346 {
347 if ( state == 0 )
348 *p_prev_node_number = link->node_number;
349 else
350 {
351 if ( *p_prev_node_number == OCTAPI_BT0_NO_SMALLER_KEY )
352 *p_prev_node_number = link->node_number;
353 else
354 {
355 /* Check if the key is the smallest one encountered yet.*/
356 okey = &(bb->key[bb->key_size * (*p_prev_node_number)]);
357 nkey = &(bb->key[bb->key_size * link->node_number]);
358 /* If the node is key smaller then the old small one, change the value.*/
359 if ( *nkey > *okey )
360 {
361 if ( *nkey < *lkey )
362 *p_prev_node_number = link->node_number;
363 }
364 }
365 }
366
367 result = OctApiBt0AddNode4(bb,&(this_node->l[1]), lkey, p_new_node_number, p_prev_node_number, 1);
368 if (result != GENERIC_OK) return(result);
369 }
370 else
371 {
372 *p_new_node_number = link->node_number;
373 return(OCTAPI_BT0_KEY_ALREADY_IN_TREE);
374 }
375
376 /* Check if this node is unbalanced by 2. If so, rebalance it:*/
377 if (this_node->l[0].depth > (this_node->l[1].depth + 1) ||
378 this_node->l[1].depth > (this_node->l[0].depth + 1))
379 {
380 OctApiBt0Rebalance(bb,link);
381 }
382
383 /* Always update the OCTAPI_BT0_LINK depth before exiting.*/
384 OctApiBt0UpdateLinkDepth(bb,link);
385
386 return(GENERIC_OK);
387 }
388 }
389 #endif
390
391 #if !SKIP_OctApiBt0KeyCompare
392 UINT32 OctApiBt0KeyCompare(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link, UINT32 * lkey)
393 {
394 UINT32 * nkey;
395 UINT32 i;
396
397 /* Find the first UINT32 of the key.*/
398 nkey = &(bb->key[bb->key_size * link->node_number]);
399
400 for(i=0;i<bb->key_size;i++)
401 {
402 if (lkey[i] < nkey[i])
403 return(OCTAPI_BT0_LKEY_SMALLER);
404 else if (lkey[i] > nkey[i])
405 return(OCTAPI_BT0_LKEY_LARGER);
406 }
407
408 return(OCTAPI_BT0_LKEY_EQUAL);
409 }
410 #endif
411
412
413 #if !SKIP_OctApiBt0UpdateLinkDepth
414 void OctApiBt0UpdateLinkDepth(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link)
415 {
416 OCTAPI_BT0_NODE * this_node;
417
418 /* Get a pointer to this node.*/
419 this_node = &(bb->node[link->node_number]);
420
421 if (this_node->l[0].depth > this_node->l[1].depth)
422 link->depth = this_node->l[0].depth + 1;
423 else
424 link->depth = this_node->l[1].depth + 1;
425 }
426 #endif
427
428 #if !SKIP_OctApiBt0Rebalance
429 void OctApiBt0Rebalance(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * root_link)
430 {
431 if (bb->node[root_link->node_number].l[0].depth > (bb->node[root_link->node_number].l[1].depth + 1)) /* Heavy to the left.*/
432 {
433 /* Check if the right child of the heavy child node is causing a problem.*/
434 /* If so, do a left rotate in order to make the left most child the longer one.*/
435 {
436 OCTAPI_BT0_LINK * heavy_link;
437 heavy_link = &(bb->node[root_link->node_number].l[0]);
438
439 if (bb->node[heavy_link->node_number].l[1].depth > bb->node[heavy_link->node_number].l[0].depth)
440 {
441 OctApiBt0ExternalHeavy(bb,heavy_link);
442 }
443 }
444
445 /* Ready to do super rotation!*/
446 {
447 OCTAPI_BT0_LINK init_root_link;
448 OCTAPI_BT0_LINK init_heavy_link;
449 OCTAPI_BT0_LINK init_leaf_tree[3];
450
451 /* Save pertinent initial OCTAPI_BT0_LINK information.*/
452 init_root_link = *root_link;
453 init_heavy_link = bb->node[root_link->node_number].l[0];
454 init_leaf_tree[2] = bb->node[root_link->node_number].l[1];
455 init_leaf_tree[0] = bb->node[bb->node[root_link->node_number].l[0].node_number].l[0];
456 init_leaf_tree[1] = bb->node[bb->node[root_link->node_number].l[0].node_number].l[1];
457
458 /* Restructure the tree.*/
459 *root_link = init_heavy_link;
460 bb->node[init_heavy_link.node_number].l[1] = init_root_link;
461 bb->node[init_root_link.node_number].l[0] = init_leaf_tree[1];
462
463 /* Reconstruct the depth of the branches.*/
464 OctApiBt0UpdateLinkDepth(bb,&(bb->node[root_link->node_number].l[1]));
465 OctApiBt0UpdateLinkDepth(bb,root_link);
466 }
467 }
468 else if (bb->node[root_link->node_number].l[1].depth > (bb->node[root_link->node_number].l[0].depth + 1)) /* Heavy to the right.*/
469 {
470 /* Check if the right child of the heavy child node is causing a problem.*/
471 /* If so, do a left rotate in order to make the left most child the longer one.*/
472 {
473 OCTAPI_BT0_LINK * heavy_link;
474 heavy_link = &(bb->node[root_link->node_number].l[1]);
475
476 if (bb->node[heavy_link->node_number].l[0].depth > bb->node[heavy_link->node_number].l[1].depth)
477 {
478 OctApiBt0ExternalHeavy(bb,heavy_link);
479 }
480 }
481
482 /* Ready to do super rotation!*/
483 {
484 OCTAPI_BT0_LINK init_root_link;
485 OCTAPI_BT0_LINK init_heavy_link;
486 OCTAPI_BT0_LINK init_leaf_tree[3];
487
488 /* Save pertinent initial OCTAPI_BT0_LINK information.*/
489 init_root_link = *root_link;
490 init_heavy_link = bb->node[root_link->node_number].l[1];
491 init_leaf_tree[2] = bb->node[root_link->node_number].l[0];
492 init_leaf_tree[0] = bb->node[bb->node[root_link->node_number].l[1].node_number].l[1];
493 init_leaf_tree[1] = bb->node[bb->node[root_link->node_number].l[1].node_number].l[0];
494
495 /* Restructure the tree.*/
496 *root_link = init_heavy_link;
497 bb->node[init_heavy_link.node_number].l[0] = init_root_link;
498 bb->node[init_root_link.node_number].l[1] = init_leaf_tree[1];
499
500 /* Reconstruct the depth of the branches.*/
501 OctApiBt0UpdateLinkDepth(bb,&(bb->node[root_link->node_number].l[0]));
502 OctApiBt0UpdateLinkDepth(bb,root_link);
503 }
504 }
505 }
506 #endif
507
508 /* This function does a rotation towards the outside of the tree*/
509 /* in order to keep the heavy branches towards the outside.*/
510 #if !SKIP_OctApiBt0ExternalHeavy
511 void OctApiBt0ExternalHeavy(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * root_link)
512 {
513 if (bb->node[root_link->node_number].l[1].depth > bb->node[root_link->node_number].l[0].depth) /* Exterior of tree is towards the left.*/
514 {
515 OCTAPI_BT0_LINK init_root_link;
516 OCTAPI_BT0_LINK init_heavy_link;
517 OCTAPI_BT0_LINK init_leaf_tree[3];
518
519 /* Save pertinent initial OCTAPI_BT0_LINK information.*/
520 init_root_link = *root_link;
521 init_leaf_tree[0] = bb->node[root_link->node_number].l[0];
522 init_heavy_link = bb->node[root_link->node_number].l[1];
523 init_leaf_tree[1] = bb->node[bb->node[root_link->node_number].l[1].node_number].l[0];
524 init_leaf_tree[2] = bb->node[bb->node[root_link->node_number].l[1].node_number].l[1];
525
526 /* Restructure the tree.*/
527 *root_link = init_heavy_link;
528 bb->node[init_heavy_link.node_number].l[0] = init_root_link;
529 bb->node[init_root_link.node_number].l[1] = init_leaf_tree[1];
530
531 /* Reconstruct the depth of the branches.*/
532 OctApiBt0UpdateLinkDepth(bb,&(bb->node[root_link->node_number].l[0]));
533 OctApiBt0UpdateLinkDepth(bb,root_link);
534 }
535 else if (bb->node[root_link->node_number].l[0].depth > bb->node[root_link->node_number].l[1].depth) /* Exterior of tree is towards the right.*/
536 {
537 OCTAPI_BT0_LINK init_root_link;
538 OCTAPI_BT0_LINK init_heavy_link;
539 OCTAPI_BT0_LINK init_leaf_tree[3];
540
541 /* Save pertinent initial OCTAPI_BT0_LINK information.*/
542 init_root_link = *root_link;
543 init_leaf_tree[0] = bb->node[root_link->node_number].l[1];
544 init_heavy_link = bb->node[root_link->node_number].l[0];
545 init_leaf_tree[1] = bb->node[bb->node[root_link->node_number].l[0].node_number].l[1];
546 init_leaf_tree[2] = bb->node[bb->node[root_link->node_number].l[0].node_number].l[0];
547
548 /* Restructure the tree.*/
549 *root_link = init_heavy_link;
550 bb->node[init_heavy_link.node_number].l[1] = init_root_link;
551 bb->node[init_root_link.node_number].l[0] = init_leaf_tree[1];
552
553 /* Reconstruct the depth of the branches.*/
554 OctApiBt0UpdateLinkDepth(bb,&(bb->node[root_link->node_number].l[1]));
555 OctApiBt0UpdateLinkDepth(bb,root_link);
556 }
557 }
558 #endif
559
560
561 /* State:*/
562 /* 0 = seeking node to be removed.*/
563 /* 1 = node found, left branch taken.*/
564 /* 2 = node found, right branch taken.*/
565 #if !SKIP_OctApiBt0RemoveNode2
566 UINT32 OctApiBt0RemoveNode2(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link, UINT32 * lkey, OCTAPI_BT0_LINK * link_to_removed_node, UINT32 state, OCTAPI_BT0_LINK * volatile_grandparent_link)
567 {
568 UINT32 result;
569 OCTAPI_BT0_NODE * this_node;
570
571 /* Get a pointer to this node.*/
572 this_node = &(bb->node[link->node_number]);
573
574 if (state == 0)
575 {
576 if (link->node_number == 0xFFFFFFFF) /* We have an empty node. The node we were looking for does not exist.*/
577 {
578 return(OCTAPI_BT0_KEY_NOT_IN_TREE);
579 }
580 else /* Current node is used, check for a match and a direction.*/
581 {
582 UINT32 compare;
583
584 /* Compare this node to the lkey.*/
585 compare = OctApiBt0KeyCompare(bb,link,lkey);
586
587 if (compare == OCTAPI_BT0_LKEY_SMALLER) /* Go left.*/
588 {
589 result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[0]), lkey, link_to_removed_node, 0, NULL);
590 if (result != GENERIC_OK) return(result);
591 }
592 else if (compare == OCTAPI_BT0_LKEY_LARGER) /* Go right.*/
593 {
594 result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[1]), lkey, link_to_removed_node, 0, NULL);
595 if (result != GENERIC_OK) return(result);
596 }
597 else
598 {
599 link_to_removed_node = link;
600
601 /* Keep on going down to find a replacement node.*/
602 if (bb->node[link->node_number].l[0].node_number == 0xFFFFFFFF && bb->node[link->node_number].l[1].node_number == 0xFFFFFFFF)
603 {
604 /* Doe! No tree left! WHAT TO DO? */
605 /* Just delete the current node. That's it.*/
606
607 /* Release the current node (restore free node link-list)*/
608 bb->node[link->node_number].next_free_node = bb->next_free_node;
609 bb->next_free_node = link->node_number;
610
611 link->node_number = 0xFFFFFFFF;
612 link->depth = 0;
613
614 return(GENERIC_OK);
615 }
616 else if (bb->node[link->node_number].l[0].node_number != 0xFFFFFFFF) /* Left node is present. Go left, then permanently right.*/
617 {
618 OCTAPI_BT0_NODE * removed_node_pnt;
619 removed_node_pnt = &(bb->node[link->node_number]);
620
621 result = OctApiBt0RemoveNode2(bb,&(removed_node_pnt->l[0]), lkey, link_to_removed_node, 1, link);
622 if (result != GENERIC_OK) return(result);
623
624 /* Caution! Once we are here, the link->node_pnt->l[0] has been modified,*/
625 /* but is about to be discarded! Save it quickly!*/
626 /* bb->node[link->node_number].l[0] = removed_node_pnt->l[0];*/
627 }
628 else /* Right node is present. Go right, then permanently left.*/
629 {
630 OCTAPI_BT0_NODE * removed_node_pnt;
631 removed_node_pnt = &(bb->node[link->node_number]);
632
633 result = OctApiBt0RemoveNode2(bb,&(removed_node_pnt->l[1]), lkey, link_to_removed_node, 2, link);
634 if (result != GENERIC_OK) return(result);
635
636 /* Caution! Once we are here, the link->node_pnt->l[0] has been modified,*/
637 /* but is about to be discarded! Save it quickly!*/
638 /* bb->node[link->node_number].l[1] = removed_node_pnt->l[1];*/
639 }
640 }
641 }
642 }
643 else
644 {
645 /* Left side, Right-most node found! OR*/
646 /* Right side, Left-most node found!*/
647 if ((state == 1 && bb->node[link->node_number].l[1].node_number == 0xFFFFFFFF) ||
648 (state == 2 && bb->node[link->node_number].l[0].node_number == 0xFFFFFFFF))
649 {
650 OCTAPI_BT0_LINK init_chosen_link;
651
652 /* Release the current node (restore free node link-list)*/
653 bb->node[link_to_removed_node->node_number].next_free_node = bb->next_free_node;
654 bb->next_free_node = link_to_removed_node->node_number;
655
656 /* Save the link to the chosen node, because it is about to be deleted.*/
657 init_chosen_link = *link;
658
659 /* Remove this node, and allow the tree to go on:*/
660 {
661 OCTAPI_BT0_LINK init_child_link[2];
662
663 init_child_link[0] = bb->node[link->node_number].l[0];
664 init_child_link[1] = bb->node[link->node_number].l[1];
665
666 if (state == 1)
667 *link = init_child_link[0];
668 else
669 *link = init_child_link[1];
670 }
671
672 /* Replace the removed node by this node.*/
673 {
674 OCTAPI_BT0_LINK init_removed_child_link[2];
675
676 init_removed_child_link[0] = bb->node[link_to_removed_node->node_number].l[0];
677 init_removed_child_link[1] = bb->node[link_to_removed_node->node_number].l[1];
678
679 *link_to_removed_node = init_chosen_link;
680 bb->node[init_chosen_link.node_number].l[0] = init_removed_child_link[0];
681 bb->node[init_chosen_link.node_number].l[1] = init_removed_child_link[1];
682 }
683
684 return(GENERIC_OK);
685 }
686 else
687 {
688 /* Keep on going, we have not found the center most node yet!*/
689 if (state == 1)
690 {
691 result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[1]), lkey, link_to_removed_node, state, NULL);
692 if (result != GENERIC_OK) return(result);
693
694 /* Refresh the link if our link is volatile.*/
695 if (volatile_grandparent_link != NULL)
696 {
697 link = &(bb->node[volatile_grandparent_link->node_number].l[0]);
698 }
699 }
700 else
701 {
702 result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[0]), lkey, link_to_removed_node, state, NULL);
703 if (result != GENERIC_OK) return(result);
704
705 /* Refresh the link if our link is volatile.*/
706 if (volatile_grandparent_link != NULL)
707 {
708 link = &(bb->node[volatile_grandparent_link->node_number].l[1]);
709 }
710 }
711 }
712 }
713
714 /* We may have messed up the tree. So patch it!*/
715 /* Check if this node is unbalanced by 2. If so, rebalance it:*/
716 if (this_node->l[0].depth > (this_node->l[1].depth + 1) ||
717 this_node->l[1].depth > (this_node->l[0].depth + 1))
718 {
719 OctApiBt0Rebalance(bb,link);
720 }
721
722 /* Always update the OCTAPI_BT0_LINK depth before exiting.*/
723 OctApiBt0UpdateLinkDepth(bb,link);
724
725 return(GENERIC_OK);
726 }
727 #endif
728
729
730 /* State:*/
731 /* 0 = seeking node to be removed.*/
732 /* 1 = node found, left branch taken.*/
733 /* 2 = node found, right branch taken.*/
734 #if !SKIP_OctApiBt0RemoveNode3
735 UINT32 OctApiBt0RemoveNode3(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link, UINT32 * lkey, OCTAPI_BT0_LINK * link_to_removed_node, UINT32 state, OCTAPI_BT0_LINK * volatile_grandparent_link, UINT32 *p_prev_node_number )
736 {
737 UINT32 result;
738 UINT32 *nkey;
739 UINT32 *okey;
740 OCTAPI_BT0_NODE * this_node;
741
742 /* Get a pointer to this node.*/
743 this_node = &(bb->node[link->node_number]);
744
745 if (state == 0)
746 {
747 if (link->node_number == 0xFFFFFFFF) /* We have an empty node. The node we were looking for does not exist.*/
748 {
749 return(OCTAPI_BT0_KEY_NOT_IN_TREE);
750 }
751 else /* Current node is used, check for a match and a direction.*/
752 {
753 UINT32 compare;
754
755 /* Compare this node to the lkey.*/
756 compare = OctApiBt0KeyCompare(bb,link,lkey);
757
758 if (compare == OCTAPI_BT0_LKEY_SMALLER) /* Go left.*/
759 {
760 /* Check if the key is the biggest one encountered yet.*/
761 okey = &(bb->key[bb->key_size * (*p_prev_node_number)]);
762 nkey = &(bb->key[bb->key_size * link->node_number]);
763 /* If the node is key bigger then the old one, change the value.*/
764 if ( *nkey > *okey )
765 {
766 if ( *nkey < *lkey )
767 *p_prev_node_number = link->node_number;
768 }
769
770 result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[0]), lkey, link_to_removed_node, 0, NULL);
771 if (result != GENERIC_OK) return(result);
772 }
773 else if (compare == OCTAPI_BT0_LKEY_LARGER) /* Go right.*/
774 {
775 /* Check if the key is the biggest one encountered yet.*/
776 okey = &(bb->key[bb->key_size * (*p_prev_node_number)]);
777 nkey = &(bb->key[bb->key_size * link->node_number]);
778 /* If the node is key bigger then the old one, change the value.*/
779 if ( *nkey > *okey )
780 {
781 if ( *nkey < *lkey )
782 *p_prev_node_number = link->node_number;
783 }
784
785 result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[1]), lkey, link_to_removed_node, 0, NULL);
786 if (result != GENERIC_OK) return(result);
787 }
788 else
789 {
790 link_to_removed_node = link;
791
792 /* Keep on going down to find a replacement node.*/
793 if (bb->node[link->node_number].l[0].node_number == 0xFFFFFFFF && bb->node[link->node_number].l[1].node_number == 0xFFFFFFFF)
794 {
795 /* Doe! No tree left! WHAT TO DO? */
796 /* Just delete the current node. That's it.*/
797
798 /* Release the current node (restore free node link-list)*/
799 bb->node[link->node_number].next_free_node = bb->next_free_node;
800 bb->next_free_node = link->node_number;
801
802 link->node_number = 0xFFFFFFFF;
803 link->depth = 0;
804
805 return(GENERIC_OK);
806 }
807 else if (bb->node[link->node_number].l[0].node_number != 0xFFFFFFFF) /* Left node is present. Go left, then permanently right.*/
808 {
809 OCTAPI_BT0_NODE * removed_node_pnt;
810 removed_node_pnt = &(bb->node[link->node_number]);
811
812 result = OctApiBt0RemoveNode2(bb,&(removed_node_pnt->l[0]), lkey, link_to_removed_node, 1, link);
813 if (result != GENERIC_OK) return(result);
814
815 /* Caution! Once we are here, the link->node_pnt->l[0] has been modified,*/
816 /* but is about to be discarded! Save it quickly!*/
817 /* bb->node[link->node_number].l[0] = removed_node_pnt->l[0];*/
818 }
819 else /* Right node is present. Go right, then permanently left.*/
820 {
821 OCTAPI_BT0_NODE * removed_node_pnt;
822 removed_node_pnt = &(bb->node[link->node_number]);
823
824 result = OctApiBt0RemoveNode2(bb,&(removed_node_pnt->l[1]), lkey, link_to_removed_node, 2, link);
825 if (result != GENERIC_OK) return(result);
826
827 /* Caution! Once we are here, the link->node_pnt->l[0] has been modified,*/
828 /* but is about to be discarded! Save it quickly!*/
829 /* bb->node[link->node_number].l[1] = removed_node_pnt->l[1];*/
830 }
831 }
832 }
833 }
834 else
835 {
836 /* Check if the key is the biggest one encountered yet.*/
837 okey = &(bb->key[bb->key_size * (*p_prev_node_number)]);
838 nkey = &(bb->key[bb->key_size * link->node_number]);
839 /* If the node is key bigger then the old one, change the value.*/
840 if ( *nkey > *okey )
841 {
842 if ( *nkey < *lkey )
843 *p_prev_node_number = link->node_number;
844 }
845
846 /* Left side, Right-most node found! OR*/
847 /* Right side, Left-most node found!*/
848 if ((state == 1 && bb->node[link->node_number].l[1].node_number == 0xFFFFFFFF) ||
849 (state == 2 && bb->node[link->node_number].l[0].node_number == 0xFFFFFFFF))
850 {
851 OCTAPI_BT0_LINK init_chosen_link;
852
853 /* Release the current node (restore free node link-list)*/
854 bb->node[link_to_removed_node->node_number].next_free_node = bb->next_free_node;
855 bb->next_free_node = link_to_removed_node->node_number;
856
857 /* Save the link to the chosen node, because it is about to be deleted.*/
858 init_chosen_link = *link;
859
860 /* Remove this node, and allow the tree to go on:*/
861 {
862 OCTAPI_BT0_LINK init_child_link[2];
863
864 init_child_link[0] = bb->node[link->node_number].l[0];
865 init_child_link[1] = bb->node[link->node_number].l[1];
866
867 if (state == 1)
868 *link = init_child_link[0];
869 else
870 *link = init_child_link[1];
871 }
872
873 /* Replace the removed node by this node.*/
874 {
875 OCTAPI_BT0_LINK init_removed_child_link[2];
876
877 init_removed_child_link[0] = bb->node[link_to_removed_node->node_number].l[0];
878 init_removed_child_link[1] = bb->node[link_to_removed_node->node_number].l[1];
879
880 *link_to_removed_node = init_chosen_link;
881 bb->node[init_chosen_link.node_number].l[0] = init_removed_child_link[0];
882 bb->node[init_chosen_link.node_number].l[1] = init_removed_child_link[1];
883 }
884
885 return(GENERIC_OK);
886 }
887 else
888 {
889 /* Keep on going, we have not found the center most node yet!*/
890 if (state == 1)
891 {
892 result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[1]), lkey, link_to_removed_node, state, NULL);
893 if (result != GENERIC_OK) return(result);
894
895 /* Refresh the link if our link is volatile.*/
896 if (volatile_grandparent_link != NULL)
897 {
898 link = &(bb->node[volatile_grandparent_link->node_number].l[0]);
899 }
900 }
901 else
902 {
903 result = OctApiBt0RemoveNode2(bb,&(bb->node[link->node_number].l[0]), lkey, link_to_removed_node, state, NULL);
904 if (result != GENERIC_OK) return(result);
905
906 /* Refresh the link if our link is volatile.*/
907 if (volatile_grandparent_link != NULL)
908 {
909 link = &(bb->node[volatile_grandparent_link->node_number].l[1]);
910 }
911 }
912 }
913 }
914
915 /* We may have messed up the tree. So patch it!*/
916 /* Check if this node is unbalanced by 2. If so, rebalance it:*/
917 if (this_node->l[0].depth > (this_node->l[1].depth + 1) ||
918 this_node->l[1].depth > (this_node->l[0].depth + 1))
919 {
920 OctApiBt0Rebalance(bb,link);
921 }
922
923 /* Always update the OCTAPI_BT0_LINK depth before exiting.*/
924 OctApiBt0UpdateLinkDepth(bb,link);
925
926 return(GENERIC_OK);
927 }
928 #endif
929
930 #if !SKIP_OctApiBt0RemoveNode
931 UINT32 OctApiBt0RemoveNode(void * b,void * key)
932 {
933 OCTAPI_BT0 * bb;
934 UINT32 result;
935 UINT32 * lkey;
936
937 /* Load all!*/
938 bb = (OCTAPI_BT0 *)(b);
939 OctApiBt0CorrectPointers(bb);
940
941 /* Register in the key and the data.*/
942 lkey = ((UINT32 *)key);
943
944 /* Attempt to remove the node. Only a "no hit" will cause an error.*/
945 result = OctApiBt0RemoveNode2(bb,&(bb->root_link), lkey, NULL, 0, NULL);
946 if (result != GENERIC_OK) return(result);
947
948 return(GENERIC_OK);
949 }
950 #endif
951
952 #if !SKIP_OctApiBt0QueryNode2
953 UINT32 OctApiBt0QueryNode2(OCTAPI_BT0 * bb,OCTAPI_BT0_LINK * link,UINT32 * lkey,UINT32 * node_number)
954 {
955 UINT32 result;
956
957 if (link->node_number == 0xFFFFFFFF) /* We have an empty node. The node we were looking for does not exist.*/
958 {
959 return(OCTAPI_BT0_KEY_NOT_IN_TREE);
960 }
961 else /* Current node is used, check for a match and a direction.*/
962 {
963 UINT32 compare;
964
965 /* Compare this node to the lkey.*/
966 compare = OctApiBt0KeyCompare(bb,link,lkey);
967
968 if (compare == OCTAPI_BT0_LKEY_SMALLER) /* Go left.*/
969 {
970 result = OctApiBt0QueryNode2(bb,&(bb->node[link->node_number].l[0]), lkey, node_number);
971 if (result != GENERIC_OK) return(result);
972 }
973 else if (compare == OCTAPI_BT0_LKEY_LARGER) /* Go right.*/
974 {
975 result = OctApiBt0QueryNode2(bb,&(bb->node[link->node_number].l[1]), lkey, node_number);
976 if (result != GENERIC_OK) return(result);
977 }
978 else
979 {
980 /* A match!*/
981 *node_number = link->node_number;
982 }
983 }
984
985 return(GENERIC_OK);
986 }
987 #endif
988
989
990 #if !SKIP_OctApiBt0QueryNode
991 UINT32 OctApiBt0QueryNode(void * b,void * key,void ** data)
992 {
993 OCTAPI_BT0 * bb;
994 UINT32 node_number;
995 UINT32 result;
996 UINT32 * lkey;
997
998 /* Load all!*/
999 bb = (OCTAPI_BT0 *)(b);
1000 OctApiBt0CorrectPointers(bb);
1001
1002 /* Register in the key and the data.*/
1003 lkey = ((UINT32 *)key);
1004
1005 /* Get the node number.*/
1006 result = OctApiBt0QueryNode2(bb,&(bb->root_link),lkey,&node_number);
1007 if (result != GENERIC_OK) return(result);
1008
1009 /* Return the address of the data to the user.*/
1010 if ( bb->data_size > 0 )
1011 *data = (void *)(&(bb->data[bb->data_size * node_number]));
1012
1013 return(GENERIC_OK);
1014 }
1015 #endif
1016
1017 #if !SKIP_OctApiBt0GetFirstNode
1018 UINT32 OctApiBt0GetFirstNode(void * b,void ** key, void ** data)
1019 {
1020 OCTAPI_BT0 * bb;
1021 OCTAPI_BT0_NODE * node;
1022 UINT32 node_number;
1023 UINT32 * lkey;
1024
1025 /* Load all!*/
1026 bb = (OCTAPI_BT0 *)(b);
1027 OctApiBt0CorrectPointers(bb);
1028
1029 /* Register in the key and the data.*/
1030 lkey = ((UINT32 *)key);
1031
1032 /* Check if there are any keys present in the tree. */
1033 if (bb->root_link.node_number == 0xFFFFFFFF) return OCTAPI_BT0_NO_NODES_AVAILABLE;
1034
1035 node_number = bb->root_link.node_number;
1036 node = &bb->node[node_number];
1037
1038 /* Make our way down to the left-most node. */
1039 while (node->l[0].node_number != 0xFFFFFFFF)
1040 {
1041 node_number = node->l[0].node_number;
1042 node = &bb->node[node_number];
1043 }
1044
1045 /* Return the address of the data to the user.*/
1046 if ( bb->key_size > 0 )
1047 *key = (void *)(&(bb->key[bb->key_size * node_number]));
1048
1049 if ( bb->data_size > 0 )
1050 *data = (void *)(&(bb->data[bb->data_size * node_number]));
1051
1052 return(GENERIC_OK);
1053 }
1054 #endif
1055
1056 #if !SKIP_OctApiBt0FindOrAddNode
1057 UINT32 OctApiBt0FindOrAddNode(void * b,void * key,void ** data, UINT32 *fnct_result)
1058 {
1059 OCTAPI_BT0 * bb;
1060 OCTAPI_BT0_NODE * new_node;
1061 UINT32 * lkey;
1062 UINT32 * nkey;
1063 UINT32 i;
1064 UINT32 new_node_number;
1065 UINT32 temp_node_number = 0;
1066 UINT32 result;
1067 UINT32 tree_already_full = FALSE;
1068
1069 /* Load all!*/
1070 bb = (OCTAPI_BT0 *)(b);
1071 OctApiBt0CorrectPointers(bb);
1072
1073 /* Seize the node!*/
1074 new_node_number = bb->next_free_node;
1075 /* Register in the key and the data.*/
1076 lkey = ((UINT32 *)key);
1077
1078 /* Check that there is at least one block left.*/
1079 if (bb->next_free_node != 0xFFFFFFFF)
1080 {
1081
1082 temp_node_number = new_node_number;
1083 new_node = &(bb->node[new_node_number]);
1084 bb->next_free_node = new_node->next_free_node;
1085
1086 /* Find the first UINT32 of the key.*/
1087 nkey = &(bb->key[bb->key_size * new_node_number]);
1088
1089 /* Copy the key.*/
1090 for(i=0;i<bb->key_size;i++)
1091 nkey[i] = lkey[i];
1092 }
1093 else
1094 tree_already_full = TRUE; /* Signal that the tree was already full when the function was called.*/
1095
1096 /* Attempt to place the node. Only a "multiple hit" will cause an error.*/
1097 result = OctApiBt0AddNode3(bb,&(bb->root_link), lkey, &new_node_number);
1098 switch( result )
1099 {
1100 case GENERIC_OK:
1101 *fnct_result = OCTAPI0_BT0_NODE_ADDDED;
1102 break;
1103 case OCTAPI_BT0_KEY_ALREADY_IN_TREE:
1104 *fnct_result = OCTAPI0_BT0_NODE_FOUND;
1105 /* This attempt did not add a new node. Refree the node!*/
1106 if ( tree_already_full == FALSE )
1107 bb->next_free_node = temp_node_number;
1108 result = GENERIC_OK;
1109 break;
1110 default:
1111 break;
1112 }
1113
1114 if (result != GENERIC_OK)
1115 {
1116 /* This attempt failed. Refree the node!*/
1117 if ( tree_already_full == FALSE )
1118 bb->next_free_node = new_node_number;
1119
1120 /* Return the error code.*/
1121 return(result);
1122 }
1123
1124 /* Return the address of the data to the user.*/
1125 if ( bb->data_size > 0 )
1126 *data = (void *)(&(bb->data[bb->data_size * new_node_number]));
1127
1128 return(GENERIC_OK);
1129 }
1130 #endif
1131
1132
1133 #if !SKIP_OctApiBt0AddNodeReportPrevNodeData
1134 UINT32 OctApiBt0AddNodeReportPrevNodeData(void * b,void * key,void ** data, void ** prev_data, PUINT32 fnct_result )
1135 {
1136 OCTAPI_BT0 * bb;
1137 OCTAPI_BT0_NODE * new_node;
1138 UINT32 * lkey;
1139 UINT32 * nkey;
1140 UINT32 i;
1141 UINT32 new_node_number;
1142 UINT32 temp_node_number;
1143 UINT32 prev_node_number;
1144 UINT32 result;
1145
1146 /* Load all!*/
1147 bb = (OCTAPI_BT0 *)(b);
1148 OctApiBt0CorrectPointers(bb);
1149
1150 /* Check that there is at least one block left.*/
1151 if (bb->next_free_node == 0xFFFFFFFF) return(OCTAPI_BT0_NO_NODES_AVAILABLE);
1152
1153 /* Seize the node!*/
1154 new_node_number = bb->next_free_node;
1155 temp_node_number = new_node_number;
1156 new_node = &(bb->node[new_node_number]);
1157 bb->next_free_node = new_node->next_free_node;
1158
1159 /* Set the previous node value */
1160 prev_node_number = 0xFFFFFFFF;
1161
1162 /* Register in the key and the data.*/
1163 lkey = ((UINT32 *)key);
1164
1165 /* Find the first UINT32 of the key.*/
1166 nkey = &(bb->key[bb->key_size * new_node_number]);
1167
1168 /* Copy the key.*/
1169 for(i=0;i<bb->key_size;i++)
1170 nkey[i] = lkey[i];
1171
1172 /* Attempt to place the node. Only a "multiple hit" will cause an error.*/
1173 result = OctApiBt0AddNode4(bb,&(bb->root_link), lkey, &new_node_number, &prev_node_number, 0);
1174 switch( result )
1175 {
1176 case GENERIC_OK:
1177 *fnct_result = OCTAPI0_BT0_NODE_ADDDED;
1178 break;
1179 case OCTAPI_BT0_KEY_ALREADY_IN_TREE:
1180 *fnct_result = OCTAPI0_BT0_NODE_FOUND;
1181 /* This attempt did not add a new node. Refree the node!*/
1182 bb->next_free_node = temp_node_number;
1183 result = GENERIC_OK;
1184 break;
1185 default:
1186 break;
1187 }
1188
1189 if (result != GENERIC_OK)
1190 {
1191 /* This attempt failed. Refree the node!*/
1192 bb->next_free_node = new_node_number;
1193
1194 /* Return the error code.*/
1195 return(result);
1196 }
1197
1198 /* Return the address of the data to the user.*/
1199 if ( bb->data_size > 0 )
1200 *data = (void *)(&(bb->data[bb->data_size * new_node_number]));
1201
1202 if ( bb->data_size > 0 )
1203 {
1204 if ( (prev_node_number != 0xFFFFFFFF) &&
1205 (prev_node_number != OCTAPI_BT0_NO_SMALLER_KEY) &&
1206 (*fnct_result == OCTAPI0_BT0_NODE_ADDDED))
1207 *prev_data = ( void* )(&(bb->data[bb->data_size * prev_node_number]));
1208 else if ( prev_node_number == 0xFFFFFFFF )
1209 *prev_data = ( void* )(&bb->invalid_value);
1210 else if ( prev_node_number == OCTAPI_BT0_NO_SMALLER_KEY )
1211 *prev_data = ( void* )(&bb->no_smaller_key);
1212 }
1213
1214 return(GENERIC_OK);
1215 }
1216 #endif
1217