The Bit-vector Library  0.3.0
Typedefs
bitv.h File Reference

Header for Bit-vector Library (CDSL) More...

#include <stddef.h>
Include dependency graph for bitv.h:
This graph shows which files directly or indirectly include this file:

Typedefs

typedef struct bitv_t bitv_t
 represents a bit-vector.

Functions

bit-vector creating/destroying functions:
bitv_tbitv_new (size_t)
 creates a new bit-vector.
void bitv_free (bitv_t **)
 destroys a bit-vector.
data/information retrieving functions:
size_t bitv_length (const bitv_t *)
 returns the length of a bit-vector.
size_t bitv_count (const bitv_t *)
 returns the number of bits set.
int bitv_get (const bitv_t *, size_t)
 gets a bit in a bit-vector.
int bitv_put (bitv_t *, size_t, int)
 changes the value of a bit in a bit-vector.
void bitv_set (bitv_t *, size_t, size_t)
 sets bits to 1 in a bit-vector.
void bitv_clear (bitv_t *, size_t, size_t)
 clears bits in a bit-vector.
void bitv_not (bitv_t *, size_t, size_t)
 complements bits in a bit-vector.
void bitv_setv (bitv_t *, unsigned char *, size_t)
 sets bits in a bit-vector with bit patterns.
bit-vector handling functions:
void bitv_map (bitv_t *, void(size_t, int, void *), void *)
bit-vector comparison functions:
int bitv_eq (const bitv_t *, const bitv_t *)
 compares two bit-vectors for equality.
int bitv_leq (const bitv_t *, const bitv_t *)
 compares two bit-vectors for subset.
int bitv_lt (const bitv_t *, const bitv_t *)
 compares two bit-vectors for proper subset.
set operation functions:
bitv_tbitv_union (const bitv_t *, const bitv_t *)
 returns a union of two bit-vectors.
bitv_tbitv_inter (const bitv_t *, const bitv_t *)
 returns an intersection of two bit-vectors.
bitv_tbitv_minus (const bitv_t *, const bitv_t *)
 returns a difference of two bit-vectors.
bitv_tbitv_diff (const bitv_t *, const bitv_t *)
 returns a symmetric difference of two bit-vectors.

Detailed Description

Header for Bit-vector Library (CDSL)

Documentation for Bit-vector Library (CDSL)


Function Documentation

void bitv_clear ( bitv_t set,
size_t  l,
size_t  h 
)

clears bits in a bit-vector.

bitv_clear() clears bits in a specified range of a bit-vector. The inclusive lower bound l and the inclusive upper bound h specify the range. l must be equal to or smaller than h and h must be smaller than the length of the bit-vector to set.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for set

Parameters:
[in,out]setbit-vector to set
[in]llower bound of range (inclusive)
[in]hupper bound of range (inclusive)
Returns:
nothing
size_t bitv_count ( const bitv_t set)

returns the number of bits set.

bitv_count() returns the number of bits set in a bit-vector.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for set

Parameters:
[in]setbit-vector to count
Returns:
number of bits set
bitv_t* bitv_diff ( const bitv_t t,
const bitv_t s 
)

returns a symmetric difference of two bit-vectors.

bitv_diff() returns a symmetric difference of two bit-vectors of the same length; the bit in the resulting bit-vector is set if only one of the corresponding bits in the operands is set. One of those may be a null pointer, in which case it is considered an empty (all-cleared) bit-vector. bitv_diff() constitutes a distinct bit-vector from its operands as a result, which means it always allocates storage for its result even when one of the operands is empty.

Possible exceptions: assert_exceptfail, mem_exceptfail

Unchecked errors: foreign data structure given for s or t

Parameters:
[in]soperand of difference operation
[in]toperand of difference operation
Returns:
symmetric difference of bit-vectors

Here is the call graph for this function:

int bitv_eq ( const bitv_t s,
const bitv_t t 
)

compares two bit-vectors for equality.

bitv_eq() compares two bit-vectors to check whether they are equal. Two bit-vectors must be of the same length.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for s or t

Parameters:
[in]sbit-vector to compare
[in]tbit-vector to compare
Returns:
whether or not two bit-vectors compare equal
Return values:
0not equal
1equal
void bitv_free ( bitv_t **  pset)

destroys a bit-vector.

bitv_free() destroys a bit-vector by deallocating the storage for it and set a given pointer to a null pointer.

Possible exceptions: assert_exceptfail

Unchecked errors: pointer to foreign data structure given for pset

Parameters:
[in,out]psetpointer to bit-vector to destroy
Returns:
nothing
int bitv_get ( const bitv_t set,
size_t  n 
)

gets a bit in a bit-vector.

bitv_get() inspects whether a bit in a bit-vector is set or not. The position of a bit to inspect, n starts at 0 and must be smaller than the length of the bit-vector to inspect.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for set

Parameters:
[in]setbit-vector to inspect
[in]nbit position
Returns:
bit value (0 or 1)
bitv_t* bitv_inter ( const bitv_t t,
const bitv_t s 
)

returns an intersection of two bit-vectors.

bitv_inter() creates an intersection of two bit-vectors of the same length and returns it. One of those may be a null pointer, in which case it is considered an empty (all-cleared) bit-vector. bitv_inter() constitutes a distinct bit-vector from its operands as a result, which means it always allocates storage for its result even when one of the operands is empty.

Possible exceptions: assert_exceptfail, mem_exceptfail

Unchecked errors: foreign data structure given for s or t

Parameters:
[in]soperand of intersection operation
[in]toperand of intersection operation
Returns:
intersection of bit-vectors

Here is the call graph for this function:

size_t bitv_length ( const bitv_t set)

