CBitVec

Overview

Module that defines the CBitVec type and the associated functions.

Types and Definitions

C_BitVecMeta

cMeta const C_BitVecMeta;

Stores the cMeta instance that all CBitVec instances reference.

CBitVec

struct CBitVec;
typedef struct CBitVec CBitVec;

Abstract type that represents a bit vector.

Functions

create

new_bit_vec_c

CBitVec* new_bit_vec_c( int64_t n );

Creates a bit vector with n bits.

copy_bit_vec_c

CBitVec* copy_bit_vec_c( CBitVec const* vec );

Creates a copy of a bit vector.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

int main( void )
{
   init_tap_c_();

   CBitVec* orig = bit_vec_from_cstr_c( "01011010" );
   CBitVec* copy = copy_bit_vec_c( orig );

   expect_c_( orig != copy );
   expect_c_( bit_vec_is_c_( copy, "01011010" ) );

   release_all_c_( orig, copy );

   return finish_tap_c_();
}

bit_vec_from_chars_c

CBitVec* bit_vec_from_chars_c( cChars chars );

Creates a bit vector from a char slice representation. Each \'0' and \'o' will be an unset bit, each \'1' will be set bit and space characters will be ignored.

bit_vec_from_cstr_c

CBitVec* bit_vec_from_cstr_c( char const bitstr[static 1] );

Creates a bit vector from a C string representation. Each \'0' and \'o' will be an unset bit, each \'1' will be set bit and space characters will be ignored.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

int main( void )
{
   init_tap_c_();

   char const* bitStr = "00011011 00110011 10101010";
   char const* lowStr = "ooo11o11 oo11oo11 1o1o1o1o";
   char const* invStr = "11100100 11001100 01010101";

   CBitVec* vec = bit_vec_from_cstr_c( bitStr );
   CBitVec* low = bit_vec_from_cstr_c( lowStr );

   expect_c_( bit_vec_size_c( vec ) == 24 );
   expect_c_( bit_vec_is_c_( vec, bitStr ) );
   expect_c_( bit_vec_is_c_( vec, lowStr ) );
   expect_c_( eq_bit_vec_c( vec, low ) );
   expect_c_( not bit_vec_is_c_( vec, invStr ) );

   release_all_c_( vec, low );

   return finish_tap_c_();
}

resize_bit_vec_c

bool resize_bit_vec_c( CBitVec* vec, int64_t n );

Reduces or expands the number of bits that can be stored inside the CBitVec instance.

prop

bit_vec_size_c

int64_t bit_vec_size_c( CBitVec const* vec );

Returns the number of bits the vector stores.

get_from_bit_vec_c

cByte get_from_bit_vec_c( CBitVec const* vec, int64_t pos );

Returns the bit value at the index pos.

find_index_of_bit_c

int64_t find_index_of_bit_c( CBitVec const* vec, cByte bit, int64_t from );

Returns the next index with a bit value, starting from a known index.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

int main( void )
{
   init_tap_c_();

   CBitVec* vec = bit_vec_from_cstr_c( "00100010" );

   expect_c_( find_index_of_bit_c( vec, 1, 0 ) == 2 );
   expect_c_( find_index_of_bit_c( vec, 0, 3 ) == 3 );
   expect_c_( find_index_of_bit_c( vec, 1, 3 ) == 6 );

   release_c( vec );

   return finish_tap_c_();
}

popcount_bit_vec_c

int64_t popcount_bit_vec_c( CBitVec const* vec, cByte bit );

Counts the number of bits with the specified bit value.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

int main( void )
{
   init_tap_c_();

   {
      CBitVec* vec = bit_vec_from_cstr_c( "00111111" );

      expect_c_( popcount_bit_vec_c( vec, 0 ) == 2 );
      expect_c_( popcount_bit_vec_c( vec, 1 ) == 6 );

      release_c( vec );
   }
   {
      CBitVec* vec = bit_vec_from_cstr_c( "00001111 11000000 1001" );

      expect_c_( popcount_bit_vec_c( vec, 0 ) == 12 );
      expect_c_( popcount_bit_vec_c( vec, 1 ) ==  8 );

      release_c( vec );
   }

   return finish_tap_c_();
}

rfind_index_of_bit_c

int64_t rfind_index_of_bit_c( CBitVec const* vec, cByte bit, int64_t from );

Returns the previous index with a bit value, starting from a known index.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

