compat/tfind.c

   1 /*****************************************************************************
   2  * tfind.c : implement every t* fuctions
   3  *****************************************************************************/
   4
   5 #ifdef HAVE_CONFIG_H
   6 # include <config.h>
   7 #endif
   8
   9 /** search.h is not present so every t* functions has to be implemented */
  10 #ifndef HAVE_SEARCH_H
  11
  12 #include <assert.h>
  13 #include <stdlib.h>
  14
  15 typedef struct node {
  16     char         *key;
  17     struct node  *llink, *rlink;
  18 } node_t;
  19
  20 /*      $NetBSD: tdelete.c,v 1.4 2006/03/19 01:12:08 christos Exp $     */
  21
  22 /*
  23  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
  24  * the AT&T man page says.
  25  *
  26  * The node_t structure is for internal use only, lint doesn't grok it.
  27  *
  28  * Written by reading the System V Interface Definition, not the code.
  29  *
  30  * Totally public domain.
  31  */
  32
  33 /* delete node with given key */
  34 void *
  35 tdelete(const void* vkey, void** vrootp, int (*compar)(const void*, const void*))
  36 {
  37         node_t **rootp = (node_t **)vrootp;
  38         node_t *p, *q, *r;
  39         int  cmp;
  40
  41         assert(vkey != NULL);
  42         assert(compar != NULL);
  43
  44         if (rootp == NULL || (p = *rootp) == NULL)
  45                 return NULL;
  46
  47         while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) {
  48                 p = *rootp;
  49                 rootp = (cmp < 0) ?
  50                     &(*rootp)->llink :          /* follow llink branch */
  51                     &(*rootp)->rlink;           /* follow rlink branch */
  52                 if (*rootp == NULL)
  53                         return NULL;            /* key not found */
  54         }
  55         r = (*rootp)->rlink;                    /* D1: */
  56         if ((q = (*rootp)->llink) == NULL)      /* Left NULL? */
  57                 q = r;
  58         else if (r != NULL) {                   /* Right link is NULL? */
  59                 if (r->llink == NULL) {         /* D2: Find successor */
  60                         r->llink = q;
  61                         q = r;
  62                 } else {                        /* D3: Find NULL link */
  63                         for (q = r->llink; q->llink != NULL; q = r->llink)
  64                                 r = q;
  65                         r->llink = q->rlink;
  66                         q->llink = (*rootp)->llink;
  67                         q->rlink = (*rootp)->rlink;
  68                 }
  69         }
  70         if (p != *rootp)
  71                 free(*rootp);                   /* D4: Free node */
  72         *rootp = q;                             /* link parent to new node */
  73         return p;
  74 }
  75
  76
  77 /*      $NetBSD: tdestroy.c,v 1.2 1999/09/16 11:45:37 lukem Exp $       */
  78
  79 /*
  80  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
  81  * the AT&T man page says.
  82  *
  83  * The node_t structure is for internal use only, lint doesn't grok it.
  84  *
  85  * Written by reading the System V Interface Definition, not the code.
  86  *
  87  * Totally public domain.
  88  */
  89
  90 /* Walk the nodes of a tree */
  91 static void
  92 tdestroy_recurse(node_t* root, void (*free_action)(void *))
  93 {
  94   if (root->llink != NULL)
  95     tdestroy_recurse(root->llink, free_action);
  96   if (root->rlink != NULL)
  97     tdestroy_recurse(root->rlink, free_action);
  98
  99   (*free_action) ((void *) root->key);
 100   free(root);
 101 }
 102
 103 void
 104 tdestroy(void *vrootp, void (*freefct)(void*))
 105 {
 106   node_t *root = (node_t *) vrootp;
 107
 108   if (root != NULL)
 109     tdestroy_recurse(root, freefct);
 110 }
 111
 112
 113 /*      $NetBSD: tfind.c,v 1.5 2005/03/23 08:16:53 kleink Exp $ */
 114
 115 /*
 116  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
 117  * the AT&T man page says.
 118  *
 119  * The node_t structure is for internal use only, lint doesn't grok it.
 120  *
 121  * Written by reading the System V Interface Definition, not the code.
 122  *
 123  * Totally public domain.
 124  */
 125
 126 /* find a node, or return 0 */
 127 void *
 128 tfind(const void* vkey, void* const *vrootp, int (*compar) (const void *, const void *))
 129 {
 130         node_t * const *rootp = (node_t * const*)vrootp;
 131
 132         assert(vkey != NULL);
 133         assert(compar != NULL);
 134
 135         if (rootp == NULL)
 136                 return NULL;
 137
 138         while (*rootp != NULL) {                /* T1: */
 139                 int r;
 140
 141                 if ((r = (*compar)(vkey, (*rootp)->key)) == 0)  /* T2: */
 142                         return *rootp;          /* key found */
 143                 rootp = (r < 0) ?
 144                     &(*rootp)->llink :          /* T3: follow left branch */
 145                     &(*rootp)->rlink;           /* T4: follow right branch */
 146         }
 147         return NULL;
 148 }
 149
 150
 151 /*      $NetBSD: tsearch.c,v 1.5 2005/11/29 03:12:00 christos Exp $     */
 152
 153 /*
 154  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
 155  * the AT&T man page says.
 156  *
 157  * The node_t structure is for internal use only, lint doesn't grok it.
 158  *
 159  * Written by reading the System V Interface Definition, not the code.
 160  *
 161  * Totally public domain.
 162  */
 163
 164 /* find or insert datum into search tree */
 165 void *
 166 tsearch(const void* vkey, void** vrootp, int (*compar)(const void*, const void*))
 167 {
 168         node_t *q;
 169         node_t **rootp = (node_t **)vrootp;
 170
 171         assert(vkey != NULL);
 172         assert(compar != NULL);
 173
 174         if (rootp == NULL)
 175                 return NULL;
 176
 177         while (*rootp != NULL) {        /* Knuth's T1: */
 178                 int r;
 179
 180                 if ((r = (*compar)(vkey, (*rootp)->key)) == 0)  /* T2: */
 181                         return *rootp;          /* we found it! */
 182
 183                 rootp = (r < 0) ?
 184                     &(*rootp)->llink :          /* T3: follow left branch */
 185                     &(*rootp)->rlink;           /* T4: follow right branch */
 186         }
 187
 188         q = malloc(sizeof(node_t));             /* T5: key not found */
 189         if (q != 0) {                           /* make new node */
 190                 *rootp = q;                     /* link new node to old */
 191                 q->key = (void*)vkey;   /* initialize new node */
 192                 q->llink = q->rlink = NULL;
 193         }
 194         return q;
 195 }
 196
 197
 198 /*      $NetBSD: twalk.c,v 1.2 1999/09/16 11:45:37 lukem Exp $  */
 199
 200 /*
 201  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
 202  * the AT&T man page says.
 203  *
 204  * The node_t structure is for internal use only, lint doesn't grok it.
 205  *
 206  * Written by reading the System V Interface Definition, not the code.
 207  *
 208  * Totally public domain.
 209  */
 210
 211 /* Walk the nodes of a tree */
 212 static void
 213 twalk_recurse(const node_t* root, void (*action)(const void*, VISIT, int), int level)
 214 {
 215         assert(root != NULL);
 216         assert(action != NULL);
 217
 218         if (root->llink == NULL && root->rlink == NULL)
 219                 (*action)(root, leaf, level);
 220         else {
 221                 (*action)(root, preorder, level);
 222                 if (root->llink != NULL)
 223                         twalk_recurse(root->llink, action, level + 1);
 224                 (*action)(root, postorder, level);
 225                 if (root->rlink != NULL)
 226                         twalk_recurse(root->rlink, action, level + 1);
 227                 (*action)(root, endorder, level);
 228         }
 229 }
 230
 231 /* Walk the nodes of a tree */
 232 void
 233 twalk(const void* vroot, void (*action)(const void*, VISIT, int))
 234 {
 235         if (vroot != NULL && action != NULL)
 236                 twalk_recurse(vroot, action, 0);
 237 }
 238
 239 #endif // HAVE_SEARCH_H