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	127080	vbit_rndup(unsigned bit, unsigned to)
49		{
50	127080	bit += to - 1;
51	127080	bit -= (bit % to);
52
53	127080	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	122880	vbit_expand(struct vbitmap *vb, unsigned bit)
67		{
68		unsigned char *p;
69
70	122880	bit = vbit_rndup(bit, VBITMAP_LUMP);
71	122880	assert(bit > vb->nbits);
72
73	122880	if (vb->flags & VBITMAP_FL_MALLOC_BITS) {
74	80	p = realloc(vb->bits, bit / 8);
75	80	assert(p != NULL);
76	80	} else {
77	122800	p = malloc(bit / 8);
78	122800	assert(p != NULL);
79	122800	if (vb->nbits > 0)
80	40	memcpy(p, vb->bits, vb->nbits / 8);
81		}
82	122880	memset(p + vb->nbits / 8, 0, (bit - vb->nbits) / 8);
83	122880	vb->flags \|= VBITMAP_FL_MALLOC_BITS;
84	122880	vb->bits = (void*)p;
85	122880	vb->nbits = bit;
86	122880	}
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	4200	vbit_init(void *p, size_t sz)
100		{
101		struct vbitmap *vb;
102
103	4200	if (sz < sizeof(*vb))
104	0	return (NULL);
105
106	4200	memset(p, 0, sz);
107	4200	vb = p;
108
109	4200	p = (char )p + sizeof(vb);
110	4200	sz -= sizeof(*vb);
111
112	4200	vb->nbits = (sz / VBITMAP_WORD) * VBITMAP_WORD;
113	4200	if (vb->nbits)
114	4200	vb->bits = p;
115
116	4200	return (vb);
117	4200	}
118
119		/* init using malloc */
120		static inline struct vbitmap *
121	122760	vbit_new(unsigned initial)
122		{
123		struct vbitmap *vb;
124
125	122760	vb = calloc(1, sizeof *vb);
126	122760	assert(vb != NULL);
127	122760	vb->flags \|= VBITMAP_FL_MALLOC;
128	122760	if (initial == 0)
129	0	initial = VBITMAP_LUMP;
130	122760	vbit_expand(vb, initial);
131	122760	return (vb);
132		}
133
134		static inline void
135	114480	vbit_destroy(struct vbitmap *vb)
136		{
137
138	114480	if (vb == NULL)
139	0	return;
140	114480	if (vb->flags & VBITMAP_FL_MALLOC_BITS) {
141	110280	free(vb->bits);
142	110280	vb->bits = NULL;
143	110280	vb->nbits = 0;
144	110280	}
145	114480	if (vb->flags & VBITMAP_FL_MALLOC)
146	110200	free(vb);
147	114480	}
148
149		static inline void
150	298400	vbit_set(struct vbitmap *vb, unsigned bit)
151		{
152
153	298400	if (bit >= vb->nbits)
154	120	vbit_expand(vb, bit + 1);
155	298400	vb->bits[VBITMAP_IDX(bit)] \|= VBITMAP_BIT(bit);
156	298400	}
157
158		static inline void
159	1760	vbit_clr(const struct vbitmap *vb, unsigned bit)
160		{
161
162	1760	if (bit < vb->nbits)
163	1760	vb->bits[VBITMAP_IDX(bit)] &= ~VBITMAP_BIT(bit);
164	1760	}
165
166		static inline int
167	3317432	vbit_test(const struct vbitmap *vb, unsigned bit)
168		{
169
170	3317432	if (bit >= vb->nbits)
171	0	return (0);
172	3317432	return (vb->bits[VBITMAP_IDX(bit)] & VBITMAP_BIT(bit));
173	3317432	}