returns the length of a bit-vector.

bitv_length() returns the length of a bit-vector which is the number of bits in a bit-vector.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for set

Parameters:
[in]setbit-vector whose legnth returned
Returns:
length of bit-vector
int bitv_leq ( const bitv_t s,
const bitv_t t 
)

compares two bit-vectors for subset.

bitv_leq() compares two bit-vectors to check whether a bit-vector is a subset of the other; note that two bit-vectors have a subset relationship for each other when they compare equal. Two bit-vectors must be of the same length.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for s or t

Parameters:
[in]sbit-vector to compare
[in]tbit-vector to compare
Returns:
whether s is a subset of t
Return values:
0s is not a subset of t
1s is a subset of t
int bitv_lt ( const bitv_t s,
const bitv_t t 
)

compares two bit-vectors for proper subset.

bitv_lt() compares two bit-vectors to check whether a bit-vector is a proper subset of the other. Two bit-vectors must be of the same length.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for s or t

Parameters:
[in]sbit-vector to compare
[in]tbit-vector to compare
Returns:
whether s is a proper subset of t
Return values:
0s is not a proper subset of t
1s is a proper subset of t
bitv_t* bitv_minus ( const bitv_t t,
const bitv_t s 
)

returns a difference of two bit-vectors.

bitv_minus() returns a difference of two bit-vectors of the same length; the bit in the resulting bit-vector is set if and only if the corresponding bit in the first operand is set and the corresponding bit in the second operand is not set. One of those may be a null pointer, in which case it is considered an empty (all-cleared) bit-vector. bitv_minus() constitutes a distinct bit-vector from its operands as a result, which means it always allocates storage for its result even when one of the operands is empty.

Possible exceptions: assert_exceptfail, mem_exceptfail

Unchecked errors: foreign data structure given for s or t

Parameters:
[in]soperand of difference operation
[in]toperand of difference operation
Returns:
difference of bit-vectors, s - t

Here is the call graph for this function:

bitv_t* bitv_new ( size_t  len)

creates a new bit-vector.

bitv_new() creates a new bit-vector. Since a bit-vector has a much simpler data structure than a set (provided by cdsl/set) does, the only information that bitv_new() needs to create a new instance is the length of the bit vector it will create; bitv_new() will create a bit-vector with length bits. The length cannot be changed after creation.

Possible exceptions: mem_exceptfail

Parameters:
[in]lenlength of bit-vector to create

new bit-vector created

Here is the caller graph for this function:

void bitv_not ( bitv_t set,
size_t  l,
size_t  h 
)

complements bits in a bit-vector.

bitv_not() flips bits in a specified range of a bit-vector. The inclusive lower bound l and the inclusive upper bound h specify the range. l must be equal to or smaller than h and h must be smaller than the length of the bit-vector to set.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for set

Parameters:
[in,out]setbit-vector to set
[in]llower bound of range (inclusive)
[in]hupper bound of range (inclusive)
Returns:
nothing
int bitv_put ( bitv_t set,
size_t  n,
int  bit 
)

changes the value of a bit in a bit-vector.

bitv_put() changes the value of a bit in a bit-vector to 0 or 1 and returns its previous value. The position of a bit to change, n starts at 0 and must be smaller than the length of the bit-vector.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for set

Parameters:
[in,out]setbit-vector to set
[in]nbit position
[in]bitvalue
Returns:
previous value of bit
void bitv_set ( bitv_t set,
size_t  l,
size_t  h 
)

sets bits to 1 in a bit-vector.

bitv_set() sets bits in a specified range of a bit-vector to 1. The inclusive lower bound l and the inclusive upper bound h specify the range. l must be equal to or smaller than h and h must be smaller than the length of the bit-vector to set.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for set

Parameters:
[in,out]setbit-vector to set
[in]llower bound of range (inclusive)
[in]hupper bound of range (inclusive)
Returns:
nothing
void bitv_setv ( bitv_t set,
unsigned char *  v,
size_t  n 
)

sets bits in a bit-vector with bit patterns.

bitv_setv() copies bit patterns from an array of bytes to a bit vector. Because only 8 bits in a byte are used to represent a bit-vector for table-driven approaches, any excess bits are masked out before copying, which explains why bitv_setv() needs to modify the array, v.

Be careful with how to count bit positions in a bit vector. Within a byte, the first bit (the bit position 0) indicates the least significant bit of a byte and the last bit (the bit position 7) does the most significant bit. Therefore, the array

      { 0x01, 0x02, 0x03, 0x04 }

can be used to set bits of a bit-vector as follows:

      0        8        16       24     31
      |        |        |        |      |
      10000000 01000000 11000000 00100000

where the bit position is shown on the first line.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for set, invalid pointer given for v, invalid size given for n

Parameters:
[in,out]setbit-vector to set
[in,out]vbit patterns to use
[in]nsize of v in bytes
Returns:
nothing
bitv_t* bitv_union ( const bitv_t t,
const bitv_t s 
)

returns a union of two bit-vectors.

bitv_union() creates a union of two given bit-vectors of the same length and returns it. One of those may be a null pointer, in which case it is considered an empty (all-cleared) bit-vector. bitv_union() constitutes a distinct bit-vector from its operands as a result, which means it always allocates storage for its results even when one of the operands is empty. This property can be used to make a copy of a bit-vector as follows:

      bitv_t *v *w;
      v = bitv_new(n);
      ...
      w = bitv_union(v, NULL);

Possible exceptions: assert_exceptfail, mem_exceptfail

Unchecked errors: foreign data structure given for s or t

Parameters:
[in]soperand of union operation
[in]toperand of union operation
Returns:
union of bit-vectors
 All Files Functions Typedefs