burkey.co /docs/libflint/set
index set
~/docs/libflint/set.md
libflint

Set

libflint·Data Structures

A collection of unique void * values, with membership linear in the size of the set. Hashed membership is hashset.

Usage#

Initialize a caller-owned Set with an equality callback. match returns 0 when two elements are equal. This example passes NULL for the destructor because the payloads are stack allocated.

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

Set set;
int value = 1;
int duplicate = 1;
void *removed;
if (set_init(&set, int_match, NULL) == 0) {
    if (set_insert(&set, &value) == 0 && set_insert(&set, &duplicate) == 1) {
        removed = &duplicate;
        if (set_remove(&set, &removed) == 0) {
            /* removed == &value */
        }
    }
    set_destroy(&set);
}

set_destroy frees the nodes and calls the destructor on remaining payloads. It does not free the Set. Payloads are not copied. Do not change a stored value in a way that affects match, and do not free a payload while it is in the set unless set_remove has returned it or the destructor is NULL.

Structs#

Set#

typedef struct {
    List impl;
} Set;

impl is the list storage. Read the length with set_size. An insert through the list API bypasses uniqueness.

Functions#

set_init#

Initializes a caller-owned Set. match is required. It returns 0 when two elements are equal, the same convention as strcmp. Any other value means not equal. The sign is ignored. Compare with ==, not subtraction, so signed overflow is not an issue. destroy is optional and runs only from set_destroy, on payloads still in the set. Returns 0 on success. Returns -1 if set or match is NULL, and does not write the handle. Do not initialize a live set.

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

set_destroy#

Frees the nodes and calls destroy on each remaining payload when the callback is non-NULL. Zeros the list inside the handle. Does not free the handle. A NULL set is a no-op. A second destroy on a destroyed set is a no-op.

void set_destroy(Set *set);

set_insert#

Stores data when no member compares equal. The pointee is not copied. Returns 0 on insertion, 1 when match reports a duplicate, and -1 if set is NULL or the node allocation fails. A duplicate or a failed insert leaves the set unchanged and leaves the payload with the caller.

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

set_remove#

Removes the member that matches *data. On success, *data is the stored pointer, which may differ from the key that was passed in, and the destructor is not called. Returns 0 on success. Returns -1 if set or data is NULL or if no member matches. On failure, *data is unchanged when data is non-NULL.

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

set_union / set_intersection / set_difference#

Write into a destination the caller has initialized. dest must be empty, must use the same match pointer as a and b, and must have destroy == NULL. dest must not be a or b. Result members alias payloads in a and b. Do not destroy a or b while dest is in use. Returns 0 on success. Returns -1 when a precondition fails, and then dest is unchanged. If a node allocation fails, dest is emptied and left initialized. Union contains every element of a or b. Intersection contains elements present in both. Difference contains elements in a that are not in b.

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);

dest is a different set, initialized with the same match and a NULL destructor:

Set result;
if (set_init(&result, int_match, NULL) == 0) {
    if (set_union(&result, &a, &b) == 0) {
        /* result aliases payloads in a and b */
    }
    set_destroy(&result);
}

set_is_member#

Returns 1 if data matches a member, otherwise 0. A NULL set returns 0.

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

set_is_subset#

Returns 1 if every member of a is a member of b. An empty a is a subset when both pointers are non-NULL. Returns 0 if a or b is NULL, or if some member of a is missing from b.

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

set_is_equal#

Returns 1 if a and b have the same size and a is a subset of b. Returns 0 if either pointer is NULL or the membership differs.

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

Macros#

set_size#

Returns the number of elements in an initialized set. s must be non-NULL.

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