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" 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 #include <stdio.h> 38 #include <malloc.h> 39 40 typedef char *POINTER; 41 typedef struct node { POINTER key; struct node *llink, *rlink; } NODE; 42 43 /* 44 * Find or insert key into search tree 45 * 46 * Arguments 47 * key: Key to be located 48 * rootp: Address of the root of the tree 49 * compar: Comparison function 50 */ 51 NODE * 52 tsearch(POINTER key, NODE **rootp, int (*compar)(POINTER, POINTER)) 53 { 54 NODE *q; /* New node if key not found */ 55 56 if (rootp == NULL) 57 return (NULL); 58 while (*rootp != NULL) { /* T1: */ 59 int r = (*compar)(key, (*rootp)->key); /* T2: */ 60 if (r == 0) 61 return (*rootp); /* Key found */ 62 rootp = (r < 0) ? 63 &(*rootp)->llink : /* T3: Take left branch */ 64 &(*rootp)->rlink; /* T4: Take right branch */ 65 } 66 q = (NODE *) malloc(sizeof(NODE)); /* T5: Not found */ 67 if (q != NULL) { /* Allocate new node */ 68 *rootp = q; /* Link new node to old */ 69 q->key = key; /* Initialize new node */ 70 q->llink = q->rlink = NULL; 71 } 72 return (q); 73 } 74 75 /* 76 * Delete node with key key 77 * 78 * Arguments 79 * key: Key to be deleted 80 * rootp: Address of the root of tree 81 * compar: Comparison function 82 */ 83 NODE * 84 tdelete(POINTER key, NODE **rootp, int (*compar)(POINTER, POINTER)) 85 { 86 NODE *p; /* Parent of node to be deleted */ 87 NODE *q; /* Successor node */ 88 NODE *r; /* Right son node */ 89 int ans; /* Result of comparison */ 90 91 if (rootp == NULL || (p = *rootp) == NULL) 92 return (NULL); 93 while ((ans = (*compar)(key, (*rootp)->key)) != 0) { 94 p = *rootp; 95 rootp = (ans < 0) ? 96 &(*rootp)->llink : /* Take left branch */ 97 &(*rootp)->rlink; /* Take right branch */ 98 if (*rootp == NULL) 99 return (NULL); /* Key not found */ 100 } 101 r = (*rootp)->rlink; /* D1: */ 102 if ((q = (*rootp)->llink) == NULL) /* Llink NULL? */ 103 q = r; 104 else if (r != NULL) { /* Rlink NULL? */ 105 if (r->llink == NULL) { /* D2: Find successor */ 106 r->llink = q; 107 q = r; 108 } else { /* D3: Find NULL link */ 109 for (q = r->llink; q->llink != NULL; q = r->llink) 110 r = q; 111 r->llink = q->rlink; 112 q->llink = (*rootp)->llink; 113 q->rlink = (*rootp)->rlink; 114 } 115 } 116 free((POINTER) *rootp); /* D4: Free node */ 117 *rootp = q; /* Link parent to replacement */ 118 return (p); 119 } 120 121 static void _twalk(NODE *, void (*)(NODE *, VISIT, int), int); 122 123 /* 124 * Walk the nodes of a tree 125 * 126 * Arguments 127 * root: Root of the tree to be walked 128 * action: Function to be called at each node 129 */ 130 void 131 twalk(NODE *root, void (*action)(NODE *, VISIT, int)) 132 { 133 134 if (root != NULL && action != NULL) 135 _twalk(root, action, 0); 136 } 137 138 /* 139 * Walk the nodes of a tree 140 * 141 * Arguments 142 * root: Root of the tree to be walked 143 * action: Function to be called at each node 144 */ 145 static void 146 _twalk(NODE *root, void (*action)(NODE *, VISIT, int), int level) 147 { 148 if (root->llink == NULL && root->rlink == NULL) 149 (*action)(root, leaf, level); 150 else { 151 (*action)(root, preorder, level); 152 if (root->llink != NULL) 153 _twalk(root->llink, action, level + 1); 154 (*action)(root, postorder, level); 155 if (root->rlink != NULL) 156 _twalk(root->rlink, action, level + 1); 157 (*action)(root, endorder, level); 158 } 159 } 160