The Bit-vector Library  0.3.0
Functions
bitv.c File Reference

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

#include <stddef.h>
#include <string.h>
#include "cbl/memory.h"
#include "cbl/assert.h"
#include "bitv.h"
Include dependency graph for bitv.c:

Functions

bitv_t *() bitv_new (size_t len)
 creates a new bit-vector.
void() bitv_free (bitv_t **pset)
 destroys a bit-vector.
size_t() bitv_length (const bitv_t *set)
 returns the length of a bit-vector.
size_t() bitv_count (const bitv_t *set)
 returns the number of bits set.
int() bitv_get (const bitv_t *set, size_t n)
 gets a bit in a bit-vector.
int() bitv_put (bitv_t *set, size_t n, int bit)
 changes the value of a bit in a bit-vector.
void() bitv_set (bitv_t *set, size_t l, size_t h)
 sets bits to 1 in a bit-vector.
void() bitv_clear (bitv_t *set, size_t l, size_t h)
 clears bits in a bit-vector.
void() bitv_not (bitv_t *set, size_t l, size_t h)
 complements bits in a bit-vector.
void() bitv_setv (bitv_t *set, unsigned char *v, size_t n)
 sets bits in a bit-vector with bit patterns.
void() bitv_map (bitv_t *set, void apply(size_t, int, void *), void *cl)
 calls a user-provided function for each bit in a bit-vector.
int() bitv_eq (const bitv_t *s, const bitv_t *t)
 compares two bit-vectors for equality.
int() bitv_leq (const bitv_t *s, const bitv_t *t)
 compares two bit-vectors for subset.
int() bitv_lt (const bitv_t *s, const bitv_t *t)
 compares two bit-vectors for proper subset.
bitv_t *() bitv_union (const bitv_t *t, const bitv_t *s)
 returns a union of two bit-vectors.
bitv_t *() bitv_inter (const bitv_t *t, const bitv_t *s)
 returns an intersection of two bit-vectors.
bitv_t *() bitv_minus (const bitv_t *t, const bitv_t *s)
 returns a difference of two bit-vectors.
bitv_t *() bitv_diff (const bitv_t *t, const bitv_t *s)
 returns a symmetric difference of two bit-vectors.

Detailed Description

Source 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
void() bitv_map ( bitv_t set,
void   applysize_t, int, void *,
void *  cl 
)

calls a user-provided function for each bit in a bit-vector.

For each bit in a bit-vector, bitv_map() calls a user-provided callback function; it is useful when doing some common task for each bit. The pointer given in cl is passed to the third parameter of a user callback function, so can be used as a communication channel between the caller of bitv_map() and the callback. Differently from mapping functions for other data structures (e.g., tables and sets), changes made in an earlier invocation to apply are visible to later invocations.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for set

Parameters:
[in,out]setbit-vector with which apply called
[in]applyuser-provided function (callback)
[in]clpassing-by argument to apply
Returns:
nothing
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