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 * The NODE * arguments are declared in the lint files as char *,
347c478bd9Sstevel@tonic-gate * because the definition of NODE isn't available to the user.
357c478bd9Sstevel@tonic-gate */
367c478bd9Sstevel@tonic-gate
37*7257d1b4Sraf #pragma weak _tfind = tfind
387c478bd9Sstevel@tonic-gate
39*7257d1b4Sraf #include "lint.h"
407c478bd9Sstevel@tonic-gate #include <mtlib.h>
417c478bd9Sstevel@tonic-gate #include <sys/types.h>
427c478bd9Sstevel@tonic-gate #include <search.h>
437c478bd9Sstevel@tonic-gate #include <thread.h>
447c478bd9Sstevel@tonic-gate #include <synch.h>
457c478bd9Sstevel@tonic-gate
467c478bd9Sstevel@tonic-gate typedef struct node { void *key; struct node *llink, *rlink; } NODE;
477c478bd9Sstevel@tonic-gate
487c478bd9Sstevel@tonic-gate
497c478bd9Sstevel@tonic-gate /* tfind - find a node, or return 0 */
507c478bd9Sstevel@tonic-gate /*
517c478bd9Sstevel@tonic-gate * ky is Key to be located
527c478bd9Sstevel@tonic-gate * rtp is the Address of the root of the tree
537c478bd9Sstevel@tonic-gate * compar is the Comparison function
547c478bd9Sstevel@tonic-gate */
557c478bd9Sstevel@tonic-gate void *
tfind(const void * ky,void * const * rtp,int (* compar)(const void *,const void *))567c478bd9Sstevel@tonic-gate tfind(const void *ky, void *const *rtp,
577c478bd9Sstevel@tonic-gate int (*compar)(const void *, const void *))
587c478bd9Sstevel@tonic-gate {
597c478bd9Sstevel@tonic-gate void *key = (char *)ky;
607c478bd9Sstevel@tonic-gate NODE **rootp = (NODE **)rtp;
617c478bd9Sstevel@tonic-gate if (rootp == NULL)
627c478bd9Sstevel@tonic-gate return (NULL);
637c478bd9Sstevel@tonic-gate while (*rootp != NULL) { /* T1: */
647c478bd9Sstevel@tonic-gate int r = (*compar)(key, (*rootp)->key); /* T2: */
657c478bd9Sstevel@tonic-gate if (r == 0)
667c478bd9Sstevel@tonic-gate return ((void *)*rootp); /* Key found */
677c478bd9Sstevel@tonic-gate rootp = (r < 0) ?
687c478bd9Sstevel@tonic-gate &(*rootp)->llink : /* T3: Take left branch */
697c478bd9Sstevel@tonic-gate &(*rootp)->rlink; /* T4: Take right branch */
707c478bd9Sstevel@tonic-gate }
717c478bd9Sstevel@tonic-gate return (NULL);
727c478bd9Sstevel@tonic-gate }
73