1 /* $NetBSD: tsearch.c,v 1.3 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 #ifndef _MSC_FULL_VER 15 #include <sys/cdefs.h> 16 #endif //! _MSC_FULL_VER 17 #define _SEARCH_PRIVATE 18 #include "tsearch.h" 19 #include <stdlib.h> 20 21 /* find or insert datum into search tree */ 22 void * 23 tsearch(vkey, vrootp, compar) 24 const void *vkey; /* key to be located */ 25 void **vrootp; /* address of tree root */ 26 int (*compar)(const void *, const void *); 27 { 28 node_t *q; 29 node_t **rootp = (node_t **)vrootp; 30 31 if (rootp == NULL) 32 return NULL; 33 34 while (*rootp != NULL) { /* Knuth's T1: */ 35 int r; 36 37 if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ 38 return *rootp; /* we found it! */ 39 40 rootp = (r < 0) ? 41 &(*rootp)->llink : /* T3: follow left branch */ 42 &(*rootp)->rlink; /* T4: follow right branch */ 43 } 44 45 q = malloc(sizeof(node_t)); /* T5: key not found */ 46 if (q != 0) { /* make new node */ 47 *rootp = q; /* link new node to old */ 48 /* LINTED const castaway ok */ 49 q->key = (void *)vkey; /* initialize new node */ 50 q->llink = q->rlink = NULL; 51 } 52 return q; 53 } 54 55 /* find a node, or return 0 */ 56 void * 57 tfind(vkey, vrootp, compar) 58 const void *vkey; /* key to be found */ 59 void * const *vrootp; /* address of the tree root */ 60 int (*compar)(const void *, const void *); 61 { 62 node_t **rootp = (node_t **)vrootp; 63 64 if (rootp == NULL) 65 return NULL; 66 67 while (*rootp != NULL) { /* T1: */ 68 int r; 69 70 if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ 71 return *rootp; /* key found */ 72 rootp = (r < 0) ? 73 &(*rootp)->llink : /* T3: follow left branch */ 74 &(*rootp)->rlink; /* T4: follow right branch */ 75 } 76 return NULL; 77 } 78 79 /* 80 * delete node with given key 81 * 82 * vkey: key to be deleted 83 * vrootp: address of the root of the tree 84 * compar: function to carry out node comparisons 85 */ 86 void * 87 tdelete(const void * __restrict vkey, void ** __restrict vrootp, 88 int (*compar)(const void *, const void *)) 89 { 90 node_t **rootp = (node_t **)vrootp; 91 node_t *p, *q, *r; 92 int cmp; 93 94 if (rootp == NULL || (p = *rootp) == NULL) 95 return NULL; 96 97 while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) { 98 p = *rootp; 99 rootp = (cmp < 0) ? 100 &(*rootp)->llink : /* follow llink branch */ 101 &(*rootp)->rlink; /* follow rlink branch */ 102 if (*rootp == NULL) 103 return NULL; /* key not found */ 104 } 105 r = (*rootp)->rlink; /* D1: */ 106 if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ 107 q = r; 108 else if (r != NULL) { /* Right link is NULL? */ 109 if (r->llink == NULL) { /* D2: Find successor */ 110 r->llink = q; 111 q = r; 112 } else { /* D3: Find NULL link */ 113 for (q = r->llink; q->llink != NULL; q = r->llink) 114 r = q; 115 r->llink = q->rlink; 116 q->llink = (*rootp)->llink; 117 q->rlink = (*rootp)->rlink; 118 } 119 } 120 free(*rootp); /* D4: Free node */ 121 *rootp = q; /* link parent to new node */ 122 return p; 123 } 124 125 /* end of tsearch.c */ 126
