source: lib/libvarnish/binary_heap.c @ 203eaf

Revision 203eaf, 14.2 KB checked in by Poul-Henning Kamp <phk@…>, 3 days ago (diff)

Some stylistic consistency patches from Dridi Boukelmoune
who made them with Coccinelle.

Thanks!

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