Data Structures
struct	set_iter_s
	Represent the state of a scan through a set. More...

struct	set_pool_s

struct	set_s
	Represent a set using a bitmap. More...

Macros
#define	SET_BITS (sizeof (set_bits_t) * 8)

#define	SET_DEFMAP_SIZE

#define	SET_ONE ((set_bits_t) 1)

#define	SET_SIZE(x) (((x) + SET_BITS) & ~(SET_BITS - 1))

#define	SET_TEST_MEMBER(s, x) ((s)->map[(x) / SET_BITS] & (SET_ONE << ((x) % SET_BITS)))

#define	SET_WORDS(s) ((s)->size / SET_BITS)

#define	SET_ZERO ((set_bits_t) 0)

Typedefs
typedef uint32_t	set_bits_t

typedef struct set_iter_s	set_iter_t
	Represent the state of a scan through a set. More...

typedef struct set_pool_s	set_pool_t

typedef struct set_s	set_t
	Represent a set using a bitmap. More...

Functions
set_t *	set_add (set_t *set, unsigned x)
	Add an element to a set. More...

const char *	set_as_string (const set_t *set)
	Return a human-readable string representing the set. More...

set_t *	set_assign (set_t dst, const set_t src)
	Make a set equivalent to another. More...

void	set_del_iter (set_iter_t *set_iter)
	Delete a set iterator that is no longer needed. More...

void	set_del_iter_r (set_pool_t set_pool, set_iter_t set_iter)

void	set_delete (set_t *set)
	Delete a set that is no longer needed. More...

void	set_delete_r (set_pool_t set_pool, set_t set)

set_t *	set_difference (set_t dst, const set_t src)
	Compute the diffedrence of two sets. More...

set_t *	set_empty (set_t *set)
	Make a set the empty set. More...

set_t *	set_everything (set_t *set)
	Make a set the set of everything. More...

set_iter_t *	set_first (const set_t *set)
	Find the first "member" of the set. More...

set_iter_t *	set_first_r (set_pool_t set_pool, const set_t set)

set_t *	set_intersection (set_t dst, const set_t src)
	Compute the intersection of two sets. More...

set_t *	set_invert (set_t *set)
	Compute the inverse of a set. More...

int	set_is_disjoint (const set_t s1, const set_t s2)
	Test if two sets are disjoint. More...

int	set_is_empty (const set_t *set)
	Test if a set is the set of everything. More...

int	set_is_equivalent (const set_t s1, const set_t s2)
	Test if two sets are equivalent. More...

int	set_is_everything (const set_t *set)
	Test if a set is the set of everything. More...

int	set_is_intersecting (const set_t s1, const set_t s2)
	Test if two sets intersect. More...

int	set_is_member (const set_t *set, unsigned x)
	Test an element for membership in a set. More...

int	set_is_subset (const set_t set, const set_t sub)
	Test if a set is a subset of another set. More...

set_t *	set_new (void)
	Create a new set. More...

set_t *	set_new_r (set_pool_t *set_pool)

set_t *	set_new_size (int size)
	Create a new set with space pre-allocated for the specified set size. More...

set_t *	set_new_size_r (set_pool_t *set_pool, int size)

set_iter_t *	set_next (set_iter_t *set_iter)
	Find the next "member" of the set. More...

set_iter_t *	set_next_r (set_pool_t set_pool, set_iter_t set_iter)

void	set_pool_init (set_pool_t *set_pool)

set_t *	set_remove (set_t *set, unsigned x)
	Remove an element from a set. More...

set_t *	set_reverse_difference (set_t dst, const set_t src)
	Compute the diffedrence of two sets. More...

unsigned	set_size (const set_t *set)
	Obtain the number of members (or non-members) of a set. More...

set_t *	set_union (set_t dst, const set_t src)
	Compute the union of two sets. More...

Detailed Description

Macro Definition Documentation

#define SET_BITS (sizeof (set_bits_t) * 8)

#define SET_DEFMAP_SIZE

Value:

((32 - sizeof (struct set_s *) \
                          - sizeof (set_bits_t *) \
                          - sizeof (int) - sizeof (unsigned))\
                         / sizeof (set_bits_t))

