1 /* 2 * Tree search generalized from Knuth (6.2.2) Algorithm T just like 3 * the AT&T man page says. 4 * 5 * The node_t structure is for internal use only, lint doesn't grok it. 6 * 7 * Written by reading the System V Interface Definition, not the code. 8 * 9 * Totally public domain. 10 * 11 * $NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $ 12 * $NetBSD: twalk.c,v 1.1 1999/02/22 10:33:16 christos Exp $ 13 * $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ 14 * $NetBSD: tfind.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ 15 */ 16 17 #include <config.h> 18 #include "roken.h" 19 #include "search.h" 20 #include <stdlib.h> 21 22 typedef struct node { 23 char *key; 24 struct node *llink, *rlink; 25 } node_t; 26 27 #ifndef __DECONST 28 #define __DECONST(type, var) ((type)(uintptr_t)(const void *)(var)) 29 #endif 30 31 /* 32 * find or insert datum into search tree 33 * 34 * Parameters: 35 * vkey: key to be located 36 * vrootp: address of tree root 37 */ 38 39 ROKEN_LIB_FUNCTION void * 40 rk_tsearch(const void *vkey, void **vrootp, 41 int (*compar)(const void *, const void *)) 42 { 43 node_t *q; 44 node_t **rootp = (node_t **)vrootp; 45 46 if (rootp == NULL) 47 return NULL; 48 49 while (*rootp != NULL) { /* Knuth's T1: */ 50 int r; 51 52 if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ 53 return *rootp; /* we found it! */ 54 55 rootp = (r < 0) ? 56 &(*rootp)->llink : /* T3: follow left branch */ 57 &(*rootp)->rlink; /* T4: follow right branch */ 58 } 59 60 q = malloc(sizeof(node_t)); /* T5: key not found */ 61 if (q != 0) { /* make new node */ 62 *rootp = q; /* link new node to old */ 63 /* LINTED const castaway ok */ 64 q->key = __DECONST(void *, vkey); /* initialize new node */ 65 q->llink = q->rlink = NULL; 66 } 67 return q; 68 } 69 70 /* 71 * Walk the nodes of a tree 72 * 73 * Parameters: 74 * root: Root of the tree to be walked 75 */ 76 static void 77 trecurse(const node_t *root, void (*action)(const void *, VISIT, int), 78 int level) 79 { 80 81 if (root->llink == NULL && root->rlink == NULL) 82 (*action)(root, leaf, level); 83 else { 84 (*action)(root, preorder, level); 85 if (root->llink != NULL) 86 trecurse(root->llink, action, level + 1); 87 (*action)(root, postorder, level); 88 if (root->rlink != NULL) 89 trecurse(root->rlink, action, level + 1); 90 (*action)(root, endorder, level); 91 } 92 } 93 94 /* 95 * Walk the nodes of a tree 96 * 97 * Parameters: 98 * vroot: Root of the tree to be walked 99 */ 100 ROKEN_LIB_FUNCTION void 101 rk_twalk(const void *vroot, 102 void (*action)(const void *, VISIT, int)) 103 { 104 if (vroot != NULL && action != NULL) 105 trecurse(vroot, action, 0); 106 } 107 108 /* 109 * delete node with given key 110 * 111 * vkey: key to be deleted 112 * vrootp: address of the root of the tree 113 * compar: function to carry out node comparisons 114 */ 115 ROKEN_LIB_FUNCTION void * 116 rk_tdelete(const void * vkey, void ** vrootp, 117 int (*compar)(const void *, const void *)) 118 { 119 node_t **rootp = (node_t **)vrootp; 120 node_t *p, *q, *r; 121 int cmp; 122 123 if (rootp == NULL || (p = *rootp) == NULL) 124 return NULL; 125 126 while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) { 127 p = *rootp; 128 rootp = (cmp < 0) ? 129 &(*rootp)->llink : /* follow llink branch */ 130 &(*rootp)->rlink; /* follow rlink branch */ 131 if (*rootp == NULL) 132 return NULL; /* key not found */ 133 } 134 r = (*rootp)->rlink; /* D1: */ 135 if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ 136 q = r; 137 else if (r != NULL) { /* Right link is NULL? */ 138 if (r->llink == NULL) { /* D2: Find successor */ 139 r->llink = q; 140 q = r; 141 } else { /* D3: Find NULL link */ 142 for (q = r->llink; q->llink != NULL; q = r->llink) 143 r = q; 144 r->llink = q->rlink; 145 q->llink = (*rootp)->llink; 146 q->rlink = (*rootp)->rlink; 147 } 148 } 149 free(*rootp); /* D4: Free node */ 150 *rootp = q; /* link parent to new node */ 151 return p; 152 } 153 154 /* 155 * find a node, or return 0 156 * 157 * Parameters: 158 * vkey: key to be found 159 * vrootp: address of the tree root 160 */ 161 ROKEN_LIB_FUNCTION void * 162 rk_tfind(const void *vkey, void * const *vrootp, 163 int (*compar)(const void *, const void *)) 164 { 165 node_t **rootp = (node_t **)vrootp; 166 167 if (rootp == NULL) 168 return NULL; 169 170 while (*rootp != NULL) { /* T1: */ 171 int r; 172 173 if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ 174 return *rootp; /* key found */ 175 rootp = (r < 0) ? 176 &(*rootp)->llink : /* T3: follow left branch */ 177 &(*rootp)->rlink; /* T4: follow right branch */ 178 } 179 return NULL; 180 } 181