libmicrohttpd

HTTP/1.x server C library (MHD 1.x, stable)
Log | Files | Refs | Submodules | README | LICENSE

tsearch.c (3529B)

      1 /*
      2  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
      3  * the AT&T man page says.
      4  *
      5  * The node_t structure is for internal use only, lint doesn't grok it.
      6  *
      7  * Written by reading the System V Interface Definition, not the code.
      8  *
      9  * Totally public domain.
     10  */
     11 
     12 #include "mhd_options.h"
     13 #include "tsearch.h"
     14 #ifdef HAVE_STDDEF_H
     15 #include <stddef.h>
     16 #endif /* HAVE_STDDEF_H */
     17 #ifdef HAVE_STDLIB_H
     18 #include <stdlib.h>
     19 #endif /* HAVE_STDLIB_H */
     20 
     21 
     22 typedef struct node
     23 {
     24   const void *key;
     25   struct node  *llink, *rlink;
     26 } node_t;
     27 
     28 
     29 /*  $NetBSD: tsearch.c,v 1.7 2012/06/25 22:32:45 abs Exp $  */
     30 /* find or insert datum into search tree */
     31 void *
     32 tsearch (const void *vkey, void **vrootp,
     33          int (*compar)(const void *, const void *))
     34 {
     35   node_t *q;
     36   node_t **rootp = (node_t **) vrootp;
     37 
     38   if (rootp == NULL)
     39     return NULL;
     40 
     41   while (*rootp != NULL)        /* Knuth's T1: */
     42   {
     43     int r;
     44 
     45     if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
     46       return *rootp;                               /* we found it! */
     47 
     48     rootp = (r < 0) ?
     49             &(*rootp)->llink :      /* T3: follow left branch */
     50             &(*rootp)->rlink;       /* T4: follow right branch */
     51   }
     52 
     53   q = malloc (sizeof(node_t)); /* T5: key not found */
     54   if (q != NULL)               /* make new node */
     55   {
     56     *rootp = q;                /* link new node to old */
     57     q->key = vkey; /* initialize new node */
     58     q->llink = q->rlink = NULL;
     59   }
     60   return q;
     61 }
     62 
     63 
     64 /*  $NetBSD: tfind.c,v 1.7 2012/06/25 22:32:45 abs Exp $    */
     65 /* find a node by key "vkey" in tree "vrootp", or return 0 */
     66 void *
     67 tfind (const void *vkey, void * const *vrootp,
     68        int (*compar)(const void *, const void *))
     69 {
     70   node_t * const *rootp = (node_t * const *) vrootp;
     71 
     72   if (rootp == NULL)
     73     return NULL;
     74 
     75   while (*rootp != NULL)            /* T1: */
     76   {
     77     int r;
     78 
     79     if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
     80       return *rootp;                               /* key found */
     81     rootp = (r < 0) ?
     82             &(*rootp)->llink :                     /* T3: follow left branch */
     83             &(*rootp)->rlink;                      /* T4: follow right branch */
     84   }
     85   return NULL;
     86 }
     87 
     88 
     89 /*  $NetBSD: tdelete.c,v 1.8 2016/01/20 20:47:41 christos Exp $ */
     90 /* find a node with key "vkey" in tree "vrootp" */
     91 void *
     92 tdelete (const void *vkey, void **vrootp,
     93          int (*compar)(const void *, const void *))
     94 {
     95   node_t **rootp = (node_t **) vrootp;
     96   node_t *p, *q, *r;
     97   int cmp;
     98 
     99   if ((rootp == NULL) || ((p = *rootp) == NULL) )
    100     return NULL;
    101 
    102   while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0)
    103   {
    104     p = *rootp;
    105     rootp = (cmp < 0) ?
    106             &(*rootp)->llink :       /* follow llink branch */
    107             &(*rootp)->rlink;        /* follow rlink branch */
    108     if (*rootp == NULL)
    109       return NULL;                   /* key not found */
    110   }
    111   r = (*rootp)->rlink;               /* D1: */
    112   if ((q = (*rootp)->llink) == NULL) /* Left NULL? */
    113     q = r;
    114   else if (r != NULL)                /* Right link is NULL? */
    115   {
    116     if (r->llink == NULL)            /* D2: Find successor */
    117     {
    118       r->llink = q;
    119       q = r;
    120     }
    121     else                    /* D3: Find NULL link */
    122     {
    123       for (q = r->llink; q->llink != NULL; q = r->llink)
    124         r = q;
    125       r->llink = q->rlink;
    126       q->llink = (*rootp)->llink;
    127       q->rlink = (*rootp)->rlink;
    128     }
    129   }
    130   free (*rootp);            /* D4: Free node */
    131   *rootp = q;               /* link parent to new node */
    132   return p;
    133 }
    134 
    135 
    136 /* end of tsearch.c */