set.h File Reference

A set data structure. More...

`#include "int_sizes.h"`
`#include "list.h"`

Go to the source code of this file.

## Functions

struct set * | set_create (int buckets)
| Create a new set.
struct set * | set_duplicate (struct set *s)
| Duplicate a set from an existing set.
struct set * | set_union (struct set *s1, struct set *s2)
| Unions two sets into one set.
void | set_clear (struct set *s)
| Remove all entries from a set.
void | set_delete (struct set *s)
| Delete a set.
int | set_size (struct set *s)
| Count the entries in a set.
int | set_insert (struct set *s, const void *element)
| Insert an element to the set.
int | set_insert_set (struct set *s, struct set *s2)
| Insert an existing set into the set.
int | set_insert_list (struct set *s, struct list *l)
| Insert an existing list into the set.
int | set_push (struct set *h, const void *element)
| Insert an element to the set.
int | set_lookup (struct set *s, void *element)
| Look up a element in the set.
int | set_remove (struct set *s, const void *element)
| Remove an element.
void * | set_pop (struct set *s)
| Remove an arbitrary element from the set.
void | set_first_element (struct set *s)
| Begin iteration over all the elements.
void * | set_next_element (struct set *s)
| Continue iteration over all elements.
void | set_random_element (struct set *s, int *offset_bookkeep)
| Begin iteration over all elements from a random offset.
void * | set_next_element_with_offset (struct set *s, int offset_bookkeep)
| Continue iteration over all elements from an arbitray offset.
void ** | set_values (struct set *s)
| A set_size(s) array of the current elements in the set in a random order.
void ** | set_values_array (struct set *s)
| A set_size(s) + 1 array of the current elements in the set in a random order.
void | set_free_values_array (void **values)
| Free an array returned by set_values_array.

## Detailed Description

A set data structure.

Arbitrary objects that are equal (the same location in memory) appear only once in the set. For example, as a set of filenames:

    struct set *s;
    s = set_create(0);

    set_push(s,pathname);
    set_push(s,pathname_b);
    set_push(s,pathname);

    assert(set_size(s) == 2);

    path = set_pop(s);

    assert(set_size(s) == 1);

To list all of the elements in a set, use set_first_element and set_next_element like this:

    void *element;

    set_first_element(s);
    while(element = set_next_element(s)) {
            printf("set contains: %x\n", element);
    }

## Function Documentation

## set_create()

struct set * set_create | ( | int | buckets | ) |

Create a new set.

Parameters

  buckets | The number of elements in the set. If zero, a default element will be used. Increases dynamically as needed.

Returns
  A pointer to a new set.

## set_duplicate()

struct set * set_duplicate | ( | struct set * | s | ) |

Duplicate a set from an existing set.

NOTE: This does not duplicated the element pointers, beware of double frees.

Parameters

  s | The set to be duplicated.

Returns
  A pointer to a new set.

## set_union()

struct set * set_union | ( | struct set * | s1,
|  | struct set * | s2 )

Unions two sets into one set.

Could also be called Merge. NOTE: This does not duplicated the element pointers, beware of double frees.

Parameters

  s1 | A pointer to the first set to be unioned.
  s2 | A pointer to the second set to be unioned.

Returns
  A pointer to a new set.

## set_clear()

void set_clear | ( | struct set * | s | ) |

Remove all entries from a set.

Note that this function will not free all of the objects contained within the set.

Parameters

  s | A pointer to a set.

## set_delete()

void set_delete | ( | struct set * | s | ) |

Delete a set.

Note that this function will not free all of the objects contained within the set.

Parameters

  s | A pointer to a set.

## set_size()

int set_size | ( | struct set * | s | ) |

Count the entries in a set.

Returns
  The number of entries in the set.

Parameters

  s | A pointer to a set.

## set_insert()

int set_insert | ( | struct set * | s,
|  | const void * | element )

Insert an element to the set.

