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 *
00036 tavl_create (tavl_comparison_func *compare, void *param,
00037 struct libavl_allocator *allocator)
00038 {
00039 struct tavl_table *tree;
00040
00041 assert (compare != NULL);
00042
00043 if (allocator == NULL)
00044 allocator = &tavl_allocator_default;
00045
00046 tree = allocator->libavl_malloc (allocator, sizeof *tree);
00047 if (tree == NULL)
00048 return NULL;
00049
00050 tree->tavl_root = NULL;
00051 tree->tavl_compare = compare;
00052 tree->tavl_param = param;
00053 tree->tavl_alloc = allocator;
00054 tree->tavl_count = 0;
00055
00056 return tree;
00057 }
00058
00059
00060
00061 void *
00062 tavl_find (const struct tavl_table *tree, const void *item)
00063 {
00064 const struct tavl_node *p;
00065
00066 assert (tree != NULL && item != NULL);
00067
00068 p = tree->tavl_root;
00069 if (p == NULL)
00070 return NULL;
00071
00072 for (;;)
00073 {
00074 int cmp, dir;
00075
00076 cmp = tree->tavl_compare (item, p->tavl_data, tree->tavl_param);
00077 if (cmp == 0)
00078 return p->tavl_data;
00079
00080 dir = cmp > 0;
00081 if (p->tavl_tag[dir] == TAVL_CHILD)
00082 p = p->tavl_link[dir];
00083 else
00084 return NULL;
00085 }
00086 }
00087
00088
00089
00090
00091
00092 void **
00093 tavl_probe (struct tavl_table *tree, void *item)
00094 {
00095 struct tavl_node *y, *z;
00096 struct tavl_node *p, *q;
00097 struct tavl_node *n;
00098 struct tavl_node *w;
00099 int dir;
00100
00101 unsigned char da[TAVL_MAX_HEIGHT];
00102 int k = 0;
00103
00104 assert (tree != NULL && item != NULL);
00105
00106 z = (struct tavl_node *) &tree->tavl_root;
00107 y = tree->tavl_root;
00108 if (y != NULL)
00109 {
00110 for (q = z, p = y; ; q = p, p = p->tavl_link[dir])
00111 {
00112 int cmp = tree->tavl_compare (item, p->tavl_data, tree->tavl_param);
00113 if (cmp == 0)
00114 return &p->tavl_data;
00115
00116 if (p->tavl_balance != 0)
00117 z = q, y = p, k = 0;
00118 da[k++] = dir = cmp > 0;
00119
00120 if (p->tavl_tag[dir] == TAVL_THREAD)
00121 break;
00122 }
00123 }
00124 else
00125 {
00126 p = z;
00127 dir = 0;
00128 }
00129
00130 n = tree->tavl_alloc->libavl_malloc (tree->tavl_alloc, sizeof *n);
00131 if (n == NULL)
00132 return NULL;
00133
00134 tree->tavl_count++;
00135 n->tavl_data = item;
00136 n->tavl_tag[0] = n->tavl_tag[1] = TAVL_THREAD;
00137 n->tavl_link[dir] = p->tavl_link[dir];
00138 if (tree->tavl_root != NULL)
00139 {
00140 p->tavl_tag[dir] = TAVL_CHILD;
00141 n->tavl_link[!dir] = p;
00142 }
00143 else
00144 n->tavl_link[1] = NULL;
00145 p->tavl_link[dir] = n;
00146 n->tavl_balance = 0;
00147 if (tree->tavl_root == n)
00148 return &n->tavl_data;
00149
00150 for (p = y, k = 0; p != n; p = p->tavl_link[da[k]], k++)
00151 if (da[k] == 0)
00152 p->tavl_balance--;
00153 else
00154 p->tavl_balance++;
00155
00156 if (y->tavl_balance == -2)
00157 {
00158 struct tavl_node *x = y->tavl_link[0];
00159 if (x->tavl_balance == -1)
00160 {
00161 w = x;
00162 if (x->tavl_tag[1] == TAVL_THREAD)
00163 {
00164 x->tavl_tag[1] = TAVL_CHILD;
00165 y->tavl_tag[0] = TAVL_THREAD;
00166 y->tavl_link[0] = x;
00167 }
00168 else
00169 y->tavl_link[0] = x->tavl_link[1];
00170 x->tavl_link[1] = y;
00171 x->tavl_balance = y->tavl_balance = 0;
00172 }
00173 else
00174 {
00175 assert (x->tavl_balance == +1);
00176 w = x->tavl_link[1];
00177 x->tavl_link[1] = w->tavl_link[0];
00178 w->tavl_link[0] = x;
00179 y->tavl_link[0] = w->tavl_link[1];
00180 w->tavl_link[1] = y;
00181 if (w->tavl_balance == -1)
00182 x->tavl_balance = 0, y->tavl_balance = +1;
00183 else if (w->tavl_balance == 0)
00184 x->tavl_balance = y->tavl_balance = 0;
00185 else
00186 x->tavl_balance = -1, y->tavl_balance = 0;
00187 w->tavl_balance = 0;
00188 if (w->tavl_tag[0] == TAVL_THREAD)
00189 {
00190 x->tavl_tag[1] = TAVL_THREAD;
00191 x->tavl_link[1] = w;
00192 w->tavl_tag[0] = TAVL_CHILD;
00193 }
00194 if (w->tavl_tag[1] == TAVL_THREAD)
00195 {
00196 y->tavl_tag[0] = TAVL_THREAD;
00197 y->tavl_link[0] = w;
00198 w->tavl_tag[1] = TAVL_CHILD;
00199 }
00200 }
00201 }
00202 else if (y->tavl_balance == +2)
00203 {
00204 struct tavl_node *x = y->tavl_link[1];
00205 if (x->tavl_balance == +1)
00206 {
00207 w = x;
00208 if (x->tavl_tag[0] == TAVL_THREAD)
00209 {
00210 x->tavl_tag[0] = TAVL_CHILD;
00211 y->tavl_tag[1] = TAVL_THREAD;
00212 y->tavl_link[1] = x;
00213 }
00214 else
00215 y->tavl_link[1] = x->tavl_link[0];
00216 x->tavl_link[0] = y;
00217 x->tavl_balance = y->tavl_balance = 0;
00218 }
00219 else
00220 {
00221 assert (x->tavl_balance == -1);
00222 w = x->tavl_link[0];
00223 x->tavl_link[0] = w->tavl_link[1];
00224 w->tavl_link[1] = x;
00225 y->tavl_link[1] = w->tavl_link[0];
00226 w->tavl_link[0] = y;
00227 if (w->tavl_balance == +1)
00228 x->tavl_balance = 0, y->tavl_balance = -1;
00229 else if (w->tavl_balance == 0)
00230 x->tavl_balance = y->tavl_balance = 0;
00231 else
00232 x->tavl_balance = +1, y->tavl_balance = 0;
00233 w->tavl_balance = 0;
00234 if (w->tavl_tag[0] == TAVL_THREAD)
00235 {
00236 y->tavl_tag[1] = TAVL_THREAD;
00237 y->tavl_link[1] = w;
00238 w->tavl_tag[0] = TAVL_CHILD;
00239 }
00240 if (w->tavl_tag[1] == TAVL_THREAD)
00241 {
00242 x->tavl_tag[0] = TAVL_THREAD;
00243 x->tavl_link[0] = w;
00244 w->tavl_tag[1] = TAVL_CHILD;
00245 }
00246 }
00247 }
00248 else
00249 return &n->tavl_data;
00250 z->tavl_link[y != z->tavl_link[0]] = w;
00251
00252 return &n->tavl_data;
00253 }
00254
00255
00256
00257
00258
00259 void *
00260 tavl_insert (struct tavl_table *table, void *item)
00261 {
00262 void **p = tavl_probe (table, item);
00263 return p == NULL || *p == item ? NULL : *p;
00264 }
00265
00266
00267
00268
00269
00270 void *
00271 tavl_replace (struct tavl_table *table, void *item)
00272 {
00273 void **p = tavl_probe (table, item);
00274 if (p == NULL || *p == item)
00275 return NULL;
00276 else
00277 {
00278 void *r = *p;
00279 *p = item;
00280 return r;
00281 }
00282 }
00283
00284
00285
00286 static struct tavl_node *
00287 find_parent (struct tavl_table *tree, struct tavl_node *node)
00288 {
00289 if (node != tree->tavl_root)
00290 {
00291 struct tavl_node *x, *y;
00292
00293 for (x = y = node; ; x = x->tavl_link[0], y = y->tavl_link[1])
00294 if (y->tavl_tag[1] == TAVL_THREAD)
00295 {
00296 struct tavl_node *p = y->tavl_link[1];
00297 if (p == NULL || p->tavl_link[0] != node)
00298 {
00299 while (x->tavl_tag[0] == TAVL_CHILD)
00300 x = x->tavl_link[0];
00301 p = x->tavl_link[0];
00302 }
00303 return p;
00304 }
00305 else if (x->tavl_tag[0] == TAVL_THREAD)
00306 {
00307 struct tavl_node *p = x->tavl_link[0];
00308 if (p == NULL || p->tavl_link[1] != node)
00309 {
00310 while (y->tavl_tag[1] == TAVL_CHILD)
00311 y = y->tavl_link[1];
00312 p = y->tavl_link[1];
00313 }
00314 return p;
00315 }
00316 }
00317 else
00318 return (struct tavl_node *) &tree->tavl_root;
00319 }
00320
00321
00322
00323 void *
00324 tavl_delete (struct tavl_table *tree, const void *item)
00325 {
00326 struct tavl_node *p;
00327 struct tavl_node *q;
00328 int dir;
00329 int cmp;
00330
00331 assert (tree != NULL && item != NULL);
00332
00333 if (tree->tavl_root == NULL)
00334 return NULL;
00335
00336 p = (struct tavl_node *) &tree->tavl_root;
00337 for (cmp = -1; cmp != 0;
00338 cmp = tree->tavl_compare (item, p->tavl_data, tree->tavl_param))
00339 {
00340 dir = cmp > 0;
00341
00342 q = p;
00343 if (p->tavl_tag[dir] == TAVL_THREAD)
00344 return NULL;
00345 p = p->tavl_link[dir];
00346 }
00347 item = p->tavl_data;
00348
00349 if (p->tavl_tag[1] == TAVL_THREAD)
00350 {
00351 if (p->tavl_tag[0] == TAVL_CHILD)
00352 {
00353 struct tavl_node *t = p->tavl_link[0];
00354 while (t->tavl_tag[1] == TAVL_CHILD)
00355 t = t->tavl_link[1];
00356 t->tavl_link[1] = p->tavl_link[1];
00357 q->tavl_link[dir] = p->tavl_link[0];
00358 }
00359 else
00360 {
00361 q->tavl_link[dir] = p->tavl_link[dir];
00362 if (q != (struct tavl_node *) &tree->tavl_root)
00363 q->tavl_tag[dir] = TAVL_THREAD;
00364 }
00365 }
00366 else
00367 {
00368 struct tavl_node *r = p->tavl_link[1];
00369 if (r->tavl_tag[0] == TAVL_THREAD)
00370 {
00371 r->tavl_link[0] = p->tavl_link[0];
00372 r->tavl_tag[0] = p->tavl_tag[0];
00373 if (r->tavl_tag[0] == TAVL_CHILD)
00374 {
00375 struct tavl_node *t = r->tavl_link[0];
00376 while (t->tavl_tag[1] == TAVL_CHILD)
00377 t = t->tavl_link[1];
00378 t->tavl_link[1] = r;
00379 }
00380 q->tavl_link[dir] = r;
00381 r->tavl_balance = p->tavl_balance;
00382 q = r;
00383 dir = 1;
00384 }
00385 else
00386 {
00387 struct tavl_node *s;
00388
00389 for (;;)
00390 {
00391 s = r->tavl_link[0];
00392 if (s->tavl_tag[0] == TAVL_THREAD)
00393 break;
00394
00395 r = s;
00396 }
00397
00398 if (s->tavl_tag[1] == TAVL_CHILD)
00399 r->tavl_link[0] = s->tavl_link[1];
00400 else
00401 {
00402 r->tavl_link[0] = s;
00403 r->tavl_tag[0] = TAVL_THREAD;
00404 }
00405
00406 s->tavl_link[0] = p->tavl_link[0];
00407 if (p->tavl_tag[0] == TAVL_CHILD)
00408 {
00409 struct tavl_node *t = p->tavl_link[0];
00410 while (t->tavl_tag[1] == TAVL_CHILD)
00411 t = t->tavl_link[1];
00412 t->tavl_link[1] = s;
00413
00414 s->tavl_tag[0] = TAVL_CHILD;
00415 }
00416
00417 s->tavl_link[1] = p->tavl_link[1];
00418 s->tavl_tag[1] = TAVL_CHILD;
00419
00420 q->tavl_link[dir] = s;
00421 s->tavl_balance = p->tavl_balance;
00422 q = r;
00423 dir = 0;
00424 }
00425 }
00426
00427 tree->tavl_alloc->libavl_free (tree->tavl_alloc, p);
00428
00429 while (q != (struct tavl_node *) &tree->tavl_root)
00430 {
00431 struct tavl_node *y = q;
00432
00433 q = find_parent (tree, y);
00434
00435 if (dir == 0)
00436 {
00437 dir = q->tavl_link[0] != y;
00438 y->tavl_balance++;
00439 if (y->tavl_balance == +1)
00440 break;
00441 else if (y->tavl_balance == +2)
00442 {
00443 struct tavl_node *x = y->tavl_link[1];
00444
00445 assert (x != NULL);
00446 if (x->tavl_balance == -1)
00447 {
00448 struct tavl_node *w;
00449
00450 assert (x->tavl_balance == -1);
00451 w = x->tavl_link[0];
00452 x->tavl_link[0] = w->tavl_link[1];
00453 w->tavl_link[1] = x;
00454 y->tavl_link[1] = w->tavl_link[0];
00455 w->tavl_link[0] = y;
00456 if (w->tavl_balance == +1)
00457 x->tavl_balance = 0, y->tavl_balance = -1;
00458 else if (w->tavl_balance == 0)
00459 x->tavl_balance = y->tavl_balance = 0;
00460 else
00461 x->tavl_balance = +1, y->tavl_balance = 0;
00462 w->tavl_balance = 0;
00463 if (w->tavl_tag[0] == TAVL_THREAD)
00464 {
00465 y->tavl_tag[1] = TAVL_THREAD;
00466 y->tavl_link[1] = w;
00467 w->tavl_tag[0] = TAVL_CHILD;
00468 }
00469 if (w->tavl_tag[1] == TAVL_THREAD)
00470 {
00471 x->tavl_tag[0] = TAVL_THREAD;
00472 x->tavl_link[0] = w;
00473 w->tavl_tag[1] = TAVL_CHILD;
00474 }
00475 q->tavl_link[dir] = w;
00476 }
00477 else
00478 {
00479 q->tavl_link[dir] = x;
00480
00481 if (x->tavl_balance == 0)
00482 {
00483 y->tavl_link[1] = x->tavl_link[0];
00484 x->tavl_link[0] = y;
00485 x->tavl_balance = -1;
00486 y->tavl_balance = +1;
00487 break;
00488 }
00489 else
00490 {
00491 if (x->tavl_tag[0] == TAVL_CHILD)
00492 y->tavl_link[1] = x->tavl_link[0];
00493 else
00494 {
00495 y->tavl_tag[1] = TAVL_THREAD;
00496 x->tavl_tag[0] = TAVL_CHILD;
00497 }
00498 x->tavl_link[0] = y;
00499 y->tavl_balance = x->tavl_balance = 0;
00500 }
00501 }
00502 }
00503 }
00504 else
00505 {
00506 dir = q->tavl_link[0] != y;
00507 y->tavl_balance--;
00508 if (y->tavl_balance == -1)
00509 break;
00510 else if (y->tavl_balance == -2)
00511 {
00512 struct tavl_node *x = y->tavl_link[0];
00513 assert (x != NULL);
00514 if (x->tavl_balance == +1)
00515 {
00516 struct tavl_node *w;
00517
00518 assert (x->tavl_balance == +1);
00519 w = x->tavl_link[1];
00520 x->tavl_link[1] = w->tavl_link[0];
00521 w->tavl_link[0] = x;
00522 y->tavl_link[0] = w->tavl_link[1];
00523 w->tavl_link[1] = y;
00524 if (w->tavl_balance == -1)
00525 x->tavl_balance = 0, y->tavl_balance = +1;
00526 else if (w->tavl_balance == 0)
00527 x->tavl_balance = y->tavl_balance = 0;
00528 else
00529 x->tavl_balance = -1, y->tavl_balance = 0;
00530 w->tavl_balance = 0;
00531 if (w->tavl_tag[0] == TAVL_THREAD)
00532 {
00533 x->tavl_tag[1] = TAVL_THREAD;
00534 x->tavl_link[1] = w;
00535 w->tavl_tag[0] = TAVL_CHILD;
00536 }
00537 if (w->tavl_tag[1] == TAVL_THREAD)
00538 {
00539 y->tavl_tag[0] = TAVL_THREAD;
00540 y->tavl_link[0] = w;
00541 w->tavl_tag[1] = TAVL_CHILD;
00542 }
00543 q->tavl_link[dir] = w;
00544 }
00545 else
00546 {
00547 q->tavl_link[dir] = x;
00548
00549 if (x->tavl_balance == 0)
00550 {
00551 y->tavl_link[0] = x->tavl_link[1];
00552 x->tavl_link[1] = y;
00553 x->tavl_balance = +1;
00554 y->tavl_balance = -1;
00555 break;
00556 }
00557 else
00558 {
00559 if (x->tavl_tag[1] == TAVL_CHILD)
00560 y->tavl_link[0] = x->tavl_link[1];
00561 else
00562 {
00563 y->tavl_tag[0] = TAVL_THREAD;
00564 x->tavl_tag[1] = TAVL_CHILD;
00565 }
00566 x->tavl_link[1] = y;
00567 y->tavl_balance = x->tavl_balance = 0;
00568 }
00569 }
00570 }
00571 }
00572 }
00573
00574 tree->tavl_count--;
00575 return (void *) item;
00576 }
00577
00578
00579
00580 void
00581 tavl_t_init (struct tavl_traverser *trav, struct tavl_table *tree)
00582 {
00583 trav->tavl_table = tree;
00584 trav->tavl_node = NULL;
00585 }
00586
00587
00588
00589
00590 void *
00591 tavl_t_first (struct tavl_traverser *trav, struct tavl_table *tree)
00592 {
00593 assert (tree != NULL && trav != NULL);
00594
00595 trav->tavl_table = tree;
00596 trav->tavl_node = tree->tavl_root;
00597 if (trav->tavl_node != NULL)
00598 {
00599 while (trav->tavl_node->tavl_tag[0] == TAVL_CHILD)
00600 trav->tavl_node = trav->tavl_node->tavl_link[0];
00601 return trav->tavl_node->tavl_data;
00602 }
00603 else
00604 return NULL;
00605 }
00606
00607
00608
00609
00610 void *
00611 tavl_t_last (struct tavl_traverser *trav, struct tavl_table *tree)
00612 {
00613 assert (tree != NULL && trav != NULL);
00614
00615 trav->tavl_table = tree;
00616 trav->tavl_node = tree->tavl_root;
00617 if (trav->tavl_node != NULL)
00618 {
00619 while (trav->tavl_node->tavl_tag[1] == TAVL_CHILD)
00620 trav->tavl_node = trav->tavl_node->tavl_link[1];
00621 return trav->tavl_node->tavl_data;
00622 }
00623 else
00624 return NULL;
00625 }
00626
00627
00628
00629
00630
00631
00632 void *
00633 tavl_t_find (struct tavl_traverser *trav, struct tavl_table *tree, void *item)
00634 {
00635 struct tavl_node *p;
00636
00637 assert (trav != NULL && tree != NULL && item != NULL);
00638
00639 trav->tavl_table = tree;
00640 trav->tavl_node = NULL;
00641
00642 p = tree->tavl_root;
00643 if (p == NULL)
00644 return NULL;
00645
00646 for (;;)
00647 {
00648 int cmp, dir;
00649
00650 cmp = tree->tavl_compare (item, p->tavl_data, tree->tavl_param);
00651 if (cmp == 0)
00652 {
00653 trav->tavl_node = p;
00654 return p->tavl_data;
00655 }
00656
00657 dir = cmp > 0;
00658 if (p->tavl_tag[dir] == TAVL_CHILD)
00659 p = p->tavl_link[dir];
00660 else
00661 return NULL;
00662 }
00663 }
00664
00665
00666
00667
00668
00669
00670
00671
00672 void *
00673 tavl_t_insert (struct tavl_traverser *trav,
00674 struct tavl_table *tree, void *item)
00675 {
00676 void **p;
00677
00678 assert (trav != NULL && tree != NULL && item != NULL);
00679
00680 p = tavl_probe (tree, item);
00681 if (p != NULL)
00682 {
00683 trav->tavl_table = tree;
00684 trav->tavl_node =
00685 ((struct tavl_node *)
00686 ((char *) p - offsetof (struct tavl_node, tavl_data)));
00687 return *p;
00688 }
00689 else
00690 {
00691 tavl_t_init (trav, tree);
00692 return NULL;
00693 }
00694 }
00695
00696
00697 void *
00698 tavl_t_copy (struct tavl_traverser *trav, const struct tavl_traverser *src)
00699 {
00700 assert (trav != NULL && src != NULL);
00701
00702 trav->tavl_table = src->tavl_table;
00703 trav->tavl_node = src->tavl_node;
00704
00705 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
00706 }
00707
00708
00709
00710
00711 void *
00712 tavl_t_next (struct tavl_traverser *trav)
00713 {
00714 assert (trav != NULL);
00715
00716 if (trav->tavl_node == NULL)
00717 return tavl_t_first (trav, trav->tavl_table);
00718 else if (trav->tavl_node->tavl_tag[1] == TAVL_THREAD)
00719 {
00720 trav->tavl_node = trav->tavl_node->tavl_link[1];
00721 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
00722 }
00723 else
00724 {
00725 trav->tavl_node = trav->tavl_node->tavl_link[1];
00726 while (trav->tavl_node->tavl_tag[0] == TAVL_CHILD)
00727 trav->tavl_node = trav->tavl_node->tavl_link[0];
00728 return trav->tavl_node->tavl_data;
00729 }
00730 }
00731
00732
00733
00734
00735 void *
00736 tavl_t_prev (struct tavl_traverser *trav)
00737 {
00738 assert (trav != NULL);
00739
00740 if (trav->tavl_node == NULL)
00741 return tavl_t_last (trav, trav->tavl_table);
00742 else if (trav->tavl_node->tavl_tag[0] == TAVL_THREAD)
00743 {
00744 trav->tavl_node = trav->tavl_node->tavl_link[0];
00745 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
00746 }
00747 else
00748 {
00749 trav->tavl_node = trav->tavl_node->tavl_link[0];
00750 while (trav->tavl_node->tavl_tag[1] == TAVL_CHILD)
00751 trav->tavl_node = trav->tavl_node->tavl_link[1];
00752 return trav->tavl_node->tavl_data;
00753 }
00754 }
00755
00756
00757 void *
00758 tavl_t_cur (struct tavl_traverser *trav)
00759 {
00760 assert (trav != NULL);
00761
00762 return trav->tavl_node != NULL ? trav->tavl_node->tavl_data : NULL;
00763 }
00764
00765
00766
00767
00768 void *
00769 tavl_t_replace (struct tavl_traverser *trav, void *new)
00770 {
00771 struct tavl_node *old;
00772
00773 assert (trav != NULL && trav->tavl_node != NULL && new != NULL);
00774 old = trav->tavl_node->tavl_data;
00775 trav->tavl_node->tavl_data = new;
00776 return old;
00777 }
00778
00779
00780
00781
00782
00783
00784
00785 static int
00786 copy_node (struct tavl_table *tree,
00787 struct tavl_node *dst, int dir,
00788 const struct tavl_node *src, tavl_copy_func *copy)
00789 {
00790 struct tavl_node *new =
00791 tree->tavl_alloc->libavl_malloc (tree->tavl_alloc, sizeof *new);
00792 if (new == NULL)
00793 return 0;
00794
00795 new->tavl_link[dir] = dst->tavl_link[dir];
00796 new->tavl_tag[dir] = TAVL_THREAD;
00797 new->tavl_link[!dir] = dst;
00798 new->tavl_tag[!dir] = TAVL_THREAD;
00799 dst->tavl_link[dir] = new;
00800 dst->tavl_tag[dir] = TAVL_CHILD;
00801
00802 new->tavl_balance = src->tavl_balance;
00803 if (copy == NULL)
00804 new->tavl_data = src->tavl_data;
00805 else
00806 {
00807 new->tavl_data = copy (src->tavl_data, tree->tavl_param);
00808 if (new->tavl_data == NULL)
00809 return 0;
00810 }
00811
00812 return 1;
00813 }
00814
00815 static void
00816 copy_error_recovery (struct tavl_node *p,
00817 struct tavl_table *new, tavl_item_func *destroy)
00818 {
00819 new->tavl_root = p;
00820 if (p != NULL)
00821 {
00822 while (p->tavl_tag[1] == TAVL_CHILD)
00823 p = p->tavl_link[1];
00824 p->tavl_link[1] = NULL;
00825 }
00826 tavl_destroy (new, destroy);
00827 }
00828
00829
00830
00831
00832
00833
00834
00835
00836
00837
00838 struct tavl_table *
00839 tavl_copy (const struct tavl_table *org, tavl_copy_func *copy,
00840 tavl_item_func *destroy, struct libavl_allocator *allocator)
00841 {
00842 struct tavl_table *new;
00843
00844 const struct tavl_node *p;
00845 struct tavl_node *q;
00846 struct tavl_node rp, rq;
00847
00848 assert (org != NULL);
00849 new = tavl_create (org->tavl_compare, org->tavl_param,
00850 allocator != NULL ? allocator : org->tavl_alloc);
00851 if (new == NULL)
00852 return NULL;
00853
00854 new->tavl_count = org->tavl_count;
00855 if (new->tavl_count == 0)
00856 return new;
00857
00858 p = &rp;
00859 rp.tavl_link[0] = org->tavl_root;
00860 rp.tavl_tag[0] = TAVL_CHILD;
00861
00862 q = &rq;
00863 rq.tavl_link[0] = NULL;
00864 rq.tavl_tag[0] = TAVL_THREAD;
00865
00866 for (;;)
00867 {
00868 if (p->tavl_tag[0] == TAVL_CHILD)
00869 {
00870 if (!copy_node (new, q, 0, p->tavl_link[0], copy))
00871 {
00872 copy_error_recovery (rq.tavl_link[0], new, destroy);
00873 return NULL;
00874 }
00875
00876 p = p->tavl_link[0];
00877 q = q->tavl_link[0];
00878 }
00879 else
00880 {
00881 while (p->tavl_tag[1] == TAVL_THREAD)
00882 {
00883 p = p->tavl_link[1];
00884 if (p == NULL)
00885 {
00886 q->tavl_link[1] = NULL;
00887 new->tavl_root = rq.tavl_link[0];
00888 return new;
00889 }
00890
00891 q = q->tavl_link[1];
00892 }
00893
00894 p = p->tavl_link[1];
00895 q = q->tavl_link[1];
00896 }
00897
00898 if (p->tavl_tag[1] == TAVL_CHILD)
00899 if (!copy_node (new, q, 1, p->tavl_link[1], copy))
00900 {
00901 copy_error_recovery (rq.tavl_link[0], new, destroy);
00902 return NULL;
00903 }
00904 }
00905 }
00906
00907
00908
00909 void
00910 tavl_destroy (struct tavl_table *tree, tavl_item_func *destroy)
00911 {
00912 struct tavl_node *p;
00913 struct tavl_node *n;
00914
00915 p = tree->tavl_root;
00916 if (p != NULL)
00917 while (p->tavl_tag[0] == TAVL_CHILD)
00918 p = p->tavl_link[0];
00919
00920 while (p != NULL)
00921 {
00922 n = p->tavl_link[1];
00923 if (p->tavl_tag[1] == TAVL_CHILD)
00924 while (n->tavl_tag[0] == TAVL_CHILD)
00925 n = n->tavl_link[0];
00926
00927 if (destroy != NULL && p->tavl_data != NULL)
00928 destroy (p->tavl_data, tree->tavl_param);
00929 tree->tavl_alloc->libavl_free (tree->tavl_alloc, p);
00930
00931 p = n;
00932 }
00933
00934 tree->tavl_alloc->libavl_free (tree->tavl_alloc, tree);
00935 }
00936
00937
00938
00939 void *
00940 tavl_malloc (struct libavl_allocator *allocator, size_t size)
00941 {
00942 assert (allocator != NULL && size > 0);
00943 return malloc (size);
00944 }
00945
00946
00947 void
00948 tavl_free (struct libavl_allocator *allocator, void *block)
00949 {
00950 assert (allocator != NULL && block != NULL);
00951 free (block);
00952 }
00953
00954
00955 struct libavl_allocator tavl_allocator_default =
00956 {
00957 tavl_malloc,
00958 tavl_free
00959 };
00960
00961 #undef NDEBUG
00962 #include <assert.h>
00963
00964
00965 void
00966 (tavl_assert_insert) (struct tavl_table *table, void *item)
00967 {
00968 void **p = tavl_probe (table, item);
00969 assert (p != NULL && *p == item);
00970 }
00971
00972
00973
00974 void *
00975 (tavl_assert_delete) (struct tavl_table *table, void *item)
00976 {
00977 void *p = tavl_delete (table, item);
00978 assert (p != NULL);
00979 return p;
00980 }
00981