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