]>
Commit | Line | Data |
---|---|---|
60478656 RM |
1 | /* Copyright (C) 1995 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 | ||
89 | ||
90 | void * | |
91 | tfind (key, vrootp, compar) | |
92 | const void *key; | |
93 | const void **vrootp; | |
94 | __compar_fn_t compar; | |
95 | { | |
96 | node **rootp = (node **) vrootp; | |
97 | ||
98 | if (rootp == NULL) | |
99 | return NULL; | |
100 | ||
101 | while (*rootp != NULL) /* Knuth's T1: */ | |
102 | { | |
103 | int r; | |
104 | ||
105 | r = (*compar)(key, (*rootp)->key); | |
106 | if (r == 0) /* T2: */ | |
107 | return *rootp; /* we found it! */ | |
108 | ||
109 | rootp = (r < 0) | |
110 | ? &(*rootp)->left /* T3: follow left branch */ | |
111 | : &(*rootp)->right; /* T4: follow right branch */ | |
112 | } | |
113 | return NULL; | |
114 | } | |
115 | ||
116 | ||
117 | /* delete node with given key | |
118 | char *key; key to be deleted | |
119 | node **rootp; address of the root of tree | |
120 | int (*compar)(); comparison function | |
121 | */ | |
122 | void * | |
123 | tdelete (key, vrootp, compar) | |
124 | const void *key; | |
125 | void **vrootp; | |
126 | __compar_fn_t compar; | |
127 | { | |
128 | node *p; | |
129 | node *q; | |
130 | node *r; | |
131 | int cmp; | |
132 | node **rootp = (node **) vrootp; | |
133 | ||
134 | if (rootp == NULL || (p = *rootp) == NULL) | |
135 | return NULL; | |
136 | ||
137 | while ((cmp = (*compar) (key, (*rootp)->key)) != 0) | |
138 | { | |
139 | p = *rootp; | |
140 | rootp = (cmp < 0) | |
141 | ? &(*rootp)->left /* follow left branch */ | |
142 | : &(*rootp)->right; /* follow right branch */ | |
143 | if (*rootp == NULL) | |
144 | return NULL; /* key not found */ | |
145 | } | |
146 | ||
147 | r = (*rootp)->right; /* D1: */ | |
148 | q = (*rootp)->left; | |
149 | if (q == NULL) /* Left NULL? */ | |
150 | q = r; | |
151 | else if (r != NULL) /* Right link is NULL? */ | |
152 | { | |
153 | if (r->left == NULL) /* D2: Find successor */ | |
154 | { | |
155 | r->left = q; | |
156 | q = r; | |
157 | } | |
158 | else | |
159 | { /* D3: Find (struct node_t *)0 link */ | |
160 | for (q = r->left; q->left != NULL; q = r->left) | |
161 | r = q; | |
162 | r->left = q->right; | |
163 | q->left = (*rootp)->left; | |
164 | q->right = (*rootp)->right; | |
165 | } | |
166 | } | |
167 | free ((struct node_t *) *rootp); /* D4: Free node */ | |
168 | *rootp = q; /* link parent to new node */ | |
169 | return p; | |
170 | } | |
171 | ||
172 | ||
173 | /* Walk the nodes of a tree | |
174 | node *root; Root of the tree to be walked | |
175 | void (*action)(); Function to be called at each node | |
176 | int level; | |
177 | */ | |
178 | static void | |
179 | trecurse (vroot, action, level) | |
180 | const void *vroot; | |
181 | __action_fn_t action; | |
182 | int level; | |
183 | { | |
184 | node *root = (node *) vroot; | |
185 | ||
186 | if (root->left == NULL && root->right == NULL) | |
187 | (*action) (root, leaf, level); | |
188 | else | |
189 | { | |
190 | (*action) (root, preorder, level); | |
191 | if (root->left != NULL) | |
192 | trecurse (root->left, action, level + 1); | |
193 | (*action) (root, postorder, level); | |
194 | if (root->right != NULL) | |
195 | trecurse (root->right, action, level + 1); | |
196 | (*action) (root, endorder, level); | |
197 | } | |
198 | } | |
199 | ||
200 | ||
201 | /* void twalk(root, action) Walk the nodes of a tree | |
202 | node *root; Root of the tree to be walked | |
203 | void (*action)(); Function to be called at each node | |
204 | PTR | |
205 | */ | |
206 | void | |
207 | twalk (vroot, action) | |
208 | const void *vroot; | |
209 | __action_fn_t action; | |
210 | { | |
211 | const node *root = (node *) vroot; | |
212 | ||
213 | if (root != NULL && action != NULL) | |
214 | trecurse (root, action, 0); | |
215 | } |