varnish-cache/lib/libvarnish/binary_heap.c
1
/*-
2
 * Copyright (c) 2006 Verdens Gang AS
3
 * Copyright (c) 2006-2011 Varnish Software AS
4
 * All rights reserved.
5
 *
6
 * Author: Poul-Henning Kamp <phk@phk.freebsd.dk>
7
 *
8
 * Redistribution and use in source and binary forms, with or without
9
 * modification, are permitted provided that the following conditions
10
 * are met:
11
 * 1. Redistributions of source code must retain the above copyright
12
 *    notice, this list of conditions and the following disclaimer.
13
 * 2. Redistributions in binary form must reproduce the above copyright
14
 *    notice, this list of conditions and the following disclaimer in the
15
 *    documentation and/or other materials provided with the distribution.
16
 *
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
21
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27
 * SUCH DAMAGE.
28
 *
29
 * Implementation of a binary heap API
30
 *
31
 * See also:
32
 *      http://dl.acm.org/citation.cfm?doid=1785414.1785434
33
 *      (or: http://queue.acm.org/detail.cfm?id=1814327)
34
 */
35
36
#include "config.h"
37
38
#include <limits.h>
39
#include <stdint.h>
40
#include <stdlib.h>
41
#include <unistd.h>
42
43
#include "vdef.h"
44
#include "vas.h"
45
#include "binary_heap.h"
46
47
/* Parameters --------------------------------------------------------*/
48
49
/*
50
 * The number of elements in a row has to be a compromise between
51
 * wasted space and number of memory allocations.
52
 * With 64k objects per row, there will be at least 5...10 seconds
53
 * between row additions on a very busy server.
54
 * At the same time, the worst case amount of wasted memory is kept
55
 * at a reasonable 1 MB -- two rows on 64bit system.
56
 * Finally, but without practical significance: 16 bits should be
57
 * easier for the compiler to optimize.
58
 */
