Macros implementing bit vectors. More...
Data Structures | |
struct | bitvector_iterator_t |
Iterator structure for walking bit vectors. More... | |
Macros | |
#define | BITVECTOR_SHIFT_BYTES 3 |
Right shift to convert bytes indices to element indices. More... | |
#define | BITVECTOR_SHIFT_ELEMENTS (BITVECTOR_SHIFT_BYTES + 3) |
Right shift to convert bit indices to element indices. | |
#define | BITVECTOR_ELEMENT_BITS (1u << BITVECTOR_SHIFT_ELEMENTS) |
Bit vector element size in bits. | |
#define | BITVECTOR_ELEMENT_MASK (BITVECTOR_ELEMENT_BITS - 1u) |
Mask to extract bit index within element from bit index. | |
#define | BITVECTOR_ELEMENT_ZEROS (bitvector_element_t)0 |
Bitvector element containing all zeros. | |
#define | BITVECTOR_ELEMENT_ONES (bitvector_element_t)(~BITVECTOR_ELEMENT_ZEROS) |
Bitvector element containing all ones. | |
#define | BITVECTOR_SIZE_ELEMENTS(length_) (((length_) + BITVECTOR_ELEMENT_BITS - 1u) >> BITVECTOR_SHIFT_ELEMENTS) |
Size of a bitvector containing length_ bits, in elements. More... | |
#define | BITVECTOR_SIZE_BYTES(length_) (BITVECTOR_SIZE_ELEMENTS(length_) << BITVECTOR_SHIFT_BYTES) |
Size of a bitvector containing length_ bits, in bytes. More... | |
#define | bitvector_t(name_, size_) bitvector_element_t name_[BITVECTOR_SIZE_ELEMENTS(size_)] |
Declare a bitvector variable or field. More... | |
#define | BITVECTOR_SET_ELEMENTS(vec_, size_, value_) |
Set all of the bits in a bit vector to a value. More... | |
#define | BITVECTOR_COPY_FLIP(dest_, src_, size_, flip_) |
Copy the contents of one bit vector to another, with an optional exclusive-or operation. More... | |
#define | BITVECTOR_CLEAR(vec_, bit_) (vec_)[(bit_) >> BITVECTOR_SHIFT_ELEMENTS] &= ~((bitvector_element_t)1 << (BITVECTOR_ELEMENT_MASK & (bit_))) |
Clear a single bit in a bit vector. More... | |
#define | BITVECTOR_SET(vec_, bit_) (vec_)[(bit_) >> BITVECTOR_SHIFT_ELEMENTS] |= ((bitvector_element_t)1 << (BITVECTOR_ELEMENT_MASK & (bit_))) |
Set a single bit in a bit vector. More... | |
#define | BITVECTOR_IS_SET(vec_, bit_) ((vec_)[(bit_) >> BITVECTOR_SHIFT_ELEMENTS] & ((bitvector_element_t)1 << (BITVECTOR_ELEMENT_MASK & (bit_)))) |
Test if a bit in a bit vector is set. More... | |
#define | BITVECTOR_ELEMENT_BIT_MASK(element_, bit_) (((element_) == ((bit_) >> BITVECTOR_SHIFT_ELEMENTS)) << ((bit_) & BITVECTOR_ELEMENT_MASK)) |
Return a mask which can be used to test and isolate a bit in an identified element. More... | |
#define | BITVECTOR_ITERATE_BITS(iterator_, size_) |
Initialise per-bit iteration over a bit vector using an element, mask pair. More... | |
#define | BITVECTOR_ITERATE_BITS_MORE(iterator_) ((iterator_).element >= 0) |
Test if per-bit iteration over a bitvector using an element, mask pair is complete. More... | |
#define | BITVECTOR_ITERATE_BITS_NEXT(iterator_) |
Continue per-bit iteration over a bit vector using an element, mask pair. More... | |
#define | BITVECTOR_ITERATE_BITS_N(iterator_, size_, chunk_) |
Initialise multi-bit iteration over a bit vector using an element, mask pair. More... | |
#define | BITVECTOR_ITERATE_BITS_NEXT_N(iterator_, chunk_) |
Continue multi-bit iteration over a bit vector using an element, mask pair. More... | |
#define | BITVECTOR_ITERATE_ELEMENTS(iterator_, size_) |
Initialise per-element iteration over a bit vector using an element, mask pair. More... | |
#define | BITVECTOR_ITERATE_ELEMENTS_MORE(iterator_) ((iterator_).element >= 0) |
Test if per-element iteration over a bitvector using an element, mask pair is complete. More... | |
#define | BITVECTOR_ITERATE_ELEMENTS_NEXT(iterator_) |
Continue per-element iteration over a bit vector using an element, mask pair. More... | |
Typedefs | |
typedef uint64 | bitvector_element_t |
An unsigned type used to implement bit vectors. | |
typedef struct bitvector_iterator_t | bitvector_iterator_t |
Iterator structure for walking bit vectors. More... | |
Macros implementing bit vectors.
Bit vectors are stored in units of a fundamental type, bitvector_element_t. They may be iterated, indexed and manipulated in terms of bits or the element type.
A stack or static bitvector may be declared using the bitvector_t() macro.
Individual bits in a bitvector may be cleared, set, or tested using BITVECTOR_CLEAR(), BITVECTOR_SET(), and BITVECTOR_IS_SET(). The entire bitvector may be set using BITVECTOR_SET_ELEMENTS(), or copied and transformed using BITVECTOR_COPY_FLIP().
Several ways of iterating bit vectors are provided, all using the bitvector_iterator_t type.
BITVECTOR_ITERATE_BITS(), BITVECTOR_ITERATE_BITS_MORE(), and BITVECTOR_ITERATE_BITS_NEXT() iterate one bit at a time.
BITVECTOR_ITERATE_BITS_N(), BITVECTOR_ITERATE_BITS_MORE(), and BITVECTOR_ITERATE_BITS_NEXT_N() iterate multiple bits at a time.
BITVECTOR_ITERATE_ELEMENTS(), BITVECTOR_ITERATE_ELEMENTS_MORE(), and BITVECTOR_ITERATE_ELEMENTS_NEXT() iterate by bitvector_element_t units.
Copyright (C) 2023 Global Graphics Software Ltd. All rights reserved. This source code contains the confidential and trade secret information of Global Graphics Software Ltd. It may not be used, copied or distributed for any reason except as set forth in the applicable Global Graphics license agreement.
#define BITVECTOR_CLEAR | ( | vec_, | |
bit_ | |||
) | (vec_)[(bit_) >> BITVECTOR_SHIFT_ELEMENTS] &= ~((bitvector_element_t)1 << (BITVECTOR_ELEMENT_MASK & (bit_))) |
Clear a single bit in a bit vector.
vec_ | The bitvector to modify. |
bit_ | The bit index to clear. |
#define BITVECTOR_COPY_FLIP | ( | dest_, | |
src_, | |||
size_, | |||
flip_ | |||
) |
Copy the contents of one bit vector to another, with an optional exclusive-or operation.
dest_ | The destination bitvector. |
src_ | The source bitvector. |
size_ | The number of bits in the vector. |
flip_ | A boolean, indicating if the destination should be the inverse of the source. |
#define BITVECTOR_ELEMENT_BIT_MASK | ( | element_, | |
bit_ | |||
) | (((element_) == ((bit_) >> BITVECTOR_SHIFT_ELEMENTS)) << ((bit_) & BITVECTOR_ELEMENT_MASK)) |
Return a mask which can be used to test and isolate a bit in an identified element.
element_ | The element index being processed. |
bit_ | The bit index to derive a mask for. |
The return value is a mask that is zero if bit_ is not in element_, or set to the bit mask within element_ if it is.
This can be used to implement bulk operations in clients, without having to test if particular bits that should be treated specially are present in each element.
#define BITVECTOR_IS_SET | ( | vec_, | |
bit_ | |||
) | ((vec_)[(bit_) >> BITVECTOR_SHIFT_ELEMENTS] & ((bitvector_element_t)1 << (BITVECTOR_ELEMENT_MASK & (bit_)))) |
Test if a bit in a bit vector is set.
vec_ | The bitvector to test. |
bit_ | The bit index to test. |
#define BITVECTOR_ITERATE_BITS | ( | iterator_, | |
size_ | |||
) |
Initialise per-bit iteration over a bit vector using an element, mask pair.
iterator_ | A bitvector_iterator_t variable to initialise. |
size_ | The size of the bit vector. |
This macro is written such that it can be used in a for-loop initialisation statement. Note that the iteration goes from the highest to lowest bits. The iterator will be initialised correctly for bitvectors of size zero or more. The idiom will usually look like this:
#define BITVECTOR_ITERATE_BITS_MORE | ( | iterator_ | ) | ((iterator_).element >= 0) |
Test if per-bit iteration over a bitvector using an element, mask pair is complete.
iterator_ | The bitvector_iterator_t variable to test. |
This macro is written such that it can be used in a for-loop condition statement. Note that the iteration goes from the highest to lowest bits.
#define BITVECTOR_ITERATE_BITS_N | ( | iterator_, | |
size_, | |||
chunk_ | |||
) |
Initialise multi-bit iteration over a bit vector using an element, mask pair.
iterator_ | A bitvector_iterator_t variable to initialise. |
size_ | The size of the bit vector. |
chunk_ | The number of bits to iterate at a time. This should be a power of 2. |
This macro is written such that it can be used in a for-loop initialisation statement. Note that the iteration goes from the highest to lowest bits. The iterator will be initialised correctly for bitvectors of size zero or more. The idiom will usually look like this:
#define BITVECTOR_ITERATE_BITS_NEXT | ( | iterator_ | ) |
Continue per-bit iteration over a bit vector using an element, mask pair.
iterator_ | The bitvector_iterator_t variable to step. |
This macro is written such that it can be used in a for-loop continuation statement. Note that the iteration goes from the highest to lowest bits.
#define BITVECTOR_ITERATE_BITS_NEXT_N | ( | iterator_, | |
chunk_ | |||
) |
Continue multi-bit iteration over a bit vector using an element, mask pair.
iterator_ | The bitvector_iterator_t variable to step. |
chunk_ | The number of bits to iterate at a time. This should be a power of 2. |
This macro is written such that it can be used in a for-loop continuation statement. Note that the iteration goes from the highest to lowest bits.
#define BITVECTOR_ITERATE_ELEMENTS | ( | iterator_, | |
size_ | |||
) |
Initialise per-element iteration over a bit vector using an element, mask pair.
iterator_ | The bitvector_iterator_t variable to initialise. |
size_ | The size of the bit vector. |
This macro is written such that it can be used in a for-loop initialisation statement. Note that the iteration goes from the highest to lowest element. The iterator will be initialised correctly for bitvectors of size zero or more. The iteration idiom will usually look like this:
#define BITVECTOR_ITERATE_ELEMENTS_MORE | ( | iterator_ | ) | ((iterator_).element >= 0) |
Test if per-element iteration over a bitvector using an element, mask pair is complete.
iterator_ | The bitvector_iterator_t variable to test. |
The bits index to test. This macro is written such that it can be used in a for-loop condition statement. Note that the iteration goes from the highest to lowest element.
#define BITVECTOR_ITERATE_ELEMENTS_NEXT | ( | iterator_ | ) |
Continue per-element iteration over a bit vector using an element, mask pair.
iterator_ | The bitvector_iterator_t variable to step. |
This macro is written such that it can be used in a for-loop continuation statement. Note that the iteration goes from the highest to lowest element.
#define BITVECTOR_SET | ( | vec_, | |
bit_ | |||
) | (vec_)[(bit_) >> BITVECTOR_SHIFT_ELEMENTS] |= ((bitvector_element_t)1 << (BITVECTOR_ELEMENT_MASK & (bit_))) |
Set a single bit in a bit vector.
vec_ | The bitvector to modify. |
bit_ | The bit index to set. |
#define BITVECTOR_SET_ELEMENTS | ( | vec_, | |
size_, | |||
value_ | |||
) |
Set all of the bits in a bit vector to a value.
vec_ | The bitvector to clear. |
size_ | The number of bits in the vector. |
value_ | This should be BITVECTOR_ELEMENT_ZEROS to clear the vector, BITVECTOR_ELEMENT_ONES to set the vector. |
#define BITVECTOR_SHIFT_BYTES 3 |
Right shift to convert bytes indices to element indices.
The relationship:
(1 << BITVECTOR_SHIFT_BYTES) == sizeof(bitvector_element_t)
should always hold.
#define BITVECTOR_SIZE_BYTES | ( | length_ | ) | (BITVECTOR_SIZE_ELEMENTS(length_) << BITVECTOR_SHIFT_BYTES) |
Size of a bitvector containing length_ bits, in bytes.
length_ | Length of the bitvector, in bits. |
#define BITVECTOR_SIZE_ELEMENTS | ( | length_ | ) | (((length_) + BITVECTOR_ELEMENT_BITS - 1u) >> BITVECTOR_SHIFT_ELEMENTS) |
Size of a bitvector containing length_ bits, in elements.
length_ | Length of the bitvector, in bits. |
#define bitvector_t | ( | name_, | |
size_ | |||
) | bitvector_element_t name_[BITVECTOR_SIZE_ELEMENTS(size_)] |
Declare a bitvector variable or field.
name_ | The name of the bitvector name or field. |
size_ | A constant expression, giving the number of bits in the vector. |
This macro can be used anywhere that a variable or parameter declaration can occur.
typedef struct bitvector_iterator_t bitvector_iterator_t |
Iterator structure for walking bit vectors.
This structure is transparent; the element index and the mask can be used by the client to extract and manipulate words from the bitvector directly.