TaPAS  0.2
Typedefs | Functions
ccl-bittable.h File Reference

Implementation of vectors of bits. More...

#include <ccl/ccl-common.h>
#include <ccl/ccl-log.h>
#include <ccl/ccl-iterator.h>

Go to the source code of this file.

Typedefs

typedef struct ccl_bittable_st ccl_bittable
 Abstract type of a vector of bytes.
 

Functions

ccl_bittableccl_bittable_create (int size)
 Creates a new table of bits large enough for size bits. More...
 
void ccl_bittable_delete (ccl_bittable *bt)
 Releases resources allocated to bt. More...
 
int ccl_bittable_get_size (const ccl_bittable *bt)
 Returns the number of bits of the table. More...
 
int ccl_bittable_has (const ccl_bittable *bt, int index)
 Checks if the bit at position index is set or not. More...
 
void ccl_bittable_set (ccl_bittable *bt, int index)
 Set the bit at position index. More...
 
void ccl_bittable_unset (ccl_bittable *bt, int index)
 Unset the bit at position index. More...
 
int ccl_bittable_get_first (ccl_bittable *bt)
 Returns the index of the first non-null bit. More...
 
int ccl_bittable_get_next (ccl_bittable *bt, int prev)
 Returns the index of the first non-null bit encountered after the position prev. More...
 
void ccl_bittable_clear (ccl_bittable *bt)
 Sets to zero all bits of bt. More...
 
unsigned int ccl_bittable_hash (const ccl_bittable *bt)
 Computes an hashed value of the content of bt. More...
 
int ccl_bittable_equals (const ccl_bittable *bt1, const ccl_bittable *bt2)
 Checks if bt1 and bt2 are equal. More...
 
ccl_bittableccl_bittable_dup (const ccl_bittable *bt)
 Duplicates the table bt. More...
 
int ccl_bittable_get_nb_one (ccl_bittable *bt)
 Returns the number of bits set to 1 in bt/. More...
 
ccl_int_iterator * ccl_bittable_get_ones (ccl_bittable *bt)
 Returns an iterator that gives positions of bit equal to 1. More...
 
ccl_bittableccl_bittable_resize (ccl_bittable *bt, int newsize)
 Resize the table of bits bt for newsize bits. More...
 
ccl_bittableccl_bittable_union (const ccl_bittable *bt1, const ccl_bittable *bt2)
 Computes the bitwise disjunction of tables bt1 and bt2. More...
 
ccl_bittableccl_bittable_nary_union (ccl_bittable **bts, int nb_bts)
 Computes the bitwise disjunction of tables bt[0], ..., bt[nb_bts-1]. More...
 
ccl_bittableccl_bittable_intersection (const ccl_bittable *bt1, const ccl_bittable *bt2)
 Computes the bitwise conjunction of tables bt1 and bt2. More...
 
ccl_bittableccl_bittable_sub (const ccl_bittable *bt1, const ccl_bittable *bt2)
 Computes the bitwise difference of tables bt1 and bt2. More...
 
ccl_bittableccl_bittable_complement (const ccl_bittable *bt)
 Negate the bits of bt. More...
 
void ccl_bittable_window_union (ccl_bittable *bt_dst, int dst, const ccl_bittable *bt_src, int src, int w)
 Makes a bitwise disjunction between bts_dst and bt_src but on a restricted part of indices. More...
 
int ccl_bittable_window_union_with_roll (ccl_bittable *bt_dst, int dst, const ccl_bittable *bt_src, int src, int w)
 Does the same work than ccl_bittable_window_union but the window of bt_src is rolled for 1 bit on the right (i.e. circular shift on the right) prior the disjunction. More...
 
int ccl_bittable_is_included_in (const ccl_bittable *bt1, const ccl_bittable *bt2)
 Checks if the set represented by bt1 is included in bt2. More...
 
void ccl_bittable_log (ccl_log_type log, const ccl_bittable *bt)
 Display the content of the table bt to the stream log. More...
 

