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