17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
5*7257d1b4Sraf * Common Development and Distribution License (the "License").
6*7257d1b4Sraf * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate * and limitations under the License.
127c478bd9Sstevel@tonic-gate *
137c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate *
197c478bd9Sstevel@tonic-gate * CDDL HEADER END
207c478bd9Sstevel@tonic-gate */
21*7257d1b4Sraf
227c478bd9Sstevel@tonic-gate /*
23*7257d1b4Sraf * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
247c478bd9Sstevel@tonic-gate * Use is subject to license terms.
257c478bd9Sstevel@tonic-gate */
267c478bd9Sstevel@tonic-gate
277c478bd9Sstevel@tonic-gate /* Copyright (c) 1988 AT&T */
287c478bd9Sstevel@tonic-gate /* All Rights Reserved */
297c478bd9Sstevel@tonic-gate
307c478bd9Sstevel@tonic-gate /*
317c478bd9Sstevel@tonic-gate * Tree search algorithm, generalized from Knuth (6.2.2) Algorithm T.
327c478bd9Sstevel@tonic-gate *
337c478bd9Sstevel@tonic-gate *
347c478bd9Sstevel@tonic-gate * The NODE * arguments are declared in the lint files as char *,
357c478bd9Sstevel@tonic-gate * because the definition of NODE isn't available to the user.
367c478bd9Sstevel@tonic-gate */
377c478bd9Sstevel@tonic-gate
38*7257d1b4Sraf #pragma weak _tdelete = tdelete
39*7257d1b4Sraf #pragma weak _tsearch = tsearch
40*7257d1b4Sraf #pragma weak _twalk = twalk
417c478bd9Sstevel@tonic-gate
42*7257d1b4Sraf #include "lint.h"
437c478bd9Sstevel@tonic-gate #include "mtlib.h"
447c478bd9Sstevel@tonic-gate #include "libc.h"
457c478bd9Sstevel@tonic-gate #include <sys/types.h>
467c478bd9Sstevel@tonic-gate #include <search.h>
477c478bd9Sstevel@tonic-gate #include <stdlib.h>
487c478bd9Sstevel@tonic-gate #include <thread.h>
497c478bd9Sstevel@tonic-gate #include <synch.h>
507c478bd9Sstevel@tonic-gate
517c478bd9Sstevel@tonic-gate
527c478bd9Sstevel@tonic-gate
537c478bd9Sstevel@tonic-gate typedef struct node { char *key; struct node *llink, *rlink; } NODE;
547c478bd9Sstevel@tonic-gate
557c478bd9Sstevel@tonic-gate static void __twalk(NODE *, void (*)(const void *, VISIT, int), int);
567c478bd9Sstevel@tonic-gate
577c478bd9Sstevel@tonic-gate
587c478bd9Sstevel@tonic-gate /* Find or insert key into search tree */
597c478bd9Sstevel@tonic-gate void *
tsearch(const void * ky,void ** rtp,int (* compar)())607c478bd9Sstevel@tonic-gate tsearch(const void *ky, void **rtp, int (*compar)())
617c478bd9Sstevel@tonic-gate {
627c478bd9Sstevel@tonic-gate char *key = (char *)ky;
637c478bd9Sstevel@tonic-gate NODE **rootp = (NODE **)rtp;
647c478bd9Sstevel@tonic-gate NODE *q; /* New node if key not found */
657c478bd9Sstevel@tonic-gate
667c478bd9Sstevel@tonic-gate if (rootp == NULL)
677c478bd9Sstevel@tonic-gate return (NULL);
687c478bd9Sstevel@tonic-gate while (*rootp != NULL) { /* T1: */
697c478bd9Sstevel@tonic-gate int r = (*compar)(key, (*rootp)->key); /* T2: */
707c478bd9Sstevel@tonic-gate if (r == 0)
717c478bd9Sstevel@tonic-gate return ((void *)*rootp); /* Key found */
727c478bd9Sstevel@tonic-gate rootp = (r < 0) ?
737c478bd9Sstevel@tonic-gate &(*rootp)->llink : /* T3: Take left branch */
747c478bd9Sstevel@tonic-gate &(*rootp)->rlink; /* T4: Take right branch */
757c478bd9Sstevel@tonic-gate }
767c478bd9Sstevel@tonic-gate q = lmalloc(sizeof (NODE)); /* T5: Not found */
777c478bd9Sstevel@tonic-gate if (q != NULL) { /* Allocate new node */
787c478bd9Sstevel@tonic-gate *rootp = q; /* Link new node to old */
797c478bd9Sstevel@tonic-gate q->key = key; /* Initialize new node */
807c478bd9Sstevel@tonic-gate q->llink = q->rlink = NULL;
817c478bd9Sstevel@tonic-gate }
827c478bd9Sstevel@tonic-gate return ((void *)q);
837c478bd9Sstevel@tonic-gate }
847c478bd9Sstevel@tonic-gate
857c478bd9Sstevel@tonic-gate /* Delete node with key key */
867c478bd9Sstevel@tonic-gate void *
tdelete(const void * ky,void ** rtp,int (* compar)())877c478bd9Sstevel@tonic-gate tdelete(const void *ky, void **rtp, int (*compar)())
887c478bd9Sstevel@tonic-gate {
897c478bd9Sstevel@tonic-gate char *key = (char *)ky;
907c478bd9Sstevel@tonic-gate NODE **rootp = (NODE **)rtp;
917c478bd9Sstevel@tonic-gate NODE *p; /* Parent of node to be deleted */
927c478bd9Sstevel@tonic-gate NODE *q; /* Successor node */
937c478bd9Sstevel@tonic-gate NODE *r; /* Right son node */
947c478bd9Sstevel@tonic-gate int ans; /* Result of comparison */
957c478bd9Sstevel@tonic-gate
967c478bd9Sstevel@tonic-gate if (rootp == NULL || (p = *rootp) == NULL)
977c478bd9Sstevel@tonic-gate return (NULL);
987c478bd9Sstevel@tonic-gate while ((ans = (*compar)(key, (*rootp)->key)) != 0) {
997c478bd9Sstevel@tonic-gate p = *rootp;
1007c478bd9Sstevel@tonic-gate rootp = (ans < 0) ?
1017c478bd9Sstevel@tonic-gate &(*rootp)->llink : /* Take left branch */
1027c478bd9Sstevel@tonic-gate &(*rootp)->rlink; /* Take right branch */
1037c478bd9Sstevel@tonic-gate if (*rootp == NULL)
1047c478bd9Sstevel@tonic-gate return (NULL); /* Key not found */
1057c478bd9Sstevel@tonic-gate }
1067c478bd9Sstevel@tonic-gate r = (*rootp)->rlink; /* D1: */
1077c478bd9Sstevel@tonic-gate if ((q = (*rootp)->llink) == NULL) /* Llink NULL? */
1087c478bd9Sstevel@tonic-gate q = r;
1097c478bd9Sstevel@tonic-gate else if (r != NULL) { /* Rlink NULL? */
1107c478bd9Sstevel@tonic-gate if (r->llink == NULL) { /* D2: Find successor */
1117c478bd9Sstevel@tonic-gate r->llink = q;
1127c478bd9Sstevel@tonic-gate q = r;
1137c478bd9Sstevel@tonic-gate } else { /* D3: Find NULL link */
1147c478bd9Sstevel@tonic-gate for (q = r->llink; q->llink != NULL; q = r->llink)
1157c478bd9Sstevel@tonic-gate r = q;
1167c478bd9Sstevel@tonic-gate r->llink = q->rlink;
1177c478bd9Sstevel@tonic-gate q->llink = (*rootp)->llink;
1187c478bd9Sstevel@tonic-gate q->rlink = (*rootp)->rlink;
1197c478bd9Sstevel@tonic-gate }
1207c478bd9Sstevel@tonic-gate }
1217c478bd9Sstevel@tonic-gate lfree(*rootp, sizeof (NODE)); /* D4: Free node */
1227c478bd9Sstevel@tonic-gate *rootp = q; /* Link parent to replacement */
1237c478bd9Sstevel@tonic-gate return ((void *)p);
1247c478bd9Sstevel@tonic-gate }
1257c478bd9Sstevel@tonic-gate
1267c478bd9Sstevel@tonic-gate
1277c478bd9Sstevel@tonic-gate /* Walk the nodes of a tree */
1287c478bd9Sstevel@tonic-gate void
twalk(const void * rt,void (* action)(const void *,VISIT,int))1297c478bd9Sstevel@tonic-gate twalk(const void *rt, /* Root of the tree to be walked */
1307c478bd9Sstevel@tonic-gate void (*action)(const void *, VISIT, int))
1317c478bd9Sstevel@tonic-gate {
1327c478bd9Sstevel@tonic-gate NODE *root = (NODE *)rt;
1337c478bd9Sstevel@tonic-gate
1347c478bd9Sstevel@tonic-gate if (root != NULL && action != NULL)
1357c478bd9Sstevel@tonic-gate __twalk(root, action, 0);
1367c478bd9Sstevel@tonic-gate }
1377c478bd9Sstevel@tonic-gate
1387c478bd9Sstevel@tonic-gate
1397c478bd9Sstevel@tonic-gate /* Walk the nodes of a tree */
1407c478bd9Sstevel@tonic-gate static void
__twalk(NODE * root,void (* action)(const void *,VISIT,int),int level)1417c478bd9Sstevel@tonic-gate __twalk(NODE *root, /* Root of the tree to be walked */
1427c478bd9Sstevel@tonic-gate void (*action)(const void *, VISIT, int),
1437c478bd9Sstevel@tonic-gate int level)
1447c478bd9Sstevel@tonic-gate {
1457c478bd9Sstevel@tonic-gate if (root->llink == NULL && root->rlink == NULL)
1467c478bd9Sstevel@tonic-gate (*action)(root, leaf, level);
1477c478bd9Sstevel@tonic-gate else {
1487c478bd9Sstevel@tonic-gate (*action)(root, preorder, level);
1497c478bd9Sstevel@tonic-gate if (root->llink != NULL)
1507c478bd9Sstevel@tonic-gate __twalk(root->llink, action, level + 1);
1517c478bd9Sstevel@tonic-gate (*action)(root, postorder, level);
1527c478bd9Sstevel@tonic-gate if (root->rlink != NULL)
1537c478bd9Sstevel@tonic-gate __twalk(root->rlink, action, level + 1);
1547c478bd9Sstevel@tonic-gate (*action)(root, endorder, level);
1557c478bd9Sstevel@tonic-gate }
1567c478bd9Sstevel@tonic-gate }
157