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))
 
// B_BITS_PER_BLOCK is a power of 2 in any real architecture
#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 += SAFE_POPC(__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 = B_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 = SAFE_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;                                                     \
})