Set

The Ambiorix set is an abstract data type that can store unique values. More...

Data Structures
struct	_flag
	The flag structure. More...
struct	_set
	The set structure. More...

Typedefs
typedef struct _flag	amxc_flag_t
	The flag structure. More...

Functions
int	amxc_set_new (amxc_set_t **set, bool counted)
	Allocates a set. More...
void	amxc_set_delete (amxc_set_t **set)
	Frees a set. More...
int	amxc_set_init (amxc_set_t *const set, bool counted)
	Initializes a set. More...
void	amxc_set_clean (amxc_set_t *const set)
	Cleans a set. More...
amxc_set_t *	amxc_set_copy (const amxc_set_t *const set)
	Copies a set. More...
void	amxc_set_reset (amxc_set_t *set)
	Reset or empty a set, i.e. clear all flags. More...
int	amxc_set_parse (amxc_set_t *set, const char *str)
	Parses a space-separated string of flags and adds them to the set. More...
char *	amxc_set_to_string (const amxc_set_t *const set)
	Converts a set to a space-separated string of flags. More...
char *	amxc_set_to_string_sep (const amxc_set_t *const set, const char *sep)
	Converts a set to a separated string of flags. More...
void	amxc_set_add_flag (amxc_set_t *set, const char *flag)
	Adds a flag to a set, or increases the flag counter. More...
void	amxc_set_remove_flag (amxc_set_t *set, const char *flag)
	Removes a flag from a set or decreases the flag counter. More...
bool	amxc_set_has_flag (const amxc_set_t *const set, const char *flag)
	Check if a set contains a flag. More...
uint32_t	amxc_set_get_count (const amxc_set_t *const set, const char *flag)
	Get a flag counter. More...
void	amxc_set_union (amxc_set_t *const set, const amxc_set_t *const operand)
	Joins two sets. More...
void	amxc_set_intersect (amxc_set_t *const set, const amxc_set_t *const operand)
	Intersect a set with another set. More...
void	amxc_set_subtract (amxc_set_t *const set, const amxc_set_t *const operand)
	Subtract a set from another set. More...
bool	amxc_set_is_equal (const amxc_set_t *const set1, const amxc_set_t *const set2)
	Compare two sets. More...
void	amxc_set_alert_cb (amxc_set_t *set, amxc_set_alert_t handler, void *priv)
	Install a set alert callback function. More...
void	amxc_set_symmetric_difference (amxc_set_t *const set, const amxc_set_t *const operand)
	Calculates the symmetric difference of two sets. More...

Detailed Description

The Ambiorix set is an abstract data type that can store unique values.

A set is an abstract data type that can store unique values, without any particular order. It is a computer implementation of the mathematical concept of a finite set. Unlike most other collection types, rather than retrieving a specific element from a set, one typically tests a value for membership in a set.

Typedef Documentation

amxc_flag_t

typedef struct _flag amxc_flag_t

The flag structure.

Flags can be added to a set.

Function Documentation

amxc_set_add_flag()

void amxc_set_add_flag	(	amxc_set_t *	set,
		const char *	flag
	)

Adds a flag to a set, or increases the flag counter.

Adds a flag to a set if it does not contain it already. If the set already contains the flag, increase its counter if the flag set is a counted set or do nothing at all for normal flag sets.

Parameters

set	The flag set on which a flag needs to be added.
flag	The flag to add.

Definition at line 305 of file amxc_set.c.

                                                          {
    when_null(set, exit);
    when_str_empty(flag, exit);
 
    amxc_set_flag_add(set, flag, 0, 1);
 
exit:
    return;
}

amxc_set_alert_cb()

void amxc_set_alert_cb	(	amxc_set_t *	set,
		amxc_set_alert_t	handler,
		void *	priv
	)

Install a set alert callback function.

For normal sets, this handler is called every time a flag is added or removed from the set.

For counted sets, this handler is called only whenever a flag is really added to or removed from the flag set, i.e. not when setting or clearing a flag only causes a flag counter to be incremented or decremented.

Parameters

set	The set on which an alert handler needs to be installed.
handler	The callback function to be called whenever a flag is set or cleared.
priv	A void pointer to be passed to the callback function.

