Bitmap data type. More...

#include <core/intrinsics.h>
#include <limits.h>
#include <memory.h>

Include dependency graph for bitmap.h:

This graph shows which files directly or indirectly include this file:

Macros
#define	B_BLOCK_TYPE uint_fast32_t
	The primitive type used to build a bitmap.

#define	B_BLOCK_SIZE ((unsigned)sizeof(B_BLOCK_TYPE))
	The size of the primitive type to build a bitmap.

#define	B_BITS_PER_BLOCK (B_BLOCK_SIZE * CHAR_BIT)
	Number of bits in a primitive type to build a bitmap.

#define	B_MASK ((B_BLOCK_TYPE)1U)
	Mask used to fiddle single bits.

#define	B_UNION_CAST(bitmap) ((B_BLOCK_TYPE *)(bitmap))
	Union cast to access the bitmap.

#define	B_MOD_OF_BPB(n) (((unsigned)(n)) & ((unsigned)(B_BITS_PER_BLOCK - 1)))
	B_BITS_PER_BLOCK is a power of 2 in any real architecture.

#define	B_SET_BIT_AT(B, K) ((B) \|= (B_MASK << (K)))
	Macro to set a bit in a primitive block composing a bitmap.

#define	B_RESET_BIT_AT(B, K) ((B) &= ~(B_MASK << (K)))
	Macro to clear a bit in a primitive block composing a bitmap.

#define	B_CHECK_BIT_AT(B, K) ((B) & (B_MASK << (K)))
	Macro to check if a bit is set in a primitive block composing a bitmap.

#define	B_SET_BIT(A, I) B_SET_BIT_AT((A)[((I) / B_BITS_PER_BLOCK)], (B_MOD_OF_BPB(I)))
	Macro to set a bit in a bitmap.

#define	B_RESET_BIT(A, I) B_RESET_BIT_AT((A)[((I) / B_BITS_PER_BLOCK)], (B_MOD_OF_BPB(I)))
	Macro to clear a bit in a bitmap.

#define	B_CHECK_BIT(A, I) B_CHECK_BIT_AT((A)[((I) / B_BITS_PER_BLOCK)], (B_MOD_OF_BPB(I)))
	Macro to check if a bit is set in a bitmap.

#define	bitmap_required_size(requested_bits) ((((requested_bits) / B_BITS_PER_BLOCK) + (B_MOD_OF_BPB(requested_bits) != 0)) * B_BLOCK_SIZE)
	Computes the required size of a bitmap. More...

#define	bitmap_initialize(memory_pointer, requested_bits) memset(memory_pointer, 0, bitmap_required_size(requested_bits))
	Initializes a bitmap. More...

#define	bitmap_set(bitmap, bit_index) (B_SET_BIT(B_UNION_CAST(bitmap), ((unsigned)(bit_index))))
	Sets a bit in a bitmap. More...

#define	bitmap_reset(bitmap, bit_index) (B_RESET_BIT(B_UNION_CAST(bitmap), ((unsigned)(bit_index))))
	Resets a bit in a bitmap. More...

#define	bitmap_check(bitmap, bit_index) (B_CHECK_BIT(B_UNION_CAST(bitmap), ((unsigned)(bit_index))) != 0)
	Checks a bit in a bitmap. More...

#define	bitmap_count_set(bitmap, bitmap_size)
	Counts the occurrences of set bits in a bitmap. More...

#define	bitmap_count_reset(bitmap, bitmap_size) __extension__({ (bitmap_size) * CHAR_BIT - bitmap_count_set(bitmap, bitmap_size); })
	Counts the occurrences of cleared bits in a bitmap. More...

#define	bitmap_first_reset(bitmap, bitmap_size)
	Computes the index of the first cleared bit in a bitmap. More...

#define	bitmap_foreach_set(bitmap, bitmap_size, func)
	Executes a user supplied function for each set bit in a bitmap. More...

#define	bitmap_merge_or(dest, source, bitmap_size)
	Merges a bitmap into another one by OR-ing all the bits. More...

Typedefs
typedef unsigned char	block_bitmap
	The type of a generic bitmap.

Detailed Description

Bitmap data type.

This a simple bitmap implemented with some simple macros. Keep in mind that some trust is given to the developer since the implementation, for performances and simplicity reasons, doesn't remember its effective size; consequently it doesn't check boundaries on the array that stores the bits.

Copyright: Copyright (C) 2008-2022 HPDCS Group https://hpdcs.github.io

Macro Definition Documentation

◆ bitmap_check

#define bitmap_check	(	bitmap,
		bit_index
	)	(B_CHECK_BIT(B_UNION_CAST(bitmap), ((unsigned)(bit_index))) != 0)

Checks a bit in a bitmap.

Parameters

bitmap	a pointer to the bitmap.
bit_index	the index of the bit to read

Returns: 0 if the bit is not set, 1 otherwise

Avoid side effects in the arguments, they may be evaluated more than once.

◆ bitmap_count_reset

#define bitmap_count_reset	(	bitmap,
		bitmap_size
	)	__extension__({ (bitmap_size) * CHAR_BIT - bitmap_count_set(bitmap, bitmap_size); })