This call will return 0 if element was already in the set. You must call set_remove to remove it. Also note that you cannot insert a null element into the set.

Parameters

  s | A pointer to a set.
  element | A pointer to store.

Returns
  One if the insert succeeded, 0 otherwise.

## set_insert_set()

int set_insert_set | ( | struct set * | s,
|  | struct set * | s2 )

Insert an existing set into the set.

This call will return 1 if all elements of s2 exist or are added to the set. Also note that you cannot insert a null set into the set. NOTE: This does not duplicated the element pointers, beware of double frees.

Parameters

  s | A pointer to a set.
  s2 | A pointer to a set to be inserted.

Returns
  Number of items added to set.

## set_insert_list()

int set_insert_list | ( | struct set * | s,
|  | struct list * | l )

Insert an existing list into the set.

This call will return 1 if all elements of list exist or are added to the set. Also note that you cannot insert a null list into the set. NOTE: This does not duplicated the element pointers, beware of double frees.

Parameters

  s | A pointer to a set.
  l | A pointer to a list to be inserted.

Returns
  Number of items added to set.

## set_push()

int set_push | ( | struct set * | h,
|  | const void * | element )

Insert an element to the set.

This is equivalent to set_insert

## set_lookup()

int set_lookup | ( | struct set * | s,
|  | void * | element )

Look up a element in the set.

Parameters

  s | A pointer to a set.
  element | A pointer to search for.

Returns
  If found, 1, otherwise 0.

## set_remove()

int set_remove | ( | struct set * | s,
|  | const void * | element )

Remove an element.

Parameters

  s | A pointer to a set.
  element | A pointer to remove.

Returns
  If found 1, otherwise 0.

## set_pop()

void * set_pop | ( | struct set * | s | ) |

Remove an arbitrary element from the set.

Parameters

  s | A pointer to a set.

Returns
  The pointer removed.

## set_first_element()

void set_first_element | ( | struct set * | s | ) |

Begin iteration over all the elements.

This function begins a new iteration over a set, allowing you to visit every element in the set. Next, invoke set_next_element to retrieve each element in order.

Parameters

  s | A pointer to a set.

## set_next_element()

void * set_next_element | ( | struct set * | s | ) |

Continue iteration over all elements.

This function returns the next element in the iteration.

Parameters

  s | A pointer to a set.

Returns
  zero if there are no more elements to visit, the next element otherwise.

## set_random_element()

void set_random_element | ( | struct set * | s,
|  | int * | offset_bookkeep )

Begin iteration over all elements from a random offset.

This function begins a new iteration over a set, allowing you to visit every element in the set. Next, invoke set_next_element_with_offset to retrieve each value in order.

Parameters

  s | A pointer to a set.
  offset_bookkeep | An integer to pointer where the origin to the iteration is recorded.

## set_next_element_with_offset()

void * set_next_element_with_offset | ( | struct set * | s,
|  | int | offset_bookkeep )

Continue iteration over all elements from an arbitray offset.

This function returns the next element in the iteration.

Parameters

  s | A pointer to a set.
  offset_bookkeep | The origin for this iteration. See set_random_element

## set_values()

void ** set_values | ( | struct set * | s | ) |

A set_size(s) array of the current elements in the set in a random order.

Caller should free the array.

Parameters

  s | A pointer to a set.

Returns
  An array of pointers. NULL if there are no elements in the set.

## set_values_array()

void ** set_values_array | ( | struct set * | s | ) |

A set_size(s) + 1 array of the current elements in the set in a random order.

The array is NULL-terminated. Caller should free the array with set_free_values_array.

Parameters

  s | A pointer to a set.

Returns
  An array of pointers terminated with NULL. NULL if there are no elements in the set.

## set_free_values_array()

void set_free_values_array | ( | void ** | values | ) |

Free an array returned by set_values_array.

Parameters

  values | An array returned by set_values_array.