varnish-cache/include/vbm.h
1
/*-
2
 * Copyright (c) 2006 Verdens Gang AS
3
 * Copyright (c) 2006-2010 Varnish Software AS
4
 * All rights reserved.
5
 *
6
 * Author: Poul-Henning Kamp <phk@phk.freebsd.dk>
7
 *
8
 * SPDX-License-Identifier: BSD-2-Clause
9
 *
10
 * Redistribution and use in source and binary forms, with or without
11
 * modification, are permitted provided that the following conditions
12
 * are met:
13
 * 1. Redistributions of source code must retain the above copyright
14
 *    notice, this list of conditions and the following disclaimer.
15
 * 2. Redistributions in binary form must reproduce the above copyright
16
 *    notice, this list of conditions and the following disclaimer in the
17
 *    documentation and/or other materials provided with the distribution.
18
 *
19
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
20
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
23
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29
 * SUCH DAMAGE.
30
 *
31
 * Self-sizeing bitmap operations
32
 */
33
34
#include <stdlib.h>
35
#include <string.h>
36
#include <stdint.h>
37
38
/**********************************************************************
39
 * Generic bitmap functions
40
 */
41
42
#define VBITMAP_TYPE    unsigned        /* Our preferred wordsize */
43
#define VBITMAP_LUMP    (1024)          /* How many bits we alloc at a time */
44
#define VBITMAP_WORD    (sizeof(VBITMAP_TYPE) * 8)
45
#define VBITMAP_IDX(n)  ((n) / VBITMAP_WORD)
46
#define VBITMAP_BIT(n)  (1U << ((n) % VBITMAP_WORD))
47
48
static inline unsigned
49 3264
vbit_rndup(unsigned bit, unsigned to)
50
{
51 3264
        bit += to - 1;
52 3264
        bit -= (bit % to);
53
54 3264
        return (bit);
55
}
56
57
struct vbitmap {
58
        unsigned        flags;
59
#define VBITMAP_FL_MALLOC        1      /* struct vbitmap is malloced */
60
#define VBITMAP_FL_MALLOC_BITS  (1<<1)  /* bits space is malloced */
61
62
        VBITMAP_TYPE    *bits;
63
        unsigned        nbits;
64
};
65
66
static inline void
67 3203
vbit_expand(struct vbitmap *vb, unsigned bit)
68
{
69
        unsigned char *p;
70
71 3203
        bit = vbit_rndup(bit, VBITMAP_LUMP);
72 3203
        assert(bit > vb->nbits);
73
74 3203
        if (vb->flags & VBITMAP_FL_MALLOC_BITS) {
75 2
                p = realloc(vb->bits, bit / 8);
76 2
                assert(p != NULL);
77 2
        } else {
78 3201
                p = malloc(bit / 8);
79 3201
                assert(p != NULL);
80 3201
                if (vb->nbits > 0)
81 1
                        memcpy(p, vb->bits, vb->nbits / 8);
82
        }
83 3203
        memset(p + vb->nbits / 8, 0, (bit - vb->nbits) / 8);
84 3203
        vb->flags |= VBITMAP_FL_MALLOC_BITS;
85 3203
        vb->bits = (void*)p;
86 3203
        vb->nbits = bit;
87 3203
}
88
89
#define VBITMAP_SZ(b) (sizeof(struct vbitmap) + \
90
        vbit_rndup(b, VBITMAP_WORD))
91
92
/*
93
 * init from some extent of memory (e.g. workspace) which the caller must
94
 * manage. Returns a vbitmap with as many bits as fit into sz in VBITMAP_WORD
95
 * chunks.
96
 *
97
 * use VBITMAP_SZ to calculate sz
98
 */
99
static inline struct vbitmap *
100 61
vbit_init(void *p, size_t sz)
101
{
102
        struct vbitmap *vb;
103
104 61
        if (sz < sizeof(*vb))
105 0
                return NULL;
106
107 61
        memset(p, 0, sz);
108 61
        vb = p;
109
110 61
        p = (char *)p + sizeof(*vb);
111 61
        sz -= sizeof(*vb);
112
113 61
        vb->nbits = (sz / VBITMAP_WORD) * VBITMAP_WORD;
114 61
        if (vb->nbits)
115 61
                vb->bits = p;
116
117 61
        return (vb);
118 61
}
119
120
/* init using malloc */
121
static inline struct vbitmap *
122 3200
vbit_new(unsigned initial)
123
{
124
        struct vbitmap *vb;
125
126 3200
        vb = calloc(1, sizeof *vb);
127 3200
        assert(vb != NULL);
128 3200
        vb->flags |= VBITMAP_FL_MALLOC;
129 3200
        if (initial == 0)
130 0
                initial = VBITMAP_LUMP;
131 3200
        vbit_expand(vb, initial);
132 3200
        return (vb);
133
}
134
135
static inline void
136 2164
vbit_destroy(struct vbitmap *vb)
137
{
138
139 2164
        if (vb == NULL)
140 0
                return;
141 2164
        if (vb->flags & VBITMAP_FL_MALLOC_BITS) {
142 2103
                free(vb->bits);
143 2103
                vb->bits = NULL;
144 2103
                vb->nbits = 0;
145 2103
        }
146 2164
        if (vb->flags & VBITMAP_FL_MALLOC)
147 2101
                free(vb);
148 2164
}
149
150
static inline void
151 9265
vbit_set(struct vbitmap *vb, unsigned bit)
152
{
153
154 9265
        if (bit >= vb->nbits)
155 3
                vbit_expand(vb, bit + 1);
156 9265
        vb->bits[VBITMAP_IDX(bit)] |= VBITMAP_BIT(bit);
157 9265
}
158
159
static inline void
160 2387
vbit_clr(const struct vbitmap *vb, unsigned bit)
161
{
162
163 2387
        if (bit < vb->nbits)
164 2387
                vb->bits[VBITMAP_IDX(bit)] &= ~VBITMAP_BIT(bit);
165 2387
}
166
167
static inline int
168 64399
vbit_test(const struct vbitmap *vb, unsigned bit)
169
{
170
171 64399
        if (bit >= vb->nbits)
172 0
                return (0);
173 64399
        return (vb->bits[VBITMAP_IDX(bit)] & VBITMAP_BIT(bit));
174 64398
}