1 /* $NetBSD: tdelete.c,v 1.4 2006/03/19 01:12:08 christos Exp $ */
4 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
5 * the AT&T man page says.
7 * The node_t structure is for internal use only, lint doesn't grok it.
9 * Written by reading the System V Interface Definition, not the code.
11 * Totally public domain.
14 #include <sys/cdefs.h>
15 #if defined(LIBC_SCCS) && !defined(lint)
16 __RCSID("$NetBSD: tdelete.c,v 1.4 2006/03/19 01:12:08 christos Exp $");
17 #endif /* LIBC_SCCS and not lint */
20 #define _SEARCH_PRIVATE
25 /* delete node with given key */
27 tdelete(vkey
, vrootp
, compar
)
28 const void *vkey
; /* key to be deleted */
29 void **vrootp
; /* address of the root of tree */
30 int (*compar
) __P((const void *, const void *));
32 node_t
**rootp
= (node_t
**)vrootp
;
36 _DIAGASSERT(vkey
!= NULL
);
37 _DIAGASSERT(compar
!= NULL
);
39 if (rootp
== NULL
|| (p
= *rootp
) == NULL
)
42 while ((cmp
= (*compar
)(vkey
, (*rootp
)->key
)) != 0) {
45 &(*rootp
)->llink
: /* follow llink branch */
46 &(*rootp
)->rlink
; /* follow rlink branch */
48 return NULL
; /* key not found */
50 r
= (*rootp
)->rlink
; /* D1: */
51 if ((q
= (*rootp
)->llink
) == NULL
) /* Left NULL? */
53 else if (r
!= NULL
) { /* Right link is NULL? */
54 if (r
->llink
== NULL
) { /* D2: Find successor */
57 } else { /* D3: Find NULL link */
58 for (q
= r
->llink
; q
->llink
!= NULL
; q
= r
->llink
)
61 q
->llink
= (*rootp
)->llink
;
62 q
->rlink
= (*rootp
)->rlink
;
66 free(*rootp
); /* D4: Free node */
67 *rootp
= q
; /* link parent to new node */