int main( void )
{
   init_tap_c_();

   CBitVec* vec = bit_vec_from_cstr_c( "00100010" );

   expect_c_( rfind_index_of_bit_c( vec, 1, 7 ) == 6 );
   expect_c_( rfind_index_of_bit_c( vec, 0, 3 ) == 3 );
   expect_c_( rfind_index_of_bit_c( vec, 1, 3 ) == 2 );

   release_c( vec );

   return finish_tap_c_();
}

set

set_on_bit_vec_c

void set_on_bit_vec_c( CBitVec* vec, int64_t pos, cByte bit );

Sets the bit value at the index pos.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

int main( void )
{
   init_tap_c_();

   CBitVec* vec = new_bit_vec_c( 15 );

   expect_c_( bit_vec_is_c_( vec, "0000 0000 0000 000" ) );

   set_on_bit_vec_c( vec, 0, 1 );
   set_on_bit_vec_c( vec, 3, 1 );
   set_on_bit_vec_c( vec, 4, 1 );
   set_on_bit_vec_c( vec, 7, 1 );
   set_on_bit_vec_c( vec, 10, 1 );
   set_on_bit_vec_c( vec, 11, 1 );
   set_on_bit_vec_c( vec, 14, 1 );

   expect_c_( bit_vec_is_c_( vec, "1001 1001 0011 001" ) );

   set_on_bit_vec_c( vec, 19, 1 );

   expect_c_( bit_vec_is_c_( vec, "1001 1001 0011 0010 0001" ) );
   
   release_c( vec );

   return finish_tap_c_();
}

set_range_on_bit_vec_c

void set_range_on_bit_vec_c( CBitVec* vec, cRange range, cByte bit );

Sets the same value on a range in the bit vector.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

int main( void )
{
   init_tap_c_();

   CBitVec* vec = bit_vec_from_cstr_c( "1000 0001 0000 001" );

   set_range_on_bit_vec_c( vec, closed_range_c_( 5, 9 ), 1 );
   expect_c_( bit_vec_is_c_( vec, "1000 0111 1100 001" ) );

   set_range_on_bit_vec_c( vec, closed_range_c_( 6, 8 ), 0 );
   expect_c_( bit_vec_is_c_( vec, "1000 0100 0100 001" ) );

   set_range_on_bit_vec_c( vec, closed_range_c_( 17, 19 ), 1 );
   expect_c_( bit_vec_is_c_( vec, "1000 0100 0100 0010 0111" ) );

   set_range_on_bit_vec_c( vec, closed_range_c_( 18, 25 ), 0 );
   expect_c_( bit_vec_is_c_( vec, "1000 0100 0100 0010 0100" ) );

   release_c( vec );

   return finish_tap_c_();
}

logic

bitand_bit_vec_c

CBitVec* bitand_bit_vec_c( CBitVec const* a, CBitVec const* b );

Combines the bits of a and b with a logical and to a new bit vector. Returns NULL if the allocation fails or a and b have a different number of bits.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

int main( void )
{
   init_tap_c_();

   CBitVec* a = bit_vec_from_cstr_c( "0101" );
   CBitVec* b = bit_vec_from_cstr_c( "0011" );

   CBitVec* res = bitand_bit_vec_c( a, b );
   expect_c_( bit_vec_is_c_( res, "0001" ) );

   release_all_c_( a, b, res );

   return finish_tap_c_();
}

bitand_on_bit_vec_c

bool bitand_on_bit_vec_c( CBitVec* a, CBitVec const* b );

Overwrites a with a logical and of the bits of a and b. Returns false if a and b have a different number of bits.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

int main( void )
{
   init_tap_c_();

   CBitVec* a = bit_vec_from_cstr_c( "0101" );
   CBitVec* b = bit_vec_from_cstr_c( "0011" );

   bitand_on_bit_vec_c( a, b );
   expect_c_( bit_vec_is_c_( a, "0001" ) );

   release_all_c_( a, b );

   return finish_tap_c_();
}

bitor_bit_vec_c

CBitVec* bitor_bit_vec_c( CBitVec const* a, CBitVec const* b );

Combines the bits of a and b with a logical or to a new bit vector. Returns NULL if the allocation fails or a and b have a different number of bits.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

int main( void )
{
   init_tap_c_();

   CBitVec* a = bit_vec_from_cstr_c( "0101" );
   CBitVec* b = bit_vec_from_cstr_c( "0011" );

   CBitVec* res = bitor_bit_vec_c( a, b );
   expect_c_( bit_vec_is_c_( res, "0111" ) );

   release_all_c_( a, b, res );

   return finish_tap_c_();
}

bitor_on_bit_vec_c

bool bitor_on_bit_vec_c( CBitVec* a, CBitVec const* b );

