sys/contrib/ck/include/ck_bitmap.h

   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
 117 struct ck_bitmap {
 118         unsigned int n_bits;
 119         unsigned int map[];
 120 };
 121 typedef struct ck_bitmap ck_bitmap_t;
 122
 123 struct ck_bitmap_iterator {
 124         unsigned int cache;
 125         unsigned int n_block;
 126         unsigned int n_limit;
 127 };
 128 typedef struct ck_bitmap_iterator ck_bitmap_iterator_t;
 129
 130 CK_CC_INLINE static unsigned int
 131 ck_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  */
 141 CK_CC_INLINE static unsigned int
 142 ck_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  */
 151 CK_CC_INLINE static unsigned int
 152 ck_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  */
 162 CK_CC_INLINE static void *
 163 ck_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  */
 172 CK_CC_INLINE static void
 173 ck_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  */
 186 CK_CC_INLINE static bool
 187 ck_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  */
 197 CK_CC_INLINE static void
 198 ck_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  */
 209 CK_CC_INLINE static bool
 210 ck_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  */
 222 CK_CC_INLINE static void
 223 ck_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  */
 245 CK_CC_INLINE static void
 246 ck_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  */
 273 CK_CC_INLINE static void
 274 ck_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  */
 296 CK_CC_INLINE static void
 297 ck_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  */
 314 CK_CC_INLINE static bool
 315 ck_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  */
 345 CK_CC_UNUSED static bool
 346 ck_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  */
 376 CK_CC_INLINE static unsigned int
 377 ck_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  */
 403 CK_CC_INLINE static unsigned int
 404 ck_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  */
 441 CK_CC_INLINE static void
 442 ck_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  */
 466 CK_CC_INLINE static void
 467 ck_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  */
 484 CK_CC_INLINE static bool
 485 ck_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
 508 non_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 */