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