GCOV - Varnish Cache


/*-
 * Copyright (c) 2006 Verdens Gang AS
 * Copyright (c) 2006-2011 Varnish Software AS
 * All rights reserved.
 *
 * Author: Poul-Henning Kamp <phk@phk.freebsd.dk>
 *
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * Implementation of a binary heap API
 *
 * See also:
 *      http://dl.acm.org/citation.cfm?doid=1785414.1785434
 *      (or: http://queue.acm.org/detail.cfm?id=1814327)
 */

#include "config.h"

#include <limits.h>
#include <stdint.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

#include "miniobj.h"
#include "vdef.h"
#include "vas.h"
#include "vbh.h"

/* Parameters --------------------------------------------------------*/

/*
 * The number of elements in a row has to be a compromise between
 * wasted space and number of memory allocations.
 * With 64k objects per row, there will be at least 5...10 seconds
 * between row additions on a very busy server.
 * At the same time, the worst case amount of wasted memory is kept
 * at a reasonable 1 MB -- two rows on 64bit system.
 * Finally, but without practical significance: 16 bits should be
 * easier for the compiler to optimize.
 */
#define ROW_SHIFT               16


#undef PARANOIA

/* Private definitions -----------------------------------------------*/

#define ROOT_IDX                1

#define ROW_WIDTH               (1 << ROW_SHIFT)

/*lint -emacro(572, ROW) shift 0 >> by 16 */
/*lint -emacro(835, ROW) 0 left of >> */
/*lint -emacro(778, ROW) const >> evaluates to zero */
#define ROW(b, n)               ((b)->array[(n) >> ROW_SHIFT])

/*lint -emacro(835, A) 0 left of & */
#define A(b, n)                 ROW(b, n)[(n) & (ROW_WIDTH - 1)]

struct vbh {
        unsigned                magic;
#define VBH_MAGIC               0xf581581a      /* from /dev/random */
        void                    *priv;
        vbh_cmp_t               *cmp;
        vbh_update_t            *update;
        void                    ***array;
        unsigned                rows;
        unsigned                length;
        unsigned                next;
        unsigned                page_size;
        unsigned                page_mask;
        unsigned                page_shift;
};

#define VM_AWARE

#ifdef VM_AWARE

static  unsigned
parent(const struct vbh *bh, unsigned u)
{
        unsigned po;
        unsigned v;

        assert(u != UINT_MAX);
        po = u & bh->page_mask;

        if (u < bh->page_size || po > 3) {
                v = (u & ~bh->page_mask) | (po >> 1);
        } else if (po < 2) {
                v = (u - bh->page_size) >> bh->page_shift;
                v += v & ~(bh->page_mask >> 1);
                v |= bh->page_size / 2;
        } else {
                v = u - 2;
        }
        return (v);
}

static void
child(const struct vbh *bh, unsigned u, unsigned *a, unsigned *b)
{
        uintmax_t uu;

        if (u > bh->page_mask && (u & (bh->page_mask - 1)) == 0) {
                /* First two elements are magical except on the first page */
                *a = *b = u + 2;
        } else if (u & (bh->page_size >> 1)) {
                /* The bottom row is even more magical */
                *a = (u & ~bh->page_mask) >> 1;
                *a |= u & (bh->page_mask >> 1);
                *a += 1;
                uu = (uintmax_t)*a << bh->page_shift;
                *a = uu;
                if (*a == uu) {
                        *b = *a + 1;
                } else {
                        /*
                         * An unsigned is not big enough: clamp instead
                         * of truncating.  We do not support adding
                         * more than UINT_MAX elements anyway, so this
                         * is without consequence.
                         */
                        *a = UINT_MAX;
                        *b = UINT_MAX;
                }
        } else {
                /* The rest is as usual, only inside the page */
                *a = u + (u & bh->page_mask);
                *b = *a + 1;
        }
#ifdef PARANOIA
        assert(*a > 0);
        assert(*b > 0);
        if (*a != UINT_MAX) {
                assert(parent(bh, *a) == u);
                assert(parent(bh, *b) == u);
        }
#endif
}


#else

static unsigned
parent(const struct vbh *bh, unsigned u)
{

        (void)bh;
        return (u / 2);
}

static void
child(const struct vbh *bh, unsigned u, unsigned *a, unsigned *b)
{

        (void)bh;
        *a = u * 2;
        *b = *a + 1;
}

#endif

/* Implementation ----------------------------------------------------*/

