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_free_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 {
 304     int count = 0;
 305     apr_skiplistnode *m;
 306     m = sl->top;
 307     while (m) {
 308         if (m->next) {
 309             int compared = comp(data, m->next->data);
 310             if (compared == 0) {
 311                 m = m->next;
 312                 while (m->down) {
 313                     m = m->down;
 314                 }
 315                 *ret = m;
 316                 return count;
 317             }
 318             if (compared > 0) {
 319                 m = m->next;
 320                 count++;
 321                 continue;
 322             }
 323         }
 324         m = m->down;
 325         count++;
 326     }
 327     *ret = NULL;
 328     return count;
 329 }
 330
 331 APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sli, void *data,
 332                                apr_skiplistnode **iter,
 333                                apr_skiplist_compare comp)
 334 {
 335     apr_skiplistnode *m;
 336     apr_skiplist *sl;
 337     if (!comp) {
 338         if (iter) {
 339             *iter = NULL;
 340         }
 341         return NULL;
 342     }
 343     if (comp == sli->compare || !sli->index) {
 344         sl = sli;
 345     }
 346     else {
 347         apr_skiplist_find(sli->index, (void *)comp, &m);
 348         if (!m) {
 349             if (iter) {
 350                 *iter = NULL;
 351             }
 352             return NULL;
 353         }
 354         sl = (apr_skiplist *) m->data;
 355     }
 356     skiplisti_find_compare(sl, data, &m, sl->comparek);
 357     if (iter) {
 358         *iter = m;
 359     }
 360     return (m) ? m->data : NULL;
 361 }
 362
 363 APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter)
 364 {
 365     return apr_skiplist_find_compare(sl, data, iter, sl->compare);
 366 }
 367
 368
 369 APR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl)
 370 {
 371     if (!sl->bottom) {
 372         return NULL;
 373     }
 374     return sl->bottom->next;
 375 }
 376
 377 APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter)
 378 {
 379     if (!*iter) {
 380         return NULL;
 381     }
 382     *iter = (*iter)->next;
 383     return (*iter) ? ((*iter)->data) : NULL;
 384 }
 385
 386 APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter)
 387 {
 388     if (!*iter) {
 389         return NULL;
 390     }
 391     *iter = (*iter)->prev;
 392     return (*iter) ? ((*iter)->data) : NULL;
 393 }
 394
 395 static APR_INLINE int skiplist_height(const apr_skiplist *sl)
 396 {
 397     /* Skiplists (even empty) always have a top node, although this
 398      * implementation defers its creation until the first insert, or
 399      * deletes it with the last remove. We want the real height here.
 400      */
 401     return sl->height ? sl->height : 1;
 402 }
 403
 404 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
 405                                       apr_skiplist_compare comp)
 406 {
 407     apr_skiplistnode *m, *p, *tmp, *ret = NULL;
 408     int ch, nh = 1;
 409
 410     if (!comp) {
 411         return NULL;
 412     }
 413
 414     ch = skiplist_height(sl);
 415     if (sl->preheight) {
 416         while (nh < sl->preheight && get_b_rand()) {
 417             nh++;
 418         }
 419     }
 420     else {
 421         while (nh <= ch && get_b_rand()) {
 422             nh++;
 423         }
 424     }
 425
 426     /* Now we have in nh the height at which we wish to insert our new node,
 427      * and in ch the current height: don't create skip paths to the inserted
 428      * element until the walk down through the tree (which decrements ch)
 429      * reaches nh. From there, any walk down pushes the current node on a
 430      * stack (the node(s) after which we would insert) to pop back through
 431      * for insertion later.
 432      */
 433     m = sl->top;
 434     while (m) {
 435         if (m->next) {
 436             int compared = comp(data, m->next->data);
 437             if (compared == 0) {
 438                 /* Keep the existing element(s) */
 439                 skiplist_qclear(&sl->stack_q);
 440                 return NULL;
 441             }
 442             if (compared > 0) {
 443                 m = m->next;
 444                 continue;
 445             }
 446         }
 447         if (ch <= nh) {
 448             /* push on stack */
 449             skiplist_qpush(&sl->stack_q, m);
 450         }
 451         m = m->down;
 452         ch--;
 453     }
 454     /* Pop the stack and insert nodes */
 455     p = NULL;
 456     while ((m = skiplist_qpop(&sl->stack_q))) {
 457         tmp = skiplist_new_node(sl);
 458         tmp->next = m->next;
 459         if (m->next) {
 460             m->next->prev = tmp;
 461         }
 462         m->next = tmp;
 463         tmp->prev = m;
 464         tmp->up = NULL;
 465         tmp->nextindex = tmp->previndex = NULL;
 466         tmp->down = p;
 467         if (p) {
 468             p->up = tmp;
 469         }
 470         else {
 471             /* This sets ret to the bottom-most node we are inserting */
 472             ret = tmp;
 473         }
 474         tmp->data = data;
 475         tmp->sl = sl;
 476         p = tmp;
 477     }
 478
 479     /* Now we are sure the node is inserted, grow our tree to 'nh' tall */
 480     for (; sl->height < nh; sl->height++) {
 481         m = skiplist_new_node(sl);
 482         tmp = skiplist_new_node(sl);
 483         m->up = m->prev = m->nextindex = m->previndex = NULL;
 484         m->next = tmp;
 485         m->down = sl->top;
 486         m->data = NULL;
 487         m->sl = sl;
 488         if (sl->top) {
 489             sl->top->up = m;
 490         }
 491         else {
 492             sl->bottom = sl->bottomend = m;
 493         }
 494         sl->top = sl->topend = tmp->prev = m;
 495         tmp->up = tmp->next = tmp->nextindex = tmp->previndex = NULL;
 496         tmp->down = p;
 497         tmp->data = data;
 498         tmp->sl = sl;
 499         if (p) {
 500             p->up = tmp;
 501         }
 502         else {
 503             /* This sets ret to the bottom-most node we are inserting */
 504             ret = tmp;
 505         }
 506         p = tmp;
 507     }
 508     if (sl->index != NULL) {
 509         /*
 510          * this is a external insertion, we must insert into each index as
 511          * well
 512          */
 513         apr_skiplistnode *ni, *li;
 514         li = ret;
 515         for (p = apr_skiplist_getlist(sl->index); p; apr_skiplist_next(sl->index, &p)) {
 516             apr_skiplist *sli = (apr_skiplist *)p->data;
 517             ni = apr_skiplist_insert_compare(sli, ret->data, sli->compare);
 518             li->nextindex = ni;
 519             ni->previndex = li;
 520             li = ni;
 521         }
 522     }
 523     sl->size++;
 524     return ret;
 525 }
 526
 527 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
 528 {
 529     return apr_skiplist_insert_compare(sl, data, sl->compare);
 530 }
 531
 532 #if 0
 533 void skiplist_print_struct(apr_skiplist * sl, char *prefix)
 534 {
 535     apr_skiplistnode *p, *q;
 536     fprintf(stderr, "Skiplist Structure (height: %d)\n", sl->height);
 537     p = sl->bottom;
 538     while (p) {
 539         q = p;
 540         fprintf(stderr, prefix);
 541         while (q) {
 542             fprintf(stderr, "%p ", q->data);
 543             q = q->up;
 544         }
 545         fprintf(stderr, "\n");
 546         p = p->next;
 547     }
 548 }
 549 #endif
 550
 551 static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, apr_skiplist_freefunc myfree)
 552 {
 553     apr_skiplistnode *p;
 554     if (!m) {
 555         return 0;
 556     }
 557     if (m->nextindex) {
 558         skiplisti_remove(m->nextindex->sl, m->nextindex, NULL);
 559     }
 560     while (m->up) {
 561         m = m->up;
 562     }
 563     while (m) {
 564         p = m;
 565         p->prev->next = p->next;/* take me out of the list */
 566         if (p->next) {
 567             p->next->prev = p->prev;    /* take me out of the list */
 568         }
 569         m = m->down;
 570         /* This only frees the actual data in the bottom one */
 571         if (!m && myfree && p->data) {
 572             myfree(p->data);
 573         }
 574         skiplist_free_node(sl, p);
 575     }
 576     sl->size--;
 577     while (sl->top && sl->top->next == NULL) {
 578         /* While the row is empty and we are not on the bottom row */
 579         p = sl->top;
 580         sl->top = sl->top->down;/* Move top down one */
 581         if (sl->top) {
 582             sl->top->up = NULL; /* Make it think its the top */
 583         }
 584         skiplist_free_node(sl, p);
 585         sl->height--;
 586     }
 587     if (!sl->top) {
 588         sl->bottom = sl->bottomend = NULL;
 589         sl->topend = NULL;
 590     }
 591     return skiplist_height(sl);
 592 }
 593
 594 APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli,
 595                             void *data,
 596                             apr_skiplist_freefunc myfree, apr_skiplist_compare comp)
 597 {
 598     apr_skiplistnode *m;
 599     apr_skiplist *sl;
 600     if (!comp) {
 601         return 0;
 602     }
 603     if (comp == sli->comparek || !sli->index) {
 604         sl = sli;
 605     }
 606     else {
 607         apr_skiplist_find(sli->index, (void *)comp, &m);
 608         if (!m) {
 609             return 0;
 610         }
 611         sl = (apr_skiplist *) m->data;
 612     }
 613     skiplisti_find_compare(sl, data, &m, comp);
 614     if (!m) {
 615         return 0;
 616     }
 617     while (m->previndex) {
 618         m = m->previndex;
 619     }
 620     return skiplisti_remove(sl, m, myfree);
 621 }
 622
 623 APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree)
 624 {
 625     return apr_skiplist_remove_compare(sl, data, myfree, sl->comparek);
 626 }
 627
 628 APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree)
 629 {
 630     /*
 631      * This must remove even the place holder nodes (bottom though top)
 632      * because we specify in the API that one can free the Skiplist after
 633      * making this call without memory leaks
 634      */
 635     apr_skiplistnode *m, *p, *u;
 636     m = sl->bottom;
 637     while (m) {
 638         p = m->next;
 639         if (myfree && p && p->data) {
 640             myfree(p->data);
 641         }
 642         do {
 643             u = m->up;
 644             skiplist_free_node(sl, m);
 645             m = u;
 646         } while (m);
 647         m = p;
 648     }
 649     sl->top = sl->bottom = NULL;
 650     sl->topend = sl->bottomend = NULL;
 651     sl->height = 0;
 652     sl->size = 0;
 653 }
 654
 655 APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *a, apr_skiplist_freefunc myfree)
 656 {
 657     apr_skiplistnode *sln;
 658     void *data = NULL;
 659     sln = apr_skiplist_getlist(a);
 660     if (sln) {
 661         data = sln->data;
 662         skiplisti_remove(a, sln, myfree);
 663     }
 664     return data;
 665 }
 666
 667 APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *a)
 668 {
 669     apr_skiplistnode *sln;
 670     sln = apr_skiplist_getlist(a);
 671     if (sln) {
 672         return sln->data;
 673     }
 674     return NULL;
 675 }
 676
 677 static void skiplisti_destroy(void *vsl)
 678 {
 679     apr_skiplist_destroy(vsl, NULL);
 680 }
 681
 682 APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree)
 683 {
 684     while (apr_skiplist_pop(sl->index, skiplisti_destroy) != NULL)
 685         ;
 686     apr_skiplist_remove_all(sl, myfree);
 687     if (!sl->pool) {
 688         while (sl->nodes_q.pos)
 689             free(sl->nodes_q.data[--sl->nodes_q.pos]);
 690         free(sl->nodes_q.data);
 691         free(sl->stack_q.data);
 692         free(sl);
 693     }
 694 }
 695
 696 APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2)
 697 {
 698     /* Check integrity! */
 699     apr_skiplist temp;
 700     struct apr_skiplistnode *b2;
 701     if (sl1->bottomend == NULL || sl1->bottomend->prev == NULL) {
 702         apr_skiplist_remove_all(sl1, NULL);
 703         temp = *sl1;
 704         *sl1 = *sl2;
 705         *sl2 = temp;
 706         /* swap them so that sl2 can be freed normally upon return. */
 707         return sl1;
 708     }
 709     if(sl2->bottom == NULL || sl2->bottom->next == NULL) {
 710         apr_skiplist_remove_all(sl2, NULL);
 711         return sl1;
 712     }
 713     /* This is what makes it brute force... Just insert :/ */
 714     b2 = apr_skiplist_getlist(sl2);
 715     while (b2) {
 716         apr_skiplist_insert(sl1, b2->data);
 717         apr_skiplist_next(sl2, &b2);
 718     }
 719     apr_skiplist_remove_all(sl2, NULL);
 720     return sl1;
 721 }