Definition at line 453 of file amxc_set.c.

                                                                              {
    when_null(set, exit);
 
    set->alert_handler = handler;
    set->priv = priv;
 
exit:
    return;
}

amxc_set_clean()

void amxc_set_clean

(

amxc_set_t *const

set

)

Cleans a set.

clean-up a set, which was previously initialized with amxc_set_init.

Parameters

set	a pointer to an amxc_set_t structure

Definition at line 177 of file amxc_set.c.

                                           {
    when_null(set, exit);
 
    amxc_llist_clean(&set->list, amxc_set_flag_free);
    set->count = 0;
 
exit:
    return;
}

amxc_set_copy()

amxc_set_t* amxc_set_copy

(

const amxc_set_t *const

set

)

Copies a set.

Allocates a new set and copies the flags of the given set into this new set. The set alert handler and private data are not copied.

Note

The allocated memory must be freed when not used anymore, use amxc_set_delete to free the memory.

Parameters

set	a pointer to an amxc_set_t structure

Returns

A pointer to the newly allocated amxc_set_t structure if the copy succeeded, NULL otherwise.

Definition at line 187 of file amxc_set.c.

                                                       {
    amxc_set_t* copy = NULL;
 
    when_null(set, exit);
    when_failed(amxc_set_new(&copy, set->counted), exit);
 
    amxc_set_union(copy, set);
 
exit:
    return copy;
}

amxc_set_delete()

void amxc_set_delete

(

amxc_set_t **

set

)

Frees a set.

Releases any allocated memory for the flag set.

Parameters

set	The set to destroy. When this function returns, the pointer is set to NULL.

Definition at line 151 of file amxc_set.c.

                                       {
    when_null(set, exit);
 
    amxc_set_clean(*set);
    free(*set);
    *set = NULL;
 
exit:
    return;
}

amxc_set_get_count()

uint32_t amxc_set_get_count	(	const amxc_set_t *const	set,
		const char *	flag
	)

Get a flag counter.

Get the counter of a specific flag if flag is non-NULL or the global flag set counter if flag is NULL. The global counter is the sum of all flag counters. For counted sets, the counter of a flag is the number of times the flag was set. For normal flag sets, the counter equals 1 if the flag is set.

Parameters

set	The set for which a counter needs to be returned. NULL is considered to be the empty flag set.
flag	The flag to count. If it equals NULL, the global flag set counter is returned.

Returns

A flag counter or the flag set's global counter.

Definition at line 349 of file amxc_set.c.

                                                                           {
    uint32_t retval = 0;
 
    when_null(set, exit);
 
    if((flag != NULL) && (*flag != 0)) {
        amxc_flag_t* f = amxc_set_flag_find(set, flag);
        retval = f != NULL ? f->count : 0;
    } else {
        return set->count;
    }
 
exit:
    return retval;
}

amxc_set_has_flag()

bool amxc_set_has_flag	(	const amxc_set_t *const	set,
		const char *	flag
	)

Check if a set contains a flag.

Parameters

set	The set on which the flag needs to be checked. NULL is considered to be the empty flag set.
flag	The flag to check.

Returns

True if and only if the flag is set.

Definition at line 337 of file amxc_set.c.

                                                                      {
    bool retval = false;
 
    when_null(set, exit);
    when_str_empty(flag, exit);
 
    retval = amxc_set_flag_find(set, flag) ? true : false;
 
exit:
    return retval;
}

amxc_set_init()

int amxc_set_init	(	amxc_set_t *const	set,
		bool	counted
	)

Initializes a set.

Initializes a set that is declared on the stack. When the set is not needed anymore use amxc_set_clean to clean it up.

Parameters

set

a pointer to an amxc_set_t structure

counted

If set to true, the initialized set will keep a counter for each flag. Each time a specific flag is set, the counter is incremented and when the flag is cleared, the counter is decremented. Only when the counter reaches zero, the flag is really removed from the flag set. If set to false, the flag set will have default behaviour, i.e. when clearing a flag, it is removed immediately no matter how many times it has been set.

Returns

-1 if an error occured. 0 on success

Definition at line 162 of file amxc_set.c.

                                                       {
    int retval = -1;
 
    when_null(set, exit);
    amxc_llist_init(&set->list);
    set->alert_handler = NULL;
    set->counted = counted;
    set->count = 0;
    set->priv = NULL;
    retval = 0;
 
exit:
    return retval;
}