static void
vbh_addrow(struct vbh *bh)
{
        unsigned u;

        /* First make sure we have space for another row */
        if (&ROW(bh, bh->length) >= bh->array + bh->rows) {
                u = bh->rows * 2;
                bh->array = realloc(bh->array, sizeof(*bh->array) * u);
                assert(bh->array != NULL);

                /* NULL out new pointers */
                while (bh->rows < u)
                        bh->array[bh->rows++] = NULL;
        }
        assert(ROW(bh, bh->length) == NULL);
        ROW(bh, bh->length) = malloc(sizeof(**bh->array) * ROW_WIDTH);
        assert(ROW(bh, bh->length));
        bh->length += ROW_WIDTH;
}

struct vbh *
VBH_new(void *priv, vbh_cmp_t *cmp_f, vbh_update_t *update_f)
{
        struct vbh *bh;
        unsigned u;

        ALLOC_OBJ(bh, VBH_MAGIC);
        if (bh == NULL)
                return (bh);
        bh->priv = priv;

        bh->page_size = (unsigned)getpagesize() / sizeof (void *);
        bh->page_mask = bh->page_size - 1;
        AZ(bh->page_size & bh->page_mask);      /* power of two */
        for (u = 1; (1U << u) != bh->page_size; u++)
                ;
        bh->page_shift = u;
        assert(bh->page_size <= (sizeof(**bh->array) * ROW_WIDTH));

        bh->cmp = cmp_f;
        bh->update = update_f;
        bh->next = ROOT_IDX;
#ifdef TEST_DRIVER
        bh->rows = 1;           /* A tiny-ish number */
#else
        bh->rows = 16;          /* A tiny-ish number */
#endif
        bh->array = calloc(bh->rows, sizeof *bh->array);
        assert(bh->array != NULL);
        vbh_addrow(bh);
        A(bh, ROOT_IDX) = NULL;
        bh->magic = VBH_MAGIC;
        return (bh);
}

void
VBH_destroy(struct vbh **bhp)
{
        struct vbh *bh;
        unsigned u;

        TAKE_OBJ_NOTNULL(bh, bhp, VBH_MAGIC);
        AZ(VBH_root(bh));

        for (u = 0; u < bh->length; u += ROW_WIDTH)
                free(ROW(bh, u));
        free(bh->array);
        FREE_OBJ(bh);
}

static void
vbh_update(const struct vbh *bh, unsigned u)
{
        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
        assert(u < bh->next);
        assert(A(bh, u) != NULL);
        if (bh->update != NULL)
                bh->update(bh->priv, A(bh, u), u);
}

static void
binhead_swap(const struct vbh *bh, unsigned u, unsigned v)
{
        void *p;

        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
        assert(u < bh->next);
        assert(A(bh, u) != NULL);
        assert(v < bh->next);
        assert(A(bh, v) != NULL);
        p = A(bh, u);
        A(bh, u) = A(bh, v);
        A(bh, v) = p;
        vbh_update(bh, u);
        vbh_update(bh, v);
}

static unsigned
vbh_trickleup(const struct vbh *bh, unsigned u)
{
        unsigned v;

        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
        assert(u < bh->next);
        assert(A(bh, u) != NULL);

        while (u > ROOT_IDX) {
                assert(u < bh->next);
                assert(A(bh, u) != NULL);
                v = parent(bh, u);
                assert(v < u);
                assert(v < bh->next);
                assert(A(bh, v) != NULL);
                if (!bh->cmp(bh->priv, A(bh, u), A(bh, v)))
                        break;
                binhead_swap(bh, u, v);
                u = v;
        }
        return (u);
}

static unsigned
vbh_trickledown(const struct vbh *bh, unsigned u)
{
        unsigned v1, v2;

        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
        assert(u < bh->next);
        assert(A(bh, u) != NULL);

        while (1) {
                assert(u < bh->next);
                assert(A(bh, u) != NULL);
                child(bh, u, &v1, &v2);
                assert(v1 > 0);
                assert(v2 > 0);
                assert(v1 <= v2);

                if (v1 >= bh->next)
                        return (u);

                assert(A(bh, v1) != NULL);
                if (v1 != v2 && v2 < bh->next) {
                        assert(A(bh, v2) != NULL);
                        if (bh->cmp(bh->priv, A(bh, v2), A(bh, v1)))
                                v1 = v2;
                }
                assert(v1 < bh->next);
                assert(A(bh, v1) != NULL);
                if (bh->cmp(bh->priv, A(bh, u), A(bh, v1)))
                        return (u);
                binhead_swap(bh, u, v1);
                u = v1;
        }
}

