apr_skiplist.c revision 266733
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 28struct 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 44struct 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 59static 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 71typedef struct { 72 size_t size; 73 apr_array_header_t *list; 74} memlist_t; 75 76typedef struct { 77 void *ptr; 78 char inuse; 79} chunk_t; 80 81APR_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 129APR_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 152static 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 177static 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 184static 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 190APR_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 200APR_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 213APR_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 251APR_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 259APR_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 275static 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 306APR_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 324APR_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 333APR_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 342APR_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 350APR_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 473APR_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 482void 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 500static 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 542APR_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 565APR_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 590APR_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 602APR_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 612static void skiplisti_destroy(void *vsl) 613{ 614 apr_skiplist_destroy((apr_skiplist *) vsl, NULL); 615 apr_skiplist_free((apr_skiplist *) vsl, vsl); 616} 617 618APR_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 625APR_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} 651