« back to all changes in this revision
Viewing changes to tables/apr_skiplist.c
- browse files at revision 31
- compare with another revision
- download diff
- download tarball
- view history from revision 31
- Committer: Package Import Robot
- Author(s): Stefan Fritsch
- Date: 2015-08-15 16:39:04 UTC
- mfrom: (1.1.15)
- Revision ID: package-import@ubuntu.com-20150815163904-jfdhk06aaikcsznf
Tags: 1.5.2-1
* New upstream version
* Don't ship useless *.md5 doxygen files.
* Bump Standards-Version (no changes)
* Don't ship useless *.md5 doxygen files.
* Bump Standards-Version (no changes)
- files added:
- test/testskiplist.c
- files removed:
- .pc/buildfix_r1589984
- files modified:
- .pc/applied-patches
added
removed
tables/apr_skiplist.c
25
25
26
26
#include "apr_skiplist.h"
27
27
28
typedef struct {
29
apr_skiplistnode **data;
30
size_t size, pos;
31
apr_pool_t *p;
32
} apr_skiplist_q;
33
28
34
struct apr_skiplist {
29
35
apr_skiplist_compare compare;
30
36
apr_skiplist_compare comparek;
31
37
int height;
32
38
int preheight;
33
int size;
39
size_t size;
34
40
apr_skiplistnode *top;
35
41
apr_skiplistnode *bottom;
36
42
/* These two are needed for appending */
38
44
apr_skiplistnode *bottomend;
39
45
apr_skiplist *index;
40
46
apr_array_header_t *memlist;
47
apr_skiplist_q nodes_q,
48
stack_q;
41
49
apr_pool_t *pool;
42
50
};
43
51
52
60
apr_skiplist *sl;
53
61
};
54
62
55
#ifndef MIN
56
#define MIN(a,b) ((a<b)?(a):(b))
57
#endif
58
59
63
static int get_b_rand(void)
60
64
{
61
65
static int ph = 32; /* More bits than we will ever use */
62
static apr_uint32_t randseq;
66
static int randseq;
63
67
if (ph > 31) { /* Num bits in return of rand() */
64
68
ph = 0;
65
randseq = (apr_uint32_t) rand();
69
randseq = rand();
66
70
}
67
ph++;
68
return ((randseq & (1 << (ph - 1))) >> (ph - 1));
71
return randseq & (1 << ph++);
69
72
}
70
73
71
74
typedef struct {
103
106
memlist++;
104
107
}
105
108
/* no free chunks */
106
ptr = apr_pcalloc(sl->pool, size);
109
ptr = apr_palloc(sl->pool, size);
107
110
if (!ptr) {
108
111
return ptr;
109
112
}
122
125
return ptr;
123
126
}
124
127
else {
125
return calloc(1, size);
128
return malloc(size);
126
129
}
127
130
}
128
131
149
152
}
150
153
}
151
154
155
static 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
179
static APR_INLINE apr_skiplistnode *skiplist_qpop(apr_skiplist_q *q)
180
{
181
return (q->pos > 0) ? q->data[--q->pos] : NULL;
182
}
183
184
static APR_INLINE void skiplist_qclear(apr_skiplist_q *q)
185
{
186
q->pos = 0;
187
}
188
189
static 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
203
static apr_status_t skiplist_free_node(apr_skiplist *sl, apr_skiplistnode *m)
204
{
205
return skiplist_qpush(&sl->nodes_q, m);
206
}
207
152
208
static apr_status_t skiplisti_init(apr_skiplist **s, apr_pool_t *p)
153
209
{
154
210
apr_skiplist *sl;
155
211
if (p) {
156
212
sl = apr_pcalloc(p, sizeof(apr_skiplist));
157
213
sl->memlist = apr_array_make(p, 20, sizeof(memlist_t));
214
sl->pool = sl->nodes_q.p = sl->stack_q.p = p;
158
215
}
159
216
else {
160
217
sl = calloc(1, sizeof(apr_skiplist));
218
if (!sl) {
219
return APR_ENOMEM;
220
}
161
221
}
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
222
*s = sl;
174
223
return APR_SUCCESS;
175
224
}
248
297
}
249
298
}
250
299
251
APR_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
259
APR_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
275
300
static int skiplisti_find_compare(apr_skiplist *sl, void *data,
276
301
apr_skiplistnode **ret,
277
302
apr_skiplist_compare comp)
278
303
{
279
apr_skiplistnode *m = NULL;
280
304
int count = 0;
305
apr_skiplistnode *m;
281
306
m = sl->top;
282
307
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
}
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++;
301
326
}
302
327
*ret = NULL;
303
328
return count;
307
332
apr_skiplistnode **iter,
308
333
apr_skiplist_compare comp)
309
334
{
310
apr_skiplistnode *m = NULL;
335
apr_skiplistnode *m;
311
336
apr_skiplist *sl;
337
if (!comp) {
338
if (iter) {
339
*iter = NULL;
340
}
341
return NULL;
342
}
312
343
if (comp == sli->compare || !sli->index) {
313
344
sl = sli;
314
345
}
315
346
else {
316
347
apr_skiplist_find(sli->index, (void *)comp, &m);
348
if (!m) {
349
if (iter) {
350
*iter = NULL;
351
}
352
return NULL;
353
}
317
354
sl = (apr_skiplist *) m->data;
318
355
}
319
skiplisti_find_compare(sl, data, iter, sl->comparek);
320
return (iter && *iter) ? ((*iter)->data) : NULL;
321
}
322
356
skiplisti_find_compare(sl, data, &m, sl->comparek);
357
if (iter) {
358
*iter = m;
359
}
360
return (m) ? m->data : NULL;
361
}
362
363
APR_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
369
APR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl)
370
{
371
if (!sl->bottom) {
372
return NULL;
373
}
374
return sl->bottom->next;
375
}
323
376
324
377
APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter)
325
378
{
339
392
return (*iter) ? ((*iter)->data) : NULL;
340
393
}
341
394
342
APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
395
static APR_INLINE int skiplist_height(const apr_skiplist *sl)
343
396
{
344
if (!sl->compare) {
345
return 0;
346
}
347
return apr_skiplist_insert_compare(sl, data, sl->compare);
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;
348
402
}
349
403
350
404
APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
351
405
apr_skiplist_compare comp)
352
406
{
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;
407
apr_skiplistnode *m, *p, *tmp, *ret = NULL;
408
int ch, nh = 1;
409
410
if (!comp) {
411
return NULL;
369
412
}
413
414
ch = skiplist_height(sl);
370
415
if (sl->preheight) {
371
416
while (nh < sl->preheight && get_b_rand()) {
372
417
nh++;
373
418
}
374
419
}
375
420
else {
376
while (nh <= sl->height && get_b_rand()) {
421
while (nh <= ch && get_b_rand()) {
377
422
nh++;
378
423
}
379
424
}
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)
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.
384
432
*/
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
433
m = sl->top;
402
stack = (apr_skiplistnode **)malloc(sizeof(apr_skiplistnode *) * (nh));
403
stacki = 0;
404
434
while (m) {
405
int compared = -1;
406
435
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
}
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--;
424
453
}
425
454
/* Pop the stack and insert nodes */
426
455
p = NULL;
427
for (; stacki > 0; stacki--) {
428
m = stack[stacki - 1];
429
tmp = (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
456
while ((m = skiplist_qpop(&sl->stack_q))) {
457
tmp = skiplist_new_node(sl);
430
458
tmp->next = m->next;
431
459
if (m->next) {
432
460
m->next->prev = tmp;
433
461
}
462
m->next = tmp;
434
463
tmp->prev = m;
435
464
tmp->up = NULL;
436
465
tmp->nextindex = tmp->previndex = NULL;
438
467
if (p) {
439
468
p->up = tmp;
440
469
}
470
else {
471
/* This sets ret to the bottom-most node we are inserting */
472
ret = tmp;
473
}
441
474
tmp->data = data;
442
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;
443
484
m->next = tmp;
444
/* This sets ret to the bottom-most node we are inserting */
445
if (!p) {
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 */
446
504
ret = tmp;
447
sl->size++; /* this seems to go here got each element to be counted */
448
505
}
449
506
p = tmp;
450
507
}
451
free(stack); /* OK. was malloc'ed */
452
508
if (sl->index != NULL) {
453
509
/*
454
510
* this is a external insertion, we must insert into each index as
457
513
apr_skiplistnode *ni, *li;
458
514
li = ret;
459
515
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);
516
apr_skiplist *sli = (apr_skiplist *)p->data;
517
ni = apr_skiplist_insert_compare(sli, ret->data, sli->compare);
461
518
li->nextindex = ni;
462
519
ni->previndex = li;
463
520
li = ni;
464
521
}
465
522
}
466
else {
467
/* sl->size++; */
468
}
469
523
sl->size++;
470
524
return ret;
471
525
}
472
526
473
APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree)
527
APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
474
528
{
475
if (!sl->compare) {
476
return 0;
477
}
478
return apr_skiplist_remove_compare(sl, data, myfree, sl->comparek);
529
return apr_skiplist_insert_compare(sl, data, sl->compare);
479
530
}
480
531
481
532
#if 0
520
571
if (!m && myfree && p->data) {
521
572
myfree(p->data);
522
573
}
523
apr_skiplist_free(sl, p);
574
skiplist_free_node(sl, p);
524
575
}
525
576
sl->size--;
526
577
while (sl->top && sl->top->next == NULL) {
530
581
if (sl->top) {
531
582
sl->top->up = NULL; /* Make it think its the top */
532
583
}
533
apr_skiplist_free(sl, p);
584
skiplist_free_node(sl, p);
534
585
sl->height--;
535
586
}
536
587
if (!sl->top) {
537
sl->bottom = NULL;
588
sl->bottom = sl->bottomend = NULL;
589
sl->topend = NULL;
538
590
}
539
return sl->height; /* return 1; ?? */
591
return skiplist_height(sl);
540
592
}
541
593
542
594
APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli,
545
597
{
546
598
apr_skiplistnode *m;
547
599
apr_skiplist *sl;
600
if (!comp) {
601
return 0;
602
}
548
603
if (comp == sli->comparek || !sli->index) {
549
604
sl = sli;
550
605
}
551
606
else {
552
607
apr_skiplist_find(sli->index, (void *)comp, &m);
608
if (!m) {
609
return 0;
610
}
553
611
sl = (apr_skiplist *) m->data;
554
612
}
555
613
skiplisti_find_compare(sl, data, &m, comp);
562
620
return skiplisti_remove(sl, m, myfree);
563
621
}
564
622
623
APR_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
565
628
APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree)
566
629
{
567
630
/*
573
636
m = sl->bottom;
574
637
while (m) {
575
638
p = m->next;
576
if (p && myfree && p->data)
639
if (myfree && p && p->data) {
577
640
myfree(p->data);
578
while (m) {
641
}
642
do {
579
643
u = m->up;
580
apr_skiplist_free(sl, p);
644
skiplist_free_node(sl, m);
581
645
m = u;
582
}
646
} while (m);
583
647
m = p;
584
648
}
585
649
sl->top = sl->bottom = NULL;
650
sl->topend = sl->bottomend = NULL;
586
651
sl->height = 0;
587
652
sl->size = 0;
588
653
}
611
676
612
677
static void skiplisti_destroy(void *vsl)
613
678
{
614
apr_skiplist_destroy((apr_skiplist *) vsl, NULL);
615
apr_skiplist_free((apr_skiplist *) vsl, vsl);
679
apr_skiplist_destroy(vsl, NULL);
616
680
}
617
681
618
682
APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree)
620
684
while (apr_skiplist_pop(sl->index, skiplisti_destroy) != NULL)
621
685
;
622
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
}
623
694
}
624
695
625
696
APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2)
Loggerhead is a web-based interface for Breezy
Version: 2.0.1