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 #define _GNU_SOURCE
  32 #include <search.h>
  33 #include <stdlib.h>
  34
  35 /* This routine is not very bad. It makes many assumptions about
  36  * the compiler. It assumpts that the first field in node must be
  37  * the "key" field, which points to the datum. It is a very trick
  38  * stuff. H.J.
  39  */
  40
  41 typedef struct node_t
  42 {
  43     void        *key;
  44     struct node_t *left, *right;
  45 } node;
  46
  47 #ifdef L_tsearch
  48 /* find or insert datum into search tree.
  49 char    *key;                    key to be located
  50 register node   **rootp;         address of tree root
  51 int     (*compar)();             ordering function
  52 */
  53
  54 void attribute_hidden *__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 strong_alias(__tsearch,tsearch)
  81 #endif
  82
  83 #ifdef L_tfind
  84 void *tfind(__const void *key, void * __const *vrootp, __compar_fn_t compar)
  85 {
  86     register node **rootp = (node **) vrootp;
  87
  88     if (rootp == (struct node_t **)0)
  89         return ((struct node_t *)0);
  90     while (*rootp != (struct node_t *)0)        /* Knuth's T1: */
  91     {
  92         int r;
  93
  94         if ((r = (*compar)(key, (*rootp)->key)) == 0)   /* T2: */
  95             return (*rootp);            /* we found it! */
  96         rootp = (r < 0) ?
  97             &(*rootp)->left :           /* T3: follow left branch */
  98             &(*rootp)->right;           /* T4: follow right branch */
  99     }
 100     return NULL;
 101 }
 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 L_tdestroy
 193 /* The standardized functions miss an important functionality: the
 194    tree cannot be removed easily.  We provide a function to do this.  */
 195 static void
 196 internal_function
 197 tdestroy_recurse (node *root, __free_fn_t freefct)
 198 {
 199     if (root->left != NULL)
 200         tdestroy_recurse (root->left, freefct);
 201     if (root->right != NULL)
 202         tdestroy_recurse (root->right, freefct);
 203     (*freefct) ((void *) root->key);
 204     /* Free the node itself.  */
 205     free (root);
 206 }
 207
 208 void attribute_hidden __tdestroy (void *vroot, __free_fn_t freefct)
 209 {
 210     node *root = (node *) vroot;
 211     if (root != NULL) {
 212         tdestroy_recurse (root, freefct);
 213     }
 214 }
 215 strong_alias(__tdestroy,tdestroy)
 216 #endif
 217
 218 /* tsearch.c ends here */
 219