]>
Commit | Line | Data |
---|---|---|
1be6ec30 | 1 | /* Copyright (C) 1995, 1996 Free Software Foundation, Inc. |
60478656 RM |
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. | |
1be6ec30 | 21 | |
60478656 | 22 | The node_t structure is for internal use only, lint doesn't grok it. |
1be6ec30 | 23 | |
60478656 | 24 | Written by reading the System V Interface Definition, not the code. |
1be6ec30 | 25 | |
60478656 RM |
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 * | |
1be6ec30 | 55 | __tsearch (key, vrootp, compar) |
60478656 RM |
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 | } | |
1be6ec30 | 88 | weak_alias (__tsearch, tsearch) |
60478656 RM |
89 | |
90 | ||
91 | void * | |
1be6ec30 | 92 | __tfind (key, vrootp, compar) |
60478656 RM |
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 | } | |
1be6ec30 | 116 | weak_alias (__tfind, tfind) |
60478656 RM |
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 * | |
1be6ec30 | 125 | __tdelete (key, vrootp, compar) |
60478656 RM |
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 | } | |
4f54cdb1 | 173 | weak_alias (__tdelete, tdelete) |
60478656 RM |
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 | ||
1be6ec30 | 204 | /* void twalk(root, action) Walk the nodes of a tree |
60478656 RM |
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 | |
1be6ec30 | 210 | __twalk (vroot, action) |
60478656 RM |
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 | } | |
1be6ec30 | 219 | weak_alias (__twalk, twalk) |