GRASS Programmer's Manual
6.4.2(2012)
|
00001 /* Produced by texiweb from libavl.w on 2002/02/09 at 01:45. */ 00002 00003 /* libavl - library for manipulation of binary trees. 00004 Copyright (C) 1998-2002 Free Software Foundation, Inc. 00005 00006 This program is free software; you can redistribute it and/or 00007 modify it under the terms of the GNU General Public License as 00008 published by the Free Software Foundation; either version 2 of the 00009 License, or (at your option) any later version. 00010 00011 This program is distributed in the hope that it will be useful, but 00012 WITHOUT ANY WARRANTY; without even the implied warranty of 00013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00014 See the GNU General Public License for more details. 00015 00016 You should have received a copy of the GNU General Public License 00017 along with this program; if not, write to the Free Software 00018 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 00019 00020 The author may be contacted at <blp@gnu.org> on the Internet, or 00021 as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA through more 00022 mundane means. 00023 */ 00024 00025 #include <assert.h> 00026 #include <stdio.h> 00027 #include <stdlib.h> 00028 #include <string.h> 00029 #include "avl.h" 00030 00031 /* Creates and returns a new table 00032 with comparison function |compare| using parameter |param| 00033 and memory allocator |allocator|. 00034 Returns |NULL| if memory allocation failed. */ 00035 struct avl_table *avl_create(avl_comparison_func * compare, void *param, 00036 struct libavl_allocator *allocator) 00037 { 00038 struct avl_table *tree; 00039 00040 assert(compare != NULL); 00041 00042 if (allocator == NULL) 00043 allocator = &avl_allocator_default; 00044 00045 tree = allocator->libavl_malloc(allocator, sizeof *tree); 00046 if (tree == NULL) 00047 return NULL; 00048 00049 tree->avl_root = NULL; 00050 tree->avl_compare = compare; 00051 tree->avl_param = param; 00052 tree->avl_alloc = allocator; 00053 tree->avl_count = 0; 00054 tree->avl_generation = 0; 00055 00056 return tree; 00057 } 00058 00059 /* Search |tree| for an item matching |item|, and return it if found. 00060 Otherwise return |NULL|. */ 00061 void *avl_find(const struct avl_table *tree, const void *item) 00062 { 00063 const struct avl_node *p; 00064 00065 assert(tree != NULL && item != NULL); 00066 for (p = tree->avl_root; p != NULL;) { 00067 int cmp = tree->avl_compare(item, p->avl_data, tree->avl_param); 00068 00069 if (cmp < 0) 00070 p = p->avl_link[0]; 00071 else if (cmp > 0) 00072 p = p->avl_link[1]; 00073 else /* |cmp == 0| */ 00074 return p->avl_data; 00075 } 00076 00077 return NULL; 00078 } 00079 00080 /* Inserts |item| into |tree| and returns a pointer to |item|'s address. 00081 If a duplicate item is found in the tree, 00082 returns a pointer to the duplicate without inserting |item|. 00083 Returns |NULL| in case of memory allocation failure. */ 00084 void **avl_probe(struct avl_table *tree, void *item) 00085 { 00086 struct avl_node *y, *z; /* Top node to update balance factor, and parent. */ 00087 struct avl_node *p, *q; /* Iterator, and parent. */ 00088 struct avl_node *n; /* Newly inserted node. */ 00089 struct avl_node *w; /* New root of rebalanced subtree. */ 00090 int dir; /* Direction to descend. */ 00091 00092 unsigned char da[AVL_MAX_HEIGHT]; /* Cached comparison results. */ 00093 int k = 0; /* Number of cached results. */ 00094 00095 assert(tree != NULL && item != NULL); 00096 00097 z = (struct avl_node *)&tree->avl_root; 00098 y = tree->avl_root; 00099 dir = 0; 00100 for (q = z, p = y; p != NULL; q = p, p = p->avl_link[dir]) { 00101 int cmp = tree->avl_compare(item, p->avl_data, tree->avl_param); 00102 00103 if (cmp == 0) 00104 return &p->avl_data; 00105 00106 if (p->avl_balance != 0) 00107 z = q, y = p, k = 0; 00108 da[k++] = dir = cmp > 0; 00109 } 00110 00111 n = q->avl_link[dir] = 00112 tree->avl_alloc->libavl_malloc(tree->avl_alloc, sizeof *n); 00113 if (n == NULL) 00114 return NULL; 00115 00116 tree->avl_count++; 00117 n->avl_data = item; 00118 n->avl_link[0] = n->avl_link[1] = NULL; 00119 n->avl_balance = 0; 00120 if (y == NULL) 00121 return &n->avl_data; 00122 00123 for (p = y, k = 0; p != n; p = p->avl_link[da[k]], k++) 00124 if (da[k] == 0) 00125 p->avl_balance--; 00126 else 00127 p->avl_balance++; 00128 00129 if (y->avl_balance == -2) { 00130 struct avl_node *x = y->avl_link[0]; 00131 00132 if (x->avl_balance == -1) { 00133 w = x; 00134 y->avl_link[0] = x->avl_link[1]; 00135 x->avl_link[1] = y; 00136 x->avl_balance = y->avl_balance = 0; 00137 } 00138 else { 00139 assert(x->avl_balance == +1); 00140 w = x->avl_link[1]; 00141 x->avl_link[1] = w->avl_link[0]; 00142 w->avl_link[0] = x; 00143 y->avl_link[0] = w->avl_link[1]; 00144 w->avl_link[1] = y; 00145 if (w->avl_balance == -1) 00146 x->avl_balance = 0, y->avl_balance = +1; 00147 else if (w->avl_balance == 0) 00148 x->avl_balance = y->avl_balance = 0; 00149 else /* |w->avl_balance == +1| */ 00150 x->avl_balance = -1, y->avl_balance = 0; 00151 w->avl_balance = 0; 00152 } 00153 } 00154 else if (y->avl_balance == +2) { 00155 struct avl_node *x = y->avl_link[1]; 00156 00157 if (x->avl_balance == +1) { 00158 w = x; 00159 y->avl_link[1] = x->avl_link[0]; 00160 x->avl_link[0] = y; 00161 x->avl_balance = y->avl_balance = 0; 00162 } 00163 else { 00164 assert(x->avl_balance == -1); 00165 w = x->avl_link[0]; 00166 x->avl_link[0] = w->avl_link[1]; 00167 w->avl_link[1] = x; 00168 y->avl_link[1] = w->avl_link[0]; 00169 w->avl_link[0] = y; 00170 if (w->avl_balance == +1) 00171 x->avl_balance = 0, y->avl_balance = -1; 00172 else if (w->avl_balance == 0) 00173 x->avl_balance = y->avl_balance = 0; 00174 else /* |w->avl_balance == -1| */ 00175 x->avl_balance = +1, y->avl_balance = 0; 00176 w->avl_balance = 0; 00177 } 00178 } 00179 else 00180 return &n->avl_data; 00181 z->avl_link[y != z->avl_link[0]] = w; 00182 00183 tree->avl_generation++; 00184 return &n->avl_data; 00185 } 00186 00187 /* Inserts |item| into |table|. 00188 Returns |NULL| if |item| was successfully inserted 00189 or if a memory allocation error occurred. 00190 Otherwise, returns the duplicate item. */ 00191 void *avl_insert(struct avl_table *table, void *item) 00192 { 00193 void **p = avl_probe(table, item); 00194 00195 return p == NULL || *p == item ? NULL : *p; 00196 } 00197 00198 /* Inserts |item| into |table|, replacing any duplicate item. 00199 Returns |NULL| if |item| was inserted without replacing a duplicate, 00200 or if a memory allocation error occurred. 00201 Otherwise, returns the item that was replaced. */ 00202 void *avl_replace(struct avl_table *table, void *item) 00203 { 00204 void **p = avl_probe(table, item); 00205 00206 if (p == NULL || *p == item) 00207 return NULL; 00208 else { 00209 void *r = *p; 00210 00211 *p = item; 00212 return r; 00213 } 00214 } 00215 00216 /* Deletes from |tree| and returns an item matching |item|. 00217 Returns a null pointer if no matching item found. */ 00218 void *avl_delete(struct avl_table *tree, const void *item) 00219 { 00220 /* Stack of nodes. */ 00221 struct avl_node *pa[AVL_MAX_HEIGHT]; /* Nodes. */ 00222 unsigned char da[AVL_MAX_HEIGHT]; /* |avl_link[]| indexes. */ 00223 int k; /* Stack pointer. */ 00224 00225 struct avl_node *p; /* Traverses tree to find node to delete. */ 00226 int cmp; /* Result of comparison between |item| and |p|. */ 00227 00228 assert(tree != NULL && item != NULL); 00229 00230 k = 0; 00231 p = (struct avl_node *)&tree->avl_root; 00232 for (cmp = -1; cmp != 0; 00233 cmp = tree->avl_compare(item, p->avl_data, tree->avl_param)) { 00234 int dir = cmp > 0; 00235 00236 pa[k] = p; 00237 da[k++] = dir; 00238 00239 p = p->avl_link[dir]; 00240 if (p == NULL) 00241 return NULL; 00242 } 00243 item = p->avl_data; 00244 00245 if (p->avl_link[1] == NULL) 00246 pa[k - 1]->avl_link[da[k - 1]] = p->avl_link[0]; 00247 else { 00248 struct avl_node *r = p->avl_link[1]; 00249 00250 if (r->avl_link[0] == NULL) { 00251 r->avl_link[0] = p->avl_link[0]; 00252 r->avl_balance = p->avl_balance; 00253 pa[k - 1]->avl_link[da[k - 1]] = r; 00254 da[k] = 1; 00255 pa[k++] = r; 00256 } 00257 else { 00258 struct avl_node *s; 00259 int j = k++; 00260 00261 for (;;) { 00262 da[k] = 0; 00263 pa[k++] = r; 00264 s = r->avl_link[0]; 00265 if (s->avl_link[0] == NULL) 00266 break; 00267 00268 r = s; 00269 } 00270 00271 s->avl_link[0] = p->avl_link[0]; 00272 r->avl_link[0] = s->avl_link[1]; 00273 s->avl_link[1] = p->avl_link[1]; 00274 s->avl_balance = p->avl_balance; 00275 00276 pa[j - 1]->avl_link[da[j - 1]] = s; 00277 da[j] = 1; 00278 pa[j] = s; 00279 } 00280 } 00281 00282 tree->avl_alloc->libavl_free(tree->avl_alloc, p); 00283 00284 assert(k > 0); 00285 while (--k > 0) { 00286 struct avl_node *y = pa[k]; 00287 00288 if (da[k] == 0) { 00289 y->avl_balance++; 00290 if (y->avl_balance == +1) 00291 break; 00292 else if (y->avl_balance == +2) { 00293 struct avl_node *x = y->avl_link[1]; 00294 00295 if (x->avl_balance == -1) { 00296 struct avl_node *w; 00297 00298 assert(x->avl_balance == -1); 00299 w = x->avl_link[0]; 00300 x->avl_link[0] = w->avl_link[1]; 00301 w->avl_link[1] = x; 00302 y->avl_link[1] = w->avl_link[0]; 00303 w->avl_link[0] = y; 00304 if (w->avl_balance == +1) 00305 x->avl_balance = 0, y->avl_balance = -1; 00306 else if (w->avl_balance == 0) 00307 x->avl_balance = y->avl_balance = 0; 00308 else /* |w->avl_balance == -1| */ 00309 x->avl_balance = +1, y->avl_balance = 0; 00310 w->avl_balance = 0; 00311 pa[k - 1]->avl_link[da[k - 1]] = w; 00312 } 00313 else { 00314 y->avl_link[1] = x->avl_link[0]; 00315 x->avl_link[0] = y; 00316 pa[k - 1]->avl_link[da[k - 1]] = x; 00317 if (x->avl_balance == 0) { 00318 x->avl_balance = -1; 00319 y->avl_balance = +1; 00320 break; 00321 } 00322 else 00323 x->avl_balance = y->avl_balance = 0; 00324 } 00325 } 00326 } 00327 else { 00328 y->avl_balance--; 00329 if (y->avl_balance == -1) 00330 break; 00331 else if (y->avl_balance == -2) { 00332 struct avl_node *x = y->avl_link[0]; 00333 00334 if (x->avl_balance == +1) { 00335 struct avl_node *w; 00336 00337 assert(x->avl_balance == +1); 00338 w = x->avl_link[1]; 00339 x->avl_link[1] = w->avl_link[0]; 00340 w->avl_link[0] = x; 00341 y->avl_link[0] = w->avl_link[1]; 00342 w->avl_link[1] = y; 00343 if (w->avl_balance == -1) 00344 x->avl_balance = 0, y->avl_balance = +1; 00345 else if (w->avl_balance == 0) 00346 x->avl_balance = y->avl_balance = 0; 00347 else /* |w->avl_balance == +1| */ 00348 x->avl_balance = -1, y->avl_balance = 0; 00349 w->avl_balance = 0; 00350 pa[k - 1]->avl_link[da[k - 1]] = w; 00351 } 00352 else { 00353 y->avl_link[0] = x->avl_link[1]; 00354 x->avl_link[1] = y; 00355 pa[k - 1]->avl_link[da[k - 1]] = x; 00356 if (x->avl_balance == 0) { 00357 x->avl_balance = +1; 00358 y->avl_balance = -1; 00359 break; 00360 } 00361 else 00362 x->avl_balance = y->avl_balance = 0; 00363 } 00364 } 00365 } 00366 } 00367 00368 tree->avl_count--; 00369 tree->avl_generation++; 00370 return (void *)item; 00371 } 00372 00373 /* Refreshes the stack of parent pointers in |trav| 00374 and updates its generation number. */ 00375 static void trav_refresh(struct avl_traverser *trav) 00376 { 00377 assert(trav != NULL); 00378 00379 trav->avl_generation = trav->avl_table->avl_generation; 00380 00381 if (trav->avl_node != NULL) { 00382 avl_comparison_func *cmp = trav->avl_table->avl_compare; 00383 void *param = trav->avl_table->avl_param; 00384 struct avl_node *node = trav->avl_node; 00385 struct avl_node *i; 00386 00387 trav->avl_height = 0; 00388 for (i = trav->avl_table->avl_root; i != node;) { 00389 assert(trav->avl_height < AVL_MAX_HEIGHT); 00390 assert(i != NULL); 00391 00392 trav->avl_stack[trav->avl_height++] = i; 00393 i = i->avl_link[cmp(node->avl_data, i->avl_data, param) > 0]; 00394 } 00395 } 00396 } 00397 00398 /* Initializes |trav| for use with |tree| 00399 and selects the null node. */ 00400 void avl_t_init(struct avl_traverser *trav, struct avl_table *tree) 00401 { 00402 trav->avl_table = tree; 00403 trav->avl_node = NULL; 00404 trav->avl_height = 0; 00405 trav->avl_generation = tree->avl_generation; 00406 } 00407 00408 /* Initializes |trav| for |tree| 00409 and selects and returns a pointer to its least-valued item. 00410 Returns |NULL| if |tree| contains no nodes. */ 00411 void *avl_t_first(struct avl_traverser *trav, struct avl_table *tree) 00412 { 00413 struct avl_node *x; 00414 00415 assert(tree != NULL && trav != NULL); 00416 00417 trav->avl_table = tree; 00418 trav->avl_height = 0; 00419 trav->avl_generation = tree->avl_generation; 00420 00421 x = tree->avl_root; 00422 if (x != NULL) 00423 while (x->avl_link[0] != NULL) { 00424 assert(trav->avl_height < AVL_MAX_HEIGHT); 00425 trav->avl_stack[trav->avl_height++] = x; 00426 x = x->avl_link[0]; 00427 } 00428 trav->avl_node = x; 00429 00430 return x != NULL ? x->avl_data : NULL; 00431 } 00432 00433 /* Initializes |trav| for |tree| 00434 and selects and returns a pointer to its greatest-valued item. 00435 Returns |NULL| if |tree| contains no nodes. */ 00436 void *avl_t_last(struct avl_traverser *trav, struct avl_table *tree) 00437 { 00438 struct avl_node *x; 00439 00440 assert(tree != NULL && trav != NULL); 00441 00442 trav->avl_table = tree; 00443 trav->avl_height = 0; 00444 trav->avl_generation = tree->avl_generation; 00445 00446 x = tree->avl_root; 00447 if (x != NULL) 00448 while (x->avl_link[1] != NULL) { 00449 assert(trav->avl_height < AVL_MAX_HEIGHT); 00450 trav->avl_stack[trav->avl_height++] = x; 00451 x = x->avl_link[1]; 00452 } 00453 trav->avl_node = x; 00454 00455 return x != NULL ? x->avl_data : NULL; 00456 } 00457 00458 /* Searches for |item| in |tree|. 00459 If found, initializes |trav| to the item found and returns the item 00460 as well. 00461 If there is no matching item, initializes |trav| to the null item 00462 and returns |NULL|. */ 00463 void *avl_t_find(struct avl_traverser *trav, struct avl_table *tree, 00464 void *item) 00465 { 00466 struct avl_node *p, *q; 00467 00468 assert(trav != NULL && tree != NULL && item != NULL); 00469 trav->avl_table = tree; 00470 trav->avl_height = 0; 00471 trav->avl_generation = tree->avl_generation; 00472 for (p = tree->avl_root; p != NULL; p = q) { 00473 int cmp = tree->avl_compare(item, p->avl_data, tree->avl_param); 00474 00475 if (cmp < 0) 00476 q = p->avl_link[0]; 00477 else if (cmp > 0) 00478 q = p->avl_link[1]; 00479 else { /* |cmp == 0| */ 00480 00481 trav->avl_node = p; 00482 return p->avl_data; 00483 } 00484 00485 assert(trav->avl_height < AVL_MAX_HEIGHT); 00486 trav->avl_stack[trav->avl_height++] = p; 00487 } 00488 00489 trav->avl_height = 0; 00490 trav->avl_node = NULL; 00491 return NULL; 00492 } 00493 00494 /* Attempts to insert |item| into |tree|. 00495 If |item| is inserted successfully, it is returned and |trav| is 00496 initialized to its location. 00497 If a duplicate is found, it is returned and |trav| is initialized to 00498 its location. No replacement of the item occurs. 00499 If a memory allocation failure occurs, |NULL| is returned and |trav| 00500 is initialized to the null item. */ 00501 void *avl_t_insert(struct avl_traverser *trav, struct avl_table *tree, 00502 void *item) 00503 { 00504 void **p; 00505 00506 assert(trav != NULL && tree != NULL && item != NULL); 00507 00508 p = avl_probe(tree, item); 00509 if (p != NULL) { 00510 trav->avl_table = tree; 00511 trav->avl_node = ((struct avl_node *) 00512 ((char *)p - offsetof(struct avl_node, avl_data))); 00513 00514 trav->avl_generation = tree->avl_generation - 1; 00515 return *p; 00516 } 00517 else { 00518 avl_t_init(trav, tree); 00519 return NULL; 00520 } 00521 } 00522 00523 /* Initializes |trav| to have the same current node as |src|. */ 00524 void *avl_t_copy(struct avl_traverser *trav, const struct avl_traverser *src) 00525 { 00526 assert(trav != NULL && src != NULL); 00527 00528 if (trav != src) { 00529 trav->avl_table = src->avl_table; 00530 trav->avl_node = src->avl_node; 00531 trav->avl_generation = src->avl_generation; 00532 if (trav->avl_generation == trav->avl_table->avl_generation) { 00533 trav->avl_height = src->avl_height; 00534 memcpy(trav->avl_stack, (const void *)src->avl_stack, 00535 sizeof *trav->avl_stack * trav->avl_height); 00536 } 00537 } 00538 00539 return trav->avl_node != NULL ? trav->avl_node->avl_data : NULL; 00540 } 00541 00542 /* Returns the next data item in inorder 00543 within the tree being traversed with |trav|, 00544 or if there are no more data items returns |NULL|. */ 00545 void *avl_t_next(struct avl_traverser *trav) 00546 { 00547 struct avl_node *x; 00548 00549 assert(trav != NULL); 00550 00551 if (trav->avl_generation != trav->avl_table->avl_generation) 00552 trav_refresh(trav); 00553 00554 x = trav->avl_node; 00555 if (x == NULL) { 00556 return avl_t_first(trav, trav->avl_table); 00557 } 00558 else if (x->avl_link[1] != NULL) { 00559 assert(trav->avl_height < AVL_MAX_HEIGHT); 00560 trav->avl_stack[trav->avl_height++] = x; 00561 x = x->avl_link[1]; 00562 00563 while (x->avl_link[0] != NULL) { 00564 assert(trav->avl_height < AVL_MAX_HEIGHT); 00565 trav->avl_stack[trav->avl_height++] = x; 00566 x = x->avl_link[0]; 00567 } 00568 } 00569 else { 00570 struct avl_node *y; 00571 00572 do { 00573 if (trav->avl_height == 0) { 00574 trav->avl_node = NULL; 00575 return NULL; 00576 } 00577 00578 y = x; 00579 x = trav->avl_stack[--trav->avl_height]; 00580 } 00581 while (y == x->avl_link[1]); 00582 } 00583 trav->avl_node = x; 00584 00585 return x->avl_data; 00586 } 00587 00588 /* Returns the previous data item in inorder 00589 within the tree being traversed with |trav|, 00590 or if there are no more data items returns |NULL|. */ 00591 void *avl_t_prev(struct avl_traverser *trav) 00592 { 00593 struct avl_node *x; 00594 00595 assert(trav != NULL); 00596 00597 if (trav->avl_generation != trav->avl_table->avl_generation) 00598 trav_refresh(trav); 00599 00600 x = trav->avl_node; 00601 if (x == NULL) { 00602 return avl_t_last(trav, trav->avl_table); 00603 } 00604 else if (x->avl_link[0] != NULL) { 00605 assert(trav->avl_height < AVL_MAX_HEIGHT); 00606 trav->avl_stack[trav->avl_height++] = x; 00607 x = x->avl_link[0]; 00608 00609 while (x->avl_link[1] != NULL) { 00610 assert(trav->avl_height < AVL_MAX_HEIGHT); 00611 trav->avl_stack[trav->avl_height++] = x; 00612 x = x->avl_link[1]; 00613 } 00614 } 00615 else { 00616 struct avl_node *y; 00617 00618 do { 00619 if (trav->avl_height == 0) { 00620 trav->avl_node = NULL; 00621 return NULL; 00622 } 00623 00624 y = x; 00625 x = trav->avl_stack[--trav->avl_height]; 00626 } 00627 while (y == x->avl_link[0]); 00628 } 00629 trav->avl_node = x; 00630 00631 return x->avl_data; 00632 } 00633 00634 /* Returns |trav|'s current item. */ 00635 void *avl_t_cur(struct avl_traverser *trav) 00636 { 00637 assert(trav != NULL); 00638 00639 return trav->avl_node != NULL ? trav->avl_node->avl_data : NULL; 00640 } 00641 00642 /* Replaces the current item in |trav| by |new| and returns the item replaced. 00643 |trav| must not have the null item selected. 00644 The new item must not upset the ordering of the tree. */ 00645 void *avl_t_replace(struct avl_traverser *trav, void *new) 00646 { 00647 struct avl_node *old; 00648 00649 assert(trav != NULL && trav->avl_node != NULL && new != NULL); 00650 old = trav->avl_node->avl_data; 00651 trav->avl_node->avl_data = new; 00652 return old; 00653 } 00654 00655 static void 00656 copy_error_recovery(struct avl_node **stack, int height, 00657 struct avl_table *new, avl_item_func * destroy) 00658 { 00659 assert(stack != NULL && height >= 0 && new != NULL); 00660 00661 for (; height > 2; height -= 2) 00662 stack[height - 1]->avl_link[1] = NULL; 00663 avl_destroy(new, destroy); 00664 } 00665 00666 /* Copies |org| to a newly created tree, which is returned. 00667 If |copy != NULL|, each data item in |org| is first passed to |copy|, 00668 and the return values are inserted into the tree, 00669 with |NULL| return values taken as indications of failure. 00670 On failure, destroys the partially created new tree, 00671 applying |destroy|, if non-null, to each item in the new tree so far, 00672 and returns |NULL|. 00673 If |allocator != NULL|, it is used for allocation in the new tree. 00674 Otherwise, the same allocator used for |org| is used. */ 00675 struct avl_table *avl_copy(const struct avl_table *org, avl_copy_func * copy, 00676 avl_item_func * destroy, 00677 struct libavl_allocator *allocator) 00678 { 00679 struct avl_node *stack[2 * (AVL_MAX_HEIGHT + 1)]; 00680 int height = 0; 00681 00682 struct avl_table *new; 00683 const struct avl_node *x; 00684 struct avl_node *y; 00685 00686 assert(org != NULL); 00687 new = avl_create(org->avl_compare, org->avl_param, 00688 allocator != NULL ? allocator : org->avl_alloc); 00689 if (new == NULL) 00690 return NULL; 00691 new->avl_count = org->avl_count; 00692 if (new->avl_count == 0) 00693 return new; 00694 00695 x = (const struct avl_node *)&org->avl_root; 00696 y = (struct avl_node *)&new->avl_root; 00697 for (;;) { 00698 while (x->avl_link[0] != NULL) { 00699 assert(height < 2 * (AVL_MAX_HEIGHT + 1)); 00700 00701 y->avl_link[0] = 00702 new->avl_alloc->libavl_malloc(new->avl_alloc, 00703 sizeof *y->avl_link[0]); 00704 if (y->avl_link[0] == NULL) { 00705 if (y != (struct avl_node *)&new->avl_root) { 00706 y->avl_data = NULL; 00707 y->avl_link[1] = NULL; 00708 } 00709 00710 copy_error_recovery(stack, height, new, destroy); 00711 return NULL; 00712 } 00713 00714 stack[height++] = (struct avl_node *)x; 00715 stack[height++] = y; 00716 x = x->avl_link[0]; 00717 y = y->avl_link[0]; 00718 } 00719 y->avl_link[0] = NULL; 00720 00721 for (;;) { 00722 y->avl_balance = x->avl_balance; 00723 if (copy == NULL) 00724 y->avl_data = x->avl_data; 00725 else { 00726 y->avl_data = copy(x->avl_data, org->avl_param); 00727 if (y->avl_data == NULL) { 00728 y->avl_link[1] = NULL; 00729 copy_error_recovery(stack, height, new, destroy); 00730 return NULL; 00731 } 00732 } 00733 00734 if (x->avl_link[1] != NULL) { 00735 y->avl_link[1] = 00736 new->avl_alloc->libavl_malloc(new->avl_alloc, 00737 sizeof *y->avl_link[1]); 00738 if (y->avl_link[1] == NULL) { 00739 copy_error_recovery(stack, height, new, destroy); 00740 return NULL; 00741 } 00742 00743 x = x->avl_link[1]; 00744 y = y->avl_link[1]; 00745 break; 00746 } 00747 else 00748 y->avl_link[1] = NULL; 00749 00750 if (height <= 2) 00751 return new; 00752 00753 y = stack[--height]; 00754 x = stack[--height]; 00755 } 00756 } 00757 } 00758 00759 /* Frees storage allocated for |tree|. 00760 If |destroy != NULL|, applies it to each data item in inorder. */ 00761 void avl_destroy(struct avl_table *tree, avl_item_func * destroy) 00762 { 00763 struct avl_node *p, *q; 00764 00765 assert(tree != NULL); 00766 00767 for (p = tree->avl_root; p != NULL; p = q) 00768 if (p->avl_link[0] == NULL) { 00769 q = p->avl_link[1]; 00770 if (destroy != NULL && p->avl_data != NULL) 00771 destroy(p->avl_data, tree->avl_param); 00772 tree->avl_alloc->libavl_free(tree->avl_alloc, p); 00773 } 00774 else { 00775 q = p->avl_link[0]; 00776 p->avl_link[0] = q->avl_link[1]; 00777 q->avl_link[1] = p; 00778 } 00779 00780 tree->avl_alloc->libavl_free(tree->avl_alloc, tree); 00781 } 00782 00783 /* Allocates |size| bytes of space using |malloc()|. 00784 Returns a null pointer if allocation fails. */ 00785 void *avl_malloc(struct libavl_allocator *allocator, size_t size) 00786 { 00787 assert(allocator != NULL && size > 0); 00788 return malloc(size); 00789 } 00790 00791 /* Frees |block|. */ 00792 void avl_free(struct libavl_allocator *allocator, void *block) 00793 { 00794 assert(allocator != NULL && block != NULL); 00795 free(block); 00796 } 00797 00798 /* Default memory allocator that uses |malloc()| and |free()|. */ 00799 struct libavl_allocator avl_allocator_default = { 00800 avl_malloc, 00801 avl_free 00802 }; 00803 00804 /* Asserts that |avl_insert()| succeeds at inserting |item| into |table|. */ 00805 void (avl_assert_insert) (struct avl_table * table, void *item) 00806 { 00807 void **p = avl_probe(table, item); 00808 00809 assert(p != NULL && *p == item); 00810 } 00811 00812 /* Asserts that |avl_delete()| really removes |item| from |table|, 00813 and returns the removed item. */ 00814 void *(avl_assert_delete) (struct avl_table * table, void *item) 00815 { 00816 void *p = avl_delete(table, item); 00817 00818 assert(p != NULL); 00819 return p; 00820 }