00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #include <assert.h>
00027 #include <stdio.h>
00028 #include <stdlib.h>
00029 #include "tavl.h"
00030
00031
00032
00033
00034
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
00059
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
00086
00087
00088
00089 void **tavl_probe(struct tavl_table *tree, void *item)
00090 {
00091 struct tavl_node *y, *z;
00092 struct tavl_node *p, *q;
00093 struct tavl_node *n;
00094 struct tavl_node *w;
00095 int dir;
00096
00097 unsigned char da[TAVL_MAX_HEIGHT];
00098 int k = 0;
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
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
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
00239
00240
00241
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
00250
00251
00252
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
00268
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
00302
00303 void *tavl_delete(struct tavl_table *tree, const void *item)
00304 {
00305 struct tavl_node *p;
00306 struct tavl_node *q;
00307 int dir;
00308 int cmp;
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
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 {
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
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 {
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
00535
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
00543
00544
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
00561
00562
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
00579
00580
00581
00582
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
00615
00616
00617
00618
00619
00620
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
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
00655
00656
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
00676
00677
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
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
00705
00706
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
00718
00719
00720
00721
00722
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
00766
00767
00768
00769
00770
00771
00772
00773
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
00837
00838 void tavl_destroy(struct tavl_table *tree, tavl_item_func * destroy)
00839 {
00840 struct tavl_node *p;
00841 struct tavl_node *n;
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
00865
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
00873 void tavl_free(struct libavl_allocator *allocator, void *block)
00874 {
00875 assert(allocator != NULL && block != NULL);
00876 free(block);
00877 }
00878
00879
00880 struct libavl_allocator tavl_allocator_default = {
00881 tavl_malloc,
00882 tavl_free
00883 };
00884
00885
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
00894
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 }