]> gcc.gnu.org Git - gcc.git/blob - libiberty/splay-tree.c
choose-temp.c: Always include libiberty.h.
[gcc.git] / libiberty / splay-tree.c
1 /* A splay-tree datatype.
2 Copyright (C) 1998 Free Software Foundation, Inc.
3 Contributed by Mark Mitchell (mark@markmitchell.com).
4
5 This file is part of GNU CC.
6
7 GNU CC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GNU CC is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to the Free
19 Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
20
21 For an easily readable description of splay-trees, see:
22
23 Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
24 Algorithms. Harper-Collins, Inc. 1991. */
25
26 #if defined (IN_GCC) || defined (HAVE_CONFIG_H)
27 #include "config.h"
28 #endif
29
30 #ifdef HAVE_STDLIB_H
31 #include <stdlib.h>
32 #endif
33
34 #include "libiberty.h"
35 #include "splay-tree.h"
36
37 static void splay_tree_delete_helper PARAMS((splay_tree,
38 splay_tree_node));
39 static void splay_tree_splay PARAMS((splay_tree,
40 splay_tree_key));
41 static splay_tree_node splay_tree_splay_helper
42 PARAMS((splay_tree,
43 splay_tree_key,
44 splay_tree_node*,
45 splay_tree_node*,
46 splay_tree_node*));
47 static int splay_tree_foreach_helper PARAMS((splay_tree,
48 splay_tree_node,
49 splay_tree_foreach_fn,
50 void*));
51
52 /* Deallocate NODE (a member of SP), and all its sub-trees. */
53
54 static void
55 splay_tree_delete_helper (sp, node)
56 splay_tree sp;
57 splay_tree_node node;
58 {
59 if (!node)
60 return;
61
62 splay_tree_delete_helper (sp, node->left);
63 splay_tree_delete_helper (sp, node->right);
64
65 if (sp->delete_key)
66 (*sp->delete_key)(node->key);
67 if (sp->delete_value)
68 (*sp->delete_value)(node->value);
69
70 free ((char*) node);
71 }
72
73 /* Help splay SP around KEY. PARENT and GRANDPARENT are the parent
74 and grandparent, respectively, of NODE. */
75
76 static splay_tree_node
77 splay_tree_splay_helper (sp, key, node, parent, grandparent)
78 splay_tree sp;
79 splay_tree_key key;
80 splay_tree_node *node;
81 splay_tree_node *parent;
82 splay_tree_node *grandparent;
83 {
84 splay_tree_node *next;
85 splay_tree_node n;
86 int comparison;
87
88 n = *node;
89
90 if (!n)
91 return *parent;
92
93 comparison = (*sp->comp) (key, n->key);
94
95 if (comparison == 0)
96 /* We've found the target. */
97 next = 0;
98 else if (comparison < 0)
99 /* The target is to the left. */
100 next = &n->left;
101 else
102 /* The target is to the right. */
103 next = &n->right;
104
105 if (next)
106 {
107 /* Continue down the tree. */
108 n = splay_tree_splay_helper (sp, key, next, node, parent);
109
110 /* The recursive call will change the place to which NODE
111 points. */
112 if (*node != n)
113 return n;
114 }
115
116 if (!parent)
117 /* NODE is the root. We are done. */
118 return n;
119
120 /* First, handle the case where there is no grandparent (i.e.,
121 *PARENT is the root of the tree.) */
122 if (!grandparent)
123 {
124 if (n == (*parent)->left)
125 {
126 *node = n->right;
127 n->right = *parent;
128 }
129 else
130 {
131 *node = n->left;
132 n->left = *parent;
133 }
134 *parent = n;
135 return n;
136 }
137
138 /* Next handle the cases where both N and *PARENT are left children,
139 or where both are right children. */
140 if (n == (*parent)->left && *parent == (*grandparent)->left)
141 {
142 splay_tree_node p = *parent;
143
144 (*grandparent)->left = p->right;
145 p->right = *grandparent;
146 p->left = n->right;
147 n->right = p;
148 *grandparent = n;
149 return n;
150 }
151 else if (n == (*parent)->right && *parent == (*grandparent)->right)
152 {
153 splay_tree_node p = *parent;
154
155 (*grandparent)->right = p->left;
156 p->left = *grandparent;
157 p->right = n->left;
158 n->left = p;
159 *grandparent = n;
160 return n;
161 }
162
163 /* Finally, deal with the case where N is a left child, but *PARENT
164 is a right child, or vice versa. */
165 if (n == (*parent)->left)
166 {
167 (*parent)->left = n->right;
168 n->right = *parent;
169 (*grandparent)->right = n->left;
170 n->left = *grandparent;
171 *grandparent = n;
172 return n;
173 }
174 else
175 {
176 (*parent)->right = n->left;
177 n->left = *parent;
178 (*grandparent)->left = n->right;
179 n->right = *grandparent;
180 *grandparent = n;
181 return n;
182 }
183 }
184
185 /* Splay SP around KEY. */
186
187 static void
188 splay_tree_splay (sp, key)
189 splay_tree sp;
190 splay_tree_key key;
191 {
192 if (sp->root == 0)
193 return;
194
195 splay_tree_splay_helper (sp, key, &sp->root,
196 /*grandparent=*/0, /*parent=*/0);
197 }
198
199 /* Call FN, passing it the DATA, for every node below NODE, all of
200 which are from SP, following an in-order traversal. If FN every
201 returns a non-zero value, the iteration ceases immediately, and the
202 value is returned. Otherwise, this function returns 0. */
203
204 static int
205 splay_tree_foreach_helper (sp, node, fn, data)
206 splay_tree sp;
207 splay_tree_node node;
208 splay_tree_foreach_fn fn;
209 void* data;
210 {
211 int val;
212
213 if (!node)
214 return 0;
215
216 val = splay_tree_foreach_helper (sp, node->left, fn, data);
217 if (val)
218 return val;
219
220 val = (*fn)(node, data);
221 if (val)
222 return val;
223
224 return splay_tree_foreach_helper (sp, node->right, fn, data);
225 }
226
227 /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
228 DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
229 values. */
230
231 splay_tree
232 splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
233 splay_tree_compare_fn compare_fn;
234 splay_tree_delete_key_fn delete_key_fn;
235 splay_tree_delete_value_fn delete_value_fn;
236 {
237 splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree));
238 sp->root = 0;
239 sp->comp = compare_fn;
240 sp->delete_key = delete_key_fn;
241 sp->delete_value = delete_value_fn;
242
243 return sp;
244 }
245
246 /* Deallocate SP. */
247
248 void
249 splay_tree_delete (sp)
250 splay_tree sp;
251 {
252 splay_tree_delete_helper (sp, sp->root);
253 free ((char*) sp);
254 }
255
256 /* Insert a new node (associating KEY with DATA) into SP. If a
257 previous node with the indicated KEY exists, its data is replaced
258 with the new value. */
259
260 void
261 splay_tree_insert (sp, key, value)
262 splay_tree sp;
263 splay_tree_key key;
264 splay_tree_value value;
265 {
266 int comparison;
267
268 splay_tree_splay (sp, key);
269
270 if (sp->root)
271 comparison = (*sp->comp)(sp->root->key, key);
272
273 if (sp->root && comparison == 0)
274 {
275 /* If the root of the tree already has the indicated KEY, just
276 replace the value with VALUE. */
277 if (sp->delete_value)
278 (*sp->delete_value)(sp->root->value);
279 sp->root->value = value;
280 }
281 else
282 {
283 /* Create a new node, and insert it at the root. */
284 splay_tree_node node;
285
286 node = (splay_tree_node) xmalloc (sizeof (struct splay_tree_node));
287 node->key = key;
288 node->value = value;
289
290 if (!sp->root)
291 node->left = node->right = 0;
292 else if (comparison < 0)
293 {
294 node->left = sp->root;
295 node->right = node->left->right;
296 node->left->right = 0;
297 }
298 else
299 {
300 node->right = sp->root;
301 node->left = node->right->left;
302 node->right->left = 0;
303 }
304
305 sp->root = node;
306 }
307 }
308
309 /* Lookup KEY in SP, returning VALUE if present, and NULL
310 otherwise. */
311
312 splay_tree_node
313 splay_tree_lookup (sp, key)
314 splay_tree sp;
315 splay_tree_key key;
316 {
317 splay_tree_splay (sp, key);
318
319 if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
320 return sp->root;
321 else
322 return 0;
323 }
324
325 /* Call FN, passing it the DATA, for every node in SP, following an
326 in-order traversal. If FN every returns a non-zero value, the
327 iteration ceases immediately, and the value is returned.
328 Otherwise, this function returns 0. */
329
330 int
331 splay_tree_foreach (sp, fn, data)
332 splay_tree sp;
333 splay_tree_foreach_fn fn;
334 void *data;
335 {
336 return splay_tree_foreach_helper (sp, sp->root, fn, data);
337 }
This page took 0.054714 seconds and 6 git commands to generate.