1  /*	$NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $	*/
 2  
 3  /*
 4   * Tree search generalized from Knuth (6.2.2) Algorithm T just like
 5   * the AT&T man page says.
 6   *
 7   * The node_t structure is for internal use only, lint doesn't grok it.
 8   *
 9   * Written by reading the System V Interface Definition, not the code.
10   *
11   * Totally public domain.
12   */
13  
14  #include <sys/cdefs.h>
15  #if 0
16  #if defined(LIBC_SCCS) && !defined(lint)
17  __RCSID("$NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $");
18  #endif /* LIBC_SCCS and not lint */
19  #endif
20  __FBSDID("$FreeBSD: src/lib/libc/stdlib/tdelete.c,v 1.6 2003/01/05 02:43:18 tjr Exp $");
21  
22  #define _SEARCH_PRIVATE
23  #include <search.h>
24  #include <stdlib.h>
25  
26  
27  /*
28   * delete node with given key
29   *
30   * vkey:   key to be deleted
31   * vrootp: address of the root of the tree
32   * compar: function to carry out node comparisons
33   */
34  void *
35  tdelete(const void * __restrict vkey, void ** __restrict vrootp,
36      int (*compar)(const void *, const void *))
37  {
38  	node_t **rootp = (node_t **)vrootp;
39  	node_t *p, *q, *r;
40  	int cmp;
41  
42  	if (rootp == NULL || (p = *rootp) == NULL)
43  		return NULL;
44  
45  	while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) {
46  		p = *rootp;
47  		rootp = (cmp < 0) ?
48  		    &(*rootp)->llink :		/* follow llink branch */
49  		    &(*rootp)->rlink;		/* follow rlink branch */
50  		if (*rootp == NULL)
51  			return NULL;		/* key not found */
52  	}
53  	r = (*rootp)->rlink;			/* D1: */
54  	if ((q = (*rootp)->llink) == NULL)	/* Left NULL? */
55  		q = r;
56  	else if (r != NULL) {			/* Right link is NULL? */
57  		if (r->llink == NULL) {		/* D2: Find successor */
58  			r->llink = q;
59  			q = r;
60  		} else {			/* D3: Find NULL link */
61  			for (q = r->llink; q->llink != NULL; q = r->llink)
62  				r = q;
63  			r->llink = q->rlink;
64  			q->llink = (*rootp)->llink;
65  			q->rlink = (*rootp)->rlink;
66  		}
67  	}
68  	free(*rootp);				/* D4: Free node */
69  	*rootp = q;				/* link parent to new node */
70  	return p;
71  }