~vibhavp/ubuntu/raring/dahdi-tools/merge-from-debian
» Revision
9
: xpp/oct612x/apilib/bt/octapi_bt0.c
« back to all changes in this revision
Viewing changes to xpp/oct612x/apilib/bt/octapi_bt0.c
- browse files at revision 9
- compare with another revision
- download diff
- download tarball
- view history from revision 9
- Committer: Vibhav Pant
- Date: 2012-12-26 17:23:16 UTC
- mfrom: (2.1.6 sid)
- Revision ID: vibhavp@gmail.com-20121226172316-o2jojsfcnr0aqrme
* Merge from Debian unstable. Remaining changes:
- Bug Fix: If linux-headers are not installed, don't block, and print
information for the user.
- added debian/dahdi.postinst
- added --error-handler=init_failed to debian/rules
- debian/control: Added gawk as dependency for dkms build (LP: #493304)
- Changes from Debian:
- debian/control: Change Maintainer
- debian/control: Removed Uploaders field.
- debian/control: Removed Debian Vcs-Svn entry and replaced with
ubuntu-voip Vcs-Bzr, to reflect divergence in packages.
- debian/control: Package dahdi Depends on dahdi-dkms | dahdi-source
- Bug Fix: If linux-headers are not installed, don't block, and print
information for the user.
- added debian/dahdi.postinst
- added --error-handler=init_failed to debian/rules
- debian/control: Added gawk as dependency for dkms build (LP: #493304)
- Changes from Debian:
- debian/control: Change Maintainer
- debian/control: Removed Uploaders field.
- debian/control: Removed Debian Vcs-Svn entry and replaced with
ubuntu-voip Vcs-Bzr, to reflect divergence in packages.
- debian/control: Package dahdi Depends on dahdi-dkms | dahdi-source
- files added:
- .pc/.quilt_patches
- xpp/oct612x
- xpp/oct612x/apilib
- xpp/oct612x/apilib/bt
- xpp/oct612x/apilib/largmath
- xpp/oct612x/apilib/llman
- xpp/oct612x/include
- xpp/oct612x/include/apilib
- xpp/oct612x/include/oct6100api
- xpp/oct612x/include/octrpc
- xpp/oct612x/octdeviceapi
- xpp/oct612x/octdeviceapi/oct6100api
- xpp/oct612x/octdeviceapi/oct6100api/oct6100_api
- xpp/oct612x/octdeviceapi/oct6100api/oct6100_apimi
- xpp/xtalk
- files removed:
- .pc/applied-patches
- .pc/echocan_oslec
- .pc/echocan_oslec/xpp
- .pc/echocan_oslec/xpp/perl_modules
- .pc/echocan_oslec/xpp/perl_modules/Dahdi
- .pc/echocan_oslec/xpp/perl_modules/Dahdi/Config
- .pc/init_unload_oslec
- .pc/zaptel_perl
- .pc/zaptel_perl/xpp
- files modified:
- .version
added
removed
xpp/oct612x/apilib/bt/octapi_bt0.c
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
Loggerhead is a web-based interface for Breezy
Version: 2.0.1