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 libc_hidden_proto(tsearch)
  54 void *tsearch(__const void *key, void **vrootp, __compar_fn_t compar)
  55 {
  56     register node *q;
  57     register node **rootp = (node **) vrootp;
  58
  59     if (rootp == (struct node_t **)0)
  60         return ((struct node_t *)0);
  61     while (*rootp != (struct node_t *)0)        /* Knuth's T1: */
  62     {
  63         int r;
  64
  65         if ((r = (*compar)(key, (*rootp)->key)) == 0)   /* T2: */
  66             return (*rootp);            /* we found it! */
  67         rootp = (r < 0) ?
  68             &(*rootp)->left :           /* T3: follow left branch */
  69             &(*rootp)->right;           /* T4: follow right branch */
  70     }
  71     q = (node *) malloc(sizeof(node));  /* T5: key not found */
  72     if (q != (struct node_t *)0)        /* make new node */
  73     {
  74         *rootp = q;                     /* link new node to old */
  75         q->key = (void *)key;                   /* initialize new node */
  76         q->left = q->right = (struct node_t *)0;
  77     }
  78     return (q);
  79 }
  80 libc_hidden_def(tsearch)
  81 #endif
  82
  83 #ifdef L_tfind
  84 libc_hidden_proto(tfind)
  85 void *tfind(__const void *key, void * __const *vrootp, __compar_fn_t compar)
  86 {
  87     register node **rootp = (node **) vrootp;
  88
  89     if (rootp == (struct node_t **)0)
  90         return ((struct node_t *)0);
  91     while (*rootp != (struct node_t *)0)        /* Knuth's T1: */
  92     {
  93         int r;
  94
  95         if ((r = (*compar)(key, (*rootp)->key)) == 0)   /* T2: */
  96             return (*rootp);            /* we found it! */
  97         rootp = (r < 0) ?
  98             &(*rootp)->left :           /* T3: follow left branch */
  99             &(*rootp)->right;           /* T4: follow right branch */
 100     }
 101     return NULL;
 102 }
 103 libc_hidden_def(tfind)
 104 #endif
 105
 106 #ifdef L_tdelete
 107 /* delete node with given key
 108 char    *key;                   key to be deleted
 109 register node   **rootp;        address of the root of tree
 110 int     (*compar)();            comparison function
 111 */
 112 void *tdelete(__const void *key, void ** vrootp, __compar_fn_t compar)
 113 {
 114     node *p;
 115     register node *q;
 116     register node *r;
 117     int cmp;
 118     register node **rootp = (node **) vrootp;
 119
 120     if (rootp == (struct node_t **)0 || (p = *rootp) == (struct node_t *)0)
 121         return ((struct node_t *)0);
 122     while ((cmp = (*compar)(key, (*rootp)->key)) != 0)
 123     {
 124         p = *rootp;
 125         rootp = (cmp < 0) ?
 126             &(*rootp)->left :           /* follow left branch */
 127             &(*rootp)->right;           /* follow right branch */
 128         if (*rootp == (struct node_t *)0)
 129             return ((struct node_t *)0);        /* key not found */
 130     }
 131     r = (*rootp)->right;                        /* D1: */
 132     if ((q = (*rootp)->left) == (struct node_t *)0)     /* Left (struct node_t *)0? */
 133         q = r;
 134     else if (r != (struct node_t *)0)           /* Right link is null? */
 135     {
 136         if (r->left == (struct node_t *)0)      /* D2: Find successor */
 137         {
 138             r->left = q;
 139             q = r;
 140         }
 141         else
 142         {                       /* D3: Find (struct node_t *)0 link */
 143             for (q = r->left; q->left != (struct node_t *)0; q = r->left)
 144                 r = q;
 145             r->left = q->right;
 146             q->left = (*rootp)->left;
 147             q->right = (*rootp)->right;
 148         }
 149     }
 150     free((struct node_t *) *rootp);     /* D4: Free node */
 151     *rootp = q;                         /* link parent to new node */
 152     return(p);
 153 }
 154 #endif
 155
 156 #ifdef L_twalk
 157 /* Walk the nodes of a tree
 158 register node   *root;          Root of the tree to be walked
 159 register void   (*action)();    Function to be called at each node
 160 register int    level;
 161 */
 162 static void trecurse(__const void *vroot, __action_fn_t action, int level)
 163 {
 164     register node *root = (node *) vroot;
 165
 166     if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0)
 167         (*action)(root, leaf, level);
 168     else
 169     {
 170         (*action)(root, preorder, level);
 171         if (root->left != (struct node_t *)0)
 172             trecurse(root->left, action, level + 1);
 173         (*action)(root, postorder, level);
 174         if (root->right != (struct node_t *)0)
 175             trecurse(root->right, action, level + 1);
 176         (*action)(root, endorder, level);
 177     }
 178 }
 179
 180 /* void twalk(root, action)             Walk the nodes of a tree
 181 node    *root;                  Root of the tree to be walked
 182 void    (*action)();            Function to be called at each node
 183 PTR
 184 */
 185 void twalk(__const void *vroot, __action_fn_t action)
 186 {
 187     register __const node *root = (node *) vroot;
 188
 189     if (root != (node *)0 && action != (__action_fn_t) 0)
 190         trecurse(root, action, 0);
 191 }
 192 #endif
 193
 194 #ifdef __USE_GNU
 195 #ifdef L_tdestroy
 196 /* The standardized functions miss an important functionality: the
 197    tree cannot be removed easily.  We provide a function to do this.  */
 198 static void
 199 internal_function
 200 tdestroy_recurse (node *root, __free_fn_t freefct)
 201 {
 202     if (root->left != NULL)
 203         tdestroy_recurse (root->left, freefct);
 204     if (root->right != NULL)
 205         tdestroy_recurse (root->right, freefct);
 206     (*freefct) ((void *) root->key);
 207     /* Free the node itself.  */
 208     free (root);
 209 }
 210
 211 libc_hidden_proto(tdestroy)
 212 void tdestroy (void *vroot, __free_fn_t freefct)
 213 {
 214     node *root = (node *) vroot;
 215     if (root != NULL) {
 216         tdestroy_recurse (root, freefct);
 217     }
 218 }
 219 libc_hidden_def(tdestroy)
 220 #endif
 221 #endif
 222
 223 /* tsearch.c ends here */