1 /* $OpenBSD: tsearch.c,v 1.8 2014/03/16 18:38:30 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 /*LINTLIBRARY*/ 14 15 #include <search.h> 16 #include <stdlib.h> 17 18 typedef struct node_t { 19 char *key; 20 struct node_t *left, *right; 21 } node; 22 23 /* find or insert datum into search tree */ 24 void * 25 tsearch(const void *vkey, void **vrootp, 26 int (*compar)(const void *, const void *)) 27 { 28 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(const void *vkey, void **vrootp, 55 int (*compar)(const void *, const void *)) 56 { 57 node **rootp = (node **)vrootp; 58 char *key = (char *)vkey; 59 node *p = (node *)1; 60 node *q; 61 node *r; 62 int cmp; 63 64 if (rootp == (struct node_t **)0 || *rootp == (struct node_t *)0) 65 return ((struct node_t *)0); 66 while ((cmp = (*compar)(key, (*rootp)->key)) != 0) { 67 p = *rootp; 68 rootp = (cmp < 0) ? 69 &(*rootp)->left : /* follow left branch */ 70 &(*rootp)->right; /* follow right branch */ 71 if (*rootp == (struct node_t *)0) 72 return ((void *)0); /* key not found */ 73 } 74 r = (*rootp)->right; /* D1: */ 75 if ((q = (*rootp)->left) == (struct node_t *)0) /* Left (struct node_t *)0? */ 76 q = r; 77 else if (r != (struct node_t *)0) { /* Right link is null? */ 78 if (r->left == (struct node_t *)0) { /* D2: Find successor */ 79 r->left = q; 80 q = r; 81 } else { /* D3: Find (struct node_t *)0 link */ 82 for (q = r->left; q->left != (struct node_t *)0; q = r->left) 83 r = q; 84 r->left = q->right; 85 q->left = (*rootp)->left; 86 q->right = (*rootp)->right; 87 } 88 } 89 free((struct node_t *) *rootp); /* D4: Free node */ 90 *rootp = q; /* link parent to new node */ 91 return(p); 92 } 93 94 /* Walk the nodes of a tree */ 95 static void 96 trecurse(node *root, void (*action)(const void *, VISIT, int), int level) 97 { 98 if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0) 99 (*action)(root, leaf, level); 100 else { 101 (*action)(root, preorder, level); 102 if (root->left != (struct node_t *)0) 103 trecurse(root->left, action, level + 1); 104 (*action)(root, postorder, level); 105 if (root->right != (struct node_t *)0) 106 trecurse(root->right, action, level + 1); 107 (*action)(root, endorder, level); 108 } 109 } 110 111 /* Walk the nodes of a tree */ 112 void 113 twalk(const void *vroot, void (*action)(const void *, VISIT, int)) 114 { 115 node *root = (node *)vroot; 116 117 if (root != (node *)0 && action != (void (*)(const void *, VISIT, int))0) 118 trecurse(root, action, 0); 119 } 120
