projects / apple / libc.git / blame
| Commit | Line | Data |
|---|---|---|
| 9385eb3d A |
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 | __FBSDID("$FreeBSD: src/lib/libc/stdlib/tdelete.c,v 1.6 2003/01/05 02:43:18 tjr Exp $"); | |
| 21 | ||
| 22 | #define _SEARCH_PRIVATE | |
| 23 | #include <search.h> | |
| 24 | #include <stdlib.h> | |
| 25 | ||
| 26 | ||
| 27 | /* | |
| 28 | * delete node with given key | |
| 29 | * | |
| 30 | * vkey: key to be deleted | |
| 31 | * vrootp: address of the root of the tree | |
| 32 | * compar: function to carry out node comparisons | |
| 33 | */ | |
| 34 | void * | |
| 35 | tdelete(const void * __restrict vkey, void ** __restrict vrootp, | |
| 36 | int (*compar)(const void *, const void *)) | |
| 37 | { | |
| 38 | node_t **rootp = (node_t **)vrootp; | |
| 39 | node_t *p, *q, *r; | |
| 40 | int cmp; | |
| 41 | ||
| 42 | if (rootp == NULL || (p = *rootp) == NULL) | |
| 43 | return NULL; | |
| 44 | ||
| 45 | while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) { | |
| 46 | p = *rootp; | |
| 47 | rootp = (cmp < 0) ? | |
| 48 | &(*rootp)->llink : /* follow llink branch */ | |
| 49 | &(*rootp)->rlink; /* follow rlink branch */ | |
| 50 | if (*rootp == NULL) | |
| 51 | return NULL; /* key not found */ | |
| 52 | } | |
| 53 | r = (*rootp)->rlink; /* D1: */ | |
| 54 | if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ | |
| 55 | q = r; | |
| 56 | else if (r != NULL) { /* Right link is NULL? */ | |
| 57 | if (r->llink == NULL) { /* D2: Find successor */ | |
| 58 | r->llink = q; | |
| 59 | q = r; | |
| 60 | } else { /* D3: Find NULL link */ | |
| 61 | for (q = r->llink; q->llink != NULL; q = r->llink) | |
| 62 | r = q; | |
| 63 | r->llink = q->rlink; | |
| 64 | q->llink = (*rootp)->llink; | |
| 65 | q->rlink = (*rootp)->rlink; | |
| 66 | } | |
| 67 | } | |
| 68 | free(*rootp); /* D4: Free node */ | |
| 69 | *rootp = q; /* link parent to new node */ | |
| 70 | return p; | |
| 71 | } |