bitmap.h

Go to the documentation of this file.

 
#pragma once
 
#include <core/intrinsics.h>
 
#include <limits.h> // for CHAR_BIT
#include <memory.h> // for memset()
 
typedef unsigned char block_bitmap;
 
/* macros for internal use */
 
#define B_BLOCK_TYPE uint_fast32_t
#define B_BLOCK_SIZE ((unsigned)sizeof(B_BLOCK_TYPE))
#define B_BITS_PER_BLOCK (B_BLOCK_SIZE * CHAR_BIT)
#define B_MASK ((B_BLOCK_TYPE)1U)
#define B_UNION_CAST(bitmap) ((B_BLOCK_TYPE *)(bitmap))
 
#define B_MOD_OF_BPB(n) (((unsigned)(n)) & ((unsigned)(B_BITS_PER_BLOCK - 1)))
 
#define B_SET_BIT_AT(B, K) ((B) |= (B_MASK << (K)))
#define B_RESET_BIT_AT(B, K) ((B) &= ~(B_MASK << (K)))
#define B_CHECK_BIT_AT(B, K) ((B) & (B_MASK << (K)))
 
#define B_SET_BIT(A, I) B_SET_BIT_AT((A)[((I) / B_BITS_PER_BLOCK)], (B_MOD_OF_BPB(I)))
#define B_RESET_BIT(A, I) B_RESET_BIT_AT((A)[((I) / B_BITS_PER_BLOCK)], (B_MOD_OF_BPB(I)))
#define B_CHECK_BIT(A, I) B_CHECK_BIT_AT((A)[((I) / B_BITS_PER_BLOCK)], (B_MOD_OF_BPB(I)))
 
#define bitmap_required_size(requested_bits)                                                                           \
    ((((requested_bits) / B_BITS_PER_BLOCK) + (B_MOD_OF_BPB(requested_bits) != 0)) * B_BLOCK_SIZE)
 
#define bitmap_initialize(memory_pointer, requested_bits)                                                              \
    memset(memory_pointer, 0, bitmap_required_size(requested_bits))
 
#define bitmap_set(bitmap, bit_index) (B_SET_BIT(B_UNION_CAST(bitmap), ((unsigned)(bit_index))))
 
#define bitmap_reset(bitmap, bit_index) (B_RESET_BIT(B_UNION_CAST(bitmap), ((unsigned)(bit_index))))
 
#define bitmap_check(bitmap, bit_index) (B_CHECK_BIT(B_UNION_CAST(bitmap), ((unsigned)(bit_index))) != 0)
 
#define bitmap_count_set(bitmap, bitmap_size)                                                                          \
    __extension__({                                                                                                \
        unsigned __i = (bitmap_size) / B_BLOCK_SIZE;                                                           \
        unsigned __ret = 0;                                                                                    \
        B_BLOCK_TYPE *__block_b = B_UNION_CAST(bitmap);                                                        \
        while(__i--) {                                                                                         \
            __ret += intrinsics_popcount(__block_b[__i]);                                                  \
        }                                                                                                      \
        __ret;                                                                                                 \
    })
 
#define bitmap_count_reset(bitmap, bitmap_size)                                                                        \
    __extension__({ (bitmap_size) * CHAR_BIT - bitmap_count_set(bitmap, bitmap_size); })
 
#define bitmap_first_reset(bitmap, bitmap_size)                                                                        \
    __extension__({                                                                                                \
        unsigned __i, __blocks = (bitmap_size) / B_BLOCK_SIZE;                                                 \
        unsigned __ret = UINT_MAX;                                                                             \
        B_BLOCK_TYPE __cur_block, *__block_b = B_UNION_CAST(bitmap);                                           \
        for(__i = 0; __i < __blocks; ++__i) {                                                                  \
            if((__cur_block = ~__block_b[__i])) {                                                          \
                __ret = intrinsics_ctz(__cur_block);                                                   \
                break;                                                                                 \
            }                                                                                              \
        }                                                                                                      \
        __ret;                                                                                                 \
    })
 
#define bitmap_foreach_set(bitmap, bitmap_size, func)                                                                  \
    __extension__({                                                                                                \
        unsigned __i, __fnd, __blocks = (bitmap_size) / B_BLOCK_SIZE;                                          \
        B_BLOCK_TYPE __cur_block, *__block_b = B_UNION_CAST(bitmap);                                           \
        for(__i = 0; __i < __blocks; ++__i) {                                                                  \
            if((__cur_block = __block_b[__i])) {                                                           \
                do {                                                                                   \
                    __fnd = intrinsics_ctz(__cur_block);                                           \
                    B_RESET_BIT_AT(__cur_block, __fnd);                                            \
                    func((__fnd + __i * B_BITS_PER_BLOCK));                                        \
                } while(__cur_block);                                                                  \
            }                                                                                              \
        }                                                                                                      \
    })
 
#define bitmap_merge_or(dest, source, bitmap_size)                                                                     \
    __extension__({                                                                                                \
        unsigned __i = (bitmap_size) / B_BLOCK_SIZE;                                                           \
        B_BLOCK_TYPE *__s_blocks = B_UNION_CAST(source);                                                       \
        B_BLOCK_TYPE *__d_blocks = B_UNION_CAST(dest);                                                         \
        while(__i--) {                                                                                         \
            __d_blocks[__i] |= __s_blocks[__i];                                                            \
        }                                                                                                      \
        __d_blocks;                                                                                            \
    })