1/* Licensed to the Apache Software Foundation (ASF) under one or more 2 * contributor license agreements. See the NOTICE file distributed with 3 * this work for additional information regarding copyright ownership. 4 * The ASF licenses this file to You under the Apache License, Version 2.0 5 * (the "License"); you may not use this file except in compliance with 6 * the License. You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17/* 18 * Modified to use APR and APR pools. 19 * TODO: Is malloc() better? Will long running skiplists grow too much? 20 * Keep the skiplist_alloc() and skiplist_free() until we know 21 * Yeah, if using pools it means some bogus cycles for checks 22 * (and an useless function call for skiplist_free) which we 23 * can removed if/when needed. 24 */ 25 26#include "apr_skiplist.h" 27 28typedef struct { 29 apr_skiplistnode **data; 30 size_t size, pos; 31 apr_pool_t *p; 32} apr_skiplist_q; 33 34struct apr_skiplist { 35 apr_skiplist_compare compare; 36 apr_skiplist_compare comparek; 37 int height; 38 int preheight; 39 size_t size; 40 apr_skiplistnode *top; 41 apr_skiplistnode *bottom; 42 /* These two are needed for appending */ 43 apr_skiplistnode *topend; 44 apr_skiplistnode *bottomend; 45 apr_skiplist *index; 46 apr_array_header_t *memlist; 47 apr_skiplist_q nodes_q, 48 stack_q; 49 apr_pool_t *pool; 50}; 51 52struct apr_skiplistnode { 53 void *data; 54 apr_skiplistnode *next; 55 apr_skiplistnode *prev; 56 apr_skiplistnode *down; 57 apr_skiplistnode *up; 58 apr_skiplistnode *previndex; 59 apr_skiplistnode *nextindex; 60 apr_skiplist *sl; 61}; 62 63static int get_b_rand(void) 64{ 65 static int ph = 32; /* More bits than we will ever use */ 66 static int randseq; 67 if (ph > 31) { /* Num bits in return of rand() */ 68 ph = 0; 69 randseq = rand(); 70 } 71 return randseq & (1 << ph++); 72} 73 74typedef struct { 75 size_t size; 76 apr_array_header_t *list; 77} memlist_t; 78 79typedef struct { 80 void *ptr; 81 char inuse; 82} chunk_t; 83 84APR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size) 85{ 86 if (sl->pool) { 87 void *ptr; 88 int found_size = 0; 89 int i; 90 chunk_t *newchunk; 91 memlist_t *memlist = (memlist_t *)sl->memlist->elts; 92 for (i = 0; i < sl->memlist->nelts; i++) { 93 if (memlist->size == size) { 94 int j; 95 chunk_t *chunk = (chunk_t *)memlist->list->elts; 96 found_size = 1; 97 for (j = 0; j < memlist->list->nelts; j++) { 98 if (!chunk->inuse) { 99 chunk->inuse = 1; 100 return chunk->ptr; 101 } 102 chunk++; 103 } 104 break; /* no free of this size; punt */ 105 } 106 memlist++; 107 } 108 /* no free chunks */ 109 ptr = apr_palloc(sl->pool, size); 110 if (!ptr) { 111 return ptr; 112 } 113 /* 114 * is this a new sized chunk? If so, we need to create a new 115 * array of them. Otherwise, re-use what we already have. 116 */ 117 if (!found_size) { 118 memlist = apr_array_push(sl->memlist); 119 memlist->size = size; 120 memlist->list = apr_array_make(sl->pool, 20, sizeof(chunk_t)); 121 } 122 newchunk = apr_array_push(memlist->list); 123 newchunk->ptr = ptr; 124 newchunk->inuse = 1; 125 return ptr; 126 } 127 else { 128 return malloc(size); 129 } 130} 131 132APR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem) 133{ 134 if (!sl->pool) { 135 free(mem); 136 } 137 else { 138 int i; 139 memlist_t *memlist = (memlist_t *)sl->memlist->elts; 140 for (i = 0; i < sl->memlist->nelts; i++) { 141 int j; 142 chunk_t *chunk = (chunk_t *)memlist->list->elts; 143 for (j = 0; j < memlist->list->nelts; j++) { 144 if (chunk->ptr == mem) { 145 chunk->inuse = 0; 146 return; 147 } 148 chunk++; 149 } 150 memlist++; 151 } 152 } 153} 154 155static apr_status_t skiplist_qpush(apr_skiplist_q *q, apr_skiplistnode *m) 156{ 157 if (q->pos >= q->size) { 158 apr_skiplistnode **data; 159 size_t size = (q->pos) ? q->pos * 2 : 32; 160 if (q->p) { 161 data = apr_palloc(q->p, size * sizeof(*data)); 162 if (data) { 163 memcpy(data, q->data, q->pos * sizeof(*data)); 164 } 165 } 166 else { 167 data = realloc(q->data, size * sizeof(*data)); 168 } 169 if (!data) { 170 return APR_ENOMEM; 171 } 172 q->data = data; 173 q->size = size; 174 } 175 q->data[q->pos++] = m; 176 return APR_SUCCESS; 177} 178 179static APR_INLINE apr_skiplistnode *skiplist_qpop(apr_skiplist_q *q) 180{ 181 return (q->pos > 0) ? q->data[--q->pos] : NULL; 182} 183 184static APR_INLINE void skiplist_qclear(apr_skiplist_q *q) 185{ 186 q->pos = 0; 187} 188 189static apr_skiplistnode *skiplist_new_node(apr_skiplist *sl) 190{ 191 apr_skiplistnode *m = skiplist_qpop(&sl->nodes_q); 192 if (!m) { 193 if (sl->pool) { 194 m = apr_palloc(sl->pool, sizeof *m); 195 } 196 else { 197 m = malloc(sizeof *m); 198 } 199 } 200 return m; 201} 202 203static apr_status_t skiplist_put_node(apr_skiplist *sl, apr_skiplistnode *m) 204{ 205 return skiplist_qpush(&sl->nodes_q, m); 206} 207 208static apr_status_t skiplisti_init(apr_skiplist **s, apr_pool_t *p) 209{ 210 apr_skiplist *sl; 211 if (p) { 212 sl = apr_pcalloc(p, sizeof(apr_skiplist)); 213 sl->memlist = apr_array_make(p, 20, sizeof(memlist_t)); 214 sl->pool = sl->nodes_q.p = sl->stack_q.p = p; 215 } 216 else { 217 sl = calloc(1, sizeof(apr_skiplist)); 218 if (!sl) { 219 return APR_ENOMEM; 220 } 221 } 222 *s = sl; 223 return APR_SUCCESS; 224} 225 226static int indexing_comp(void *a, void *b) 227{ 228 void *ac = (void *) (((apr_skiplist *) a)->compare); 229 void *bc = (void *) (((apr_skiplist *) b)->compare); 230 return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0)); 231} 232 233static int indexing_compk(void *ac, void *b) 234{ 235 void *bc = (void *) (((apr_skiplist *) b)->compare); 236 return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0)); 237} 238 239APR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **s, apr_pool_t *p) 240{ 241 apr_skiplist *sl; 242 skiplisti_init(s, p); 243 sl = *s; 244 skiplisti_init(&(sl->index), p); 245 apr_skiplist_set_compare(sl->index, indexing_comp, indexing_compk); 246 return APR_SUCCESS; 247} 248 249APR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl, 250 apr_skiplist_compare comp, 251 apr_skiplist_compare compk) 252{ 253 if (sl->compare && sl->comparek) { 254 apr_skiplist_add_index(sl, comp, compk); 255 } 256 else { 257 sl->compare = comp; 258 sl->comparek = compk; 259 } 260} 261 262APR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl, 263 apr_skiplist_compare comp, 264 apr_skiplist_compare compk) 265{ 266 apr_skiplistnode *m; 267 apr_skiplist *ni; 268 int icount = 0; 269 apr_skiplist_find(sl->index, (void *)comp, &m); 270 if (m) { 271 return; /* Index already there! */ 272 } 273 skiplisti_init(&ni, sl->pool); 274 apr_skiplist_set_compare(ni, comp, compk); 275 /* Build the new index... This can be expensive! */ 276 m = apr_skiplist_insert(sl->index, ni); 277 while (m->prev) { 278 m = m->prev; 279 icount++; 280 } 281 for (m = apr_skiplist_getlist(sl); m; apr_skiplist_next(sl, &m)) { 282 int j = icount - 1; 283 apr_skiplistnode *nsln; 284 nsln = apr_skiplist_insert(ni, m->data); 285 /* skip from main index down list */ 286 while (j > 0) { 287 m = m->nextindex; 288 j--; 289 } 290 /* insert this node in the indexlist after m */ 291 nsln->nextindex = m->nextindex; 292 if (m->nextindex) { 293 m->nextindex->previndex = nsln; 294 } 295 nsln->previndex = m; 296 m->nextindex = nsln; 297 } 298} 299 300static int skiplisti_find_compare(apr_skiplist *sl, void *data, 301 apr_skiplistnode **ret, 302 apr_skiplist_compare comp, 303 int last) 304{ 305 int count = 0; 306 apr_skiplistnode *m, *found = NULL; 307 for (m = sl->top; m; count++) { 308 if (m->next) { 309 int compared = comp(data, m->next->data); 310 if (compared == 0) { 311 found = m = m->next; 312 if (!last) { 313 break; 314 } 315 continue; 316 } 317 if (compared > 0) { 318 m = m->next; 319 continue; 320 } 321 } 322 m = m->down; 323 } 324 if (found) { 325 while (found->down) { 326 found = found->down; 327 } 328 *ret = found; 329 } 330 else { 331 *ret = NULL; 332 } 333 return count; 334} 335 336static void *find_compare(apr_skiplist *sli, void *data, 337 apr_skiplistnode **iter, 338 apr_skiplist_compare comp, 339 int last) 340{ 341 apr_skiplistnode *m; 342 apr_skiplist *sl; 343 if (!comp) { 344 if (iter) { 345 *iter = NULL; 346 } 347 return NULL; 348 } 349 if (comp == sli->compare || !sli->index) { 350 sl = sli; 351 } 352 else { 353 apr_skiplist_find(sli->index, (void *)comp, &m); 354 if (!m) { 355 if (iter) { 356 *iter = NULL; 357 } 358 return NULL; 359 } 360 sl = (apr_skiplist *) m->data; 361 } 362 skiplisti_find_compare(sl, data, &m, sl->comparek, last); 363 if (iter) { 364 *iter = m; 365 } 366 return (m) ? m->data : NULL; 367} 368 369APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl, void *data, 370 apr_skiplistnode **iter, 371 apr_skiplist_compare comp) 372{ 373 return find_compare(sl, data, iter, comp, 0); 374} 375 376APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter) 377{ 378 return find_compare(sl, data, iter, sl->compare, 0); 379} 380 381APR_DECLARE(void *) apr_skiplist_last_compare(apr_skiplist *sl, void *data, 382 apr_skiplistnode **iter, 383 apr_skiplist_compare comp) 384{ 385 return find_compare(sl, data, iter, comp, 1); 386} 387 388APR_DECLARE(void *) apr_skiplist_last(apr_skiplist *sl, void *data, 389 apr_skiplistnode **iter) 390{ 391 return find_compare(sl, data, iter, sl->compare, 1); 392} 393 394 395APR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl) 396{ 397 if (!sl->bottom) { 398 return NULL; 399 } 400 return sl->bottom->next; 401} 402 403APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter) 404{ 405 if (!*iter) { 406 return NULL; 407 } 408 *iter = (*iter)->next; 409 return (*iter) ? ((*iter)->data) : NULL; 410} 411 412APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter) 413{ 414 if (!*iter) { 415 return NULL; 416 } 417 *iter = (*iter)->prev; 418 return (*iter) ? ((*iter)->data) : NULL; 419} 420 421APR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *iter) 422{ 423 return (iter) ? iter->data : NULL; 424} 425 426/* forward declared */ 427static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, 428 apr_skiplist_freefunc myfree); 429 430static APR_INLINE int skiplist_height(const apr_skiplist *sl) 431{ 432 /* Skiplists (even empty) always have a top node, although this 433 * implementation defers its creation until the first insert, or 434 * deletes it with the last remove. We want the real height here. 435 */ 436 return sl->height ? sl->height : 1; 437} 438 439static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data, 440 apr_skiplist_compare comp, int add, 441 apr_skiplist_freefunc myfree) 442{ 443 apr_skiplistnode *m, *p, *tmp, *ret = NULL; 444 int ch, top_nh, nh = 1; 445 446 ch = skiplist_height(sl); 447 if (sl->preheight) { 448 while (nh < sl->preheight && get_b_rand()) { 449 nh++; 450 } 451 } 452 else { 453 while (nh <= ch && get_b_rand()) { 454 nh++; 455 } 456 } 457 top_nh = nh; 458 459 /* Now we have in nh the height at which we wish to insert our new node, 460 * and in ch the current height: don't create skip paths to the inserted 461 * element until the walk down through the tree (which decrements ch) 462 * reaches nh. From there, any walk down pushes the current node on a 463 * stack (the node(s) after which we would insert) to pop back through 464 * for insertion later. 465 */ 466 m = sl->top; 467 while (m) { 468 /* 469 * To maintain stability, dups (compared == 0) must be added 470 * AFTER each other. 471 */ 472 if (m->next) { 473 int compared = comp(data, m->next->data); 474 if (compared == 0) { 475 if (!add) { 476 /* Keep the existing element(s) */ 477 skiplist_qclear(&sl->stack_q); 478 return NULL; 479 } 480 if (add < 0) { 481 /* Remove this element and continue with the next node 482 * or the new top if the current one is also removed. 483 */ 484 apr_skiplistnode *top = sl->top; 485 skiplisti_remove(sl, m->next, myfree); 486 if (top != sl->top) { 487 m = sl->top; 488 skiplist_qclear(&sl->stack_q); 489 ch = skiplist_height(sl); 490 nh = top_nh; 491 } 492 continue; 493 } 494 } 495 if (compared >= 0) { 496 m = m->next; 497 continue; 498 } 499 } 500 if (ch <= nh) { 501 /* push on stack */ 502 skiplist_qpush(&sl->stack_q, m); 503 } 504 m = m->down; 505 ch--; 506 } 507 /* Pop the stack and insert nodes */ 508 p = NULL; 509 while ((m = skiplist_qpop(&sl->stack_q))) { 510 tmp = skiplist_new_node(sl); 511 tmp->next = m->next; 512 if (m->next) { 513 m->next->prev = tmp; 514 } 515 m->next = tmp; 516 tmp->prev = m; 517 tmp->up = NULL; 518 tmp->nextindex = tmp->previndex = NULL; 519 tmp->down = p; 520 if (p) { 521 p->up = tmp; 522 } 523 else { 524 /* This sets ret to the bottom-most node we are inserting */ 525 ret = tmp; 526 } 527 tmp->data = data; 528 tmp->sl = sl; 529 p = tmp; 530 } 531 532 /* Now we are sure the node is inserted, grow our tree to 'nh' tall */ 533 for (; sl->height < nh; sl->height++) { 534 m = skiplist_new_node(sl); 535 tmp = skiplist_new_node(sl); 536 m->up = m->prev = m->nextindex = m->previndex = NULL; 537 m->next = tmp; 538 m->down = sl->top; 539 m->data = NULL; 540 m->sl = sl; 541 if (sl->top) { 542 sl->top->up = m; 543 } 544 else { 545 sl->bottom = sl->bottomend = m; 546 } 547 sl->top = sl->topend = tmp->prev = m; 548 tmp->up = tmp->next = tmp->nextindex = tmp->previndex = NULL; 549 tmp->down = p; 550 tmp->data = data; 551 tmp->sl = sl; 552 if (p) { 553 p->up = tmp; 554 } 555 else { 556 /* This sets ret to the bottom-most node we are inserting */ 557 ret = tmp; 558 } 559 p = tmp; 560 } 561 if (sl->index != NULL) { 562 /* 563 * this is a external insertion, we must insert into each index as 564 * well 565 */ 566 apr_skiplistnode *ni, *li; 567 li = ret; 568 for (p = apr_skiplist_getlist(sl->index); p; apr_skiplist_next(sl->index, &p)) { 569 apr_skiplist *sli = (apr_skiplist *)p->data; 570 ni = insert_compare(sli, ret->data, sli->compare, 1, NULL); 571 li->nextindex = ni; 572 ni->previndex = li; 573 li = ni; 574 } 575 } 576 sl->size++; 577 return ret; 578} 579 580APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data, 581 apr_skiplist_compare comp) 582{ 583 if (!comp) { 584 return NULL; 585 } 586 return insert_compare(sl, data, comp, 0, NULL); 587} 588 589APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data) 590{ 591 return apr_skiplist_insert_compare(sl, data, sl->compare); 592} 593 594APR_DECLARE(apr_skiplistnode *) apr_skiplist_add_compare(apr_skiplist *sl, void *data, 595 apr_skiplist_compare comp) 596{ 597 if (!comp) { 598 return NULL; 599 } 600 return insert_compare(sl, data, comp, 1, NULL); 601} 602 603APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist *sl, void *data) 604{ 605 return apr_skiplist_add_compare(sl, data, sl->compare); 606} 607 608APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace_compare(apr_skiplist *sl, 609 void *data, apr_skiplist_freefunc myfree, 610 apr_skiplist_compare comp) 611{ 612 if (!comp) { 613 return NULL; 614 } 615 return insert_compare(sl, data, comp, -1, myfree); 616} 617 618APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace(apr_skiplist *sl, 619 void *data, apr_skiplist_freefunc myfree) 620{ 621 return apr_skiplist_replace_compare(sl, data, myfree, sl->compare); 622} 623 624#if 0 625void skiplist_print_struct(apr_skiplist * sl, char *prefix) 626{ 627 apr_skiplistnode *p, *q; 628 fprintf(stderr, "Skiplist Structure (height: %d)\n", sl->height); 629 p = sl->bottom; 630 while (p) { 631 q = p; 632 fprintf(stderr, prefix); 633 while (q) { 634 fprintf(stderr, "%p ", q->data); 635 q = q->up; 636 } 637 fprintf(stderr, "\n"); 638 p = p->next; 639 } 640} 641#endif 642 643static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, 644 apr_skiplist_freefunc myfree) 645{ 646 apr_skiplistnode *p; 647 if (!m) { 648 return 0; 649 } 650 if (m->nextindex) { 651 skiplisti_remove(m->nextindex->sl, m->nextindex, NULL); 652 } 653 while (m->up) { 654 m = m->up; 655 } 656 do { 657 p = m; 658 /* take me out of the list */ 659 p->prev->next = p->next; 660 if (p->next) { 661 p->next->prev = p->prev; 662 } 663 m = m->down; 664 /* This only frees the actual data in the bottom one */ 665 if (!m && myfree && p->data) { 666 myfree(p->data); 667 } 668 skiplist_put_node(sl, p); 669 } while (m); 670 sl->size--; 671 while (sl->top && sl->top->next == NULL) { 672 /* While the row is empty and we are not on the bottom row */ 673 p = sl->top; 674 sl->top = sl->top->down;/* Move top down one */ 675 if (sl->top) { 676 sl->top->up = NULL; /* Make it think its the top */ 677 } 678 skiplist_put_node(sl, p); 679 sl->height--; 680 } 681 if (!sl->top) { 682 sl->bottom = sl->bottomend = NULL; 683 sl->topend = NULL; 684 } 685 return skiplist_height(sl); 686} 687 688APR_DECLARE(int) apr_skiplist_remove_node(apr_skiplist *sl, 689 apr_skiplistnode *iter, 690 apr_skiplist_freefunc myfree) 691{ 692 apr_skiplistnode *m = iter; 693 if (!m) { 694 return 0; 695 } 696 while (m->down) { 697 m = m->down; 698 } 699 while (m->previndex) { 700 m = m->previndex; 701 } 702 return skiplisti_remove(sl, m, myfree); 703} 704 705APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli, 706 void *data, 707 apr_skiplist_freefunc myfree, apr_skiplist_compare comp) 708{ 709 apr_skiplistnode *m; 710 apr_skiplist *sl; 711 if (!comp) { 712 return 0; 713 } 714 if (comp == sli->comparek || !sli->index) { 715 sl = sli; 716 } 717 else { 718 apr_skiplist_find(sli->index, (void *)comp, &m); 719 if (!m) { 720 return 0; 721 } 722 sl = (apr_skiplist *) m->data; 723 } 724 skiplisti_find_compare(sl, data, &m, comp, 0); 725 if (!m) { 726 return 0; 727 } 728 while (m->previndex) { 729 m = m->previndex; 730 } 731 return skiplisti_remove(sl, m, myfree); 732} 733 734APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree) 735{ 736 return apr_skiplist_remove_compare(sl, data, myfree, sl->comparek); 737} 738 739APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree) 740{ 741 /* 742 * This must remove even the place holder nodes (bottom though top) 743 * because we specify in the API that one can free the Skiplist after 744 * making this call without memory leaks 745 */ 746 apr_skiplistnode *m, *p, *u; 747 m = sl->bottom; 748 while (m) { 749 p = m->next; 750 if (myfree && p && p->data) { 751 myfree(p->data); 752 } 753 do { 754 u = m->up; 755 skiplist_put_node(sl, m); 756 m = u; 757 } while (m); 758 m = p; 759 } 760 sl->top = sl->bottom = NULL; 761 sl->topend = sl->bottomend = NULL; 762 sl->height = 0; 763 sl->size = 0; 764} 765 766APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *a, apr_skiplist_freefunc myfree) 767{ 768 apr_skiplistnode *sln; 769 void *data = NULL; 770 sln = apr_skiplist_getlist(a); 771 if (sln) { 772 data = sln->data; 773 skiplisti_remove(a, sln, myfree); 774 } 775 return data; 776} 777 778APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *a) 779{ 780 apr_skiplistnode *sln; 781 sln = apr_skiplist_getlist(a); 782 if (sln) { 783 return sln->data; 784 } 785 return NULL; 786} 787 788APR_DECLARE(size_t) apr_skiplist_size(const apr_skiplist *sl) 789{ 790 return sl->size; 791} 792 793APR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl) 794{ 795 return skiplist_height(sl); 796} 797 798APR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl) 799{ 800 return sl->preheight; 801} 802 803APR_DECLARE(void) apr_skiplist_set_preheight(apr_skiplist *sl, int to) 804{ 805 sl->preheight = (to > 0) ? to : 0; 806} 807 808static void skiplisti_destroy(void *vsl) 809{ 810 apr_skiplist_destroy(vsl, NULL); 811} 812 813APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree) 814{ 815 while (apr_skiplist_pop(sl->index, skiplisti_destroy) != NULL) 816 ; 817 apr_skiplist_remove_all(sl, myfree); 818 if (!sl->pool) { 819 while (sl->nodes_q.pos) 820 free(sl->nodes_q.data[--sl->nodes_q.pos]); 821 free(sl->nodes_q.data); 822 free(sl->stack_q.data); 823 free(sl); 824 } 825} 826 827APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2) 828{ 829 /* Check integrity! */ 830 apr_skiplist temp; 831 struct apr_skiplistnode *b2; 832 if (sl1->bottomend == NULL || sl1->bottomend->prev == NULL) { 833 apr_skiplist_remove_all(sl1, NULL); 834 temp = *sl1; 835 *sl1 = *sl2; 836 *sl2 = temp; 837 /* swap them so that sl2 can be freed normally upon return. */ 838 return sl1; 839 } 840 if(sl2->bottom == NULL || sl2->bottom->next == NULL) { 841 apr_skiplist_remove_all(sl2, NULL); 842 return sl1; 843 } 844 /* This is what makes it brute force... Just insert :/ */ 845 b2 = apr_skiplist_getlist(sl2); 846 while (b2) { 847 apr_skiplist_insert(sl1, b2->data); 848 apr_skiplist_next(sl2, &b2); 849 } 850 apr_skiplist_remove_all(sl2, NULL); 851 return sl1; 852} 853