59
#define ROW_SHIFT               16
60
61
62
#undef PARANOIA
63
64
/* Private definitions -----------------------------------------------*/
65
66
#define ROOT_IDX                1
67
68
#define ROW_WIDTH               (1 << ROW_SHIFT)
69
70
/*lint -emacro(572, ROW) shift 0 >> by 16 */
71
/*lint -emacro(835, ROW) 0 left of >> */
72
/*lint -emacro(778, ROW) const >> evaluates to zero */
73
#define ROW(b, n)               ((b)->array[(n) >> ROW_SHIFT])
74
75
/*lint -emacro(835, A) 0 left of & */
76
#define A(b, n)                 ROW(b, n)[(n) & (ROW_WIDTH - 1)]
77
78
struct binheap {
79
        unsigned                magic;
80
#define BINHEAP_MAGIC           0xf581581aU     /* from /dev/random */
81
        void                    *priv;
82
        binheap_cmp_t           *cmp;
83
        binheap_update_t        *update;
84
        void                    ***array;
85
        unsigned                rows;
86
        unsigned                length;
87
        unsigned                next;
88
        unsigned                page_size;
89
        unsigned                page_mask;
90
        unsigned                page_shift;
91
};
92
93
#define VM_AWARE
94
95
#ifdef VM_AWARE
96
97
static  unsigned
98 6894452
parent(const struct binheap *bh, unsigned u)
99
{
100
        unsigned po;
101
        unsigned v;
102
103 6894452
        assert(u != UINT_MAX);
104 6894452
        po = u & bh->page_mask;
105
106 6894452
        if (u < bh->page_size || po > 3) {
107 6864935
                v = (u & ~bh->page_mask) | (po >> 1);
108 29517
        } else if (po < 2) {
109 14574
                v = (u - bh->page_size) >> bh->page_shift;
110 14574
                v += v & ~(bh->page_mask >> 1);
111 14574
                v |= bh->page_size / 2;
112
        } else {
113 14943
                v = u - 2;
114
        }
115 6894452
        return (v);
116
}
117
118
static void
119 89710720
child(const struct binheap *bh, unsigned u, unsigned *a, unsigned *b)
120
{
121
        uintmax_t uu;
122
123 89710720
        if (u > bh->page_mask && (u & (bh->page_mask - 1)) == 0) {
124
                /* First two elements are magical except on the first page */
125 5682450
                *a = *b = u + 2;
126 84028270
        } else if (u & (bh->page_size >> 1)) {
127
                /* The bottom row is even more magical */
128 11686965
                *a = (u & ~bh->page_mask) >> 1;
129 11686965
                *a |= u & (bh->page_mask >> 1);
130 11686965
                *a += 1;
131 11686965
                uu = (uintmax_t)*a << bh->page_shift;
132 11686965
                *a = uu;
133 11686965
                if (*a == uu) {
134 11686941
                        *b = *a + 1;
135
                } else {
136
                        /*
137
                         * An unsigned is not big enough: clamp instead
138
                         * of truncating.  We do not support adding
139
                         * more than UINT_MAX elements anyway, so this
140
                         * is without consequence.
141
                         */
142 24
                        *a = UINT_MAX;
143 24
                        *b = UINT_MAX;
144
                }
145
        } else {
146
                /* The rest is as usual, only inside the page */
147 72341305
                *a = u + (u & bh->page_mask);
148 72341305
                *b = *a + 1;
149
        }
150
#ifdef PARANOIA
151
        assert(*a > 0);
152
        assert(*b > 0);
153
        if (*a != UINT_MAX) {
154
                assert(parent(bh, *a) == u);
155
                assert(parent(bh, *b) == u);
156
        }
157
#endif
158 89710720
}
159
160
161
#else
162
163
static unsigned
164
parent(const struct binheap *bh, unsigned u)
165
{
166
167
        (void)bh;
168
        return (u / 2);
169
}
170
171
static void
172
child(const struct binheap *bh, unsigned u, unsigned *a, unsigned *b)
173
{
174
175
        (void)bh;
176
        *a = u * 2;
177
        *b = *a + 1;
178
}
179
180
#endif
181
182
/* Implementation ----------------------------------------------------*/
183
184
static void
185 12837
binheap_addrow(struct binheap *bh)
186
{
187
        unsigned u;
188
189
        /* First make sure we have space for another row */
190 12837
        if (&ROW(bh, bh->length) >= bh->array + bh->rows) {
191 6
                u = bh->rows * 2;
192 6
                bh->array = realloc(bh->array, sizeof(*bh->array) * u);
193 6
                assert(bh->array != NULL);
194
195
                /* NULL out new pointers */
196 21
                while (bh->rows < u)
197 9
                        bh->array[bh->rows++] = NULL;
198
        }
199 12837
        assert(ROW(bh, bh->length) == NULL);
200 12837
        ROW(bh, bh->length) = malloc(sizeof(**bh->array) * ROW_WIDTH);
201 12837
        assert(ROW(bh, bh->length));
202 12837
        bh->length += ROW_WIDTH;
203 12837
}
204
205
struct binheap *
206 12822
binheap_new(void *priv, binheap_cmp_t *cmp_f, binheap_update_t *update_f)
207
{
208
        struct binheap *bh;
209
        unsigned u;
210
211 12822
        bh = calloc(1, sizeof *bh);
212 12822
        if (bh == NULL)
213 0
                return (bh);
214 12822
        bh->priv = priv;
215
216 12822
        bh->page_size = (unsigned)getpagesize() / sizeof (void *);
217 12822
        bh->page_mask = bh->page_size - 1;
218 12822
        AZ(bh->page_size & bh->page_mask);      /* power of two */
219 12822
        for (u = 1; (1U << u) != bh->page_size; u++)
220
                ;
221 12822
        bh->page_shift = u;
222 12822
        assert(bh->page_size <= (sizeof(**bh->array) * ROW_WIDTH));
223
224 12822
        bh->cmp = cmp_f;
225 12822
        bh->update = update_f;
226 12822
        bh->next = ROOT_IDX;
227
#ifdef TEST_DRIVER
228 3
        bh->rows = 1;           /* A tiny-ish number */
229
#else
230 12819
        bh->rows = 16;          /* A tiny-ish number */
231
#endif
232 12822
        bh->array = calloc(bh->rows, sizeof *bh->array);
233 12822
        assert(bh->array != NULL);
234 12822
        binheap_addrow(bh);
235 12822
        A(bh, ROOT_IDX) = NULL;
236 12822
        bh->magic = BINHEAP_MAGIC;
237 12822
        return (bh);
238
}
239
240
static void
241 175861467
binheap_update(const struct binheap *bh, unsigned u)
242
{
243 175861467
        assert(bh != NULL);
244 175861467
        assert(bh->magic == BINHEAP_MAGIC);
245 175861467
        assert(u < bh->next);
246 175861467
        assert(A(bh, u) != NULL);
247 175861467
        if (bh->update != NULL)
248 175861467
                bh->update(bh->priv, A(bh, u), u);
249 175861467
}
250
251
static void
252 83708071
binhead_swap(const struct binheap *bh, unsigned u, unsigned v)
253
{
254
        void *p;
255
256 83708071
        assert(bh != NULL);
257 83708071
        assert(bh->magic == BINHEAP_MAGIC);
258 83708071
        assert(u < bh->next);
259 83708071
        assert(A(bh, u) != NULL);
260 83708071
        assert(v < bh->next);
261 83708071
        assert(A(bh, v) != NULL);
262 83708071
        p = A(bh, u);
263 83708071
        A(bh, u) = A(bh, v);
264 83708071
        A(bh, v) = p;
265 83708071
        binheap_update(bh, u);
266 83708071
        binheap_update(bh, v);
267 83708071
}
268
269
static unsigned
270 10676716
binheap_trickleup(const struct binheap *bh, unsigned u)
271
{
272
        unsigned v;
273
274 10676716
        assert(bh != NULL); assert(bh->magic == BINHEAP_MAGIC);
275 10676716
        assert(u < bh->next);
276 10676716
        assert(A(bh, u) != NULL);
277
278 21405998
        while (u > ROOT_IDX) {
279 6894452
                assert(u < bh->next);
280 6894452
                assert(A(bh, u) != NULL);
281 6894452
                v = parent(bh, u);
282 6894452
                assert(v < u);
283 6894452
                assert(v < bh->next);
284 6894452
                assert(A(bh, v) != NULL);
285 6894452
                if (!bh->cmp(bh->priv, A(bh, u), A(bh, v)))
286 6841886
                        break;
287 52566
                binhead_swap(bh, u, v);
288 52566
                u = v;
289
        }
290 10676716
        return (u);
291
}
292
293
static unsigned
294 6054936
binheap_trickledown(const struct binheap *bh, unsigned u)
295
{
296
        unsigned v1, v2;
297
298 6054936
        assert(bh != NULL);
299 6054936
        assert(bh->magic == BINHEAP_MAGIC);
300 6054936
        assert(u < bh->next);
301 6054936
        assert(A(bh, u) != NULL);
302
303
        while (1) {
304 173365946
                assert(u < bh->next);
305 89710441
                assert(A(bh, u) != NULL);
306 89710441
                child(bh, u, &v1, &v2);
307 89710441
                assert(v1 > 0);
308 89710441
                assert(v2 > 0);
309 89710441
                assert(v1 <= v2);
310
311 89710441
                if (v1 >= bh->next)
312 6050886
                        return (u);
313
314 83659555
                assert(A(bh, v1) != NULL);
315 83659555
                if (v1 != v2 && v2 < bh->next) {
316 77952762
                        assert(A(bh, v2) != NULL);
317 77952762
                        if (bh->cmp(bh->priv, A(bh, v2), A(bh, v1)))
318 12762
                                v1 = v2;
319
                }
320 83659555
                assert(v1 < bh->next);
321 83659555
                assert(A(bh, v1) != NULL);
322 83659555
                if (bh->cmp(bh->priv, A(bh, u), A(bh, v1)))
323 4050
                        return (u);
324 83655505
                binhead_swap(bh, u, v1);
325 83655505
                u = v1;
326
        }
327
}
328
329
void
330 4621780
binheap_insert(struct binheap *bh, void *p)
331
{
332
        unsigned u;
333
334 4621780
        assert(bh != NULL);
335 4621780
        assert(bh->magic == BINHEAP_MAGIC);
336 4621780
        assert(bh->length >= bh->next);
337 4621780
        if (bh->length == bh->next)
338 15
                binheap_addrow(bh);
339 4621780
        assert(bh->length > bh->next);
340 4621780
        u = bh->next++;
341 4621780
        A(bh, u) = p;
342 4621780
        binheap_update(bh, u);
343 4621780
        (void)binheap_trickleup(bh, u);
344 4621780
        assert(u < bh->next);
345 4621780
        assert(A(bh, u) != NULL);
346 4621780
}
347
348
349
#ifdef PARANOIA
350
static void
351
chk(const struct binheap *bh)
352
{
353
        unsigned u, v;
354
355
        for (u = 2; u < bh->next; u++) {
356
                v = parent(bh, u);
357
                AZ(bh->cmp(bh->priv, A(bh, u), A(bh, v)));
358
        }
359
}
360
#endif
361
362
void *
363 4696169
binheap_root(const struct binheap *bh)
364
{
365
366 4696169
        assert(bh != NULL);
367 4696169
        assert(bh->magic == BINHEAP_MAGIC);
368
#ifdef PARANOIA
369
        chk(bh);
370
#endif
371 4696169
        return (A(bh, ROOT_IDX));
372
}
373
374
/*
375
 * It may seem counter-intuitive that we delete by replacement with
376
 * the tail object. "That's almost certain to not belong there, in
377
 * particular when we delete the root ?" is the typical reaction.
378
 *
379
 * If we tried to trickle up into the empty position, we would,
380
 * eventually, end up with a hole in the bottom row, at which point
381
 * we would move the tail object there.
382
 * But there is no guarantee that the tail object would not need to
383
 * trickle up from that position, in fact, it might be the new root
384
 * of this half of the subtree.
385
 * The total number of operations is guaranteed to be at least
386
 * N{height} downward selections, because we have to get the hole
387
 * all the way down, but in addition to that, we may get up to
388
 * N{height}-1 upward trickles.
389
 *
390
 * When we fill the hole with the tail object, the worst case is
391
 * that it trickles all the way up to of this half-tree, or down
392
 * to become the tail object again.
393
 *
394
 * In other words worst case is N{height} up or downward trickles.
395
 * But there is a decent chance that it does not make it all the way.
396
 */
