Rabbit Tree
Radix bit tries for implementing associative arrays and sets in C.
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Functions
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_TRBT_SET_DIFFERENCE (RBT_NODE_T *a, RBT_NODE_T *b)
 
RBT_NODE_TRBT_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_TRBT_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_TRBT_SET_UNION (RBT_NODE_T *a, RBT_NODE_T *b)
 

Detailed Description

Author
Xyne

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

Included Headers

Required macro definitions:

Optional macro definitions

Function Documentation

void RBT_SET_ADD ( RBT_NODE_T set,
RBT_KEY_T  item 
)

Add an item to a set.

Parameters
[in]setThe root node of the set.
[in]itemThe item to add.
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]aThe main set.
[in]bThe set to remove.
Returns
The resulting set.
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]aThe first set.
[in]bThe second set.
Returns
The set of the exclusive disjunction.
int RBT_SET_INCLUDES ( RBT_NODE_T set,
RBT_KEY_T  item 
)

Check if a set includes an item.

Parameters
[in]setThe root node of the set.
[in]itemThe item to check.
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]aThe first set.
[in]bThe second set.
Returns
The set of the intersection.
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]aThe subset candidate.
[in]bThe superset candidate.
Returns
Non-zero if a is a subset of b.
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]aThe set from which to remove elements of the other set.
[in]bThe other set.
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]aThe set to hold the exclusive disjunction of itself and another set.
[in]bThe other set.
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]aThe set to hold the intersection of itself and another set.
[in]bThe other set.
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]aThe set to which to add the elements of the other set.
[in]bThe other set.
void RBT_SET_REMOVE ( RBT_NODE_T set,
RBT_KEY_T  item 
)

Remove an item from a set.

Parameters
[in]setThe root node of the set.
[in]itemThe item to remove.
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]aThe first set.
[in]bThe second set.
Returns
The set containing the union.