#define SET_ONE ((set_bits_t) 1)

#define SET_SIZE ( x ) (((x) + SET_BITS) & ~(SET_BITS - 1))

#define SET_TEST_MEMBER	(	s,
		x
	)	((s)->map[(x) / SET_BITS] & (SET_ONE << ((x) % SET_BITS)))

#define SET_WORDS ( s ) ((s)->size / SET_BITS)

#define SET_ZERO ((set_bits_t) 0)

Typedef Documentation

typedef uint32_t set_bits_t

typedef struct set_iter_s set_iter_t

Represent the state of a scan through a set.

Very useful in for-loops:

 set_t      *set;
 set_iter_t *iter;
 
 create_and_populate (set);
 for (iter = set_first (set); iter; iter = set_next (iter))
     do_something (iter->element);

typedef struct set_pool_s set_pool_t

typedef struct set_s set_t

Represent a set using a bitmap.

When inverted is zero, ones in the bitmap represent members, but when inverted is non-zero, zeros in the bitmap represent members. However, this really is all private implementation details and it is best to treat set_t as a black box.

Function Documentation

set_t* set_add	(	set_t *	set,
		unsigned	x
	)

Add an element to a set.

It is not an error to add an element that is already a member of the set.

Note: set is modified.

Parameters

set	The set to which the element will be added.
x	The element to be added.

Returns: The modified set.

const char* set_as_string ( const set_t * set )

Return a human-readable string representing the set.

Empty sets will be represented by the string "[empty]". Sets of everything will be represented by the string "[everything]". Inverted sets will have the first implicit member followed by "..." (eg, "256 ...").

Parameters

set	The set to be converted to a string.

Returns: The human readable representation of the string.

Warning: The string is kept in a static variable, so subsequent calls will overwrite the results of preceeding calls.

set_t* set_assign	(	set_t *	dst,
		const set_t *	src
	)

Make a set equivalent to another.

Note: dst is modified.

Parameters

dst	The destination set to make equivalent.
src	The source set to assign to dst.

Returns: The modified destination set.

void set_del_iter ( set_iter_t * set_iter )

Delete a set iterator that is no longer needed.

Parameters

set_iter The set iterator to be deleted.

void set_del_iter_r	(	set_pool_t *	set_pool,
		set_iter_t *	set_iter
	)

void set_delete ( set_t * set )

Delete a set that is no longer needed.

Parameters

set	The set to be deleted.

void set_delete_r	(	set_pool_t *	set_pool,
		set_t *	set
	)

set_t* set_difference	(	set_t *	dst,
		const set_t *	src
	)

Compute the diffedrence of two sets.

The computation is done as dst = dst - src.

Note: dst is modified.

Parameters

dst	The destination set to be modified.
src	The source set.

Returns: The destination set modified to be dst - src.

set_t* set_empty ( set_t * set )

Make a set the empty set.

Note: set is modified.

Parameters

set	The set to make the empty set.

Returns: set.

set_t* set_everything ( set_t * set )

Make a set the set of everything.

Note: set is modified.

Parameters

set	The set to make the set of everything.

Returns: set.

set_iter_t* set_first ( const set_t * set )

Find the first "member" of the set.

Warning: For normal sets, the set iterator represents a member of the set, but for inverted sets, the set iterator represetns a non-member of the set.

Parameters

set	The set to scan.

Returns: A pointer to a set iterator indicating the first (non-)member of the set, or null if the set is empty or of everything.

set_iter_t* set_first_r	(	set_pool_t *	set_pool,
		const set_t *	set
	)

set_t* set_intersection	(	set_t *	dst,
		const set_t *	src
	)

Compute the intersection of two sets.

The computation is done as dst = dst & src.

Note: dst is modified.

Parameters

dst	The destination set to be modified.
src	The source set.

Returns: The destination set modified to be dst & src.

set_t* set_invert ( set_t * set )

Compute the inverse of a set.

The computation is done as set = ~set.

Note: set is modified.

Parameters

set	The set to be inverted.

Returns: The set modified to be ~src.