Counts the occurrences of cleared bits in a bitmap.

Parameters

bitmap	a pointer to the bitmap.
bitmap_size	the size of the bitmap in bytes

Returns: the number of cleared bits in the bitmap

This macro expects the number of bits in the bitmap to be a multiple of B_BITS_PER_BLOCK. Avoid side effects in the arguments, they may be evaluated more than once.

◆ bitmap_count_set

#define bitmap_count_set	(	bitmap,
		bitmap_size
	)

Value:

    __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;                                                                                                 \
    })

Counts the occurrences of set bits in a bitmap.

Parameters

bitmap	a pointer to the bitmap.
bitmap_size	the size of the bitmap in bytes

Returns: the number of cleared bits in the bitmap

This macro expects the number of bits in the bitmap to be a multiple of B_BITS_PER_BLOCK. Avoid side effects in the arguments, they may be evaluated more than once.

◆ bitmap_first_reset

#define bitmap_first_reset	(	bitmap,
		bitmap_size
	)

Value:

    __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;                                                                                                 \
    })

Computes the index of the first cleared bit in a bitmap.

Parameters

bitmap	a pointer to the bitmap.
bitmap_size	the size of the bitmap in bytes

Returns: the index of the first cleared bit in the bitmap, UINT_MAX if none is found.

This macro expects the number of bits in the bitmap to be a multiple of B_BITS_PER_BLOCK. Avoid side effects in the arguments, they may be evaluated more than once.

◆ bitmap_foreach_set

#define bitmap_foreach_set	(	bitmap,
		bitmap_size,
		func
	)

Value:

    __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);                                                                  \
            }                                                                                              \
        }                                                                                                      \
    })

Executes a user supplied function for each set bit in a bitmap.

Parameters

bitmap	a pointer to the bitmap.
bitmap_size	the size of the bitmap in bytes
func	a function which takes a single unsigned argument, the index of the current set bit.

This macro expects the number of bits in the bitmap to be a multiple of B_BITS_PER_BLOCK. Avoid side effects in the arguments, they may be evaluated more than once.

◆ bitmap_initialize

#define bitmap_initialize	(	memory_pointer,
		requested_bits
	)	memset(memory_pointer, 0, bitmap_required_size(requested_bits))

Initializes a bitmap.

Parameters

memory_pointer	the pointer to the bitmap to initialize.
requested_bits	the number of bits contained in the bitmap.

Returns: the very same memory_pointer

The argument requested_bits is necessary since the bitmap is "dumb" For example this dynamically declares a 100 entries bitmap and initializes it: block_bitmap *my_bitmap = malloc(bitmap_required_size(100)); bitmap_initialize(my_bitmap, 100); Avoid side effects in the arguments, they may be evaluated more than once.

◆ bitmap_merge_or

#define bitmap_merge_or	(	dest,
		source,
		bitmap_size
	)

Value:

    __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;                                                                                            \
    })

Merges a bitmap into another one by OR-ing all the bits.

Parameters

dest	a pointer to the destination bitmap.
source	a pointer to the source bitmap.
bitmap_size	the size of the bitmap in bytes

Returns: the index of the first cleared bit in the bitmap, UINT_MAX if none is found.

This macro expects the number of bits in the bitmap to be a multiple of B_BITS_PER_BLOCK. Avoid side effects in the arguments, they may be evaluated more than once.

◆ bitmap_required_size

#define bitmap_required_size ( requested_bits ) ((((requested_bits) / B_BITS_PER_BLOCK) + (B_MOD_OF_BPB(requested_bits) != 0)) * B_BLOCK_SIZE)

Computes the required size of a bitmap.

Parameters

requested_bits the requested number of bits.

Returns: the size in bytes of the requested bitmap.

For example this statically declares a 100 entries bitmap and initializes it: block_bitmap my_bitmap[bitmap_required_size(100)] = {0}; Avoid side effects in the arguments, they may be evaluated more than once.

◆ bitmap_reset

#define bitmap_reset	(	bitmap,
		bit_index
	)	(B_RESET_BIT(B_UNION_CAST(bitmap), ((unsigned)(bit_index))))

Resets a bit in a bitmap.

Parameters

bitmap	a pointer to the bitmap to write.
bit_index	the index of the bit to reset.

Avoid side effects in the arguments, they may be evaluated more than once.

◆ bitmap_set

#define bitmap_set	(	bitmap,
		bit_index
	)	(B_SET_BIT(B_UNION_CAST(bitmap), ((unsigned)(bit_index))))

Sets a bit in a bitmap.

Parameters

bitmap	a pointer to the bitmap to write.
bit_index	the index of the bit to set.

Avoid side effects in the arguments, they may be evaluated more than once.

Macros

Typedefs

Detailed Description

Macro Definition Documentation

◆ bitmap_check

◆ bitmap_count_reset

◆ bitmap_count_set

◆ bitmap_first_reset

◆ bitmap_foreach_set

◆ bitmap_initialize

◆ bitmap_merge_or

◆ bitmap_required_size

◆ bitmap_reset

◆ bitmap_set