Implementation of vectors of bits. More...

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

Macros
#define	ccl_bittable_delete ccl_bittable_del_reference
	Releases resources allocated to bt. More...

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

Functions
ccl_bittable *	ccl_bittable_create (int size)
	Creates a new table of bits large enough for size bits. 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 (const ccl_bittable *bt)
	Returns the index of the first non-null bit. More...

int	ccl_bittable_get_next (const 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_bittable *	ccl_bittable_dup (const ccl_bittable *bt)
	Duplicates the table bt. More...

int	ccl_bittable_get_nb_one (const 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_bittable *	ccl_bittable_resize (ccl_bittable *bt, int newsize)
	Resize the table of bits bt for newsize bits. More...

ccl_bittable *	ccl_bittable_union (const ccl_bittable bt1, const ccl_bittable bt2)
	Computes the bitwise disjunction of tables bt1 and bt2. More...

ccl_bittable *	ccl_bittable_nary_union (ccl_bittable **bts, int nb_bts)
	Computes the bitwise disjunction of tables bt[0], ..., bt[nb_bts-1]. More...

ccl_bittable *	ccl_bittable_intersection (const ccl_bittable bt1, const ccl_bittable bt2)
	Computes the bitwise conjunction of tables bt1 and bt2. More...

ccl_bittable *	ccl_bittable_sub (const ccl_bittable bt1, const ccl_bittable bt2)
	Computes the bitwise difference of tables bt1 and bt2. More...

ccl_bittable *	ccl_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.

Macro Definition Documentation

#define ccl_bittable_delete ccl_bittable_del_reference

Releases resources allocated to bt.

Parameters

bt	the table of bits

Precondition: bt != NULL

Definition at line 53 of file ccl-bittable.h.

Function Documentation

void ccl_bittable_clear ( ccl_bittable * bt )

Sets to zero all bits of bt.

Parameters

bt	the table of bits

Precondition: bt != NULL

ccl_bittable* ccl_bittable_complement ( const ccl_bittable * bt )

Negate the bits of bt.

Parameters

bt	the 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

size	the minimal number of bits of the table

Precondition: size >= 0

Returns: a new table of bits large enough for size bits

ccl_bittable* ccl_bittable_dup ( const ccl_bittable * bt )

Duplicates the table bt.

Parameters

bt	the 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

bt1	the first table
bt2	the second table

Precondition: bt1 != NULL; bt2 != NULL

Returns: a non-null value if bt1 and bt2 are equal.

int ccl_bittable_get_first ( const ccl_bittable * bt )

Returns the index of the first non-null bit.

Parameters

bt	the 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 ( const ccl_bittable * bt )

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

Parameters

bt	the table of bits

Precondition: bt != NULL

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

int ccl_bittable_get_next	(	const ccl_bittable *	bt,
		int	prev
	)

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

Parameters

bt	the table of bits
prev	a 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

bt	the 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

bt	the 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

bt	the table of bits
index	the 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

bt	the 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

bt1	the first table
bt2	the 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

bt1	the first table of bits
bt2	the 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

log	the stream
bt	the 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

bts	an array of bit tables
nb_bts	number 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

bt	the table of bits
newsize	the 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

bt	the table of bits
index	the 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

bt1	the first table
bt2	the 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

bt1	the first table
bt2	the 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

bt	the table of bits
index	the 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_dst	the table receiving the partial union
dst	the start index the window in bt_dst
bt_src	the second table
src	the start index the window in bt_src
w	the 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_dst	the table receiving the partial union
dst	the start index the window in bt_dst
bt_src	the second table
src	the start index the window in bt_src
w	the 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)

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

Function Documentation