void
VBH_insert(struct vbh *bh, void *p)
{
        unsigned u;

        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
        assert(bh->length >= bh->next);
        if (bh->length == bh->next)
                vbh_addrow(bh);
        assert(bh->length > bh->next);
        u = bh->next++;
        A(bh, u) = p;
        vbh_update(bh, u);
        (void)vbh_trickleup(bh, u);
        assert(u < bh->next);
        assert(A(bh, u) != NULL);
}


#ifdef PARANOIA
static void
chk(const struct vbh *bh)
{
        unsigned u, v;

        for (u = 2; u < bh->next; u++) {
                v = parent(bh, u);
                AZ(bh->cmp(bh->priv, A(bh, u), A(bh, v)));
        }
}
#endif

void *
VBH_root(const struct vbh *bh)
{

        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
#ifdef PARANOIA
        chk(bh);
#endif
        return (A(bh, ROOT_IDX));
}

/*
 * It may seem counter-intuitive that we delete by replacement with
 * the tail object. "That's almost certain to not belong there, in
 * particular when we delete the root ?" is the typical reaction.
 *
 * If we tried to trickle up into the empty position, we would,
 * eventually, end up with a hole in the bottom row, at which point
 * we would move the tail object there.
 * But there is no guarantee that the tail object would not need to
 * trickle up from that position, in fact, it might be the new root
 * of this half of the subtree.
 * The total number of operations is guaranteed to be at least
 * N{height} downward selections, because we have to get the hole
 * all the way down, but in addition to that, we may get up to
 * N{height}-1 upward trickles.
 *
 * When we fill the hole with the tail object, the worst case is
 * that it trickles all the way up to of this half-tree, or down
 * to become the tail object again.
 *
 * In other words worst case is N{height} up or downward trickles.
 * But there is a decent chance that it does not make it all the way.
 */

void
VBH_delete(struct vbh *bh, unsigned idx)
{

        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
        assert(bh->next > ROOT_IDX);
        assert(idx < bh->next);
        assert(idx > 0);
        assert(A(bh, idx) != NULL);
        bh->update(bh->priv, A(bh, idx), VBH_NOIDX);
        if (idx == --bh->next) {
                A(bh, bh->next) = NULL;
                return;
        }
        A(bh, idx) = A(bh, bh->next);
        A(bh, bh->next) = NULL;
        vbh_update(bh, idx);
        idx = vbh_trickleup(bh, idx);
        assert(idx < bh->next);
        assert(idx > 0);
        assert(A(bh, idx) != NULL);
        idx = vbh_trickledown(bh, idx);
        assert(idx < bh->next);
        assert(idx > 0);
        assert(A(bh, idx) != NULL);

        /*
         * We keep a hysteresis of one full row before we start to
         * return space to the OS to avoid silly behaviour around
         * row boundaries.
         */
        if (bh->next + 2 * ROW_WIDTH <= bh->length) {
                free(ROW(bh, bh->length - 1));
                ROW(bh, bh->length - 1) = NULL;
                bh->length -= ROW_WIDTH;
        }
}

/*
 * Move an item up/down after changing its key value
 */

void
VBH_reorder(const struct vbh *bh, unsigned idx)
{

        CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
        assert(bh->next > ROOT_IDX);
        assert(idx < bh->next);
        assert(idx > 0);
        assert(A(bh, idx) != NULL);
        idx = vbh_trickleup(bh, idx);
        assert(idx < bh->next);
        assert(idx > 0);
        assert(A(bh, idx) != NULL);
        idx = vbh_trickledown(bh, idx);
        assert(idx < bh->next);
        assert(idx > 0);
        assert(A(bh, idx) != NULL);
}

#ifdef TEST_DRIVER

#include <stdio.h>
#include <string.h>

#include "vrnd.h"

/* Test driver -------------------------------------------------------*/

struct foo {
        unsigned        magic;
#define FOO_MAGIC       0x23239823
        unsigned        idx;
        unsigned        key;
        unsigned        n;
};

#define M 500083        /* Number of operations */
#define N 131101        /* Number of items */
#define R -1            /* Random modulus */

static struct foo *ff[N];

