#include "vl_linear_pool.h"
#include "vl_compare.h"

Include dependency graph for vl_set.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	vl_set
	An ordered set. More...

Macros
#define	VL_SET_ITER_INVALID VL_STRUCTURE_INDEX_MAX

#define	VL_SET_FOREACH(set, trackVar) for(vl_set_iter trackVar = vlSetFront(set); (trackVar) != VL_SET_ITER_INVALID; (trackVar) = vlSetNext(set, trackVar))

#define	VL_SET_FOREACH_REVERSE(set, trackVar) for(vl_set_iter trackVar = vlSetBack(set); (trackVar) != VL_SET_ITER_INVALID; (trackVar) = vlSetPrev(set, trackVar))

#define	vlSetSize(set) (size_t)((set)->nodePool.totalTaken)
	Returns the size of the specified set.

Typedefs
typedef vl_linearpool_idx	vl_set_iter

Functions
void	vlSetInit (vl_set *set, vl_memsize_t elementSize, vl_compare_function compFunc)

void	vlSetFree (vl_set *set)

vl_set *	vlSetNew (vl_memsize_t elementSize, vl_compare_function compFunc)

void	vlSetDelete (vl_set *set)

vl_set_iter	vlSetFront (vl_set *set)

vl_set_iter	vlSetBack (vl_set *set)

vl_set_iter	vlSetInsert (vl_set set, const void elem)

vl_transient *	vlSetSample (vl_set *set, vl_set_iter iter)

vl_set_iter	vlSetNext (vl_set *set, vl_set_iter iter)

vl_set_iter	vlSetPrev (vl_set *set, vl_set_iter iter)

void	vlSetRemove (vl_set *set, vl_set_iter iter)

void	vlSetRemoveElem (vl_set set, const void elem)

void	vlSetClear (vl_set *set)

vl_set *	vlSetClone (const vl_set src, vl_set dest)
	Clones the specified set to another.

int	vlSetCopy (vl_set src, vl_set_iter begin, vl_set_iter end, vl_set dest)
	Copies a range of elements from one set to another.

vl_set_iter	vlSetFind (vl_set set, const void elem)

vl_set *	vlSetUnion (vl_set a, vl_set b, vl_set *dest)
	Computes the union between sets A and B, stored in set dest.

vl_set *	vlSetIntersection (vl_set a, vl_set b, vl_set *dest)
	Computes the intersection between sets A and B, stored in set dest.

vl_set *	vlSetDifference (vl_set a, vl_set b, vl_set *dest)
	Compute the difference between sets A and B, stored in set dest.

Data Structure Documentation

◆ vl_set

struct vl_set

An ordered set.

The vl_set structure represents an ordered, unique set of values sorted according to a supplied comparator. This is implemented using a red/black binary tree, a separate self-balancing structure which guarantees worse-case search, removal, and insertion complexity of O(log(n)).

This is another abstraction of a vl_linearpool instance, which maintains an underlying buffer containing all data for the structure.

Elements of the set are sorted according to a key, but can also hold supplementary data for each element that is stored in the same block of memory.

Collaboration diagram for vl_set:

Data Fields
vl_compare_function	comparator
vl_memsize_t	elementSize
vl_linearpool	nodePool
vl_set_iter	root

Macro Definition Documentation

◆ VL_SET_FOREACH

#define VL_SET_FOREACH	(		set,
			trackVar ) for(vl_set_iter trackVar = vlSetFront(set); (trackVar) != VL_SET_ITER_INVALID; (trackVar) = vlSetNext(set, trackVar))

Convenience macro for forward iterating over the entirety of a set. Implements a for-loop code structure with some of the boilerplate hidden away.

Parameters

set	pointer
trackVar	name of the tracking variable used as the set iterator

◆ VL_SET_FOREACH_REVERSE

#define VL_SET_FOREACH_REVERSE	(		set,
			trackVar ) for(vl_set_iter trackVar = vlSetBack(set); (trackVar) != VL_SET_ITER_INVALID; (trackVar) = vlSetPrev(set, trackVar))

Convenience macro for reverse iterating over the entirety of a set. Implements a for-loop code structure with some of the boilerplate hidden away.

Parameters

set	pointer
trackVar	name of the tracking variable used as the set iterator

◆ VL_SET_ITER_INVALID

#define VL_SET_ITER_INVALID VL_STRUCTURE_INDEX_MAX

◆ vlSetSize

#define vlSetSize ( set ) (size_t)((set)->nodePool.totalTaken)

Returns the size of the specified set.

This macro looks at total taken from the internal node pool.

Parameters

set pointer

Returns: total number of elements in the set.

Typedef Documentation

◆ vl_set_iter

typedef vl_linearpool_idx vl_set_iter

Function Documentation

◆ vlSetBack()

vl_set_iter vlSetBack ( vl_set * set )

Returns an iterator to the last element in the set.

Parameters

set	set pointer

Complexity O(log(n)).

Returns: iterator of last element in the set.

Here is the caller graph for this function:

