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...

Detailed Description

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.

Macro Definition Documentation

◆ BITVECTOR_CLEAR

#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.

Parameters

vec_	The bitvector to modify.
bit_	The bit index to clear.

◆ BITVECTOR_COPY_FLIP

#define BITVECTOR_COPY_FLIP	(	dest_,
		src_,
		size_,
		flip_
	)

Value:

  MACRO_START \
  unsigned int _i_ = BITVECTOR_SIZE_ELEMENTS(size_) ; \
  HQASSERT(_i_ > 0, "Bitvector has no elements") ;    \
  do {                                                \
    --_i_ ;                                           \
    (dest_)[_i_] = (src_)[_i_] ^ ((bitvector_element_t)!(flip_) - 1u) ;  \
  } while ( _i_ > 0 ) ;                               \
MACRO_END

Copy the contents of one bit vector to another, with an optional exclusive-or operation.

Parameters

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.

◆ BITVECTOR_ELEMENT_BIT_MASK

#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.

Parameters

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.

◆ BITVECTOR_IS_SET

#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.

Parameters

vec_	The bitvector to test.
bit_	The bit index to test.

◆ BITVECTOR_ITERATE_BITS

#define BITVECTOR_ITERATE_BITS	(	iterator_,
		size_
	)

Value:

  (iterator_).bit = (size_) - 1, \
    (iterator_).element = (int)BITVECTOR_SIZE_ELEMENTS(size_) - 1, \
    (iterator_).mask = ((bitvector_element_t)1 << ((iterator_).bit & BITVECTOR_ELEMENT_MASK))

Initialise per-bit iteration over a bit vector using an element, mask pair.

Parameters

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:

bitvector_iterator_t iterator ;
bitvector_t(vector, MAXBITS) ;
 
for ( BITVECTOR_ITERATE_BITS(iterator, bits_used) ;
      BITVECTOR_ITERATE_BITS_MORE(iterator) ;
      BITVECTOR_ITERATE_BITS_NEXT(iterator) ) {
  if ( (vector[iterator.element] & iterator.mask) != 0 ) {
    ...bit iterator.bit is set...
  }
}

See also: BITVECTOR_ITERATE_BITS_MORE, BITVECTOR_ITERATE_BITS_NEXT

◆ BITVECTOR_ITERATE_BITS_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.

Parameters

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.

See also: BITVECTOR_ITERATE_BITS, BITVECTOR_ITERATE_BITS_NEXT

◆ BITVECTOR_ITERATE_BITS_N

#define BITVECTOR_ITERATE_BITS_N	(	iterator_,
		size_,
		chunk_
	)

Value:

  HQASSERT_EXPR(((chunk_) & ((chunk_) - 1)) == 0 && (size_) % (chunk_) == 0, \
    "Iteration chunk or size mismatch", \
    ((iterator_).bit = (size_) - (chunk_), \
     (iterator_).element = (int)BITVECTOR_SIZE_ELEMENTS(size_) - 1, \
     (iterator_).mask = ((bitvector_element_t)((1 << (chunk_)) - 1) << ((iterator_).bit & BITVECTOR_ELEMENT_MASK))))

Initialise multi-bit iteration over a bit vector using an element, mask pair.

Parameters

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:

bitvector_iterator_t iterator ;
bitvector_t(vector, MAXLEN * 2) ;
 
for ( BITVECTOR_ITERATE_BITS_N(iterator, bits_used, 2) ;
      BITVECTOR_ITERATE_BITS_MORE(iterator) ;
      BITVECTOR_ITERATE_BITS_NEXT_N(iterator, 2) ) {
  int chunk = ((vector[iterator.element] & iterator.mask) >> iterator.bit) ;
  ...
}

See also: BITVECTOR_ITERATE_BITS_MORE, BITVECTOR_ITERATE_BITS_NEXT_N

◆ BITVECTOR_ITERATE_BITS_NEXT

#define BITVECTOR_ITERATE_BITS_NEXT ( iterator_ )

Value:

  (iterator_).bit -= 1, \
    (iterator_).element -= (int)((iterator_).mask & 1), \
    (iterator_).mask = ((iterator_).mask >> 1) | ((iterator_).mask << (BITVECTOR_ELEMENT_BITS - 1u))

Continue per-bit iteration over a bit vector using an element, mask pair.

Parameters

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.

See also: BITVECTOR_ITERATE_BITS, BITVECTOR_ITERATE_BITS_MORE

◆ BITVECTOR_ITERATE_BITS_NEXT_N

#define BITVECTOR_ITERATE_BITS_NEXT_N	(	iterator_,
		chunk_
	)

Value:

  HQASSERT_EXPR(((chunk_) & ((chunk_) - 1)) == 0 && (iterator_).bit % (chunk_) == 0, \
    "Iteration chunk or size mismatch", \
    ((iterator_).bit -= (chunk_), \
     (iterator_).element -= (int)((iterator_).mask & 1), \
     (iterator_).mask = (((iterator_).mask >> (chunk_)) | \
                         ((iterator_).mask << (BITVECTOR_ELEMENT_BITS - (chunk_))))))

Continue multi-bit iteration over a bit vector using an element, mask pair.

Parameters

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.

