From b7803ec19d6dcc0ea5cc56ac4fc958f8b7c61b12 Mon Sep 17 00:00:00 2001 From: phk Date: Sun, 22 Jun 2008 11:41:32 +0000 Subject: [PATCH] Add VBM, a resizing bitmap implementation we previously had in kqueue. git-svn-id: svn+ssh://projects.linpro.no/svn/varnish/trunk@2769 d4fa192b-c00b-0410-8231-f00ffab90ce4 --- varnish-cache/include/vbm.h | 103 ++++++++++++++++++++++++++++++++++++ 1 file changed, 103 insertions(+) create mode 100644 varnish-cache/include/vbm.h diff --git a/varnish-cache/include/vbm.h b/varnish-cache/include/vbm.h new file mode 100644 index 00000000..7015a1d9 --- /dev/null +++ b/varnish-cache/include/vbm.h @@ -0,0 +1,103 @@ +/*- + * Copyright (c) 2006 Verdens Gang AS + * Copyright (c) 2006-2008 Linpro AS + * All rights reserved. + * + * Author: Poul-Henning Kamp + * + * 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. + * + * $Id: cache_acceptor_kqueue.c 2513 2008-02-18 17:04:30Z des $ + * + * Self-sizeing bitmap operations + */ + +#include "config.h" + +/********************************************************************** + * Generic bitmap functions, may be generalized at some point. + */ + +#define VBITMAP_TYPE unsigned /* Our preferred wordsize */ +#define VBITMAP_LUMP (32*1024) /* How many bits we alloc at a time */ +#define VBITMAP_WORD (sizeof(VBITMAP_TYPE) * 8) +#define VBITMAP_IDX(n) (n / VBITMAP_WORD) +#define VBITMAP_BIT(n) (1U << (n % VBITMAP_WORD)) + +struct vbitmap { + VBITMAP_TYPE *bits; + unsigned nbits; +}; + +static inline void +vbit_expand(struct vbitmap *vb, unsigned bit) +{ + unsigned char *p; + + bit += VBITMAP_LUMP - 1; + bit -= (bit % VBITMAP_LUMP); + p = realloc(vb->bits, bit / 8); + AN(p); + memset(p + vb->nbits / 8, 0, (bit - vb->nbits) / 8); + vb->bits = (void*)p; + vb->nbits = bit; +} + +static inline struct vbitmap * +vbit_init(unsigned initial) +{ + struct vbitmap *vb; + + vb = calloc(sizeof *vb, 1); + AN(vb); + if (initial == 0) + initial = VBITMAP_LUMP; + vbit_expand(vb, initial); + return (vb); +} + +static inline void +vbit_set(struct vbitmap *vb, unsigned bit) +{ + + if (bit >= vb->nbits) + vbit_expand(vb, bit); + vb->bits[VBITMAP_IDX(bit)] |= VBITMAP_BIT(bit); +} + +static inline void +vbit_clr(struct vbitmap *vb, unsigned bit) +{ + + if (bit >= vb->nbits) + vbit_expand(vb, bit); + vb->bits[VBITMAP_IDX(bit)] &= ~VBITMAP_BIT(bit); +} + +static inline int +vbit_test(struct vbitmap *vb, unsigned bit) +{ + + if (bit >= vb->nbits) + vbit_expand(vb, bit); + return (vb->bits[VBITMAP_IDX(bit)] & VBITMAP_BIT(bit)); +} -- 2.39.5