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	2294739	parent(const struct vbh *bh, unsigned u)
102		{
103		unsigned po;
104		unsigned v;
105
106	2294739	assert(u != UINT_MAX);
107	2294739	po = u & bh->page_mask;
108
109	2294739	if (u < bh->page_size \|\| po > 3) {
110	2284900	v = (u & ~bh->page_mask) \| (po >> 1);
111	2294739	} else if (po < 2) {
112	4858	v = (u - bh->page_size) >> bh->page_shift;
113	4858	v += v & ~(bh->page_mask >> 1);
114	4858	v \|= bh->page_size / 2;
115	4858	} else {
116	4981	v = u - 2;
117		}
118	2294739	return (v);
119		}
120
121		static void
122	35637716	child(const struct vbh bh, unsigned u, unsigned a, unsigned *b)
123		{
124		uintmax_t uu;
125
126	35637716	if (u > bh->page_mask && (u & (bh->page_mask - 1)) == 0) {
127		/* First two elements are magical except on the first page */
128	2274956	a = b = u + 2;
129	35637716	} else if (u & (bh->page_size >> 1)) {
130		/* The bottom row is even more magical */
131	4532144	*a = (u & ~bh->page_mask) >> 1;
132	4532144	*a \|= u & (bh->page_mask >> 1);
133	4532144	*a += 1;
134	4532144	uu = (uintmax_t)*a << bh->page_shift;
135	4532144	*a = uu;
136	4532144	if (*a == uu) {
137	4532136	b = a + 1;
138	4532136	} 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	8	*a = UINT_MAX;
146	8	*b = UINT_MAX;
147		}
148	4532144	} else {
149		/* The rest is as usual, only inside the page */
150	28830616	*a = u + (u & bh->page_mask);
151	28830616	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	35637716	}
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	6830	vbh_addrow(struct vbh *bh)
189		{
190		unsigned u;
191
192		/* First make sure we have space for another row */
193	6830	if (&ROW(bh, bh->length) >= bh->array + bh->rows) {
194	2	u = bh->rows * 2;
195	2	bh->array = realloc(bh->array, sizeof(bh->array) u);
196	2	assert(bh->array != NULL);
197
198		/* NULL out new pointers */
199	5	while (bh->rows < u)
200	3	bh->array[bh->rows++] = NULL;
201	2	}
202	6830	assert(ROW(bh, bh->length) == NULL);
203	6830	ROW(bh, bh->length) = malloc(sizeof(*bh->array) ROW_WIDTH);
204	6830	assert(ROW(bh, bh->length));
205	6830	bh->length += ROW_WIDTH;
206	6830	}
207
208		struct vbh *
209	6825	VBH_new(void priv, vbh_cmp_t cmp_f, vbh_update_t *update_f)
210		{
211		struct vbh *bh;
212		unsigned u;
213
214	6825	ALLOC_OBJ(bh, VBH_MAGIC);
215	6825	if (bh == NULL)
216	0	return (bh);
217	6825	bh->priv = priv;
218
219	6825	bh->page_size = (unsigned)getpagesize() / sizeof (void *);
220	6825	bh->page_mask = bh->page_size - 1;
221	6825	AZ(bh->page_size & bh->page_mask); /* power of two */
222	61425	for (u = 1; (1U << u) != bh->page_size; u++)
223		;
224	6825	bh->page_shift = u;
225	6825	assert(bh->page_size <= (sizeof(*bh->array) ROW_WIDTH));
226
227	6825	bh->cmp = cmp_f;
228	6825	bh->update = update_f;
229	6825	bh->next = ROOT_IDX;
230		#ifdef TEST_DRIVER
231	1	bh->rows = 1; /* A tiny-ish number */
232		#else
233	6824	bh->rows = 16; /* A tiny-ish number */
234		#endif
235	6825	bh->array = calloc(bh->rows, sizeof *bh->array);
236	6825	assert(bh->array != NULL);
237	6825	vbh_addrow(bh);
238	6825	A(bh, ROOT_IDX) = NULL;
239	6825	bh->magic = VBH_MAGIC;
240	6825	return (bh);
241	6825	}
242
243		void
244	1021	VBH_destroy(struct vbh **bhp)
245		{
246		struct vbh *bh;
247		unsigned u;
248
249	1021	TAKE_OBJ_NOTNULL(bh, bhp, VBH_MAGIC);
250	1021	AZ(VBH_root(bh));
251
252	2043	for (u = 0; u < bh->length; u += ROW_WIDTH)
253	1022	free(ROW(bh, u));
254	1021	free(bh->array);
255	1021	FREE_OBJ(bh);
256	1021	}
257
258		static void
259	69824669	vbh_update(const struct vbh *bh, unsigned u)
260		{
261	69824669	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
262	69824669	assert(u < bh->next);
263	69824669	assert(A(bh, u) != NULL);
264	69824669	if (bh->update != NULL)
265	69824669	bh->update(bh->priv, A(bh, u), u);
266	69824669	}
267
268		static void
269	33374019	binhead_swap(const struct vbh *bh, unsigned u, unsigned v)
270		{
271		void *p;
272
273	33374019	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
274	33374019	assert(u < bh->next);
275	33374019	assert(A(bh, u) != NULL);
276	33374019	assert(v < bh->next);
277	33374019	assert(A(bh, v) != NULL);
278	33374019	p = A(bh, u);
279	33374019	A(bh, u) = A(bh, v);
280	33374019	A(bh, v) = p;
281	33374019	vbh_update(bh, u);
282	33374019	vbh_update(bh, v);
283	33374019	}
284
285		static unsigned
286	3820353	vbh_trickleup(const struct vbh *bh, unsigned u)
287		{
288		unsigned v;
289
290	3820353	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
291	3820353	assert(u < bh->next);
292	3820353	assert(A(bh, u) != NULL);
293
294	3834941	while (u > ROOT_IDX) {
295	2294739	assert(u < bh->next);
296	2294739	assert(A(bh, u) != NULL);
297	2294739	v = parent(bh, u);
298	2294739	assert(v < u);
299	2294739	assert(v < bh->next);
300	2294739	assert(A(bh, v) != NULL);
301	2294739	if (!bh->cmp(bh->priv, A(bh, u), A(bh, v)))
302	2280151	break;
303	14588	binhead_swap(bh, u, v);
304	14588	u = v;
305		}
306	3820353	return (u);
307		}
308
309		static unsigned
310	2278192	vbh_trickledown(const struct vbh *bh, unsigned u)
311		{
312		unsigned v1, v2;
313
314	2278192	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
315	2278192	assert(u < bh->next);
316	2278192	assert(A(bh, u) != NULL);
317
318	35637623	while (1) {
319	35637623	assert(u < bh->next);
320	35637623	assert(A(bh, u) != NULL);
321	35637623	child(bh, u, &v1, &v2);
322	35637623	assert(v1 > 0);
323	35637623	assert(v2 > 0);
324	35637623	assert(v1 <= v2);
325
326	35637623	if (v1 >= bh->next)
327	2275929	return (u);
328
329	33361694	assert(A(bh, v1) != NULL);
330	33361694	if (v1 != v2 && v2 < bh->next) {
331	31081003	assert(A(bh, v2) != NULL);
332	31081003	if (bh->cmp(bh->priv, A(bh, v2), A(bh, v1)))
333	3995	v1 = v2;
334	31081003	}
335	33361694	assert(v1 < bh->next);
336	33361694	assert(A(bh, v1) != NULL);
337	33361694	if (bh->cmp(bh->priv, A(bh, u), A(bh, v1)))
338	2263	return (u);
339	33359431	binhead_swap(bh, u, v1);
340	33359431	u = v1;
341		}
342	2278192	}
343
344		void
345	1542161	VBH_insert(struct vbh bh, void p)
346		{
347		unsigned u;
348
349	1542161	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
350	1542161	assert(bh->length >= bh->next);
351	1542161	if (bh->length == bh->next)
352	5	vbh_addrow(bh);
353	1542161	assert(bh->length > bh->next);
354	1542161	u = bh->next++;
355	1542161	A(bh, u) = p;
356	1542161	vbh_update(bh, u);
357	1542161	(void)vbh_trickleup(bh, u);
358	1542161	assert(u < bh->next);
359	1542161	assert(A(bh, u) != NULL);
360	1542161	}
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	1842941	VBH_root(const struct vbh *bh)
378		{
379
380	1842941	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
381		#ifdef PARANOIA
382		chk(bh);
383		#endif
384	1842941	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	1540956	VBH_delete(struct vbh *bh, unsigned idx)
413		{
414
415	1540956	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
416	1540956	assert(bh->next > ROOT_IDX);
417	1540956	assert(idx < bh->next);
418	1540956	assert(idx > 0);
419	1540956	assert(A(bh, idx) != NULL);
420	1540956	bh->update(bh->priv, A(bh, idx), VBH_NOIDX);
421	1540956	if (idx == --bh->next) {
422	6485	A(bh, bh->next) = NULL;
423	6485	return;
424		}
425	1534471	A(bh, idx) = A(bh, bh->next);
426	1534471	A(bh, bh->next) = NULL;
427	1534471	vbh_update(bh, idx);
428	1534471	idx = vbh_trickleup(bh, idx);
429	1534471	assert(idx < bh->next);
430	1534471	assert(idx > 0);
431	1534471	assert(A(bh, idx) != NULL);
432	1534471	idx = vbh_trickledown(bh, idx);
433	1534471	assert(idx < bh->next);
434	1534471	assert(idx > 0);
435	1534471	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	1534471	if (bh->next + 2 * ROW_WIDTH <= bh->length) {
443	4	free(ROW(bh, bh->length - 1));
444	4	ROW(bh, bh->length - 1) = NULL;
445	4	bh->length -= ROW_WIDTH;
446	4	}
447	1540956	}
448
449		/*
450		* Move an item up/down after changing its key value
451		*/
452
453		void
454	743721	VBH_reorder(const struct vbh *bh, unsigned idx)
455		{
456
457	743721	CHECK_OBJ_NOTNULL(bh, VBH_MAGIC);
458	743721	assert(bh->next > ROOT_IDX);
459	743721	assert(idx < bh->next);
460	743721	assert(idx > 0);
461	743721	assert(A(bh, idx) != NULL);
462	743721	idx = vbh_trickleup(bh, idx);
463	743721	assert(idx < bh->next);
464	743721	assert(idx > 0);
465	743721	assert(A(bh, idx) != NULL);
466	743721	idx = vbh_trickledown(bh, idx);
467	743721	assert(idx < bh->next);
468	743721	assert(idx > 0);
469	743721	assert(A(bh, idx) != NULL);
470	743721	}
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	66663589	cmp(void priv, const void a, const void *b)
497		{
498		const struct foo fa, fb;
499