1 /************************************************************************/
2 /* */
3 /* A mapping from string values to pointer values. */
4 /* */
5 /* A tree implements the mapping of strings to pointer values. */
6 /* * Memory management (If any) of the stored pointers is the */
7 /* responsibility of the user. */
8 /* * A property of the tree decides whether the tree, or the user */
9 /* keeps trak of the string values that are used as keys inside */
10 /* the trees. */
11 /* */
12 /* IMPLEMENTATION: */
13 /* * 2-3 trees as discussed on pp 145.. of: */
14 /* AHO, Alfred V., John E. HOPCROFT & Jeffrey D. Ullman: "The */
15 /* desigh and analysis of Computer Algorithms", Addison and */
16 /* Wesley, Reading MA, 1974. */
17 /* */
18 /************************************************************************/
19
20 # include "utilTree.h"
21 # include <stdlib.h>
22 # include <string.h>
23
24 # include <appDebugon.h>
25
26 /************************************************************************/
27 /* */
28 /* A node in the tree */
29 /* */
30 /* The node is an array of three slots and a pointer to a parent node. */
31 /* In the root node, the pointer to the parent is NULL. */
32 /* In internal nodes, the left most slot does not have a key value, */
33 /* and the pointers in the slots are pointers to nodes. */
34 /* In leaf nodes: Nodes that store the actual values, the left most */
35 /* slot always has a key value, and the pointers in the slots refer */
36 /* to the stored value. */
37 /* */
38 /* Between two invocations of the routines nodes contain either */
39 /* two or three occupied slots. During the the invocation this may be */
40 /* temporarily different. The anomaly is repaired immediately. Only */
41 /* the tree with exactly one stored value is an exception: The root */
42 /* node is a leaf node that contains one stored value in the left-most */
43 /* slot. */
44 /* */
45 /************************************************************************/
46
47 typedef struct NodeSlot
48 {
49 char * nsKey; /* key of slot */
50 union /* stored value */
51 {
52 struct TreeNode * pt_nod; /* see it as a node */
53 void * pt_val; /* see it as a stored value */
54 } sl_ptr;
55 } NodeSlot;
56
57 typedef struct TreeNode
58 {
59 NodeSlot no_L; /* left slot */
60 NodeSlot no_M; /* middle slot */
61 NodeSlot no_R; /* right slot */
62
63 struct TreeNode * no_dn; /* pointer down */
64 } TreeNode;
65
66
67 /************************************************************************/
68 /* */
69 /* Avoid unnecessary typing */
70 /* */
71 /************************************************************************/
72
73 # define sl_val sl_ptr.pt_val
74 # define sl_nod sl_ptr.pt_nod
75
76 /************************************************************************/
77 /* */
78 /* struct describing a whole tree */
79 /* */
80 /* Unless the last action on a tree was a delete, tr_curr is the node */
81 /* in which the current slot resides and tr_lfcu is the key of the */
82 /* current slot. */
83 /* After a delete the flag trCurrentDeleted is set. The slot that was */
84 /* to be deleted is cut from the tree. And currency is supposed to be */
85 /* half a slot before where tr_lfcu tells us it is. */
86 /* When tr_lfcu == 0 currency is right of any slot in tr_curr */
87 /* So when trCurrentDeleted is on, currency is on what trnxt would */
88 /* give */
89 /* */
90 /************************************************************************/
91
92 # define TRsINACTIVE 0
93 # define TRsALL 1
94 # define TRsCLOSE 2
95
96 typedef struct TreeMapping
97 {
98 TreeNode * tr_root; /* the whole structure of the tree */
99 TreeNode * tr_curr; /* the current leaf */
100 char * tr_lfcu; /* the currency (key) within tr_curr */
101 char trCurrentDeleted;/* corrected currency? */
102 char trStatusFlag; /* Set by trall(), trclose() */
103 char trOwnKeys; /* If set, strdup/free keys. */
104 } TreeMapping;
105
106 /************************************************************************/
107 /* */
108 /* Memory management primitives: The indirection can be used to check */
109 /* memory management. */
110 /* */
111 /************************************************************************/
112
113 # define treeSaveKey( s ) strdup( s )
114 # define treeFreeKey( s ) free( s )
115
116 # define treeMakeNode() (TreeNode *)malloc( sizeof(TreeNode) )
117 # define treeFreeNode( n ) free( n )
118
119 # define treeMakeTree() (TreeMapping *)malloc( sizeof(TreeMapping) )
120 # define treeFreeTree( t ) free( t )
121
122 /************************************************************************/
123 /* */
124 /* Make a new tree */
125 /* */
126 /************************************************************************/
127
utilTreeMakeTree(int ownKeys)128 void * utilTreeMakeTree( int ownKeys )
129 {
130 TreeMapping * tm= (TreeMapping *)treeMakeTree();
131
132 if ( ! tm )
133 { XDEB(tm); return (void *)0; }
134
135 tm->tr_root= (TreeNode *)0;
136 tm->tr_curr= (TreeNode *)0;
137 tm->tr_lfcu= (char *)0;
138 tm->trCurrentDeleted= 0;
139 tm->trStatusFlag= TRsINACTIVE;
140 tm->trOwnKeys= ownKeys;
141
142 return (void *)tm;
143 }
144
145 /************************************************************************/
146 /* */
147 /* Find the leaf in which the entry for key possibly resides */
148 /* This is the basic 2-3 tree search function. */
149 /* */
150 /* 1) As long we are in an internal node. */
151 /* 2) Before middle: Enter left. */
152 /* 3) No right: Enter middle. */
153 /* 4) Choose between middle and right. */
154 /* */
155 /************************************************************************/
156
treeGetLeaf(TreeNode * tn,const char * key)157 static TreeNode * treeGetLeaf( TreeNode * tn,
158 const char * key )
159 {
160 /* 1 */
161 while( ! tn->no_L.nsKey )
162 {
163 int cmp;
164
165 /* 2 */
166 cmp= strcmp( key, tn->no_M.nsKey );
167 if ( cmp < 0 )
168 { tn= tn->no_L.sl_nod; continue; }
169
170 /* 3 */
171 if ( ! tn->no_R.nsKey )
172 { tn= tn->no_M.sl_nod; continue; }
173
174 /* 4 */
175 cmp= strcmp( key, tn->no_R.nsKey );
176 if ( cmp < 0 )
177 { tn= tn->no_M.sl_nod; continue; }
178 else{ tn= tn->no_R.sl_nod; continue; }
179 }
180
181 return tn;
182 }
183
184 /************************************************************************/
185 /* */
186 /* suppose tn is a leaf, return next leaf */
187 /* */
188 /************************************************************************/
189
treeGetNextLeaf(TreeNode * tn)190 static TreeNode * treeGetNextLeaf( TreeNode * tn )
191 {
192 TreeNode * dn;
193
194 for (;;)
195 {
196 /* leaf is root ? else step down */
197 dn= tn->no_dn;
198 if ( ! dn )
199 { return (TreeNode *)0; }
200
201 /* redescent from leftmost */
202 if ( dn->no_L.sl_nod == tn )
203 { tn= dn->no_M.sl_nod; break; }
204 /* redescent from middle */
205 if ( dn->no_M.sl_nod == tn )
206 {
207 /* is there a right hand branch ? */
208 if ( dn->no_R.nsKey )
209 { tn= dn->no_R.sl_nod; break; }
210 }
211 tn= dn;
212 }
213
214 /* walk to leftmost leaf */
215 while( ! tn->no_L.nsKey ) { tn= tn->no_L.sl_nod; }
216
217 return tn;
218 }
219
220 /************************************************************************/
221 /* */
222 /* suppose tn is a leaf, return previous leaf */
223 /* */
224 /************************************************************************/
225
treeGetPrevLeaf(TreeNode * tn)226 static TreeNode * treeGetPrevLeaf( TreeNode * tn )
227 {
228 TreeNode * dn;
229
230 for (;;)
231 {
232 /* leaf is root ? else step down */
233 dn= tn->no_dn;
234 if ( ! dn )
235 { return (TreeNode *)0; }
236
237 /* redescent from where */
238 if ( dn->no_M.nsKey )
239 {
240 if ( tn == dn->no_M.sl_nod )
241 { tn= dn->no_L.sl_nod; break; }
242
243 if ( dn->no_R.nsKey )
244 {
245 if ( tn == dn->no_R.sl_nod )
246 { tn= dn->no_M.sl_nod; break; }
247 }
248 }
249 tn= dn;
250 }
251
252 /* walk to rightmost leaf */
253 while( ! tn->no_L.nsKey )
254 {
255 if ( tn->no_R.nsKey )
256 { tn= tn->no_R.sl_nod; continue; }
257 tn= tn->no_M.sl_nod;
258 }
259
260 return tn;
261 }
262
263 /************************************************************************/
264 /* */
265 /* Insert a pointer into a tree. */
266 /* */
267 /************************************************************************/
268
utilTreeStoreValue(void * tree,void ** pPrevVal,const char ** pStoredKey,const char * key,void * val)269 int utilTreeStoreValue( void * tree,
270 void ** pPrevVal,
271 const char ** pStoredKey,
272 const char * key,
273 void * val )
274 {
275 TreeMapping * tm= (TreeMapping *)tree;
276
277 TreeNode * no;
278 TreeNode * dn;
279 TreeNode * nw;
280 int cmp;
281 int where;
282 int nwkey;
283
284 void * prevVal= (void *)0;
285 char * savedKey= (char *)0;
286 char * childKey;
287
288 if ( tm->trStatusFlag == TRsCLOSE )
289 { LDEB(tm->trStatusFlag); return -1; }
290
291 if ( ! tm->tr_root )
292 {
293 no= treeMakeNode();
294 if ( ! no )
295 { LDEB(no); return -1; }
296
297 if ( tm->trOwnKeys )
298 {
299 savedKey= treeSaveKey( key );
300 if ( ! savedKey )
301 { XDEB(savedKey); treeFreeNode( no ); return -1; }
302
303 }
304 else{ savedKey= (char *)key; }
305
306 no->no_L.nsKey= savedKey;
307 no->no_L.sl_val= val;
308 no->no_M.nsKey= (char *)0;
309 no->no_R.nsKey= (char *)0;
310 no->no_dn= (TreeNode *)0;
311
312 tm->tr_root= no;
313 tm->tr_curr= no;
314 tm->trCurrentDeleted= 0;
315 tm->tr_lfcu= savedKey;
316 if ( pStoredKey )
317 { *pStoredKey= tm->tr_lfcu; }
318 if ( pPrevVal )
319 { *pPrevVal= prevVal; }
320
321 return 0;
322 }
323
324 /* get leaf with key */
325 no= treeGetLeaf( tm->tr_root, key );
326
327 /********************************************************************/
328 /* Try to store value in LEAF no */
329 /* If an insertion between two values is necessary, The stored */
330 /* values are shifted to the right. */
331 /* */
332 /* Find out where to insert in leaf and whether key must be */
333 /* allocated. */
334 /* values of where: */
335 /* 0: before L */
336 /* 1: in L */
337 /* 2: before M */
338 /* 3: in M */
339 /* 4: before R */
340 /* 5: in R */
341 /* 6: after R */
342 /* */
343 /********************************************************************/
344
345 cmp= strcmp( key, no->no_L.nsKey );
346 if ( cmp < 0 ) { nwkey= 1; where= 0; }
347 else{
348 if ( cmp == 0 ) { nwkey= 0; where= 1; }
349 else{
350 if ( ! no->no_M.nsKey ) { nwkey= 1; where= 3; }
351 else{
352 cmp= strcmp( key, no->no_M.nsKey );
353 if ( cmp < 0 ) { nwkey= 1; where= 2; }
354 else{
355 if ( cmp == 0 ) { nwkey= 0; where= 3; }
356 else{
357 if ( ! no->no_R.nsKey ) { nwkey= 1; where= 5; }
358 else{
359 cmp= strcmp( key, no->no_R.nsKey );
360 if ( cmp < 0 ) { nwkey= 1; where= 4; }
361 else{
362 if ( cmp == 0 ) { nwkey= 0; where= 5; }
363 else { nwkey= 1; where= 6; }
364 }
365 }
366 }
367 }
368 }
369 }
370 }
371
372 /************************************/
373 /* allocate new key */
374 /* Refuse to update active trees */
375 /************************************/
376 if ( nwkey )
377 {
378 if ( tm->trStatusFlag != TRsINACTIVE )
379 { LDEB(tm->trStatusFlag); return -1; }
380
381 if ( tm->trOwnKeys )
382 {
383 savedKey= treeSaveKey( key );
384 if ( ! savedKey )
385 { XDEB(savedKey); treeFreeNode( no ); return -1; }
386
387 }
388 else{ savedKey= (char *)key; }
389 }
390
391 /* allocate overflow node */
392 if ( ( where % 2 ) == 0 && no->no_M.nsKey && no->no_R.nsKey )
393 {
394 dn= no->no_dn;
395 nw= treeMakeNode();
396 if ( ! nw )
397 { XDEB(nw); return -1; }
398
399 nw->no_R.nsKey= (char *)0;
400 nw->no_dn= dn;
401 }
402 else{
403 nw= (TreeNode *)0;
404 dn= (TreeNode *)0;
405 }
406
407 switch( where )
408 {
409 case 0:
410 /* before L */
411 if ( nw )
412 {
413 nw->no_M= no->no_R;
414 nw->no_L= no->no_M;
415 no->no_R.nsKey= (char *)0;
416 }
417 else{
418 no->no_R= no->no_M;
419 }
420 no->no_M= no->no_L;
421 no->no_L.nsKey= savedKey;
422 /*FALLTHROUGH*/
423
424 case 1:
425 /* in L */
426 if ( ! nwkey )
427 { prevVal= no->no_L.sl_val; }
428 no->no_L.sl_val= val;
429 tm->tr_curr= no;
430 tm->trCurrentDeleted= 0;
431 tm->tr_lfcu= no->no_L.nsKey;
432 if ( pStoredKey )
433 { *pStoredKey= tm->tr_lfcu; }
434 if ( pPrevVal )
435 { *pPrevVal= prevVal; }
436 break;
437
438 case 2:
439 /* before M */
440 if ( nw )
441 {
442 nw->no_M= no->no_R;
443 nw->no_L= no->no_M;
444 no->no_R.nsKey= (char *)0;
445 }
446 else{ no->no_R= no->no_M; }
447 no->no_M.nsKey= savedKey;
448 /*FALLTHROUGH*/
449
450 case 3:
451 /* in M */
452 if ( nwkey )
453 { no->no_M.nsKey= savedKey; }
454 else{ prevVal= no->no_M.sl_val; }
455 no->no_M.sl_val= val;
456 tm->tr_curr= no;
457 tm->trCurrentDeleted= 0;
458 tm->tr_lfcu= no->no_M.nsKey;
459 if ( pStoredKey )
460 { *pStoredKey= tm->tr_lfcu; }
461 if ( pPrevVal )
462 { *pPrevVal= prevVal; }
463 break;
464
465 case 4:
466 if ( ! nw )
467 { XDEB(nw); return -1; }
468 /* before R */
469 nw->no_M= no->no_R;
470 nw->no_L.nsKey= savedKey;
471 nw->no_L.sl_val= val;
472 no->no_R.nsKey= (char *)0;
473 tm->tr_curr= nw;
474 tm->trCurrentDeleted= 0;
475 tm->tr_lfcu= savedKey;
476 if ( pStoredKey )
477 { *pStoredKey= tm->tr_lfcu; }
478 if ( pPrevVal )
479 { *pPrevVal= prevVal; }
480 break;
481
482 case 5:
483 /* in R */
484 if ( nwkey )
485 { no->no_R.nsKey= savedKey; }
486 else{ prevVal= no->no_R.sl_val; }
487 no->no_R.sl_val= val;
488 tm->tr_curr= no;
489 tm->trCurrentDeleted= 0;
490 tm->tr_lfcu= no->no_R.nsKey;
491 if ( pStoredKey )
492 { *pStoredKey= tm->tr_lfcu; }
493 if ( pPrevVal )
494 { *pPrevVal= prevVal; }
495 break;
496
497 case 6:
498 if ( ! nw )
499 { XDEB(nw); return -1; }
500 /* after R */
501 nw->no_L= no->no_R;
502 nw->no_M.nsKey= savedKey;
503 nw->no_M.sl_val= val;
504 no->no_R.nsKey= (char *)0;
505 tm->tr_curr= nw;
506 tm->trCurrentDeleted= 0;
507 tm->tr_lfcu= savedKey;
508 if ( pStoredKey )
509 { *pStoredKey= tm->tr_lfcu; }
510 if ( pPrevVal )
511 { *pPrevVal= prevVal; }
512 break;
513
514 default:
515 LDEB(where);
516 return -1;
517 }
518
519 if ( ! nw )
520 { return 0; }
521
522 childKey= nw->no_L.nsKey;
523
524 /* descend tree and where necessary split nodes */
525 while( dn )
526 {
527 NodeSlot Hslot;
528
529 /* insert new node into parent. If the parent should be split */
530 /* continue; else return; */
531 if ( no == dn->no_L.sl_nod )
532 {
533 Hslot= dn->no_R;
534 dn->no_R= dn->no_M;
535 dn->no_M.nsKey= childKey;
536 dn->no_M.sl_nod= nw;
537 }
538 else{
539 if ( no == dn->no_M.sl_nod )
540 {
541 Hslot= dn->no_R;
542 dn->no_R.nsKey= childKey;
543 dn->no_R.sl_nod= nw;
544 }
545 else{
546 if ( no == dn->no_R.sl_nod )
547 {
548 Hslot.nsKey= childKey;
549 Hslot.sl_nod= nw;
550 }
551 else{ XDEB(no); return -1; }
552 }
553 }
554
555 if ( ! Hslot.nsKey )
556 { return 0; }
557
558 /* split node, insert information into new nodes */
559 if ( ! ( nw= treeMakeNode() ) )
560 { XDEB(nw); return -1; }
561
562 /* new values in new node */
563 nw->no_L.nsKey= (char *)0;
564 nw->no_L.sl_nod= dn->no_R.sl_nod;
565 nw->no_M= Hslot;
566 nw->no_R.nsKey= (char *)0;
567 nw->no_dn= dn->no_dn;
568
569 /* connect children */
570 nw->no_L.sl_nod->no_dn= nw;
571 nw->no_M.sl_nod->no_dn= nw;
572
573 /* remember key of new node; adapt old node */
574 childKey= dn->no_R.nsKey;
575 dn->no_R.nsKey= (char *)0;
576
577 /* step down */
578 no= dn;
579 dn= no->no_dn;
580 }
581
582 /* when we reach this place, every node in the descent of the tree */
583 /* was split. Make a new root */
584 dn= treeMakeNode();
585 if ( ! dn )
586 { XDEB(dn); return -1; }
587
588 dn->no_L.nsKey= (char *)0;
589 dn->no_L.sl_nod= no;
590 dn->no_M.nsKey= childKey;
591 dn->no_M.sl_nod= nw;
592 dn->no_R.nsKey= (char *)0;
593 dn->no_R.sl_nod= (TreeNode *)0;
594 dn->no_dn= (TreeNode *)0;
595
596 /* connect children */
597 dn->no_L.sl_nod->no_dn= dn;
598 dn->no_M.sl_nod->no_dn= dn;
599
600 nw->no_dn= dn;
601 no->no_dn= dn;
602 tm->tr_root= dn;
603
604 return 0;
605 }
606
607 /************************************************************************/
608 /* */
609 /* If there is any, return value stored at the first key < key */
610 /* If there is any, return value stored at the first key <= key */
611 /* */
612 /************************************************************************/
613
treeGetLX(void * tree,const char ** pKey,const char * key,int skew)614 static void * treeGetLX( void * tree,
615 const char ** pKey,
616 const char * key,
617 int skew )
618 {
619 TreeMapping * tm= (TreeMapping *)tree;
620
621 TreeNode * no;
622 int cmp;
623
624 if ( ! tm || ! tm->tr_root )
625 { *pKey= (char *)0; return (void *)0; }
626
627 if ( tm->trStatusFlag == TRsCLOSE )
628 { LDEB(tm->trStatusFlag); *pKey= (char *)0; return (void *)0; }
629
630 /* get leaf with key */
631 no= treeGetLeaf( tm->tr_root, key );
632 if ( ! no )
633 { XDEB(no); *pKey= (char *)0; return (void *)0; }
634
635 cmp= strcmp( key, no->no_L.nsKey );
636 if ( cmp > skew )
637 {
638 if ( no->no_M.nsKey )
639 {
640 cmp= strcmp( key, no->no_M.nsKey );
641 if ( cmp > skew )
642 {
643 if ( no->no_R.nsKey )
644 {
645 cmp= strcmp( key, no->no_R.nsKey );
646 if ( cmp > skew )
647 {
648 tm->tr_curr= no;
649 tm->trCurrentDeleted= 0;
650 *pKey= tm->tr_lfcu= no->no_R.nsKey;
651 return no->no_R.sl_val;
652 }
653 }
654
655 tm->tr_curr= no;
656 tm->trCurrentDeleted= 0;
657 *pKey= tm->tr_lfcu= no->no_M.nsKey;
658 return no->no_M.sl_val;
659 }
660 }
661
662 tm->tr_curr= no;
663 tm->trCurrentDeleted= 0;
664 *pKey= tm->tr_lfcu= no->no_L.nsKey;
665 return no->no_L.sl_val;
666 }
667
668 if ( ! ( no= treeGetPrevLeaf( no ) ) )
669 { *pKey= (char *)0; return (void *)0; }
670
671 tm->tr_curr= no;
672 tm->trCurrentDeleted= 0;
673 if ( no->no_R.nsKey )
674 {
675 *pKey= tm->tr_lfcu= no->no_R.nsKey;
676 return no->no_R.sl_val;
677 }
678
679 *pKey= tm->tr_lfcu= no->no_M.nsKey;
680 return no->no_M.sl_val;
681 }
682
utilTreeGetLT(void * tree,const char ** pKey,const char * key)683 void * utilTreeGetLT( void * tree,
684 const char ** pKey,
685 const char * key )
686 { return treeGetLX( tree, pKey, key, 0 ); }
687
utilTreeGetLE(void * tree,const char ** pKey,const char * key)688 void * utilTreeGetLE( void * tree,
689 const char ** pKey,
690 const char * key )
691 { return treeGetLX( tree, pKey, key, -1 ); }
692
693 /************************************************************************/
694 /* */
695 /* If there is any, return value stored at the first key > key */
696 /* If there is any, return value stored at the first key >= key */
697 /* */
698 /************************************************************************/
699
treeGetGX(void * tree,const char ** pKey,const char * key,int skew)700 static void * treeGetGX( void * tree,
701 const char ** pKey,
702 const char * key,
703 int skew )
704 {
705 TreeMapping * tm= (TreeMapping *)tree;
706
707 TreeNode * no;
708 int cmp;
709
710 if ( ! tree ||
711 ! ( no= tm->tr_root ) )
712 { *pKey= (char *)0; return (void *)0; }
713
714 if ( tm->trStatusFlag == TRsCLOSE )
715 { LDEB(tm->trStatusFlag); *pKey= (char *)0; return (void *)0; }
716
717 /* get leaf with key */
718 no= treeGetLeaf( no, key );
719
720 cmp= strcmp( key, no->no_L.nsKey );
721 if ( cmp < skew )
722 {
723 tm->tr_curr= no;
724 tm->trCurrentDeleted= 0;
725 *pKey= tm->tr_lfcu= no->no_L.nsKey;
726 return no->no_L.sl_val;
727 }
728
729 if ( ! no->no_M.nsKey )
730 { *pKey= (char *)0; return (void *)0; }
731
732 cmp= strcmp( key, no->no_M.nsKey );
733 if ( cmp < skew )
734 {
735 tm->tr_curr= no;
736 tm->trCurrentDeleted= 0;
737 *pKey= tm->tr_lfcu= no->no_M.nsKey;
738 return no->no_M.sl_val;
739 }
740
741 if ( no->no_R.nsKey )
742 {
743 cmp= strcmp( key, no->no_R.nsKey );
744 if ( cmp < skew )
745 {
746 tm->tr_curr= no;
747 tm->trCurrentDeleted= 0;
748 *pKey= tm->tr_lfcu= no->no_R.nsKey;
749 return no->no_R.sl_val;
750 }
751 }
752
753 if ( ! ( no= treeGetNextLeaf( no ) ) )
754 { return (void *)0; }
755
756 tm->tr_curr= no;
757 tm->trCurrentDeleted= 0;
758 *pKey= tm->tr_lfcu= no->no_L.nsKey;
759 return no->no_L.sl_val;
760 }
761
utilTreeGetGT(void * tree,const char ** pKey,const char * key)762 void * utilTreeGetGT( void * tree,
763 const char ** pKey,
764 const char * key )
765 { return treeGetGX( tree, pKey, key, 0 ); }
766
utilTreeGetGE(void * tree,const char ** pKey,const char * key)767 void * utilTreeGetGE( void * tree,
768 const char ** pKey,
769 const char * key )
770 { return treeGetGX( tree, pKey, key, 1 ); }
771
772 /************************************************************************/
773 /* */
774 /* If there is any, return value stored at key. */
775 /* */
776 /************************************************************************/
777
utilTreeGetEQ(const void * tree,const char ** pStoredKey,const char * key)778 void * utilTreeGetEQ( const void * tree,
779 const char ** pStoredKey,
780 const char * key )
781 {
782 TreeMapping * tm= (TreeMapping *)tree;
783
784 TreeNode * no;
785 int cmp;
786
787 if ( ! tree )
788 {
789 if ( pStoredKey )
790 { *pStoredKey= (const char *)0; }
791
792 return (void *)0;
793 }
794 no= tm->tr_root;
795 if ( ! no )
796 {
797 if ( pStoredKey )
798 { *pStoredKey= (const char *)0; }
799
800 return (void *)0;
801 }
802
803 if ( tm->trStatusFlag == TRsCLOSE )
804 {
805 LDEB(tm->trStatusFlag);
806
807 if ( pStoredKey )
808 { *pStoredKey= (const char *)0; }
809
810 return (void *)0;
811 }
812
813 /* get leaf with key */
814 no= treeGetLeaf( no, key );
815 if ( ! no )
816 {
817 XDEB(no);
818
819 if ( pStoredKey )
820 { *pStoredKey= (const char *)0; }
821
822 return (void *)0;
823 }
824
825 cmp= strcmp( key, no->no_L.nsKey );
826 if ( cmp < 0 )
827 {
828 if ( pStoredKey )
829 { *pStoredKey= (const char *)0; }
830
831 return (void *)0;
832 }
833
834 if ( cmp == 0 )
835 {
836 tm->tr_curr= no;
837 tm->trCurrentDeleted= 0;
838
839 if ( pStoredKey )
840 { *pStoredKey= tm->tr_lfcu= no->no_L.nsKey; }
841
842 return no->no_L.sl_val;
843 }
844
845 if ( ! no->no_M.nsKey )
846 {
847 if ( pStoredKey )
848 { *pStoredKey= (const char *)0; }
849
850 return (void *)0;
851 }
852
853 cmp= strcmp( key, no->no_M.nsKey );
854 if ( cmp < 0 )
855 {
856 if ( pStoredKey )
857 { *pStoredKey= (const char *)0; }
858
859 return (void *)0;
860 }
861
862 if ( cmp == 0 )
863 {
864 tm->tr_curr= no;
865 tm->trCurrentDeleted= 0;
866
867 if ( pStoredKey )
868 { *pStoredKey= tm->tr_lfcu= no->no_M.nsKey; }
869
870 return no->no_M.sl_val;
871 }
872
873 if ( ! no->no_R.nsKey )
874 {
875 if ( pStoredKey )
876 { *pStoredKey= (const char *)0; }
877
878 return (void *)0;
879 }
880
881 cmp= strcmp( key, no->no_R.nsKey );
882 if ( cmp == 0 )
883 {
884 tm->tr_curr= no;
885 tm->trCurrentDeleted= 0;
886
887 if ( pStoredKey )
888 { *pStoredKey= tm->tr_lfcu= no->no_R.nsKey; }
889
890 return no->no_R.sl_val;
891 }
892
893 if ( pStoredKey )
894 { *pStoredKey= (const char *)0; }
895 return (void *)0;
896 }
897
898 /************************************************************************/
899 /* fills slots in a node from an array, Is used below for the */
900 /* redistribution of the children. Note that leaves are treated */
901 /* differently from other nodes in two ways: */
902 /* - Their Left hand slot gets a key. */
903 /* - As they do not have children, these are not connected to parent */
904 /************************************************************************/
905
trfillslots(const NodeSlot * hs,TreeNode * no,int n,int leaf)906 static void trfillslots( const NodeSlot * hs,
907 TreeNode * no,
908 int n,
909 int leaf )
910 {
911 if ( leaf )
912 {
913 no->no_L= *(hs++);
914 no->no_M= *(hs++);
915 if ( n != 3 )
916 { no->no_R.nsKey= (char *)0; return; }
917 no->no_R= *hs;
918 }
919 else{
920 TreeNode * child;
921
922 child= hs->sl_nod;
923 no->no_L.sl_nod= child; child->no_dn= no;
924 no->no_L.nsKey= (char *)0;
925
926 hs++;
927 child= hs->sl_nod;
928 no->no_M= *(hs++); child->no_dn= no;
929
930 if ( n != 3 )
931 { no->no_R.nsKey= (char *)0; return; }
932
933 child= hs->sl_nod;
934 no->no_R= *hs; child->no_dn= no;
935 }
936
937 return;
938 }
939
940 /************************************************************************/
941 /* */
942 /* Delete a node from a tree. All gotos jump to the same label from */
943 /* above. This label cannot be reached otherwise */
944 /* */
945 /************************************************************************/
946
utilTreeDeleteEQ(void * tree,const char * key,UTIL_TREE_CALLBACK callback,void * through)947 int utilTreeDeleteEQ( void * tree,
948 const char * key,
949 UTIL_TREE_CALLBACK callback,
950 void * through )
951 {
952 const char * storedKey;
953
954 if ( ! utilTreeGetEQ( tree, &storedKey, key ) &&
955 ! storedKey )
956 { return -1; }
957
958 return utilTreeDeleteCurrent( tree, callback, through );
959 }
960
utilTreeDeleteCurrent(void * tree,UTIL_TREE_CALLBACK callback,void * through)961 int utilTreeDeleteCurrent( void * tree,
962 UTIL_TREE_CALLBACK callback,
963 void * through )
964 {
965 TreeMapping * tm= (TreeMapping *)tree;
966
967 TreeNode * no;
968 TreeNode * dn;
969 TreeNode * nh;
970 char * Lkey, * Nkey;
971 int cur; /* idea of currency */
972 int n; /* # of slots do distribute */
973 static NodeSlot Hslot[7]; /* slots to distribute */
974 int leaf= 1; /* working in leaf? */
975 char * lfcu; /* currency in leaf */
976
977 if ( ! tree )
978 { return -1; }
979
980 no= tm->tr_curr;
981 lfcu= tm->tr_lfcu;
982 if ( ! no || ! lfcu || tm->trCurrentDeleted )
983 { return -1; }
984
985 if ( tm->trStatusFlag != TRsINACTIVE )
986 { LDEB(tm->trStatusFlag); return -1; }
987
988 if ( lfcu == no->no_L.nsKey )
989 {
990 /********************************************************/
991 /* left most deletion: patch pointer in parent node */
992 /* that refers to this slot */
993 /********************************************************/
994
995 if ( callback )
996 {
997 (void) (*callback)( no->no_L.nsKey, no->no_L.sl_val, through );
998 }
999
1000 Lkey= no->no_L.nsKey;
1001 Nkey= no->no_M.nsKey;
1002 dn= no; nh= dn;
1003 while( ( dn= dn->no_dn ) )
1004 {
1005 if ( dn->no_M.nsKey == Lkey )
1006 { dn->no_M.nsKey= Nkey; break; }
1007 if ( dn->no_R.nsKey == Lkey )
1008 { dn->no_R.nsKey= Nkey; break; }
1009 nh= dn;
1010 }
1011 if ( tm->trOwnKeys )
1012 { treeFreeKey( Lkey ); }
1013 /* shift */
1014 no->no_L= no->no_M;
1015 no->no_M= no->no_R;
1016 no->no_R.nsKey= (char *)0;
1017 tm->tr_curr= no;
1018 tm->tr_lfcu= no->no_L.nsKey;
1019 tm->trCurrentDeleted= 1;
1020
1021 cur= 0;
1022 }
1023 else{
1024 if ( lfcu == no->no_M.nsKey )
1025 {
1026 if ( callback )
1027 {
1028 (void) (*callback)( no->no_M.nsKey, no->no_M.sl_val, through );
1029 }
1030
1031 if ( tm->trOwnKeys )
1032 { treeFreeKey( no->no_M.nsKey ); }
1033 no->no_M= no->no_R;
1034 no->no_R.nsKey= (char *)0;
1035 tm->tr_curr= no;
1036 tm->tr_lfcu= no->no_M.nsKey;
1037 tm->trCurrentDeleted= 1;
1038 cur= 1;
1039 }
1040 else{
1041 if ( callback )
1042 {
1043 (void) (*callback)( no->no_R.nsKey, no->no_R.sl_val, through );
1044 }
1045
1046 if ( tm->trOwnKeys )
1047 { treeFreeKey( no->no_R.nsKey ); }
1048
1049 no->no_R.nsKey= (char *)0;
1050 tm->tr_lfcu= (char *)0;
1051 tm->trCurrentDeleted= 1;
1052 return 0;
1053 }
1054 }
1055
1056 /* exception: root is leaf. */
1057 if ( no == tm->tr_root )
1058 {
1059 /* deletion of last item in tree? */
1060 if ( ! no->no_L.nsKey )
1061 {
1062 treeFreeNode( no );
1063 tm->tr_root= (TreeNode *)0;
1064 tm->tr_curr= (TreeNode *)0;
1065 tm->tr_lfcu= (char *)0;
1066 }
1067 /* root is leaf and less than two items is allowed. */
1068 return 0;
1069 }
1070
1071 /* walk down */
1072 while( ( dn= no->no_dn ) )
1073 {
1074 /* still two children left ? */
1075 if ( no->no_M.nsKey ) { return 0; }
1076
1077 /* collect all slots in Hslot */
1078 n= 0;
1079 nh= dn->no_L.sl_nod;
1080 /* if ( leaf && nh == no ) { cur += n; } */
1081 Hslot[n++]= nh->no_L;
1082 if ( nh->no_M.nsKey )
1083 {
1084 Hslot[n++]= nh->no_M;
1085 if ( nh->no_R.nsKey )
1086 { Hslot[n++]= nh->no_R; }
1087 }
1088 nh= dn->no_M.sl_nod;
1089 if ( leaf && nh == no ) { cur += n; }
1090 if ( leaf )
1091 { Hslot[n++]= nh->no_L; }
1092 else{
1093 Hslot[n ].nsKey= dn->no_M.nsKey;
1094 Hslot[n++].sl_ptr= nh->no_L.sl_ptr;
1095 }
1096 if ( nh->no_M.nsKey )
1097 {
1098 Hslot[n++]= nh->no_M;
1099 if ( nh->no_R.nsKey )
1100 { Hslot[n++]= nh->no_R; }
1101 }
1102 if ( dn->no_R.nsKey )
1103 {
1104 nh= dn->no_R.sl_nod;
1105 if ( leaf && nh == no ) { cur += n; }
1106 if ( leaf )
1107 { Hslot[n++]= nh->no_L; }
1108 else{
1109 Hslot[n ].nsKey= dn->no_R.nsKey;
1110 Hslot[n++].sl_ptr= nh->no_L.sl_ptr;
1111 }
1112 if ( nh->no_M.nsKey )
1113 {
1114 Hslot[n++]= nh->no_M;
1115 if ( nh->no_R.nsKey )
1116 { Hslot[n++]= nh->no_R; }
1117 }
1118 }
1119
1120 if ( leaf )
1121 {
1122 if ( cur < n )
1123 { tm->tr_lfcu= Hslot[cur].nsKey; }
1124 else{ tm->tr_lfcu= (char *)0; }
1125 }
1126
1127 switch( n )
1128 {
1129 case 3: /* from 2,2 */
1130 trfillslots( Hslot , dn->no_L.sl_nod, 3, leaf );
1131 if ( leaf ) { tm->tr_curr= dn->no_L.sl_nod; }
1132 treeFreeNode( dn->no_M.sl_nod );
1133 dn->no_M.nsKey= (char *)0;
1134 break;
1135 case 4: /* from 3,2 or 2,3 */
1136 trfillslots( Hslot , dn->no_L.sl_nod, 2, leaf );
1137 trfillslots( Hslot+ 2, dn->no_M.sl_nod, 2, leaf );
1138 dn->no_M.nsKey= Hslot[2].nsKey;
1139 if ( leaf )
1140 {
1141 if ( cur < 2 ) { tm->tr_curr= dn->no_L.sl_nod; }
1142 else { tm->tr_curr= dn->no_M.sl_nod; }
1143 }
1144 return 0;
1145 case 5: /* from 2,2,2 */
1146 trfillslots( Hslot , dn->no_L.sl_nod, 3, leaf );
1147 trfillslots( Hslot+ 3, dn->no_M.sl_nod, 2, leaf );
1148 dn->no_M.nsKey= Hslot[3].nsKey;
1149 if ( leaf )
1150 {
1151 if ( cur < 3 ) { tm->tr_curr= dn->no_L.sl_nod; }
1152 else { tm->tr_curr= dn->no_M.sl_nod; }
1153 }
1154 treeFreeNode( dn->no_R.sl_nod );
1155 dn->no_R.nsKey= (char *)0;
1156 break;
1157 case 6: /* from 2,2,3 or 2,3,2 or 3,2,2 */
1158 # ifdef YOU_MIGHT_DO_THIS
1159 trfillslots( Hslot , dn->no_L.sl_nod, 3, leaf );
1160 trfillslots( Hslot+3 , dn->no_M.sl_nod, 3, leaf );
1161 dn->no_M.nsKey= Hslot[3].nsKey;
1162 if ( leaf )
1163 {
1164 if ( cur < 3 ) { tm->tr_curr= dn->no_L.sl_nod; }
1165 else { tm->tr_curr= dn->no_M.sl_nod; }
1166 }
1167 treeFreeNode( dn->no_R.sl_nod );
1168 dn->no_R.nsKey= (char *)0;
1169 break;
1170 # else
1171 trfillslots( Hslot , dn->no_L.sl_nod, 2, leaf );
1172 trfillslots( Hslot+ 2, dn->no_M.sl_nod, 2, leaf );
1173 trfillslots( Hslot+ 4, dn->no_R.sl_nod, 2, leaf );
1174 dn->no_M.nsKey= Hslot[2].nsKey;
1175 dn->no_R.nsKey= Hslot[4].nsKey;
1176 if ( leaf )
1177 {
1178 if ( cur < 2 ) { tm->tr_curr= dn->no_L.sl_nod; }
1179 else{
1180 if ( cur < 4 ) { tm->tr_curr= dn->no_M.sl_nod; }
1181 else { tm->tr_curr= dn->no_R.sl_nod; }
1182 }
1183 }
1184 return 0;
1185 # endif
1186 case 7: /* from 3,3,2 or 3,2,3 or 2,3,3 */
1187 trfillslots( Hslot , dn->no_L.sl_nod, 3, leaf );
1188 trfillslots( Hslot+3 , dn->no_M.sl_nod, 2, leaf );
1189 trfillslots( Hslot+5 , dn->no_R.sl_nod, 2, leaf );
1190 dn->no_M.nsKey= Hslot[3].nsKey;
1191 dn->no_R.nsKey= Hslot[5].nsKey;
1192 if ( leaf )
1193 {
1194 if ( cur < 3 ) { tm->tr_curr= dn->no_L.sl_nod; }
1195 else{
1196 if ( cur < 5 ) { tm->tr_curr= dn->no_M.sl_nod; }
1197 else { tm->tr_curr= dn->no_R.sl_nod; }
1198 }
1199 }
1200 return 0;
1201 default:
1202 LDEB(n); return -1;
1203 }
1204
1205 no= dn; leaf= 0;
1206 }
1207
1208 /* more than one slot in root ? */
1209 if ( no->no_M.nsKey )
1210 { return 0; }
1211
1212 /* no->no_L.sl_slot becomes new root. Old root is deleted */
1213 tm->tr_root= no->no_L.sl_nod;
1214 no->no_L.sl_nod->no_dn= (TreeNode *)0;
1215 treeFreeNode( no );
1216
1217 return 0;
1218 }
1219
1220 /************************************************************************/
1221 /* */
1222 /* shift currency in tree to the left and return value stored there */
1223 /* */
1224 /************************************************************************/
1225
utilTreeGetPrevious(void * tree,const char ** pKey)1226 void * utilTreeGetPrevious( void * tree,
1227 const char ** pKey )
1228 {
1229 TreeMapping * tm= (TreeMapping *)tree;
1230
1231 TreeNode * no;
1232 char * lfcu;
1233
1234 if ( ! tree )
1235 { *pKey= (char *)0; return (void *)0; }
1236 if ( tm->trStatusFlag == TRsCLOSE )
1237 { LDEB(tm->trStatusFlag); *pKey= (char *)0; return (void *)0; }
1238
1239 no= tm->tr_curr;
1240 if ( ! no )
1241 { *pKey= (char *)0; return (void *)0; }
1242
1243 lfcu= tm->tr_lfcu;
1244 if ( lfcu )
1245 {
1246 if ( no->no_M.nsKey )
1247 {
1248 if ( lfcu == no->no_M.nsKey )
1249 {
1250 tm->trCurrentDeleted= 0;
1251 *pKey= tm->tr_lfcu= no->no_L.nsKey;
1252 return no->no_L.sl_val;
1253 }
1254 if ( lfcu == no->no_R.nsKey )
1255 {
1256 tm->trCurrentDeleted= 0;
1257 *pKey= tm->tr_lfcu= no->no_M.nsKey;
1258 return no->no_M.sl_val;
1259 }
1260 }
1261
1262 /* shift to previous node */
1263 no= treeGetPrevLeaf( no );
1264 if ( ! no )
1265 { *pKey= (char *)0; return (void *)0; }
1266 }
1267 /* else simply last in this node */
1268
1269 if ( no->no_R.nsKey )
1270 {
1271 tm->trCurrentDeleted= 0;
1272 tm->tr_curr= no;
1273 *pKey= tm->tr_lfcu= no->no_R.nsKey;
1274 return no->no_R.sl_val;
1275 }
1276
1277 if ( no->no_M.nsKey )
1278 {
1279 tm->trCurrentDeleted= 0;
1280 tm->tr_curr= no;
1281 *pKey= tm->tr_lfcu= no->no_M.nsKey;
1282 return no->no_M.sl_val;
1283 }
1284
1285 if ( no->no_L.nsKey )
1286 {
1287 tm->trCurrentDeleted= 0;
1288 tm->tr_curr= no;
1289 *pKey= tm->tr_lfcu= no->no_L.nsKey;
1290 return no->no_L.sl_val;
1291 }
1292
1293 XDEB(no->no_L.nsKey);
1294 *pKey= (char *)0; return (void *)0;
1295 }
1296
1297 /************************************************************************/
1298 /* */
1299 /* shift currency in tree to the right and return value stored there */
1300 /* */
1301 /************************************************************************/
1302
utilTreeGetNext(void * tree,const char ** pKey)1303 void * utilTreeGetNext( void * tree,
1304 const char ** pKey )
1305 {
1306 TreeMapping * tm= (TreeMapping *)tree;
1307 TreeNode * no;
1308 char * lfcu;
1309
1310 if ( ! tree )
1311 { *pKey= (char *)0; return (void *)0; }
1312 if ( tm->trStatusFlag == TRsCLOSE )
1313 { LDEB(tm->trStatusFlag); *pKey= (char *)0; return (void *)0; }
1314
1315 no= tm->tr_curr;
1316 if ( ! no )
1317 { *pKey= (char *)0; return (void *)0; }
1318
1319 lfcu= tm->tr_lfcu;
1320 if ( lfcu )
1321 {
1322 if ( tm->trCurrentDeleted )
1323 {
1324 tm->trCurrentDeleted= 0;
1325
1326 *pKey= lfcu;
1327
1328 if ( lfcu == no->no_L.nsKey )
1329 { return no->no_L.sl_val; }
1330 if ( lfcu == no->no_M.nsKey )
1331 { return no->no_M.sl_val; }
1332
1333 return no->no_R.sl_val;
1334 }
1335
1336 if ( lfcu == no->no_L.nsKey && no->no_M.nsKey )
1337 {
1338 tm->trCurrentDeleted= 0;
1339 *pKey= tm->tr_lfcu= no->no_M.nsKey;
1340 return no->no_M.sl_val;
1341 }
1342
1343 if ( lfcu == no->no_M.nsKey && no->no_R.nsKey )
1344 {
1345 tm->trCurrentDeleted= 0;
1346 *pKey= tm->tr_lfcu= no->no_R.nsKey;
1347 return no->no_R.sl_val;
1348 }
1349 }
1350
1351 if ( ! ( no= treeGetNextLeaf( no ) ) )
1352 { *pKey= (char *)0; return (void *)0; }
1353
1354 tm->tr_curr= no;
1355 tm->trCurrentDeleted= 0;
1356 *pKey= tm->tr_lfcu= no->no_L.nsKey;
1357 return no->no_L.sl_val;
1358 }
1359
1360 /************************************************************************/
1361 /* */
1362 /* return value stored on current leaf of tree */
1363 /* */
1364 /************************************************************************/
1365
utilTreeGetCurrent(void * tree,const char ** pKey)1366 void * utilTreeGetCurrent( void * tree,
1367 const char ** pKey )
1368 {
1369 TreeMapping * tm= (TreeMapping *)tree;
1370 TreeNode * no;
1371 char * lfcu;
1372
1373 if ( ! tree )
1374 { *pKey= (char *)0; return (void *)0; }
1375 if ( tm->trStatusFlag == TRsCLOSE )
1376 { LDEB(tm->trStatusFlag); *pKey= (char *)0; return (void *)0; }
1377
1378 no= tm->tr_curr;
1379 lfcu= tm->tr_lfcu;
1380
1381 if ( ! no || ! lfcu || tm->trCurrentDeleted )
1382 { *pKey= (char *)0; return (void *)0; }
1383
1384 *pKey= lfcu;
1385 if ( lfcu == no->no_L.nsKey ) { return no->no_L.sl_val; }
1386 if ( lfcu == no->no_M.nsKey ) { return no->no_M.sl_val; }
1387 return no->no_R.sl_val;
1388 }
1389
1390 /************************************************************************/
1391 /* */
1392 /* return value stored on first leaf of tree */
1393 /* */
1394 /************************************************************************/
1395
utilTreeGetFirst(void * tree,const char ** pKey)1396 void * utilTreeGetFirst( void * tree,
1397 const char ** pKey )
1398 {
1399 TreeMapping * tm= (TreeMapping *)tree;
1400 TreeNode * no;
1401
1402 if ( ! tree )
1403 { *pKey= (char *)0; return (void *)0; }
1404 if ( tm->trStatusFlag == TRsCLOSE )
1405 { LDEB(tm->trStatusFlag); *pKey= (char *)0; return (void *)0; }
1406
1407 no= tm->tr_root;
1408 if ( ! no )
1409 { *pKey= (char *)0; return (void *)0; }
1410
1411 /* walk to leftmost leaf */
1412 while( ! no->no_L.nsKey )
1413 { no= no->no_L.sl_nod; }
1414
1415 /* set currency */
1416 tm->tr_curr= no;
1417 tm->trCurrentDeleted= 0;
1418 *pKey= tm->tr_lfcu= no->no_L.nsKey;
1419
1420 return no->no_L.sl_val;
1421 }
1422
1423 /************************************************************************/
1424 /* */
1425 /* return value stored on last leaf of tree */
1426 /* */
1427 /************************************************************************/
1428
utilTreeGetLast(void * tree,const char ** pKey)1429 void * utilTreeGetLast( void * tree,
1430 const char ** pKey )
1431 {
1432 TreeMapping * tm= (TreeMapping *)tree;
1433 TreeNode * no;
1434
1435 if ( ! tree )
1436 { *pKey= (char *)0; return (void *)0; }
1437 if ( tm->trStatusFlag == TRsCLOSE )
1438 { LDEB(tm->trStatusFlag); *pKey= (char *)0; return (void *)0; }
1439
1440 no= tm->tr_root;
1441 if ( ! no )
1442 { *pKey= (char *)0; return (void *)0; }
1443
1444 /* walk to rightmost leaf */
1445 while( ! no->no_L.nsKey )
1446 {
1447 if ( no->no_R.nsKey )
1448 { no= no->no_R.sl_nod; }
1449 else{ no= no->no_M.sl_nod; }
1450 }
1451
1452 tm->tr_curr= no;
1453
1454 if ( no->no_R.nsKey )
1455 {
1456 tm->trCurrentDeleted= 0;
1457 *pKey= tm->tr_lfcu= no->no_R.nsKey;
1458 return no->no_R.sl_val;
1459 }
1460
1461 if ( no->no_M.nsKey )
1462 {
1463 tm->trCurrentDeleted= 0;
1464 *pKey= tm->tr_lfcu= no->no_M.nsKey;
1465 return no->no_M.sl_val;
1466 }
1467
1468 if ( no->no_L.nsKey )
1469 {
1470 /********************************************************/
1471 /* ONLY possible when root is leaf with one slot. */
1472 /********************************************************/
1473 tm->trCurrentDeleted= 0;
1474 *pKey= tm->tr_lfcu= no->no_L.nsKey;
1475 return no->no_L.sl_val;
1476 }
1477
1478 XDEB(no->no_L.nsKey);
1479 *pKey= (char *)0; return (void *)0;
1480 }
1481
1482 /************************************************************************/
1483 /* */
1484 /* call callback for all stored name, value combinations */
1485 /* */
1486 /************************************************************************/
1487
utilTreeForAll(void * tree,int stopOnFailure,UTIL_TREE_CALLBACK callback,void * through)1488 int utilTreeForAll( void * tree,
1489 int stopOnFailure,
1490 UTIL_TREE_CALLBACK callback,
1491 void * through )
1492 {
1493 TreeMapping * tm= (TreeMapping *)tree;
1494 TreeNode * no;
1495
1496 int oldStatusFlag;
1497 int rval= 0;
1498
1499 if ( ! tree )
1500 { return 0; }
1501 if ( tm->trStatusFlag == TRsCLOSE )
1502 { LDEB(tm->trStatusFlag); return -1; }
1503
1504 no= tm->tr_root;
1505 if ( ! no )
1506 { return 0; }
1507
1508 oldStatusFlag= tm->trStatusFlag;
1509 tm->trStatusFlag= TRsALL;
1510
1511 /* walk to leftmost leaf */
1512 while( ! no->no_L.nsKey )
1513 { no= no->no_L.sl_nod; }
1514
1515 while( no ) /* for all leaves */
1516 {
1517 if ( (*callback)( no->no_L.nsKey, no->no_L.sl_val, through ) )
1518 {
1519 rval= -1;
1520 if ( stopOnFailure )
1521 { break; }
1522 }
1523
1524 if ( no->no_M.nsKey )
1525 {
1526 if ( (*callback)( no->no_M.nsKey, no->no_M.sl_val, through ) )
1527 {
1528 rval= -1;
1529 if ( stopOnFailure )
1530 { break; }
1531 }
1532
1533 if ( no->no_R.nsKey )
1534 {
1535 if ( (*callback)( no->no_R.nsKey, no->no_R.sl_val, through ) )
1536 {
1537 rval= -1;
1538 if ( stopOnFailure )
1539 { break; }
1540 }
1541 }
1542 }
1543
1544 no= treeGetNextLeaf( no );
1545 }
1546
1547 tm->trStatusFlag= oldStatusFlag;
1548
1549 if ( stopOnFailure )
1550 { return rval; }
1551 else{ return 0; }
1552 }
1553
1554 /************************************************************************/
1555 /* */
1556 /* Free the whole tree. Possibly call a callback for all stored */
1557 /* values. */
1558 /* */
1559 /* The function of the callback is to free the stored values without */
1560 /* having to traverse the tree twice. */
1561 /* */
1562 /************************************************************************/
1563
utilTreeFreeTree(void * tree,UTIL_TREE_CALLBACK callback,void * through)1564 int utilTreeFreeTree( void * tree,
1565 UTIL_TREE_CALLBACK callback,
1566 void * through )
1567 {
1568 TreeMapping * tm= (TreeMapping *)tree;
1569 TreeNode * no;
1570 TreeNode * dn;
1571
1572 if ( tm->trStatusFlag != TRsINACTIVE )
1573 { XDEB(tm->trStatusFlag); return -1; }
1574 tm->trStatusFlag= TRsCLOSE;
1575
1576 no= tm->tr_root;
1577
1578 while( no )
1579 {
1580 /* walk to leftmost leaf */
1581 while( ! no->no_L.nsKey )
1582 { no= no->no_L.sl_nod; }
1583
1584 if ( callback )
1585 { (*callback)( no->no_L.nsKey, no->no_L.sl_val, through ); }
1586 if ( tm->trOwnKeys )
1587 { treeFreeKey( no->no_L.nsKey ); }
1588
1589 if ( no->no_M.nsKey )
1590 {
1591 if ( callback )
1592 { (*callback)( no->no_M.nsKey, no->no_M.sl_val, through ); }
1593 if ( tm->trOwnKeys )
1594 { treeFreeKey( no->no_M.nsKey ); }
1595
1596 if ( no->no_R.nsKey )
1597 {
1598 if ( callback )
1599 { (*callback)( no->no_R.nsKey, no->no_R.sl_val, through ); }
1600 if ( tm->trOwnKeys )
1601 { treeFreeKey( no->no_R.nsKey ); }
1602 }
1603 }
1604
1605 for (;;)
1606 {
1607 dn= no->no_dn;
1608 if ( ! dn )
1609 {
1610 treeFreeNode( no );
1611 no= dn;
1612 break;
1613 }
1614
1615 /* redescent from leftmost */
1616 if ( dn->no_L.sl_nod == no )
1617 {
1618 treeFreeNode( no );
1619 no= dn->no_M.sl_nod;
1620 break;
1621 }
1622
1623 /* redescent from middle */
1624 if ( dn->no_M.sl_nod == no )
1625 {
1626 /* is there a right hand branch ? */
1627 if ( dn->no_R.nsKey )
1628 { treeFreeNode( no ); no= dn->no_R.sl_nod; break; }
1629 }
1630
1631 /* redescent from last */
1632 treeFreeNode( no );
1633 no= dn;
1634 }
1635 }
1636
1637 treeFreeTree( tree );
1638 return 0;
1639 }
1640
1641 /************************************************************************/
1642 /* */
1643 /* Utility callback: Free the values when a tree is closed. */
1644 /* */
1645 /************************************************************************/
1646 /* */
1647 /*ARGSUSED*/
utilTreeFreeValue(const char * key,void * val,void * through)1648 int utilTreeFreeValue( const char * key,
1649 void * val,
1650 void * through )
1651 {
1652 if ( val )
1653 { free( val ); }
1654
1655 return 0;
1656 }
1657