static int v_matchproto_(vbh_cmp_t)
cmp(void *priv, const void *a, const void *b)
{
        const struct foo *fa, *fb;

        (void)priv;
        CAST_OBJ_NOTNULL(fa, a, FOO_MAGIC);
        CAST_OBJ_NOTNULL(fb, b, FOO_MAGIC);
        return (fa->key < fb->key);
}

static void v_matchproto_(vbh_update_t)
update(void *priv, void *a, unsigned u)
{
        struct foo *fa;

        (void)priv;
        CAST_OBJ_NOTNULL(fa, a, FOO_MAGIC);
        fa->idx = u;
}

#ifdef CHECK2
static void
chk2(struct vbh *bh)
{
        unsigned u, v;
        struct foo *fa, *fb;

        for (u = 2; u < bh->next; u++) {
                v = parent(bh, u);
                fa = A(bh, u);
                fb = A(bh, v);
                assert(fa->key >= fb->key);
        }
}
#endif

static void
vrnd_lock(void)
{
}

int
main(void)
{
        struct vbh *bh;
        unsigned j, u, v, lr, n;
        struct foo *fp;

        VRND_SeedAll();
        VRND_SeedTestable(1);
        VRND_Lock = vrnd_lock;
        VRND_Unlock = vrnd_lock;

        bh = VBH_new(NULL, cmp, update);
        for (n = 2; n; n += n) {
                child(bh, n - 1, &u, &v);
                child(bh, n, &u, &v);
                child(bh, n + 1, &u, &v);
        }

        lr = 0; /* unconfuse some compilers... */

        for (j = 0; j < 2; j++) {
                /* First insert our N elements */
                for (u = 0; u < N; u++) {
                        lr = VRND_RandomTestable() % R;
                        ALLOC_OBJ(ff[u], FOO_MAGIC);
                        assert(ff[u] != NULL);
                        ff[u]->key = lr;
                        ff[u]->n = u;
                        VBH_insert(bh, ff[u]);

                        fp = VBH_root(bh);
                        assert(fp->idx == 1);
                        assert(fp->key <= lr);
                }
                fprintf(stderr, "%d inserts OK\n", N);
                /* For M cycles, pick the root, insert new */
                for (u = 0; u < M; u++) {
                        fp = VBH_root(bh);
                        CHECK_OBJ_NOTNULL(fp, FOO_MAGIC);
                        assert(fp->idx == 1);

                        /*
                         * It cannot possibly be larger than the last
                         * value we added
                         */
                        assert(fp->key <= lr);
                        VBH_delete(bh, fp->idx);

                        n = fp->n;
                        ALLOC_OBJ(ff[n], FOO_MAGIC);
                        assert(ff[n] != NULL);
                        FREE_OBJ(fp);
                        fp = ff[n];
                        fp->n = n;

                        lr = VRND_RandomTestable() % R;
                        fp->key = lr;
                        VBH_insert(bh, fp);
                }
                fprintf(stderr, "%d replacements OK\n", M);
                /* The remove everything */
                lr = 0;
                for (u = 0; u < N; u++) {
                        fp = VBH_root(bh);
                        CHECK_OBJ_NOTNULL(fp, FOO_MAGIC);
                        assert(fp->idx == 1);
                        assert(fp->key >= lr);
                        lr = fp->key;
                        VBH_delete(bh, fp->idx);
                        ff[fp->n] = NULL;
                        FREE_OBJ(fp);
                }
                fprintf(stderr, "%d removes OK\n", N);

                for (u = 0; u < M; u++) {
                        v = VRND_RandomTestable() % N;
                        if (ff[v] != NULL) {
                                CHECK_OBJ(ff[v], FOO_MAGIC);
                                AN(ff[v]->idx);
                                if (ff[v]->key & 1) {
                                        VBH_delete(bh, ff[v]->idx);
                                        assert(ff[v]->idx == VBH_NOIDX);
                                        FREE_OBJ(ff[v]);
                                        ff[v] = NULL;
                                } else {
                                        ff[v]->key = VRND_RandomTestable() % R;
                                        VBH_reorder(bh, ff[v]->idx);
                                }
                        } else {
                                ALLOC_OBJ(ff[v], FOO_MAGIC);
                                assert(ff[v] != NULL);
                                ff[v]->key = VRND_RandomTestable() % R;
                                VBH_insert(bh, ff[v]);
                                CHECK_OBJ_NOTNULL(ff[v], FOO_MAGIC);
                                AN(ff[v]->idx);
                        }
#ifdef CHECK2
                        chk2(bh);
#endif
                }
                fprintf(stderr, "%d updates OK\n", M);
        }
        while ((fp = VBH_root(bh)) != NULL) {
                CHECK_OBJ(fp, FOO_MAGIC);
                VBH_delete(bh, fp->idx);
                FREE_OBJ(fp);
        }
        VBH_destroy(&bh);
        AZ(bh);
        return (0);
}
#endif

		varnish-cache/lib/libvarnish/vbh.c