amxc_set_intersect()

void amxc_set_intersect	(	amxc_set_t *const	set,
		const amxc_set_t *const	operand
	)

Intersect a set with another set.

All flags that are set in the set referenced by set, but not in the set referenced by operand, are removed from set. Additionally, for counted sets, the counter of each flag of set will be set to the minimum of itself and the counter of the corresponding flag in operand.

Parameters

set	Left hand operand of the intersect operator, as well as the target to store the result into.
operand	Right hand operand of the intersect operator. NULL is considered to be the empty set.

Definition at line 384 of file amxc_set.c.

                                                                                {
    when_null(set, exit);
 
    if(operand == NULL) {
        amxc_set_reset(set);
        goto exit;
    }
 
    amxc_llist_for_each(it, &set->list) {
        amxc_flag_t* f = amxc_container_of(it, amxc_flag_t, it);
        amxc_flag_t* fo = amxc_set_flag_find(operand, f->flag);
 
        if(fo == NULL) {
            amxc_set_flag_delete(set, &f->it);
        } else if(set->counted && (fo->count < f->count)) {
            set->count += fo->count - f->count;
            f->count = fo->count;
        }
    }
 
exit:
    return;
}

amxc_set_is_equal()

bool amxc_set_is_equal	(	const amxc_set_t *const	set1,
		const amxc_set_t *const	set2
	)

Compare two sets.

Normal sets are considered to be equal if they contain the exact same set of flags. For counted sets, the flag counters have to match as well in order to be considered as equal.

Parameters

set1	Left hand operand of the equals operator. NULL is considered to be the empty set.
set2	Right hand operand of the equals operator. NULL is considered to be the empty set.

Returns

True if and only if set1 and set2 are equal.

Definition at line 430 of file amxc_set.c.

                                                     {
    if(set1 != NULL) {
        amxc_llist_iterate(it, &set1->list) {
            amxc_flag_t* f = amxc_container_of(it, amxc_flag_t, it);
            if(amxc_set_get_count(set2, f->flag) != f->count) {
                return false;
            }
        }
    }
 
    if(set2 != NULL) {
        amxc_llist_iterate(it, &set2->list) {
            amxc_flag_t* f = amxc_container_of(it, amxc_flag_t, it);
            if(amxc_set_get_count(set1, f->flag) != f->count) {
                return false;
            }
        }
    }
 
    return true;
}

amxc_set_new()

int amxc_set_new	(	amxc_set_t **	set,
		bool	counted
	)

Allocates a set.

Allocates and initializes memory to store a set. This function allocates memory from the heap, if a set is on the stack, it can be initialized using function amxc_set_init

Note

The allocated memory must be freed when not used anymore, use amxc_set_delete to free the memory

Parameters

set

a pointer to the location where the pointer to the new set can be stored

counted

If set to true, the created set will keep a counter for each flag. Each time a specific flag is set, the counter is incremented and when the flag is cleared, the counter is decremented. Only when the counter reaches zero, the flag is really removed from the flag set. If set to false, the flag set will have default behaviour, i.e. when clearing a flag, it is removed immediately no matter how many times it has been set.

Returns

-1 if an error occured. 0 on success

Definition at line 138 of file amxc_set.c.

                                                 {
    int retval = -1;
 
    when_null(set, exit);
 
    *set = (amxc_set_t*) calloc(1, sizeof(amxc_set_t));
    when_null(*set, exit);
    retval = amxc_set_init(*set, counted);
 
exit:
    return retval;
}

amxc_set_parse()

int amxc_set_parse	(	amxc_set_t *	set,
		const char *	str
	)

Parses a space-separated string of flags and adds them to the set.

This function will iterate over the given string, uses space characters as delimiter (uses function isspace). Multiple consecutive spaces are considered as one single space.

When the set is a counted set, a flag can be followed by a : sign and a number, that number is used as the initial count value. If the set is not a counted set, the number is ignored.

The : sign can not be used in flag names.

Parameters

set	The flag set to store the parsed flags into.
str	The string that holds the space separated string of flags.

Returns

0 if the string was parsed successfully, any other value otherwise.

