libc/misc/search/_tsearch.c

   1 /* Copyright (C) 1994 Free Software Foundation, Inc.
   2 This file is part of the GNU C Library.
   3
   4 The GNU C Library is free software; you can redistribute it and/or
   5 modify it under the terms of the GNU Library General Public License as
   6 published by the Free Software Foundation; either version 2 of the
   7 License, or (at your option) any later version.
   8
   9 The GNU C Library is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12 Library General Public License for more details.
  13
  14 You should have received a copy of the GNU Library General Public
  15 License along with the GNU C Library; see the file COPYING.LIB.  If
  16 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
  17 Cambridge, MA 02139, USA.  */
  18
  19 /*
  20  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
  21  * the AT&T man page says.
  22  *
  23  * The node_t structure is for internal use only, lint doesn't grok it.
  24  *
  25  * Written by reading the System V Interface Definition, not the code.
  26  *
  27  * Totally public domain.
  28  */
  29 /*LINTLIBRARY*/
  30
  31 #include <search.h>
  32 #include <stdlib.h>
  33
  34 /* This routine is not very bad. It makes many assumptions about
  35  * the compiler. It assumpts that the first field in node must be
  36  * the "key" field, which points to the datum. It is a very trick
  37  * stuff. H.J.
  38  */
  39
  40 typedef struct node_t
  41 {
  42     void        *key;
  43     struct node_t *left, *right;
  44 } node;
  45
  46 #ifdef L_tsearch
  47 /* find or insert datum into search tree.
  48 char    *key;                    key to be located
  49 register node   **rootp;         address of tree root
  50 int     (*compar)();             ordering function
  51 */
  52
  53 void *tsearch(__const void *key, void **vrootp, __compar_fn_t compar)
  54 {
  55     register node *q;
  56     register node **rootp = (node **) vrootp;
  57
  58     if (rootp == (struct node_t **)0)
  59         return ((struct node_t *)0);
  60     while (*rootp != (struct node_t *)0)        /* Knuth's T1: */
  61     {
  62         int r;
  63
  64         if ((r = (*compar)(key, (*rootp)->key)) == 0)   /* T2: */
  65             return (*rootp);            /* we found it! */
  66         rootp = (r < 0) ?
  67             &(*rootp)->left :           /* T3: follow left branch */
  68             &(*rootp)->right;           /* T4: follow right branch */
  69     }
  70     q = (node *) malloc(sizeof(node));  /* T5: key not found */
  71     if (q != (struct node_t *)0)        /* make new node */
  72     {
  73         *rootp = q;                     /* link new node to old */
  74         q->key = (void *)key;                   /* initialize new node */
  75         q->left = q->right = (struct node_t *)0;
  76     }
  77     return (q);
  78 }
  79 libc_hidden_def(tsearch)
  80 #endif
  81
  82 #ifdef L_tfind
  83 void *tfind(__const void *key, void * __const *vrootp, __compar_fn_t compar)
  84 {
  85     register node **rootp = (node **) vrootp;
  86
  87     if (rootp == (struct node_t **)0)
  88         return ((struct node_t *)0);
  89     while (*rootp != (struct node_t *)0)        /* Knuth's T1: */
  90     {
  91         int r;
  92
  93         if ((r = (*compar)(key, (*rootp)->key)) == 0)   /* T2: */
  94             return (*rootp);            /* we found it! */
  95         rootp = (r < 0) ?
  96             &(*rootp)->left :           /* T3: follow left branch */
  97             &(*rootp)->right;           /* T4: follow right branch */
  98     }
  99     return NULL;
 100 }
 101 libc_hidden_def(tfind)
 102 #endif
 103
 104 #ifdef L_tdelete
 105 /* delete node with given key
 106 char    *key;                   key to be deleted
 107 register node   **rootp;        address of the root of tree
 108 int     (*compar)();            comparison function
 109 */
 110 void *tdelete(__const void *key, void ** vrootp, __compar_fn_t compar)
 111 {
 112     node *p;
 113     register node *q;
 114     register node *r;
 115     int cmp;
 116     register node **rootp = (node **) vrootp;
 117
 118     if (rootp == (struct node_t **)0 || (p = *rootp) == (struct node_t *)0)
 119         return ((struct node_t *)0);
 120     while ((cmp = (*compar)(key, (*rootp)->key)) != 0)
 121     {
 122         p = *rootp;
 123         rootp = (cmp < 0) ?
 124             &(*rootp)->left :           /* follow left branch */
 125             &(*rootp)->right;           /* follow right branch */
 126         if (*rootp == (struct node_t *)0)
 127             return ((struct node_t *)0);        /* key not found */
 128     }
 129     r = (*rootp)->right;                        /* D1: */
 130     if ((q = (*rootp)->left) == (struct node_t *)0)     /* Left (struct node_t *)0? */
 131         q = r;
 132     else if (r != (struct node_t *)0)           /* Right link is null? */
 133     {
 134         if (r->left == (struct node_t *)0)      /* D2: Find successor */
 135         {
 136             r->left = q;
 137             q = r;
 138         }
 139         else
 140         {                       /* D3: Find (struct node_t *)0 link */
 141             for (q = r->left; q->left != (struct node_t *)0; q = r->left)
 142                 r = q;
 143             r->left = q->right;
 144             q->left = (*rootp)->left;
 145             q->right = (*rootp)->right;
 146         }
 147     }
 148     free((struct node_t *) *rootp);     /* D4: Free node */
 149     *rootp = q;                         /* link parent to new node */
 150     return(p);
 151 }
 152 #endif
 153
 154 #ifdef L_twalk
 155 /* Walk the nodes of a tree
 156 register node   *root;          Root of the tree to be walked
 157 register void   (*action)();    Function to be called at each node
 158 register int    level;
 159 */
 160 static void trecurse(__const void *vroot, __action_fn_t action, int level)
 161 {
 162     register node *root = (node *) vroot;
 163
 164     if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0)
 165         (*action)(root, leaf, level);
 166     else
 167     {
 168         (*action)(root, preorder, level);
 169         if (root->left != (struct node_t *)0)
 170             trecurse(root->left, action, level + 1);
 171         (*action)(root, postorder, level);
 172         if (root->right != (struct node_t *)0)
 173             trecurse(root->right, action, level + 1);
 174         (*action)(root, endorder, level);
 175     }
 176 }
 177
 178 /* void twalk(root, action)             Walk the nodes of a tree
 179 node    *root;                  Root of the tree to be walked
 180 void    (*action)();            Function to be called at each node
 181 PTR
 182 */
 183 void twalk(__const void *vroot, __action_fn_t action)
 184 {
 185     register __const node *root = (node *) vroot;
 186
 187     if (root != (node *)0 && action != (__action_fn_t) 0)
 188         trecurse(root, action, 0);
 189 }
 190 #endif
 191
 192 #ifdef __USE_GNU
 193 #ifdef L_tdestroy
 194 /* The standardized functions miss an important functionality: the
 195    tree cannot be removed easily.  We provide a function to do this.  */
 196 static void
 197 internal_function
 198 tdestroy_recurse (node *root, __free_fn_t freefct)
 199 {
 200     if (root->left != NULL)
 201         tdestroy_recurse (root->left, freefct);
 202     if (root->right != NULL)
 203         tdestroy_recurse (root->right, freefct);
 204     (*freefct) ((void *) root->key);
 205     /* Free the node itself.  */
 206     free (root);
 207 }
 208
 209 void tdestroy (void *vroot, __free_fn_t freefct)
 210 {
 211     node *root = (node *) vroot;
 212     if (root != NULL) {
 213         tdestroy_recurse (root, freefct);
 214     }
 215 }
 216 libc_hidden_def(tdestroy)
 217 #endif
 218 #endif
 219
 220 /* tsearch.c ends here */