usr/src/lib/libc/port/gen/tfind.c

   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 #pragma ident   "%Z%%M% %I%     %E% SMI"
  31
  32 /*
  33  * Tree search algorithm, generalized from Knuth (6.2.2) Algorithm T.
  34  *
  35  * The NODE * arguments are declared in the lint files as char *,
  36  * because the definition of NODE isn't available to the user.
  37  */
  38
  39 #pragma weak _tfind = tfind
  40
  41 #include "lint.h"
  42 #include <mtlib.h>
  43 #include <sys/types.h>
  44 #include <search.h>
  45 #include <thread.h>
  46 #include <synch.h>
  47
  48 typedef struct node { void *key; struct node *llink, *rlink; } NODE;
  49
  50
  51 /*      tfind - find a node, or return 0        */
  52 /*
  53  * ky is Key to be located
  54  * rtp is the Address of the root of the tree
  55  * compar is the Comparison function
  56  */
  57 void *
  58 tfind(const void *ky, void *const *rtp,
  59     int (*compar)(const void *, const void *))
  60 {
  61         void *key = (char *)ky;
  62         NODE **rootp = (NODE **)rtp;
  63         if (rootp == NULL)
  64                 return (NULL);
  65         while (*rootp != NULL) {                        /* T1: */
  66                 int r = (*compar)(key, (*rootp)->key);  /* T2: */
  67                 if (r == 0)
  68                         return ((void *)*rootp);        /* Key found */
  69                 rootp = (r < 0) ?
  70                     &(*rootp)->llink :          /* T3: Take left branch */
  71                     &(*rootp)->rlink;           /* T4: Take right branch */
  72         }
  73         return (NULL);
  74 }