source: lib/libvarnish/binary_heap.c @ c24650

Revision c24650, 14.2 KB checked in by Poul-Henning Kamp <phk@…>, 4 months ago (diff)

Remove a lot of <errno.h> includes no longer needed and delegate from
central include files (like <common/common.h>) to specific source files.

  • Property mode set to 100644
Line 
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://portal.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 "binary_heap.h"
44#include "vas.h"
45
46/* Parameters --------------------------------------------------------*/
47
48/*
49 * The number of elements in a row has to be a compromise between
50 * wasted space and number of memory allocations.
51 * With 64k objects per row, there will be at least 5...10 seconds
52 * between row additions on a very busy server.
53 * At the same time, the worst case amount of wasted memory is kept
54 * at a reasonable 1 MB -- two rows on 64bit system.
55 * Finally, but without practical significance: 16 bits should be
56 * easier for the compiler to optimize.
57 */
58#define ROW_SHIFT               16
59
60
61#undef PARANOIA
62
63/* Private definitions -----------------------------------------------*/
64
65#define ROOT_IDX                1
66
67#define ROW_WIDTH               (1 << ROW_SHIFT)
68
69/*lint -emacro(572, ROW) shift 0 >> by 16 */
70/*lint -emacro(835, ROW) 0 left of >> */
71/*lint -emacro(778, ROW) const >> evaluates to zero */
72#define ROW(b, n)               ((b)->array[(n) >> ROW_SHIFT])
73
74/*lint -emacro(835, A) 0 left of & */
75#define A(b, n)                 ROW(b, n)[(n) & (ROW_WIDTH - 1)]
76
77struct binheap {
78        unsigned                magic;
79#define BINHEAP_MAGIC           0xf581581aU     /* from /dev/random */
80        void                    *priv;
81        binheap_cmp_t           *cmp;
82        binheap_update_t        *update;
83        void                    ***array;
84        unsigned                rows;
85        unsigned                length;
86        unsigned                next;
87        unsigned                page_size;
88        unsigned                page_mask;
89        unsigned                page_shift;
90};
91
92#define VM_AWARE
93
94#ifdef VM_AWARE
95
96static  unsigned
97parent(const struct binheap *bh, unsigned u)
98{
99        unsigned po;
100        unsigned v;
101
102        assert(u != UINT_MAX);
103        po = u & bh->page_mask;
104
105        if (u < bh->page_size || po > 3) {
106                v = (u & ~bh->page_mask) | (po >> 1);
107        } else if (po < 2) {
108                v = (u - bh->page_size) >> bh->page_shift;
109                v += v & ~(bh->page_mask >> 1);
110                v |= bh->page_size / 2;
111        } else {
112                v = u - 2;
113        }
114        return (v);
115}
116
117static void
118child(const struct binheap *bh, unsigned u, unsigned *a, unsigned *b)
119{
120        uintmax_t uu;
121
122        if (u > bh->page_mask && (u & (bh->page_mask - 1)) == 0) {
123                /* First two elements are magical except on the first page */
124                *a = *b = u + 2;
125        } else if (u & (bh->page_size >> 1)) {
126                /* The bottom row is even more magical */
127                *a = (u & ~bh->page_mask) >> 1;
128                *a |= u & (bh->page_mask >> 1);
129                *a += 1;
130                uu = (uintmax_t)*a << bh->page_shift;
131                *a = uu;
132                if (*a == uu) {
133                        *b = *a + 1;
134                } else {
135                        /*
136                         * An unsigned is not big enough: clamp instead
137                         * of truncating.  We do not support adding
138                         * more than UINT_MAX elements anyway, so this
139                         * is without consequence.
140                         */
141                        *a = UINT_MAX;
142                        *b = UINT_MAX;
143                }
144        } else {
145                /* The rest is as usual, only inside the page */
146                *a = u + (u & bh->page_mask);
147                *b = *a + 1;
148        }
149#ifdef PARANOIA
150        assert(*a > 0);
151        assert(*b > 0);
152        if (*a != UINT_MAX) {
153                assert(parent(bh, *a) == u);
154                assert(parent(bh, *b) == u);
155        }
156#endif
157}
158
159
160#else
161
162static unsigned
163parent(const struct binheap *bh, unsigned u)
164{
165
166        (void)bh;
167        return (u / 2);
168}
169
170static void
171child(const struct binheap *bh, unsigned u, unsigned *a, unsigned *b)
172{
173
174        (void)bh;
175        *a = u * 2;
176        *b = *a + 1;
177}
178
179#endif
180
181/* Implementation ----------------------------------------------------*/
182
183static void
184binheap_addrow(struct binheap *bh)
185{
186        unsigned u;
187
188        /* First make sure we have space for another row */
189        if (&ROW(bh, bh->length) >= bh->array + bh->rows) {
190                u = bh->rows * 2;
191                bh->array = realloc(bh->array, sizeof(*bh->array) * u);
192                assert(bh->array != NULL);
193
194                /* NULL out new pointers */
195                while (bh->rows < u)
196                        bh->array[bh->rows++] = NULL;
197        }
198        assert(ROW(bh, bh->length) == NULL);
199        ROW(bh, bh->length) = malloc(sizeof(**bh->array) * ROW_WIDTH);
200        assert(ROW(bh, bh->length));
201        bh->length += ROW_WIDTH;
202}
203
204struct binheap *
205binheap_new(void *priv, binheap_cmp_t *cmp_f, binheap_update_t *update_f)
206{
207        struct binheap *bh;
208        unsigned u;
209
210        bh = calloc(sizeof *bh, 1);
211        if (bh == NULL)
212                return (bh);
213        bh->priv = priv;
214
215        bh->page_size = (unsigned)getpagesize() / sizeof (void *);
216        bh->page_mask = bh->page_size - 1;
217        AZ(bh->page_size & bh->page_mask);      /* power of two */
218        for (u = 1; (1U << u) != bh->page_size; u++)
219                ;
220        bh->page_shift = u;
221        assert(bh->page_size <= (sizeof(**bh->array) * ROW_WIDTH));
222
223        bh->cmp = cmp_f;
224        bh->update = update_f;
225        bh->next = ROOT_IDX;
226        bh->rows = 16;          /* A tiny-ish number */
227        bh->array = calloc(sizeof *bh->array, bh->rows);
228        assert(bh->array != NULL);
229        binheap_addrow(bh);
230        A(bh, ROOT_IDX) = NULL;
231        bh->magic = BINHEAP_MAGIC;
232        return (bh);
233}
234
235static void
236binheap_update(const struct binheap *bh, unsigned u)
237{
238        assert(bh != NULL);
239        assert(bh->magic == BINHEAP_MAGIC);
240        assert(u < bh->next);
241        assert(A(bh, u) != NULL);
242        if (bh->update != NULL)
243                bh->update(bh->priv, A(bh, u), u);
244}
245
246static void
247binhead_swap(const struct binheap *bh, unsigned u, unsigned v)
248{
249        void *p;
250
251        assert(bh != NULL);
252        assert(bh->magic == BINHEAP_MAGIC);
253        assert(u < bh->next);
254        assert(A(bh, u) != NULL);
255        assert(v < bh->next);
256        assert(A(bh, v) != NULL);
257        p = A(bh, u);
258        A(bh, u) = A(bh, v);
259        A(bh, v) = p;
260        binheap_update(bh, u);
261        binheap_update(bh, v);
262}
263
264static unsigned
265binheap_trickleup(const struct binheap *bh, unsigned u)
266{
267        unsigned v;
268
269        assert(bh != NULL); assert(bh->magic == BINHEAP_MAGIC);
270        assert(u < bh->next);
271        assert(A(bh, u) != NULL);
272
273        while (u > ROOT_IDX) {
274                assert(u < bh->next);
275                assert(A(bh, u) != NULL);
276                v = parent(bh, u);
277                assert(v < u);
278                assert(v < bh->next);
279                assert(A(bh, v) != NULL);
280                if (!bh->cmp(bh->priv, A(bh, u), A(bh, v)))
281                        break;
282                binhead_swap(bh, u, v);
283                u = v;
284        }
285        return (u);
286}
287
288static unsigned
289binheap_trickledown(const struct binheap *bh, unsigned u)
290{
291        unsigned v1, v2;
292
293        assert(bh != NULL);
294        assert(bh->magic == BINHEAP_MAGIC);
295        assert(u < bh->next);
296        assert(A(bh, u) != NULL);
297
298        while (1) {
299                assert(u < bh->next);
300                assert(A(bh, u) != NULL);
301                child(bh, u, &v1, &v2);
302                assert(v1 > 0);
303                assert(v2 > 0);
304                assert(v1 <= v2);
305
306                if (v1 >= bh->next)
307                        return (u);
308
309                assert(A(bh, v1) != NULL);
310                if (v1 != v2 && v2 < bh->next) {
311                        assert(A(bh, v2) != NULL);
312                        if (bh->cmp(bh->priv, A(bh, v2), A(bh, v1)))
313                                v1 = v2;
314                }
315                assert(v1 < bh->next);
316                assert(A(bh, v1) != NULL);
317                if (bh->cmp(bh->priv, A(bh, u), A(bh, v1)))
318                        return (u);
319                binhead_swap(bh, u, v1);
320                u = v1;
321        }
322}
323
324void
325binheap_insert(struct binheap *bh, void *p)
326{
327        unsigned u;
328
329        assert(bh != NULL);
330        assert(bh->magic == BINHEAP_MAGIC);
331        assert(bh->length >= bh->next);
332        if (bh->length == bh->next)
333                binheap_addrow(bh);
334        assert(bh->length > bh->next);
335        u = bh->next++;
336        A(bh, u) = p;
337        binheap_update(bh, u);
338        (void)binheap_trickleup(bh, u);
339        assert(u < bh->next);
340        assert(A(bh, u) != NULL);
341}
342
343
344#ifdef PARANOIA
345static void
346chk(const struct binheap *bh)
347{
348        unsigned u, v;
349
350        for (u = 2; u < bh->next; u++) {
351                v = parent(bh, u);
352                AZ(bh->cmp(bh->priv, A(bh, u), A(bh, v)));
353        }
354}
355#endif
356
357void *
358binheap_root(const struct binheap *bh)
359{
360
361        assert(bh != NULL);
362        assert(bh->magic == BINHEAP_MAGIC);
363#ifdef PARANOIA
364        chk(bh);
365#endif
366        return (A(bh, ROOT_IDX));
367}
368
369/*
370 * It may seem counter-intuitive that we delete by replacement with
371 * the tail object. "That's almost certain to not belong there, in
372 * particular when we delete the root ?" is the typical reaction.
373 *
374 * If we tried to trickle up into the empty position, we would,
375 * eventually, end up with a hole in the bottom row, at which point
376 * we would move the tail object there.
377 * But there is no guarantee that the tail object would not need to
378 * trickle up from that position, in fact, it might be the new root
379 * of this half of the subtree.
380 * The total number of operations is guaranteed to be at least
381 * N{height} downward selections, because we have to get the hole
382 * all the way down, but in addition to that, we may get up to
383 * N{height}-1 upward trickles.
384 *
385 * When we fill the hole with the tail object, the worst case is
386 * that it trickles all the way up to of this half-tree, or down
387 * to become the tail object again.
388 *
389 * In other words worst case is N{height} up or downward trickles.
390 * But there is a decent chance that it does not make it all the way.
391 */
392
393void
394binheap_delete(struct binheap *bh, unsigned idx)
395{
396
397        assert(bh != NULL);
398        assert(bh->magic == BINHEAP_MAGIC);
399        assert(bh->next > ROOT_IDX);
400        assert(idx < bh->next);
401        assert(idx > 0);
402        assert(A(bh, idx) != NULL);
403        bh->update(bh->priv, A(bh, idx), BINHEAP_NOIDX);
404        if (idx == --bh->next) {
405                A(bh, bh->next) = NULL;
406                return;
407        }
408        A(bh, idx) = A(bh, bh->next);
409        A(bh, bh->next) = NULL;
410        binheap_update(bh, idx);
411        idx = binheap_trickleup(bh, idx);
412        assert(idx < bh->next);
413        assert(idx > 0);
414        assert(A(bh, idx) != NULL);
415        idx = binheap_trickledown(bh, idx);
416        assert(idx < bh->next);
417        assert(idx > 0);
418        assert(A(bh, idx) != NULL);
419
420        /*
421         * We keep a hysteresis of one full row before we start to
422         * return space to the OS to avoid silly behaviour around
423         * row boundaries.
424         */
425        if (bh->next + 2 * ROW_WIDTH <= bh->length) {
426                free(ROW(bh, bh->length - 1));
427                ROW(bh, bh->length - 1) = NULL;
428                bh->length -= ROW_WIDTH;
429        }
430}
431
432/*
433 * Move an item up/down after changing its key value
434 */
435
436void
437binheap_reorder(const struct binheap *bh, unsigned idx)
438{
439
440        assert(bh != NULL);
441        assert(bh->magic == BINHEAP_MAGIC);
442        assert(bh->next > ROOT_IDX);
443        assert(idx < bh->next);
444        assert(idx > 0);
445        assert(A(bh, idx) != NULL);
446        idx = binheap_trickleup(bh, idx);
447        assert(idx < bh->next);
448        assert(idx > 0);
449        assert(A(bh, idx) != NULL);
450        idx = binheap_trickledown(bh, idx);
451        assert(idx < bh->next);
452        assert(idx > 0);
453        assert(A(bh, idx) != NULL);
454}
455
456#ifdef TEST_DRIVER
457
458#include <stdio.h>
459
460#include "miniobj.h"
461
462/* Test driver -------------------------------------------------------*/
463
464static void
465vasfail(const char *func, const char *file, int line,
466    const char *cond, int err, int xxx)
467{
468        fprintf(stderr, "PANIC: %s %s %d %s %d %d\n",
469                func, file, line, cond, err, xxx);
470        abort();
471}
472
473vas_f *VAS_Fail = vasfail;
474
475struct foo {
476        unsigned        magic;
477#define FOO_MAGIC       0x23239823
478        unsigned        idx;
479        unsigned        key;
480        unsigned        n;
481};
482
483#if 1
484#define M 31011091      /* Number of operations */
485#define N 17313102      /* Number of items */
486#else
487#define M 3401          /* Number of operations */
488#define N 1131          /* Number of items */
489#endif
490#define R -1            /* Random modulus */
491
492struct foo *ff[N];
493
494static int
495cmp(void *priv, void *a, void *b)
496{
497        struct foo *fa, *fb;
498
499        CAST_OBJ_NOTNULL(fa, a, FOO_MAGIC);
500        CAST_OBJ_NOTNULL(fb, b, FOO_MAGIC);
501        return (fa->key < fb->key);
502}
503
504void
505update(void *priv, void *a, unsigned u)
506{
507        struct foo *fa;
508
509        CAST_OBJ_NOTNULL(fa, a, FOO_MAGIC);
510        fa->idx = u;
511}
512
513void
514chk2(struct binheap *bh)
515{
516        unsigned u, v;
517        struct foo *fa, *fb;
518
519        for (u = 2; u < bh->next; u++) {
520                v = parent(bh, u);
521                fa = A(bh, u);
522                fb = A(bh, v);
523                assert(fa->key >= fb->key);
524        }
525}
526
527int
528main(int argc, char **argv)
529{
530        struct binheap *bh;
531        unsigned u, v, lr, n;
532        struct foo *fp;
533
534        if (0) {
535                srandomdev();
536                u = random();
537                printf("Seed %u\n", u);
538                srandom(u);
539        }
540        bh = binheap_new(NULL, cmp, update);
541        for (n = 2; n; n += n) {
542                child(bh, n - 1, &u, &v);
543                child(bh, n, &u, &v);
544                child(bh, n + 1, &u, &v);
545        }
546
547        while (1) {
548                /* First insert our N elements */
549                for (u = 0; u < N; u++) {
550                        lr = random() % R;
551                        ALLOC_OBJ(ff[u], FOO_MAGIC);
552                        assert(ff[u] != NULL);
553                        ff[u]->key = lr;
554                        ff[u]->n = u;
555                        binheap_insert(bh, ff[u]);
556
557                        fp = binheap_root(bh);
558                        assert(fp->idx == 1);
559                        assert(fp->key <= lr);
560                }
561                fprintf(stderr, "%d inserts OK\n", N);
562                /* For M cycles, pick the root, insert new */
563                for (u = 0; u < M; u++) {
564                        fp = binheap_root(bh);
565                        CHECK_OBJ_NOTNULL(fp, FOO_MAGIC);
566                        assert(fp->idx == 1);
567
568                        /*
569                         * It cannot possibly be larger than the last
570                         * value we added
571                         */
572                        assert(fp->key <= lr);
573                        binheap_delete(bh, fp->idx);
574
575                        n = fp->n;
576                        ALLOC_OBJ(ff[n], FOO_MAGIC);
577                        assert(ff[n] != NULL);
578                        FREE_OBJ(fp);
579                        fp = ff[n];
580                        fp->n = n;
581
582                        lr = random() % R;
583                        fp->key = lr;
584                        binheap_insert(bh, fp);
585                }
586                fprintf(stderr, "%d replacements OK\n", M);
587                /* The remove everything */
588                lr = 0;
589                for (u = 0; u < N; u++) {
590                        fp = binheap_root(bh);
591                        CHECK_OBJ_NOTNULL(fp, FOO_MAGIC);
592                        assert(fp->idx == 1);
593                        assert(fp->key >= lr);
594                        lr = fp->key;
595                        binheap_delete(bh, fp->idx);
596                        ff[fp->n] = NULL;
597                        FREE_OBJ(fp);
598                }
599                fprintf(stderr, "%d removes OK\n", N);
600
601                for (u = 0; u < M; u++) {
602                        v = random() % N;
603                        if (ff[v] != NULL) {
604                                CHECK_OBJ_NOTNULL(ff[v], FOO_MAGIC);
605                                AN(ff[v]->idx);
606                                if (ff[v]->key & 1) {
607                                        binheap_delete(bh, ff[v]->idx);
608                                        assert(ff[v]->idx == BINHEAP_NOIDX);
609                                        FREE_OBJ(ff[v]);
610                                        ff[v] = NULL;
611                                } else {
612                                        ff[v]->key = random() % R;
613                                        binheap_reorder(bh, ff[v]->idx);
614                                }
615                        } else {
616                                ALLOC_OBJ(ff[v], FOO_MAGIC);
617                                assert(ff[v] != NULL);
618                                ff[v]->key = random() % R;
619                                binheap_insert(bh, ff[v]);
620                                CHECK_OBJ_NOTNULL(ff[v], FOO_MAGIC);
621                                AN(ff[v]->idx);
622                        }
623                        if (0)
624                                chk2(bh);
625                }
626                fprintf(stderr, "%d updates OK\n", M);
627        }
628        return (0);
629}
630#endif
Note: See TracBrowser for help on using the repository browser.