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 "tavl.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 tavl_table *tavl_create(tavl_comparison_func * compare, void *param, 00036 struct libavl_allocator *allocator) 00037 { 00038 struct tavl_table *tree; 00039 00040 assert(compare != NULL); 00041 00042 if (allocator == NULL) 00043 allocator = &tavl_allocator_default; 00044 00045 tree = allocator->libavl_malloc(allocator, sizeof *tree); 00046 if (tree == NULL) 00047 return NULL; 00048 00049 tree->tavl_root = NULL; 00050 tree->tavl_compare = compare; 00051 tree->tavl_param = param; 00052 tree->tavl_alloc = allocator; 00053 tree->tavl_count = 0; 00054 00055 return tree; 00056 } 00057 00058 /* Search |tree| for an item matching |item|, and return it if found. 00059 Otherwise return |NULL|. */ 00060 void *tavl_find(const struct tavl_table *tree, const void *item) 00061 { 00062 const struct tavl_node *p; 00063 00064 assert(tree != NULL && item != NULL); 00065 00066 p = tree->tavl_root; 00067 if (p == NULL) 00068 return NULL; 00069 00070 for (;;) { 00071 int cmp, dir; 00072 00073 cmp = tree->tavl_compare(item, p->tavl_data, tree->tavl_param); 00074 if (cmp == 0) 00075 return p->tavl_data; 00076 00077 dir = cmp > 0; 00078 if (p->tavl_tag[dir] == TAVL_CHILD) 00079 p = p->tavl_link[dir]; 00080 else 00081 return NULL; 00082 } 00083 } 00084 00085 /* Inserts |item| into |tree| and returns a pointer to |item|'s address. 00086 If a duplicate item is found in the tree, 00087 returns a pointer to the duplicate without inserting |item|. 00088 Returns |NULL| in case of memory allocation failure. */ 00089 void **tavl_probe(struct tavl_table *tree, void *item) 00090 { 00091 struct tavl_node *y, *z; /* Top node to update balance factor, and parent. */ 00092 struct tavl_node *p, *q; /* Iterator, and parent. */ 00093 struct tavl_node *n; /* Newly inserted node. */ 00094 struct tavl_node *w; /* New root of rebalanced subtree. */ 00095 int dir; /* Direction to descend. */ 00096 00097 unsigned char da[TAVL_MAX_HEIGHT]; /* Cached comparison results. */ 00098 int k = 0; /* Number of cached results. */ 00099 00100 assert(tree != NULL && item != NULL); 00101 00102 z = (struct tavl_node *)&tree->tavl_root; 00103 y = tree->tavl_root; 00104 if (y != NULL) { 00105 for (q = z, p = y;; q = p, p = p->tavl_link[dir]) { 00106 int cmp = 00107 tree->tavl_compare(item, p->tavl_data, tree->tavl_param); 00108 if (cmp == 0) 00109 return &p->tavl_data; 00110 00111 if (p->tavl_balance != 0) 00112 z = q, y = p, k = 0; 00113 da[k++] = dir = cmp > 0; 00114 00115 if (p->tavl_tag[dir] == TAVL_THREAD) 00116 break; 00117 } 00118 } 00119 else { 00120 p = z; 00121 dir = 0; 00122 } 00123 00124 n = tree->tavl_alloc->libavl_malloc(tree->tavl_alloc, sizeof *n); 00125 if (n == NULL) 00126 return NULL; 00127 00128 tree->tavl_count++; 00129 n->tavl_data = item; 00130 n->tavl_tag[0] = n->tavl_tag[1] = TAVL_THREAD; 00131 n->tavl_link[dir] = p->tavl_link[dir]; 00132 if (tree->tavl_root != NULL) { 00133 p->tavl_tag[dir] = TAVL_CHILD; 00134 n->tavl_link[!dir] = p; 00135 } 00136 else 00137 n->tavl_link[1] = NULL; 00138 p->tavl_link[dir] = n; 00139 n->tavl_balance = 0; 00140 if (tree->tavl_root == n) 00141 return &n->tavl_data; 00142 00143 for (p = y, k = 0; p != n; p = p->tavl_link[da[k]], k++) 00144 if (da[k] == 0) 00145 p->tavl_balance--; 00146 else 00147 p->tavl_balance++; 00148 00149 if (y->tavl_balance == -2) { 00150 struct tavl_node *x = y->tavl_link[0]; 00151 00152 if (x->tavl_balance == -1) { 00153 w = x; 00154 if (x->tavl_tag[1] == TAVL_THREAD) { 00155 x->tavl_tag[1] = TAVL_CHILD; 00156 y->tavl_tag[0] = TAVL_THREAD; 00157 y->tavl_link[0] = x; 00158 } 00159 else 00160 y->tavl_link[0] = x->tavl_link[1]; 00161 x->tavl_link[1] = y; 00162 x->tavl_balance = y->tavl_balance = 0; 00163 } 00164 else { 00165 assert(x->tavl_balance == +1); 00166 w = x->tavl_link[1]; 00167 x->tavl_link[1] = w->tavl_link[0]; 00168 w->tavl_link[0] = x; 00169 y->tavl_link[0] = w->tavl_link[1]; 00170 w->tavl_link[1] = y; 00171 if (w->tavl_balance == -1) 00172 x->tavl_balance = 0, y->tavl_balance = +1; 00173 else if (w->tavl_balance == 0) 00174 x->tavl_balance = y->tavl_balance = 0; 00175 else /* |w->tavl_balance == +1| */ 00176 x->tavl_balance = -1, y->tavl_balance = 0; 00177 w->tavl_balance = 0; 00178 if (w->tavl_tag[0] == TAVL_THREAD) { 00179 x->tavl_tag[1] = TAVL_THREAD; 00180 x->tavl_link[1] = w; 00181 w->tavl_tag[0] = TAVL_CHILD; 00182 } 00183 if (w->tavl_tag[1] == TAVL_THREAD) { 00184 y->tavl_tag[0] = TAVL_THREAD; 00185 y->tavl_link[0] = w; 00186 w->tavl_tag[1] = TAVL_CHILD; 00187 } 00188 } 00189 } 00190 else if (y->tavl_balance == +2) { 00191 struct tavl_node *x = y->tavl_link[1]; 00192 00193 if (x->tavl_balance == +1) { 00194 w = x; 00195 if (x->tavl_tag[0] == TAVL_THREAD) { 00196 x->tavl_tag[0] = TAVL_CHILD; 00197 y->tavl_tag[1] = TAVL_THREAD; 00198 y->tavl_link[1] = x; 00199 } 00200 else 00201 y->tavl_link[1] = x->tavl_link[0]; 00202 x->tavl_link[0] = y; 00203 x->tavl_balance = y->tavl_balance = 0; 00204 } 00205 else { 00206 assert(x->tavl_balance == -1); 00207 w = x->tavl_link[0]; 00208 x->tavl_link[0] = w->tavl_link[1]; 00209 w->tavl_link[1] = x; 00210 y->tavl_link[1] = w->tavl_link[0]; 00211 w->tavl_link[0] = y; 00212 if (w->tavl_balance == +1) 00213 x->tavl_balance = 0, y->tavl_balance = -1; 00214 else if (w->tavl_balance == 0) 00215 x->tavl_balance = y->tavl_balance = 0; 00216 else /* |w->tavl_balance == -1| */ 00217 x->tavl_balance = +1, y->tavl_balance = 0; 00218 w->tavl_balance = 0; 00219 if (w->tavl_tag[0] == TAVL_THREAD) { 00220 y->tavl_tag[1] = TAVL_THREAD; 00221 y->tavl_link[1] = w; 00222 w->tavl_tag[0] = TAVL_CHILD; 00223 } 00224 if (w->tavl_tag[1] == TAVL_THREAD) { 00225 x->tavl_tag[0] = TAVL_THREAD; 00226 x->tavl_link[0] = w; 00227 w->tavl_tag[1] = TAVL_CHILD; 00228 } 00229 } 00230 } 00231 else 00232 return &n->tavl_data; 00233 z->tavl_link[y != z->tavl_link[0]] = w; 00234 00235 return &n->tavl_data; 00236 } 00237 00238 /* Inserts |item| into |table|. 00239 Returns |NULL| if |item| was successfully inserted 00240 or if a memory allocation error occurred. 00241 Otherwise, returns the duplicate item. */ 00242 void *tavl_insert(struct tavl_table *table, void *item) 00243 { 00244 void **p = tavl_probe(table, item); 00245 00246 return p == NULL || *p == item ? NULL : *p; 00247 } 00248 00249 /* Inserts |item| into |table|, replacing any duplicate item. 00250 Returns |NULL| if |item| was inserted without replacing a duplicate, 00251 or if a memory allocation error occurred. 00252 Otherwise, returns the item that was replaced. */ 00253 void *tavl_replace(struct tavl_table *table, void *item) 00254 { 00255 void **p = tavl_probe(table, item); 00256 00257 if (p == NULL || *p == item) 00258 return NULL; 00259 else { 00260 void *r = *p; 00261 00262 *p = item; 00263 return r; 00264 } 00265 } 00266 00267 /* Returns the parent of |node| within |tree|, 00268 or a pointer to |tavl_root| if |s| is the root of the tree. */ 00269 static struct tavl_node *find_parent(struct tavl_table *tree, 00270 struct tavl_node *node) 00271 { 00272 if (node != tree->tavl_root) { 00273 struct tavl_node *x, *y; 00274 00275 for (x = y = node;; x = x->tavl_link[0], y = y->tavl_link[1]) 00276 if (y->tavl_tag[1] == TAVL_THREAD) { 00277 struct tavl_node *p = y->tavl_link[1]; 00278 00279 if (p == NULL || p->tavl_link[0] != node) { 00280 while (x->tavl_tag[0] == TAVL_CHILD) 00281 x = x->tavl_link[0]; 00282 p = x->tavl_link[0]; 00283 } 00284 return p; 00285 } 00286 else if (x->tavl_tag[0] == TAVL_THREAD) { 00287 struct tavl_node *p = x->tavl_link[0]; 00288 00289 if (p == NULL || p->tavl_link[1] != node) { 00290 while (y->tavl_tag[1] == TAVL_CHILD) 00291 y = y->tavl_link[1]; 00292 p = y->tavl_link[1]; 00293 } 00294 return p; 00295 } 00296 } 00297 else 00298 return (struct tavl_node *)&tree->tavl_root; 00299 } 00300 00301 /* Deletes from |tree| and returns an item matching |item|. 00302 Returns a null pointer if no matching item found. */ 00303 void *tavl_delete(struct tavl_table *tree, const void *item) 00304 { 00305 struct tavl_node *p; /* Traverses tree to find node to delete. */ 00306 struct tavl_node *q; /* Parent of |p|. */ 00307 int dir; /* Index into |q->tavl_link[]| to get |p|. */ 00308 int cmp; /* Result of comparison between |item| and |p|. */ 00309 00310 assert(tree != NULL && item != NULL); 00311 00312 if (tree->tavl_root == NULL) 00313 return NULL; 00314 00315 p = (struct tavl_node *)&tree->tavl_root; 00316 for (cmp = -1; cmp != 0; 00317 cmp = tree->tavl_compare(item, p->tavl_data, tree->tavl_param)) { 00318 dir = cmp > 0; 00319 00320 q = p; 00321 if (p->tavl_tag[dir] == TAVL_THREAD) 00322 return NULL; 00323 p = p->tavl_link[dir]; 00324 } 00325 item = p->tavl_data; 00326 00327 if (p->tavl_tag[1] == TAVL_THREAD) { 00328 if (p->tavl_tag[0] == TAVL_CHILD) { 00329 struct tavl_node *t = p->tavl_link[0]; 00330 00331 while (t->tavl_tag[1] == TAVL_CHILD) 00332 t = t->tavl_link[1]; 00333 t->tavl_link[1] = p->tavl_link[1]; 00334 q->tavl_link[dir] = p->tavl_link[0]; 00335 } 00336 else { 00337 q->tavl_link[dir] = p->tavl_link[dir]; 00338 if (q != (struct tavl_node *)&tree->tavl_root) 00339 q->tavl_tag[dir] = TAVL_THREAD; 00340 } 00341 } 00342 else { 00343 struct tavl_node *r = p->tavl_link[1]; 00344 00345 if (r->tavl_tag[0] == TAVL_THREAD) { 00346 r->tavl_link[0] = p->tavl_link[0]; 00347 r->tavl_tag[0] = p->tavl_tag[0]; 00348 if (r->tavl_tag[0] == TAVL_CHILD) { 00349 struct tavl_node *t = r->tavl_link[0]; 00350 00351 while (t->tavl_tag[1] == TAVL_CHILD) 00352 t = t->tavl_link[1]; 00353 t->tavl_link[1] = r; 00354 } 00355 q->tavl_link[dir] = r; 00356 r->tavl_balance = p->tavl_balance; 00357 q = r; 00358 dir = 1; 00359 } 00360 else { 00361 struct tavl_node *s; 00362 00363 for (;;) { 00364 s = r->tavl_link[0]; 00365 if (s->tavl_tag[0] == TAVL_THREAD) 00366 break; 00367 00368 r = s; 00369 } 00370 00371 if (s->tavl_tag[1] == TAVL_CHILD) 00372 r->tavl_link[0] = s->tavl_link[1]; 00373 else { 00374 r->tavl_link[0] = s; 00375 r->tavl_tag[0] = TAVL_THREAD; 00376 } 00377 00378 s->tavl_link[0] = p->tavl_link[0]; 00379 if (p->tavl_tag[0] == TAVL_CHILD) { 00380 struct tavl_node *t = p->tavl_link[0]; 00381 00382 while (t->tavl_tag[1] == TAVL_CHILD) 00383 t = t->tavl_link[1]; 00384 t->tavl_link[1] = s; 00385 00386 s->tavl_tag[0] = TAVL_CHILD; 00387 } 00388 00389 s->tavl_link[1] = p->tavl_link[1]; 00390 s->tavl_tag[1] = TAVL_CHILD; 00391 00392 q->tavl_link[dir] = s; 00393 s->tavl_balance = p->tavl_balance; 00394 q = r; 00395 dir = 0; 00396 } 00397 } 00398 00399 tree->tavl_alloc->libavl_free(tree->tavl_alloc, p); 00400 00401 while (q != (struct tavl_node *)&tree->tavl_root) { 00402 struct tavl_node *y = q; 00403 00404 q = find_parent(tree, y); 00405 00406 if (dir == 0) { 00407 dir = q->tavl_link[0] != y; 00408 y->tavl_balance++; 00409 if (y->tavl_balance == +1) 00410 break; 00411 else if (y->tavl_balance == +2) { 00412 struct tavl_node *x = y->tavl_link[1]; 00413 00414 assert(x != NULL); 00415 if (x->tavl_balance == -1) { 00416 struct tavl_node *w; 00417 00418 assert(x->tavl_balance == -1); 00419 w = x->tavl_link[0]; 00420 x->tavl_link[0] = w->tavl_link[1]; 00421 w->tavl_link[1] = x; 00422 y->tavl_link[1] = w->tavl_link[0]; 00423 w->tavl_link[0] = y; 00424 if (w->tavl_balance == +1) 00425 x->tavl_balance = 0, y->tavl_balance = -1; 00426 else if (w->tavl_balance == 0) 00427 x->tavl_balance = y->tavl_balance = 0; 00428 else /* |w->tavl_balance == -1| */ 00429 x->tavl_balance = +1, y->tavl_balance = 0; 00430 w->tavl_balance = 0; 00431 if (w->tavl_tag[0] == TAVL_THREAD) { 00432 y->tavl_tag[1] = TAVL_THREAD; 00433 y->tavl_link[1] = w; 00434 w->tavl_tag[0] = TAVL_CHILD; 00435 } 00436 if (w->tavl_tag[1] == TAVL_THREAD) { 00437 x->tavl_tag[0] = TAVL_THREAD; 00438 x->tavl_link[0] = w; 00439 w->tavl_tag[1] = TAVL_CHILD; 00440 } 00441 q->tavl_link[dir] = w; 00442 } 00443 else { 00444 q->tavl_link[dir] = x; 00445 00446 if (x->tavl_balance == 0) { 00447 y->tavl_link[1] = x->tavl_link[0]; 00448 x->tavl_link[0] = y; 00449 x->tavl_balance = -1; 00450 y->tavl_balance = +1; 00451 break; 00452 } 00453 else { /* |x->tavl_balance == +1| */ 00454 00455 if (x->tavl_tag[0] == TAVL_CHILD) 00456 y->tavl_link[1] = x->tavl_link[0]; 00457 else { 00458 y->tavl_tag[1] = TAVL_THREAD; 00459 x->tavl_tag[0] = TAVL_CHILD; 00460 } 00461 x->tavl_link[0] = y; 00462 y->tavl_balance = x->tavl_balance = 0; 00463 } 00464 } 00465 } 00466 } 00467 else { 00468 dir = q->tavl_link[0] != y; 00469 y->tavl_balance--; 00470 if (y->tavl_balance == -1) 00471 break; 00472 else if (y->tavl_balance == -2) { 00473 struct tavl_node *x = y->tavl_link[0]; 00474 00475 assert(x != NULL); 00476 if (x->tavl_balance == +1) { 00477 struct tavl_node *w; 00478 00479 assert(x->tavl_balance == +1); 00480 w = x->tavl_link[1]; 00481 x->tavl_link[1] = w->tavl_link[0]; 00482 w->tavl_link[0] = x; 00483 y->tavl_link[0] = w->tavl_link[1]; 00484 w->tavl_link[1] = y; 00485 if (w->tavl_balance == -1) 00486 x->tavl_balance = 0, y->tavl_balance = +1; 00487 else if (w->tavl_balance == 0) 00488 x->tavl_balance = y->tavl_balance = 0; 00489 else /* |w->tavl_balance == +1| */ 00490 x->tavl_balance = -1, y->tavl_balance = 0; 00491 w->tavl_balance = 0; 00492 if (w->tavl_tag[0] == TAVL_THREAD) { 00493 x->tavl_tag[1] = TAVL_THREAD; 00494 x->tavl_link[1] = w; 00495 w->tavl_tag[0] = TAVL_CHILD; 00496 } 00497 if (w->tavl_tag[1] == TAVL_THREAD) { 00498 y->tavl_tag[0] = TAVL_THREAD; 00499 y->tavl_link[0] = w; 00500 w->tavl_tag[1] = TAVL_CHILD; 00501 } 00502 q->tavl_link[dir] = w; 00503 } 00504 else { 00505 q->tavl_link[dir] = x; 00506 00507 if (x->tavl_balance == 0) { 00508 y->tavl_link[0] = x->tavl_link[1]; 00509 x->tavl_link[1] = y; 00510 x->tavl_balance = +1; 00511 y->tavl_balance = -1; 00512 break; 00513 } 00514 else { /* |x->tavl_balance == -1| */ 00515 00516 if (x->tavl_tag[1] == TAVL_CHILD) 00517 y->tavl_link[0] = x->tavl_link[1]; 00518 else { 00519 y->tavl_tag[0] = TAVL_THREAD; 00520 x->tavl_tag[1] = TAVL_CHILD; 00521 } 00522 x->tavl_link[1] = y; 00523 y->tavl_balance = x->tavl_balance = 0; 00524 } 00525 } 00526 } 00527 } 00528 } 00529 00530 tree->tavl_count--; 00531 return (void *)item; 00532 } 00533 00534 /* Initializes |trav| for use with |tree| 00535 and selects the null node. */ 00536 void tavl_t_init(struct tavl_traverser *trav, struct tavl_table *tree) 00537 { 00538 trav->tavl_table = tree; 00539 trav->tavl_node = NULL; 00540 } 00541 00542 /* Initializes |trav| for |tree|. 00543 Returns data item in |tree| with the least value, 00544 or |NULL| if |tree| is empty. */ 00545 void *tavl_t_first(struct tavl_traverser *trav, struct tavl_table *tree) 00546 { 00547 assert(tree != NULL && trav != NULL); 00548 00549 trav->tavl_table = tree; 00550 trav->tavl_node = tree->tavl_root; 00551 if (trav->tavl_node != NULL) { 00552 while (trav->tavl_node->tavl_tag[0] == TAVL_CHILD) 00553 trav->tavl_node = trav->tavl_node->tavl_link[0]; 00554 return trav->tavl_node->tavl_data; 00555 } 00556 else 00557 return NULL; 00558 } 00559 00560 /* Initializes |trav| for |tree|. 00561 Returns data item in |tree| with the greatest value, 00562 or |NULL| if |tree| is empty. */ 00563 void *tavl_t_last(struct tavl_traverser *trav, struct tavl_table *tree) 00564 { 00565 assert(tree != NULL && trav != NULL); 00566 00567 trav->tavl_table = tree; 00568 trav->tavl_node = tree->tavl_root; 00569 if (trav->tavl_node != NULL) { 00570 while (trav->tavl_node->tavl_tag[1] == TAVL_CHILD) 00571 trav->tavl_node = trav->tavl_node->tavl_link[1]; 00572 return trav->tavl_node->tavl_data; 00573 } 00574 else 00575 return NULL; 00576 } 00577 00578 /* Searches for |item| in |tree|. 00579 If found, initializes |trav| to the item found and returns the item 00580 as well. 00581 If there is no matching item, initializes |trav| to the null item 00582 and returns |NULL|. */ 00583 void *tavl_t_find(struct tavl_traverser *trav, struct tavl_table *tree, 00584 void *item) 00585 { 00586 struct tavl_node *p; 00587 00588 assert(trav != NULL && tree != NULL && item != NULL); 00589 00590 trav->tavl_table = tree; 00591 trav->tavl_node = NULL; 00592 00593 p = tree->tavl_root; 00594 if (p == NULL) 00595 return NULL; 00596 00597 for (;;) { 00598 int cmp, dir; 00599 00600 cmp = tree->tavl_compare(item, p->tavl_data, tree->tavl_param); 00601 if (cmp == 0) { 00602 trav->tavl_node = p; 00603 return p->tavl_data; 00604 } 00605 00606 dir = cmp > 0; 00607 if (p->tavl_tag[dir] == TAVL_CHILD) 00608 p = p->tavl_link[dir]; 00609 else 00610 return NULL; 00611 } 00612 } 00613 00614 /* Attempts to insert |item| into |tree|. 00615 If |item| is inserted successfully, it is returned and |trav| is 00616 initialized to its location. 00617 If a duplicate is found, it is returned and |trav| is initialized to 00618 its location. No replacement of the item occurs. 00619 If a memory allocation failure occurs, |NULL| is returned and |trav| 00620 is initialized to the null item. */ 00621 void *tavl_t_insert(struct tavl_traverser *trav, 00622 struct tavl_table *tree, void *item) 00623 { 00624 void **p; 00625 00626 assert(trav != NULL && tree != NULL && item != NULL); 00627 00628 p = tavl_probe(tree, item); 00629 if (p != NULL) { 00630 trav->tavl_table = tree; 00631 trav->tavl_node = ((struct tavl_node *) 00632 ((char *)p - 00633 offsetof(struct tavl_node, tavl_data))); 00634 return *p; 00635 } 00636 else { 00637 tavl_t_init(trav, tree); 00638 return NULL; 00639 } 00640 } 00641 00642 /* Initializes |trav| to have the same current node as |src|. */ 00643 void *tavl_t_copy(struct tavl_traverser *trav, 00644 const struct tavl_traverser *src) 00645 { 00646 assert(trav != NULL && src != NULL); 00647 00648 trav->tavl_table = src->tavl_table; 00649 trav->tavl_node = src->tavl_node; 00650 00651 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL; 00652 } 00653 00654 /* Returns the next data item in inorder 00655 within the tree being traversed with |trav|, 00656 or if there are no more data items returns |NULL|. */ 00657 void *tavl_t_next(struct tavl_traverser *trav) 00658 { 00659 assert(trav != NULL); 00660 00661 if (trav->tavl_node == NULL) 00662 return tavl_t_first(trav, trav->tavl_table); 00663 else if (trav->tavl_node->tavl_tag[1] == TAVL_THREAD) { 00664 trav->tavl_node = trav->tavl_node->tavl_link[1]; 00665 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL; 00666 } 00667 else { 00668 trav->tavl_node = trav->tavl_node->tavl_link[1]; 00669 while (trav->tavl_node->tavl_tag[0] == TAVL_CHILD) 00670 trav->tavl_node = trav->tavl_node->tavl_link[0]; 00671 return trav->tavl_node->tavl_data; 00672 } 00673 } 00674 00675 /* Returns the previous data item in inorder 00676 within the tree being traversed with |trav|, 00677 or if there are no more data items returns |NULL|. */ 00678 void *tavl_t_prev(struct tavl_traverser *trav) 00679 { 00680 assert(trav != NULL); 00681 00682 if (trav->tavl_node == NULL) 00683 return tavl_t_last(trav, trav->tavl_table); 00684 else if (trav->tavl_node->tavl_tag[0] == TAVL_THREAD) { 00685 trav->tavl_node = trav->tavl_node->tavl_link[0]; 00686 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL; 00687 } 00688 else { 00689 trav->tavl_node = trav->tavl_node->tavl_link[0]; 00690 while (trav->tavl_node->tavl_tag[1] == TAVL_CHILD) 00691 trav->tavl_node = trav->tavl_node->tavl_link[1]; 00692 return trav->tavl_node->tavl_data; 00693 } 00694 } 00695 00696 /* Returns |trav|'s current item. */ 00697 void *tavl_t_cur(struct tavl_traverser *trav) 00698 { 00699 assert(trav != NULL); 00700 00701 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL; 00702 } 00703 00704 /* Replaces the current item in |trav| by |new| and returns the item replaced. 00705 |trav| must not have the null item selected. 00706 The new item must not upset the ordering of the tree. */ 00707 void *tavl_t_replace(struct tavl_traverser *trav, void *new) 00708 { 00709 struct tavl_node *old; 00710 00711 assert(trav != NULL && trav->tavl_node != NULL && new != NULL); 00712 old = trav->tavl_node->tavl_data; 00713 trav->tavl_node->tavl_data = new; 00714 return old; 00715 } 00716 00717 /* Creates a new node as a child of |dst| on side |dir|. 00718 Copies data and |tavl_balance| from |src| into the new node, 00719 applying |copy()|, if non-null. 00720 Returns nonzero only if fully successful. 00721 Regardless of success, integrity of the tree structure is assured, 00722 though failure may leave a null pointer in a |tavl_data| member. */ 00723 static int 00724 copy_node(struct tavl_table *tree, 00725 struct tavl_node *dst, int dir, 00726 const struct tavl_node *src, tavl_copy_func * copy) 00727 { 00728 struct tavl_node *new = 00729 tree->tavl_alloc->libavl_malloc(tree->tavl_alloc, sizeof *new); 00730 if (new == NULL) 00731 return 0; 00732 00733 new->tavl_link[dir] = dst->tavl_link[dir]; 00734 new->tavl_tag[dir] = TAVL_THREAD; 00735 new->tavl_link[!dir] = dst; 00736 new->tavl_tag[!dir] = TAVL_THREAD; 00737 dst->tavl_link[dir] = new; 00738 dst->tavl_tag[dir] = TAVL_CHILD; 00739 00740 new->tavl_balance = src->tavl_balance; 00741 if (copy == NULL) 00742 new->tavl_data = src->tavl_data; 00743 else { 00744 new->tavl_data = copy(src->tavl_data, tree->tavl_param); 00745 if (new->tavl_data == NULL) 00746 return 0; 00747 } 00748 00749 return 1; 00750 } 00751 00752 static void 00753 copy_error_recovery(struct tavl_node *p, 00754 struct tavl_table *new, tavl_item_func * destroy) 00755 { 00756 new->tavl_root = p; 00757 if (p != NULL) { 00758 while (p->tavl_tag[1] == TAVL_CHILD) 00759 p = p->tavl_link[1]; 00760 p->tavl_link[1] = NULL; 00761 } 00762 tavl_destroy(new, destroy); 00763 } 00764 00765 /* Copies |org| to a newly created tree, which is returned. 00766 If |copy != NULL|, each data item in |org| is first passed to |copy|, 00767 and the return values are inserted into the tree, 00768 with |NULL| return values taken as indications of failure. 00769 On failure, destroys the partially created new tree, 00770 applying |destroy|, if non-null, to each item in the new tree so far, 00771 and returns |NULL|. 00772 If |allocator != NULL|, it is used for allocation in the new tree. 00773 Otherwise, the same allocator used for |org| is used. */ 00774 struct tavl_table *tavl_copy(const struct tavl_table *org, 00775 tavl_copy_func * copy, tavl_item_func * destroy, 00776 struct libavl_allocator *allocator) 00777 { 00778 struct tavl_table *new; 00779 00780 const struct tavl_node *p; 00781 struct tavl_node *q; 00782 struct tavl_node rp, rq; 00783 00784 assert(org != NULL); 00785 new = tavl_create(org->tavl_compare, org->tavl_param, 00786 allocator != NULL ? allocator : org->tavl_alloc); 00787 if (new == NULL) 00788 return NULL; 00789 00790 new->tavl_count = org->tavl_count; 00791 if (new->tavl_count == 0) 00792 return new; 00793 00794 p = &rp; 00795 rp.tavl_link[0] = org->tavl_root; 00796 rp.tavl_tag[0] = TAVL_CHILD; 00797 00798 q = &rq; 00799 rq.tavl_link[0] = NULL; 00800 rq.tavl_tag[0] = TAVL_THREAD; 00801 00802 for (;;) { 00803 if (p->tavl_tag[0] == TAVL_CHILD) { 00804 if (!copy_node(new, q, 0, p->tavl_link[0], copy)) { 00805 copy_error_recovery(rq.tavl_link[0], new, destroy); 00806 return NULL; 00807 } 00808 00809 p = p->tavl_link[0]; 00810 q = q->tavl_link[0]; 00811 } 00812 else { 00813 while (p->tavl_tag[1] == TAVL_THREAD) { 00814 p = p->tavl_link[1]; 00815 if (p == NULL) { 00816 q->tavl_link[1] = NULL; 00817 new->tavl_root = rq.tavl_link[0]; 00818 return new; 00819 } 00820 00821 q = q->tavl_link[1]; 00822 } 00823 00824 p = p->tavl_link[1]; 00825 q = q->tavl_link[1]; 00826 } 00827 00828 if (p->tavl_tag[1] == TAVL_CHILD) 00829 if (!copy_node(new, q, 1, p->tavl_link[1], copy)) { 00830 copy_error_recovery(rq.tavl_link[0], new, destroy); 00831 return NULL; 00832 } 00833 } 00834 } 00835 00836 /* Frees storage allocated for |tree|. 00837 If |destroy != NULL|, applies it to each data item in inorder. */ 00838 void tavl_destroy(struct tavl_table *tree, tavl_item_func * destroy) 00839 { 00840 struct tavl_node *p; /* Current node. */ 00841 struct tavl_node *n; /* Next node. */ 00842 00843 p = tree->tavl_root; 00844 if (p != NULL) 00845 while (p->tavl_tag[0] == TAVL_CHILD) 00846 p = p->tavl_link[0]; 00847 00848 while (p != NULL) { 00849 n = p->tavl_link[1]; 00850 if (p->tavl_tag[1] == TAVL_CHILD) 00851 while (n->tavl_tag[0] == TAVL_CHILD) 00852 n = n->tavl_link[0]; 00853 00854 if (destroy != NULL && p->tavl_data != NULL) 00855 destroy(p->tavl_data, tree->tavl_param); 00856 tree->tavl_alloc->libavl_free(tree->tavl_alloc, p); 00857 00858 p = n; 00859 } 00860 00861 tree->tavl_alloc->libavl_free(tree->tavl_alloc, tree); 00862 } 00863 00864 /* Allocates |size| bytes of space using |malloc()|. 00865 Returns a null pointer if allocation fails. */ 00866 void *tavl_malloc(struct libavl_allocator *allocator, size_t size) 00867 { 00868 assert(allocator != NULL && size > 0); 00869 return malloc(size); 00870 } 00871 00872 /* Frees |block|. */ 00873 void tavl_free(struct libavl_allocator *allocator, void *block) 00874 { 00875 assert(allocator != NULL && block != NULL); 00876 free(block); 00877 } 00878 00879 /* Default memory allocator that uses |malloc()| and |free()|. */ 00880 struct libavl_allocator tavl_allocator_default = { 00881 tavl_malloc, 00882 tavl_free 00883 }; 00884 00885 /* Asserts that |tavl_insert()| succeeds at inserting |item| into |table|. */ 00886 void (tavl_assert_insert) (struct tavl_table * table, void *item) 00887 { 00888 void **p = tavl_probe(table, item); 00889 00890 assert(p != NULL && *p == item); 00891 } 00892 00893 /* Asserts that |tavl_delete()| really removes |item| from |table|, 00894 and returns the removed item. */ 00895 void *(tavl_assert_delete) (struct tavl_table * table, void *item) 00896 { 00897 void *p = tavl_delete(table, item); 00898 00899 assert(p != NULL); 00900 return p; 00901 }