crypto/external/bsd/heimdal/dist/lib/roken/tsearch.c

   1 /*      $NetBSD: tsearch.c,v 1.1.1.2 2014/04/24 12:45:52 pettai 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  * NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp
  14  * NetBSD: twalk.c,v 1.1 1999/02/22 10:33:16 christos Exp
  15  * NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp
  16  * NetBSD: tfind.c,v 1.2 1999/09/16 11:45:37 lukem Exp
  17  */
  18
  19 #include <config.h>
  20 #include <krb5/roken.h>
  21 #include "search.h"
  22 #include <stdlib.h>
  23
  24 typedef struct node {
  25   char         *key;
  26   struct node  *llink, *rlink;
  27 } node_t;
  28
  29 #ifndef __DECONST
  30 #define __DECONST(type, var)    ((type)(uintptr_t)(const void *)(var))
  31 #endif
  32
  33 /*
  34  * find or insert datum into search tree
  35  *
  36  * Parameters:
  37  *      vkey:   key to be located
  38  *      vrootp: address of tree root
  39  */
  40
  41 ROKEN_LIB_FUNCTION void *
  42 rk_tsearch(const void *vkey, void **vrootp,
  43         int (*compar)(const void *, const void *))
  44 {
  45         node_t *q;
  46         node_t **rootp = (node_t **)vrootp;
  47
  48         if (rootp == NULL)
  49                 return NULL;
  50
  51         while (*rootp != NULL) {        /* Knuth's T1: */
  52                 int r;
  53
  54                 if ((r = (*compar)(vkey, (*rootp)->key)) == 0)  /* T2: */
  55                         return *rootp;          /* we found it! */
  56
  57                 rootp = (r < 0) ?
  58                     &(*rootp)->llink :          /* T3: follow left branch */
  59                     &(*rootp)->rlink;           /* T4: follow right branch */
  60         }
  61
  62         q = malloc(sizeof(node_t));             /* T5: key not found */
  63         if (q != 0) {                           /* make new node */
  64                 *rootp = q;                     /* link new node to old */
  65                 /* LINTED const castaway ok */
  66                 q->key = __DECONST(void *, vkey); /* initialize new node */
  67                 q->llink = q->rlink = NULL;
  68         }
  69         return q;
  70 }
  71
  72 /*
  73  * Walk the nodes of a tree
  74  *
  75  * Parameters:
  76  *      root:   Root of the tree to be walked
  77  */
  78 static void
  79 trecurse(const node_t *root, void (*action)(const void *, VISIT, int),
  80          int level)
  81 {
  82
  83         if (root->llink == NULL && root->rlink == NULL)
  84                 (*action)(root, leaf, level);
  85         else {
  86                 (*action)(root, preorder, level);
  87                 if (root->llink != NULL)
  88                         trecurse(root->llink, action, level + 1);
  89                 (*action)(root, postorder, level);
  90                 if (root->rlink != NULL)
  91                         trecurse(root->rlink, action, level + 1);
  92                 (*action)(root, endorder, level);
  93         }
  94 }
  95
  96 /*
  97  * Walk the nodes of a tree
  98  *
  99  * Parameters:
 100  *      vroot:  Root of the tree to be walked
 101  */
 102 ROKEN_LIB_FUNCTION void
 103 rk_twalk(const void *vroot,
 104       void (*action)(const void *, VISIT, int))
 105 {
 106         if (vroot != NULL && action != NULL)
 107                 trecurse(vroot, action, 0);
 108 }
 109
 110 /*
 111  * delete node with given key
 112  *
 113  * vkey:   key to be deleted
 114  * vrootp: address of the root of the tree
 115  * compar: function to carry out node comparisons
 116  */
 117 ROKEN_LIB_FUNCTION void *
 118 rk_tdelete(const void * vkey, void ** vrootp,
 119         int (*compar)(const void *, const void *))
 120 {
 121         node_t **rootp = (node_t **)vrootp;
 122         node_t *p, *q, *r;
 123         int cmp;
 124
 125         if (rootp == NULL || (p = *rootp) == NULL)
 126                 return NULL;
 127
 128         while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) {
 129                 p = *rootp;
 130                 rootp = (cmp < 0) ?
 131                     &(*rootp)->llink :          /* follow llink branch */
 132                     &(*rootp)->rlink;           /* follow rlink branch */
 133                 if (*rootp == NULL)
 134                         return NULL;            /* key not found */
 135         }
 136         r = (*rootp)->rlink;                    /* D1: */
 137         if ((q = (*rootp)->llink) == NULL)      /* Left NULL? */
 138                 q = r;
 139         else if (r != NULL) {                   /* Right link is NULL? */
 140                 if (r->llink == NULL) {         /* D2: Find successor */
 141                         r->llink = q;
 142                         q = r;
 143                 } else {                        /* D3: Find NULL link */
 144                         for (q = r->llink; q->llink != NULL; q = r->llink)
 145                                 r = q;
 146                         r->llink = q->rlink;
 147                         q->llink = (*rootp)->llink;
 148                         q->rlink = (*rootp)->rlink;
 149                 }
 150         }
 151         free(*rootp);                           /* D4: Free node */
 152         *rootp = q;                             /* link parent to new node */
 153         return p;
 154 }
 155
 156 /*
 157  * find a node, or return 0
 158  *
 159  * Parameters:
 160  *      vkey:   key to be found
 161  *      vrootp: address of the tree root
 162  */
 163 ROKEN_LIB_FUNCTION void *
 164 rk_tfind(const void *vkey, void * const *vrootp,
 165       int (*compar)(const void *, const void *))
 166 {
 167         node_t **rootp = (node_t **)vrootp;
 168
 169         if (rootp == NULL)
 170                 return NULL;
 171
 172         while (*rootp != NULL) {                /* T1: */
 173                 int r;
 174
 175                 if ((r = (*compar)(vkey, (*rootp)->key)) == 0)  /* T2: */
 176                         return *rootp;          /* key found */
 177                 rootp = (r < 0) ?
 178                     &(*rootp)->llink :          /* T3: follow left branch */
 179                     &(*rootp)->rlink;           /* T4: follow right branch */
 180         }
 181         return NULL;
 182 }