set.h File Reference

#include <stddef.h>
#include "arena.h"

Data Structures
struct	Set
	Represents a set of unique keys. More...
struct	SetItem
	Represents a single item in a set. More...

Macros
#define	set_for_each(item, self)
	Iterate over all items in a set.

Functions
static Set	set_create (Arena *arena)
	Create a new set.
static bool	set_insert (Set *self, const void *key, long size)
	Insert a new item into a set.
static bool	set_remove (Set *self, const void *key, long size)
	Remove an item from a set.
static bool	set_find (const Set *self, const void *key, long size)
	Find an item of a set.
static Set	set_clone (const Set *self, Arena *arena)
	Create a clone of a set.
static SetItem *	set_items (const Set *self, Arena *arena)
	Retrieve an array of set items.
static Set	set_union (const Set *self, const Set *other, Arena *arena)
	Compute the union of two sets.
static Set	set_intersection (const Set *self, const Set *other, Arena *arena)
	Compute the intersection of two sets.
static Set	set_difference (const Set *self, const Set *other, Arena *arena)
	Compute the difference of two sets.
static Set	set_symmetric_difference (const Set *self, const Set *other, Arena *arena)
	Compute the symmetric difference of two sets.
static bool	set_is_subset (const Set *self, const Set *other)
	Check if one set is a subset of another.
static bool	set_is_superset (const Set *self, const Set *other)
	Check if one set is a superset of another.

Variables
static constexpr long	set_hash_shift = 2
	Number of hash bits to shift out.
static constexpr long	set_branch_select = 64 - set_hash_shift
	Bit mask to select branch.

Macro Definition Documentation

set_for_each

#define set_for_each	(		item,
			self
	)

Value:

    for (auto(item) = (self)->begin; item; (item) = (item)->next) \
        if ((item)->key.size)

Iterate over all items in a set.

Parameters

item	Current set item
self	Pointer to a set

Function Documentation

set_create()

static Set set_create ( Arena *  arena )

static

Create a new set.

Parameters

arena

Pointer to an arena allocator

Returns

New set instance

set_insert()

static bool set_insert ( Set *  self, const void *  key, long  size  )

static

Insert a new item into a set.

Parameters

self	Pointer to a set
key	Pointer to the key data
size	Size of the key data in bytes (optional)

Returns

true if the key is newly added, or false if it already exists

Note

If size == 0, key is assumed to be a null-terminated string

set_remove()

static bool set_remove ( Set *  self, const void *  key, long  size  )

static

Remove an item from a set.

Parameters

self	Pointer to a set
key	Pointer to the key data
size	Size of the key data in bytes (optional)

Returns

true if the key is successfully removed, or false if it is not found

Note

If size == 0, key is assumed to be a null-terminated string

set_find()

static bool set_find ( const Set *  self, const void *  key, long  size  )

static

Find an item of a set.

Parameters

self	Pointer to a set
key	Pointer to the key data
size	Size of the key data in bytes (optional)

Returns

true if the key exists, or false if it is not found

Note

If size == 0, key is assumed to be a null-terminated string

set_clone()

static Set set_clone ( const Set *  self, Arena *  arena  )

static

Create a clone of a set.

Parameters

self	Pointer to a set
arena	Pointer to an arena allocator (optional)

Returns

Cloned set instance

Note

If no arena allocator is passed, the arena allocator of the set is used

set_items()

static SetItem * set_items ( const Set *  self, Arena *  arena  )

static

Retrieve an array of set items.

Parameters

self	Pointer to a set
arena	Pointer to an arena allocator (optional)

Returns

Pointer to an array of items

Note

If no arena allocator is passed, the arena allocator of the set is used

set_union()

static Set set_union ( const Set *  self, const Set *  other, Arena *  arena  )

static

Compute the union of two sets.

Parameters

self	Pointer to a set
other	Pointer to another set
arena	Pointer to an arena allocator (optional)

Returns

New set containing all unique items from both sets

set_intersection()

static Set set_intersection ( const Set *  self, const Set *  other, Arena *  arena  )

static

Compute the intersection of two sets.

Parameters

self	Pointer to a set
other	Pointer to another set
arena	Pointer to an arena allocator (optional)

Returns

New set containing items common to both sets

set_difference()

static Set set_difference ( const Set *  self, const Set *  other, Arena *  arena  )

static

Compute the difference of two sets.

Parameters

self	Pointer to a set
other	Pointer to another set
arena	Pointer to an arena allocator (optional)

Returns

New set containing items in the first set but not in the second

set_symmetric_difference()

static Set set_symmetric_difference ( const Set *  self, const Set *  other, Arena *  arena  )

static

Compute the symmetric difference of two sets.

Parameters

self	Pointer to a set
other	Pointer to another set
arena	Pointer to an arena allocator (optional)

Returns

New set containing items that are in either of the sets but not in both

set_is_subset()

static bool set_is_subset ( const Set *  self, const Set *  other  )

static

Check if one set is a subset of another.

Parameters

self	Pointer to a set
other	Pointer to another set

Returns

true if all items in the first set are also in the second, or false otherwise

set_is_superset()

static bool set_is_superset ( const Set *  self, const Set *  other  )

static

Check if one set is a superset of another.

Parameters

self	Pointer to a set
other	Pointer to another set

Returns

true if all items in the second set are also in the first, or false otherwise