1/*
2 * Copyright 2012-2015 Samy Al Bahra.
3 * Copyright 2012-2014 AppNexus, Inc.
4 * Copyright 2014 Paul Khuong.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
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.
15 *
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
26 * SUCH DAMAGE.
27 */
28
29#ifndef CK_BITMAP_H
30#define CK_BITMAP_H
31
32#include <ck_cc.h>
33#include <ck_limits.h>
34#include <ck_pr.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>
41
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) || \
44    !defined(CK_F_CC_CTZ)
45#error "ck_bitmap is not supported on your platform."
46#endif
47
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)
53
54#define CK_BITMAP_INSTANCE(n_entries)					\
55	union {								\
56		struct {						\
57			unsigned int n_bits;				\
58			unsigned int map[CK_BITMAP_BLOCKS(n_entries)];	\
59		} content;						\
60		struct ck_bitmap bitmap;				\
61	}
62
63#define CK_BITMAP_ITERATOR_INIT(a, b) \
64	ck_bitmap_iterator_init((a), &(b)->bitmap)
65
66#define CK_BITMAP_INIT(a, b, c) \
67	ck_bitmap_init(&(a)->bitmap, (b), (c))
68
69#define CK_BITMAP_NEXT(a, b, c) \
70	ck_bitmap_next(&(a)->bitmap, (b), (c))
71
72#define CK_BITMAP_SET(a, b) \
73	ck_bitmap_set(&(a)->bitmap, (b))
74
75#define CK_BITMAP_BTS(a, b) \
76	ck_bitmap_bts(&(a)->bitmap, (b))
77
78#define CK_BITMAP_RESET(a, b) \
79	ck_bitmap_reset(&(a)->bitmap, (b))
80
81#define CK_BITMAP_TEST(a, b) \
82	ck_bitmap_test(&(a)->bitmap, (b))
83
84#define CK_BITMAP_UNION(a, b) \
85	ck_bitmap_union(&(a)->bitmap, &(b)->bitmap)
86
87#define CK_BITMAP_INTERSECTION(a, b) \
88	ck_bitmap_intersection(&(a)->bitmap, &(b)->bitmap)
89
90#define CK_BITMAP_INTERSECTION_NEGATE(a, b) \
91	ck_bitmap_intersection_negate(&(a)->bitmap, &(b)->bitmap)
92
93#define CK_BITMAP_CLEAR(a) \
94	ck_bitmap_clear(&(a)->bitmap)
95
96#define CK_BITMAP_EMPTY(a, b) \
97	ck_bitmap_empty(&(a)->bitmap, b)
98
99#define CK_BITMAP_FULL(a, b) \
100	ck_bitmap_full(&(a)->bitmap, b)
101
102#define CK_BITMAP_COUNT(a, b) \
103	ck_bitmap_count(&(a)->bitmap, b)
104
105#define CK_BITMAP_COUNT_INTERSECT(a, b, c) \
106	ck_bitmap_count_intersect(&(a)->bitmap, b, c)
107
108#define CK_BITMAP_BITS(a) \
109	ck_bitmap_bits(&(a)->bitmap)
110
111#define CK_BITMAP_BUFFER(a) \
112	ck_bitmap_buffer(&(a)->bitmap)
113
114#define CK_BITMAP(a) \
115	(&(a)->bitmap)
116
117struct ck_bitmap {
118	unsigned int n_bits;
119	unsigned int map[];
120};
121typedef struct ck_bitmap ck_bitmap_t;
122
123struct ck_bitmap_iterator {
124	unsigned int cache;
125	unsigned int n_block;
126	unsigned int n_limit;
127};
128typedef struct ck_bitmap_iterator ck_bitmap_iterator_t;
129
130CK_CC_INLINE static unsigned int
131ck_bitmap_base(unsigned int n_bits)
132{
133
134	return CK_BITMAP_BLOCKS(n_bits) * sizeof(unsigned int);
135}
136
137/*
138 * Returns the required number of bytes for a ck_bitmap_t object supporting the
139 * specified number of bits.
140 */
141CK_CC_INLINE static unsigned int
142ck_bitmap_size(unsigned int n_bits)
143{
144
145	return ck_bitmap_base(n_bits) + sizeof(struct ck_bitmap);
146}
147
148/*
149 * Returns total number of bits in specified bitmap.
150 */
151CK_CC_INLINE static unsigned int
152ck_bitmap_bits(const struct ck_bitmap *bitmap)
153{
154
155	return bitmap->n_bits;
156}
157
158/*
159 * Returns a pointer to the bit buffer associated
160 * with the specified bitmap.
161 */
162CK_CC_INLINE static void *
163ck_bitmap_buffer(struct ck_bitmap *bitmap)
164{
165
166	return bitmap->map;
167}
168
169/*
170 * Sets the bit at the offset specified in the second argument.
171 */
172CK_CC_INLINE static void
173ck_bitmap_set(struct ck_bitmap *bitmap, unsigned int n)
174{
175
176	ck_pr_or_uint(CK_BITMAP_PTR(bitmap->map, n), CK_BITMAP_BIT(n));
177	return;
178}
179
180/*
181 * Performs a test-and-set operation at the offset specified in the
182 * second argument.
183 * Returns true if the bit at the specified offset was already set,
184 * false otherwise.
185 */
186CK_CC_INLINE static bool
187ck_bitmap_bts(struct ck_bitmap *bitmap, unsigned int n)
188{
189
190	return ck_pr_bts_uint(CK_BITMAP_PTR(bitmap->map, n),
191	    CK_BITMAP_OFFSET(n));
192}
193
194/*
195 * Resets the bit at the offset specified in the second argument.
196 */
197CK_CC_INLINE static void
198ck_bitmap_reset(struct ck_bitmap *bitmap, unsigned int n)
199{
200
201	ck_pr_and_uint(CK_BITMAP_PTR(bitmap->map, n), ~CK_BITMAP_BIT(n));
202	return;
203}
204
205/*
206 * Determines whether the bit at offset specified in the
207 * second argument is set.
208 */
209CK_CC_INLINE static bool
210ck_bitmap_test(const struct ck_bitmap *bitmap, unsigned int n)
211{
212	unsigned int block;
213
214	block = ck_pr_load_uint(CK_BITMAP_PTR(bitmap->map, n));
215	return block & CK_BITMAP_BIT(n);
216}
217
218/*
219 * Combines bits from second bitmap into the first bitmap. This is not a
220 * linearized operation with respect to the complete bitmap.
221 */
222CK_CC_INLINE static void
223ck_bitmap_union(struct ck_bitmap *dst, const struct ck_bitmap *src)
224{
225	unsigned int n;
226	unsigned int n_buckets = dst->n_bits;
227
228	if (src->n_bits < dst->n_bits)
229		n_buckets = src->n_bits;
230
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]));
235	}
236
237	return;
238}
239
240/*
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.
244 */
245CK_CC_INLINE static void
246ck_bitmap_intersection(struct ck_bitmap *dst, const struct ck_bitmap *src)
247{
248	unsigned int n;
249	unsigned int n_buckets = dst->n_bits;
250	unsigned int n_intersect = n_buckets;
251
252	if (src->n_bits < n_intersect)
253		n_intersect = src->n_bits;
254
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]));
260	}
261
262	for (; n < n_buckets; n++)
263		ck_pr_store_uint(&dst->map[n], 0);
264
265	return;
266}
267
268/*
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.
272 */
273CK_CC_INLINE static void
274ck_bitmap_intersection_negate(struct ck_bitmap *dst,
275    const struct ck_bitmap *src)
276{
277	unsigned int n;
278	unsigned int n_intersect = dst->n_bits;
279
280	if (src->n_bits < n_intersect)
281		n_intersect = src->n_bits;
282
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])));
287	}
288
289	return;
290}
291
292/*
293 * Resets all bits in the provided bitmap. This is not a linearized
294 * operation in ck_bitmap.
295 */
296CK_CC_INLINE static void
297ck_bitmap_clear(struct ck_bitmap *bitmap)
298{
299	unsigned int i;
300	unsigned int n_buckets = ck_bitmap_base(bitmap->n_bits) /
301	    sizeof(unsigned int);
302
303	for (i = 0; i < n_buckets; i++)
304		ck_pr_store_uint(&bitmap->map[i], 0);
305
306	return;
307}
308
309/*
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
312 * size.
313 */
314CK_CC_INLINE static bool
315ck_bitmap_empty(const ck_bitmap_t *bitmap, unsigned int limit)
316{
317	unsigned int i, words, slop;
318
319	if (limit > bitmap->n_bits)
320		limit = bitmap->n_bits;
321
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) {
326			return false;
327		}
328	}
329
330	if (slop > 0) {
331		unsigned int word;
332
333		word = ck_pr_load_uint(&bitmap->map[i]);
334		if ((word & ((1U << slop) - 1)) != 0)
335			return false;
336	}
337
338	return true;
339}
340
341/*
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.
344 */
345CK_CC_UNUSED static bool
346ck_bitmap_full(const ck_bitmap_t *bitmap, unsigned int limit)
347{
348	unsigned int i, slop, words;
349
350	if (limit > bitmap->n_bits) {
351		limit = bitmap->n_bits;
352	}
353
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)
358			return false;
359	}
360
361	if (slop > 0) {
362		unsigned int word;
363
364		word = ~ck_pr_load_uint(&bitmap->map[i]);
365		if ((word & ((1U << slop) - 1)) != 0)
366			return false;
367	}
368	return true;
369}
370
371/*
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
374 * to that size.
375 */
376CK_CC_INLINE static unsigned int
377ck_bitmap_count(const ck_bitmap_t *bitmap, unsigned int limit)
378{
379	unsigned int count, i, slop, words;
380
381	if (limit > bitmap->n_bits)
382		limit = bitmap->n_bits;
383
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]));
388
389	if (slop > 0) {
390		unsigned int word;
391
392		word = ck_pr_load_uint(&bitmap->map[i]);
393		count += ck_cc_popcount(word & ((1U << slop) - 1));
394	}
395	return count;
396}
397
398/*
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.
402 */
403CK_CC_INLINE static unsigned int
404ck_bitmap_count_intersect(const ck_bitmap_t *x, const ck_bitmap_t *y,
405    unsigned int limit)
406{
407	unsigned int count, i, slop, words;
408
409	if (limit > x->n_bits)
410		limit = x->n_bits;
411
412	if (limit > y->n_bits)
413		limit = y->n_bits;
414
415	words = limit / CK_BITMAP_BLOCK;
416	slop = limit % CK_BITMAP_BLOCK;
417	for (i = 0, count = 0; i < words; i++) {
418		unsigned int xi, yi;
419
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);
423	}
424
425	if (slop > 0) {
426		unsigned int word, xi, yi;
427
428		xi = ck_pr_load_uint(&x->map[i]);
429		yi = ck_pr_load_uint(&y->map[i]);
430		word = xi & yi;
431		count += ck_cc_popcount(word & ((1U << slop) - 1));
432	}
433	return count;
434}
435
436/*
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).
440 */
441CK_CC_INLINE static void
442ck_bitmap_init(struct ck_bitmap *bitmap,
443	       unsigned int n_bits,
444	       bool set)
445{
446	unsigned int base = ck_bitmap_base(n_bits);
447
448	bitmap->n_bits = n_bits;
449	memset(bitmap->map, -(int)set, base);
450
451	if (set == true) {
452		unsigned int b = n_bits % CK_BITMAP_BLOCK;
453
454		if (b == 0)
455			return;
456
457		*CK_BITMAP_PTR(bitmap->map, n_bits - 1) &= (1U << b) - 1U;
458	}
459
460	return;
461}
462
463/*
464 * Initialize iterator for use with provided bitmap.
465 */
466CK_CC_INLINE static void
467ck_bitmap_iterator_init(struct ck_bitmap_iterator *i,
468    const struct ck_bitmap *bitmap)
469{
470
471	i->n_block = 0;
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]);
475	} else {
476		i->cache = 0;
477	}
478	return;
479}
480
481/*
482 * Iterate to next bit.
483 */
484CK_CC_INLINE static bool
485ck_bitmap_next(const struct ck_bitmap *bitmap,
486	       struct ck_bitmap_iterator *i,
487	       unsigned int *bit)
488{
489	unsigned int cache = i->cache;
490	unsigned int n_block = i->n_block;
491	unsigned int n_limit = i->n_limit;
492
493	if (cache == 0) {
494		if (n_block >= n_limit)
495			return false;
496
497		for (n_block++; n_block < n_limit; n_block++) {
498			cache = ck_pr_load_uint(&bitmap->map[n_block]);
499			if (cache != 0)
500				goto non_zero;
501		}
502
503		i->cache = 0;
504		i->n_block = n_block;
505		return false;
506	}
507
508non_zero:
509	*bit = CK_BITMAP_BLOCK * n_block + ck_cc_ctz(cache);
510	i->cache = cache & (cache - 1);
511	i->n_block = n_block;
512	return true;
513}
514
515#endif /* CK_BITMAP_H */
516