[444] | 1 | /* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem 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.2 1999/09/16 11:45:37 lukem Exp $"); |
---|
| 18 | #endif /* LIBC_SCCS and not lint */ |
---|
| 19 | #endif |
---|
| 20 | |
---|
| 21 | #include <assert.h> |
---|
| 22 | #define _SEARCH_PRIVATE |
---|
| 23 | #include <search.h> |
---|
| 24 | #include <stdlib.h> |
---|
| 25 | |
---|
| 26 | |
---|
| 27 | /* delete node with given key */ |
---|
| 28 | void * |
---|
| 29 | tdelete (const void *__restrict vkey, /* key to be deleted */ |
---|
| 30 | void **__restrict vrootp, /* address of the root of tree */ |
---|
| 31 | int (*compar)(const void *, const void *)) |
---|
| 32 | { |
---|
| 33 | node_t **rootp = (node_t **)vrootp; |
---|
| 34 | node_t *p, *q, *r; |
---|
| 35 | int cmp; |
---|
| 36 | |
---|
| 37 | if (rootp == NULL || (p = *rootp) == NULL) |
---|
| 38 | return NULL; |
---|
| 39 | |
---|
| 40 | while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) { |
---|
| 41 | p = *rootp; |
---|
| 42 | rootp = (cmp < 0) ? |
---|
| 43 | &(*rootp)->llink : /* follow llink branch */ |
---|
| 44 | &(*rootp)->rlink; /* follow rlink branch */ |
---|
| 45 | if (*rootp == NULL) |
---|
| 46 | return NULL; /* key not found */ |
---|
| 47 | } |
---|
| 48 | r = (*rootp)->rlink; /* D1: */ |
---|
| 49 | if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ |
---|
| 50 | q = r; |
---|
| 51 | else if (r != NULL) { /* Right link is NULL? */ |
---|
| 52 | if (r->llink == NULL) { /* D2: Find successor */ |
---|
| 53 | r->llink = q; |
---|
| 54 | q = r; |
---|
| 55 | } else { /* D3: Find NULL link */ |
---|
| 56 | for (q = r->llink; q->llink != NULL; q = r->llink) |
---|
| 57 | r = q; |
---|
| 58 | r->llink = q->rlink; |
---|
| 59 | q->llink = (*rootp)->llink; |
---|
| 60 | q->rlink = (*rootp)->rlink; |
---|
| 61 | } |
---|
| 62 | } |
---|
| 63 | free(*rootp); /* D4: Free node */ |
---|
| 64 | *rootp = q; /* link parent to new node */ |
---|
| 65 | return p; |
---|
| 66 | } |
---|