1 /*===========================================================================
2 *
3 *                            PUBLIC DOMAIN NOTICE
4 *               National Center for Biotechnology Information
5 *
6 *  This software/database is a "United States Government Work" under the
7 *  terms of the United States Copyright Act.  It was written as part of
8 *  the author's official duties as a United States Government employee and
9 *  thus cannot be copyrighted.  This software/database is freely available
10 *  to the public for use. The National Library of Medicine and the U.S.
11 *  Government have not placed any restriction on its use or reproduction.
12 *
13 *  Although all reasonable efforts have been taken to ensure the accuracy
14 *  and reliability of the software and data, the NLM and the U.S.
15 *  Government do not and cannot warrant the performance or results that
16 *  may be obtained by using this software or data. The NLM and the U.S.
17 *  Government disclaim all warranties, express or implied, including
18 *  warranties of performance, merchantability or fitness for any particular
19 *  purpose.
20 *
21 *  Please cite the author in any work or product based on this material.
22 *
23 * ===========================================================================
24 *
25 */
26 
27 #include <klib/extern.h>
28 #include <klib/container.h>
29 #include <klib/rc.h>
30 #include <sysalloc.h>
31 
32 #include <stdlib.h>
33 #include <string.h>
34 #include <errno.h>
35 #include <assert.h>
36 
37 
38 /*--------------------------------------------------------------------------
39  * SLNode
40  *  singly linked node
41  */
42 
43 #if 0
44 /* SLNodeFindNext
45  *  find next element satisfying criteria
46  */
47 LIB_EXPORT SLNode* CC SLNodeFindNext ( const SLNode *p, bool ( CC * f ) ( const SLNode *n ) )
48 {
49     if ( p != NULL )
50     {
51         SLNode *n = p -> next;
52         while ( n != NULL )
53         {
54             if ( ( * f ) ( n ) )
55                 return n;
56             n = n -> next;
57         }
58     }
59     return NULL;
60 }
61 #endif
62 
63 
64 /*--------------------------------------------------------------------------
65  * SLList
66  *  singly linked list
67  */
68 
69 /* SLListPushTail
70  *  push a single node onto tail of list
71  */
SLListPushTail(SLList * sl,SLNode * n)72 LIB_EXPORT void CC SLListPushTail ( SLList *sl, SLNode *n )
73 {
74     if ( sl != NULL && n != NULL )
75     {
76         if ( sl -> tail == NULL )
77             sl -> head = sl -> tail = n;
78         else
79         {
80             sl -> tail -> next = n;
81             sl -> tail = n;
82         }
83         n -> next = NULL;
84     }
85 }
86 
87 /* SLListPopHead
88  *  pop a single node from head of list
89  */
SLListPopHead(SLList * sl)90 LIB_EXPORT SLNode* CC SLListPopHead ( SLList *sl )
91 {
92     if ( sl != NULL )
93     {
94         SLNode *n = sl -> head;
95         if ( n != NULL )
96         {
97             sl -> head = n -> next;
98             if ( n -> next == NULL )
99                 sl -> tail = NULL;
100             n -> next = NULL;
101         }
102         return n;
103     }
104     return NULL;
105 }
106 
107 /* SLListPopTail
108  *  pop a single node from tail of list
109  */
SLListPopTail(SLList * sl)110 LIB_EXPORT SLNode* CC SLListPopTail ( SLList *sl )
111 {
112     if ( sl != NULL )
113     {
114         SLNode *n = sl -> head;
115         if ( n != NULL )
116         {
117             SLNode *tail = sl -> tail;
118             if ( n == tail )
119             {
120                 sl -> head = sl -> tail = NULL;
121                 n -> next = NULL;
122                 return n;
123             }
124             while ( n -> next != tail )
125                 n = n -> next;
126             sl -> tail = n;
127             n -> next = NULL;
128             return tail;
129         }
130     }
131     return NULL;
132 }
133 
134 /* SLListUnlink
135  *  removes a designated node from list
136  */
SLListUnlink(SLList * sl,SLNode * n)137 LIB_EXPORT void CC SLListUnlink ( SLList *sl, SLNode *n )
138 {
139     if ( sl != NULL && n != NULL )
140     {
141         SLNode *p = sl -> head;
142         if ( p == n )
143         {
144             sl -> head = p -> next;
145             if ( p -> next == NULL )
146                 sl -> tail = NULL;
147         }
148         else while ( p != NULL )
149         {
150             if ( p -> next == n )
151             {
152                 p -> next = n -> next;
153                 if ( n -> next == NULL )
154                     sl -> tail = p;
155                 break;
156             }
157             p = p -> next;
158         }
159         n -> next = NULL;
160     }
161 }
162 
163 /* SLListForEach
164  *  executes a function on each list element
165  */
SLListForEach(const SLList * sl,void (CC * f)(SLNode * n,void * data),void * data)166 LIB_EXPORT void CC SLListForEach ( const SLList *sl,
167     void ( CC * f ) ( SLNode *n, void *data ), void *data )
168 {
169     if ( sl != NULL )
170     {
171         SLNode *n = sl -> head;
172         while ( n != NULL )
173         {
174             SLNode *next = n -> next;
175             ( * f ) ( n, data );
176             n = next;
177         }
178     }
179 }
180 
181 /* SLListDoUntil
182  *  executes a function on each element
183  *  until the function returns true
184  */
SLListDoUntil(const SLList * sl,bool (CC * f)(SLNode * n,void * data),void * data)185 LIB_EXPORT bool CC SLListDoUntil ( const SLList *sl,
186     bool ( CC * f ) ( SLNode *n, void *data ), void *data )
187 {
188     if ( sl )
189     {
190         SLNode *n = sl -> head;
191         while ( n != NULL )
192         {
193             SLNode *next = n -> next;
194             if ( ( * f ) ( n, data ) )
195                 return true;
196             n = next;
197         }
198     }
199 
200     return false;
201 }
202 
203 /* SLListFindFirst
204  *  find first element satisfying criteria
205  */
SLListFindFirst(const SLList * sl,bool (CC * f)(const SLNode * n))206 LIB_EXPORT SLNode* CC SLListFindFirst ( const SLList *sl,
207     bool ( CC * f ) ( const SLNode *n ) )
208 {
209     if ( sl != NULL )
210     {
211         SLNode *n = sl -> head;
212         while ( n != NULL )
213         {
214             SLNode *next = n -> next;
215             if ( ( * f ) ( n ) )
216                 return n;
217             n = next;
218         }
219     }
220     return NULL;
221 }
222 
223 /* SLListWhack
224  *  pops elements from list and
225  *  executes a user provided destructor
226  */
SLListWhack(SLList * sl,void (CC * whack)(SLNode * n,void * data),void * data)227 LIB_EXPORT void CC SLListWhack ( SLList *sl,
228     void ( CC * whack ) ( SLNode *n, void *data ), void *data )
229 {
230     if ( sl != NULL )
231     {
232         SLNode *n = sl -> head;
233         sl -> head = sl -> tail = NULL;
234 
235         if ( whack != NULL )
236         {
237             while ( n != NULL )
238             {
239                 SLNode *next = n -> next;
240                 ( * whack ) ( n, data );
241                 n = next;
242             }
243         }
244     }
245 }
246 
247 
248 /*--------------------------------------------------------------------------
249  * DLNode
250  *  doubly linked node
251  */
252 
253 #if 0
254 /* DLNodeFindNext
255  *  find next element satisfying criteria
256  */
257 LIB_EXPORT DLNode* CC DLNodeFindNext ( const DLNode *p,
258     bool ( CC * f ) ( const DLNode *n ) )
259 {
260     if ( p != NULL )
261     {
262         DLNode *n = p -> next;
263         while ( n != NULL )
264         {
265             if ( ( * f ) ( n ) )
266                 return n;
267             n = n -> next;
268         }
269     }
270     return NULL;
271 }
272 
273 /* DLNodeFindPrev
274  *  find previous element satisfying criteria
275  */
276 LIB_EXPORT DLNode* CC DLNodeFindPrev ( const DLNode *p,
277     bool ( CC * f ) ( const DLNode *n ) )
278 {
279     if ( p != NULL )
280     {
281         DLNode *n = p -> prev;
282         while ( n != NULL )
283         {
284             if ( ( * f ) ( n ) )
285                 return n;
286             n = n -> prev;
287         }
288     }
289     return NULL;
290 }
291 #endif
292 
293 
294 /*--------------------------------------------------------------------------
295  * DLList
296  *  doubly linked list
297  */
298 
299 /* DLListPushHead
300  *  push a single node onto the head of list
301  */
DLListPushHead(DLList * dl,DLNode * n)302 LIB_EXPORT void CC DLListPushHead ( DLList *dl, DLNode *n )
303 {
304     if ( dl != NULL && n != NULL )
305     {
306         n -> prev = NULL;
307         n -> next = dl -> head;
308         if ( dl -> head == NULL )
309             dl -> head = dl -> tail = n;
310         else
311         {
312             dl -> head -> prev = n;
313             dl -> head = n;
314         }
315     }
316 }
317 
318 /* DLListPushTail
319  *  push a single node onto the tail of list
320  */
DLListPushTail(DLList * dl,DLNode * n)321 LIB_EXPORT void CC DLListPushTail ( DLList *dl, DLNode *n )
322 {
323     if ( dl != NULL && n != NULL )
324     {
325         n -> next = NULL;
326         n -> prev = dl -> tail;
327         if ( dl -> tail == NULL )
328             dl -> tail = dl -> head = n;
329         else
330         {
331             dl -> tail -> next = n;
332             dl -> tail = n;
333         }
334     }
335 }
336 
337 /* DLListPopHead
338  *  pop a single node from head of list
339  */
DLListPopHead(DLList * dl)340 LIB_EXPORT DLNode* CC DLListPopHead ( DLList *dl )
341 {
342     if ( dl != NULL )
343     {
344         DLNode *n = dl -> head;
345         if ( dl -> head != NULL )
346         {
347             dl -> head = n -> next;
348             if ( n -> next == NULL )
349                 dl -> tail = NULL;
350             else
351                 n -> next -> prev = NULL;
352             n -> prev = n -> next = NULL;
353         }
354         return n;
355     }
356     return NULL;
357 }
358 
359 /* DLListPopTail
360  *  pop a single node from tail of list
361  */
DLListPopTail(DLList * dl)362 LIB_EXPORT DLNode* CC DLListPopTail ( DLList *dl )
363 {
364     if ( dl != NULL )
365     {
366         DLNode *n = dl -> tail;
367         if ( dl -> tail != NULL )
368         {
369             dl -> tail = n -> prev;
370             if ( n -> prev == NULL )
371                 dl -> head = NULL;
372             else
373                 n -> prev -> next = NULL;
374             n -> prev = n -> next = NULL;
375         }
376         return n;
377     }
378     return NULL;
379 }
380 
381 /* DLListPrependList
382  *  pushes list contents onto the head of target
383  */
DLListPrependList(DLList * dl,DLList * l)384 LIB_EXPORT void CC DLListPrependList ( DLList *dl, DLList *l )
385 {
386     if ( dl != NULL && l != NULL && l -> head != NULL )
387     {
388         if ( dl -> tail == NULL )
389             * dl = * l;
390         else
391         {
392             dl -> head -> prev = l -> tail;
393             l -> tail -> next = dl -> head;
394             dl -> head = l -> head;
395         }
396 
397         l -> head = l -> tail = NULL;
398     }
399 }
400 
401 /* DLListAppendList
402  *  pushes list contents onto the tail of target
403  */
DLListAppendList(DLList * dl,DLList * l)404 LIB_EXPORT void CC DLListAppendList ( DLList *dl, DLList *l )
405 {
406     if ( dl != NULL && l != NULL && l -> head != NULL )
407     {
408         if ( dl -> tail == NULL )
409             * dl = * l;
410         else
411         {
412             dl -> tail -> next = l -> head;
413             l -> head -> prev = dl -> tail;
414             dl -> tail = l -> tail;
415         }
416 
417         l -> head = l -> tail = NULL;
418     }
419 }
420 
421 /* DLListInsertNodeBefore
422  *  inserts node "n" before "which" within list
423  */
DLListInsertNodeBefore(DLList * dl,DLNode * which,DLNode * n)424 LIB_EXPORT void CC DLListInsertNodeBefore ( DLList *dl, DLNode *which, DLNode *n )
425 {
426     if ( which != NULL && n != NULL )
427     {
428         /* take care of "n" */
429         n -> next = which;
430         n -> prev = which -> prev;
431 
432         /* link "which"'s prev to "n" */
433         if ( which -> prev != NULL )
434             which -> prev -> next = n;
435 
436         /* or if none, then perhaps head of list */
437         else if ( dl != NULL && dl -> head == which )
438             dl -> head = n;
439 
440         /* link "which" to "n" */
441         which -> prev = n;
442     }
443 }
444 
445 /* DLListInsertNodeAfter
446  *  inserts node "n" after "which" within list
447  */
DLListInsertNodeAfter(DLList * dl,DLNode * which,DLNode * n)448 LIB_EXPORT void CC DLListInsertNodeAfter ( DLList *dl, DLNode *which, DLNode *n )
449 {
450     if ( which != NULL && n != NULL )
451     {
452         /* take care of "n" */
453         n -> prev = which;
454         n -> next = which -> next;
455 
456         /* link "which"'s next to "n" */
457         if ( which -> next != NULL )
458             which -> next -> prev = n;
459 
460         /* or if none, then perhaps tail of list */
461         else if ( dl != NULL && dl -> tail == which )
462             dl -> tail = n;
463 
464         /* link "which" to "n" */
465         which -> next = n;
466     }
467 }
468 
469 /* DLListInsertListBefore
470  *  inserts list "l" before "which" within list "dl"
471  */
DLListInsertListBefore(DLList * dl,DLNode * which,DLList * l)472 LIB_EXPORT void CC DLListInsertListBefore ( DLList *dl, DLNode *which, DLList *l )
473 {
474     if ( which != NULL && l != NULL && l -> head != NULL )
475     {
476         /* take care of inserting list */
477         l -> tail -> next = which;
478         l -> head -> prev = which -> prev;
479 
480         /* link "which"'s prev to "l -> head" */
481         if ( which -> prev != NULL )
482             which -> prev -> next = l -> head;
483 
484         /* or if none, then perhaps head of list */
485         else if ( dl != NULL && dl -> head == which )
486             dl -> head = l -> head;
487 
488         /* link "which" to "l -> tail" */
489         which -> prev = l -> tail;
490 
491         /* remove items from "l" */
492         l -> head = l -> tail = NULL;
493     }
494 }
495 
496 /* DLListInsertListAfter
497  *  inserts list "l" after "which" within list "dl"
498  */
DLListInsertListAfter(DLList * dl,DLNode * which,DLList * l)499 LIB_EXPORT void CC DLListInsertListAfter ( DLList *dl, DLNode *which, DLList *l )
500 {
501     if ( which != NULL && l != NULL && l -> head != NULL )
502     {
503         /* take care of inserting list */
504         l -> head -> prev = which;
505         l -> tail -> next = which -> next;
506 
507         /* link "which"'s next to "l -> tail" */
508         if ( which -> next != NULL )
509             which -> next -> prev = l -> tail;
510 
511         /* or if none, then perhaps tail of list */
512         else if ( dl != NULL && dl -> tail == which )
513             dl -> head = l -> tail;
514 
515         /* link "which" to "l -> head" */
516         which -> next = l -> head;
517 
518         /* remove items from "l" */
519         l -> head = l -> tail = NULL;
520     }
521 }
522 
523 /* DLListUnlink
524  *  removes a designated node from list
525  */
DLListUnlink(DLList * dl,DLNode * n)526 LIB_EXPORT void CC DLListUnlink ( DLList *dl, DLNode *n )
527 {
528     if ( n != NULL )
529     {
530         if ( n -> next == NULL )
531         {
532             if ( dl != NULL && dl -> tail == n )
533             {
534                 if ( n -> prev == NULL )
535                     dl -> head = dl -> tail = NULL;
536                 else
537                 {
538                     n -> prev -> next = NULL;
539                     dl -> tail = n -> prev;
540                 }
541             }
542             else
543             {
544                 if ( n -> prev != NULL )
545                     n -> prev -> next = NULL;
546             }
547             n -> prev = NULL;
548         }
549         else if ( n -> prev == NULL )
550         {
551             n -> next -> prev = NULL;
552             if ( dl != NULL && dl -> head == n )
553                 dl -> head = n -> next;
554             n -> next = NULL;
555         }
556         else
557         {
558             n -> next -> prev = n -> prev;
559             n -> prev -> next = n -> next;
560             n -> prev = n -> next = NULL;
561         }
562     }
563 }
564 
565 /* DLListForEach
566  *  executes a function on each list element
567  */
DLListForEach(const DLList * dl,bool reverse,void (CC * f)(DLNode * n,void * data),void * data)568 LIB_EXPORT void CC DLListForEach ( const DLList *dl, bool reverse,
569     void ( CC * f ) ( DLNode *n, void *data ), void *data )
570 {
571     if ( dl != NULL )
572     {
573         DLNode *n, *next;
574         if ( reverse )
575         {
576             n = dl -> tail;
577             while ( n != NULL )
578             {
579                 next = n -> prev;
580                 ( * f ) ( n, data );
581                 n = next;
582             }
583         }
584         else
585         {
586             n = dl -> head;
587             while ( n != NULL )
588             {
589                 next = n -> next;
590                 ( * f ) ( n, data );
591                 n = next;
592             }
593         }
594     }
595 }
596 
597 /* DLListDoUntil
598  *  executes a function on each element
599  *  until the function returns 1
600  */
DLListDoUntil(const DLList * dl,bool reverse,bool (CC * f)(DLNode * n,void * data),void * data)601 LIB_EXPORT bool CC DLListDoUntil ( const DLList *dl, bool reverse,
602     bool ( CC * f ) ( DLNode *n, void *data ), void *data )
603 {
604     if ( dl != NULL )
605     {
606         DLNode *n, *next;
607         if ( reverse )
608         {
609             n = dl -> tail;
610             while ( n != NULL )
611             {
612                 next = n -> prev;
613                 if ( ( * f ) ( n, data ) )
614                     return true;
615                 n = next;
616             }
617         }
618         else
619         {
620             n = dl -> head;
621             while ( n != NULL )
622             {
623                 next = n -> next;
624                 if ( ( * f ) ( n, data ) )
625                     return true;
626                 n = next;
627             }
628         }
629     }
630     return false;
631 }
632 
633 /* DLListFindFirst
634  *  find first element satisfying criteria
635  */
DLListFindFirst(const DLList * dl,bool (CC * f)(const DLNode * n))636 LIB_EXPORT DLNode* CC DLListFindFirst ( const DLList *dl,
637     bool ( CC * f ) ( const DLNode *n ) )
638 {
639     if ( dl != NULL )
640     {
641         DLNode *n = dl -> head;
642         while ( n != NULL )
643         {
644             if ( ( * f ) ( n ) )
645                 return n;
646             n = n -> next;
647         }
648     }
649     return NULL;
650 }
651 
652 /* DLListFindLast
653  *  find last element satisfying criteria
654  */
DLListFindLast(const DLList * dl,bool (CC * f)(const DLNode * n))655 LIB_EXPORT DLNode* CC DLListFindLast ( const DLList *dl,
656     bool ( CC * f ) ( const DLNode *n ) )
657 {
658     if ( dl != NULL )
659     {
660         DLNode *n = dl -> tail;
661         while ( n != NULL )
662         {
663             if ( ( * f ) ( n ) )
664                 return n;
665             n = n -> prev;
666         }
667     }
668     return NULL;
669 }
670 
671 /* DLListWhack
672  *  pops elements from list and
673  *  executes a user provided destructor
674  */
DLListWhack(DLList * dl,void (CC * whack)(DLNode * n,void * data),void * data)675 LIB_EXPORT void CC DLListWhack ( DLList *dl,
676     void ( CC * whack ) ( DLNode *n, void *data ), void *data )
677 {
678     if ( dl != NULL )
679     {
680         DLNode *n = dl -> head;
681         dl -> head = dl -> tail = NULL;
682 
683         if ( whack != NULL )
684         {
685             while ( n != NULL )
686             {
687                 DLNode *next = n -> next;
688                 ( * whack ) ( n, data );
689                 n = next;
690             }
691         }
692     }
693 }
694 
695 
696 /*--------------------------------------------------------------------------
697  * BSTNode
698  *  b-tree node
699  */
700 
701 #define LEFT 1
702 #define RIGHT 2
703 
704 #define BALANCE( node ) \
705     ( ( size_t ) ( node ) -> par & 3 )
706 #define ZERO_BALANCE( node ) \
707     ( * ( size_t* ) & ( node ) -> par &= ~ ( size_t ) 3 )
708 #define CLR_BALANCE( node, bal ) \
709     ( * ( size_t* ) & ( node ) -> par ^= ( bal ) )
710 #define SET_BALANCE( node, bal ) \
711     ( * ( size_t* ) & ( node ) -> par |= ( bal ) )
712 #define LEFT_HEAVY( node ) \
713     ( ( ( size_t ) ( node ) -> par & LEFT ) != 0 )
714 #define RIGHT_HEAVY( node ) \
715     ( ( ( size_t ) ( node ) -> par & RIGHT ) != 0 )
716 
717 #define PMASK 3
718 #define BBITS( node, bal ) ( bal )
719 
720 #define PBITS( node ) \
721     ( ( size_t ) ( node ) -> par & PMASK )
722 #define PARENT( node ) \
723     ( BSTNode* ) ( ( size_t ) ( node ) -> par & ~ ( size_t ) PMASK )
724 #define SET_PARENT( node, p ) \
725     ( ( node ) -> par = ( BSTNode* ) ( ( size_t ) ( p ) | PBITS ( node ) ) )
726 #define SET_PARBAL( node, p, bal ) \
727     ( ( node ) -> par = ( BSTNode* ) ( ( size_t ) ( p ) | BBITS ( node, bal ) ) )
728 
729 
730 /* LeftMost
731  *  returns the left-most child
732  */
733 static
LeftMost(BSTNode * q)734 BSTNode* CC LeftMost ( BSTNode *q )
735 {
736     if ( q != NULL )
737     {
738         BSTNode *p = q -> child [ 0 ];
739         while ( p != NULL )
740         {
741             q = p;
742             p = p -> child [ 0 ];
743         }
744     }
745     return q;
746 }
747 
748 /* RightMost
749  *  returns the right-most child
750  */
751 static
RightMost(BSTNode * q)752 BSTNode* CC RightMost ( BSTNode *q )
753 {
754     if ( q != NULL )
755     {
756         BSTNode *p = q -> child [ 1 ];
757         while ( p != NULL )
758         {
759             q = p;
760             p = p -> child [ 1 ];
761         }
762     }
763     return q;
764 }
765 
766 /* FirstNode
767  *  the left-most node in tree
768  */
769 #define FirstNode( bt ) \
770     LeftMost ( ( bt ) -> root )
771 
772 /* LastNode
773  *  the right-most node in tree
774  */
775 #define LastNode( bt ) \
776     RightMost ( ( bt ) -> root )
777 
778 /* BSTNodeNext
779  *  returns next node
780  */
BSTNodeNext(const BSTNode * n)781 LIB_EXPORT BSTNode* CC BSTNodeNext ( const BSTNode *n )
782 {
783     BSTNode *p;
784 
785     if ( n == NULL )
786         return NULL;
787 
788     p = n -> child [ 1 ];
789     if ( p == 0 )
790     {
791         BSTNode *q = ( BSTNode* ) n;
792         while ( 1 )
793         {
794             p = PARENT ( q );
795             if ( p == NULL )
796                 return NULL;
797             if ( p -> child [ 0 ] == q )
798                 return p;
799             q = p;
800         }
801     }
802     return LeftMost ( p );
803 }
804 
805 /* BSTNodePrev
806  *  returns prev node
807  */
BSTNodePrev(const BSTNode * n)808 LIB_EXPORT BSTNode* CC BSTNodePrev ( const BSTNode *n )
809 {
810     BSTNode *p = n -> child [ 0 ];
811     if ( p == 0 )
812     {
813         BSTNode *q = ( BSTNode* ) n;
814         while ( 1 )
815         {
816             p = PARENT ( q );
817             if ( p == NULL )
818                 return NULL;
819             if ( p -> child [ 1 ] == q )
820                 return p;
821             q = p;
822         }
823     }
824     return RightMost ( p );
825 }
826 
827 /* BSTNodeParent
828  *  returns a parent node if there, NULL otherwise
829  */
BSTNodeParent(const BSTNode * n)830 LIB_EXPORT BSTNode* CC BSTNodeParent ( const BSTNode *n )
831 {
832     if ( n != NULL )
833         return PARENT ( n );
834     return NULL;
835 }
836 
837 /* BSTNodeFindNext
838  *  find next element satisfying criteria
839  */
BSTNodeFindNext(const BSTNode * p,bool (CC * f)(const BSTNode * n))840 LIB_EXPORT BSTNode* CC BSTNodeFindNext ( const BSTNode *p,
841     bool ( CC * f ) ( const BSTNode *n ) )
842 {
843     if ( p != NULL )
844     {
845         BSTNode *n = BSTNodeNext ( p );
846         while ( n != NULL )
847         {
848             if ( ( * f ) ( n ) )
849                 return n;
850             n = BSTNodeNext ( n );
851         }
852     }
853     return NULL;
854 }
855 
856 /* BSTNodeFindPrev
857  *  find previous element satisfying criteria
858  */
BSTNodeFindPrev(const BSTNode * p,bool (CC * f)(const BSTNode * n))859 LIB_EXPORT BSTNode* CC BSTNodeFindPrev ( const BSTNode *p,
860     bool ( CC * f ) ( const BSTNode *n ) )
861 {
862     if ( p != NULL )
863     {
864         BSTNode *n = BSTNodePrev ( p );
865         while ( n != NULL )
866         {
867             if ( ( * f ) ( n ) )
868                 return n;
869             n = BSTNodePrev ( n );
870         }
871     }
872     return NULL;
873 }
874 
875 
876 /*--------------------------------------------------------------------------
877  * BSTree
878  *  b-tree
879  */
880 
881 /* BSTreeDepth
882  *  returns number of layers in b-tree
883  *
884  *  if "exact" is 1, then the maximum
885  *  depth is returned. otherwise, the depth of
886  *  an arbitrary leaf node is returned
887  */
BSTreeDepth(const BSTree * bt,bool exact)888 LIB_EXPORT uint32_t CC BSTreeDepth ( const BSTree *bt, bool exact )
889 {
890     BSTNode *p;
891     uint32_t depth;
892 
893     if ( bt == NULL || bt -> root == NULL )
894         return 0;
895 
896     depth = 1;
897 
898     if ( exact )
899     {
900         for ( p = FirstNode ( bt ); p != NULL; p = BSTNodeNext ( p ) )
901         {
902             BSTNode *q;
903             unsigned int ndepth;
904 
905             if ( p -> child [ 0 ] != NULL || p -> child [ 1 ] != NULL )
906                 continue;
907 
908             for ( ndepth = 1, q = PARENT ( p ); q != NULL; q = PARENT ( q ) )
909                 ++ ndepth;
910 
911             if ( ndepth > depth )
912                 depth = ndepth;
913         }
914     }
915     else
916     {
917         for ( p = bt -> root;; ++ depth )
918         {
919             if ( p -> child [ 0 ] != NULL )
920                 p = p -> child [ 0 ];
921             else if ( p -> child [ 1 ] != NULL )
922                 p = p -> child [ 1 ];
923             else
924                 break;
925         }
926     }
927 
928     return depth;
929 }
930 
931 /* BSTreeFirst
932  *  returns first node
933  */
BSTreeFirst(const BSTree * bt)934 LIB_EXPORT BSTNode* CC BSTreeFirst ( const BSTree *bt )
935 {
936     if ( bt == NULL )
937         return NULL;
938     return FirstNode ( bt );
939 }
940 
941 /* BSTreeLast
942  *  returns last node
943  */
BSTreeLast(const BSTree * bt)944 LIB_EXPORT BSTNode* CC BSTreeLast ( const BSTree *bt )
945 {
946     if ( bt == NULL )
947         return NULL;
948     return LastNode ( bt );
949 }
950 
951 /* BSTreeFind
952  *  find an object within tree
953  *  "cmp" function returns equivalent of "item" - "n"
954  */
BSTreeFind(const BSTree * bt,const void * item,int64_t (CC * cmp)(const void * item,const BSTNode * n))955 LIB_EXPORT BSTNode* CC BSTreeFind ( const BSTree *bt, const void *item,
956     int64_t ( CC * cmp ) ( const void *item, const BSTNode *n ) )
957 {
958     if ( bt != NULL )
959     {
960         BSTNode *n = bt -> root;
961         while ( n != NULL )
962         {
963             int64_t diff = ( * cmp ) ( item, n );
964             if ( diff == 0 )
965                 return n;
966             n = n -> child [ diff > 0 ];
967         }
968     }
969     return NULL;
970 }
971 
972 /* BSTreeInsert
973  *  insert an object within tree, even if duplicate
974  *  "sort" function returns equivalent of "item" - "n"
975  *
976  *  the treatment of order for items reported as identical
977  *  i.e. sort function returns zero when they are compared,
978  *  is undefined.
979  *
980  *  the current implementation treats '<=' as '<' such
981  *  that all inserts are converted to a '<' or '>' comparison,
982  *  but this should not be relied upon.
983  */
984 static
RotateRightAtY(BSTNode * y,BSTNode * x)985 BSTNode* CC RotateRightAtY ( BSTNode *y, BSTNode *x )
986 {
987     BSTNode *w = x;
988     BSTNode *z = x -> child [ 1 ];
989     y -> child [ 0 ] = z;
990     x -> child [ 1 ] = y;
991     x -> par = PARENT ( y );
992     y -> par = x;
993 
994     /* patch parent link */
995     if ( z != 0 )
996         SET_PARENT ( z, y );
997 
998     return w;
999 }
1000 
1001 static
RotateLeftAtY(BSTNode * y,BSTNode * x)1002 BSTNode* CC RotateLeftAtY ( BSTNode *y, BSTNode *x )
1003 {
1004     BSTNode *w = x;
1005     BSTNode *z = x -> child [ 0 ];
1006     y -> child [ 1 ] = z;
1007     x -> child [ 0 ] = y;
1008     x -> par = PARENT ( y );
1009     y -> par = x;
1010 
1011     /* patch parent link */
1012     if ( z != 0 )
1013         SET_PARENT ( z, y );
1014 
1015     return w;
1016 }
1017 
1018 static
RotateLeftAtXRightAtY(BSTNode * y,BSTNode * x)1019 BSTNode* CC RotateLeftAtXRightAtY ( BSTNode *y, BSTNode *x )
1020 {
1021     BSTNode *w = x -> child [ 1 ];
1022     BSTNode *z = w -> child [ 0 ];
1023     x -> child [ 1 ] = z;
1024     if ( z != 0 )
1025         SET_PARENT ( z, x );
1026     z = w -> child [ 1 ];
1027     w -> child [ 0 ] = x;
1028     y -> child [ 0 ] = z;
1029     w -> child [ 1 ] = y;
1030 
1031     switch ( BALANCE ( w ) )
1032     {
1033     case 0:
1034         w -> par = PARENT ( y );
1035         x -> par = w;
1036         y -> par = w;
1037         break;
1038     case LEFT:
1039         w -> par = PARENT ( y );
1040         x -> par = w;
1041         SET_PARBAL ( y, w, RIGHT );
1042         break;
1043     case RIGHT:
1044         w -> par = PARENT ( y );
1045         SET_PARBAL ( x, w, LEFT );
1046         y -> par = w;
1047         break;
1048     }
1049 
1050     /* patch parent link */
1051     if ( z != 0 )
1052         SET_PARENT ( z, y );
1053 
1054     return w;
1055 }
1056 
1057 static
RotateRightAtXLeftAtY(BSTNode * y,BSTNode * x)1058 BSTNode* CC RotateRightAtXLeftAtY ( BSTNode *y, BSTNode *x )
1059 {
1060     BSTNode *w = x -> child [ 0 ];
1061     BSTNode *z = w -> child [ 1 ];
1062     x -> child [ 0 ] = z;
1063     if ( z != 0 )
1064         SET_PARENT ( z, x );
1065     z = w -> child [ 0 ];
1066     w -> child [ 1 ] = x;
1067     y -> child [ 1 ] = z;
1068     w -> child [ 0 ] = y;
1069 
1070     switch ( BALANCE ( w ) )
1071     {
1072     case 0:
1073         w -> par = PARENT ( y );
1074         x -> par = w;
1075         y -> par = w;
1076         break;
1077     case LEFT:
1078         w -> par = PARENT ( y );
1079         SET_PARBAL ( x, w, RIGHT );
1080         y -> par = w;
1081         break;
1082     case RIGHT:
1083         w -> par = PARENT ( y );
1084         x -> par = w;
1085         SET_PARBAL ( y, w, LEFT );
1086         break;
1087     }
1088 
1089     /* patch parent link */
1090     if ( z != 0 )
1091         SET_PARENT ( z, y );
1092 
1093     return w;
1094 }
1095 
1096 static
RebalanceLeft(BSTNode * y,BSTNode * x)1097 BSTNode* CC RebalanceLeft ( BSTNode *y, BSTNode *x )
1098 {
1099     /* detect child balance */
1100     if ( LEFT_HEAVY ( x ) )
1101         return RotateRightAtY ( y, x );
1102 
1103     /* child is right heavy */
1104     return RotateLeftAtXRightAtY ( y, x );
1105 }
1106 
1107 static
RebalanceRight(BSTNode * y,BSTNode * x)1108 BSTNode* CC RebalanceRight ( BSTNode *y, BSTNode *x )
1109 {
1110     /* detect child balance */
1111     if ( RIGHT_HEAVY ( x ) )
1112         return RotateLeftAtY ( y, x );
1113 
1114     /* left heavy */
1115     return RotateRightAtXLeftAtY ( y, x );
1116 }
1117 
1118 
1119 static
RebalanceAfterInsert(BSTNode ** root,BSTNode * y,BSTNode * x)1120 void CC RebalanceAfterInsert ( BSTNode **root, BSTNode *y, BSTNode *x )
1121 {
1122     BSTNode *w, *z;
1123 
1124     /* detect left insertion */
1125     if ( y -> child [ 0 ] == x )
1126     {
1127         /* if y was right-heavy, done */
1128         if ( RIGHT_HEAVY ( y ) )
1129         {
1130             CLR_BALANCE ( y, RIGHT );
1131             return;
1132         }
1133 
1134         /* rebalance left insertion */
1135         w = RebalanceLeft ( y, x );
1136     }
1137 
1138     /* right insertion */
1139     else
1140     {
1141         /* if y was left-heavy, done */
1142         if ( LEFT_HEAVY ( y ) )
1143         {
1144             CLR_BALANCE ( y, LEFT );
1145             return;
1146         }
1147 
1148         /* rebalance right insertion */
1149         w = RebalanceRight ( y, x );
1150     }
1151 
1152     /* fix parent to child */
1153     assert ( BALANCE ( w ) == 0 );
1154     z = w -> par;
1155     if ( z == 0 )
1156         * root = w;
1157     else
1158         z -> child [ z -> child [ 1 ] == y ] = w;
1159 }
1160 
BSTreeInsert(BSTree * bt,BSTNode * n,int64_t (CC * sort)(const BSTNode * n,const BSTNode * p))1161 LIB_EXPORT rc_t CC BSTreeInsert ( BSTree *bt, BSTNode *n,
1162     int64_t ( CC * sort ) ( const BSTNode *n, const BSTNode *p ) )
1163 {
1164     if ( bt != NULL && n != NULL )
1165     {
1166         int64_t diff;
1167 
1168         BSTNode *p = bt -> root;
1169         BSTNode *q = NULL;
1170         BSTNode *y = NULL;
1171 
1172         while ( p != NULL )
1173         {
1174             diff = ( * sort ) ( n, p );
1175             q = p;
1176             if ( BALANCE ( p ) != 0 )
1177                 y = p;
1178             p = p -> child [ diff > 0 ];
1179         }
1180 
1181         n -> par = q;
1182         n -> child [ 0 ] = n -> child [ 1 ] = NULL;
1183 
1184         if ( q == NULL )
1185             bt -> root = n;
1186         else
1187         {
1188             q -> child [ diff > 0 ] = n;
1189 
1190             /* run a trace-back */
1191             for ( p = n; q != y; )
1192             {
1193                 /* this is safe because q has 0 balance */
1194                 BSTNode *z = q -> par;
1195                 if ( q -> child [ 0 ] == p )
1196                     SET_BALANCE ( q, LEFT );
1197                 else
1198                     SET_BALANCE ( q, RIGHT );
1199 
1200                 p = q;
1201                 q = z;
1202             }
1203 
1204             /* rebalance */
1205             if ( q != NULL )
1206                 RebalanceAfterInsert ( & bt -> root, q, p );
1207         }
1208     }
1209 
1210     /* never fails in this implementation */
1211     return 0;
1212 }
1213 
1214 /* BSTreeInsertUnique
1215  *  insert an object within tree, but only if unique
1216  *  "sort" function returns equivalent of "item" - "n"
1217  *  returns non-NULL "n" upon match or NULL on success
1218  */
BSTreeInsertUnique(BSTree * bt,BSTNode * n,BSTNode ** exist,int64_t (CC * sort)(const BSTNode * n,const BSTNode * p))1219 LIB_EXPORT rc_t CC BSTreeInsertUnique ( BSTree *bt, BSTNode *n, BSTNode **exist,
1220     int64_t ( CC * sort ) ( const BSTNode *n, const BSTNode *p ) )
1221 {
1222     if ( bt != NULL && n != NULL )
1223     {
1224         int64_t diff;
1225 
1226         BSTNode *p = bt -> root;
1227         BSTNode *q = NULL;
1228         BSTNode *y = NULL;
1229 
1230         while ( p != NULL )
1231         {
1232             diff = ( * sort ) ( n, p );
1233 
1234             if ( diff == 0 )
1235             {
1236                 /* fail to insert */
1237                 if ( exist != NULL )
1238                     * exist = p;
1239                 return SILENT_RC ( rcCont, rcTree, rcInserting, rcNode, rcExists );
1240             }
1241 
1242             q = p;
1243             if ( BALANCE ( p ) != 0 )
1244                 y = p;
1245             p = p -> child [ diff > 0 ];
1246         }
1247 
1248         n -> par = q;
1249         n -> child [ 0 ] = n -> child [ 1 ] = NULL;
1250 
1251         if ( q == NULL )
1252             bt -> root = n;
1253         else
1254         {
1255             q -> child [ diff > 0 ] = n;
1256 
1257             /* run a trace-back */
1258             for ( p = n; q != y; )
1259             {
1260                 /* this is safe because q has 0 balance */
1261                 BSTNode *z = q -> par;
1262                 if ( q -> child [ 0 ] == p )
1263                     SET_BALANCE ( q, LEFT );
1264                 else
1265                     SET_BALANCE ( q, RIGHT );
1266 
1267                 p = q;
1268                 q = z;
1269             }
1270 
1271             /* rebalance */
1272             if ( q != NULL )
1273                 RebalanceAfterInsert ( & bt -> root, q, p );
1274         }
1275     }
1276 
1277     /* only fails on existing item in this implementation */
1278     return 0;
1279 }
1280 
1281 /* BSTreeResort
1282  *  an optimized removal and re-insertion of
1283  *  all contained elements using another function
1284  *
1285  *  the treatment of order for items reported as identical
1286  *  i.e. sort function returns zero when they are compared,
1287  *  is undefined.
1288  *
1289  *  the current implementation treats '<=' as '<' such
1290  *  that all inserts are converted to a '<' or '>' comparison,
1291  *  but this should not be relied upon.
1292  */
BSTreeResort(BSTree * bt,int64_t (CC * resort)(const BSTNode * item,const BSTNode * n))1293 LIB_EXPORT void CC BSTreeResort ( BSTree *bt,
1294     int64_t ( CC * resort ) ( const BSTNode *item, const BSTNode *n ) )
1295 {
1296     if ( bt != NULL )
1297     {
1298         BSTNode *p = bt -> root;
1299         bt -> root = NULL;
1300 
1301         while ( p != NULL )
1302         {
1303             BSTNode *q = p -> child [ 0 ];
1304             if ( q == 0 )
1305             {
1306                 q = p -> child [ 1 ];
1307                 BSTreeInsert ( bt, p, resort );
1308             }
1309             else
1310             {
1311                 p -> child [ 0 ] = q -> child [ 1 ];
1312                 q -> child [ 1 ] = p;
1313             }
1314             p = q;
1315         }
1316     }
1317 }
1318 
1319 /* BSTreeUnlink
1320  *  removes a node from tree
1321  */
1322 static
RebalanceAfterUnlink(BSTNode ** root,BSTNode * q,int dir)1323 void CC RebalanceAfterUnlink ( BSTNode **root, BSTNode *q, int dir )
1324 {
1325     while ( q != 0 )
1326     {
1327         BSTNode *w, *x, *y = q;
1328         q = PARENT ( q );
1329 
1330         if ( ! dir )
1331         {
1332             if ( q && q -> child [ 1 ] == y )
1333                 dir = 1;
1334 
1335             /* simulate an increment of balance */
1336             switch ( BALANCE ( y ) )
1337             {
1338             case 0:
1339                 SET_BALANCE ( y, RIGHT );
1340                 return;
1341             case LEFT:
1342                 CLR_BALANCE ( y, LEFT );
1343                 break;
1344             case RIGHT:
1345                 /* y has just become ++ */
1346                 x = y -> child [ 1 ];
1347                 if ( LEFT_HEAVY ( x ) )
1348                 {
1349                     w = RotateRightAtXLeftAtY ( y, x );
1350                     if ( q == 0 )
1351                         * root = w;
1352                     else
1353                         q -> child [ dir ] = w;
1354                 }
1355                 else
1356                 {
1357                     w = y -> child [ 1 ] = x -> child [ 0 ];
1358                     x -> child [ 0 ] = y;
1359                     SET_PARENT ( x, q );
1360                     SET_PARENT ( y, x );
1361                     if ( w != 0 )
1362                         SET_PARENT ( w, y );
1363                     if ( q == 0 )
1364                         * root = x;
1365                     else
1366                         q -> child [ dir ] = x;
1367                     if ( BALANCE ( x ) == 0 )
1368                     {
1369                         SET_BALANCE ( x, LEFT );
1370                         SET_PARBAL ( y, x, RIGHT );
1371                         return;
1372                     }
1373                     ZERO_BALANCE ( x );
1374                     ZERO_BALANCE ( y );
1375                     /* y = x; */
1376                 }
1377                 break;
1378             }
1379         }
1380 
1381         /* symmetric case */
1382         else
1383         {
1384             if ( q && q -> child [ 0 ] == y )
1385                 dir = 0;
1386 
1387             switch ( BALANCE ( y ) )
1388             {
1389             case 0:
1390                 SET_BALANCE ( y, LEFT );
1391                 return;
1392             case LEFT:
1393                 /* y has just become -- */
1394                 x = y -> child [ 0 ];
1395                 if ( RIGHT_HEAVY ( x ) )
1396                 {
1397                     w = RotateLeftAtXRightAtY ( y, x );
1398                     if ( q == 0 )
1399                         * root = w;
1400                     else
1401                         q -> child [ dir ] = w;
1402                 }
1403                 else
1404                 {
1405                     w = x -> child [ 1 ];
1406                     y -> child [ 0 ] = w;
1407                     x -> child [ 1 ] = y;
1408                     SET_PARENT ( x, q );
1409                     SET_PARENT ( y, x );
1410                     if ( w != 0 )
1411                         SET_PARENT ( w, y );
1412                     if ( q == 0 )
1413                         * root = x;
1414                     else
1415                         q -> child [ dir ] = x;
1416                     if ( BALANCE ( x ) == 0 )
1417                     {
1418                         SET_BALANCE ( x, RIGHT );
1419                         SET_PARBAL ( y, x, LEFT );
1420                         return;
1421                     }
1422                     ZERO_BALANCE ( x );
1423                     ZERO_BALANCE ( y );
1424                     /* y = x; */
1425                 }
1426                 break;
1427             case RIGHT:
1428                 CLR_BALANCE ( y, RIGHT );
1429                 break;
1430             }
1431         }
1432     }
1433 }
1434 
1435 static
BTUnlink(BSTNode ** root,BSTNode * p,int dir)1436 void CC BTUnlink ( BSTNode **root, BSTNode *p, int dir )
1437 {
1438     BSTNode *q = PARENT ( p );
1439     BSTNode *l, *r = p -> child [ 1 ];
1440     if ( r == 0 )
1441     {
1442       /* no right child - simple unlink */
1443         l = p -> child [ 0 ];
1444         if ( q == 0 )
1445             * root = l;
1446         else
1447             q -> child [ dir ] = l;
1448         if ( l != 0 )
1449             SET_PARENT ( l, q );
1450     }
1451     else
1452     {
1453       /* have a right child - check its left */
1454         l = r -> child [ 0 ];
1455         if ( l == 0 )
1456         {
1457             l = p -> child [ 0 ];
1458             r -> child [ 0 ] = l;
1459 
1460             /* take not only p's parent ( q )
1461             // but its balance as well */
1462             r -> par = p -> par;
1463 
1464             if ( q == 0 )
1465                 * root = r;
1466             else
1467                 q -> child [ dir ] = r;
1468 
1469             if ( l != 0 )
1470                 SET_PARENT ( l, r );
1471 
1472             /* artificially reset for following */
1473             q = r;
1474             dir = 1;
1475         }
1476 
1477         /* involves some work */
1478         else
1479         {
1480 	  /* find smallest subsequent item */
1481             r = l -> child [ 0 ];
1482             while ( r != 0 )
1483             {
1484                 l = r;
1485                 r = l -> child [ 0 ];
1486             }
1487 
1488             /* unlink it */
1489             r = PARENT ( l );
1490             r -> child [ 0 ] = l -> child [ 1 ];
1491 
1492             /* take over doomed node */
1493             l -> child [ 0 ] = p -> child [ 0 ];
1494             l -> child [ 1 ] = p -> child [ 1 ];
1495 
1496             /* take not only p's parent ( q )
1497             // but its balance as well */
1498             l -> par = p -> par;
1499 
1500             /* new king pin */
1501             if ( q == 0 )
1502                 * root = l;
1503             else
1504                 q -> child [ dir ] = l;
1505 
1506             /* update parent links */
1507             q = l -> child [ 0 ];
1508             if ( q != 0 )
1509                 SET_PARENT ( q, l );
1510             q = l -> child [ 1 ];
1511             SET_PARENT ( q, l );
1512             q = r -> child [ 0 ];
1513             if ( q != 0 )
1514                 SET_PARENT ( q, r );
1515 
1516             q = r;
1517             dir = 0;
1518         }
1519     }
1520 
1521     /* now - rebalance what we've undone */
1522     if ( q != 0 )
1523         RebalanceAfterUnlink ( root, q, dir );
1524 }
1525 
1526 static
BSTreeContains(const BSTNode * root,const BSTNode * n)1527 bool CC BSTreeContains ( const BSTNode *root, const BSTNode *n )
1528 {
1529     while ( n != NULL )
1530     {
1531         if ( n == root )
1532             return true;
1533         n = PARENT ( n );
1534     }
1535     return false;
1536 }
1537 
BSTreeUnlink(BSTree * bt,BSTNode * n)1538 LIB_EXPORT bool CC BSTreeUnlink ( BSTree *bt, BSTNode *n )
1539 {
1540     if ( bt != NULL && BSTreeContains ( bt -> root, n ) )
1541     {
1542         int dir = 0;
1543         BSTNode *q = PARENT ( n );
1544         if ( q != 0 )
1545         {
1546             assert ( q -> child [ 0 ] == n || q -> child [ 1 ] == n );
1547             dir = q -> child [ 1 ] == n;
1548         }
1549         BTUnlink ( & bt -> root, n, ( int ) dir );
1550         return true;
1551     }
1552     return false;
1553 }
1554 
1555 /* BSTreeForEach
1556  *  executes a function on each tree element
1557  */
BSTreeForEach(const BSTree * bt,bool reverse,void (CC * f)(BSTNode * n,void * data),void * data)1558 LIB_EXPORT void CC BSTreeForEach ( const BSTree *bt, bool reverse,
1559     void ( CC * f ) ( BSTNode *n, void *data ), void *data )
1560 {
1561     if ( bt != NULL )
1562     {
1563         BSTNode *n, *next;
1564         if ( reverse )
1565         {
1566             n = LastNode ( bt );
1567             while ( n != NULL )
1568             {
1569                 next = BSTNodePrev ( n );
1570                 ( * f ) ( n, data );
1571                 n = next;
1572             }
1573         }
1574         else
1575         {
1576             n = FirstNode ( bt );
1577             while ( n != NULL )
1578             {
1579                 next = BSTNodeNext ( n );
1580                 ( * f ) ( n, data );
1581                 n = next;
1582             }
1583         }
1584     }
1585 }
1586 
1587 /* BSTreeDoUntil
1588  *  executes a function on each element
1589  *  until the function returns 1
1590  */
BSTreeDoUntil(const BSTree * bt,bool reverse,bool (CC * f)(BSTNode * n,void * data),void * data)1591 LIB_EXPORT bool CC BSTreeDoUntil ( const BSTree *bt, bool reverse,
1592     bool ( CC * f ) ( BSTNode *n, void *data ), void *data )
1593 {
1594     if ( bt != NULL )
1595     {
1596         BSTNode *n, *next;
1597         if ( reverse )
1598         {
1599             n = LastNode ( bt );
1600             while ( n != NULL )
1601             {
1602                 next = BSTNodePrev ( n );
1603                 if ( ( * f ) ( n, data ) )
1604                     return true;
1605                 n = next;
1606             }
1607         }
1608         else
1609         {
1610             n = FirstNode ( bt );
1611             while ( n != NULL )
1612             {
1613                 next = BSTNodeNext ( n );
1614                 if ( ( * f ) ( n, data ) )
1615                     return true;
1616                 n = next;
1617             }
1618         }
1619     }
1620     return false;
1621 }
1622 
1623 /* BSTreeWhack
1624  *  removes nodes from tree and
1625  *  executes a user provided destructor
1626  */
BSTreeWhack(BSTree * bt,void (CC * whack)(BSTNode * n,void * data),void * data)1627 LIB_EXPORT void CC BSTreeWhack ( BSTree *bt,
1628     void ( CC * whack ) ( BSTNode *n, void *data ), void *data )
1629 {
1630     if ( bt != NULL )
1631     {
1632         BSTNode *p = bt -> root;
1633         bt -> root = NULL;
1634 
1635         if ( whack != NULL )
1636         {
1637             while ( p != NULL )
1638             {
1639                 BSTNode *q = p -> child [ 0 ];
1640                 if ( q == 0 )
1641                 {
1642                     q = p -> child [ 1 ];
1643                     ( * whack ) ( p, data );
1644                 }
1645                 else
1646                 {
1647                     p -> child [ 0 ] = q -> child [ 1 ];
1648                     q -> child [ 1 ] = p;
1649                 }
1650                 p = q;
1651             }
1652         }
1653     }
1654 }
1655