GCOV - Varnish Cache


/*-
 * Copyright (c) 2006 Verdens Gang AS
 * Copyright (c) 2006-2010 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.
 *
 * Self-sizing bitmap operations
 */

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

/**********************************************************************
 * Generic bitmap functions
 */

#define VBITMAP_TYPE    unsigned        /* Our preferred wordsize */
#define VBITMAP_LUMP    (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))

static inline unsigned
vbit_rndup(unsigned bit, unsigned to)
{
        bit += to - 1;
        bit -= (bit % to);

        return (bit);
}

struct vbitmap {
        unsigned        flags;
#define VBITMAP_FL_MALLOC        1      /* struct vbitmap is malloced */
#define VBITMAP_FL_MALLOC_BITS  (1<<1)  /* bits space is malloced */

        VBITMAP_TYPE    *bits;
        unsigned        nbits;
};

static inline void
vbit_expand(struct vbitmap *vb, unsigned bit)
{
        unsigned char *p;

        bit = vbit_rndup(bit, VBITMAP_LUMP);
        assert(bit > vb->nbits);

        if (vb->flags & VBITMAP_FL_MALLOC_BITS) {
                p = realloc(vb->bits, bit / 8);
                assert(p != NULL);
        } else {
                p = malloc(bit / 8);
                assert(p != NULL);
                if (vb->nbits > 0)
                        memcpy(p, vb->bits, vb->nbits / 8);
        }
        memset(p + vb->nbits / 8, 0, (bit - vb->nbits) / 8);
        vb->flags |= VBITMAP_FL_MALLOC_BITS;
        vb->bits = (void*)p;
        vb->nbits = bit;
}

#define VBITMAP_SZ(b) (sizeof(struct vbitmap) + \
        vbit_rndup(b, VBITMAP_WORD))

/*
 * init from some extent of memory (e.g. workspace) which the caller must
 * manage. Returns a vbitmap with as many bits as fit into sz in VBITMAP_WORD
 * chunks.
 *
 * use VBITMAP_SZ to calculate sz
 */
static inline struct vbitmap *
vbit_init(void *p, size_t sz)
{
        struct vbitmap *vb;

        if (sz < sizeof(*vb))
                return (NULL);

        memset(p, 0, sz);
        vb = p;

        p = (char *)p + sizeof(*vb);
        sz -= sizeof(*vb);

        vb->nbits = (sz / VBITMAP_WORD) * VBITMAP_WORD;
        if (vb->nbits)
                vb->bits = p;

        return (vb);
}

/* init using malloc */
static inline struct vbitmap *
vbit_new(unsigned initial)
{
        struct vbitmap *vb;

        vb = calloc(1, sizeof *vb);
        assert(vb != NULL);
        vb->flags |= VBITMAP_FL_MALLOC;
        if (initial == 0)
                initial = VBITMAP_LUMP;
        vbit_expand(vb, initial);
        return (vb);
}

static inline void
vbit_destroy(struct vbitmap *vb)
{

        if (vb == NULL)
                return;
        if (vb->flags & VBITMAP_FL_MALLOC_BITS) {
                free(vb->bits);
                vb->bits = NULL;
                vb->nbits = 0;
        }
        if (vb->flags & VBITMAP_FL_MALLOC)
                free(vb);
}

static inline void
vbit_set(struct vbitmap *vb, unsigned bit)
{

        if (bit >= vb->nbits)
                vbit_expand(vb, bit + 1);
        vb->bits[VBITMAP_IDX(bit)] |= VBITMAP_BIT(bit);
}

static inline void
vbit_clr(const struct vbitmap *vb, unsigned bit)
{

        if (bit < vb->nbits)
                vb->bits[VBITMAP_IDX(bit)] &= ~VBITMAP_BIT(bit);
}

static inline int
vbit_test(const struct vbitmap *vb, unsigned bit)
{

        if (bit >= vb->nbits)
                return (0);
        return (vb->bits[VBITMAP_IDX(bit)] & VBITMAP_BIT(bit));
}

		varnish-cache/include/vbm.h
