162321Salfred/* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */ 262321Salfred 362321Salfred/* 462321Salfred * Tree search generalized from Knuth (6.2.2) Algorithm T just like 562321Salfred * the AT&T man page says. 662321Salfred * 762321Salfred * The node_t structure is for internal use only, lint doesn't grok it. 862321Salfred * 962321Salfred * Written by reading the System V Interface Definition, not the code. 1062321Salfred * 1162321Salfred * Totally public domain. 1262321Salfred */ 1362321Salfred 1462321Salfred#include <sys/cdefs.h> 1592986Sobrien#if 0 1662321Salfred#if defined(LIBC_SCCS) && !defined(lint) 1762321Salfred__RCSID("$NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $"); 1862321Salfred#endif /* LIBC_SCCS and not lint */ 1992986Sobrien#endif 2092986Sobrien__FBSDID("$FreeBSD$"); 2162321Salfred 2262321Salfred#define _SEARCH_PRIVATE 2362321Salfred#include <search.h> 2462321Salfred#include <stdlib.h> 2562321Salfred 2662321Salfred 27101882Srobert/* 28101882Srobert * delete node with given key 29101882Srobert * 30101882Srobert * vkey: key to be deleted 31101882Srobert * vrootp: address of the root of the tree 32101882Srobert * compar: function to carry out node comparisons 33101882Srobert */ 3462321Salfredvoid * 35103012Stjrtdelete(const void * __restrict vkey, void ** __restrict vrootp, 36101882Srobert int (*compar)(const void *, const void *)) 3762321Salfred{ 3862321Salfred node_t **rootp = (node_t **)vrootp; 3962321Salfred node_t *p, *q, *r; 40101882Srobert int cmp; 4162321Salfred 4262321Salfred if (rootp == NULL || (p = *rootp) == NULL) 4362321Salfred return NULL; 4462321Salfred 4562321Salfred while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) { 4662321Salfred p = *rootp; 4762321Salfred rootp = (cmp < 0) ? 4862321Salfred &(*rootp)->llink : /* follow llink branch */ 4962321Salfred &(*rootp)->rlink; /* follow rlink branch */ 5062321Salfred if (*rootp == NULL) 5162321Salfred return NULL; /* key not found */ 5262321Salfred } 5362321Salfred r = (*rootp)->rlink; /* D1: */ 5462321Salfred if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ 5562321Salfred q = r; 5662321Salfred else if (r != NULL) { /* Right link is NULL? */ 5762321Salfred if (r->llink == NULL) { /* D2: Find successor */ 5862321Salfred r->llink = q; 5962321Salfred q = r; 6062321Salfred } else { /* D3: Find NULL link */ 6162321Salfred for (q = r->llink; q->llink != NULL; q = r->llink) 6262321Salfred r = q; 6362321Salfred r->llink = q->rlink; 6462321Salfred q->llink = (*rootp)->llink; 6562321Salfred q->rlink = (*rootp)->rlink; 6662321Salfred } 6762321Salfred } 6862321Salfred free(*rootp); /* D4: Free node */ 6962321Salfred *rootp = q; /* link parent to new node */ 7062321Salfred return p; 7162321Salfred} 72