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