(tests): Add tst-tsearch.
[kopensolaris-gnu/glibc.git] / 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 not,
16    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 assumes that the first field in the node must be
34    the "key" field, which points to the datum. It is very tricky
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)