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-sizeing 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 5614
vbit_rndup(unsigned bit, unsigned to)
49
{
50 5614
        bit += to - 1;
51 5614
        bit -= (bit % to);
52
53 5614
        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 5370
vbit_expand(struct vbitmap *vb, unsigned bit)
67
{
68
        unsigned char *p;
69
70 5370
        bit = vbit_rndup(bit, VBITMAP_LUMP);
71 5370
        assert(bit > vb->nbits);
72
73 5370
        if (vb->flags & VBITMAP_FL_MALLOC_BITS) {
74 0
                p = realloc(vb->bits, bit / 8);
75 0
                assert(p != NULL);
76 0
        } else {
77 5370
                p = malloc(bit / 8);
78 5370
                assert(p != NULL);
79 5370
                if (vb->nbits > 0)
80 0
                        memcpy(p, vb->bits, vb->nbits / 8);
81
        }
82 5370
        memset(p + vb->nbits / 8, 0, (bit - vb->nbits) / 8);
83 5370
        vb->flags |= VBITMAP_FL_MALLOC_BITS;
84 5370
        vb->bits = (void*)p;
85 5370
        vb->nbits = bit;
86 5370
}
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 245
vbit_init(void *p, size_t sz)
100
{
101
        struct vbitmap *vb;
102
103 245
        if (sz < sizeof(*vb))
104 0
                return (NULL);
105
106 245
        memset(p, 0, sz);
107 245
        vb = p;
108
109 245
        p = (char *)p + sizeof(*vb);
110 245
        sz -= sizeof(*vb);
111
112 245
        vb->nbits = (sz / VBITMAP_WORD) * VBITMAP_WORD;
113 245
        if (vb->nbits)
114 245
                vb->bits = p;
115
116 245
        return (vb);
117 245
}
118
119
/* init using malloc */
120
static inline struct vbitmap *
121 5370
vbit_new(unsigned initial)
122
{
123
        struct vbitmap *vb;
124
125 5370
        vb = calloc(1, sizeof *vb);
126 5370
        assert(vb != NULL);
127 5370
        vb->flags |= VBITMAP_FL_MALLOC;
128 5370
        if (initial == 0)
129 0
                initial = VBITMAP_LUMP;
130 5370
        vbit_expand(vb, initial);
131 5370
        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 26790
vbit_set(struct vbitmap *vb, unsigned bit)
151
{
152
153 26790
        if (bit >= vb->nbits)
154 0
                vbit_expand(vb, bit + 1);
155 26790
        vb->bits[VBITMAP_IDX(bit)] |= VBITMAP_BIT(bit);
156 26790
}
157
158
static inline void
159 15816
vbit_clr(const struct vbitmap *vb, unsigned bit)
160
{
161
162 15816
        if (bit < vb->nbits)
163 15816
                vb->bits[VBITMAP_IDX(bit)] &= ~VBITMAP_BIT(bit);
164 15816
}
165
166
static inline int
167 122940
vbit_test(const struct vbitmap *vb, unsigned bit)
168
{
169
170 122940
        if (bit >= vb->nbits)
171 0
                return (0);
172 122940
        return (vb->bits[VBITMAP_IDX(bit)] & VBITMAP_BIT(bit));
173 122940
}