397
398
void
399 3833217
binheap_delete(struct binheap *bh, unsigned idx)
400
{
401
402 3833217
        assert(bh != NULL);
403 3833217
        assert(bh->magic == BINHEAP_MAGIC);
404 3833217
        assert(bh->next > ROOT_IDX);
405 3833217
        assert(idx < bh->next);
406 3833217
        assert(idx > 0);
407 3833217
        assert(A(bh, idx) != NULL);
408 3833217
        bh->update(bh->priv, A(bh, idx), BINHEAP_NOIDX);
409 3833217
        if (idx == --bh->next) {
410 9672
                A(bh, bh->next) = NULL;
411 9672
                return;
412
        }
413 3823545
        A(bh, idx) = A(bh, bh->next);
414 3823545
        A(bh, bh->next) = NULL;
415 3823545
        binheap_update(bh, idx);
416 3823545
        idx = binheap_trickleup(bh, idx);
417 3823545
        assert(idx < bh->next);
418 3823545
        assert(idx > 0);
419 3823545
        assert(A(bh, idx) != NULL);
420 3823545
        idx = binheap_trickledown(bh, idx);
421 3823545
        assert(idx < bh->next);
422 3823545
        assert(idx > 0);
423 3823545
        assert(A(bh, idx) != NULL);
424
425
        /*
426
         * We keep a hysteresis of one full row before we start to
427
         * return space to the OS to avoid silly behaviour around
428
         * row boundaries.
429
         */
430 3823545
        if (bh->next + 2 * ROW_WIDTH <= bh->length) {
431 6
                free(ROW(bh, bh->length - 1));
432 6
                ROW(bh, bh->length - 1) = NULL;
433 6
                bh->length -= ROW_WIDTH;
434
        }
435
}
436
437
/*
438
 * Move an item up/down after changing its key value
439
 */
