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 struct apr_skiplist {
  29     apr_skiplist_compare compare;
  30     apr_skiplist_compare comparek;
  31     int height;
  32     int preheight;
  33     int size;
  34     apr_skiplistnode *top;
  35     apr_skiplistnode *bottom;
  36     /* These two are needed for appending */
  37     apr_skiplistnode *topend;
  38     apr_skiplistnode *bottomend;
  39     apr_skiplist *index;
  40     apr_array_header_t *memlist;
  41     apr_pool_t *pool;
  42 };
  43
  44 struct apr_skiplistnode {
  45     void *data;
  46     apr_skiplistnode *next;
  47     apr_skiplistnode *prev;
  48     apr_skiplistnode *down;
  49     apr_skiplistnode *up;
  50     apr_skiplistnode *previndex;
  51     apr_skiplistnode *nextindex;
  52     apr_skiplist *sl;
  53 };
  54
  55 #ifndef MIN
  56 #define MIN(a,b) ((a<b)?(a):(b))
  57 #endif
  58
  59 static int get_b_rand(void)
  60 {
  61     static int ph = 32;         /* More bits than we will ever use */
  62     static apr_uint32_t randseq;
  63     if (ph > 31) {              /* Num bits in return of rand() */
  64         ph = 0;
  65         randseq = (apr_uint32_t) rand();
  66     }
  67     ph++;
  68     return ((randseq & (1 << (ph - 1))) >> (ph - 1));
  69 }
  70
  71 typedef struct {
  72     size_t size;
  73     apr_array_header_t *list;
  74 } memlist_t;
  75
  76 typedef struct {
  77     void *ptr;
  78     char inuse;
  79 } chunk_t;
  80
  81 APR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size)
  82 {
  83     if (sl->pool) {
  84         void *ptr;
  85         int found_size = 0;
  86         int i;
  87         chunk_t *newchunk;
  88         memlist_t *memlist = (memlist_t *)sl->memlist->elts;
  89         for (i = 0; i < sl->memlist->nelts; i++) {
  90             if (memlist->size == size) {
  91                 int j;
  92                 chunk_t *chunk = (chunk_t *)memlist->list->elts;
  93                 found_size = 1;
  94                 for (j = 0; j < memlist->list->nelts; j++) {
  95                     if (!chunk->inuse) {
  96                         chunk->inuse = 1;
  97                         return chunk->ptr;
  98                     }
  99                     chunk++;
 100                 }
 101                 break; /* no free of this size; punt */
 102             }
 103             memlist++;
 104         }
 105         /* no free chunks */
 106         ptr = apr_pcalloc(sl->pool, size);
 107         if (!ptr) {
 108             return ptr;
 109         }
 110         /*
 111          * is this a new sized chunk? If so, we need to create a new
 112          * array of them. Otherwise, re-use what we already have.
 113          */
 114         if (!found_size) {
 115             memlist = apr_array_push(sl->memlist);
 116             memlist->size = size;
 117             memlist->list = apr_array_make(sl->pool, 20, sizeof(chunk_t));
 118         }
 119         newchunk = apr_array_push(memlist->list);
 120         newchunk->ptr = ptr;
 121         newchunk->inuse = 1;
 122         return ptr;
 123     }
 124     else {
 125         return calloc(1, size);
 126     }
 127 }
 128
 129 APR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem)
 130 {
 131     if (!sl->pool) {
 132         free(mem);
 133     }
 134     else {
 135         int i;
 136         memlist_t *memlist = (memlist_t *)sl->memlist->elts;
 137         for (i = 0; i < sl->memlist->nelts; i++) {
 138             int j;
 139             chunk_t *chunk = (chunk_t *)memlist->list->elts;
 140             for (j = 0; j < memlist->list->nelts; j++) {
 141                 if (chunk->ptr == mem) {
 142                     chunk->inuse = 0;
 143                     return;
 144                 }
 145                 chunk++;
 146             }
 147             memlist++;
 148         }
 149     }
 150 }
 151
 152 static apr_status_t skiplisti_init(apr_skiplist **s, apr_pool_t *p)
 153 {
 154     apr_skiplist *sl;
 155     if (p) {
 156         sl = apr_pcalloc(p, sizeof(apr_skiplist));
 157         sl->memlist = apr_array_make(p, 20, sizeof(memlist_t));
 158     }
 159     else {
 160         sl = calloc(1, sizeof(apr_skiplist));
 161     }
 162 #if 0
 163     sl->compare = (apr_skiplist_compare) NULL;
 164     sl->comparek = (apr_skiplist_compare) NULL;
 165     sl->height = 0;
 166     sl->preheight = 0;
 167     sl->size = 0;
 168     sl->top = NULL;
 169     sl->bottom = NULL;
 170     sl->index = NULL;
 171 #endif
 172     sl->pool = p;
 173     *s = sl;
 174     return APR_SUCCESS;
 175 }
 176
 177 static int indexing_comp(void *a, void *b)
 178 {
 179     void *ac = (void *) (((apr_skiplist *) a)->compare);
 180     void *bc = (void *) (((apr_skiplist *) b)->compare);
 181     return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0));
 182 }
 183
 184 static int indexing_compk(void *ac, void *b)
 185 {
 186     void *bc = (void *) (((apr_skiplist *) b)->compare);
 187     return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0));
 188 }
 189
 190 APR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **s, apr_pool_t *p)
 191 {
 192     apr_skiplist *sl;
 193     skiplisti_init(s, p);
 194     sl = *s;
 195     skiplisti_init(&(sl->index), p);
 196     apr_skiplist_set_compare(sl->index, indexing_comp, indexing_compk);
 197     return APR_SUCCESS;
 198 }
 199
 200 APR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl,
 201                           apr_skiplist_compare comp,
 202                           apr_skiplist_compare compk)
 203 {
 204     if (sl->compare && sl->comparek) {
 205         apr_skiplist_add_index(sl, comp, compk);
 206     }
 207     else {
 208         sl->compare = comp;
 209         sl->comparek = compk;
 210     }
 211 }
 212
 213 APR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl,
 214                         apr_skiplist_compare comp,
 215                         apr_skiplist_compare compk)
 216 {
 217     apr_skiplistnode *m;
 218     apr_skiplist *ni;
 219     int icount = 0;
 220     apr_skiplist_find(sl->index, (void *)comp, &m);
 221     if (m) {
 222         return;                 /* Index already there! */
 223     }
 224     skiplisti_init(&ni, sl->pool);
 225     apr_skiplist_set_compare(ni, comp, compk);
 226     /* Build the new index... This can be expensive! */
 227     m = apr_skiplist_insert(sl->index, ni);
 228     while (m->prev) {
 229         m = m->prev;
 230         icount++;
 231     }
 232     for (m = apr_skiplist_getlist(sl); m; apr_skiplist_next(sl, &m)) {
 233         int j = icount - 1;
 234         apr_skiplistnode *nsln;
 235         nsln = apr_skiplist_insert(ni, m->data);
 236         /* skip from main index down list */
 237         while (j > 0) {
 238             m = m->nextindex;
 239             j--;
 240         }
 241         /* insert this node in the indexlist after m */
 242         nsln->nextindex = m->nextindex;
 243         if (m->nextindex) {
 244             m->nextindex->previndex = nsln;
 245         }
 246         nsln->previndex = m;
 247         m->nextindex = nsln;
 248     }
 249 }
 250
 251 APR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl)
 252 {
 253     if (!sl->bottom) {
 254         return NULL;
 255     }
 256     return sl->bottom->next;
 257 }
 258
 259 APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter)
 260 {
 261     void *ret;
 262     apr_skiplistnode *aiter;
 263     if (!sl->compare) {
 264         return 0;
 265     }
 266     if (iter) {
 267         ret = apr_skiplist_find_compare(sl, data, iter, sl->compare);
 268     }
 269     else {
 270         ret = apr_skiplist_find_compare(sl, data, &aiter, sl->compare);
 271     }
 272     return ret;
 273 }
 274
 275 static int skiplisti_find_compare(apr_skiplist *sl, void *data,
 276                            apr_skiplistnode **ret,
 277                            apr_skiplist_compare comp)
 278 {
 279     apr_skiplistnode *m = NULL;
 280     int count = 0;
 281     m = sl->top;
 282     while (m) {
 283         int compared;
 284         compared = (m->next) ? comp(data, m->next->data) : -1;
 285         if (compared == 0) {
 286             m = m->next;
 287             while (m->down) {
 288                 m = m->down;
 289             }
 290             *ret = m;
 291             return count;
 292         }
 293         if ((m->next == NULL) || (compared < 0)) {
 294             m = m->down;
 295             count++;
 296         }
 297         else {
 298             m = m->next;
 299             count++;
 300         }
 301     }
 302     *ret = NULL;
 303     return count;
 304 }
 305
 306 APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sli, void *data,
 307                                apr_skiplistnode **iter,
 308                                apr_skiplist_compare comp)
 309 {
 310     apr_skiplistnode *m = NULL;
 311     apr_skiplist *sl;
 312     if (comp == sli->compare || !sli->index) {
 313         sl = sli;
 314     }
 315     else {
 316         apr_skiplist_find(sli->index, (void *)comp, &m);
 317         sl = (apr_skiplist *) m->data;
 318     }
 319     skiplisti_find_compare(sl, data, iter, sl->comparek);
 320     return (iter && *iter) ? ((*iter)->data) : NULL;
 321 }
 322
 323
 324 APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter)
 325 {
 326     if (!*iter) {
 327         return NULL;
 328     }
 329     *iter = (*iter)->next;
 330     return (*iter) ? ((*iter)->data) : NULL;
 331 }
 332
 333 APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter)
 334 {
 335     if (!*iter) {
 336         return NULL;
 337     }
 338     *iter = (*iter)->prev;
 339     return (*iter) ? ((*iter)->data) : NULL;
 340 }
 341
 342 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
 343 {
 344     if (!sl->compare) {
 345         return 0;
 346     }
 347     return apr_skiplist_insert_compare(sl, data, sl->compare);
 348 }
 349
 350 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
 351                                       apr_skiplist_compare comp)
 352 {
 353     apr_skiplistnode *m, *p, *tmp, *ret = NULL, **stack;
 354     int nh = 1, ch, stacki;
 355     if (!sl->top) {
 356         sl->height = 1;
 357         sl->topend = sl->bottomend = sl->top = sl->bottom =
 358             (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
 359 #if 0
 360         sl->top->next = (apr_skiplistnode *)NULL;
 361         sl->top->data = (apr_skiplistnode *)NULL;
 362         sl->top->prev = (apr_skiplistnode *)NULL;
 363         sl->top->up = (apr_skiplistnode *)NULL;
 364         sl->top->down = (apr_skiplistnode *)NULL;
 365         sl->top->nextindex = (apr_skiplistnode *)NULL;
 366         sl->top->previndex = (apr_skiplistnode *)NULL;
 367 #endif
 368         sl->top->sl = sl;
 369     }
 370     if (sl->preheight) {
 371         while (nh < sl->preheight && get_b_rand()) {
 372             nh++;
 373         }
 374     }
 375     else {
 376         while (nh <= sl->height && get_b_rand()) {
 377             nh++;
 378         }
 379     }
 380     /* Now we have the new height at which we wish to insert our new node */
 381     /*
 382      * Let us make sure that our tree is a least that tall (grow if
 383      * necessary)
 384      */
 385     for (; sl->height < nh; sl->height++) {
 386         sl->top->up =
 387             (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
 388         sl->top->up->down = sl->top;
 389         sl->top = sl->topend = sl->top->up;
 390 #if 0
 391         sl->top->prev = sl->top->next = sl->top->nextindex =
 392             sl->top->previndex = sl->top->up = NULL;
 393         sl->top->data = NULL;
 394 #endif
 395         sl->top->sl = sl;
 396     }
 397     ch = sl->height;
 398     /* Find the node (or node after which we would insert) */
 399     /* Keep a stack to pop back through for insertion */
 400     /* malloc() is OK since we free the temp stack */
 401     m = sl->top;
 402     stack = (apr_skiplistnode **)malloc(sizeof(apr_skiplistnode *) * (nh));
 403     stacki = 0;
 404     while (m) {
 405         int compared = -1;
 406         if (m->next) {
 407             compared = comp(data, m->next->data);
 408         }
 409         if (compared == 0) {
 410             free(stack);    /* OK. was malloc'ed */
 411             return 0;
 412         }
 413         if ((m->next == NULL) || (compared < 0)) {
 414             if (ch <= nh) {
 415                 /* push on stack */
 416                 stack[stacki++] = m;
 417             }
 418             m = m->down;
 419             ch--;
 420         }
 421         else {
 422             m = m->next;
 423         }
 424     }
 425     /* Pop the stack and insert nodes */
 426     p = NULL;
 427     for (; stacki > 0; stacki--) {
 428         m = stack[stacki - 1];
 429         tmp = (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
 430         tmp->next = m->next;
 431         if (m->next) {
 432             m->next->prev = tmp;
 433         }
 434         tmp->prev = m;
 435         tmp->up = NULL;
 436         tmp->nextindex = tmp->previndex = NULL;
 437         tmp->down = p;
 438         if (p) {
 439             p->up = tmp;
 440         }
 441         tmp->data = data;
 442         tmp->sl = sl;
 443         m->next = tmp;
 444         /* This sets ret to the bottom-most node we are inserting */
 445         if (!p) {
 446             ret = tmp;
 447             sl->size++; /* this seems to go here got each element to be counted */
 448         }
 449         p = tmp;
 450     }
 451     free(stack); /* OK. was malloc'ed */
 452     if (sl->index != NULL) {
 453         /*
 454          * this is a external insertion, we must insert into each index as
 455          * well
 456          */
 457         apr_skiplistnode *ni, *li;
 458         li = ret;
 459         for (p = apr_skiplist_getlist(sl->index); p; apr_skiplist_next(sl->index, &p)) {
 460             ni = apr_skiplist_insert((apr_skiplist *) p->data, ret->data);
 461             li->nextindex = ni;
 462             ni->previndex = li;
 463             li = ni;
 464         }
 465     }
 466     else {
 467         /* sl->size++; */
 468     }
 469     sl->size++;
 470     return ret;
 471 }
 472
 473 APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree)
 474 {
 475     if (!sl->compare) {
 476         return 0;
 477     }
 478     return apr_skiplist_remove_compare(sl, data, myfree, sl->comparek);
 479 }
 480
 481 #if 0
 482 void skiplist_print_struct(apr_skiplist * sl, char *prefix)
 483 {
 484     apr_skiplistnode *p, *q;
 485     fprintf(stderr, "Skiplist Structure (height: %d)\n", sl->height);
 486     p = sl->bottom;
 487     while (p) {
 488         q = p;
 489         fprintf(stderr, prefix);
 490         while (q) {
 491             fprintf(stderr, "%p ", q->data);
 492             q = q->up;
 493         }
 494         fprintf(stderr, "\n");
 495         p = p->next;
 496     }
 497 }
 498 #endif
 499
 500 static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, apr_skiplist_freefunc myfree)
 501 {
 502     apr_skiplistnode *p;
 503     if (!m) {
 504         return 0;
 505     }
 506     if (m->nextindex) {
 507         skiplisti_remove(m->nextindex->sl, m->nextindex, NULL);
 508     }
 509     while (m->up) {
 510         m = m->up;
 511     }
 512     while (m) {
 513         p = m;
 514         p->prev->next = p->next;/* take me out of the list */
 515         if (p->next) {
 516             p->next->prev = p->prev;    /* take me out of the list */
 517         }
 518         m = m->down;
 519         /* This only frees the actual data in the bottom one */
 520         if (!m && myfree && p->data) {
 521             myfree(p->data);
 522         }
 523         apr_skiplist_free(sl, p);
 524     }
 525     sl->size--;
 526     while (sl->top && sl->top->next == NULL) {
 527         /* While the row is empty and we are not on the bottom row */
 528         p = sl->top;
 529         sl->top = sl->top->down;/* Move top down one */
 530         if (sl->top) {
 531             sl->top->up = NULL; /* Make it think its the top */
 532         }
 533         apr_skiplist_free(sl, p);
 534         sl->height--;
 535     }
 536     if (!sl->top) {
 537         sl->bottom = NULL;
 538     }
 539     return sl->height;  /* return 1; ?? */
 540 }
 541
 542 APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli,
 543                             void *data,
 544                             apr_skiplist_freefunc myfree, apr_skiplist_compare comp)
 545 {
 546     apr_skiplistnode *m;
 547     apr_skiplist *sl;
 548     if (comp == sli->comparek || !sli->index) {
 549         sl = sli;
 550     }
 551     else {
 552         apr_skiplist_find(sli->index, (void *)comp, &m);
 553         sl = (apr_skiplist *) m->data;
 554     }
 555     skiplisti_find_compare(sl, data, &m, comp);
 556     if (!m) {
 557         return 0;
 558     }
 559     while (m->previndex) {
 560         m = m->previndex;
 561     }
 562     return skiplisti_remove(sl, m, myfree);
 563 }
 564
 565 APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree)
 566 {
 567     /*
 568      * This must remove even the place holder nodes (bottom though top)
 569      * because we specify in the API that one can free the Skiplist after
 570      * making this call without memory leaks
 571      */
 572     apr_skiplistnode *m, *p, *u;
 573     m = sl->bottom;
 574     while (m) {
 575         p = m->next;
 576         if (p && myfree && p->data)
 577             myfree(p->data);
 578         while (m) {
 579             u = m->up;
 580             apr_skiplist_free(sl, p);
 581             m = u;
 582         }
 583         m = p;
 584     }
 585     sl->top = sl->bottom = NULL;
 586     sl->height = 0;
 587     sl->size = 0;
 588 }
 589
 590 APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *a, apr_skiplist_freefunc myfree)
 591 {
 592     apr_skiplistnode *sln;
 593     void *data = NULL;
 594     sln = apr_skiplist_getlist(a);
 595     if (sln) {
 596         data = sln->data;
 597         skiplisti_remove(a, sln, myfree);
 598     }
 599     return data;
 600 }
 601
 602 APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *a)
 603 {
 604     apr_skiplistnode *sln;
 605     sln = apr_skiplist_getlist(a);
 606     if (sln) {
 607         return sln->data;
 608     }
 609     return NULL;
 610 }
 611
 612 static void skiplisti_destroy(void *vsl)
 613 {
 614     apr_skiplist_destroy((apr_skiplist *) vsl, NULL);
 615     apr_skiplist_free((apr_skiplist *) vsl, vsl);
 616 }
 617
 618 APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree)
 619 {
 620     while (apr_skiplist_pop(sl->index, skiplisti_destroy) != NULL)
 621         ;
 622     apr_skiplist_remove_all(sl, myfree);
 623 }
 624
 625 APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2)
 626 {
 627     /* Check integrity! */
 628     apr_skiplist temp;
 629     struct apr_skiplistnode *b2;
 630     if (sl1->bottomend == NULL || sl1->bottomend->prev == NULL) {
 631         apr_skiplist_remove_all(sl1, NULL);
 632         temp = *sl1;
 633         *sl1 = *sl2;
 634         *sl2 = temp;
 635         /* swap them so that sl2 can be freed normally upon return. */
 636         return sl1;
 637     }
 638     if(sl2->bottom == NULL || sl2->bottom->next == NULL) {
 639         apr_skiplist_remove_all(sl2, NULL);
 640         return sl1;
 641     }
 642     /* This is what makes it brute force... Just insert :/ */
 643     b2 = apr_skiplist_getlist(sl2);
 644     while (b2) {
 645         apr_skiplist_insert(sl1, b2->data);
 646         apr_skiplist_next(sl2, &b2);
 647     }
 648     apr_skiplist_remove_all(sl2, NULL);
 649     return sl1;
 650 }