0		/*-
1		* Copyright (c) 2006 Verdens Gang AS
2		* Copyright (c) 2006-2011 Varnish Software AS
3		* All rights reserved.
4		*
5		* Author: Poul-Henning Kamp <phk@phk.freebsd.dk>
6		*
7		* SPDX-License-Identifier: BSD-2-Clause
8		*
9		* Redistribution and use in source and binary forms, with or without
10		* modification, are permitted provided that the following conditions
11		* are met:
12		* 1. Redistributions of source code must retain the above copyright
13		* notice, this list of conditions and the following disclaimer.
14		* 2. Redistributions in binary form must reproduce the above copyright
15		* notice, this list of conditions and the following disclaimer in the
16		* documentation and/or other materials provided with the distribution.
17		*
18		* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19		* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20		* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21		* ARE DISCLAIMED. IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
22		* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23		* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24		* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25		* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26		* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27		* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28		* SUCH DAMAGE.
29		*
30		* Implementation of a binary heap API
31		*
32		* See also:
33		* http://dl.acm.org/citation.cfm?doid=1785414.1785434
34		* (or: http://queue.acm.org/detail.cfm?id=1814327)
35		*/
36
37		#include "config.h"
38
39		#include <limits.h>
40		#include <stdint.h>
41		#include <stdlib.h>
42		#include <unistd.h>
43		#include <string.h>
44
45		#include "miniobj.h"
46		#include "vdef.h"
47		#include "vas.h"
48		#include "vbh.h"
49
50		/* Parameters --------------------------------------------------------*/
51
52		/*
53		* The number of elements in a row has to be a compromise between
54		* wasted space and number of memory allocations.
55		* With 64k objects per row, there will be at least 5...10 seconds
56		* between row additions on a very busy server.
57		* At the same time, the worst case amount of wasted memory is kept
58		* at a reasonable 1 MB -- two rows on 64bit system.
59		* Finally, but without practical significance: 16 bits should be
60		* easier for the compiler to optimize.
61		*/
62		#define ROW_SHIFT 16
63
64
65		#undef PARANOIA
66
67		/* Private definitions -----------------------------------------------*/
68
69		#define ROOT_IDX 1
70
71		#define ROW_WIDTH (1 << ROW_SHIFT)
72
73		/lint -emacro(572, ROW) shift 0 >> by 16 /
74		/lint -emacro(835, ROW) 0 left of >> /
75		/lint -emacro(778, ROW) const >> evaluates to zero /
76		#define ROW(b, n) ((b)->array[(n) >> ROW_SHIFT])
77
78		/lint -emacro(835, A) 0 left of & /
79		#define A(b, n) ROW(b, n)[(n) & (ROW_WIDTH - 1)]
80
81		struct vbh {
82		unsigned magic;
83		#define VBH_MAGIC 0xf581581a /* from /dev/random */
84		void *priv;
85		vbh_cmp_t *cmp;
86		vbh_update_t *update;
87		void ***array;
88		unsigned rows;
89		unsigned length;
90		unsigned next;
91		unsigned page_size;
92		unsigned page_mask;
93		unsigned page_shift;
94		};
95
96		#define VM_AWARE
97
98		#ifdef VM_AWARE
99
100		static unsigned
101	91771899	parent(const struct vbh *bh, unsigned u)
102		{
103		unsigned po;
104		unsigned v;
105
106	91771899	assert(u != UINT_MAX);
107	91771899	po = u & bh->page_mask;
108
109	91771899	if (u < bh->page_size \|\| po > 3) {
110	91378339	v = (u & ~bh->page_mask) \| (po >> 1);
111	91771899	} else if (po < 2) {
112	194320	v = (u - bh->page_size) >> bh->page_shift;
113	194320	v += v & ~(bh->page_mask >> 1);
114	194320	v \|= bh->page_size / 2;
115	194320	} else {
116	199240	v = u - 2;
117		}
118	91771899	return (v);
119		}
120
121		static void
122	1425484064	child(const struct vbh bh, unsigned u, unsigned a, unsigned *b)
123		{
124		uintmax_t uu;
125
126	1425484064	if (u > bh->page_mask && (u & (bh->page_mask - 1)) == 0) {
127		/* First two elements are magical except on the first page */
128	90998240	a = b = u + 2;
129	1425484064	} else if (u & (bh->page_size >> 1)) {
130		/* The bottom row is even more magical */
131	181285760	*a = (u & ~bh->page_mask) >> 1;
132	181285760	*a \|= u & (bh->page_mask >> 1);
133	181285760	*a += 1;
134	181285760	uu = (uintmax_t)*a << bh->page_shift;
135	181285760	*a = uu;
136	181285760	if (*a == uu) {
137	181285440	b = a + 1;
138	181285440	} else {
139		/*
140		* An unsigned is not big enough: clamp instead
141		* of truncating. We do not support adding
142		* more than UINT_MAX elements anyway, so this
143		* is without consequence.
144		*/
145	320	*a = UINT_MAX;
146	320	*b = UINT_MAX;
147		}
148	181285760	} else {
149		/* The rest is as usual, only inside the page */
150	1153200064	*a = u + (u & bh->page_mask);
151	1153200064	b = a + 1;
152		}
153		#ifdef PARANOIA
154		assert(*a > 0);
155		assert(*b > 0);
156		if (*a != UINT_MAX) {
157		assert(parent(bh, *a) == u);
158		assert(parent(bh, *b) == u);
159		}
160		#endif
161	1425484064	}
162
163
164		#else
165
166		static unsigned
167		parent(const struct vbh *bh, unsigned u)
168		{
169
170		(void)bh;
171		return (u / 2);
172		}
173
174		static void
175		child(const struct vbh bh, unsigned u, unsigned a, unsigned *b)
176		{
177
178		(void)bh;
179		a = u 2;
180		b = a + 1;
181		}
182
183		#endif
184
185		/* Implementation ----------------------------------------------------*/
186
187		static void
188	267899	vbh_addrow(struct vbh *bh)
189		{
190		unsigned u;
191
192		/* First make sure we have space for another row */
193	267899	if (&ROW(bh, bh->length) >= bh->array + bh->rows) {
194	80	u = bh->rows * 2;
195	80	bh->array = realloc(bh->array, sizeof(bh->array) u);
196	80	assert(bh->array != NULL);
197
198		/* NULL out new pointers */
199	200	while (bh->rows < u)
200	120	bh->array[bh->rows++] = NULL;
201	80	}
202	267899	assert(ROW(bh, bh->length) == NULL);
203	267899	ROW(bh, bh->length) = malloc(sizeof(*bh->array) ROW_WIDTH);
204	267899	assert(ROW(bh, bh->length));
205	267899	bh->length += ROW_WIDTH;
206	267899	}
207
208		struct vbh *
209	267699	VBH_new(void priv, vbh_cmp_t cmp_f, vbh_update_t *update_f)
210		{
211		struct vbh *bh;
212		unsigned u;
213
214	267699	ALLOC_OBJ(bh, VBH_MAGIC);
215	267699	if (bh == NULL)
216	0	return (bh);
217	267699	bh->priv = priv;
218
219	267699	bh->page_size = (unsigned)getpagesize() / sizeof (void *);
220	267699	bh->page_mask = bh->page_size - 1;
221	267699	AZ(bh->page_size & bh->page_mask); /* power of two */
222	2409291	for (u = 1; (1U << u) != bh->page_size; u++)
223		;
224	267699	bh->page_shift = u;
225	267699	assert(bh->page_size <= (sizeof(*bh->array) ROW_WIDTH));
226
227	267699	bh->cmp = cmp_f;
228	267699	bh->update = update_f;
229	267699	bh->next = ROOT_IDX;
230		#ifdef TEST_DRIVER
231	40	bh->rows = 1; /* A tiny-ish number */
232		#else
233	267659	bh->rows = 16; /* A tiny-ish number */
234		#endif
235	267699	bh->array = calloc(bh->rows, sizeof *bh->array);
236	267699	assert(bh->array != NULL);
237	267699	vbh_addrow(bh);
238	267699	A(bh, ROOT_IDX) = NULL;
239	267699	bh->magic = VBH_MAGIC;
240	267699	return (bh);
241	267699	}
242
243		void
244	40120	VBH_destroy(struct vbh **bhp)
245		{
246		struct vbh *bh;
247		unsigned u;
248
249	40120	TAKE_OBJ_NOTNULL(bh, bhp, VBH_MAGIC);
250	40120	AZ(VBH_root(bh));
251
252	80280	for (u = 0; u < bh->length; u += ROW_WIDTH)
253	40160	free(ROW(bh, u));
254	40120	free(bh->array);
255	40120	FREE_OBJ(bh);
256	40120	}
257
258		static void
259	2792923235	vbh_update(const struct vbh *bh, unsigned u)
260		{
261	2792923235	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
262	2792923235	assert(u < bh->next);
263	2792923235	assert(A(bh, u) != NULL);
264	2792923235	if (bh->update != NULL)
265	2792923229	bh->update(bh->priv, A(bh, u), u);
266	2792923247	}
267
268		static void
269	1334941661	binhead_swap(const struct vbh *bh, unsigned u, unsigned v)
270		{
271		void *p;
272
273	1334941661	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
274	1334941661	assert(u < bh->next);
275	1334941661	assert(A(bh, u) != NULL);
276	1334941661	assert(v < bh->next);
277	1334941661	assert(A(bh, v) != NULL);
278	1334941661	p = A(bh, u);
279	1334941661	A(bh, u) = A(bh, v);
280	1334941661	A(bh, v) = p;
281	1334941661	vbh_update(bh, u);
282	1334941661	vbh_update(bh, v);
283	1334941661	}
284
285		static unsigned
286	152788741	vbh_trickleup(const struct vbh *bh, unsigned u)
287		{
288		unsigned v;
289
290	152788741	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
291	152788741	assert(u < bh->next);
292	152788741	assert(A(bh, u) != NULL);
293
294	153366726	while (u > ROOT_IDX) {
295	91771898	assert(u < bh->next);
296	91771898	assert(A(bh, u) != NULL);
297	91771898	v = parent(bh, u);
298	91771898	assert(v < u);
299	91771898	assert(v < bh->next);
300	91771898	assert(A(bh, v) != NULL);
301	91771898	if (!bh->cmp(bh->priv, A(bh, u), A(bh, v)))
302	91193913	break;
303	577985	binhead_swap(bh, u, v);
304	577985	u = v;
305		}
306	152788741	return (u);
307		}
308
309		static unsigned
310	91116668	vbh_trickledown(const struct vbh *bh, unsigned u)
311		{
312		unsigned v1, v2;
313
314	91116668	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
315	91116668	assert(u < bh->next);
316	91116668	assert(A(bh, u) != NULL);
317
318	1425480344	while (1) {
319	1425480344	assert(u < bh->next);
320	1425480344	assert(A(bh, u) != NULL);
321	1425480344	child(bh, u, &v1, &v2);
322	1425480344	assert(v1 > 0);
323	1425480344	assert(v2 > 0);
324	1425480344	assert(v1 <= v2);
325
326	1425480344	if (v1 >= bh->next)
327	91024552	return (u);
328
329	1334455792	assert(A(bh, v1) != NULL);
330	1334455792	if (v1 != v2 && v2 < bh->next) {
331	1243230427	assert(A(bh, v2) != NULL);
332	1243230427	if (bh->cmp(bh->priv, A(bh, v2), A(bh, v1)))
333	160149	v1 = v2;
334	1243230427	}
335	1334455792	assert(v1 < bh->next);
336	1334455792	assert(A(bh, v1) != NULL);
337	1334455792	if (bh->cmp(bh->priv, A(bh, u), A(bh, v1)))
338	92116	return (u);
339	1334363676	binhead_swap(bh, u, v1);
340	1334363676	u = v1;
341		}
342	91116668	}
343
344		void
345	61672074	VBH_insert(struct vbh bh, void p)
346		{
347		unsigned u;
348
349	61672074	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
350	61672074	assert(bh->length >= bh->next);
351	61672074	if (bh->length == bh->next)
352	200	vbh_addrow(bh);
353	61672074	assert(bh->length > bh->next);
354	61672074	u = bh->next++;
355	61672074	A(bh, u) = p;
356	61672074	vbh_update(bh, u);
357	61672074	(void)vbh_trickleup(bh, u);
358	61672074	assert(u < bh->next);
359	61672074	assert(A(bh, u) != NULL);
360	61672074	}
361
362
363		#ifdef PARANOIA
364		static void
365		chk(const struct vbh *bh)
366		{
367		unsigned u, v;
368
369		for (u = 2; u < bh->next; u++) {
370		v = parent(bh, u);
371		AZ(bh->cmp(bh->priv, A(bh, u), A(bh, v)));
372		}
373		}
374		#endif
375
376		void *
377	73675344	VBH_root(const struct vbh *bh)
378		{
379
380	73675344	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
381		#ifdef PARANOIA
382		chk(bh);
383		#endif
384	73675344	return (A(bh, ROOT_IDX));
385		}
386
387		/*
388		* It may seem counter-intuitive that we delete by replacement with
389		* the tail object. "That's almost certain to not belong there, in
390		* particular when we delete the root ?" is the typical reaction.
391		*
392		* If we tried to trickle up into the empty position, we would,
393		* eventually, end up with a hole in the bottom row, at which point
394		* we would move the tail object there.
395		* But there is no guarantee that the tail object would not need to
396		* trickle up from that position, in fact, it might be the new root
397		* of this half of the subtree.
398		* The total number of operations is guaranteed to be at least
399		* N{height} downward selections, because we have to get the hole
400		* all the way down, but in addition to that, we may get up to
401		* N{height}-1 upward trickles.
402		*
403		* When we fill the hole with the tail object, the worst case is
404		* that it trickles all the way up to of this half-tree, or down
405		* to become the tail object again.
406		*
407		* In other words worst case is N{height} up or downward trickles.
408		* But there is a decent chance that it does not make it all the way.
409		*/
410
411		void
412	61625456	VBH_delete(struct vbh *bh, unsigned idx)
413		{
414
415	61625456	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
416	61625456	assert(bh->next > ROOT_IDX);
417	61625456	assert(idx < bh->next);
418	61625456	assert(idx > 0);
419	61625456	assert(A(bh, idx) != NULL);
420	61625456	bh->update(bh->priv, A(bh, idx), VBH_NOIDX);
421	61625456	if (idx == --bh->next) {
422	257628	A(bh, bh->next) = NULL;
423	257628	return;
424		}
425	61367828	A(bh, idx) = A(bh, bh->next);
426	61367828	A(bh, bh->next) = NULL;
427	61367828	vbh_update(bh, idx);
428	61367828	idx = vbh_trickleup(bh, idx);
429	61367828	assert(idx < bh->next);
430	61367828	assert(idx > 0);
431	61367828	assert(A(bh, idx) != NULL);
432	61367828	idx = vbh_trickledown(bh, idx);
433	61367828	assert(idx < bh->next);
434	61367828	assert(idx > 0);
435	61367828	assert(A(bh, idx) != NULL);
436
437		/*
438		* We keep a hysteresis of one full row before we start to
439		* return space to the OS to avoid silly behaviour around
440		* row boundaries.
441		*/
442	61367828	if (bh->next + 2 * ROW_WIDTH <= bh->length) {
443	160	free(ROW(bh, bh->length - 1));
444	160	ROW(bh, bh->length - 1) = NULL;
445	160	bh->length -= ROW_WIDTH;
446	160	}
447	61625456	}
448
449		/*
450		* Move an item up/down after changing its key value
451		*/
452
453		void
454	29748840	VBH_reorder(const struct vbh *bh, unsigned idx)
455		{
456
457	29748840	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
458	29748840	assert(bh->next > ROOT_IDX);
459	29748840	assert(idx < bh->next);
460	29748840	assert(idx > 0);
461	29748840	assert(A(bh, idx) != NULL);
462	29748840	idx = vbh_trickleup(bh, idx);
463	29748840	assert(idx < bh->next);
464	29748840	assert(idx > 0);
465	29748840	assert(A(bh, idx) != NULL);
466	29748840	idx = vbh_trickledown(bh, idx);
467	29748840	assert(idx < bh->next);
468	29748840	assert(idx > 0);
469	29748840	assert(A(bh, idx) != NULL);
470	29748840	}
471
472		#ifdef TEST_DRIVER
473
474		#include <stdio.h>
475		#include <string.h>
476
477		#include "vrnd.h"
478
479		/* Test driver -------------------------------------------------------*/
480
481		struct foo {
482		unsigned magic;
483		#define FOO_MAGIC 0x23239823
484		unsigned idx;
485		unsigned key;
486		unsigned n;
487		};
488
489		#define M 500083 /* Number of operations */
490		#define N 131101 /* Number of items */
491		#define R -1 /* Random modulus */
492
493		static struct foo *ff[N];
494
495		static int v_matchproto_(vbh_cmp_t)
496	2666543560	cmp(void priv, const void a, const void *b)
497		{
498		const struct foo fa, fb;
499