idset_create(3)

SYNOPSIS

#include <flux/idset.h>

struct idset *idset_create (size_t size, int flags);

void idset_destroy (struct idset *idset);

struct idset *idset_copy (const struct idset *idset);

int idset_set (struct idset *idset, unsigned int id);

int idset_range_set (struct idset *idset,
                     unsigned int lo,
                     unsigned int hi);

int idset_clear (struct idset *idset, unsigned int id);

int idset_range_clear (struct idset *idset,
                       unsigned int lo,
                       unsigned int hi);

bool idset_test (const struct idset *idset, unsigned int id);

unsigned int idset_first (const struct idset *idset);

unsigned int idset_next (const struct idset *idset,
                         unsigned int id);

unsigned int idset_last (const struct idset *idset);

unsigned int idset_prev (const struct idset *idset,
                         unsigned int id);

size_t idset_count (const struct idset *idset);

bool idset_empty (const struct idset *idset);

size_t idset_universe_size (const struct idset *idset);

Link with -lflux-idset.

DESCRIPTION

An idset is a set of numerically sorted, non-negative integers. It is internally represented as a van Embde Boas (or vEB) tree. Functionally it behaves like a bitmap, and has space efficiency comparable to a bitmap, but performs test, set, clear, next, and prev operations in \(O(log(m))\) time (where \(2^m\) is the universe size); and performs first and last operations in constant time.

idset_create() creates an idset. size specifies the universe size, which is the maximum id it can hold, plus one. The universe size is fixed unless flags specify otherwise (see FLAGS below).

idset_destroy() destroys an idset.

idset_copy() copies an idset.

idset_set() and idset_clear() set or clear id.

idset_range_set() and idset_range_clear() set or clear an inclusive range of ids, from lo to hi.

idset_test() returns true if id is set, false if not.

idset_first() and idset_next() can be used to iterate forward over ids in the set, returning IDSET_INVALID_ID at the end.

idset_last() and idset_prev() can be used to iterate backward over ids in the set, returning IDSET_INVALID_ID at the end.

idset_count() returns the number of ids in the set. A running count is kept so this function runs in constant time.

idset_empty() returns true if the set is empty. This function runs in constant time.

idset_universe_size() returns the current set universe size. This is normally the size specified at creation, or a multiple of it if IDSET_FLAG_AUTOGROW was specified.

FLAGS

The following flags are valid for idset_create():

IDSET_FLAG_AUTOGROW: The idset will grow to accommodate any id that is the target of a set, or if IDSET_FLAG_INITFULL is set, a clear operation. The universe size is doubled until until the new id can be accessed. Resizing is a costly operation that requires all ids in the old tree to be inserted into the new one.
IDSET_FLAG_INITFULL: The idset is created full instead of empty. If specified with IDSET_FLAG_AUTOGROW, new portions that are added are also filled.
IDSET_FLAG_COUNT_LAZY: The running count is not maintained and idset_count() uses a slower iteration method. Not maintaining the count makes set/clear operations slightly faster, an acceptable trade-off for some use cases. This flag does not affect idset_empty().

RETURN VALUE

idset_create() and idset_copy() return an idset on success which must be freed with idset_destroy(). On error, NULL is returned with errno set.

idset_first(), idset_next(), idset_prev(), and idset_last() return an id, or IDSET_INVALID_ID if no id is available.

idset_count() and idset_universe_size() return 0 if the argument is invalid.

idset_empty() returns true for the empty set or invalid arguments.

Other functions return 0 on success, or -1 on error with errno set.

ERRORS

EINVAL: One or more arguments were invalid.
ENOMEM: Out of memory.

RESOURCES

Flux: http://flux-framework.org

Flux RFC: https://flux-framework.readthedocs.io/projects/flux-rfc

Issue Tracker: https://github.com/flux-framework/flux-core/issues

FLUX RFC

22/Idset String Representation