1 /* $OpenBSD: tsearch.c,v 1.10 2015/09/26 16:03:48 guenther 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 8 * 9 * Written by reading the System V Interface Definition, not the code. 10 * 11 * Totally public domain. 12 */ 13 14 #include <search.h> 15 #include <stdlib.h> 16 17 typedef struct node_t { 18 char *key; 19 struct node_t *left, *right; 20 } node; 21 22 /* find or insert datum into search tree */ 23 void * 24 tsearch(const void *vkey, void **vrootp, 25 int (*compar)(const void *, const void *)) 26 { 27 node *q; 28 char *key = (char *)vkey; 29 node **rootp = (node **)vrootp; 30 31 if (rootp == (struct node_t **)0) 32 return ((void *)0); 33 while (*rootp != (struct node_t *)0) { /* Knuth's T1: */ 34 int r; 35 36 if ((r = (*compar)(key, (*rootp)->key)) == 0) /* T2: */ 37 return ((void *)*rootp); /* we found it! */ 38 rootp = (r < 0) ? 39 &(*rootp)->left : /* T3: follow left branch */ 40 &(*rootp)->right; /* T4: follow right branch */ 41 } 42 q = malloc(sizeof(node)); /* T5: key not found */ 43 if (q != (struct node_t *)0) { /* make new node */ 44 *rootp = q; /* link new node to old */ 45 q->key = key; /* initialize new node */ 46 q->left = q->right = (struct node_t *)0; 47 } 48 return ((void *)q); 49 } 50 51 /* delete node with given key */ 52 void * 53 tdelete(const void *vkey, void **vrootp, 54 int (*compar)(const void *, const void *)) 55 { 56 node **rootp = (node **)vrootp; 57 char *key = (char *)vkey; 58 node *p = (node *)1; 59 node *q; 60 node *r; 61 int cmp; 62 63 if (rootp == (struct node_t **)0 || *rootp == (struct node_t *)0) 64 return ((struct node_t *)0); 65 while ((cmp = (*compar)(key, (*rootp)->key)) != 0) { 66 p = *rootp; 67 rootp = (cmp < 0) ? 68 &(*rootp)->left : /* follow left branch */ 69 &(*rootp)->right; /* follow right branch */ 70 if (*rootp == (struct node_t *)0) 71 return ((void *)0); /* key not found */ 72 } 73 r = (*rootp)->right; /* D1: */ 74 if ((q = (*rootp)->left) == (struct node_t *)0) /* Left (struct node_t *)0? */ 75 q = r; 76 else if (r != (struct node_t *)0) { /* Right link is null? */ 77 if (r->left == (struct node_t *)0) { /* D2: Find successor */ 78 r->left = q; 79 q = r; 80 } else { /* D3: Find (struct node_t *)0 link */ 81 for (q = r->left; q->left != (struct node_t *)0; q = r->left) 82 r = q; 83 r->left = q->right; 84 q->left = (*rootp)->left; 85 q->right = (*rootp)->right; 86 } 87 } 88 free((struct node_t *) *rootp); /* D4: Free node */ 89 *rootp = q; /* link parent to new node */ 90 return(p); 91 } 92 93 /* Walk the nodes of a tree */ 94 static void 95 trecurse(node *root, void (*action)(const void *, VISIT, int), int level) 96 { 97 if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0) 98 (*action)(root, leaf, level); 99 else { 100 (*action)(root, preorder, level); 101 if (root->left != (struct node_t *)0) 102 trecurse(root->left, action, level + 1); 103 (*action)(root, postorder, level); 104 if (root->right != (struct node_t *)0) 105 trecurse(root->right, action, level + 1); 106 (*action)(root, endorder, level); 107 } 108 } 109 110 /* Walk the nodes of a tree */ 111 void 112 twalk(const void *vroot, void (*action)(const void *, VISIT, int)) 113 { 114 node *root = (node *)vroot; 115 116 if (root != (node *)0 && action != (void (*)(const void *, VISIT, int))0) 117 trecurse(root, action, 0); 118 } 119
