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