l4/pkg/l4re-core/uclibc/lib/contrib/uclibc/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, see <http://www.gnu.org/licenses/>.  */
  17
  18 /*
  19  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
  20  * the AT&T man page says.
  21  *
  22  * The node_t structure is for internal use only, lint doesn't grok it.
  23  *
  24  * Written by reading the System V Interface Definition, not the code.
  25  *
  26  * Totally public domain.
  27  */
  28 /*LINTLIBRARY*/
  29
  30 #include <search.h>
  31 #include <stdlib.h>
  32
  33 /* This routine is not very bad. It makes many assumptions about
  34  * the compiler. It assumpts that the first field in node must be
  35  * the "key" field, which points to the datum. It is a very trick
  36  * stuff. H.J.
  37  */
  38
  39 typedef struct node_t
  40 {
  41     void        *key;
  42     struct node_t *left, *right;
  43 } node;
  44
  45 #ifdef L_tsearch
  46 /* find or insert datum into search tree.
  47 char    *key;                    key to be located
  48 register node   **rootp;         address of tree root
  49 int     (*compar)();             ordering function
  50 */
  51
  52 void *tsearch(const void *key, void **vrootp, __compar_fn_t compar)
  53 {
  54     register node *q;
  55     register node **rootp = (node **) vrootp;
  56
  57     if (rootp == (struct node_t **)0)
  58         return ((struct node_t *)0);
  59     while (*rootp != (struct node_t *)0)        /* Knuth's T1: */
  60     {
  61         int r;
  62
  63         if ((r = (*compar)(key, (*rootp)->key)) == 0)   /* T2: */
  64             return (*rootp);            /* we found it! */
  65         rootp = (r < 0) ?
  66             &(*rootp)->left :           /* T3: follow left branch */
  67             &(*rootp)->right;           /* T4: follow right branch */
  68     }
  69     q = (node *) malloc(sizeof(node));  /* T5: key not found */
  70     if (q != (struct node_t *)0)        /* make new node */
  71     {
  72         *rootp = q;                     /* link new node to old */
  73         q->key = (void *)key;                   /* initialize new node */
  74         q->left = q->right = (struct node_t *)0;
  75     }
  76     return (q);
  77 }
  78 libc_hidden_def(tsearch)
  79 #endif
  80
  81 #ifdef L_tfind
  82 void *tfind(const void *key, void * const *vrootp, __compar_fn_t compar)
  83 {
  84     register node **rootp = (node **) vrootp;
  85
  86     if (rootp == (struct node_t **)0)
  87         return ((struct node_t *)0);
  88     while (*rootp != (struct node_t *)0)        /* Knuth's T1: */
  89     {
  90         int r;
  91
  92         if ((r = (*compar)(key, (*rootp)->key)) == 0)   /* T2: */
  93             return (*rootp);            /* we found it! */
  94         rootp = (r < 0) ?
  95             &(*rootp)->left :           /* T3: follow left branch */
  96             &(*rootp)->right;           /* T4: follow right branch */
  97     }
  98     return NULL;
  99 }
 100 libc_hidden_def(tfind)
 101 #endif
 102
 103 #ifdef L_tdelete
 104 /* delete node with given key
 105 char    *key;                   key to be deleted
 106 register node   **rootp;        address of the root of tree
 107 int     (*compar)();            comparison function
 108 */
 109 void *tdelete(const void *key, void ** vrootp, __compar_fn_t compar)
 110 {
 111     node *p;
 112     register node *q;
 113     register node *r;
 114     int cmp;
 115     register node **rootp = (node **) vrootp;
 116
 117     if (rootp == (struct node_t **)0 || (p = *rootp) == (struct node_t *)0)
 118         return ((struct node_t *)0);
 119     while ((cmp = (*compar)(key, (*rootp)->key)) != 0)
 120     {
 121         p = *rootp;
 122         rootp = (cmp < 0) ?
 123             &(*rootp)->left :           /* follow left branch */
 124             &(*rootp)->right;           /* follow right branch */
 125         if (*rootp == (struct node_t *)0)
 126             return ((struct node_t *)0);        /* key not found */
 127     }
 128     r = (*rootp)->right;                        /* D1: */
 129     if ((q = (*rootp)->left) == (struct node_t *)0)     /* Left (struct node_t *)0? */
 130         q = r;
 131     else if (r != (struct node_t *)0)           /* Right link is null? */
 132     {
 133         if (r->left == (struct node_t *)0)      /* D2: Find successor */
 134         {
 135             r->left = q;
 136             q = r;
 137         }
 138         else
 139         {                       /* D3: Find (struct node_t *)0 link */
 140             for (q = r->left; q->left != (struct node_t *)0; q = r->left)
 141                 r = q;
 142             r->left = q->right;
 143             q->left = (*rootp)->left;
 144             q->right = (*rootp)->right;
 145         }
 146     }
 147     free((struct node_t *) *rootp);     /* D4: Free node */
 148     *rootp = q;                         /* link parent to new node */
 149     return(p);
 150 }
 151 #endif
 152
 153 #ifdef L_twalk
 154 /* Walk the nodes of a tree
 155 register node   *root;          Root of the tree to be walked
 156 register void   (*action)();    Function to be called at each node
 157 register int    level;
 158 */
 159 static void trecurse(const void *vroot, __action_fn_t action, int level)
 160 {
 161     register node *root = (node *) vroot;
 162
 163     if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0)
 164         (*action)(root, leaf, level);
 165     else
 166     {
 167         (*action)(root, preorder, level);
 168         if (root->left != (struct node_t *)0)
 169             trecurse(root->left, action, level + 1);
 170         (*action)(root, postorder, level);
 171         if (root->right != (struct node_t *)0)
 172             trecurse(root->right, action, level + 1);
 173         (*action)(root, endorder, level);
 174     }
 175 }
 176
 177 /* void twalk(root, action)             Walk the nodes of a tree
 178 node    *root;                  Root of the tree to be walked
 179 void    (*action)();            Function to be called at each node
 180 PTR
 181 */
 182 void twalk(const void *vroot, __action_fn_t action)
 183 {
 184     register const node *root = (node *) vroot;
 185
 186     if (root != (node *)0 && action != (__action_fn_t) 0)
 187         trecurse(root, action, 0);
 188 }
 189 #endif
 190
 191 #ifdef __USE_GNU
 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 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 libc_hidden_def(tdestroy)
 216 #endif
 217 #endif
 218
 219 /* tsearch.c ends here */