tdelete.c revision 103012
1219820Sjeff/* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */ 2219820Sjeff 3219820Sjeff/* 4219820Sjeff * Tree search generalized from Knuth (6.2.2) Algorithm T just like 5219820Sjeff * the AT&T man page says. 6219820Sjeff * 7219820Sjeff * The node_t structure is for internal use only, lint doesn't grok it. 8219820Sjeff * 9219820Sjeff * Written by reading the System V Interface Definition, not the code. 10219820Sjeff * 11219820Sjeff * Totally public domain. 12219820Sjeff */ 13219820Sjeff 14219820Sjeff#include <sys/cdefs.h> 15219820Sjeff#if 0 16219820Sjeff#if defined(LIBC_SCCS) && !defined(lint) 17219820Sjeff__RCSID("$NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $"); 18219820Sjeff#endif /* LIBC_SCCS and not lint */ 19219820Sjeff#endif 20219820Sjeff__FBSDID("$FreeBSD: head/lib/libc/stdlib/tdelete.c 103012 2002-09-06 11:24:06Z tjr $"); 21219820Sjeff 22219820Sjeff#include <assert.h> 23219820Sjeff#define _SEARCH_PRIVATE 24219820Sjeff#include <search.h> 25219820Sjeff#include <stdlib.h> 26219820Sjeff 27219820Sjeff 28219820Sjeff/* 29219820Sjeff * delete node with given key 30219820Sjeff * 31219820Sjeff * vkey: key to be deleted 32219820Sjeff * vrootp: address of the root of the tree 33219820Sjeff * compar: function to carry out node comparisons 34219820Sjeff */ 35219820Sjeffvoid * 36219820Sjefftdelete(const void * __restrict vkey, void ** __restrict vrootp, 37219820Sjeff int (*compar)(const void *, const void *)) 38219820Sjeff{ 39219820Sjeff node_t **rootp = (node_t **)vrootp; 40219820Sjeff node_t *p, *q, *r; 41219820Sjeff int cmp; 42219820Sjeff 43219820Sjeff if (rootp == NULL || (p = *rootp) == NULL) 44219820Sjeff return NULL; 45219820Sjeff 46219820Sjeff while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) { 47219820Sjeff p = *rootp; 48219820Sjeff rootp = (cmp < 0) ? 49219820Sjeff &(*rootp)->llink : /* follow llink branch */ 50219820Sjeff &(*rootp)->rlink; /* follow rlink branch */ 51219820Sjeff if (*rootp == NULL) 52219820Sjeff return NULL; /* key not found */ 53219820Sjeff } 54219820Sjeff r = (*rootp)->rlink; /* D1: */ 55219820Sjeff if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ 56219820Sjeff q = r; 57219820Sjeff else if (r != NULL) { /* Right link is NULL? */ 58219820Sjeff if (r->llink == NULL) { /* D2: Find successor */ 59219820Sjeff r->llink = q; 60219820Sjeff q = r; 61219820Sjeff } else { /* D3: Find NULL link */ 62219820Sjeff for (q = r->llink; q->llink != NULL; q = r->llink) 63219820Sjeff r = q; 64219820Sjeff r->llink = q->rlink; 65219820Sjeff q->llink = (*rootp)->llink; 66219820Sjeff q->rlink = (*rootp)->rlink; 67219820Sjeff } 68219820Sjeff } 69219820Sjeff free(*rootp); /* D4: Free node */ 70219820Sjeff *rootp = q; /* link parent to new node */ 71219820Sjeff return p; 72219820Sjeff} 73219820Sjeff