contrib/apr/tables/apr_skiplist.c

   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
  28 typedef struct {
  29     apr_skiplistnode **data;
  30     size_t size, pos;
  31     apr_pool_t *p;
  32 } apr_skiplist_q;
  33
  34 struct 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
  52 struct 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
  63 static 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
  74 typedef struct {
  75     size_t size;
  76     apr_array_header_t *list;
  77 } memlist_t;
  78
  79 typedef struct {
  80     void *ptr;
  81     char inuse;
  82 } chunk_t;
  83
  84 APR_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
 132 APR_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
 155 static 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
 179 static APR_INLINE apr_skiplistnode *skiplist_qpop(apr_skiplist_q *q)
 180 {
 181     return (q->pos > 0) ? q->data[--q->pos] : NULL;
 182 }
 183
 184 static APR_INLINE void skiplist_qclear(apr_skiplist_q *q)
 185 {
 186     q->pos = 0;
 187 }
 188
 189 static 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
 203 static apr_status_t skiplist_put_node(apr_skiplist *sl, apr_skiplistnode *m)
 204 {
 205     return skiplist_qpush(&sl->nodes_q, m);
 206 }
 207
 208 static 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
 226 static 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
 233 static 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
 239 APR_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
 249 APR_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
 262 APR_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
 300 static 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
 336 static 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
 369 APR_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
 376 APR_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
 381 APR_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
 388 APR_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
 395 APR_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
 403 APR_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
 412 APR_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
 421 APR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *iter)
 422 {
 423     return (iter) ? iter->data : NULL;
 424 }
 425
 426 /* forward declared */
 427 static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m,
 428                             apr_skiplist_freefunc myfree);
 429
 430 static 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
 439 static 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
 580 APR_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
 589 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
 590 {
 591     return apr_skiplist_insert_compare(sl, data, sl->compare);
 592 }
 593
 594 APR_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
 603 APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist *sl, void *data)
 604 {
 605     return apr_skiplist_add_compare(sl, data, sl->compare);
 606 }
 607
 608 APR_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
 618 APR_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
 625 void 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
 643 static 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
 688 APR_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
 705 APR_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
 734 APR_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
 739 APR_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
 766 APR_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
 778 APR_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
 788 APR_DECLARE(size_t) apr_skiplist_size(const apr_skiplist *sl)
 789 {
 790     return sl->size;
 791 }
 792
 793 APR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl)
 794 {
 795     return skiplist_height(sl);
 796 }
 797
 798 APR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl)
 799 {
 800     return sl->preheight;
 801 }
 802
 803 APR_DECLARE(void) apr_skiplist_set_preheight(apr_skiplist *sl, int to)
 804 {
 805     sl->preheight = (to > 0) ? to : 0;
 806 }
 807
 808 static void skiplisti_destroy(void *vsl)
 809 {
 810     apr_skiplist_destroy(vsl, NULL);
 811 }
 812
 813 APR_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
 827 APR_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 }