Overwrites a with a logical or of the bits of a and b. Returns false if a and b have a different number of bits.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

int main( void )
{
   init_tap_c_();

   CBitVec* a = bit_vec_from_cstr_c( "0101" );
   CBitVec* b = bit_vec_from_cstr_c( "0011" );

   bitor_on_bit_vec_c( a, b );
   expect_c_( bit_vec_is_c_( a, "0111" ) );

   release_all_c_( a, b );

   return finish_tap_c_();
}

compl_bit_vec_c

CBitVec* compl_bit_vec_c( CBitVec const* vec );

Creates a new vector with the complement of the slice a. Returns NULL if the allocation fails.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

int main( void )
{
   init_tap_c_();

   CBitVec* vec = bit_vec_from_cstr_c( "0101" );

   CBitVec* res = compl_bit_vec_c( vec );
   expect_c_( bit_vec_is_c_( res, "1010" ) );

   release_all_c_( vec, res );

   return finish_tap_c_();
}

compl_on_bit_vec_c

bool compl_on_bit_vec_c( CBitVec* vec );

Builds the complement of the slice a. Returns false if the slices have different s values.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

int main( void )
{
   init_tap_c_();

   CBitVec* vec = bit_vec_from_cstr_c( "0101" );

   compl_on_bit_vec_c( vec );
   expect_c_( bit_vec_is_c_( vec, "1010" ) );

   release_all_c_( vec );

   return finish_tap_c_();
}

xor_bit_vec_c

CBitVec* xor_bit_vec_c( CBitVec const* a, CBitVec const* b );

Overwrites a with a logical exclusive or of the bits of a and b. Returns NULL if the allocation fails or a and b have a different number of bits.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

int main( void )
{
   init_tap_c_();

   CBitVec* a = bit_vec_from_cstr_c( "0101" );
   CBitVec* b = bit_vec_from_cstr_c( "0011" );

   CBitVec* res = xor_bit_vec_c( a, b );
   expect_c_( bit_vec_is_c_( res, "0110" ) );

   release_all_c_( a, b, res );

   return finish_tap_c_();
}

xor_on_bit_vec_c

bool xor_on_bit_vec_c( CBitVec* a, CBitVec* b );

Combines the bits of a and b with a logical exclusive or and overwrites a. Returns false if a and b have a different number of bits.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

int main( void )
{
   init_tap_c_();

   CBitVec* a = bit_vec_from_cstr_c( "0101" );
   CBitVec* b = bit_vec_from_cstr_c( "0011" );

   xor_on_bit_vec_c( a, b );
   expect_c_( bit_vec_is_c_( a, "0110" ) );

   release_all_c_( a, b );

   return finish_tap_c_();
}

shift

shift_bit_vec_c

void shift_bit_vec_c( CBitVec* vec, int64_t distance, cByte fill );

Shifts the bits in a byte slice. A negative offset shifts the bits to the left, a positive offset shifts the bits to the right.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

#define expect_( Vec, BinStr )                                                 \
   expect_c_( bit_vec_is_c_( (Vec), (BinStr) ) )

int main( void )
{
   init_tap_c_();

   { // ------------------------------------------------------------ short shift
      CBitVec* vec = bit_vec_from_cstr_c( "00010111" );
      expect_c_( bit_vec_size_c( vec ) == 8 );

      shift_bit_vec_c( vec, -1, 0 );
      expect_( vec, "00101110" );
  
      shift_bit_vec_c( vec, 1, 1 ); 
      expect_( vec, "10010111" );

      shift_bit_vec_c( vec, -3, 1 );
      expect_( vec, "10111111" );

      shift_bit_vec_c( vec, 3, 0 );
      expect_( vec, "00010111" );

      release_c( vec );
   }
   { // -------------------------------------------------------------- big shift
      CBitVec* vec = bit_vec_from_cstr_c( "00001111 00001111 00001111"
                                          "00001111 00001111 0000" );
      expect_c_( bit_vec_size_c( vec ) == 44 );

      shift_bit_vec_c( vec, -5, 1 );
      expect_( vec, "11100001 11100001 11100001"
                    "11100001 11100001 1111" );

      shift_bit_vec_c( vec, 6, 0 );
      expect_( vec, "00000011 10000111 10000111"
                    "10000111 10000111 1000" );

      shift_bit_vec_c( vec, -13, 1 );
      expect_( vec, "11110000 11110000 11110000"
                    "11110001 11111111 1111" );

      shift_bit_vec_c( vec, 16, 0 );
      expect_( vec, "00000000 00000000 11110000"
                    "11110000 11110000 1111" );

      release_c( vec );
   }

   return finish_tap_c_();
}

