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