Mercurial > hg > CbC > CbC_gcc
annotate libiberty/splay-tree.c @ 76:6381ea127240
call argument iterator fix
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 20 Sep 2011 16:58:47 +0900 |
parents | f6334be47118 |
children | 04ced10e8804 |
rev | line source |
---|---|
0 | 1 /* A splay-tree datatype. |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2 Copyright (C) 1998, 1999, 2000, 2001, 2009, |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
3 2010, 2011 Free Software Foundation, Inc. |
0 | 4 Contributed by Mark Mitchell (mark@markmitchell.com). |
5 | |
6 This file is part of GNU CC. | |
7 | |
8 GNU CC is free software; you can redistribute it and/or modify it | |
9 under the terms of the GNU General Public License as published by | |
10 the Free Software Foundation; either version 2, or (at your option) | |
11 any later version. | |
12 | |
13 GNU CC is distributed in the hope that it will be useful, but | |
14 WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
16 General Public License for more details. | |
17 | |
18 You should have received a copy of the GNU General Public License | |
19 along with GNU CC; see the file COPYING. If not, write to | |
20 the Free Software Foundation, 51 Franklin Street - Fifth Floor, | |
21 Boston, MA 02110-1301, USA. */ | |
22 | |
23 /* For an easily readable description of splay-trees, see: | |
24 | |
25 Lewis, Harry R. and Denenberg, Larry. Data Structures and Their | |
26 Algorithms. Harper-Collins, Inc. 1991. */ | |
27 | |
28 #ifdef HAVE_CONFIG_H | |
29 #include "config.h" | |
30 #endif | |
31 | |
32 #ifdef HAVE_STDLIB_H | |
33 #include <stdlib.h> | |
34 #endif | |
35 | |
36 #include <stdio.h> | |
37 | |
38 #include "libiberty.h" | |
39 #include "splay-tree.h" | |
40 | |
41 static void splay_tree_delete_helper (splay_tree, splay_tree_node); | |
42 static inline void rotate_left (splay_tree_node *, | |
43 splay_tree_node, splay_tree_node); | |
44 static inline void rotate_right (splay_tree_node *, | |
45 splay_tree_node, splay_tree_node); | |
46 static void splay_tree_splay (splay_tree, splay_tree_key); | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
47 static int splay_tree_foreach_helper (splay_tree_node, |
0 | 48 splay_tree_foreach_fn, void*); |
49 | |
50 /* Deallocate NODE (a member of SP), and all its sub-trees. */ | |
51 | |
52 static void | |
53 splay_tree_delete_helper (splay_tree sp, splay_tree_node node) | |
54 { | |
55 splay_tree_node pending = 0; | |
56 splay_tree_node active = 0; | |
57 | |
58 if (!node) | |
59 return; | |
60 | |
61 #define KDEL(x) if (sp->delete_key) (*sp->delete_key)(x); | |
62 #define VDEL(x) if (sp->delete_value) (*sp->delete_value)(x); | |
63 | |
64 KDEL (node->key); | |
65 VDEL (node->value); | |
66 | |
67 /* We use the "key" field to hold the "next" pointer. */ | |
68 node->key = (splay_tree_key)pending; | |
69 pending = (splay_tree_node)node; | |
70 | |
71 /* Now, keep processing the pending list until there aren't any | |
72 more. This is a little more complicated than just recursing, but | |
73 it doesn't toast the stack for large trees. */ | |
74 | |
75 while (pending) | |
76 { | |
77 active = pending; | |
78 pending = 0; | |
79 while (active) | |
80 { | |
81 splay_tree_node temp; | |
82 | |
83 /* active points to a node which has its key and value | |
84 deallocated, we just need to process left and right. */ | |
85 | |
86 if (active->left) | |
87 { | |
88 KDEL (active->left->key); | |
89 VDEL (active->left->value); | |
90 active->left->key = (splay_tree_key)pending; | |
91 pending = (splay_tree_node)(active->left); | |
92 } | |
93 if (active->right) | |
94 { | |
95 KDEL (active->right->key); | |
96 VDEL (active->right->value); | |
97 active->right->key = (splay_tree_key)pending; | |
98 pending = (splay_tree_node)(active->right); | |
99 } | |
100 | |
101 temp = active; | |
102 active = (splay_tree_node)(temp->key); | |
103 (*sp->deallocate) ((char*) temp, sp->allocate_data); | |
104 } | |
105 } | |
106 #undef KDEL | |
107 #undef VDEL | |
108 } | |
109 | |
110 /* Rotate the edge joining the left child N with its parent P. PP is the | |
111 grandparents' pointer to P. */ | |
112 | |
113 static inline void | |
114 rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) | |
115 { | |
116 splay_tree_node tmp; | |
117 tmp = n->right; | |
118 n->right = p; | |
119 p->left = tmp; | |
120 *pp = n; | |
121 } | |
122 | |
123 /* Rotate the edge joining the right child N with its parent P. PP is the | |
124 grandparents' pointer to P. */ | |
125 | |
126 static inline void | |
127 rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) | |
128 { | |
129 splay_tree_node tmp; | |
130 tmp = n->left; | |
131 n->left = p; | |
132 p->right = tmp; | |
133 *pp = n; | |
134 } | |
135 | |
136 /* Bottom up splay of key. */ | |
137 | |
138 static void | |
139 splay_tree_splay (splay_tree sp, splay_tree_key key) | |
140 { | |
141 if (sp->root == 0) | |
142 return; | |
143 | |
144 do { | |
145 int cmp1, cmp2; | |
146 splay_tree_node n, c; | |
147 | |
148 n = sp->root; | |
149 cmp1 = (*sp->comp) (key, n->key); | |
150 | |
151 /* Found. */ | |
152 if (cmp1 == 0) | |
153 return; | |
154 | |
155 /* Left or right? If no child, then we're done. */ | |
156 if (cmp1 < 0) | |
157 c = n->left; | |
158 else | |
159 c = n->right; | |
160 if (!c) | |
161 return; | |
162 | |
163 /* Next one left or right? If found or no child, we're done | |
164 after one rotation. */ | |
165 cmp2 = (*sp->comp) (key, c->key); | |
166 if (cmp2 == 0 | |
167 || (cmp2 < 0 && !c->left) | |
168 || (cmp2 > 0 && !c->right)) | |
169 { | |
170 if (cmp1 < 0) | |
171 rotate_left (&sp->root, n, c); | |
172 else | |
173 rotate_right (&sp->root, n, c); | |
174 return; | |
175 } | |
176 | |
177 /* Now we have the four cases of double-rotation. */ | |
178 if (cmp1 < 0 && cmp2 < 0) | |
179 { | |
180 rotate_left (&n->left, c, c->left); | |
181 rotate_left (&sp->root, n, n->left); | |
182 } | |
183 else if (cmp1 > 0 && cmp2 > 0) | |
184 { | |
185 rotate_right (&n->right, c, c->right); | |
186 rotate_right (&sp->root, n, n->right); | |
187 } | |
188 else if (cmp1 < 0 && cmp2 > 0) | |
189 { | |
190 rotate_right (&n->left, c, c->right); | |
191 rotate_left (&sp->root, n, n->left); | |
192 } | |
193 else if (cmp1 > 0 && cmp2 < 0) | |
194 { | |
195 rotate_left (&n->right, c, c->left); | |
196 rotate_right (&sp->root, n, n->right); | |
197 } | |
198 } while (1); | |
199 } | |
200 | |
201 /* Call FN, passing it the DATA, for every node below NODE, all of | |
202 which are from SP, following an in-order traversal. If FN every | |
203 returns a non-zero value, the iteration ceases immediately, and the | |
204 value is returned. Otherwise, this function returns 0. */ | |
205 | |
206 static int | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
207 splay_tree_foreach_helper (splay_tree_node node, |
0 | 208 splay_tree_foreach_fn fn, void *data) |
209 { | |
210 int val; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
211 splay_tree_node *stack; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
212 int stack_ptr, stack_size; |
0 | 213 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
214 /* A non-recursive implementation is used to avoid filling the stack |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
215 for large trees. Splay trees are worst case O(n) in the depth of |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
216 the tree. */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
217 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
218 #define INITIAL_STACK_SIZE 100 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
219 stack_size = INITIAL_STACK_SIZE; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
220 stack_ptr = 0; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
221 stack = XNEWVEC (splay_tree_node, stack_size); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
222 val = 0; |
0 | 223 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
224 for (;;) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
225 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
226 while (node != NULL) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
227 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
228 if (stack_ptr == stack_size) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
229 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
230 stack_size *= 2; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
231 stack = XRESIZEVEC (splay_tree_node, stack, stack_size); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
232 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
233 stack[stack_ptr++] = node; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
234 node = node->left; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
235 } |
0 | 236 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
237 if (stack_ptr == 0) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
238 break; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
239 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
240 node = stack[--stack_ptr]; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
241 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
242 val = (*fn) (node, data); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
243 if (val) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
244 break; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
245 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
246 node = node->right; |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
247 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
248 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
249 XDELETEVEC (stack); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
250 return val; |
0 | 251 } |
252 | |
253 /* An allocator and deallocator based on xmalloc. */ | |
254 static void * | |
255 splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED) | |
256 { | |
257 return (void *) xmalloc (size); | |
258 } | |
259 | |
260 static void | |
261 splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED) | |
262 { | |
263 free (object); | |
264 } | |
265 | |
266 | |
267 /* Allocate a new splay tree, using COMPARE_FN to compare nodes, | |
268 DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate | |
269 values. Use xmalloc to allocate the splay tree structure, and any | |
270 nodes added. */ | |
271 | |
272 splay_tree | |
273 splay_tree_new (splay_tree_compare_fn compare_fn, | |
274 splay_tree_delete_key_fn delete_key_fn, | |
275 splay_tree_delete_value_fn delete_value_fn) | |
276 { | |
277 return (splay_tree_new_with_allocator | |
278 (compare_fn, delete_key_fn, delete_value_fn, | |
279 splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0)); | |
280 } | |
281 | |
282 | |
283 /* Allocate a new splay tree, using COMPARE_FN to compare nodes, | |
284 DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate | |
285 values. */ | |
286 | |
287 splay_tree | |
288 splay_tree_new_with_allocator (splay_tree_compare_fn compare_fn, | |
289 splay_tree_delete_key_fn delete_key_fn, | |
290 splay_tree_delete_value_fn delete_value_fn, | |
291 splay_tree_allocate_fn allocate_fn, | |
292 splay_tree_deallocate_fn deallocate_fn, | |
293 void *allocate_data) | |
294 { | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
295 return |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
296 splay_tree_new_typed_alloc (compare_fn, delete_key_fn, delete_value_fn, |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
297 allocate_fn, allocate_fn, deallocate_fn, |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
298 allocate_data); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
299 } |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
300 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
301 /* |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
302 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
303 @deftypefn Supplemental splay_tree splay_tree_new_with_typed_alloc @ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
304 (splay_tree_compare_fn @var{compare_fn}, @ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
305 splay_tree_delete_key_fn @var{delete_key_fn}, @ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
306 splay_tree_delete_value_fn @var{delete_value_fn}, @ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
307 splay_tree_allocate_fn @var{tree_allocate_fn}, @ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
308 splay_tree_allocate_fn @var{node_allocate_fn}, @ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
309 splay_tree_deallocate_fn @var{deallocate_fn}, @ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
310 void * @var{allocate_data}) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
311 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
312 This function creates a splay tree that uses two different allocators |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
313 @var{tree_allocate_fn} and @var{node_allocate_fn} to use for allocating the |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
314 tree itself and its nodes respectively. This is useful when variables of |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
315 different types need to be allocated with different allocators. |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
316 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
317 The splay tree will use @var{compare_fn} to compare nodes, |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
318 @var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
319 deallocate values. |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
320 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
321 @end deftypefn |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
322 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
323 */ |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
324 |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
325 splay_tree |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
326 splay_tree_new_typed_alloc (splay_tree_compare_fn compare_fn, |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
327 splay_tree_delete_key_fn delete_key_fn, |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
328 splay_tree_delete_value_fn delete_value_fn, |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
329 splay_tree_allocate_fn tree_allocate_fn, |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
330 splay_tree_allocate_fn node_allocate_fn, |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
331 splay_tree_deallocate_fn deallocate_fn, |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
332 void * allocate_data) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
333 { |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
334 splay_tree sp = (splay_tree) (*tree_allocate_fn) |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
335 (sizeof (struct splay_tree_s), allocate_data); |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
336 |
0 | 337 sp->root = 0; |
338 sp->comp = compare_fn; | |
339 sp->delete_key = delete_key_fn; | |
340 sp->delete_value = delete_value_fn; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
341 sp->allocate = node_allocate_fn; |
0 | 342 sp->deallocate = deallocate_fn; |
343 sp->allocate_data = allocate_data; | |
344 | |
345 return sp; | |
346 } | |
347 | |
348 /* Deallocate SP. */ | |
349 | |
350 void | |
351 splay_tree_delete (splay_tree sp) | |
352 { | |
353 splay_tree_delete_helper (sp, sp->root); | |
354 (*sp->deallocate) ((char*) sp, sp->allocate_data); | |
355 } | |
356 | |
357 /* Insert a new node (associating KEY with DATA) into SP. If a | |
358 previous node with the indicated KEY exists, its data is replaced | |
359 with the new value. Returns the new node. */ | |
360 | |
361 splay_tree_node | |
362 splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value) | |
363 { | |
364 int comparison = 0; | |
365 | |
366 splay_tree_splay (sp, key); | |
367 | |
368 if (sp->root) | |
369 comparison = (*sp->comp)(sp->root->key, key); | |
370 | |
371 if (sp->root && comparison == 0) | |
372 { | |
373 /* If the root of the tree already has the indicated KEY, just | |
374 replace the value with VALUE. */ | |
375 if (sp->delete_value) | |
376 (*sp->delete_value)(sp->root->value); | |
377 sp->root->value = value; | |
378 } | |
379 else | |
380 { | |
381 /* Create a new node, and insert it at the root. */ | |
382 splay_tree_node node; | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
383 |
0 | 384 node = ((splay_tree_node) |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
385 (*sp->allocate) (sizeof (struct splay_tree_node_s), |
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
386 sp->allocate_data)); |
0 | 387 node->key = key; |
388 node->value = value; | |
389 | |
390 if (!sp->root) | |
391 node->left = node->right = 0; | |
392 else if (comparison < 0) | |
393 { | |
394 node->left = sp->root; | |
395 node->right = node->left->right; | |
396 node->left->right = 0; | |
397 } | |
398 else | |
399 { | |
400 node->right = sp->root; | |
401 node->left = node->right->left; | |
402 node->right->left = 0; | |
403 } | |
404 | |
405 sp->root = node; | |
406 } | |
407 | |
408 return sp->root; | |
409 } | |
410 | |
411 /* Remove KEY from SP. It is not an error if it did not exist. */ | |
412 | |
413 void | |
414 splay_tree_remove (splay_tree sp, splay_tree_key key) | |
415 { | |
416 splay_tree_splay (sp, key); | |
417 | |
418 if (sp->root && (*sp->comp) (sp->root->key, key) == 0) | |
419 { | |
420 splay_tree_node left, right; | |
421 | |
422 left = sp->root->left; | |
423 right = sp->root->right; | |
424 | |
425 /* Delete the root node itself. */ | |
426 if (sp->delete_value) | |
427 (*sp->delete_value) (sp->root->value); | |
428 (*sp->deallocate) (sp->root, sp->allocate_data); | |
429 | |
430 /* One of the children is now the root. Doesn't matter much | |
431 which, so long as we preserve the properties of the tree. */ | |
432 if (left) | |
433 { | |
434 sp->root = left; | |
435 | |
436 /* If there was a right child as well, hang it off the | |
437 right-most leaf of the left child. */ | |
438 if (right) | |
439 { | |
440 while (left->right) | |
441 left = left->right; | |
442 left->right = right; | |
443 } | |
444 } | |
445 else | |
446 sp->root = right; | |
447 } | |
448 } | |
449 | |
450 /* Lookup KEY in SP, returning VALUE if present, and NULL | |
451 otherwise. */ | |
452 | |
453 splay_tree_node | |
454 splay_tree_lookup (splay_tree sp, splay_tree_key key) | |
455 { | |
456 splay_tree_splay (sp, key); | |
457 | |
458 if (sp->root && (*sp->comp)(sp->root->key, key) == 0) | |
459 return sp->root; | |
460 else | |
461 return 0; | |
462 } | |
463 | |
464 /* Return the node in SP with the greatest key. */ | |
465 | |
466 splay_tree_node | |
467 splay_tree_max (splay_tree sp) | |
468 { | |
469 splay_tree_node n = sp->root; | |
470 | |
471 if (!n) | |
472 return NULL; | |
473 | |
474 while (n->right) | |
475 n = n->right; | |
476 | |
477 return n; | |
478 } | |
479 | |
480 /* Return the node in SP with the smallest key. */ | |
481 | |
482 splay_tree_node | |
483 splay_tree_min (splay_tree sp) | |
484 { | |
485 splay_tree_node n = sp->root; | |
486 | |
487 if (!n) | |
488 return NULL; | |
489 | |
490 while (n->left) | |
491 n = n->left; | |
492 | |
493 return n; | |
494 } | |
495 | |
496 /* Return the immediate predecessor KEY, or NULL if there is no | |
497 predecessor. KEY need not be present in the tree. */ | |
498 | |
499 splay_tree_node | |
500 splay_tree_predecessor (splay_tree sp, splay_tree_key key) | |
501 { | |
502 int comparison; | |
503 splay_tree_node node; | |
504 | |
505 /* If the tree is empty, there is certainly no predecessor. */ | |
506 if (!sp->root) | |
507 return NULL; | |
508 | |
509 /* Splay the tree around KEY. That will leave either the KEY | |
510 itself, its predecessor, or its successor at the root. */ | |
511 splay_tree_splay (sp, key); | |
512 comparison = (*sp->comp)(sp->root->key, key); | |
513 | |
514 /* If the predecessor is at the root, just return it. */ | |
515 if (comparison < 0) | |
516 return sp->root; | |
517 | |
518 /* Otherwise, find the rightmost element of the left subtree. */ | |
519 node = sp->root->left; | |
520 if (node) | |
521 while (node->right) | |
522 node = node->right; | |
523 | |
524 return node; | |
525 } | |
526 | |
527 /* Return the immediate successor KEY, or NULL if there is no | |
528 successor. KEY need not be present in the tree. */ | |
529 | |
530 splay_tree_node | |
531 splay_tree_successor (splay_tree sp, splay_tree_key key) | |
532 { | |
533 int comparison; | |
534 splay_tree_node node; | |
535 | |
536 /* If the tree is empty, there is certainly no successor. */ | |
537 if (!sp->root) | |
538 return NULL; | |
539 | |
540 /* Splay the tree around KEY. That will leave either the KEY | |
541 itself, its predecessor, or its successor at the root. */ | |
542 splay_tree_splay (sp, key); | |
543 comparison = (*sp->comp)(sp->root->key, key); | |
544 | |
545 /* If the successor is at the root, just return it. */ | |
546 if (comparison > 0) | |
547 return sp->root; | |
548 | |
549 /* Otherwise, find the leftmost element of the right subtree. */ | |
550 node = sp->root->right; | |
551 if (node) | |
552 while (node->left) | |
553 node = node->left; | |
554 | |
555 return node; | |
556 } | |
557 | |
558 /* Call FN, passing it the DATA, for every node in SP, following an | |
559 in-order traversal. If FN every returns a non-zero value, the | |
560 iteration ceases immediately, and the value is returned. | |
561 Otherwise, this function returns 0. */ | |
562 | |
563 int | |
564 splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data) | |
565 { | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
566 return splay_tree_foreach_helper (sp->root, fn, data); |
0 | 567 } |
568 | |
569 /* Splay-tree comparison function, treating the keys as ints. */ | |
570 | |
571 int | |
572 splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2) | |
573 { | |
574 if ((int) k1 < (int) k2) | |
575 return -1; | |
576 else if ((int) k1 > (int) k2) | |
577 return 1; | |
578 else | |
579 return 0; | |
580 } | |
581 | |
582 /* Splay-tree comparison function, treating the keys as pointers. */ | |
583 | |
584 int | |
585 splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2) | |
586 { | |
587 if ((char*) k1 < (char*) k2) | |
588 return -1; | |
589 else if ((char*) k1 > (char*) k2) | |
590 return 1; | |
591 else | |
592 return 0; | |
593 } |