Detailed Description

Implementation of vectors of bits.

Definition in file ccl-bittable.h.

Function Documentation

void ccl_bittable_clear ( ccl_bittable bt)

Sets to zero all bits of bt.

Parameters
btthe table of bits
Precondition
bt != NULL
ccl_bittable* ccl_bittable_complement ( const ccl_bittable bt)

Negate the bits of bt.

Parameters
btthe table to complement
Precondition
bt != NULL
Returns
the complement of bt
ccl_bittable* ccl_bittable_create ( int  size)

Creates a new table of bits large enough for size bits.

Parameters
sizethe minimal number of bits of the table
Precondition
size >= 0
Returns
a new table of bits large enough for size bits
void ccl_bittable_delete ( ccl_bittable bt)

Releases resources allocated to bt.

Parameters
btthe table of bits
Precondition
bt != NULL
ccl_bittable* ccl_bittable_dup ( const ccl_bittable bt)

Duplicates the table bt.

Parameters
btthe table of bits
Precondition
bt != NULL
Returns
a copy of bt
int ccl_bittable_equals ( const ccl_bittable bt1,
const ccl_bittable bt2 
)

Checks if bt1 and bt2 are equal.

To be equal the two tables must be defined on the same number of bits.

Parameters
bt1the first table
bt2the second table
Precondition
bt1 != NULL
bt2 != NULL
Returns
a non-null value if bt1 and bt2 are equal.
int ccl_bittable_get_first ( ccl_bittable bt)

Returns the index of the first non-null bit.

Parameters
btthe table of bits
Precondition
bt != NULL
Returns
the index of the first bit different of 0 or a negative value all bits are null.
int ccl_bittable_get_nb_one ( ccl_bittable bt)

Returns the number of bits set to 1 in bt/.

Parameters
btthe table of bits
Precondition
bt != NULL
Returns
the number of bits set to 1 in bt/
int ccl_bittable_get_next ( ccl_bittable bt,
int  prev 
)

Returns the index of the first non-null bit encountered after the position prev.

Parameters
btthe table of bits
preva postion in the table
Precondition
0 <= prev && prec < ccl_bittable_get_size (bt)
Returns
the index of the first non-null bit encountered after the position prev.
ccl_int_iterator* ccl_bittable_get_ones ( ccl_bittable bt)

Returns an iterator that gives positions of bit equal to 1.

The behavior of the iterator is undefined if the table is modified between two iterations.

Parameters
btthe table of bits
Precondition
bt != NULL
Returns
on iterator over bits equal to 1
int ccl_bittable_get_size ( const ccl_bittable bt)

Returns the number of bits of the table.

Parameters
btthe table of bits
Precondition
bt != NULL
int ccl_bittable_has ( const ccl_bittable bt,
int  index 
)

Checks if the bit at position index is set or not.

Parameters
btthe table of bits
indexthe index of the bit
Precondition
bt != NULL
index >= 0
Returns
a non-null value if the bit is set.
unsigned int ccl_bittable_hash ( const ccl_bittable bt)

Computes an hashed value of the content of bt.

Parameters
btthe table of bits
Precondition
bt != NULL
Returns
an hashed value of the content of bt
ccl_bittable* ccl_bittable_intersection ( const ccl_bittable bt1,
const ccl_bittable bt2 
)

Computes the bitwise conjunction of tables bt1 and bt2.

Parameters
bt1the first table
bt2the second table
Precondition
ccl_bittable_get_size (bt1) == ccl_bittable_get_size (bt2)
Returns
the intersection of sets of integers represented by bt1 and bt2
int ccl_bittable_is_included_in ( const ccl_bittable bt1,
const ccl_bittable bt2 
)

Checks if the set represented by bt1 is included in bt2.

Parameters
bt1the first table of bits
bt2the second table of bits
Precondition
ccl_bittable_get_size (bt1) == ccl_bittable_get_size (bt2)
Returns
a non-null value if all bits set to 1 in bt1 are also set to 1 in bt2
void ccl_bittable_log ( ccl_log_type  log,
const ccl_bittable bt 
)

