1266733Speter/* Licensed to the Apache Software Foundation (ASF) under one or more 2266733Speter * contributor license agreements. See the NOTICE file distributed with 3266733Speter * this work for additional information regarding copyright ownership. 4266733Speter * The ASF licenses this file to You under the Apache License, Version 2.0 5266733Speter * (the "License"); you may not use this file except in compliance with 6266733Speter * the License. You may obtain a copy of the License at 7266733Speter * 8266733Speter * http://www.apache.org/licenses/LICENSE-2.0 9266733Speter * 10266733Speter * Unless required by applicable law or agreed to in writing, software 11266733Speter * distributed under the License is distributed on an "AS IS" BASIS, 12266733Speter * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13266733Speter * See the License for the specific language governing permissions and 14266733Speter * limitations under the License. 15266733Speter */ 16266733Speter 17266733Speter/* 18266733Speter * Modified to use APR and APR pools. 19266733Speter * TODO: Is malloc() better? Will long running skiplists grow too much? 20266733Speter * Keep the skiplist_alloc() and skiplist_free() until we know 21266733Speter * Yeah, if using pools it means some bogus cycles for checks 22266733Speter * (and an useless function call for skiplist_free) which we 23266733Speter * can removed if/when needed. 24266733Speter */ 25266733Speter 26266733Speter#include "apr_skiplist.h" 27266733Speter 28266733Speterstruct apr_skiplist { 29266733Speter apr_skiplist_compare compare; 30266733Speter apr_skiplist_compare comparek; 31266733Speter int height; 32266733Speter int preheight; 33266733Speter int size; 34266733Speter apr_skiplistnode *top; 35266733Speter apr_skiplistnode *bottom; 36266733Speter /* These two are needed for appending */ 37266733Speter apr_skiplistnode *topend; 38266733Speter apr_skiplistnode *bottomend; 39266733Speter apr_skiplist *index; 40266733Speter apr_array_header_t *memlist; 41266733Speter apr_pool_t *pool; 42266733Speter}; 43266733Speter 44266733Speterstruct apr_skiplistnode { 45266733Speter void *data; 46266733Speter apr_skiplistnode *next; 47266733Speter apr_skiplistnode *prev; 48266733Speter apr_skiplistnode *down; 49266733Speter apr_skiplistnode *up; 50266733Speter apr_skiplistnode *previndex; 51266733Speter apr_skiplistnode *nextindex; 52266733Speter apr_skiplist *sl; 53266733Speter}; 54266733Speter 55266733Speter#ifndef MIN 56266733Speter#define MIN(a,b) ((a<b)?(a):(b)) 57266733Speter#endif 58266733Speter 59266733Speterstatic int get_b_rand(void) 60266733Speter{ 61266733Speter static int ph = 32; /* More bits than we will ever use */ 62266733Speter static apr_uint32_t randseq; 63266733Speter if (ph > 31) { /* Num bits in return of rand() */ 64266733Speter ph = 0; 65266733Speter randseq = (apr_uint32_t) rand(); 66266733Speter } 67266733Speter ph++; 68266733Speter return ((randseq & (1 << (ph - 1))) >> (ph - 1)); 69266733Speter} 70266733Speter 71266733Spetertypedef struct { 72266733Speter size_t size; 73266733Speter apr_array_header_t *list; 74266733Speter} memlist_t; 75266733Speter 76266733Spetertypedef struct { 77266733Speter void *ptr; 78266733Speter char inuse; 79266733Speter} chunk_t; 80266733Speter 81266733SpeterAPR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size) 82266733Speter{ 83266733Speter if (sl->pool) { 84266733Speter void *ptr; 85266733Speter int found_size = 0; 86266733Speter int i; 87266733Speter chunk_t *newchunk; 88266733Speter memlist_t *memlist = (memlist_t *)sl->memlist->elts; 89266733Speter for (i = 0; i < sl->memlist->nelts; i++) { 90266733Speter if (memlist->size == size) { 91266733Speter int j; 92266733Speter chunk_t *chunk = (chunk_t *)memlist->list->elts; 93266733Speter found_size = 1; 94266733Speter for (j = 0; j < memlist->list->nelts; j++) { 95266733Speter if (!chunk->inuse) { 96266733Speter chunk->inuse = 1; 97266733Speter return chunk->ptr; 98266733Speter } 99266733Speter chunk++; 100266733Speter } 101266733Speter break; /* no free of this size; punt */ 102266733Speter } 103266733Speter memlist++; 104266733Speter } 105266733Speter /* no free chunks */ 106266733Speter ptr = apr_pcalloc(sl->pool, size); 107266733Speter if (!ptr) { 108266733Speter return ptr; 109266733Speter } 110266733Speter /* 111266733Speter * is this a new sized chunk? If so, we need to create a new 112266733Speter * array of them. Otherwise, re-use what we already have. 113266733Speter */ 114266733Speter if (!found_size) { 115266733Speter memlist = apr_array_push(sl->memlist); 116266733Speter memlist->size = size; 117266733Speter memlist->list = apr_array_make(sl->pool, 20, sizeof(chunk_t)); 118266733Speter } 119266733Speter newchunk = apr_array_push(memlist->list); 120266733Speter newchunk->ptr = ptr; 121266733Speter newchunk->inuse = 1; 122266733Speter return ptr; 123266733Speter } 124266733Speter else { 125266733Speter return calloc(1, size); 126266733Speter } 127266733Speter} 128266733Speter 129266733SpeterAPR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem) 130266733Speter{ 131266733Speter if (!sl->pool) { 132266733Speter free(mem); 133266733Speter } 134266733Speter else { 135266733Speter int i; 136266733Speter memlist_t *memlist = (memlist_t *)sl->memlist->elts; 137266733Speter for (i = 0; i < sl->memlist->nelts; i++) { 138266733Speter int j; 139266733Speter chunk_t *chunk = (chunk_t *)memlist->list->elts; 140266733Speter for (j = 0; j < memlist->list->nelts; j++) { 141266733Speter if (chunk->ptr == mem) { 142266733Speter chunk->inuse = 0; 143266733Speter return; 144266733Speter } 145266733Speter chunk++; 146266733Speter } 147266733Speter memlist++; 148266733Speter } 149266733Speter } 150266733Speter} 151266733Speter 152266733Speterstatic apr_status_t skiplisti_init(apr_skiplist **s, apr_pool_t *p) 153266733Speter{ 154266733Speter apr_skiplist *sl; 155266733Speter if (p) { 156266733Speter sl = apr_pcalloc(p, sizeof(apr_skiplist)); 157266733Speter sl->memlist = apr_array_make(p, 20, sizeof(memlist_t)); 158266733Speter } 159266733Speter else { 160266733Speter sl = calloc(1, sizeof(apr_skiplist)); 161266733Speter } 162266733Speter#if 0 163266733Speter sl->compare = (apr_skiplist_compare) NULL; 164266733Speter sl->comparek = (apr_skiplist_compare) NULL; 165266733Speter sl->height = 0; 166266733Speter sl->preheight = 0; 167266733Speter sl->size = 0; 168266733Speter sl->top = NULL; 169266733Speter sl->bottom = NULL; 170266733Speter sl->index = NULL; 171266733Speter#endif 172266733Speter sl->pool = p; 173266733Speter *s = sl; 174266733Speter return APR_SUCCESS; 175266733Speter} 176266733Speter 177266733Speterstatic int indexing_comp(void *a, void *b) 178266733Speter{ 179266733Speter void *ac = (void *) (((apr_skiplist *) a)->compare); 180266733Speter void *bc = (void *) (((apr_skiplist *) b)->compare); 181266733Speter return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0)); 182266733Speter} 183266733Speter 184266733Speterstatic int indexing_compk(void *ac, void *b) 185266733Speter{ 186266733Speter void *bc = (void *) (((apr_skiplist *) b)->compare); 187266733Speter return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0)); 188266733Speter} 189266733Speter 190266733SpeterAPR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **s, apr_pool_t *p) 191266733Speter{ 192266733Speter apr_skiplist *sl; 193266733Speter skiplisti_init(s, p); 194266733Speter sl = *s; 195266733Speter skiplisti_init(&(sl->index), p); 196266733Speter apr_skiplist_set_compare(sl->index, indexing_comp, indexing_compk); 197266733Speter return APR_SUCCESS; 198266733Speter} 199266733Speter 200266733SpeterAPR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl, 201266733Speter apr_skiplist_compare comp, 202266733Speter apr_skiplist_compare compk) 203266733Speter{ 204266733Speter if (sl->compare && sl->comparek) { 205266733Speter apr_skiplist_add_index(sl, comp, compk); 206266733Speter } 207266733Speter else { 208266733Speter sl->compare = comp; 209266733Speter sl->comparek = compk; 210266733Speter } 211266733Speter} 212266733Speter 213266733SpeterAPR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl, 214266733Speter apr_skiplist_compare comp, 215266733Speter apr_skiplist_compare compk) 216266733Speter{ 217266733Speter apr_skiplistnode *m; 218266733Speter apr_skiplist *ni; 219266733Speter int icount = 0; 220266733Speter apr_skiplist_find(sl->index, (void *)comp, &m); 221266733Speter if (m) { 222266733Speter return; /* Index already there! */ 223266733Speter } 224266733Speter skiplisti_init(&ni, sl->pool); 225266733Speter apr_skiplist_set_compare(ni, comp, compk); 226266733Speter /* Build the new index... This can be expensive! */ 227266733Speter m = apr_skiplist_insert(sl->index, ni); 228266733Speter while (m->prev) { 229266733Speter m = m->prev; 230266733Speter icount++; 231266733Speter } 232266733Speter for (m = apr_skiplist_getlist(sl); m; apr_skiplist_next(sl, &m)) { 233266733Speter int j = icount - 1; 234266733Speter apr_skiplistnode *nsln; 235266733Speter nsln = apr_skiplist_insert(ni, m->data); 236266733Speter /* skip from main index down list */ 237266733Speter while (j > 0) { 238266733Speter m = m->nextindex; 239266733Speter j--; 240266733Speter } 241266733Speter /* insert this node in the indexlist after m */ 242266733Speter nsln->nextindex = m->nextindex; 243266733Speter if (m->nextindex) { 244266733Speter m->nextindex->previndex = nsln; 245266733Speter } 246266733Speter nsln->previndex = m; 247266733Speter m->nextindex = nsln; 248266733Speter } 249266733Speter} 250266733Speter 251266733SpeterAPR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl) 252266733Speter{ 253266733Speter if (!sl->bottom) { 254266733Speter return NULL; 255266733Speter } 256266733Speter return sl->bottom->next; 257266733Speter} 258266733Speter 259266733SpeterAPR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter) 260266733Speter{ 261266733Speter void *ret; 262266733Speter apr_skiplistnode *aiter; 263266733Speter if (!sl->compare) { 264266733Speter return 0; 265266733Speter } 266266733Speter if (iter) { 267266733Speter ret = apr_skiplist_find_compare(sl, data, iter, sl->compare); 268266733Speter } 269266733Speter else { 270266733Speter ret = apr_skiplist_find_compare(sl, data, &aiter, sl->compare); 271266733Speter } 272266733Speter return ret; 273266733Speter} 274266733Speter 275266733Speterstatic int skiplisti_find_compare(apr_skiplist *sl, void *data, 276266733Speter apr_skiplistnode **ret, 277266733Speter apr_skiplist_compare comp) 278266733Speter{ 279266733Speter apr_skiplistnode *m = NULL; 280266733Speter int count = 0; 281266733Speter m = sl->top; 282266733Speter while (m) { 283266733Speter int compared; 284266733Speter compared = (m->next) ? comp(data, m->next->data) : -1; 285266733Speter if (compared == 0) { 286266733Speter m = m->next; 287266733Speter while (m->down) { 288266733Speter m = m->down; 289266733Speter } 290266733Speter *ret = m; 291266733Speter return count; 292266733Speter } 293266733Speter if ((m->next == NULL) || (compared < 0)) { 294266733Speter m = m->down; 295266733Speter count++; 296266733Speter } 297266733Speter else { 298266733Speter m = m->next; 299266733Speter count++; 300266733Speter } 301266733Speter } 302266733Speter *ret = NULL; 303266733Speter return count; 304266733Speter} 305266733Speter 306266733SpeterAPR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sli, void *data, 307266733Speter apr_skiplistnode **iter, 308266733Speter apr_skiplist_compare comp) 309266733Speter{ 310266733Speter apr_skiplistnode *m = NULL; 311266733Speter apr_skiplist *sl; 312266733Speter if (comp == sli->compare || !sli->index) { 313266733Speter sl = sli; 314266733Speter } 315266733Speter else { 316266733Speter apr_skiplist_find(sli->index, (void *)comp, &m); 317266733Speter sl = (apr_skiplist *) m->data; 318266733Speter } 319266733Speter skiplisti_find_compare(sl, data, iter, sl->comparek); 320266733Speter return (iter && *iter) ? ((*iter)->data) : NULL; 321266733Speter} 322266733Speter 323266733Speter 324266733SpeterAPR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter) 325266733Speter{ 326266733Speter if (!*iter) { 327266733Speter return NULL; 328266733Speter } 329266733Speter *iter = (*iter)->next; 330266733Speter return (*iter) ? ((*iter)->data) : NULL; 331266733Speter} 332266733Speter 333266733SpeterAPR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter) 334266733Speter{ 335266733Speter if (!*iter) { 336266733Speter return NULL; 337266733Speter } 338266733Speter *iter = (*iter)->prev; 339266733Speter return (*iter) ? ((*iter)->data) : NULL; 340266733Speter} 341266733Speter 342266733SpeterAPR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data) 343266733Speter{ 344266733Speter if (!sl->compare) { 345266733Speter return 0; 346266733Speter } 347266733Speter return apr_skiplist_insert_compare(sl, data, sl->compare); 348266733Speter} 349266733Speter 350266733SpeterAPR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data, 351266733Speter apr_skiplist_compare comp) 352266733Speter{ 353266733Speter apr_skiplistnode *m, *p, *tmp, *ret = NULL, **stack; 354266733Speter int nh = 1, ch, stacki; 355266733Speter if (!sl->top) { 356266733Speter sl->height = 1; 357266733Speter sl->topend = sl->bottomend = sl->top = sl->bottom = 358266733Speter (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode)); 359266733Speter#if 0 360266733Speter sl->top->next = (apr_skiplistnode *)NULL; 361266733Speter sl->top->data = (apr_skiplistnode *)NULL; 362266733Speter sl->top->prev = (apr_skiplistnode *)NULL; 363266733Speter sl->top->up = (apr_skiplistnode *)NULL; 364266733Speter sl->top->down = (apr_skiplistnode *)NULL; 365266733Speter sl->top->nextindex = (apr_skiplistnode *)NULL; 366266733Speter sl->top->previndex = (apr_skiplistnode *)NULL; 367266733Speter#endif 368266733Speter sl->top->sl = sl; 369266733Speter } 370266733Speter if (sl->preheight) { 371266733Speter while (nh < sl->preheight && get_b_rand()) { 372266733Speter nh++; 373266733Speter } 374266733Speter } 375266733Speter else { 376266733Speter while (nh <= sl->height && get_b_rand()) { 377266733Speter nh++; 378266733Speter } 379266733Speter } 380266733Speter /* Now we have the new height at which we wish to insert our new node */ 381266733Speter /* 382266733Speter * Let us make sure that our tree is a least that tall (grow if 383266733Speter * necessary) 384266733Speter */ 385266733Speter for (; sl->height < nh; sl->height++) { 386266733Speter sl->top->up = 387266733Speter (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode)); 388266733Speter sl->top->up->down = sl->top; 389266733Speter sl->top = sl->topend = sl->top->up; 390266733Speter#if 0 391266733Speter sl->top->prev = sl->top->next = sl->top->nextindex = 392266733Speter sl->top->previndex = sl->top->up = NULL; 393266733Speter sl->top->data = NULL; 394266733Speter#endif 395266733Speter sl->top->sl = sl; 396266733Speter } 397266733Speter ch = sl->height; 398266733Speter /* Find the node (or node after which we would insert) */ 399266733Speter /* Keep a stack to pop back through for insertion */ 400266733Speter /* malloc() is OK since we free the temp stack */ 401266733Speter m = sl->top; 402266733Speter stack = (apr_skiplistnode **)malloc(sizeof(apr_skiplistnode *) * (nh)); 403266733Speter stacki = 0; 404266733Speter while (m) { 405266733Speter int compared = -1; 406266733Speter if (m->next) { 407266733Speter compared = comp(data, m->next->data); 408266733Speter } 409266733Speter if (compared == 0) { 410266733Speter free(stack); /* OK. was malloc'ed */ 411266733Speter return 0; 412266733Speter } 413266733Speter if ((m->next == NULL) || (compared < 0)) { 414266733Speter if (ch <= nh) { 415266733Speter /* push on stack */ 416266733Speter stack[stacki++] = m; 417266733Speter } 418266733Speter m = m->down; 419266733Speter ch--; 420266733Speter } 421266733Speter else { 422266733Speter m = m->next; 423266733Speter } 424266733Speter } 425266733Speter /* Pop the stack and insert nodes */ 426266733Speter p = NULL; 427266733Speter for (; stacki > 0; stacki--) { 428266733Speter m = stack[stacki - 1]; 429266733Speter tmp = (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode)); 430266733Speter tmp->next = m->next; 431266733Speter if (m->next) { 432266733Speter m->next->prev = tmp; 433266733Speter } 434266733Speter tmp->prev = m; 435266733Speter tmp->up = NULL; 436266733Speter tmp->nextindex = tmp->previndex = NULL; 437266733Speter tmp->down = p; 438266733Speter if (p) { 439266733Speter p->up = tmp; 440266733Speter } 441266733Speter tmp->data = data; 442266733Speter tmp->sl = sl; 443266733Speter m->next = tmp; 444266733Speter /* This sets ret to the bottom-most node we are inserting */ 445266733Speter if (!p) { 446266733Speter ret = tmp; 447266733Speter sl->size++; /* this seems to go here got each element to be counted */ 448266733Speter } 449266733Speter p = tmp; 450266733Speter } 451266733Speter free(stack); /* OK. was malloc'ed */ 452266733Speter if (sl->index != NULL) { 453266733Speter /* 454266733Speter * this is a external insertion, we must insert into each index as 455266733Speter * well 456266733Speter */ 457266733Speter apr_skiplistnode *ni, *li; 458266733Speter li = ret; 459266733Speter for (p = apr_skiplist_getlist(sl->index); p; apr_skiplist_next(sl->index, &p)) { 460266733Speter ni = apr_skiplist_insert((apr_skiplist *) p->data, ret->data); 461266733Speter li->nextindex = ni; 462266733Speter ni->previndex = li; 463266733Speter li = ni; 464266733Speter } 465266733Speter } 466266733Speter else { 467266733Speter /* sl->size++; */ 468266733Speter } 469266733Speter sl->size++; 470266733Speter return ret; 471266733Speter} 472266733Speter 473266733SpeterAPR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree) 474266733Speter{ 475266733Speter if (!sl->compare) { 476266733Speter return 0; 477266733Speter } 478266733Speter return apr_skiplist_remove_compare(sl, data, myfree, sl->comparek); 479266733Speter} 480266733Speter 481266733Speter#if 0 482266733Spetervoid skiplist_print_struct(apr_skiplist * sl, char *prefix) 483266733Speter{ 484266733Speter apr_skiplistnode *p, *q; 485266733Speter fprintf(stderr, "Skiplist Structure (height: %d)\n", sl->height); 486266733Speter p = sl->bottom; 487266733Speter while (p) { 488266733Speter q = p; 489266733Speter fprintf(stderr, prefix); 490266733Speter while (q) { 491266733Speter fprintf(stderr, "%p ", q->data); 492266733Speter q = q->up; 493266733Speter } 494266733Speter fprintf(stderr, "\n"); 495266733Speter p = p->next; 496266733Speter } 497266733Speter} 498266733Speter#endif 499266733Speter 500266733Speterstatic int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, apr_skiplist_freefunc myfree) 501266733Speter{ 502266733Speter apr_skiplistnode *p; 503266733Speter if (!m) { 504266733Speter return 0; 505266733Speter } 506266733Speter if (m->nextindex) { 507266733Speter skiplisti_remove(m->nextindex->sl, m->nextindex, NULL); 508266733Speter } 509266733Speter while (m->up) { 510266733Speter m = m->up; 511266733Speter } 512266733Speter while (m) { 513266733Speter p = m; 514266733Speter p->prev->next = p->next;/* take me out of the list */ 515266733Speter if (p->next) { 516266733Speter p->next->prev = p->prev; /* take me out of the list */ 517266733Speter } 518266733Speter m = m->down; 519266733Speter /* This only frees the actual data in the bottom one */ 520266733Speter if (!m && myfree && p->data) { 521266733Speter myfree(p->data); 522266733Speter } 523266733Speter apr_skiplist_free(sl, p); 524266733Speter } 525266733Speter sl->size--; 526266733Speter while (sl->top && sl->top->next == NULL) { 527266733Speter /* While the row is empty and we are not on the bottom row */ 528266733Speter p = sl->top; 529266733Speter sl->top = sl->top->down;/* Move top down one */ 530266733Speter if (sl->top) { 531266733Speter sl->top->up = NULL; /* Make it think its the top */ 532266733Speter } 533266733Speter apr_skiplist_free(sl, p); 534266733Speter sl->height--; 535266733Speter } 536266733Speter if (!sl->top) { 537266733Speter sl->bottom = NULL; 538266733Speter } 539266733Speter return sl->height; /* return 1; ?? */ 540266733Speter} 541266733Speter 542266733SpeterAPR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli, 543266733Speter void *data, 544266733Speter apr_skiplist_freefunc myfree, apr_skiplist_compare comp) 545266733Speter{ 546266733Speter apr_skiplistnode *m; 547266733Speter apr_skiplist *sl; 548266733Speter if (comp == sli->comparek || !sli->index) { 549266733Speter sl = sli; 550266733Speter } 551266733Speter else { 552266733Speter apr_skiplist_find(sli->index, (void *)comp, &m); 553266733Speter sl = (apr_skiplist *) m->data; 554266733Speter } 555266733Speter skiplisti_find_compare(sl, data, &m, comp); 556266733Speter if (!m) { 557266733Speter return 0; 558266733Speter } 559266733Speter while (m->previndex) { 560266733Speter m = m->previndex; 561266733Speter } 562266733Speter return skiplisti_remove(sl, m, myfree); 563266733Speter} 564266733Speter 565266733SpeterAPR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree) 566266733Speter{ 567266733Speter /* 568266733Speter * This must remove even the place holder nodes (bottom though top) 569266733Speter * because we specify in the API that one can free the Skiplist after 570266733Speter * making this call without memory leaks 571266733Speter */ 572266733Speter apr_skiplistnode *m, *p, *u; 573266733Speter m = sl->bottom; 574266733Speter while (m) { 575266733Speter p = m->next; 576266733Speter if (p && myfree && p->data) 577266733Speter myfree(p->data); 578266733Speter while (m) { 579266733Speter u = m->up; 580266733Speter apr_skiplist_free(sl, p); 581266733Speter m = u; 582266733Speter } 583266733Speter m = p; 584266733Speter } 585266733Speter sl->top = sl->bottom = NULL; 586266733Speter sl->height = 0; 587266733Speter sl->size = 0; 588266733Speter} 589266733Speter 590266733SpeterAPR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *a, apr_skiplist_freefunc myfree) 591266733Speter{ 592266733Speter apr_skiplistnode *sln; 593266733Speter void *data = NULL; 594266733Speter sln = apr_skiplist_getlist(a); 595266733Speter if (sln) { 596266733Speter data = sln->data; 597266733Speter skiplisti_remove(a, sln, myfree); 598266733Speter } 599266733Speter return data; 600266733Speter} 601266733Speter 602266733SpeterAPR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *a) 603266733Speter{ 604266733Speter apr_skiplistnode *sln; 605266733Speter sln = apr_skiplist_getlist(a); 606266733Speter if (sln) { 607266733Speter return sln->data; 608266733Speter } 609266733Speter return NULL; 610266733Speter} 611266733Speter 612266733Speterstatic void skiplisti_destroy(void *vsl) 613266733Speter{ 614266733Speter apr_skiplist_destroy((apr_skiplist *) vsl, NULL); 615266733Speter apr_skiplist_free((apr_skiplist *) vsl, vsl); 616266733Speter} 617266733Speter 618266733SpeterAPR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree) 619266733Speter{ 620266733Speter while (apr_skiplist_pop(sl->index, skiplisti_destroy) != NULL) 621266733Speter ; 622266733Speter apr_skiplist_remove_all(sl, myfree); 623266733Speter} 624266733Speter 625266733SpeterAPR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2) 626266733Speter{ 627266733Speter /* Check integrity! */ 628266733Speter apr_skiplist temp; 629266733Speter struct apr_skiplistnode *b2; 630266733Speter if (sl1->bottomend == NULL || sl1->bottomend->prev == NULL) { 631266733Speter apr_skiplist_remove_all(sl1, NULL); 632266733Speter temp = *sl1; 633266733Speter *sl1 = *sl2; 634266733Speter *sl2 = temp; 635266733Speter /* swap them so that sl2 can be freed normally upon return. */ 636266733Speter return sl1; 637266733Speter } 638266733Speter if(sl2->bottom == NULL || sl2->bottom->next == NULL) { 639266733Speter apr_skiplist_remove_all(sl2, NULL); 640266733Speter return sl1; 641266733Speter } 642266733Speter /* This is what makes it brute force... Just insert :/ */ 643266733Speter b2 = apr_skiplist_getlist(sl2); 644266733Speter while (b2) { 645266733Speter apr_skiplist_insert(sl1, b2->data); 646266733Speter apr_skiplist_next(sl2, &b2); 647266733Speter } 648266733Speter apr_skiplist_remove_all(sl2, NULL); 649266733Speter return sl1; 650266733Speter} 651