set.h File Reference

#include <stdint.h>
#include "common.h"
#include "debug.h"
#include "key.h"

Include dependency graph for set.h:

Go to the source code of this file.

Functions
void	RBT_SET_ADD (RBT_NODE_T *set, RBT_KEY_T item)
RBT_NODE_T *	RBT_SET_DIFFERENCE (RBT_NODE_T *a, RBT_NODE_T *b)
RBT_NODE_T *	RBT_SET_EXCLUSIVE_DISJUNCTION (RBT_NODE_T *a, RBT_NODE_T *b)
int	RBT_SET_INCLUDES (RBT_NODE_T *set, RBT_KEY_T item)
RBT_NODE_T *	RBT_SET_INTERSECTION (RBT_NODE_T *a, RBT_NODE_T *b)
int	RBT_SET_IS_SUBSET (RBT_NODE_T *a, RBT_NODE_T *b)
void	RBT_SET_MODIFY_DIFFERENCE (RBT_NODE_T *a, RBT_NODE_T *b)
void	RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION (RBT_NODE_T *a, RBT_NODE_T *b)
void	RBT_SET_MODIFY_INTERSECTION (RBT_NODE_T *a, RBT_NODE_T *b)
void	RBT_SET_MODIFY_UNION (RBT_NODE_T *a, RBT_NODE_T *b)
void	RBT_SET_REMOVE (RBT_NODE_T *set, RBT_KEY_T item)
RBT_NODE_T *	RBT_SET_UNION (RBT_NODE_T *a, RBT_NODE_T *b)

Detailed Description

Author

Xyne

Copyright

GPL2 only

Overview

Sets are implemented with associative arrays that map keys to integer values. The keys act as set items and the integer values determine set membership.

All node functions will work on sets.

Required Headers

• key.h

Included Headers

• node.h
• wrapper.h

Required macro definitions:

• RBT_SET_H_PREFIX_

  The prefix for visible variable and function declarations in this header. This will also be used as the prefix for the included files.

• RBT_KEY_T

  The type of the keys that will be used. The only requirement for a key is that a pointer can be extracted from it and used to read the underlying contiguous bits.

• RBT_KEY_COUNT_BITS(key)

  Return the number of bits in the key.

• RBT_KEY_PTR(key)

  Return a pointer to the underlying bytes.

• RBT_KEY_FPRINT(fd, key)

  Print a representation of the key to the given file descriptor.

Optional macro definitions

• RBT_KEY_SIZE_FIXED

  The size of the key, in bytes, if it is fixed or if a maximum key size can be anticipated.

Function Documentation

RBT_SET_ADD()

void RBT_SET_ADD	(	RBT_NODE_T *	set,
		RBT_KEY_T	item
	)

Add an item to a set.

Parameters

[in]	set	The root node of the set.
[in]	item	The item to add.

RBT_SET_DIFFERENCE()

RBT_NODE_T * RBT_SET_DIFFERENCE	(	RBT_NODE_T *	a,
		RBT_NODE_T *	b
	)

Create a set that contains all items in set a that are not in set b.

Neither a nor b is not changed.

Parameters

[in]	a	The main set.
[in]	b	The set to remove.

Returns

The resulting set.

RBT_SET_EXCLUSIVE_DISJUNCTION()

RBT_NODE_T * RBT_SET_EXCLUSIVE_DISJUNCTION	(	RBT_NODE_T *	a,
		RBT_NODE_T *	b
	)

Create the exclusive disjunction of sets a and b.

Neither a nor b is not changed.

Parameters

[in]	a	The first set.
[in]	b	The second set.

Returns

The set of the exclusive disjunction.

RBT_SET_INCLUDES()

int RBT_SET_INCLUDES	(	RBT_NODE_T *	set,
		RBT_KEY_T	item
	)

Check if a set includes an item.

Parameters

[in]	set	The root node of the set.
[in]	item	The item to check.

RBT_SET_INTERSECTION()

RBT_NODE_T * RBT_SET_INTERSECTION	(	RBT_NODE_T *	a,
		RBT_NODE_T *	b
	)

Modify a in place to be the result of an intersection with b.

Neither a nor b is not changed.

Parameters

[in]	a	The first set.
[in]	b	The second set.

Returns

The set of the intersection.

RBT_SET_IS_SUBSET()

int RBT_SET_IS_SUBSET	(	RBT_NODE_T *	a,
		RBT_NODE_T *	b
	)

Determine if a is a subset of b.

Neither set is changed.

Parameters

[in]	a	The subset candidate.
[in]	b	The superset candidate.

Returns

Non-zero if a is a subset of b.

RBT_SET_MODIFY_DIFFERENCE()

void RBT_SET_MODIFY_DIFFERENCE	(	RBT_NODE_T *	a,
		RBT_NODE_T *	b
	)

Remove all elements of b from a.

b is not changed.

Parameters

[in]	a	The set from which to remove elements of the other set.
[in]	b	The other set.

RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION()

void RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION	(	RBT_NODE_T *	a,
		RBT_NODE_T *	b
	)

Update a in place to be the result of an exclusive disjunction (xor) with b.

b is not changed.

Parameters

[in]	a	The set to hold the exclusive disjunction of itself and another set.
[in]	b	The other set.

RBT_SET_MODIFY_INTERSECTION()

void RBT_SET_MODIFY_INTERSECTION	(	RBT_NODE_T *	a,
		RBT_NODE_T *	b
	)

Create a set that is the intersection of sets a and b.

b is not changed.

Parameters

[in]	a	The set to hold the intersection of itself and another set.
[in]	b	The other set.

RBT_SET_MODIFY_UNION()

void RBT_SET_MODIFY_UNION	(	RBT_NODE_T *	a,
		RBT_NODE_T *	b
	)

Add all elements of set b to set a.

b is not changed.

Parameters

[in]	a	The set to which to add the elements of the other set.
[in]	b	The other set.

RBT_SET_REMOVE()

void RBT_SET_REMOVE	(	RBT_NODE_T *	set,
		RBT_KEY_T	item
	)

Remove an item from a set.

Parameters

[in]	set	The root node of the set.
[in]	item	The item to remove.

RBT_SET_UNION()

RBT_NODE_T * RBT_SET_UNION	(	RBT_NODE_T *	a,
		RBT_NODE_T *	b
	)

Create a set that is the union of sets a and b.

Neither a nor b is not changed.

Parameters

[in]	a	The first set.
[in]	b	The second set.

Returns

The set containing the union.