164566a3eSAlfred Perlstein /* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */ 264566a3eSAlfred Perlstein 364566a3eSAlfred Perlstein /* 464566a3eSAlfred Perlstein * Tree search generalized from Knuth (6.2.2) Algorithm T just like 564566a3eSAlfred Perlstein * the AT&T man page says. 664566a3eSAlfred Perlstein * 764566a3eSAlfred Perlstein * The node_t structure is for internal use only, lint doesn't grok it. 864566a3eSAlfred Perlstein * 964566a3eSAlfred Perlstein * Written by reading the System V Interface Definition, not the code. 1064566a3eSAlfred Perlstein * 1164566a3eSAlfred Perlstein * Totally public domain. 1264566a3eSAlfred Perlstein */ 1364566a3eSAlfred Perlstein 1464566a3eSAlfred Perlstein #include <sys/cdefs.h> 15333fc21eSDavid E. O'Brien #if 0 1664566a3eSAlfred Perlstein #if defined(LIBC_SCCS) && !defined(lint) 1764566a3eSAlfred Perlstein __RCSID("$NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $"); 1864566a3eSAlfred Perlstein #endif /* LIBC_SCCS and not lint */ 19333fc21eSDavid E. O'Brien #endif 20333fc21eSDavid E. O'Brien __FBSDID("$FreeBSD$"); 2164566a3eSAlfred Perlstein 2264566a3eSAlfred Perlstein #include <assert.h> 2364566a3eSAlfred Perlstein #define _SEARCH_PRIVATE 2464566a3eSAlfred Perlstein #include <search.h> 2564566a3eSAlfred Perlstein #include <stdlib.h> 2664566a3eSAlfred Perlstein 2764566a3eSAlfred Perlstein 28840b798cSRobert Drehmel /* 29840b798cSRobert Drehmel * delete node with given key 30840b798cSRobert Drehmel * 31840b798cSRobert Drehmel * vkey: key to be deleted 32840b798cSRobert Drehmel * vrootp: address of the root of the tree 33840b798cSRobert Drehmel * compar: function to carry out node comparisons 34840b798cSRobert Drehmel */ 3564566a3eSAlfred Perlstein void * 36840b798cSRobert Drehmel tdelete(const void *__restrict vkey, void **__restrict vrootp, 37840b798cSRobert Drehmel int (*compar)(const void *, const void *)) 3864566a3eSAlfred Perlstein { 3964566a3eSAlfred Perlstein node_t **rootp = (node_t **)vrootp; 4064566a3eSAlfred Perlstein node_t *p, *q, *r; 4164566a3eSAlfred Perlstein int cmp; 4264566a3eSAlfred Perlstein 4364566a3eSAlfred Perlstein if (rootp == NULL || (p = *rootp) == NULL) 4464566a3eSAlfred Perlstein return NULL; 4564566a3eSAlfred Perlstein 4664566a3eSAlfred Perlstein while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) { 4764566a3eSAlfred Perlstein p = *rootp; 4864566a3eSAlfred Perlstein rootp = (cmp < 0) ? 4964566a3eSAlfred Perlstein &(*rootp)->llink : /* follow llink branch */ 5064566a3eSAlfred Perlstein &(*rootp)->rlink; /* follow rlink branch */ 5164566a3eSAlfred Perlstein if (*rootp == NULL) 5264566a3eSAlfred Perlstein return NULL; /* key not found */ 5364566a3eSAlfred Perlstein } 5464566a3eSAlfred Perlstein r = (*rootp)->rlink; /* D1: */ 5564566a3eSAlfred Perlstein if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ 5664566a3eSAlfred Perlstein q = r; 5764566a3eSAlfred Perlstein else if (r != NULL) { /* Right link is NULL? */ 5864566a3eSAlfred Perlstein if (r->llink == NULL) { /* D2: Find successor */ 5964566a3eSAlfred Perlstein r->llink = q; 6064566a3eSAlfred Perlstein q = r; 6164566a3eSAlfred Perlstein } else { /* D3: Find NULL link */ 6264566a3eSAlfred Perlstein for (q = r->llink; q->llink != NULL; q = r->llink) 6364566a3eSAlfred Perlstein r = q; 6464566a3eSAlfred Perlstein r->llink = q->rlink; 6564566a3eSAlfred Perlstein q->llink = (*rootp)->llink; 6664566a3eSAlfred Perlstein q->rlink = (*rootp)->rlink; 6764566a3eSAlfred Perlstein } 6864566a3eSAlfred Perlstein } 6964566a3eSAlfred Perlstein free(*rootp); /* D4: Free node */ 7064566a3eSAlfred Perlstein *rootp = q; /* link parent to new node */ 7164566a3eSAlfred Perlstein return p; 7264566a3eSAlfred Perlstein } 73