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