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 /* 23 * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 #pragma ident "%Z%%M% %I% %E% SMI" 28 29 /* Copyright (c) 1988 AT&T */ 30 /* All Rights Reserved */ 31 32 33 /* 34 * Tree search algorithm, generalized from Knuth (6.2.2) Algorithm T. 35 * 36 * 37 * The NODE * arguments are declared in the lint files as char *, 38 * because the definition of NODE isn't available to the user. 39 */ 40 41 #pragma weak tdelete = _tdelete 42 #pragma weak tsearch = _tsearch 43 #pragma weak twalk = _twalk 44 45 #include "synonyms.h" 46 #include "mtlib.h" 47 #include "libc.h" 48 #include <sys/types.h> 49 #include <search.h> 50 #include <stdlib.h> 51 #include <thread.h> 52 #include <synch.h> 53 54 55 56 typedef struct node { char *key; struct node *llink, *rlink; } NODE; 57 58 static void __twalk(NODE *, void (*)(const void *, VISIT, int), int); 59 60 61 /* Find or insert key into search tree */ 62 void * 63 tsearch(const void *ky, void **rtp, int (*compar)()) 64 { 65 char *key = (char *)ky; 66 NODE **rootp = (NODE **)rtp; 67 NODE *q; /* New node if key not found */ 68 69 if (rootp == NULL) 70 return (NULL); 71 while (*rootp != NULL) { /* T1: */ 72 int r = (*compar)(key, (*rootp)->key); /* T2: */ 73 if (r == 0) 74 return ((void *)*rootp); /* Key found */ 75 rootp = (r < 0) ? 76 &(*rootp)->llink : /* T3: Take left branch */ 77 &(*rootp)->rlink; /* T4: Take right branch */ 78 } 79 q = lmalloc(sizeof (NODE)); /* T5: Not found */ 80 if (q != NULL) { /* Allocate new node */ 81 *rootp = q; /* Link new node to old */ 82 q->key = key; /* Initialize new node */ 83 q->llink = q->rlink = NULL; 84 } 85 return ((void *)q); 86 } 87 88 /* Delete node with key key */ 89 void * 90 tdelete(const void *ky, void **rtp, int (*compar)()) 91 { 92 char *key = (char *)ky; 93 NODE **rootp = (NODE **)rtp; 94 NODE *p; /* Parent of node to be deleted */ 95 NODE *q; /* Successor node */ 96 NODE *r; /* Right son node */ 97 int ans; /* Result of comparison */ 98 99 if (rootp == NULL || (p = *rootp) == NULL) 100 return (NULL); 101 while ((ans = (*compar)(key, (*rootp)->key)) != 0) { 102 p = *rootp; 103 rootp = (ans < 0) ? 104 &(*rootp)->llink : /* Take left branch */ 105 &(*rootp)->rlink; /* Take right branch */ 106 if (*rootp == NULL) 107 return (NULL); /* Key not found */ 108 } 109 r = (*rootp)->rlink; /* D1: */ 110 if ((q = (*rootp)->llink) == NULL) /* Llink NULL? */ 111 q = r; 112 else if (r != NULL) { /* Rlink NULL? */ 113 if (r->llink == NULL) { /* D2: Find successor */ 114 r->llink = q; 115 q = r; 116 } else { /* D3: Find NULL link */ 117 for (q = r->llink; q->llink != NULL; q = r->llink) 118 r = q; 119 r->llink = q->rlink; 120 q->llink = (*rootp)->llink; 121 q->rlink = (*rootp)->rlink; 122 } 123 } 124 lfree(*rootp, sizeof (NODE)); /* D4: Free node */ 125 *rootp = q; /* Link parent to replacement */ 126 return ((void *)p); 127 } 128 129 130 /* Walk the nodes of a tree */ 131 void 132 twalk(const void *rt, /* Root of the tree to be walked */ 133 void (*action)(const void *, VISIT, int)) 134 { 135 NODE *root = (NODE *)rt; 136 137 if (root != NULL && action != NULL) 138 __twalk(root, action, 0); 139 } 140 141 142 /* Walk the nodes of a tree */ 143 static void 144 __twalk(NODE *root, /* Root of the tree to be walked */ 145 void (*action)(const void *, VISIT, int), 146 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