440
441
void
442 2231391
binheap_reorder(const struct binheap *bh, unsigned idx)
443
{
444
445 2231391
        assert(bh != NULL);
446 2231391
        assert(bh->magic == BINHEAP_MAGIC);
447 2231391
        assert(bh->next > ROOT_IDX);
448 2231391
        assert(idx < bh->next);
449 2231391
        assert(idx > 0);
450 2231391
        assert(A(bh, idx) != NULL);
451 2231391
        idx = binheap_trickleup(bh, idx);
452 2231391
        assert(idx < bh->next);
453 2231391
        assert(idx > 0);
454 2231391
        assert(A(bh, idx) != NULL);
455 2231391
        idx = binheap_trickledown(bh, idx);
456 2231391
        assert(idx < bh->next);
457 2231391
        assert(idx > 0);
458 2231391
        assert(A(bh, idx) != NULL);
459 2231391
}
460
461
#ifdef TEST_DRIVER
462
463
#include <stdio.h>
464
#include <string.h>
465
466
#include "vrnd.h"
467
#include "miniobj.h"
468
469
/* Test driver -------------------------------------------------------*/
470
471
struct foo {
472
        unsigned        magic;
473
#define FOO_MAGIC       0x23239823
474
        unsigned        idx;
475
        unsigned        key;
476
        unsigned        n;
477
};
478
479
#define M 500083        /* Number of operations */
480
#define N 131101        /* Number of items */
481
#define R -1            /* Random modulus */
482
483
struct foo *ff[N];
484
485
static int v_matchproto_(binheap_cmp_t)
486 168269253
cmp(void *priv, const void *a, const void *b)
487
{
488
        const struct foo *fa, *fb;
489
490
        (void)priv;
491 168269253
        CAST_OBJ_NOTNULL(fa, a, FOO_MAGIC);
492 168269253
        CAST_OBJ_NOTNULL(fb, b, FOO_MAGIC);
493 168269253
        return (fa->key < fb->key);
494
}
495
496
static void v_matchproto_(binheap_update_t)
497 179294730
update(void *priv, void *a, unsigned u)
498
{
499
        struct foo *fa;
500
501
        (void)priv;
502 179294730
        CAST_OBJ_NOTNULL(fa, a, FOO_MAGIC);
503 179294730
        fa->idx = u;
504 179294730
}
505
506
#ifdef CHECK2
507
static void
508
chk2(struct binheap *bh)
509
{
510
        unsigned u, v;
511
        struct foo *fa, *fb;
512
513
        for (u = 2; u < bh->next; u++) {
514
                v = parent(bh, u);
515
                fa = A(bh, u);
516
                fb = A(bh, v);
517
                assert(fa->key >= fb->key);
518
        }
519
}
520
#endif
521
522
static void
523 19576200
vrnd_lock(void)
524
{
525 19576200
}
526
527
int
528 3
main(void)
529
{
530
        struct binheap *bh;
531
        unsigned j, u, v, lr, n;
532
        struct foo *fp;
533
534 3
        VRND_SeedAll();
535 3
        VRND_SeedTestable(1);
536 3
        VRND_Lock = vrnd_lock;
537 3
        VRND_Unlock = vrnd_lock;
538
539 3
        bh = binheap_new(NULL, cmp, update);
540 96
        for (n = 2; n; n += n) {
541 93
                child(bh, n - 1, &u, &v);
542 93
                child(bh, n, &u, &v);
543 93
                child(bh, n + 1, &u, &v);
544
        }
545
546 3
        lr = 0; /* unconfuse some compilers... */
547
548 9
        for (j = 0; j < 2; j++) {
549
                /* First insert our N elements */
550 786612
                for (u = 0; u < N; u++) {
551 786606
                        lr = VRND_RandomTestable() % R;
552 786606
                        ALLOC_OBJ(ff[u], FOO_MAGIC);
553 786606
                        assert(ff[u] != NULL);
554 786606
                        ff[u]->key = lr;
555 786606
                        ff[u]->n = u;
556 786606
                        binheap_insert(bh, ff[u]);
557
558 786606
                        fp = binheap_root(bh);
559 786606
                        assert(fp->idx == 1);
560 786606
                        assert(fp->key <= lr);
561
                }
562 6
                fprintf(stderr, "%d inserts OK\n", N);
563
                /* For M cycles, pick the root, insert new */
564 3000504
                for (u = 0; u < M; u++) {
565 3000498
                        fp = binheap_root(bh);
566 3000498
                        CHECK_OBJ_NOTNULL(fp, FOO_MAGIC);
567 3000498
                        assert(fp->idx == 1);
568
569
                        /*
570
                         * It cannot possibly be larger than the last
571
                         * value we added
572
                         */
573 3000498
                        assert(fp->key <= lr);
574 3000498
                        binheap_delete(bh, fp->idx);
575
576 3000498
                        n = fp->n;
577 3000498
                        ALLOC_OBJ(ff[n], FOO_MAGIC);
578 3000498
                        assert(ff[n] != NULL);
579 3000498
                        FREE_OBJ(fp);
580 3000498
                        fp = ff[n];
581 3000498
                        fp->n = n;
582
583 3000498
                        lr = VRND_RandomTestable() % R;
584 3000498
                        fp->key = lr;
585 3000498
                        binheap_insert(bh, fp);
586
                }
587 6
                fprintf(stderr, "%d replacements OK\n", M);
588
                /* The remove everything */
589 6
                lr = 0;
590 786612
                for (u = 0; u < N; u++) {
591 786606
                        fp = binheap_root(bh);
592 786606
                        CHECK_OBJ_NOTNULL(fp, FOO_MAGIC);
593 786606
                        assert(fp->idx == 1);
594 786606
                        assert(fp->key >= lr);
595 786606
                        lr = fp->key;
596 786606
                        binheap_delete(bh, fp->idx);
597 786606
                        ff[fp->n] = NULL;
598 786606
                        FREE_OBJ(fp);
599
                }
600 6
                fprintf(stderr, "%d removes OK\n", N);
601
602 3000504
                for (u = 0; u < M; u++) {
603 3000498
                        v = VRND_RandomTestable() % N;
604 3000498
                        if (ff[v] != NULL) {
605 2231145
                                CHECK_OBJ_NOTNULL(ff[v], FOO_MAGIC);
606 2231145
                                AN(ff[v]->idx);
607 2231145
                                if (ff[v]->key & 1) {
608 0
                                        binheap_delete(bh, ff[v]->idx);
609 0
                                        assert(ff[v]->idx == BINHEAP_NOIDX);
610 0
                                        FREE_OBJ(ff[v]);
611 0
                                        ff[v] = NULL;
612
                                } else {
613 2231145
                                        ff[v]->key = VRND_RandomTestable() % R;
614 2231145
                                        binheap_reorder(bh, ff[v]->idx);
615
                                }
616
                        } else {
617 769353
                                ALLOC_OBJ(ff[v], FOO_MAGIC);
618 769353
                                assert(ff[v] != NULL);
619 769353
                                ff[v]->key = VRND_RandomTestable() % R;
620 769353
                                binheap_insert(bh, ff[v]);
621 769353
                                CHECK_OBJ_NOTNULL(ff[v], FOO_MAGIC);
622 769353
                                AN(ff[v]->idx);
623
                        }
624
#ifdef CHECK2
625
                        chk2(bh);
626
#endif
627
                }
628 6
                fprintf(stderr, "%d updates OK\n", M);
629
        }
630 3
        return (0);
631
}
632
#endif