gonzui

    1: /*      $OpenBSD: tfind.c,v 1.5 2005/03/30 18:51:49 pat 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:  * The node_t structure is for internal use only, lint doesn't grok it.
    8:  *
    9:  * Written by reading the System V Interface Definition, not the code.
   10:  *
   11:  * Totally public domain.
   12:  */
   13: /*LINTLIBRARY*/
   14: #include <search.h>
   15: 
   16: typedef struct node_t
   17: {
   18:     char          *key;
   19:     struct node_t *llink, *rlink;
   20: } node;
   21: 
   22: /* find a node, or return 0 */
   23: void *
   24: tfind(const void *vkey, void * const *vrootp,
   25:     int (*compar)(const void *, const void *))
   26: {
   27:     char *key = (char *)vkey;
   28:     node **rootp = (node **)vrootp;
   29: 
   30:     if (rootp == (struct node_t **)0)
   31:         return ((struct node_t *)0);
   32:     while (*rootp != (struct node_t *)0) {      /* T1: */
   33:         int r;
   34:         if ((r = (*compar)(key, (*rootp)->key)) == 0)  /* T2: */
   35:             return (*rootp);           /* key found */
   36:         rootp = (r < 0) ?
   37:             &(*rootp)->llink :         /* T3: follow left branch */
   38:             &(*rootp)->rlink;          /* T4: follow right branch */
   39:     }
   40:     return (node *)0;
   41: }