tdelete.c revision 256281
1130803Smarcel/* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */ 2130803Smarcel 3130803Smarcel/* 4130803Smarcel * Tree search generalized from Knuth (6.2.2) Algorithm T just like 5130803Smarcel * the AT&T man page says. 6130803Smarcel * 7130803Smarcel * The node_t structure is for internal use only, lint doesn't grok it. 8130803Smarcel * 9130803Smarcel * Written by reading the System V Interface Definition, not the code. 10130803Smarcel * 11130803Smarcel * Totally public domain. 12130803Smarcel */ 13130803Smarcel 14130803Smarcel#include <sys/cdefs.h> 15130803Smarcel#if 0 16130803Smarcel#if defined(LIBC_SCCS) && !defined(lint) 17130803Smarcel__RCSID("$NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $"); 18130803Smarcel#endif /* LIBC_SCCS and not lint */ 19130803Smarcel#endif 20130803Smarcel__FBSDID("$FreeBSD: stable/10/lib/libc/stdlib/tdelete.c 108694 2003-01-05 02:43:18Z tjr $"); 21130803Smarcel 22130803Smarcel#define _SEARCH_PRIVATE 23130803Smarcel#include <search.h> 24130803Smarcel#include <stdlib.h> 25130803Smarcel 26130803Smarcel 27130803Smarcel/* 28130803Smarcel * delete node with given key 29130803Smarcel * 30130803Smarcel * vkey: key to be deleted 31130803Smarcel * vrootp: address of the root of the tree 32130803Smarcel * compar: function to carry out node comparisons 33130803Smarcel */ 34130803Smarcelvoid * 35130803Smarceltdelete(const void * __restrict vkey, void ** __restrict vrootp, 36130803Smarcel int (*compar)(const void *, const void *)) 37130803Smarcel{ 38130803Smarcel node_t **rootp = (node_t **)vrootp; 39130803Smarcel node_t *p, *q, *r; 40130803Smarcel int cmp; 41130803Smarcel 42130803Smarcel if (rootp == NULL || (p = *rootp) == NULL) 43130803Smarcel return NULL; 44130803Smarcel 45130803Smarcel while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) { 46130803Smarcel p = *rootp; 47130803Smarcel rootp = (cmp < 0) ? 48130803Smarcel &(*rootp)->llink : /* follow llink branch */ 49130803Smarcel &(*rootp)->rlink; /* follow rlink branch */ 50130803Smarcel if (*rootp == NULL) 51130803Smarcel return NULL; /* key not found */ 52130803Smarcel } 53130803Smarcel r = (*rootp)->rlink; /* D1: */ 54130803Smarcel if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ 55130803Smarcel q = r; 56130803Smarcel else if (r != NULL) { /* Right link is NULL? */ 57130803Smarcel if (r->llink == NULL) { /* D2: Find successor */ 58130803Smarcel r->llink = q; 59130803Smarcel q = r; 60130803Smarcel } else { /* D3: Find NULL link */ 61130803Smarcel for (q = r->llink; q->llink != NULL; q = r->llink) 62130803Smarcel r = q; 63130803Smarcel r->llink = q->rlink; 64130803Smarcel q->llink = (*rootp)->llink; 65130803Smarcel q->rlink = (*rootp)->rlink; 66130803Smarcel } 67130803Smarcel } 68130803Smarcel free(*rootp); /* D4: Free node */ 69130803Smarcel *rootp = q; /* link parent to new node */ 70130803Smarcel return p; 71130803Smarcel} 72130803Smarcel