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 28289166Spetertypedef struct { 29289166Speter apr_skiplistnode **data; 30289166Speter size_t size, pos; 31289166Speter apr_pool_t *p; 32289166Speter} apr_skiplist_q; 33289166Speter 34266733Speterstruct apr_skiplist { 35266733Speter apr_skiplist_compare compare; 36266733Speter apr_skiplist_compare comparek; 37266733Speter int height; 38266733Speter int preheight; 39289166Speter size_t size; 40266733Speter apr_skiplistnode *top; 41266733Speter apr_skiplistnode *bottom; 42266733Speter /* These two are needed for appending */ 43266733Speter apr_skiplistnode *topend; 44266733Speter apr_skiplistnode *bottomend; 45266733Speter apr_skiplist *index; 46266733Speter apr_array_header_t *memlist; 47289166Speter apr_skiplist_q nodes_q, 48289166Speter stack_q; 49266733Speter apr_pool_t *pool; 50266733Speter}; 51266733Speter 52266733Speterstruct apr_skiplistnode { 53266733Speter void *data; 54266733Speter apr_skiplistnode *next; 55266733Speter apr_skiplistnode *prev; 56266733Speter apr_skiplistnode *down; 57266733Speter apr_skiplistnode *up; 58266733Speter apr_skiplistnode *previndex; 59266733Speter apr_skiplistnode *nextindex; 60266733Speter apr_skiplist *sl; 61266733Speter}; 62266733Speter 63266733Speterstatic int get_b_rand(void) 64266733Speter{ 65266733Speter static int ph = 32; /* More bits than we will ever use */ 66289166Speter static int randseq; 67266733Speter if (ph > 31) { /* Num bits in return of rand() */ 68266733Speter ph = 0; 69289166Speter randseq = rand(); 70266733Speter } 71289166Speter return randseq & (1 << ph++); 72266733Speter} 73266733Speter 74266733Spetertypedef struct { 75266733Speter size_t size; 76266733Speter apr_array_header_t *list; 77266733Speter} memlist_t; 78266733Speter 79266733Spetertypedef struct { 80266733Speter void *ptr; 81266733Speter char inuse; 82266733Speter} chunk_t; 83266733Speter 84266733SpeterAPR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size) 85266733Speter{ 86266733Speter if (sl->pool) { 87266733Speter void *ptr; 88266733Speter int found_size = 0; 89266733Speter int i; 90266733Speter chunk_t *newchunk; 91266733Speter memlist_t *memlist = (memlist_t *)sl->memlist->elts; 92266733Speter for (i = 0; i < sl->memlist->nelts; i++) { 93266733Speter if (memlist->size == size) { 94266733Speter int j; 95266733Speter chunk_t *chunk = (chunk_t *)memlist->list->elts; 96266733Speter found_size = 1; 97266733Speter for (j = 0; j < memlist->list->nelts; j++) { 98266733Speter if (!chunk->inuse) { 99266733Speter chunk->inuse = 1; 100266733Speter return chunk->ptr; 101266733Speter } 102266733Speter chunk++; 103266733Speter } 104266733Speter break; /* no free of this size; punt */ 105266733Speter } 106266733Speter memlist++; 107266733Speter } 108266733Speter /* no free chunks */ 109289166Speter ptr = apr_palloc(sl->pool, size); 110266733Speter if (!ptr) { 111266733Speter return ptr; 112266733Speter } 113266733Speter /* 114266733Speter * is this a new sized chunk? If so, we need to create a new 115266733Speter * array of them. Otherwise, re-use what we already have. 116266733Speter */ 117266733Speter if (!found_size) { 118266733Speter memlist = apr_array_push(sl->memlist); 119266733Speter memlist->size = size; 120266733Speter memlist->list = apr_array_make(sl->pool, 20, sizeof(chunk_t)); 121266733Speter } 122266733Speter newchunk = apr_array_push(memlist->list); 123266733Speter newchunk->ptr = ptr; 124266733Speter newchunk->inuse = 1; 125266733Speter return ptr; 126266733Speter } 127266733Speter else { 128289166Speter return malloc(size); 129266733Speter } 130266733Speter} 131266733Speter 132266733SpeterAPR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem) 133266733Speter{ 134266733Speter if (!sl->pool) { 135266733Speter free(mem); 136266733Speter } 137266733Speter else { 138266733Speter int i; 139266733Speter memlist_t *memlist = (memlist_t *)sl->memlist->elts; 140266733Speter for (i = 0; i < sl->memlist->nelts; i++) { 141266733Speter int j; 142266733Speter chunk_t *chunk = (chunk_t *)memlist->list->elts; 143266733Speter for (j = 0; j < memlist->list->nelts; j++) { 144266733Speter if (chunk->ptr == mem) { 145266733Speter chunk->inuse = 0; 146266733Speter return; 147266733Speter } 148266733Speter chunk++; 149266733Speter } 150266733Speter memlist++; 151266733Speter } 152266733Speter } 153266733Speter} 154266733Speter 155289166Speterstatic apr_status_t skiplist_qpush(apr_skiplist_q *q, apr_skiplistnode *m) 156289166Speter{ 157289166Speter if (q->pos >= q->size) { 158289166Speter apr_skiplistnode **data; 159289166Speter size_t size = (q->pos) ? q->pos * 2 : 32; 160289166Speter if (q->p) { 161289166Speter data = apr_palloc(q->p, size * sizeof(*data)); 162289166Speter if (data) { 163289166Speter memcpy(data, q->data, q->pos * sizeof(*data)); 164289166Speter } 165289166Speter } 166289166Speter else { 167289166Speter data = realloc(q->data, size * sizeof(*data)); 168289166Speter } 169289166Speter if (!data) { 170289166Speter return APR_ENOMEM; 171289166Speter } 172289166Speter q->data = data; 173289166Speter q->size = size; 174289166Speter } 175289166Speter q->data[q->pos++] = m; 176289166Speter return APR_SUCCESS; 177289166Speter} 178289166Speter 179289166Speterstatic APR_INLINE apr_skiplistnode *skiplist_qpop(apr_skiplist_q *q) 180289166Speter{ 181289166Speter return (q->pos > 0) ? q->data[--q->pos] : NULL; 182289166Speter} 183289166Speter 184289166Speterstatic APR_INLINE void skiplist_qclear(apr_skiplist_q *q) 185289166Speter{ 186289166Speter q->pos = 0; 187289166Speter} 188289166Speter 189289166Speterstatic apr_skiplistnode *skiplist_new_node(apr_skiplist *sl) 190289166Speter{ 191289166Speter apr_skiplistnode *m = skiplist_qpop(&sl->nodes_q); 192289166Speter if (!m) { 193289166Speter if (sl->pool) { 194289166Speter m = apr_palloc(sl->pool, sizeof *m); 195289166Speter } 196289166Speter else { 197289166Speter m = malloc(sizeof *m); 198289166Speter } 199289166Speter } 200289166Speter return m; 201289166Speter} 202289166Speter 203289166Speterstatic apr_status_t skiplist_free_node(apr_skiplist *sl, apr_skiplistnode *m) 204289166Speter{ 205289166Speter return skiplist_qpush(&sl->nodes_q, m); 206289166Speter} 207289166Speter 208266733Speterstatic apr_status_t skiplisti_init(apr_skiplist **s, apr_pool_t *p) 209266733Speter{ 210266733Speter apr_skiplist *sl; 211266733Speter if (p) { 212266733Speter sl = apr_pcalloc(p, sizeof(apr_skiplist)); 213266733Speter sl->memlist = apr_array_make(p, 20, sizeof(memlist_t)); 214289166Speter sl->pool = sl->nodes_q.p = sl->stack_q.p = p; 215266733Speter } 216266733Speter else { 217266733Speter sl = calloc(1, sizeof(apr_skiplist)); 218289166Speter if (!sl) { 219289166Speter return APR_ENOMEM; 220289166Speter } 221266733Speter } 222266733Speter *s = sl; 223266733Speter return APR_SUCCESS; 224266733Speter} 225266733Speter 226266733Speterstatic int indexing_comp(void *a, void *b) 227266733Speter{ 228266733Speter void *ac = (void *) (((apr_skiplist *) a)->compare); 229266733Speter void *bc = (void *) (((apr_skiplist *) b)->compare); 230266733Speter return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0)); 231266733Speter} 232266733Speter 233266733Speterstatic int indexing_compk(void *ac, void *b) 234266733Speter{ 235266733Speter void *bc = (void *) (((apr_skiplist *) b)->compare); 236266733Speter return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0)); 237266733Speter} 238266733Speter 239266733SpeterAPR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **s, apr_pool_t *p) 240266733Speter{ 241266733Speter apr_skiplist *sl; 242266733Speter skiplisti_init(s, p); 243266733Speter sl = *s; 244266733Speter skiplisti_init(&(sl->index), p); 245266733Speter apr_skiplist_set_compare(sl->index, indexing_comp, indexing_compk); 246266733Speter return APR_SUCCESS; 247266733Speter} 248266733Speter 249266733SpeterAPR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl, 250266733Speter apr_skiplist_compare comp, 251266733Speter apr_skiplist_compare compk) 252266733Speter{ 253266733Speter if (sl->compare && sl->comparek) { 254266733Speter apr_skiplist_add_index(sl, comp, compk); 255266733Speter } 256266733Speter else { 257266733Speter sl->compare = comp; 258266733Speter sl->comparek = compk; 259266733Speter } 260266733Speter} 261266733Speter 262266733SpeterAPR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl, 263266733Speter apr_skiplist_compare comp, 264266733Speter apr_skiplist_compare compk) 265266733Speter{ 266266733Speter apr_skiplistnode *m; 267266733Speter apr_skiplist *ni; 268266733Speter int icount = 0; 269266733Speter apr_skiplist_find(sl->index, (void *)comp, &m); 270266733Speter if (m) { 271266733Speter return; /* Index already there! */ 272266733Speter } 273266733Speter skiplisti_init(&ni, sl->pool); 274266733Speter apr_skiplist_set_compare(ni, comp, compk); 275266733Speter /* Build the new index... This can be expensive! */ 276266733Speter m = apr_skiplist_insert(sl->index, ni); 277266733Speter while (m->prev) { 278266733Speter m = m->prev; 279266733Speter icount++; 280266733Speter } 281266733Speter for (m = apr_skiplist_getlist(sl); m; apr_skiplist_next(sl, &m)) { 282266733Speter int j = icount - 1; 283266733Speter apr_skiplistnode *nsln; 284266733Speter nsln = apr_skiplist_insert(ni, m->data); 285266733Speter /* skip from main index down list */ 286266733Speter while (j > 0) { 287266733Speter m = m->nextindex; 288266733Speter j--; 289266733Speter } 290266733Speter /* insert this node in the indexlist after m */ 291266733Speter nsln->nextindex = m->nextindex; 292266733Speter if (m->nextindex) { 293266733Speter m->nextindex->previndex = nsln; 294266733Speter } 295266733Speter nsln->previndex = m; 296266733Speter m->nextindex = nsln; 297266733Speter } 298266733Speter} 299266733Speter 300266733Speterstatic int skiplisti_find_compare(apr_skiplist *sl, void *data, 301266733Speter apr_skiplistnode **ret, 302266733Speter apr_skiplist_compare comp) 303266733Speter{ 304266733Speter int count = 0; 305289166Speter apr_skiplistnode *m; 306266733Speter m = sl->top; 307266733Speter while (m) { 308289166Speter if (m->next) { 309289166Speter int compared = comp(data, m->next->data); 310289166Speter if (compared == 0) { 311289166Speter m = m->next; 312289166Speter while (m->down) { 313289166Speter m = m->down; 314289166Speter } 315289166Speter *ret = m; 316289166Speter return count; 317266733Speter } 318289166Speter if (compared > 0) { 319289166Speter m = m->next; 320289166Speter count++; 321289166Speter continue; 322289166Speter } 323266733Speter } 324289166Speter m = m->down; 325289166Speter count++; 326266733Speter } 327266733Speter *ret = NULL; 328266733Speter return count; 329266733Speter} 330266733Speter 331266733SpeterAPR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sli, void *data, 332266733Speter apr_skiplistnode **iter, 333266733Speter apr_skiplist_compare comp) 334266733Speter{ 335289166Speter apr_skiplistnode *m; 336266733Speter apr_skiplist *sl; 337289166Speter if (!comp) { 338289166Speter if (iter) { 339289166Speter *iter = NULL; 340289166Speter } 341289166Speter return NULL; 342289166Speter } 343266733Speter if (comp == sli->compare || !sli->index) { 344266733Speter sl = sli; 345266733Speter } 346266733Speter else { 347266733Speter apr_skiplist_find(sli->index, (void *)comp, &m); 348289166Speter if (!m) { 349289166Speter if (iter) { 350289166Speter *iter = NULL; 351289166Speter } 352289166Speter return NULL; 353289166Speter } 354266733Speter sl = (apr_skiplist *) m->data; 355266733Speter } 356289166Speter skiplisti_find_compare(sl, data, &m, sl->comparek); 357289166Speter if (iter) { 358289166Speter *iter = m; 359289166Speter } 360289166Speter return (m) ? m->data : NULL; 361266733Speter} 362266733Speter 363289166SpeterAPR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter) 364289166Speter{ 365289166Speter return apr_skiplist_find_compare(sl, data, iter, sl->compare); 366289166Speter} 367266733Speter 368289166Speter 369289166SpeterAPR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl) 370289166Speter{ 371289166Speter if (!sl->bottom) { 372289166Speter return NULL; 373289166Speter } 374289166Speter return sl->bottom->next; 375289166Speter} 376289166Speter 377266733SpeterAPR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter) 378266733Speter{ 379266733Speter if (!*iter) { 380266733Speter return NULL; 381266733Speter } 382266733Speter *iter = (*iter)->next; 383266733Speter return (*iter) ? ((*iter)->data) : NULL; 384266733Speter} 385266733Speter 386266733SpeterAPR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter) 387266733Speter{ 388266733Speter if (!*iter) { 389266733Speter return NULL; 390266733Speter } 391266733Speter *iter = (*iter)->prev; 392266733Speter return (*iter) ? ((*iter)->data) : NULL; 393266733Speter} 394266733Speter 395289166Speterstatic APR_INLINE int skiplist_height(const apr_skiplist *sl) 396266733Speter{ 397289166Speter /* Skiplists (even empty) always have a top node, although this 398289166Speter * implementation defers its creation until the first insert, or 399289166Speter * deletes it with the last remove. We want the real height here. 400289166Speter */ 401289166Speter return sl->height ? sl->height : 1; 402266733Speter} 403266733Speter 404266733SpeterAPR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data, 405266733Speter apr_skiplist_compare comp) 406266733Speter{ 407289166Speter apr_skiplistnode *m, *p, *tmp, *ret = NULL; 408289166Speter int ch, nh = 1; 409289166Speter 410289166Speter if (!comp) { 411289166Speter return NULL; 412266733Speter } 413289166Speter 414289166Speter ch = skiplist_height(sl); 415266733Speter if (sl->preheight) { 416266733Speter while (nh < sl->preheight && get_b_rand()) { 417266733Speter nh++; 418266733Speter } 419266733Speter } 420266733Speter else { 421289166Speter while (nh <= ch && get_b_rand()) { 422266733Speter nh++; 423266733Speter } 424266733Speter } 425289166Speter 426289166Speter /* Now we have in nh the height at which we wish to insert our new node, 427289166Speter * and in ch the current height: don't create skip paths to the inserted 428289166Speter * element until the walk down through the tree (which decrements ch) 429289166Speter * reaches nh. From there, any walk down pushes the current node on a 430289166Speter * stack (the node(s) after which we would insert) to pop back through 431289166Speter * for insertion later. 432266733Speter */ 433266733Speter m = sl->top; 434266733Speter while (m) { 435266733Speter if (m->next) { 436289166Speter int compared = comp(data, m->next->data); 437289166Speter if (compared == 0) { 438289166Speter /* Keep the existing element(s) */ 439289166Speter skiplist_qclear(&sl->stack_q); 440289166Speter return NULL; 441266733Speter } 442289166Speter if (compared > 0) { 443289166Speter m = m->next; 444289166Speter continue; 445289166Speter } 446266733Speter } 447289166Speter if (ch <= nh) { 448289166Speter /* push on stack */ 449289166Speter skiplist_qpush(&sl->stack_q, m); 450266733Speter } 451289166Speter m = m->down; 452289166Speter ch--; 453266733Speter } 454266733Speter /* Pop the stack and insert nodes */ 455266733Speter p = NULL; 456289166Speter while ((m = skiplist_qpop(&sl->stack_q))) { 457289166Speter tmp = skiplist_new_node(sl); 458266733Speter tmp->next = m->next; 459266733Speter if (m->next) { 460266733Speter m->next->prev = tmp; 461266733Speter } 462289166Speter m->next = tmp; 463266733Speter tmp->prev = m; 464266733Speter tmp->up = NULL; 465266733Speter tmp->nextindex = tmp->previndex = NULL; 466266733Speter tmp->down = p; 467266733Speter if (p) { 468266733Speter p->up = tmp; 469266733Speter } 470289166Speter else { 471289166Speter /* This sets ret to the bottom-most node we are inserting */ 472289166Speter ret = tmp; 473289166Speter } 474266733Speter tmp->data = data; 475266733Speter tmp->sl = sl; 476289166Speter p = tmp; 477289166Speter } 478289166Speter 479289166Speter /* Now we are sure the node is inserted, grow our tree to 'nh' tall */ 480289166Speter for (; sl->height < nh; sl->height++) { 481289166Speter m = skiplist_new_node(sl); 482289166Speter tmp = skiplist_new_node(sl); 483289166Speter m->up = m->prev = m->nextindex = m->previndex = NULL; 484266733Speter m->next = tmp; 485289166Speter m->down = sl->top; 486289166Speter m->data = NULL; 487289166Speter m->sl = sl; 488289166Speter if (sl->top) { 489289166Speter sl->top->up = m; 490289166Speter } 491289166Speter else { 492289166Speter sl->bottom = sl->bottomend = m; 493289166Speter } 494289166Speter sl->top = sl->topend = tmp->prev = m; 495289166Speter tmp->up = tmp->next = tmp->nextindex = tmp->previndex = NULL; 496289166Speter tmp->down = p; 497289166Speter tmp->data = data; 498289166Speter tmp->sl = sl; 499289166Speter if (p) { 500289166Speter p->up = tmp; 501289166Speter } 502289166Speter else { 503289166Speter /* This sets ret to the bottom-most node we are inserting */ 504266733Speter ret = tmp; 505266733Speter } 506266733Speter p = tmp; 507266733Speter } 508266733Speter if (sl->index != NULL) { 509266733Speter /* 510266733Speter * this is a external insertion, we must insert into each index as 511266733Speter * well 512266733Speter */ 513266733Speter apr_skiplistnode *ni, *li; 514266733Speter li = ret; 515266733Speter for (p = apr_skiplist_getlist(sl->index); p; apr_skiplist_next(sl->index, &p)) { 516289166Speter apr_skiplist *sli = (apr_skiplist *)p->data; 517289166Speter ni = apr_skiplist_insert_compare(sli, ret->data, sli->compare); 518266733Speter li->nextindex = ni; 519266733Speter ni->previndex = li; 520266733Speter li = ni; 521266733Speter } 522266733Speter } 523266733Speter sl->size++; 524266733Speter return ret; 525266733Speter} 526266733Speter 527289166SpeterAPR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data) 528266733Speter{ 529289166Speter return apr_skiplist_insert_compare(sl, data, sl->compare); 530266733Speter} 531266733Speter 532266733Speter#if 0 533266733Spetervoid skiplist_print_struct(apr_skiplist * sl, char *prefix) 534266733Speter{ 535266733Speter apr_skiplistnode *p, *q; 536266733Speter fprintf(stderr, "Skiplist Structure (height: %d)\n", sl->height); 537266733Speter p = sl->bottom; 538266733Speter while (p) { 539266733Speter q = p; 540266733Speter fprintf(stderr, prefix); 541266733Speter while (q) { 542266733Speter fprintf(stderr, "%p ", q->data); 543266733Speter q = q->up; 544266733Speter } 545266733Speter fprintf(stderr, "\n"); 546266733Speter p = p->next; 547266733Speter } 548266733Speter} 549266733Speter#endif 550266733Speter 551266733Speterstatic int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, apr_skiplist_freefunc myfree) 552266733Speter{ 553266733Speter apr_skiplistnode *p; 554266733Speter if (!m) { 555266733Speter return 0; 556266733Speter } 557266733Speter if (m->nextindex) { 558266733Speter skiplisti_remove(m->nextindex->sl, m->nextindex, NULL); 559266733Speter } 560266733Speter while (m->up) { 561266733Speter m = m->up; 562266733Speter } 563266733Speter while (m) { 564266733Speter p = m; 565266733Speter p->prev->next = p->next;/* take me out of the list */ 566266733Speter if (p->next) { 567266733Speter p->next->prev = p->prev; /* take me out of the list */ 568266733Speter } 569266733Speter m = m->down; 570266733Speter /* This only frees the actual data in the bottom one */ 571266733Speter if (!m && myfree && p->data) { 572266733Speter myfree(p->data); 573266733Speter } 574289166Speter skiplist_free_node(sl, p); 575266733Speter } 576266733Speter sl->size--; 577266733Speter while (sl->top && sl->top->next == NULL) { 578266733Speter /* While the row is empty and we are not on the bottom row */ 579266733Speter p = sl->top; 580266733Speter sl->top = sl->top->down;/* Move top down one */ 581266733Speter if (sl->top) { 582266733Speter sl->top->up = NULL; /* Make it think its the top */ 583266733Speter } 584289166Speter skiplist_free_node(sl, p); 585266733Speter sl->height--; 586266733Speter } 587266733Speter if (!sl->top) { 588289166Speter sl->bottom = sl->bottomend = NULL; 589289166Speter sl->topend = NULL; 590266733Speter } 591289166Speter return skiplist_height(sl); 592266733Speter} 593266733Speter 594266733SpeterAPR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli, 595266733Speter void *data, 596266733Speter apr_skiplist_freefunc myfree, apr_skiplist_compare comp) 597266733Speter{ 598266733Speter apr_skiplistnode *m; 599266733Speter apr_skiplist *sl; 600289166Speter if (!comp) { 601289166Speter return 0; 602289166Speter } 603266733Speter if (comp == sli->comparek || !sli->index) { 604266733Speter sl = sli; 605266733Speter } 606266733Speter else { 607266733Speter apr_skiplist_find(sli->index, (void *)comp, &m); 608289166Speter if (!m) { 609289166Speter return 0; 610289166Speter } 611266733Speter sl = (apr_skiplist *) m->data; 612266733Speter } 613266733Speter skiplisti_find_compare(sl, data, &m, comp); 614266733Speter if (!m) { 615266733Speter return 0; 616266733Speter } 617266733Speter while (m->previndex) { 618266733Speter m = m->previndex; 619266733Speter } 620266733Speter return skiplisti_remove(sl, m, myfree); 621266733Speter} 622266733Speter 623289166SpeterAPR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree) 624289166Speter{ 625289166Speter return apr_skiplist_remove_compare(sl, data, myfree, sl->comparek); 626289166Speter} 627289166Speter 628266733SpeterAPR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree) 629266733Speter{ 630266733Speter /* 631266733Speter * This must remove even the place holder nodes (bottom though top) 632266733Speter * because we specify in the API that one can free the Skiplist after 633266733Speter * making this call without memory leaks 634266733Speter */ 635266733Speter apr_skiplistnode *m, *p, *u; 636266733Speter m = sl->bottom; 637266733Speter while (m) { 638266733Speter p = m->next; 639289166Speter if (myfree && p && p->data) { 640266733Speter myfree(p->data); 641289166Speter } 642289166Speter do { 643266733Speter u = m->up; 644289166Speter skiplist_free_node(sl, m); 645266733Speter m = u; 646289166Speter } while (m); 647266733Speter m = p; 648266733Speter } 649266733Speter sl->top = sl->bottom = NULL; 650289166Speter sl->topend = sl->bottomend = NULL; 651266733Speter sl->height = 0; 652266733Speter sl->size = 0; 653266733Speter} 654266733Speter 655266733SpeterAPR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *a, apr_skiplist_freefunc myfree) 656266733Speter{ 657266733Speter apr_skiplistnode *sln; 658266733Speter void *data = NULL; 659266733Speter sln = apr_skiplist_getlist(a); 660266733Speter if (sln) { 661266733Speter data = sln->data; 662266733Speter skiplisti_remove(a, sln, myfree); 663266733Speter } 664266733Speter return data; 665266733Speter} 666266733Speter 667266733SpeterAPR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *a) 668266733Speter{ 669266733Speter apr_skiplistnode *sln; 670266733Speter sln = apr_skiplist_getlist(a); 671266733Speter if (sln) { 672266733Speter return sln->data; 673266733Speter } 674266733Speter return NULL; 675266733Speter} 676266733Speter 677266733Speterstatic void skiplisti_destroy(void *vsl) 678266733Speter{ 679289166Speter apr_skiplist_destroy(vsl, NULL); 680266733Speter} 681266733Speter 682266733SpeterAPR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree) 683266733Speter{ 684266733Speter while (apr_skiplist_pop(sl->index, skiplisti_destroy) != NULL) 685266733Speter ; 686266733Speter apr_skiplist_remove_all(sl, myfree); 687289166Speter if (!sl->pool) { 688289166Speter while (sl->nodes_q.pos) 689289166Speter free(sl->nodes_q.data[--sl->nodes_q.pos]); 690289166Speter free(sl->nodes_q.data); 691289166Speter free(sl->stack_q.data); 692289166Speter free(sl); 693289166Speter } 694266733Speter} 695266733Speter 696266733SpeterAPR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2) 697266733Speter{ 698266733Speter /* Check integrity! */ 699266733Speter apr_skiplist temp; 700266733Speter struct apr_skiplistnode *b2; 701266733Speter if (sl1->bottomend == NULL || sl1->bottomend->prev == NULL) { 702266733Speter apr_skiplist_remove_all(sl1, NULL); 703266733Speter temp = *sl1; 704266733Speter *sl1 = *sl2; 705266733Speter *sl2 = temp; 706266733Speter /* swap them so that sl2 can be freed normally upon return. */ 707266733Speter return sl1; 708266733Speter } 709266733Speter if(sl2->bottom == NULL || sl2->bottom->next == NULL) { 710266733Speter apr_skiplist_remove_all(sl2, NULL); 711266733Speter return sl1; 712266733Speter } 713266733Speter /* This is what makes it brute force... Just insert :/ */ 714266733Speter b2 = apr_skiplist_getlist(sl2); 715266733Speter while (b2) { 716266733Speter apr_skiplist_insert(sl1, b2->data); 717266733Speter apr_skiplist_next(sl2, &b2); 718266733Speter } 719266733Speter apr_skiplist_remove_all(sl2, NULL); 720266733Speter return sl1; 721266733Speter} 722