The Bit-vector Library
0.3.0
|
Source for Bit-vector Library (CDSL) More...
#include <stddef.h>
#include <string.h>
#include "cbl/memory.h"
#include "cbl/assert.h"
#include "bitv.h"
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. |
Source for Bit-vector Library (CDSL)
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
[in,out] | set | bit-vector to set |
[in] | l | lower bound of range (inclusive) |
[in] | h | upper bound of range (inclusive) |
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
[in] | set | bit-vector to count |
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
[in] | s | operand of difference operation |
[in] | t | operand of difference operation |
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
[in] | s | bit-vector to compare |
[in] | t | bit-vector to compare |
0 | not equal |
1 | equal |
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
[in,out] | pset | pointer to bit-vector to destroy |
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
[in] | set | bit-vector to inspect |
[in] | n | bit position |
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
[in] | s | operand of intersection operation |
[in] | t | operand of intersection operation |
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
[in] | set | bit-vector whose legnth returned |
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
[in] | s | bit-vector to compare |
[in] | t | bit-vector to compare |
s
is a subset of t
0 | s is not a subset of t |
1 | s is a subset of 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
[in] | s | bit-vector to compare |
[in] | t | bit-vector to compare |
s
is a proper subset of t
0 | s is not a proper subset of t |
1 | s is a proper subset of t |
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
[in,out] | set | bit-vector with which apply called |
[in] | apply | user-provided function (callback) |
[in] | cl | passing-by argument to apply |
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
[in] | s | operand of difference operation |
[in] | t | operand of difference operation |
s
- t
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
[in] | len | length of bit-vector to create |
new bit-vector created
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
[in,out] | set | bit-vector to set |
[in] | l | lower bound of range (inclusive) |
[in] | h | upper bound of range (inclusive) |
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
[in,out] | set | bit-vector to set |
[in] | n | bit position |
[in] | bit | value |
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
[in,out] | set | bit-vector to set |
[in] | l | lower bound of range (inclusive) |
[in] | h | upper bound of range (inclusive) |
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
[in,out] | set | bit-vector to set |
[in,out] | v | bit patterns to use |
[in] | n | size of v in bytes |
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
[in] | s | operand of union operation |
[in] | t | operand of union operation |