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