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