home *** CD-ROM | disk | FTP | other *** search
/ Serving the Web / ServingTheWeb1995.disc1of1.iso / linux / slacksrce / d / libc / libc-4.6 / libc-4 / libc-linux / misc / tsearch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-26  |  5.6 KB  |  198 lines
  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 <ansidecl.h>
  32. #include <search.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. /* 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. PTR
  52. DEFUN(tsearch, (key, vrootp, compar),
  53.     register CONST PTR key AND PTR *vrootp AND
  54.     register int EXFUN((*compar), (CONST PTR, CONST PTR)))
  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 = key;            /* initialize new node */
  76.     q->left = q->right = (struct node_t *)0;
  77.     }
  78.     return (q);
  79. }
  80.  
  81. PTR
  82. DEFUN(tfind, (key, vrootp, compar),
  83.     register CONST PTR key AND CONST PTR *vrootp AND
  84.     register int EXFUN((*compar), (CONST PTR, CONST PTR)))
  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.  
  103. /* delete node with given key
  104. char    *key;            key to be deleted
  105. register node    **rootp;    address of the root of tree
  106. int    (*compar)();        comparison function
  107. */
  108. PTR
  109. DEFUN(tdelete, (key, vrootp, compar),
  110.     register CONST PTR key AND PTR *vrootp AND
  111.     register int EXFUN((*compar), (CONST PTR, CONST PTR)))
  112. {
  113.     node *p;
  114.     register node *q;
  115.     register node *r;
  116.     int cmp;
  117.     register node **rootp = (node **) vrootp;
  118.  
  119.     if (rootp == (struct node_t **)0 || (p = *rootp) == (struct node_t *)0)
  120.     return ((struct node_t *)0);
  121.     while ((cmp = (*compar)(key, (*rootp)->key)) != 0)
  122.     {
  123.     p = *rootp;
  124.     rootp = (cmp < 0) ?
  125.         &(*rootp)->left :        /* follow left branch */
  126.         &(*rootp)->right;        /* follow right branch */
  127.     if (*rootp == (struct node_t *)0)
  128.         return ((struct node_t *)0);    /* key not found */
  129.     }
  130.     r = (*rootp)->right;            /* D1: */
  131.     if ((q = (*rootp)->left) == (struct node_t *)0)    /* Left (struct node_t *)0? */
  132.     q = r;
  133.     else if (r != (struct node_t *)0)        /* Right link is null? */
  134.     {
  135.     if (r->left == (struct node_t *)0)    /* D2: Find successor */
  136.     {
  137.         r->left = q;
  138.         q = r;
  139.     }
  140.     else
  141.     {            /* D3: Find (struct node_t *)0 link */
  142.         for (q = r->left; q->left != (struct node_t *)0; q = r->left)
  143.         r = q;
  144.         r->left = q->right;
  145.         q->left = (*rootp)->left;
  146.         q->right = (*rootp)->right;
  147.     }
  148.     }
  149.     free((struct node_t *) *rootp);    /* D4: Free node */
  150.     *rootp = q;                /* link parent to new node */
  151.     return(p);
  152. }
  153.  
  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
  160. DEFUN(trecurse, (vroot, action, level),
  161.     register CONST PTR vroot AND
  162.     register void EXFUN((*action), (CONST PTR, VISIT, int)) AND
  163.     register int level)
  164. {
  165.     register node *root = (node *) vroot;
  166.  
  167.     if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0)
  168.     (*action)(root, leaf, level);
  169.     else
  170.     {
  171.     (*action)(root, preorder, level);
  172.     if (root->left != (struct node_t *)0)
  173.         trecurse(root->left, action, level + 1);
  174.     (*action)(root, postorder, level);
  175.     if (root->right != (struct node_t *)0)
  176.         trecurse(root->right, action, level + 1);
  177.     (*action)(root, endorder, level);
  178.     }
  179. }
  180.  
  181. /* void twalk(root, action)        Walk the nodes of a tree 
  182. node    *root;            Root of the tree to be walked
  183. void    (*action)();        Function to be called at each node
  184. PTR
  185. */
  186. void
  187. DEFUN(twalk, (vroot, action),
  188.     register CONST PTR vroot AND
  189.     register void EXFUN((*action), (CONST PTR, VISIT, int)))
  190. {
  191.     register CONST node *root = (node *) vroot;
  192.  
  193.     if (root != (node *)0 && action != (__action_fn_t) 0)
  194.     trecurse(root, action, 0);
  195. }
  196.  
  197. /* tsearch.c ends here */
  198.