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 /*LINTLIBRARY*/ 12 13 #include <search.h> 14 #include <stdlib.h> 15 16 typedef struct node_t { 17 char *key; 18 struct node_t *left, *right; 19 } node; 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 register node *q; 29 char *key = (char *)vkey; 30 node **rootp = (node **)vrootp; 31 32 if (rootp == (struct node_t **)0) 33 return ((void *)0); 34 while (*rootp != (struct node_t *)0) { /* Knuth's T1: */ 35 int r; 36 37 if ((r = (*compar)(key, (*rootp)->key)) == 0) /* T2: */ 38 return ((void *)*rootp); /* we found it! */ 39 rootp = (r < 0) ? 40 &(*rootp)->left : /* T3: follow left branch */ 41 &(*rootp)->right; /* T4: follow right branch */ 42 } 43 q = (node *) malloc(sizeof(node)); /* T5: key not found */ 44 if (q != (struct node_t *)0) { /* make new node */ 45 *rootp = q; /* link new node to old */ 46 q->key = key; /* initialize new node */ 47 q->left = q->right = (struct node_t *)0; 48 } 49 return ((void *)q); 50 } 51 52 /* delete node with given key */ 53 void * 54 tdelete(vkey, vrootp, compar) 55 const void *vkey; /* key to be deleted */ 56 void **vrootp; /* address of the root of tree */ 57 int (*compar)(const void *, const void *); 58 { 59 node **rootp = (node **)vrootp; 60 char *key = (char *)vkey; 61 node *p; 62 register node *q; 63 register node *r; 64 int cmp; 65 66 if (rootp == (struct node_t **)0 || (p = *rootp) == (struct node_t *)0) 67 return ((struct node_t *)0); 68 while ((cmp = (*compar)(key, (*rootp)->key)) != 0) { 69 p = *rootp; 70 rootp = (cmp < 0) ? 71 &(*rootp)->left : /* follow left branch */ 72 &(*rootp)->right; /* follow right branch */ 73 if (*rootp == (struct node_t *)0) 74 return ((void *)0); /* key not found */ 75 } 76 r = (*rootp)->right; /* D1: */ 77 if ((q = (*rootp)->left) == (struct node_t *)0) /* Left (struct node_t *)0? */ 78 q = r; 79 else if (r != (struct node_t *)0) { /* Right link is null? */ 80 if (r->left == (struct node_t *)0) { /* D2: Find successor */ 81 r->left = q; 82 q = r; 83 } else { /* D3: Find (struct node_t *)0 link */ 84 for (q = r->left; q->left != (struct node_t *)0; q = r->left) 85 r = q; 86 r->left = q->right; 87 q->left = (*rootp)->left; 88 q->right = (*rootp)->right; 89 } 90 } 91 free((struct node_t *) *rootp); /* D4: Free node */ 92 *rootp = q; /* link parent to new node */ 93 return(p); 94 } 95 96 /* Walk the nodes of a tree */ 97 static void 98 trecurse(root, action, level) 99 register node *root; /* Root of the tree to be walked */ 100 register void (*action)(); /* Function to be called at each node */ 101 register int level; 102 { 103 if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0) 104 (*action)(root, leaf, level); 105 else { 106 (*action)(root, preorder, level); 107 if (root->left != (struct node_t *)0) 108 trecurse(root->left, action, level + 1); 109 (*action)(root, postorder, level); 110 if (root->right != (struct node_t *)0) 111 trecurse(root->right, action, level + 1); 112 (*action)(root, endorder, level); 113 } 114 } 115 116 /* Walk the nodes of a tree */ 117 void 118 twalk(vroot, action) 119 const void *vroot; /* Root of the tree to be walked */ 120 void (*action)(const void *, VISIT, int); 121 { 122 node *root = (node *)vroot; 123 124 if (root != (node *)0 && action != (void(*)())0) 125 trecurse(root, action, 0); 126 } 127