Definition at line 210 of file amxc_set.c.

                                                     {
    int retval = -1;
    amxc_set_t newset;
 
    when_null(set, exit);
    amxc_set_init(&newset, set->counted);
 
    if((str != NULL) && (*str != 0)) {
        const char* strptr = str;
        char* newstr = NULL;
        int count = 0;
        do {
            if(!((*str == '\0') || (isspace(*str) != 0) || (*str == ':'))) {
                continue;
            }
            if(str > strptr) {
                if(*str == ':') {
                    count = strtol(str + 1, &newstr, 0);
                    if((*newstr != '\0') && (isspace(*newstr) == 0)) {
                        goto exit_clean;
                    }
                    if(count > 0) {
                        amxc_set_flag_add(&newset, strptr, str - strptr, set->counted ? count : 1);
                    }
                    str = newstr;
                } else {
                    amxc_set_flag_add(&newset, strptr, str - strptr, 1);
                }
            }
            strptr = str + 1;
        } while(*str++);
    }
    // intersect + union instead of simply overwrite to avoid that unchanged flags are cleared and set again
    amxc_set_intersect(set, &newset);
    amxc_set_union(set, &newset);
    if(set->counted) {
        set->count = 0;
        amxc_llist_iterate(it, &set->list) {
            amxc_flag_t* flag = amxc_container_of(it, amxc_flag_t, it);
            amxc_flag_t* new_flag = amxc_set_flag_find(&newset, flag->flag);
            if((flag != NULL) && (new_flag != NULL)) {
                flag->count = new_flag->count;
                set->count += flag->count;
            }
        }
    }
    retval = 0;
 
exit_clean:
    amxc_set_clean(&newset);
exit:
    return retval;
}

amxc_set_remove_flag()

void amxc_set_remove_flag	(	amxc_set_t *	set,
		const char *	flag
	)

Removes a flag from a set or decreases the flag counter.

If the flag set contains the flag, decrease its counter if it is a counted set. If it is a normal flag set, or the flag's counter reaches zero, removes the flag from the set. If the set does not contain the flag, doesn't do anything at all.

Parameters

set	The set on which a flag needs to be removed.
flag	The flag to clear.

Definition at line 315 of file amxc_set.c.

                                                             {
    amxc_flag_t* f = NULL;
 
    when_null(set, exit);
    when_str_empty(flag, exit);
 
    f = amxc_set_flag_find(set, flag);
    if(f == NULL) {
        goto exit;
    }
 
    if(set->counted && (f->count > 1)) {
        f->count--;
        set->count--;
    } else {
        amxc_set_flag_delete(set, &f->it);
    }
 
exit:
    return;
}

amxc_set_reset()

void amxc_set_reset

(

amxc_set_t *

set

)

Reset or empty a set, i.e. clear all flags.

Parameters

set	The set to reset.

Definition at line 199 of file amxc_set.c.

                                     {
    when_null(set, exit);
 
    amxc_llist_for_each(it, &set->list) {
        amxc_set_flag_delete(set, it);
    }
 
exit:
    return;
}

amxc_set_subtract()

void amxc_set_subtract	(	amxc_set_t *const	set,
		const amxc_set_t *const	operand
	)

Subtract a set from another set.

For normal sets, all flags that are set in both the set referenced by set and the set referenced by operand, are removed from set.

For counted sets, the counter of each flag of set will be decremented by the counter of the corresponding flag in operand. If this results in a counter equal to or less than zero, the flag is removed from set.

Parameters

set	Left hand operand of the subtract operator, as well as the target to store the result into.
operand	Right hand operand of the subtract operator. NULL is considered to be the empty set.

Definition at line 408 of file amxc_set.c.

                                                                               {
    when_null(set, exit);
    when_null(operand, exit);
 
    amxc_llist_iterate(it, &operand->list) {
        amxc_flag_t* fo = amxc_container_of(it, amxc_flag_t, it);
        amxc_flag_t* f = amxc_set_flag_find(set, fo->flag);
        if(f == NULL) {
            continue;
        }
        if(set->counted && (f->count > fo->count)) {
            set->count -= fo->count;
            f->count -= fo->count;
        } else {
            amxc_set_flag_delete(set, &f->it);
        }
    }
 
exit:
    return;
}

