From b7803ec19d6dcc0ea5cc56ac4fc958f8b7c61b12 Mon Sep 17 00:00:00 2001
From: phk <phk@d4fa192b-c00b-0410-8231-f00ffab90ce4>
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 <phk@phk.freebsd.dk>
+ *
+ * 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