See also: BITVECTOR_ITERATE_BITS_MORE, BITVECTOR_ITERATE_BITS_N

◆ BITVECTOR_ITERATE_ELEMENTS

#define BITVECTOR_ITERATE_ELEMENTS	(	iterator_,
		size_
	)

Value:

  (iterator_).bit = ((size_) - 1), \
    (iterator_).element = (int)BITVECTOR_SIZE_ELEMENTS(size_) - 1, \
    (iterator_).mask = (BITVECTOR_ELEMENT_ONES >> ((BITVECTOR_ELEMENT_BITS - (size_)) & BITVECTOR_ELEMENT_MASK))

Initialise per-element iteration over a bit vector using an element, mask pair.

Parameters

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:

bitvector_iterator_t iterator ;
bitvector_t(vector, MAXBITS) ;
 
for ( BITVECTOR_ITERATE_ELEMENTS(iterator, bits_used) ;
      BITVECTOR_ITERATE_ELEMENTS_MORE(iterator) ;
      BITVECTOR_ITERATE_ELEMENTS_NEXT(iterator) ) {
  if ( (vector[iterator.element] & iterator.mask) == iterator.mask ) {
    ...all bits set...
  } else if ( (vector[iterator.element] & iterator.mask) == 0 ) {
    ...no bits set...
  } ...etc...
}

See also: BITVECTOR_ITERATE_ELEMENTS_MORE, BITVECTOR_ITERATE_ELEMENTS_NEXT

◆ BITVECTOR_ITERATE_ELEMENTS_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.

Parameters

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.

See also: BITVECTOR_ITERATE_ELEMENTS, BITVECTOR_ITERATE_ELEMENTS_NEXT

◆ BITVECTOR_ITERATE_ELEMENTS_NEXT

#define BITVECTOR_ITERATE_ELEMENTS_NEXT ( iterator_ )

Value:

(iterator_).bit = ((iterator_).bit & ~BITVECTOR_ELEMENT_MASK) - 1, \

(iterator_).element -= 1, (iterator_).mask = BITVECTOR_ELEMENT_ONES

Continue per-element iteration over a bit vector using an element, mask pair.

Parameters

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.

See also: BITVECTOR_ITERATE_ELEMENTS, BITVECTOR_ITERATE_ELEMENTS_MORE

◆ BITVECTOR_SET

#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.

Parameters

vec_	The bitvector to modify.
bit_	The bit index to set.

◆ BITVECTOR_SET_ELEMENTS

#define BITVECTOR_SET_ELEMENTS	(	vec_,
		size_,
		value_
	)

Value:

  MACRO_START   \
  unsigned int _i_ = BITVECTOR_SIZE_ELEMENTS(size_) ; \
  HQASSERT(_i_ > 0, "Bitvector has no elements") ;    \
  do {                                                \
    (vec_)[--_i_] = (value_) ;                        \
  } while ( _i_ > 0 ) ;                               \
MACRO_END

Set all of the bits in a bit vector to a value.

Parameters

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.

◆ BITVECTOR_SHIFT_BYTES

#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.

◆ BITVECTOR_SIZE_BYTES

#define BITVECTOR_SIZE_BYTES ( length_ ) (BITVECTOR_SIZE_ELEMENTS(length_) << BITVECTOR_SHIFT_BYTES)

Size of a bitvector containing length_ bits, in bytes.

Parameters

length_ Length of the bitvector, in bits.

◆ BITVECTOR_SIZE_ELEMENTS

#define BITVECTOR_SIZE_ELEMENTS ( length_ ) (((length_) + BITVECTOR_ELEMENT_BITS - 1u) >> BITVECTOR_SHIFT_ELEMENTS)

Size of a bitvector containing length_ bits, in elements.

Parameters

length_ Length of the bitvector, in bits.

◆ bitvector_t

#define bitvector_t	(	name_,
		size_
	)	bitvector_element_t name_[BITVECTOR_SIZE_ELEMENTS(size_)]

Declare a bitvector variable or field.

Parameters

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 Documentation

◆ bitvector_iterator_t

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.

Data Structures

Macros

Typedefs

Detailed Description

Macro Definition Documentation

◆ BITVECTOR_CLEAR

◆ BITVECTOR_COPY_FLIP

◆ BITVECTOR_ELEMENT_BIT_MASK

◆ BITVECTOR_IS_SET

◆ BITVECTOR_ITERATE_BITS

◆ BITVECTOR_ITERATE_BITS_MORE

◆ BITVECTOR_ITERATE_BITS_N

◆ BITVECTOR_ITERATE_BITS_NEXT

◆ BITVECTOR_ITERATE_BITS_NEXT_N

◆ BITVECTOR_ITERATE_ELEMENTS

◆ BITVECTOR_ITERATE_ELEMENTS_MORE

◆ BITVECTOR_ITERATE_ELEMENTS_NEXT

◆ BITVECTOR_SET

◆ BITVECTOR_SET_ELEMENTS

◆ BITVECTOR_SHIFT_BYTES

◆ BITVECTOR_SIZE_BYTES

◆ BITVECTOR_SIZE_ELEMENTS

◆ bitvector_t

Typedef Documentation

◆ bitvector_iterator_t