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