usr/src/lib/libbc/libc/gen/common/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, Version 1.0 only
   6  * (the "License").  You may not use this file except in compliance
   7  * with the License.
   8  *
   9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
  10  * or http://www.opensolaris.org/os/licensing.
  11  * See the License for the specific language governing permissions
  12  * and limitations under the License.
  13  *
  14  * When distributing Covered Code, include this CDDL HEADER in each
  15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  16  * If applicable, add the following below this CDDL HEADER, with the
  17  * fields enclosed by brackets "[]" replaced with your own identifying
  18  * information: Portions Copyright [yyyy] [name of copyright owner]
  19  *
  20  * CDDL HEADER END
  21  */
  22 /*      Copyright (c) 1984 AT&T */
  23 /*        All Rights Reserved   */
  24
  25 #pragma ident   "%Z%%M% %I%     %E% SMI"  /* from S5R2 1.2 */
  26
  27 /*LINTLIBRARY*/
  28 /*
  29  * Tree search algorithm, generalized from Knuth (6.2.2) Algorithm T.
  30  *
  31  * The NODE * arguments are declared in the lint files as char *,
  32  * because the definition of NODE isn't available to the user.
  33  */
  34
  35 #include <search.h>
  36 typedef char *POINTER;
  37 typedef struct node { POINTER key; struct node *llink, *rlink; } NODE;
  38
  39 #define NULL    0
  40
  41
  42 /*      tfind - find a node, or return 0        */
  43 NODE *
  44 tfind(key, rootp, compar)
  45 POINTER key;                    /* Key to be located */
  46 register NODE   **rootp;        /* Address of the root of the tree */
  47 int     (*compar)();            /* Comparison function */
  48 {
  49         if (rootp == NULL)
  50                 return (NULL);
  51         while (*rootp != NULL) {                        /* T1: */
  52                 int r = (*compar)(key, (*rootp)->key);  /* T2: */
  53                 if (r == 0)
  54                         return (*rootp);        /* Key found */
  55                 rootp = (r < 0) ?
  56                     &(*rootp)->llink :          /* T3: Take left branch */
  57                     &(*rootp)->rlink;           /* T4: Take right branch */
  58         }
  59         return (NODE *)(NULL);
  60 }