Mercurial > hg > CbC > CbC_gcc
annotate libiberty/splay-tree.c @ 108:7ad14f446135
add CbC-example/rectypeTest/
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 14 Jun 2012 20:30:24 +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 } |