misc/tsearch.c

   1 /* Copyright (C) 1995, 1996 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., 59 Temple Place - Suite 330,
  17 Boston, MA 02111-1307, USA.  */
  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 /*LINTLIBRARY*/
  28
  29 #include <stdlib.h>
  30 #include <search.h>
  31
  32 /* This routine is not very bad.  It makes many assumptions about
  33    the compiler. It assumpts that the first field in node must be
  34    the "key" field, which points to the datum. It is a very trick
  35    stuff. H.J.  */
  36
  37 typedef struct node_t
  38 {
  39   const void *key;
  40   struct node_t *left;
  41   struct node_t *right;
  42 }
  43 node;
  44
  45 /* Prototype fpr local function.  */
  46 static void trecurse __P ((const void *vroot, __action_fn_t action, int level));
  47
  48
  49 /* find or insert datum into search tree.
  50 char    *key;            key to be located
  51 node    **rootp;         address of tree root
  52 int     (*compar)();     ordering function
  53 */
  54 void *
  55 __tsearch (key, vrootp, compar)
  56      const void *key;
  57      void **vrootp;
  58      __compar_fn_t compar;
  59 {
  60   node *q;
  61   node **rootp = (node **) vrootp;
  62
  63   if (rootp == NULL)
  64     return NULL;
  65
  66   while (*rootp != NULL)                /* Knuth's T1: */
  67     {
  68       int r;
  69
  70       r = (*compar) (key, (*rootp)->key);
  71       if (r == 0)                       /* T2: */
  72         return *rootp;                  /* we found it! */
  73       rootp = (r < 0)
  74               ? &(*rootp)->left         /* T3: follow left branch */
  75               : &(*rootp)->right;       /* T4: follow right branch */
  76     }
  77
  78   q = (node *) malloc (sizeof (node));  /* T5: key not found */
  79   if (q != NULL)                        /* make new node */
  80     {
  81       *rootp = q;                       /* link new node to old */
  82       q->key = key;                     /* initialize new node */
  83       q->left = q->right = NULL;
  84     }
  85
  86   return q;
  87 }
  88 weak_alias (__tsearch, tsearch)
  89
  90
  91 void *
  92 __tfind (key, vrootp, compar)
  93      const void *key;
  94      const void **vrootp;
  95      __compar_fn_t compar;
  96 {
  97   node **rootp = (node **) vrootp;
  98
  99   if (rootp == NULL)
 100     return NULL;
 101
 102   while (*rootp != NULL)                /* Knuth's T1: */
 103     {
 104       int r;
 105
 106       r = (*compar)(key, (*rootp)->key);
 107       if (r == 0)                       /* T2: */
 108         return *rootp;                  /* we found it! */
 109
 110       rootp = (r < 0)
 111               ? &(*rootp)->left         /* T3: follow left branch */
 112               : &(*rootp)->right;       /* T4: follow right branch */
 113     }
 114     return NULL;
 115 }
 116 weak_alias (__tfind, tfind)
 117
 118
 119 /* delete node with given key
 120 char    *key;           key to be deleted
 121 node    **rootp;        address of the root of tree
 122 int     (*compar)();    comparison function
 123 */
 124 void *
 125 __tdelete (key, vrootp, compar)
 126      const void *key;
 127      void **vrootp;
 128      __compar_fn_t compar;
 129 {
 130   node *p;
 131   node *q;
 132   node *r;
 133   int cmp;
 134   node **rootp = (node **) vrootp;
 135
 136   if (rootp == NULL || (p = *rootp) == NULL)
 137     return NULL;
 138
 139   while ((cmp = (*compar) (key, (*rootp)->key)) != 0)
 140     {
 141       p = *rootp;
 142       rootp = (cmp < 0)
 143               ? &(*rootp)->left         /* follow left branch */
 144               : &(*rootp)->right;       /* follow right branch */
 145       if (*rootp == NULL)
 146         return NULL;                    /* key not found */
 147     }
 148
 149   r = (*rootp)->right;                  /* D1: */
 150   q = (*rootp)->left;
 151   if (q == NULL)                        /* Left NULL? */
 152     q = r;
 153   else if (r != NULL)                   /* Right link is NULL? */
 154     {
 155       if (r->left == NULL)              /* D2: Find successor */
 156         {
 157           r->left = q;
 158           q = r;
 159         }
 160       else
 161         {                               /* D3: Find (struct node_t *)0 link */
 162           for (q = r->left; q->left != NULL; q = r->left)
 163             r = q;
 164           r->left = q->right;
 165           q->left = (*rootp)->left;
 166           q->right = (*rootp)->right;
 167         }
 168     }
 169   free ((struct node_t *) *rootp);      /* D4: Free node */
 170   *rootp = q;                           /* link parent to new node */
 171   return p;
 172 }
 173 weak_alias (__tdelete, tdelete)
 174
 175
 176 /* Walk the nodes of a tree
 177 node    *root;          Root of the tree to be walked
 178 void    (*action)();    Function to be called at each node
 179 int     level;
 180 */
 181 static void
 182 trecurse (vroot, action, level)
 183      const void *vroot;
 184      __action_fn_t action;
 185      int level;
 186 {
 187   node *root = (node *) vroot;
 188
 189   if (root->left == NULL && root->right == NULL)
 190     (*action) (root, leaf, level);
 191   else
 192     {
 193       (*action) (root, preorder, level);
 194       if (root->left != NULL)
 195         trecurse (root->left, action, level + 1);
 196       (*action) (root, postorder, level);
 197       if (root->right != NULL)
 198         trecurse (root->right, action, level + 1);
 199       (*action) (root, endorder, level);
 200     }
 201 }
 202
 203
 204 /* void twalk(root, action)     Walk the nodes of a tree
 205 node    *root;                  Root of the tree to be walked
 206 void    (*action)();            Function to be called at each node
 207 PTR
 208 */
 209 void
 210 __twalk (vroot, action)
 211      const void *vroot;
 212      __action_fn_t action;
 213 {
 214   const node *root = (node *) vroot;
 215
 216   if (root != NULL && action != NULL)
 217     trecurse (root, action, 0);
 218 }
 219 weak_alias (__twalk, twalk)