1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* Copyright (c) 1984 AT&T */ 23 /* All Rights Reserved */ 24 25 #pragma ident "%Z%%M% %I% %E% SMI" /* from S5R2 2.3 */ 26 27 /*LINTLIBRARY*/ 28 /* 29 * Tree search algorithm, generalized from Knuth (6.2.2) Algorithm T. 30 * 31 * 32 * The NODE * arguments are declared in the lint files as char *, 33 * because the definition of NODE isn't available to the user. 34 */ 35 36 #include <search.h> 37 typedef char *POINTER; 38 typedef struct node { POINTER key; struct node *llink, *rlink; } NODE; 39 40 #define NULL 0 41 42 extern char *malloc(); 43 44 NODE * 45 tsearch(key, rootp, compar) /* Find or insert key into search tree*/ 46 POINTER key; /* Key to be located */ 47 register NODE **rootp; /* Address of the root of the tree */ 48 int (*compar)(); /* Comparison function */ 49 { 50 register NODE *q; /* New node if key not found */ 51 52 if (rootp == NULL) 53 return (NULL); 54 while (*rootp != NULL) { /* T1: */ 55 int r = (*compar)(key, (*rootp)->key); /* T2: */ 56 if (r == 0) 57 return (*rootp); /* Key found */ 58 rootp = (r < 0) ? 59 &(*rootp)->llink : /* T3: Take left branch */ 60 &(*rootp)->rlink; /* T4: Take right branch */ 61 } 62 q = (NODE *) malloc(sizeof(NODE)); /* T5: Not found */ 63 if (q != NULL) { /* Allocate new node */ 64 *rootp = q; /* Link new node to old */ 65 q->key = key; /* Initialize new node */ 66 q->llink = q->rlink = NULL; 67 } 68 return (q); 69 } 70 71 NODE * 72 tdelete(key, rootp, compar) /* Delete node with key key */ 73 POINTER key; /* Key to be deleted */ 74 register NODE **rootp; /* Address of the root of tree */ 75 int (*compar)(); /* Comparison function */ 76 { 77 NODE *p; /* Parent of node to be deleted */ 78 register NODE *q; /* Successor node */ 79 register NODE *r; /* Right son node */ 80 int ans; /* Result of comparison */ 81 82 if (rootp == NULL || (p = *rootp) == NULL) 83 return (NULL); 84 while ((ans = (*compar)(key, (*rootp)->key)) != 0) { 85 p = *rootp; 86 rootp = (ans < 0) ? 87 &(*rootp)->llink : /* Take left branch */ 88 &(*rootp)->rlink; /* Take right branch */ 89 if (*rootp == NULL) 90 return (NULL); /* Key not found */ 91 } 92 r = (*rootp)->rlink; /* D1: */ 93 if ((q = (*rootp)->llink) == NULL) /* Llink NULL? */ 94 q = r; 95 else if (r != NULL) { /* Rlink NULL? */ 96 if (r->llink == NULL) { /* D2: Find successor */ 97 r->llink = q; 98 q = r; 99 } else { /* D3: Find NULL link */ 100 for (q = r->llink; q->llink != NULL; q = r->llink) 101 r = q; 102 r->llink = q->rlink; 103 q->llink = (*rootp)->llink; 104 q->rlink = (*rootp)->rlink; 105 } 106 } 107 free((POINTER) *rootp); /* D4: Free node */ 108 *rootp = q; /* Link parent to replacement */ 109 return (p); 110 } 111 112 void 113 twalk(root, action) /* Walk the nodes of a tree */ 114 NODE *root; /* Root of the tree to be walked */ 115 void (*action)(); /* Function to be called at each node */ 116 { 117 void _twalk(); 118 119 if (root != NULL && action != NULL) 120 _twalk(root, action, 0); 121 } 122 123 static void 124 _twalk(root, action, level) /* Walk the nodes of a tree */ 125 register NODE *root; /* Root of the tree to be walked */ 126 register void (*action)(); /* Function to be called at each node */ 127 register int level; 128 { 129 if (root->llink == NULL && root->rlink == NULL) 130 (*action)(root, leaf, level); 131 else { 132 (*action)(root, preorder, level); 133 if (root->llink != NULL) 134 _twalk(root->llink, action, level + 1); 135 (*action)(root, postorder, level); 136 if (root->rlink != NULL) 137 _twalk(root->rlink, action, level + 1); 138 (*action)(root, endorder, level); 139 } 140 } 141