◆ vlSetClear()

void vlSetClear ( vl_set * set )

Clears the specified set. Does not modify buffer memory associated with the set, but rather resets some variables used to track state.

Parameters

set	pointer to set

Complexity O(1).

Here is the call graph for this function:

Here is the caller graph for this function:

◆ vlSetClone()

vl_set * vlSetClone	(	const vl_set *	src,
		vl_set *	dest )

Clones the specified set to another.

Clones the entirety of the src set to the dest set.

The 'src' set pointer must be non-null and initialized. The 'dest' set pointer may be null, but if it is not null it must be initialized.

If the 'dest' set pointer is null, a new list is created via vlSetNew. Otherwise, its element size is set to the source's and all of its existing data is replaced.

Parameters

src	pointer
dest	pointer

Returns: pointer to set that was copied to or created.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ vlSetCopy()

int vlSetCopy	(	vl_set *	src,
		vl_set_iter	begin,
		vl_set_iter	end,
		vl_set *	dest )

Copies a range of elements from one set to another.

Both the src set and the dest set must have equivalent element sizes, otherwise this is a no-op. Similarly, both sets must also have matching comparators.

This is an inclusive range, and as such, the elements referred to by the begin and end iterators are also copied to the target set.

The begin and end iterators are expected to be in logical iterative order, meaning that if iterating through the entire src set, begin would be found before end.

Parameters

src	source buffer pointer
begin	iterator to start the copy at, or VL_SET_ITER_INVALID for the beginning of the list.
end	iterator to end the copy after, or VL_SET_ITER_INVALID for the end of the list.
dest	destination buffer pointer

Complexity of O(nlog(n)) log-linear.

Returns: number of elements copied

Here is the call graph for this function:

◆ vlSetDelete()

void vlSetDelete ( vl_set * set )

Deletes the specified set from the heap. Frees the underlying storage buffers for the specified set. Should only be used by sets initialized via vlSetNew.

Parameters

set	set pointer

See also: vlSetNew

Complexity O(1) constant.

Here is the call graph for this function:

◆ vlSetDifference()

vl_set * vlSetDifference	(	vl_set *	a,
		vl_set *	b,
		vl_set *	dest )

Compute the difference between sets A and B, stored in set dest.

Differences consist of all elements that reside in either A and B, but NOT elements that exist in both A and B. Consider this equivalent to bitwise XOR.

This function has computational relevance to set theory.

Both A and B sets must have identical element sizes and comparators. Otherwise, this is a no-op and will return null.

The 'dest' set pointer may be null, but if it is not null it must be initialized. If the 'dest' set pointer is null, a new list is created via vlListNew.

The set notation for this operation is: A - B

Parameters

a	first set
b	second set
dest	destination set

Complexity of O(nlog(n)) log-linear.

Returns: pointer to set that was copied to or created, or NULL on mismatched sets.

Here is the call graph for this function:

◆ vlSetFind()

vl_set_iter vlSetFind	(	vl_set *	set,
		const void *	elem )

Searches for the specified element in the set. Returns VL_SET_ITER_INVALID if element is not found.

Parameters

set	pointer to set
elem	pointer to element

Complexity O(log(n)).

Returns: iterator of found element, or VL_SET_ITER_INVALID.

Here is the caller graph for this function:

◆ vlSetFree()

void vlSetFree ( vl_set * set )

Frees the underlying storage buffers for the specified set. Should only be used on sets initialized via vlSetInit.

Parameters

set	set pointer

See also: vlSetInit

Complexity O(1) constant.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ vlSetFront()

vl_set_iter vlSetFront ( vl_set * set )

Returns an iterator to the last element in the set.

Parameters

set	set pointer

Complexity O(log(n)).

Returns: iterator of last element in the set.

Here is the caller graph for this function:

◆ vlSetInit()

void vlSetInit	(	vl_set *	set,
		vl_memsize_t	elementSize,
		vl_compare_function	compFunc )

Initializes the specified set pointer to hold elements of the specified size. This set should be freed via vlSetFree.

Parameters

set	set pointer
elementSize	element size, in bytes.
compFunc	comparator function; 0 = same, >0 = greater, <0 = lesser.

See also: vlSetFree

Complexity O(1) constant.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ vlSetInsert()

vl_set_iter vlSetInsert	(	vl_set *	set,
		const void *	elem )

Inserts the specified element into the set. If the element already exists in the set, the existing iterator is returned. Insertion does not invalidate existing iterators in the set.

Parameters

set	set pointer
elem	element pointer

Complexity of O(log(n)).

Returns: iterator to inserted or existing element

Here is the call graph for this function:

Here is the caller graph for this function:

◆ vlSetIntersection()

vl_set * vlSetIntersection	(	vl_set *	a,
		vl_set *	b,
		vl_set *	dest )

Computes the intersection between sets A and B, stored in set dest.

Intersections consist of all elements that reside in both A and B, and ONLY elements that exist in both A and B. Consider this equivalent to bitwise AND.

