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