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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
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.
26 #include "apr_skiplist.h"
29 apr_skiplistnode **data;
35 apr_skiplist_compare compare;
36 apr_skiplist_compare comparek;
40 apr_skiplistnode *top;
41 apr_skiplistnode *bottom;
42 /* These two are needed for appending */
43 apr_skiplistnode *topend;
44 apr_skiplistnode *bottomend;
46 apr_array_header_t *memlist;
47 apr_skiplist_q nodes_q,
52 struct apr_skiplistnode {
54 apr_skiplistnode *next;
55 apr_skiplistnode *prev;
56 apr_skiplistnode *down;
58 apr_skiplistnode *previndex;
59 apr_skiplistnode *nextindex;
63 static int get_b_rand(void)
65 static int ph = 32; /* More bits than we will ever use */
67 if (ph > 31) { /* Num bits in return of rand() */
71 return randseq & (1 << ph++);
76 apr_array_header_t *list;
84 APR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size)
91 memlist_t *memlist = (memlist_t *)sl->memlist->elts;
92 for (i = 0; i < sl->memlist->nelts; i++) {
93 if (memlist->size == size) {
95 chunk_t *chunk = (chunk_t *)memlist->list->elts;
97 for (j = 0; j < memlist->list->nelts; j++) {
104 break; /* no free of this size; punt */
109 ptr = apr_palloc(sl->pool, size);
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.
118 memlist = apr_array_push(sl->memlist);
119 memlist->size = size;
120 memlist->list = apr_array_make(sl->pool, 20, sizeof(chunk_t));
122 newchunk = apr_array_push(memlist->list);
132 APR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem)
139 memlist_t *memlist = (memlist_t *)sl->memlist->elts;
140 for (i = 0; i < sl->memlist->nelts; i++) {
142 chunk_t *chunk = (chunk_t *)memlist->list->elts;
143 for (j = 0; j < memlist->list->nelts; j++) {
144 if (chunk->ptr == mem) {
155 static apr_status_t skiplist_qpush(apr_skiplist_q *q, apr_skiplistnode *m)
157 if (q->pos >= q->size) {
158 apr_skiplistnode **data;
159 size_t size = (q->pos) ? q->pos * 2 : 32;
161 data = apr_palloc(q->p, size * sizeof(*data));
163 memcpy(data, q->data, q->pos * sizeof(*data));
167 data = realloc(q->data, size * sizeof(*data));
175 q->data[q->pos++] = m;
179 static APR_INLINE apr_skiplistnode *skiplist_qpop(apr_skiplist_q *q)
181 return (q->pos > 0) ? q->data[--q->pos] : NULL;
184 static APR_INLINE void skiplist_qclear(apr_skiplist_q *q)
189 static apr_skiplistnode *skiplist_new_node(apr_skiplist *sl)
191 apr_skiplistnode *m = skiplist_qpop(&sl->nodes_q);
194 m = apr_palloc(sl->pool, sizeof *m);
197 m = malloc(sizeof *m);
203 static apr_status_t skiplist_free_node(apr_skiplist *sl, apr_skiplistnode *m)
205 return skiplist_qpush(&sl->nodes_q, m);
208 static apr_status_t skiplisti_init(apr_skiplist **s, apr_pool_t *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;
217 sl = calloc(1, sizeof(apr_skiplist));
226 static int indexing_comp(void *a, void *b)
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));
233 static int indexing_compk(void *ac, void *b)
235 void *bc = (void *) (((apr_skiplist *) b)->compare);
236 return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0));
239 APR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **s, apr_pool_t *p)
242 skiplisti_init(s, p);
244 skiplisti_init(&(sl->index), p);
245 apr_skiplist_set_compare(sl->index, indexing_comp, indexing_compk);
249 APR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl,
250 apr_skiplist_compare comp,
251 apr_skiplist_compare compk)
253 if (sl->compare && sl->comparek) {
254 apr_skiplist_add_index(sl, comp, compk);
258 sl->comparek = compk;
262 APR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl,
263 apr_skiplist_compare comp,
264 apr_skiplist_compare compk)
269 apr_skiplist_find(sl->index, (void *)comp, &m);
271 return; /* Index already there! */
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);
281 for (m = apr_skiplist_getlist(sl); m; apr_skiplist_next(sl, &m)) {
283 apr_skiplistnode *nsln;
284 nsln = apr_skiplist_insert(ni, m->data);
285 /* skip from main index down list */
290 /* insert this node in the indexlist after m */
291 nsln->nextindex = m->nextindex;
293 m->nextindex->previndex = nsln;
300 static int skiplisti_find_compare(apr_skiplist *sl, void *data,
301 apr_skiplistnode **ret,
302 apr_skiplist_compare comp)
309 int compared = comp(data, m->next->data);
331 APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sli, void *data,
332 apr_skiplistnode **iter,
333 apr_skiplist_compare comp)
343 if (comp == sli->compare || !sli->index) {
347 apr_skiplist_find(sli->index, (void *)comp, &m);
354 sl = (apr_skiplist *) m->data;
356 skiplisti_find_compare(sl, data, &m, sl->comparek);
360 return (m) ? m->data : NULL;
363 APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter)
365 return apr_skiplist_find_compare(sl, data, iter, sl->compare);
369 APR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl)
374 return sl->bottom->next;
377 APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter)
382 *iter = (*iter)->next;
383 return (*iter) ? ((*iter)->data) : NULL;
386 APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter)
391 *iter = (*iter)->prev;
392 return (*iter) ? ((*iter)->data) : NULL;
395 static APR_INLINE int skiplist_height(const apr_skiplist *sl)
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.
401 return sl->height ? sl->height : 1;
404 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
405 apr_skiplist_compare comp)
407 apr_skiplistnode *m, *p, *tmp, *ret = NULL;
414 ch = skiplist_height(sl);
416 while (nh < sl->preheight && get_b_rand()) {
421 while (nh <= ch && get_b_rand()) {
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.
436 int compared = comp(data, m->next->data);
438 /* Keep the existing element(s) */
439 skiplist_qclear(&sl->stack_q);
449 skiplist_qpush(&sl->stack_q, m);
454 /* Pop the stack and insert nodes */
456 while ((m = skiplist_qpop(&sl->stack_q))) {
457 tmp = skiplist_new_node(sl);
465 tmp->nextindex = tmp->previndex = NULL;
471 /* This sets ret to the bottom-most node we are inserting */
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;
492 sl->bottom = sl->bottomend = m;
494 sl->top = sl->topend = tmp->prev = m;
495 tmp->up = tmp->next = tmp->nextindex = tmp->previndex = NULL;
503 /* This sets ret to the bottom-most node we are inserting */
508 if (sl->index != NULL) {
510 * this is a external insertion, we must insert into each index as
513 apr_skiplistnode *ni, *li;
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);
527 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
529 return apr_skiplist_insert_compare(sl, data, sl->compare);
533 void skiplist_print_struct(apr_skiplist * sl, char *prefix)
535 apr_skiplistnode *p, *q;
536 fprintf(stderr, "Skiplist Structure (height: %d)\n", sl->height);
540 fprintf(stderr, prefix);
542 fprintf(stderr, "%p ", q->data);
545 fprintf(stderr, "\n");
551 static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, apr_skiplist_freefunc myfree)
558 skiplisti_remove(m->nextindex->sl, m->nextindex, NULL);
565 p->prev->next = p->next;/* take me out of the list */
567 p->next->prev = p->prev; /* take me out of the list */
570 /* This only frees the actual data in the bottom one */
571 if (!m && myfree && p->data) {
574 skiplist_free_node(sl, p);
577 while (sl->top && sl->top->next == NULL) {
578 /* While the row is empty and we are not on the bottom row */
580 sl->top = sl->top->down;/* Move top down one */
582 sl->top->up = NULL; /* Make it think its the top */
584 skiplist_free_node(sl, p);
588 sl->bottom = sl->bottomend = NULL;
591 return skiplist_height(sl);
594 APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli,
596 apr_skiplist_freefunc myfree, apr_skiplist_compare comp)
603 if (comp == sli->comparek || !sli->index) {
607 apr_skiplist_find(sli->index, (void *)comp, &m);
611 sl = (apr_skiplist *) m->data;
613 skiplisti_find_compare(sl, data, &m, comp);
617 while (m->previndex) {
620 return skiplisti_remove(sl, m, myfree);
623 APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree)
625 return apr_skiplist_remove_compare(sl, data, myfree, sl->comparek);
628 APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree)
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
635 apr_skiplistnode *m, *p, *u;
639 if (myfree && p && p->data) {
644 skiplist_free_node(sl, m);
649 sl->top = sl->bottom = NULL;
650 sl->topend = sl->bottomend = NULL;
655 APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *a, apr_skiplist_freefunc myfree)
657 apr_skiplistnode *sln;
659 sln = apr_skiplist_getlist(a);
662 skiplisti_remove(a, sln, myfree);
667 APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *a)
669 apr_skiplistnode *sln;
670 sln = apr_skiplist_getlist(a);
677 static void skiplisti_destroy(void *vsl)
679 apr_skiplist_destroy(vsl, NULL);
682 APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree)
684 while (apr_skiplist_pop(sl->index, skiplisti_destroy) != NULL)
686 apr_skiplist_remove_all(sl, myfree);
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);
696 APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2)
698 /* Check integrity! */
700 struct apr_skiplistnode *b2;
701 if (sl1->bottomend == NULL || sl1->bottomend->prev == NULL) {
702 apr_skiplist_remove_all(sl1, NULL);
706 /* swap them so that sl2 can be freed normally upon return. */
709 if(sl2->bottom == NULL || sl2->bottom->next == NULL) {
710 apr_skiplist_remove_all(sl2, NULL);
713 /* This is what makes it brute force... Just insert :/ */
714 b2 = apr_skiplist_getlist(sl2);
716 apr_skiplist_insert(sl1, b2->data);
717 apr_skiplist_next(sl2, &b2);
719 apr_skiplist_remove_all(sl2, NULL);