This function has computational relevance to set theory.

Both A and B sets must have identical element sizes and comparators. Otherwise, this is a no-op and will return null.

The 'dest' set pointer may be null, but if it is not null it must be initialized. If the 'dest' set pointer is null, a new list is created via vlListNew.

The set notation for this operation is: A n B

Parameters

a	first set
b	second set
dest	destination set

Complexity of O(nlog(n)) log-linear.

Returns: pointer to set that was copied to or created, or NULL on mismatched sets.

Here is the call graph for this function:

◆ vlSetNew()

vl_set * vlSetNew	(	vl_memsize_t	elementSize,
		vl_compare_function	compFunc )

Allocates a new set on the heap. Initializes the specified set pointer to hold elements of the specified size. This set should be freed via vlSetDelete.

Parameters

elementSize	element size, in bytes
compFunc	comparator function; 0 = same, >0 = greater, <0 = lesser.

Returns: set pointer

See also: vlSetDelete

Complexity O(1) constant.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ vlSetNext()

vl_set_iter vlSetNext	(	vl_set *	set,
		vl_set_iter	iter )

Returns the iterator to the previous element in the set relative to the specified iterator, as if the set tree is being iterated by inorder traversal. If there is no next element, (e.g, vlSetNext(&set, vlSetBack(&set)), this will return VL_SET_ITER_INVALID.

Parameters

set	set pointer
iter	set iterator

Complexity O(log(n)).

Returns: iterator to next element relative to input iter.

Here is the caller graph for this function:

◆ vlSetPrev()

vl_set_iter vlSetPrev	(	vl_set *	set,
		vl_set_iter	iter )

Returns the iterator to the previous element in the set relative to the specified iterator, as if the set tree is being iterated by reverse inorder traversal. If there is no previous element, (e.g, vlSetPrev(&set, vlSetFront(&set)), this will return VL_SET_ITER_INVALID.

Parameters

set	set pointer
iter	set iterator

Complexity O(log(n)).

Returns: iterator to previous element relative to input iter.

◆ vlSetRemove()

void vlSetRemove	(	vl_set *	set,
		vl_set_iter	iter )

Removes the specified iterator from the set. Undefined behavior if element does not exist in the set. Removal of an element does not invalidate other iterators in the set.

Parameters

set	pointer to set
iter	set iterator

Complexity O(log(n)).

Here is the call graph for this function:

Here is the caller graph for this function:

◆ vlSetRemoveElem()

void vlSetRemoveElem	(	vl_set *	set,
		const void *	elem )

Removes the specified element from the set. Undefined behavior if element does not exist in the set. Removal of an element does not invalidate other iterators in the set.

Parameters

set	pointer to set
elem	pointer to element.

Complexity O(log(n)).

Here is the call graph for this function:

◆ vlSetSample()

vl_transient * vlSetSample	(	vl_set *	set,
		vl_set_iter	iter )

Returns the pointer to the element at the specified iterator in the set. Undefined behavior occurs when iterator does not exist in the set, or is VL_SET_ITER_INVALID.

The pointer is returned as non-const based on the trust that the key by which the set is ordered is not modified. Any supplemental information in the element may be freely modified.

Parameters

set	set pointer
iter	element iterator

Complexity O(1) constant.

Returns: pointer to element data

Here is the caller graph for this function:

◆ vlSetUnion()

vl_set * vlSetUnion	(	vl_set *	a,
		vl_set *	b,
		vl_set *	dest )

Computes the union between sets A and B, stored in set dest.

Unions consist of all elements that reside in either A and B. Consider this equivalent to bitwise OR.

This function has computational relevance to set theory.

Both A and B sets must have identical element sizes and comparators. Otherwise, this is a no-op and will return null.

The 'dest' set pointer may be null, but if it is not null it must be initialized. If the 'dest' set pointer is null, a new list is created via vlSetNew.

The set notation for this operation is: A u B

Parameters

a	first set
b	second set
dest	destination set

Complexity of O(nlog(n)) log-linear.

Returns: pointer to set that was copied to or created, or NULL on mismatched sets.

Here is the call graph for this function:

Data Structures

Macros

Typedefs

Functions

Data Structure Documentation

◆ vl_set

Macro Definition Documentation

◆ VL_SET_FOREACH

◆ VL_SET_FOREACH_REVERSE

◆ VL_SET_ITER_INVALID

◆ vlSetSize

Typedef Documentation

◆ vl_set_iter

Function Documentation

◆ vlSetBack()

◆ vlSetClear()

◆ vlSetClone()

◆ vlSetCopy()

◆ vlSetDelete()

◆ vlSetDifference()

◆ vlSetFind()

◆ vlSetFree()

◆ vlSetFront()

◆ vlSetInit()

◆ vlSetInsert()

◆ vlSetIntersection()

◆ vlSetNew()

◆ vlSetNext()

◆ vlSetPrev()

◆ vlSetRemove()

◆ vlSetRemoveElem()

◆ vlSetSample()

◆ vlSetUnion()