mingwrt/mingwex/tfind.c

   1 /* $NetBSD: tfind.c,v 1.3.18.2 2005/03/23 11:12:21 tron Exp $
   2  *
   3  *
   4  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
   5  * the AT&T man page says.
   6  *
   7  * Written by reading the System V Interface Definition, not the code.
   8  *
   9  * Totally public domain.
  10  *
  11  */
  12 #define _SEARCH_PRIVATE
  13 #include <stdlib.h>
  14 #include <search.h>
  15
  16 __CRT_ALIAS void *__tfind
  17 (const void *key, node_t *const *rootp, int (*compar)(const void *, const void *))
  18 {
  19   /* Find node with specified "key", within tree referred to by "rootp";
  20    * return NULL if not found, (or if either "rootp" or "compar" is not
  21    * a valid pointer).
  22    *
  23    * NOTE: node_t is defined as a structured data type, for internal use
  24    * when _SEARCH_PRIVATE is enabled; for public consumption, it becomes
  25    * an alias for "void", (assuming _SEARCH_PRIVATE is NOT enabled).
  26    */
  27   if( (rootp == NULL) || (compar == NULL) )
  28     return NULL;
  29
  30   while (*rootp != NULL)        /* Knuth's T1: */
  31   {
  32     int cmp;                    /* T2: */
  33     if( (cmp = (*compar)(key, (*rootp)->key)) == 0 )
  34       return *rootp;            /* key found */
  35
  36     rootp = (cmp < 0)
  37       ? &(*rootp)->llink        /* T3: follow left branch */
  38       : &(*rootp)->rlink;       /* T4: follow right branch */
  39   }
  40   return NULL;                  /* key not found */
  41 }
  42
  43 void *tfind
  44 (const void *key, void *const *rootp, int (*compar)(const void *, const void *))
  45 { return __tfind (key, (node_t *const *)(rootp), compar); }