apr_skiplist.c revision 289166
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_free_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{ 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 331APR_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 363APR_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 369APR_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 377APR_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 386APR_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 395static 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 404APR_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 527APR_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 533void 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 551static 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 594APR_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 623APR_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 628APR_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 655APR_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 667APR_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 677static void skiplisti_destroy(void *vsl) 678{ 679 apr_skiplist_destroy(vsl, NULL); 680} 681 682APR_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 696APR_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} 722