Display the content of the table bt to the stream log.

Parameters
logthe stream
btthe table of bits
Precondition
bt != NULL
ccl_bittable* ccl_bittable_nary_union ( ccl_bittable **  bts,
int  nb_bts 
)

Computes the bitwise disjunction of tables bt[0], ..., bt[nb_bts-1].

Parameters
btsan array of bit tables
nb_btsnumber of tables to consider
Precondition
ccl_bittable_get_size (bt[0]) == ccl_bittable_get_size (bt[i]) for all i from 1 to nb_bts-1
Returns
the union of sets of integers represented by bt1 and bt2
ccl_bittable* ccl_bittable_resize ( ccl_bittable bt,
int  newsize 
)

Resize the table of bits bt for newsize bits.

The function creates a new table for newsize bits. The content of bt is copied into the new table between positions 0 and newsize-1.

Parameters
btthe table of bits
newsizethe new number of bits
Precondition
bt != NULL
Returns
a new table with newsize bits; common bits with bt are kept.
void ccl_bittable_set ( ccl_bittable bt,
int  index 
)

Set the bit at position index.

If index is out of the current bounds of bt then the table is resized to contain index.

Parameters
btthe table of bits
indexthe index of the bit
Precondition
bt != NULL
index >= 0
ccl_bittable* ccl_bittable_sub ( const ccl_bittable bt1,
const ccl_bittable bt2 
)

Computes the bitwise difference of tables bt1 and bt2.

Parameters
bt1the first table
bt2the second table
Precondition
ccl_bittable_get_size (bt1) == ccl_bittable_get_size (bt2)
Returns
the difference of sets of integers represented by bt1 and bt2
ccl_bittable* ccl_bittable_union ( const ccl_bittable bt1,
const ccl_bittable bt2 
)

Computes the bitwise disjunction of tables bt1 and bt2.

Parameters
bt1the first table
bt2the second table
Precondition
ccl_bittable_get_size (bt1) == ccl_bittable_get_size (bt2)
Returns
the union of sets of integers represented by bt1 and bt2
void ccl_bittable_unset ( ccl_bittable bt,
int  index 
)

Unset the bit at position index.

If index is out of the current bounds of bt then the table is resized to contain index.

Parameters
btthe table of bits
indexthe index of the bit
Precondition
bt != NULL
index >= 0
void ccl_bittable_window_union ( ccl_bittable bt_dst,
int  dst,
const ccl_bittable bt_src,
int  src,
int  w 
)

Makes a bitwise disjunction between bts_dst and bt_src but on a restricted part of indices.

The function computes a bitwise disjunction of two windows in bt_dst and bt_src. Both windows contain w bits and start respectively at index dst and src. The result of the disjunction is stored in bt_dst at position dst.

Parameters
bt_dstthe table receiving the partial union
dstthe start index the window in bt_dst
bt_srcthe second table
srcthe start index the window in bt_src
wthe width of the window
Precondition
bt_dst != bt_src || dst + w - 1 < src || src + w - 1 < dst
src + w - 1 < ccl_bittable_get_size(bt_src)
dst + w - 1 < ccl_bittable_get_size(bt_dst)
int ccl_bittable_window_union_with_roll ( ccl_bittable bt_dst,
int  dst,
const ccl_bittable bt_src,
int  src,
int  w 
)

Does the same work than ccl_bittable_window_union but the window of bt_src is rolled for 1 bit on the right (i.e. circular shift on the right) prior the disjunction.

Parameters
bt_dstthe table receiving the partial union
dstthe start index the window in bt_dst
bt_srcthe second table
srcthe start index the window in bt_src
wthe width of the window
Precondition
bt_dst != bt_src || dst + w - 1 < src || src + w - 1 < dst
src + w - 1 < ccl_bittable_get_size(bt_src)
dst + w - 1 < ccl_bittable_get_size(bt_dst)