int set_is_disjoint	(	const set_t *	s1,
		const set_t *	s2
	)

Test if two sets are disjoint.

Parameters

s1	The first set to test.
s2	The second set to test.

Returns: 1 if s2 is disjoint from s1, 0 if not.

Note: The emtpy set is disjoint with itself.

int set_is_empty ( const set_t * set )

Test if a set is the set of everything.

Parameters

set	The set to test.

Returns: 1 if set is empty (non-inverted).

int set_is_equivalent	(	const set_t *	s1,
		const set_t *	s2
	)

Test if two sets are equivalent.

Parameters

s1	The first set to test.
s2	The second set to test.

Returns: 1 if s2 is equivalent to s1, 0 if not.

int set_is_everything ( const set_t * set )

Test if a set is the set of everything.

Parameters

set	The set to test.

Returns: 1 if set is the set of everything (empty inverted set).

int set_is_intersecting	(	const set_t *	s1,
		const set_t *	s2
	)

Test if two sets intersect.

Parameters

s1	The first set to test.
s2	The second set to test.

Returns: 1 if s2 intersects s1, 0 if not.

Note: Equivalent non-empty sets are treated as intersecting.

int set_is_member	(	const set_t *	set,
		unsigned	x
	)

Test an element for membership in a set.

Parameters

set	The set to test.
x	The element to test.

Returns: 1 if the element is a member of the set, otherwise 0.

int set_is_subset	(	const set_t *	set,
		const set_t *	sub
	)

Test if a set is a subset of another set.

An equivalent set is considered to be a subset.

Parameters

set	The potential super-set.
sub	The potential subset.

Returns: 1 if sub is a subset of set, or if the sets are equivalent.

set_t* set_new ( void )

Create a new set.

The set is initialized to be the empty set.

Returns: The newly created, empty set.

set_t* set_new_r ( set_pool_t * set_pool )

inline

set_t* set_new_size ( int size )

Create a new set with space pre-allocated for the specified set size.

Although sets automatically grow to accommodate new members as necessary, sometimes the maximum set size is known in advance and it can be more efficient to grow the set in advance.

The set is initialized to be the empty set.

Parameters

size	The number of elements for which space is to be allocated.

Returns: The newly created, empty set.

set_t* set_new_size_r	(	set_pool_t *	set_pool,
		int	size
	)

inline

set_iter_t* set_next ( set_iter_t * set_iter )

Find the next "member" of the set.

Warning: For normal sets, the set iterator represents a member of the set, but for inverted sets, the set iterator represetns a non-member of the set.

Parameters

set_iter The set iterator representing the state of the current scan.

Returns: A pointer to a set iterator indicating the next (non-)member of the set, or null if no mor (non-)members are available.

Note: The set iterator is automatically deleted when the end of the set is reached.

set_iter_t* set_next_r	(	set_pool_t *	set_pool,
		set_iter_t *	set_iter
	)

void set_pool_init ( set_pool_t * set_pool )

set_t* set_remove	(	set_t *	set,
		unsigned	x
	)

Remove an element from a set.

It is not an error to remove an element that is not a member of the set.

Note: set is modified.

Parameters

set	The set from which the element will be removed.
x	The element to be removed.

Returns: The modified set.

set_t* set_reverse_difference	(	set_t *	dst,
		const set_t *	src
	)

Compute the diffedrence of two sets.

The computation is done as dst = src - dst.

Note: dst is modified.

Parameters

dst	The destination set to be modified.
src	The source set.

Returns: The destination set modified to be src - dst.

unsigned set_size ( const set_t * set )

Obtain the number of members (or non-members) of a set.

Normal sets return the number of members, inverted sets return the number of non-members.

Parameters

set	The set from which the number of (non-)members will be obtained.

Returns: The number of (non-)members. Both empty sets and sets of evertything will return 0.

set_t* set_union	(	set_t *	dst,
		const set_t *	src
	)

Compute the union of two sets.

The computation is done as dst = dst | src.

Note: dst is modified.

Parameters

dst	The destination set to be modified.
src	The source set.

Returns: The destination set modified to be dst | src.

Data Structures

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

Typedef Documentation

Function Documentation