Set

A small collection of unique void * values. Membership is linear in the size of the set. Use the set functions to preserve uniqueness. For hashed membership, see hashset.

Usage

Initialize the set with an equality callback and an optional payload destructor. The equality callback returns 0 for equal values. This example passes NULL for the destructor because its payloads are stack allocated.

int int_match(const void *a, const void *b) {
    return *(const int *)a == *(const int *)b ? 0 : 1;
}

Set set;
if (set_init(&set, int_match, NULL) == 0) {
    int value = 1;
    int duplicate = 1;
    set_insert(&set, &value);
    set_insert(&set, &duplicate); /* Keeps value if the first insert succeeded. */
    set_destroy(&set);
}

set_destroy frees the nodes and calls the destructor on remaining payloads. It does not free the Set handle. Keep values unchanged in ways that affect equality while stored.

Structs

Set

typedef struct {
    List impl;
} Set;

match is required at set_init. It returns 0 if two elements are equal (the same convention as strcmp). Compare with ==, not subtraction, so signed overflow is not an issue.

Functions

set_init

Initializes the set. The user owns the Set handle. match is required; destroy is optional and is called on members only by set_destroy. Returns 0 on success, -1 if set or match is NULL.

int set_init(Set *set, int (*match)(const void *a, const void *b),
             void (*destroy)(void *data));

/* Usage */
int int_match(const void *a, const void *b) {
    return *(const int *)a == *(const int *)b ? 0 : 1;
}

Set set;
set_init(&set, int_match, NULL);

set_destroy

Destroys the nodes inside a Set and calls the deallocation function on the data if one was provided. Does not destroy the set itself, that is left up to the user.

void set_destroy(Set *set);

/* Usage */
set_destroy(&set);

set_insert

Inserts data into the set. If data is already a member (determined by the match function), the insertion is skipped and 1 is returned. Returns 0 on successful insertion, -1 on error. Duplicate and failed inserts leave the payload with the caller.

int set_insert(Set *set, const void *data);

/* Usage */
int a = 1;
int b = 1;
set_insert(&set, &a); /* returns 0, inserted */
set_insert(&set, &b); /* returns 1, duplicate skipped */

set_remove

Removes the element matching *data from the set. data is updated to point to the removed element's data so the user can manage its memory. The destructor is not called. Returns 0 on success, -1 if the element is not found or if data is NULL.

int set_remove(Set *set, void **data);

/* Usage */
int key = 1;
void *removed = &key;
set_remove(&set, &removed);

Algebra (borrowed)

set_union, set_intersection, and set_difference write into a destination you initialize. The destination must be empty, use the same match as a and b, and have destroy == NULL. Result members alias the payloads in a and b. Do not destroy a or b while the result is in use. dest cannot be a or b. Returns 0 on success, -1 on error. Allocation failure leaves the destination empty and initialized.

int set_union(Set *dest, const Set *a, const Set *b);
int set_intersection(Set *dest, const Set *a, const Set *b);
int set_difference(Set *dest, const Set *a, const Set *b);

/* Usage */
Set result;
set_init(&result, int_match, NULL);
set_union(&result, &set1, &set2);
/* use result, then: */
set_destroy(&result); /* nodes only; payloads still owned by set1/set2 */

Union contains every element from a or b. Intersection contains elements present in both. Difference is elements in a that are not in b.

set_is_member

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

int set_is_member(const Set *set, const void *data);

set_is_subset

Returns 1 if a is a subset of b (every element in a is also in b), 0 otherwise.

int set_is_subset(const Set *a, const Set *b);

set_is_equal

Returns 1 if sets a and b contain the same elements, 0 otherwise.

int set_is_equal(const Set *a, const Set *b);

Macros

set_size

Returns the number of elements in the set.

#define set_size(s) ((s)->impl.size)