0		/*-
1		* Copyright (c) 2006 Verdens Gang AS
2		* Copyright (c) 2006-2010 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		* Self-sizing bitmap operations
31		*/
32
33		#include <stdlib.h>
34		#include <string.h>
35		#include <stdint.h>
36
37		/**********************************************************************
38		* Generic bitmap functions
39		*/
40
41		#define VBITMAP_TYPE unsigned /* Our preferred wordsize */
42		#define VBITMAP_LUMP (1024) /* How many bits we alloc at a time */
43		#define VBITMAP_WORD (sizeof(VBITMAP_TYPE) * 8)
44		#define VBITMAP_IDX(n) ((n) / VBITMAP_WORD)
45		#define VBITMAP_BIT(n) (1U << ((n) % VBITMAP_WORD))
46
47		static inline unsigned
48	39916	vbit_rndup(unsigned bit, unsigned to)
49		{
50	39916	bit += to - 1;
51	39916	bit -= (bit % to);
52
53	39916	return (bit);
54		}
55
56		struct vbitmap {
57		unsigned flags;
58		#define VBITMAP_FL_MALLOC 1 /* struct vbitmap is malloced */
59		#define VBITMAP_FL_MALLOC_BITS (1<<1) /* bits space is malloced */
60
61		VBITMAP_TYPE *bits;
62		unsigned nbits;
63		};
64
65		static inline void
66	38280	vbit_expand(struct vbitmap *vb, unsigned bit)
67		{
68		unsigned char *p;
69
70	38280	bit = vbit_rndup(bit, VBITMAP_LUMP);
71	38280	assert(bit > vb->nbits);
72
73	38280	if (vb->flags & VBITMAP_FL_MALLOC_BITS) {
74	0	p = realloc(vb->bits, bit / 8);
75	0	assert(p != NULL);
76	0	} else {
77	38280	p = malloc(bit / 8);
78	38280	assert(p != NULL);
79	38280	if (vb->nbits > 0)
80	0	memcpy(p, vb->bits, vb->nbits / 8);
81		}
82	38280	memset(p + vb->nbits / 8, 0, (bit - vb->nbits) / 8);
83	38280	vb->flags \|= VBITMAP_FL_MALLOC_BITS;
84	38280	vb->bits = (void*)p;
85	38280	vb->nbits = bit;
86	38280	}
87
88		#define VBITMAP_SZ(b) (sizeof(struct vbitmap) + \
89		vbit_rndup(b, VBITMAP_WORD))
90
91		/*
92		* init from some extent of memory (e.g. workspace) which the caller must
93		* manage. Returns a vbitmap with as many bits as fit into sz in VBITMAP_WORD
94		* chunks.
95		*
96		* use VBITMAP_SZ to calculate sz
97		*/
98		static inline struct vbitmap *
99	1634	vbit_init(void *p, size_t sz)
100		{
101		struct vbitmap *vb;
102
103	1634	if (sz < sizeof(*vb))
104	0	return (NULL);
105
106	1634	memset(p, 0, sz);
107	1634	vb = p;
108
109	1634	p = (char )p + sizeof(vb);
110	1634	sz -= sizeof(*vb);
111
112	1634	vb->nbits = (sz / VBITMAP_WORD) * VBITMAP_WORD;
113	1634	if (vb->nbits)
114	1634	vb->bits = p;
115
116	1634	return (vb);
117	1634	}
118
119		/* init using malloc */
120		static inline struct vbitmap *
121	38280	vbit_new(unsigned initial)
122		{
123		struct vbitmap *vb;
124
125	38280	vb = calloc(1, sizeof *vb);
126	38280	assert(vb != NULL);
127	38280	vb->flags \|= VBITMAP_FL_MALLOC;
128	38280	if (initial == 0)
129	0	initial = VBITMAP_LUMP;
130	38280	vbit_expand(vb, initial);
131	38280	return (vb);
132		}
133
134		static inline void
135		vbit_destroy(struct vbitmap *vb)
136		{
137
138		if (vb == NULL)
139		return;
140		if (vb->flags & VBITMAP_FL_MALLOC_BITS) {
141		free(vb->bits);
142		vb->bits = NULL;
143		vb->nbits = 0;
144		}
145		if (vb->flags & VBITMAP_FL_MALLOC)
146		free(vb);
147		}
148
149		static inline void
150	155120	vbit_set(struct vbitmap *vb, unsigned bit)
151		{
152
153	155120	if (bit >= vb->nbits)
154	0	vbit_expand(vb, bit + 1);
155	155120	vb->bits[VBITMAP_IDX(bit)] \|= VBITMAP_BIT(bit);
156	155120	}
157
158		static inline void
159	76280	vbit_clr(const struct vbitmap *vb, unsigned bit)
160		{
161
162	76280	if (bit < vb->nbits)
163	76280	vb->bits[VBITMAP_IDX(bit)] &= ~VBITMAP_BIT(bit);
164	76280	}
165
166		static inline int
167	811446	vbit_test(const struct vbitmap *vb, unsigned bit)
168		{
169
170	811446	if (bit >= vb->nbits)
171	0	return (0);
172	811446	return (vb->bits[VBITMAP_IDX(bit)] & VBITMAP_BIT(bit));
173	811446	}