Mercurial > hg > CbC > CbC_gcc
comparison libiberty/splay-tree.c @ 67:f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
author | nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 22 Mar 2011 17:18:12 +0900 |
parents | a06113de4d67 |
children | 04ced10e8804 |
comparison
equal
deleted
inserted
replaced
65:65488c3d617d | 67:f6334be47118 |
---|---|
1 /* A splay-tree datatype. | 1 /* A splay-tree datatype. |
2 Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. | 2 Copyright (C) 1998, 1999, 2000, 2001, 2009, |
3 2010, 2011 Free Software Foundation, Inc. | |
3 Contributed by Mark Mitchell (mark@markmitchell.com). | 4 Contributed by Mark Mitchell (mark@markmitchell.com). |
4 | 5 |
5 This file is part of GNU CC. | 6 This file is part of GNU CC. |
6 | 7 |
7 GNU CC is free software; you can redistribute it and/or modify it | 8 GNU CC is free software; you can redistribute it and/or modify it |
41 static inline void rotate_left (splay_tree_node *, | 42 static inline void rotate_left (splay_tree_node *, |
42 splay_tree_node, splay_tree_node); | 43 splay_tree_node, splay_tree_node); |
43 static inline void rotate_right (splay_tree_node *, | 44 static inline void rotate_right (splay_tree_node *, |
44 splay_tree_node, splay_tree_node); | 45 splay_tree_node, splay_tree_node); |
45 static void splay_tree_splay (splay_tree, splay_tree_key); | 46 static void splay_tree_splay (splay_tree, splay_tree_key); |
46 static int splay_tree_foreach_helper (splay_tree, splay_tree_node, | 47 static int splay_tree_foreach_helper (splay_tree_node, |
47 splay_tree_foreach_fn, void*); | 48 splay_tree_foreach_fn, void*); |
48 | 49 |
49 /* Deallocate NODE (a member of SP), and all its sub-trees. */ | 50 /* Deallocate NODE (a member of SP), and all its sub-trees. */ |
50 | 51 |
51 static void | 52 static void |
201 which are from SP, following an in-order traversal. If FN every | 202 which are from SP, following an in-order traversal. If FN every |
202 returns a non-zero value, the iteration ceases immediately, and the | 203 returns a non-zero value, the iteration ceases immediately, and the |
203 value is returned. Otherwise, this function returns 0. */ | 204 value is returned. Otherwise, this function returns 0. */ |
204 | 205 |
205 static int | 206 static int |
206 splay_tree_foreach_helper (splay_tree sp, splay_tree_node node, | 207 splay_tree_foreach_helper (splay_tree_node node, |
207 splay_tree_foreach_fn fn, void *data) | 208 splay_tree_foreach_fn fn, void *data) |
208 { | 209 { |
209 int val; | 210 int val; |
210 | 211 splay_tree_node *stack; |
211 if (!node) | 212 int stack_ptr, stack_size; |
212 return 0; | 213 |
213 | 214 /* A non-recursive implementation is used to avoid filling the stack |
214 val = splay_tree_foreach_helper (sp, node->left, fn, data); | 215 for large trees. Splay trees are worst case O(n) in the depth of |
215 if (val) | 216 the tree. */ |
216 return val; | 217 |
217 | 218 #define INITIAL_STACK_SIZE 100 |
218 val = (*fn)(node, data); | 219 stack_size = INITIAL_STACK_SIZE; |
219 if (val) | 220 stack_ptr = 0; |
220 return val; | 221 stack = XNEWVEC (splay_tree_node, stack_size); |
221 | 222 val = 0; |
222 return splay_tree_foreach_helper (sp, node->right, fn, data); | 223 |
223 } | 224 for (;;) |
224 | 225 { |
226 while (node != NULL) | |
227 { | |
228 if (stack_ptr == stack_size) | |
229 { | |
230 stack_size *= 2; | |
231 stack = XRESIZEVEC (splay_tree_node, stack, stack_size); | |
232 } | |
233 stack[stack_ptr++] = node; | |
234 node = node->left; | |
235 } | |
236 | |
237 if (stack_ptr == 0) | |
238 break; | |
239 | |
240 node = stack[--stack_ptr]; | |
241 | |
242 val = (*fn) (node, data); | |
243 if (val) | |
244 break; | |
245 | |
246 node = node->right; | |
247 } | |
248 | |
249 XDELETEVEC (stack); | |
250 return val; | |
251 } | |
225 | 252 |
226 /* An allocator and deallocator based on xmalloc. */ | 253 /* An allocator and deallocator based on xmalloc. */ |
227 static void * | 254 static void * |
228 splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED) | 255 splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED) |
229 { | 256 { |
263 splay_tree_delete_value_fn delete_value_fn, | 290 splay_tree_delete_value_fn delete_value_fn, |
264 splay_tree_allocate_fn allocate_fn, | 291 splay_tree_allocate_fn allocate_fn, |
265 splay_tree_deallocate_fn deallocate_fn, | 292 splay_tree_deallocate_fn deallocate_fn, |
266 void *allocate_data) | 293 void *allocate_data) |
267 { | 294 { |
268 splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s), | 295 return |
269 allocate_data); | 296 splay_tree_new_typed_alloc (compare_fn, delete_key_fn, delete_value_fn, |
297 allocate_fn, allocate_fn, deallocate_fn, | |
298 allocate_data); | |
299 } | |
300 | |
301 /* | |
302 | |
303 @deftypefn Supplemental splay_tree splay_tree_new_with_typed_alloc @ | |
304 (splay_tree_compare_fn @var{compare_fn}, @ | |
305 splay_tree_delete_key_fn @var{delete_key_fn}, @ | |
306 splay_tree_delete_value_fn @var{delete_value_fn}, @ | |
307 splay_tree_allocate_fn @var{tree_allocate_fn}, @ | |
308 splay_tree_allocate_fn @var{node_allocate_fn}, @ | |
309 splay_tree_deallocate_fn @var{deallocate_fn}, @ | |
310 void * @var{allocate_data}) | |
311 | |
312 This function creates a splay tree that uses two different allocators | |
313 @var{tree_allocate_fn} and @var{node_allocate_fn} to use for allocating the | |
314 tree itself and its nodes respectively. This is useful when variables of | |
315 different types need to be allocated with different allocators. | |
316 | |
317 The splay tree will use @var{compare_fn} to compare nodes, | |
318 @var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to | |
319 deallocate values. | |
320 | |
321 @end deftypefn | |
322 | |
323 */ | |
324 | |
325 splay_tree | |
326 splay_tree_new_typed_alloc (splay_tree_compare_fn compare_fn, | |
327 splay_tree_delete_key_fn delete_key_fn, | |
328 splay_tree_delete_value_fn delete_value_fn, | |
329 splay_tree_allocate_fn tree_allocate_fn, | |
330 splay_tree_allocate_fn node_allocate_fn, | |
331 splay_tree_deallocate_fn deallocate_fn, | |
332 void * allocate_data) | |
333 { | |
334 splay_tree sp = (splay_tree) (*tree_allocate_fn) | |
335 (sizeof (struct splay_tree_s), allocate_data); | |
336 | |
270 sp->root = 0; | 337 sp->root = 0; |
271 sp->comp = compare_fn; | 338 sp->comp = compare_fn; |
272 sp->delete_key = delete_key_fn; | 339 sp->delete_key = delete_key_fn; |
273 sp->delete_value = delete_value_fn; | 340 sp->delete_value = delete_value_fn; |
274 sp->allocate = allocate_fn; | 341 sp->allocate = node_allocate_fn; |
275 sp->deallocate = deallocate_fn; | 342 sp->deallocate = deallocate_fn; |
276 sp->allocate_data = allocate_data; | 343 sp->allocate_data = allocate_data; |
277 | 344 |
278 return sp; | 345 return sp; |
279 } | 346 } |
311 } | 378 } |
312 else | 379 else |
313 { | 380 { |
314 /* Create a new node, and insert it at the root. */ | 381 /* Create a new node, and insert it at the root. */ |
315 splay_tree_node node; | 382 splay_tree_node node; |
316 | 383 |
317 node = ((splay_tree_node) | 384 node = ((splay_tree_node) |
318 (*sp->allocate) (sizeof (struct splay_tree_node_s), | 385 (*sp->allocate) (sizeof (struct splay_tree_node_s), |
319 sp->allocate_data)); | 386 sp->allocate_data)); |
320 node->key = key; | 387 node->key = key; |
321 node->value = value; | 388 node->value = value; |
322 | 389 |
323 if (!sp->root) | 390 if (!sp->root) |
324 node->left = node->right = 0; | 391 node->left = node->right = 0; |
494 Otherwise, this function returns 0. */ | 561 Otherwise, this function returns 0. */ |
495 | 562 |
496 int | 563 int |
497 splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data) | 564 splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data) |
498 { | 565 { |
499 return splay_tree_foreach_helper (sp, sp->root, fn, data); | 566 return splay_tree_foreach_helper (sp->root, fn, data); |
500 } | 567 } |
501 | 568 |
502 /* Splay-tree comparison function, treating the keys as ints. */ | 569 /* Splay-tree comparison function, treating the keys as ints. */ |
503 | 570 |
504 int | 571 int |