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