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