1/*	$NetBSD: tdelete.c,v 1.8 2016/01/20 20:47:41 christos 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.8 2016/01/20 20:47:41 christos Exp $");
18#endif /* LIBC_SCCS and not lint */
19#endif
20__FBSDID("$FreeBSD$");
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 */
34void *
35tdelete(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}
72