2 * Copyright 2012-2015 Samy Al Bahra.
3 * Copyright 2012-2014 AppNexus, Inc.
4 * Copyright 2014 Paul Khuong.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 #include <ck_limits.h>
35 #include <ck_stdint.h>
36 #include <ck_stdbool.h>
37 #include <ck_stddef.h>
38 #include <ck_stdbool.h>
39 #include <ck_stddef.h>
40 #include <ck_string.h>
42 #if !defined(CK_F_PR_LOAD_UINT) || !defined(CK_F_PR_STORE_UINT) || \
43 !defined(CK_F_PR_AND_UINT) || !defined(CK_F_PR_OR_UINT) || \
45 #error "ck_bitmap is not supported on your platform."
48 #define CK_BITMAP_BLOCK (sizeof(unsigned int) * CHAR_BIT)
49 #define CK_BITMAP_OFFSET(i) ((i) % CK_BITMAP_BLOCK)
50 #define CK_BITMAP_BIT(i) (1U << CK_BITMAP_OFFSET(i))
51 #define CK_BITMAP_PTR(x, i) ((x) + ((i) / CK_BITMAP_BLOCK))
52 #define CK_BITMAP_BLOCKS(n) (((n) + CK_BITMAP_BLOCK - 1) / CK_BITMAP_BLOCK)
54 #define CK_BITMAP_INSTANCE(n_entries) \
57 unsigned int n_bits; \
58 unsigned int map[CK_BITMAP_BLOCKS(n_entries)]; \
60 struct ck_bitmap bitmap; \
63 #define CK_BITMAP_ITERATOR_INIT(a, b) \
64 ck_bitmap_iterator_init((a), &(b)->bitmap)
66 #define CK_BITMAP_INIT(a, b, c) \
67 ck_bitmap_init(&(a)->bitmap, (b), (c))
69 #define CK_BITMAP_NEXT(a, b, c) \
70 ck_bitmap_next(&(a)->bitmap, (b), (c))
72 #define CK_BITMAP_SET(a, b) \
73 ck_bitmap_set(&(a)->bitmap, (b))
75 #define CK_BITMAP_BTS(a, b) \
76 ck_bitmap_bts(&(a)->bitmap, (b))
78 #define CK_BITMAP_RESET(a, b) \
79 ck_bitmap_reset(&(a)->bitmap, (b))
81 #define CK_BITMAP_TEST(a, b) \
82 ck_bitmap_test(&(a)->bitmap, (b))
84 #define CK_BITMAP_UNION(a, b) \
85 ck_bitmap_union(&(a)->bitmap, &(b)->bitmap)
87 #define CK_BITMAP_INTERSECTION(a, b) \
88 ck_bitmap_intersection(&(a)->bitmap, &(b)->bitmap)
90 #define CK_BITMAP_INTERSECTION_NEGATE(a, b) \
91 ck_bitmap_intersection_negate(&(a)->bitmap, &(b)->bitmap)
93 #define CK_BITMAP_CLEAR(a) \
94 ck_bitmap_clear(&(a)->bitmap)
96 #define CK_BITMAP_EMPTY(a, b) \
97 ck_bitmap_empty(&(a)->bitmap, b)
99 #define CK_BITMAP_FULL(a, b) \
100 ck_bitmap_full(&(a)->bitmap, b)
102 #define CK_BITMAP_COUNT(a, b) \
103 ck_bitmap_count(&(a)->bitmap, b)
105 #define CK_BITMAP_COUNT_INTERSECT(a, b, c) \
106 ck_bitmap_count_intersect(&(a)->bitmap, b, c)
108 #define CK_BITMAP_BITS(a) \
109 ck_bitmap_bits(&(a)->bitmap)
111 #define CK_BITMAP_BUFFER(a) \
112 ck_bitmap_buffer(&(a)->bitmap)
114 #define CK_BITMAP(a) \
121 typedef struct ck_bitmap ck_bitmap_t;
123 struct ck_bitmap_iterator {
125 unsigned int n_block;
126 unsigned int n_limit;
128 typedef struct ck_bitmap_iterator ck_bitmap_iterator_t;
130 CK_CC_INLINE static unsigned int
131 ck_bitmap_base(unsigned int n_bits)
134 return CK_BITMAP_BLOCKS(n_bits) * sizeof(unsigned int);
138 * Returns the required number of bytes for a ck_bitmap_t object supporting the
139 * specified number of bits.
141 CK_CC_INLINE static unsigned int
142 ck_bitmap_size(unsigned int n_bits)
145 return ck_bitmap_base(n_bits) + sizeof(struct ck_bitmap);
149 * Returns total number of bits in specified bitmap.
151 CK_CC_INLINE static unsigned int
152 ck_bitmap_bits(const struct ck_bitmap *bitmap)
155 return bitmap->n_bits;
159 * Returns a pointer to the bit buffer associated
160 * with the specified bitmap.
162 CK_CC_INLINE static void *
163 ck_bitmap_buffer(struct ck_bitmap *bitmap)
170 * Sets the bit at the offset specified in the second argument.
172 CK_CC_INLINE static void
173 ck_bitmap_set(struct ck_bitmap *bitmap, unsigned int n)
176 ck_pr_or_uint(CK_BITMAP_PTR(bitmap->map, n), CK_BITMAP_BIT(n));
181 * Performs a test-and-set operation at the offset specified in the
183 * Returns true if the bit at the specified offset was already set,
186 CK_CC_INLINE static bool
187 ck_bitmap_bts(struct ck_bitmap *bitmap, unsigned int n)
190 return ck_pr_bts_uint(CK_BITMAP_PTR(bitmap->map, n),
191 CK_BITMAP_OFFSET(n));
195 * Resets the bit at the offset specified in the second argument.
197 CK_CC_INLINE static void
198 ck_bitmap_reset(struct ck_bitmap *bitmap, unsigned int n)
201 ck_pr_and_uint(CK_BITMAP_PTR(bitmap->map, n), ~CK_BITMAP_BIT(n));
206 * Determines whether the bit at offset specified in the
207 * second argument is set.
209 CK_CC_INLINE static bool
210 ck_bitmap_test(const struct ck_bitmap *bitmap, unsigned int n)
214 block = ck_pr_load_uint(CK_BITMAP_PTR(bitmap->map, n));
215 return block & CK_BITMAP_BIT(n);
219 * Combines bits from second bitmap into the first bitmap. This is not a
220 * linearized operation with respect to the complete bitmap.
222 CK_CC_INLINE static void
223 ck_bitmap_union(struct ck_bitmap *dst, const struct ck_bitmap *src)
226 unsigned int n_buckets = dst->n_bits;
228 if (src->n_bits < dst->n_bits)
229 n_buckets = src->n_bits;
231 n_buckets = CK_BITMAP_BLOCKS(n_buckets);
232 for (n = 0; n < n_buckets; n++) {
233 ck_pr_or_uint(&dst->map[n],
234 ck_pr_load_uint(&src->map[n]));
241 * Intersects bits from second bitmap into the first bitmap. This is
242 * not a linearized operation with respect to the complete bitmap.
243 * Any trailing bit in dst is cleared.
245 CK_CC_INLINE static void
246 ck_bitmap_intersection(struct ck_bitmap *dst, const struct ck_bitmap *src)
249 unsigned int n_buckets = dst->n_bits;
250 unsigned int n_intersect = n_buckets;
252 if (src->n_bits < n_intersect)
253 n_intersect = src->n_bits;
255 n_buckets = CK_BITMAP_BLOCKS(n_buckets);
256 n_intersect = CK_BITMAP_BLOCKS(n_intersect);
257 for (n = 0; n < n_intersect; n++) {
258 ck_pr_and_uint(&dst->map[n],
259 ck_pr_load_uint(&src->map[n]));
262 for (; n < n_buckets; n++)
263 ck_pr_store_uint(&dst->map[n], 0);
269 * Intersects the complement of bits from second bitmap into the first
270 * bitmap. This is not a linearized operation with respect to the
271 * complete bitmap. Any trailing bit in dst is left as is.
273 CK_CC_INLINE static void
274 ck_bitmap_intersection_negate(struct ck_bitmap *dst,
275 const struct ck_bitmap *src)
278 unsigned int n_intersect = dst->n_bits;
280 if (src->n_bits < n_intersect)
281 n_intersect = src->n_bits;
283 n_intersect = CK_BITMAP_BLOCKS(n_intersect);
284 for (n = 0; n < n_intersect; n++) {
285 ck_pr_and_uint(&dst->map[n],
286 (~ck_pr_load_uint(&src->map[n])));
293 * Resets all bits in the provided bitmap. This is not a linearized
294 * operation in ck_bitmap.
296 CK_CC_INLINE static void
297 ck_bitmap_clear(struct ck_bitmap *bitmap)
300 unsigned int n_buckets = ck_bitmap_base(bitmap->n_bits) /
301 sizeof(unsigned int);
303 for (i = 0; i < n_buckets; i++)
304 ck_pr_store_uint(&bitmap->map[i], 0);
310 * Returns true if the first limit bits in bitmap are cleared. If
311 * limit is greater than the bitmap size, limit is truncated to that
314 CK_CC_INLINE static bool
315 ck_bitmap_empty(const ck_bitmap_t *bitmap, unsigned int limit)
317 unsigned int i, words, slop;
319 if (limit > bitmap->n_bits)
320 limit = bitmap->n_bits;
322 words = limit / CK_BITMAP_BLOCK;
323 slop = limit % CK_BITMAP_BLOCK;
324 for (i = 0; i < words; i++) {
325 if (ck_pr_load_uint(&bitmap->map[i]) != 0) {
333 word = ck_pr_load_uint(&bitmap->map[i]);
334 if ((word & ((1U << slop) - 1)) != 0)
342 * Returns true if the first limit bits in bitmap are set. If limit
343 * is greater than the bitmap size, limit is truncated to that size.
345 CK_CC_UNUSED static bool
346 ck_bitmap_full(const ck_bitmap_t *bitmap, unsigned int limit)
348 unsigned int i, slop, words;
350 if (limit > bitmap->n_bits) {
351 limit = bitmap->n_bits;
354 words = limit / CK_BITMAP_BLOCK;
355 slop = limit % CK_BITMAP_BLOCK;
356 for (i = 0; i < words; i++) {
357 if (ck_pr_load_uint(&bitmap->map[i]) != -1U)
364 word = ~ck_pr_load_uint(&bitmap->map[i]);
365 if ((word & ((1U << slop) - 1)) != 0)
372 * Returns the number of set bit in bitmap, upto (and excluding)
373 * limit. If limit is greater than the bitmap size, it is truncated
376 CK_CC_INLINE static unsigned int
377 ck_bitmap_count(const ck_bitmap_t *bitmap, unsigned int limit)
379 unsigned int count, i, slop, words;
381 if (limit > bitmap->n_bits)
382 limit = bitmap->n_bits;
384 words = limit / CK_BITMAP_BLOCK;
385 slop = limit % CK_BITMAP_BLOCK;
386 for (i = 0, count = 0; i < words; i++)
387 count += ck_cc_popcount(ck_pr_load_uint(&bitmap->map[i]));
392 word = ck_pr_load_uint(&bitmap->map[i]);
393 count += ck_cc_popcount(word & ((1U << slop) - 1));
399 * Returns the number of set bit in the intersection of two bitmaps,
400 * upto (and excluding) limit. If limit is greater than either bitmap
401 * size, it is truncated to the smallest.
403 CK_CC_INLINE static unsigned int
404 ck_bitmap_count_intersect(const ck_bitmap_t *x, const ck_bitmap_t *y,
407 unsigned int count, i, slop, words;
409 if (limit > x->n_bits)
412 if (limit > y->n_bits)
415 words = limit / CK_BITMAP_BLOCK;
416 slop = limit % CK_BITMAP_BLOCK;
417 for (i = 0, count = 0; i < words; i++) {
420 xi = ck_pr_load_uint(&x->map[i]);
421 yi = ck_pr_load_uint(&y->map[i]);
422 count += ck_cc_popcount(xi & yi);
426 unsigned int word, xi, yi;
428 xi = ck_pr_load_uint(&x->map[i]);
429 yi = ck_pr_load_uint(&y->map[i]);
431 count += ck_cc_popcount(word & ((1U << slop) - 1));
437 * Initializes a ck_bitmap pointing to a region of memory with
438 * ck_bitmap_size(n_bits) bytes. Third argument determines whether
439 * default bit value is 1 (true) or 0 (false).
441 CK_CC_INLINE static void
442 ck_bitmap_init(struct ck_bitmap *bitmap,
446 unsigned int base = ck_bitmap_base(n_bits);
448 bitmap->n_bits = n_bits;
449 memset(bitmap->map, -(int)set, base);
452 unsigned int b = n_bits % CK_BITMAP_BLOCK;
457 *CK_BITMAP_PTR(bitmap->map, n_bits - 1) &= (1U << b) - 1U;
464 * Initialize iterator for use with provided bitmap.
466 CK_CC_INLINE static void
467 ck_bitmap_iterator_init(struct ck_bitmap_iterator *i,
468 const struct ck_bitmap *bitmap)
472 i->n_limit = CK_BITMAP_BLOCKS(bitmap->n_bits);
473 if (i->n_limit > 0) {
474 i->cache = ck_pr_load_uint(&bitmap->map[0]);
482 * Iterate to next bit.
484 CK_CC_INLINE static bool
485 ck_bitmap_next(const struct ck_bitmap *bitmap,
486 struct ck_bitmap_iterator *i,
489 unsigned int cache = i->cache;
490 unsigned int n_block = i->n_block;
491 unsigned int n_limit = i->n_limit;
494 if (n_block >= n_limit)
497 for (n_block++; n_block < n_limit; n_block++) {
498 cache = ck_pr_load_uint(&bitmap->map[n_block]);
504 i->n_block = n_block;
509 *bit = CK_BITMAP_BLOCK * n_block + ck_cc_ctz(cache);
510 i->cache = cache & (cache - 1);
511 i->n_block = n_block;
515 #endif /* CK_BITMAP_H */