2 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
3 * the AT&T man page says.
5 * The node_t structure is for internal use only, lint doesn't grok it.
7 * Written by reading the System V Interface Definition, not the code.
9 * Totally public domain.
11 * $NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $
12 * $NetBSD: twalk.c,v 1.1 1999/02/22 10:33:16 christos Exp $
13 * $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $
14 * $NetBSD: tfind.c,v 1.2 1999/09/16 11:45:37 lukem Exp $
24 struct node
*llink
, *rlink
;
28 #define __DECONST(type, var) ((type)(uintptr_t)(const void *)(var))
32 * find or insert datum into search tree
35 * vkey: key to be located
36 * vrootp: address of tree root
39 ROKEN_LIB_FUNCTION
void *
40 rk_tsearch(const void *vkey
, void **vrootp
,
41 int (*compar
)(const void *, const void *))
44 node_t
**rootp
= (node_t
**)vrootp
;
49 while (*rootp
!= NULL
) { /* Knuth's T1: */
52 if ((r
= (*compar
)(vkey
, (*rootp
)->key
)) == 0) /* T2: */
53 return *rootp
; /* we found it! */
56 &(*rootp
)->llink
: /* T3: follow left branch */
57 &(*rootp
)->rlink
; /* T4: follow right branch */
60 q
= malloc(sizeof(node_t
)); /* T5: key not found */
61 if (q
!= 0) { /* make new node */
62 *rootp
= q
; /* link new node to old */
63 /* LINTED const castaway ok */
64 q
->key
= __DECONST(void *, vkey
); /* initialize new node */
65 q
->llink
= q
->rlink
= NULL
;
71 * Walk the nodes of a tree
74 * root: Root of the tree to be walked
77 trecurse(const node_t
*root
, void (*action
)(const void *, VISIT
, int),
81 if (root
->llink
== NULL
&& root
->rlink
== NULL
)
82 (*action
)(root
, leaf
, level
);
84 (*action
)(root
, preorder
, level
);
85 if (root
->llink
!= NULL
)
86 trecurse(root
->llink
, action
, level
+ 1);
87 (*action
)(root
, postorder
, level
);
88 if (root
->rlink
!= NULL
)
89 trecurse(root
->rlink
, action
, level
+ 1);
90 (*action
)(root
, endorder
, level
);
95 * Walk the nodes of a tree
98 * vroot: Root of the tree to be walked
100 ROKEN_LIB_FUNCTION
void
101 rk_twalk(const void *vroot
,
102 void (*action
)(const void *, VISIT
, int))
104 if (vroot
!= NULL
&& action
!= NULL
)
105 trecurse(vroot
, action
, 0);
109 * delete node with given key
111 * vkey: key to be deleted
112 * vrootp: address of the root of the tree
113 * compar: function to carry out node comparisons
115 ROKEN_LIB_FUNCTION
void *
116 rk_tdelete(const void * vkey
, void ** vrootp
,
117 int (*compar
)(const void *, const void *))
119 node_t
**rootp
= (node_t
**)vrootp
;
123 if (rootp
== NULL
|| *rootp
== NULL
)
126 while ((cmp
= (*compar
)(vkey
, (*rootp
)->key
)) != 0) {
128 &(*rootp
)->llink
: /* follow llink branch */
129 &(*rootp
)->rlink
; /* follow rlink branch */
131 return NULL
; /* key not found */
133 r
= (*rootp
)->rlink
; /* D1: */
134 if ((q
= (*rootp
)->llink
) == NULL
) /* Left NULL? */
136 else if (r
!= NULL
) { /* Right link is NULL? */
137 if (r
->llink
== NULL
) { /* D2: Find successor */
140 } else { /* D3: Find NULL link */
141 for (q
= r
->llink
; q
->llink
!= NULL
; q
= r
->llink
)
144 q
->llink
= (*rootp
)->llink
;
145 q
->rlink
= (*rootp
)->rlink
;
148 free(*rootp
); /* D4: Free node */
149 *rootp
= q
; /* link parent to new node */
154 * find a node, or return 0
157 * vkey: key to be found
158 * vrootp: address of the tree root
160 ROKEN_LIB_FUNCTION
void *
161 rk_tfind(const void *vkey
, void * const *vrootp
,
162 int (*compar
)(const void *, const void *))
164 node_t
**rootp
= (node_t
**)vrootp
;
169 while (*rootp
!= NULL
) { /* T1: */
172 if ((r
= (*compar
)(vkey
, (*rootp
)->key
)) == 0) /* T2: */
173 return *rootp
; /* key found */
175 &(*rootp
)->llink
: /* T3: follow left branch */
176 &(*rootp
)->rlink
; /* T4: follow right branch */