amxc_set_symmetric_difference()

void amxc_set_symmetric_difference	(	amxc_set_t *const	set,
		const amxc_set_t *const	operand
	)

Calculates the symmetric difference of two sets.

The symmetric difference of two sets is the set of elements which are in either of the sets, but not in both. E.g. the symmetric difference of the sets {1,2,3} and {3,4} is {1,2,4}.

Parameters

set	Left hand operand of the operator, as well as the target to store the result into.
operand	Right hand operand of the operator. NULL is considered to be the empty flag set.

Definition at line 463 of file amxc_set.c.

                                                                    {
    amxc_set_t* tmp = NULL;
 
    when_null(set, exit);
    when_null(operand, exit);
 
    tmp = amxc_set_copy(operand);
    when_null(tmp, exit);
 
    amxc_set_subtract(tmp, set);
    amxc_set_subtract(set, operand);
    amxc_set_union(set, tmp);
 
    amxc_set_delete(&tmp);
exit:
    return;
}

amxc_set_to_string()

char* amxc_set_to_string

(

const amxc_set_t *const

set

)

Converts a set to a space-separated string of flags.

Parameters

set	The flag set to convert.

Returns

A string holding the space-separated string of flags. It's allocated on the heap and needs to be freed by the caller with free(). A NULL pointer is returned if the set is NULL, empty or if memory allocation failed.

Definition at line 301 of file amxc_set.c.

                                                      {
    return amxc_set_to_string_sep(set, " ");
}

amxc_set_to_string_sep()

char* amxc_set_to_string_sep	(	const amxc_set_t *const	set,
		const char *	sep
	)

Converts a set to a separated string of flags.

Parameters

set	The flag set to convert.
sep	The separation string.

Returns

A string holding the separated string of flags. It's allocated on the heap and needs to be freed by the caller with free(). A NULL pointer is returned if the set is NULL, empty or if memory allocation failed.

Definition at line 264 of file amxc_set.c.

                                                                           {
    int n = 0;
    char* buf = NULL;
    char* bufptr = NULL;
    char countbuf[16];
    int started = 0;
 
    when_null(set, exit);
    when_null(sep, exit);
 
    amxc_llist_iterate(it, &set->list) {
        amxc_flag_t* f = amxc_container_of(it, amxc_flag_t, it);
        n += strlen(f->flag) + started;
        if((f->count != 1) && set->counted) {
            n += sprintf(countbuf, ":%d", f->count);
        }
        started = 1;
    }
    buf = (char*) calloc(n + 1, 1);
    bufptr = buf;
    when_null(buf, exit);
 
    started = 0;
    amxc_llist_iterate(it, &set->list) {
        amxc_flag_t* f = amxc_container_of(it, amxc_flag_t, it);
        if((f->count != 1) && set->counted) {
            bufptr += sprintf(bufptr, "%s%s:%d", started ? sep : "", f->flag, f->count);
        } else {
            bufptr += sprintf(bufptr, "%s%s", started ? sep : "", f->flag);
        }
        started = 1;
    }
 
exit:
    return buf;
}

amxc_set_union()

void amxc_set_union	(	amxc_set_t *const	set,
		const amxc_set_t *const	operand
	)

Joins two sets.

All flags that are set in the set referenced by operand, but are not in the flag set referenced by set, are added to set. Additionally, for counted sets, the counter of each flag of set will be incremented by the counter of the corresponding flag in operand.

Parameters

set	Left hand operand of the union operator, as well as the target to store the result into.
operand	Right hand operand of the union operator. NULL is considered to be the empty flag set.

Definition at line 365 of file amxc_set.c.

                                                                            {
    when_null(set, exit);
    when_null(operand, exit);
 
    amxc_llist_iterate(it, &operand->list) {
        amxc_flag_t* fo = amxc_container_of(it, amxc_flag_t, it);
        amxc_flag_t* f = amxc_set_flag_find(set, fo->flag);
        if(f == NULL) {
            amxc_set_flag_add(set, fo->flag, 0, set->counted ? fo->count : 1);
        } else if(set->counted) {
            set->count += fo->count;
            f->count += fo->count;
        }
    }
 
exit:
    return;
}