bitmap.h

Go to the documentation of this file.

#pragma once

#include <limits.h>     // for CHAR_BIT
#include <memory.h>     // for memset()
#include <core/core.h>      // for UNION_CAST()

typedef unsigned char rootsim_bitmap;

/* macros for internal use */

#define B_BLOCK_TYPE unsigned
#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) UNION_CAST(((rootsim_bitmap*)(bitmap)), B_BLOCK_TYPE*)

// we leverage the fact that 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 B_CTZ(x)    (\
        __builtin_choose_expr( \
        __builtin_types_compatible_p (__typeof__ (x), unsigned), __builtin_ctz(x),\
        __builtin_choose_expr(\
        __builtin_types_compatible_p (__typeof__ (x), unsigned long), __builtin_ctzl(x),\
        __builtin_choose_expr(\
        __builtin_types_compatible_p (__typeof__ (x), unsigned long long), __builtin_ctzll(x),\
        (void)0))))

#define B_POPC(x)   (\
        __builtin_choose_expr( \
        __builtin_types_compatible_p (__typeof__ (x), unsigned), __builtin_popcount(x),\
        __builtin_choose_expr(\
        __builtin_types_compatible_p (__typeof__ (x), unsigned long), __builtin_popcountl(x),\
        __builtin_choose_expr(\
        __builtin_types_compatible_p (__typeof__ (x), unsigned long long), __builtin_popcountll(x),\
        (void)0))))

#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_reset(bitmap, bitmap_size) ({              \
        unsigned __i, __blocks = bitmap_size / B_BLOCK_SIZE;        \
        unsigned __ret = bitmap_size * CHAR_BIT;            \
        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_POPC(__cur_block);           \
            }                           \
        }                               \
        __ret;                              \
    })

#define bitmap_first_reset(bitmap, bitmap_size) ({              \
        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) ({            \
        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 = B_CTZ(__cur_block);     \
                    B_RESET_BIT_AT(__cur_block, __fnd); \
                    func((__fnd + __i * B_BITS_PER_BLOCK)); \
                }while(__cur_block);                \
            }                           \
        }                               \
    })