cmp

bit_vec_is_c

#define bit_vec_is_c( Vec, Cstr )                                              \
   bit_vec_is_c( (Vec), c_c( Cstr ) )
bool bit_vec_is_c( CBitVec* vec, cChars chars );

Function that checks the bits with the help of a chars value. The check ignores the \\0 of the c string.

cmp_bit_vec_c

int cmp_bit_vec_c( CBitVec const* a, CBitVec const* b );

Compares to bit vectors.

eq_bit_vec_c

bool eq_bit_vec_c( CBitVec const* a, CBitVec const* b );

Util function that wraps cmp_bit_vec_c and returns true if both bit vectors are equal.

io

read_bit_vec_c

#define read_bit_vec_c_( Sca, Vec )                                            \
   read_bit_vec_c( (Sca), (Vec), "" )
bool read_bit_vec_c( cScanner sca[static 1],
                     CBitVec* vec[static 1],
                     char const fmt[static 1] );

write_bit_vec_c

#define write_bit_vec_c_( Rec, Vec )                                           \
   write_bit_vec_c( (Rec), (Vec), "" )
bool write_bit_vec_c( cRecorder rec[static 1],
                      CBitVec const* vec,
                      char const fmt[static 1] );

Writes the bits in a text format into the recorder. The format can be "dbg", "zip" or a format string with the following syntax:

[set][/[line][count][/chunk]]

The fix format "dbg" writes the struct layout of a CBitVec into the recorder.

The fix format "zip" compresses the bit string with the following rules: .zip

single 1 value between 0 values

write a \'+'

single 0 value between 1 values

write a \'_'

more then one 1 value beween 0 values

write the number of 1 followed by a \'i'

more then one 0 value beween 1 values

write the number of 0 followed by a \'z'

The format string has the following options:

The set represents the two characters that should be used to represent 0 and 1. The defualt set is 'o1'.

The optional line value defines how much bits a line should contain, the default value is 80.

Table 1. count

c

appends at the end of the line the number of bits allready written

By default is the flag not set and no counter will be written.

The chunk value defines after how much bits in a line a whitespace character should be added, the default value is 10.

Example
#include "clingo/container/CBitVec.h"
#include "clingo/lang/expect.h"

TEMP_SLICE_C_(
   test,
   {
      CBitVec* vec;
      char const* fmt;
      char const* exp;
   }
)
#define t_( ... ) ((test){__VA_ARGS__})

int main( void )
{
   init_tap_c_();

   CBitVec* vec1 = bit_vec_from_cstr_c( "0000111111"
                                        "0110001111"
                                        "0001" );

   CBitVec* vec2 = bit_vec_from_cstr_c( "0110101010"
                                        "00101" );

   testSlice tests = slice_c_( test,
   // format
      t_( vec1, "","oooo111111 o11ooo1111 ooo1" ),  // "" / "b/80/10"
      t_( vec1, "/c", "oooo111111 o11ooo1111 ooo1 | 24" ),
      t_( vec1, "01/9c/5", "00001 1111 | 9\n"
                           "10110 0011 | 18\n"
                           "11000 1 | 24" ),
      t_( vec1, "/8/0", "oooo1111\n"
                        "11o11ooo\n"
                        "1111ooo1" ),
      t_( vec1, "_I/12c", "____IIIIII _I | 12\n"
                          "I___IIII__ _I | 24" ),
   // list
      t_( vec1, "list", "4-9,11-12,16-19,23" ),
      t_( vec2, "list", "1-2,4,6,8,12,14" ),
   // zip
      t_( vec1, "zip", "4z6i_2i3z4i3z+" ),
      t_( vec2, "zip", "_2i_+_+_+3z+_+" ),
   // dbg
      t_( vec1, "dbg", "{ .numOfBits=24"
                       ", .numOfBytes=3"
                       ", .bitMask=11111111 }" ),
      t_( vec2, "dbg", "{ .numOfBits=15"
                       ", .numOfBytes=2"
                       ", .bitMask=1111111o }" )
   );

   for ( int64_t i = 0; i < tests.s; ++i )
   {
      test t = tests.v[i];
      cRecorder* rec = &recorder_c_( 128 );

      bool res = write_bit_vec_c( rec, t.vec, t.fmt );
      res &= recorded_is_c( rec, t.exp );

      tap_descf_c( res, "test '%s' at %"PRIi64, t.fmt, i );
   }

   release_all_c_( vec1, vec2 );

   return finish_tap_c_();
}