List

Data Structures
struct	M_list_callbacks

Typedefs
typedef struct M_list	M_list_t
typedef void *(*	M_list_duplicate_func) (const void *)
typedef void(*	M_list_free_func) (void *)

Enumerations
enum	M_list_flags_t {   M_LIST_NONE = 0 ,   M_LIST_SORTED = 1 << 0 ,   M_LIST_STABLE = 1 << 1 ,   M_LIST_STACK = 1 << 2 ,   M_LIST_SET_VAL = 1 << 3 ,   M_LIST_SET_PTR = 1 << 4 ,   M_LIST_NEVERSHRINK = 1 << 5 }
enum	M_list_match_type_t {   M_LIST_MATCH_VAL = 0 ,   M_LIST_MATCH_PTR = 1 << 0 ,   M_LIST_MATCH_ALL = 1 << 1 }

Functions
M_list_t *	M_list_create (const struct M_list_callbacks *callbacks, M_uint32 flags) M_MALLOC
void	M_list_destroy (M_list_t *d, M_bool destroy_vals) M_FREE(1)
void	M_list_change_sorting (M_list_t *d, M_sort_compar_t equality, M_uint32 sorted_flags, void *thunk)
M_bool	M_list_insert (M_list_t *d, const void *val)
size_t	M_list_insert_idx (const M_list_t *d, const void *val)
M_bool	M_list_insert_at (M_list_t *d, const void *val, size_t idx)
void	M_list_insert_begin (M_list_t *d)
void	M_list_insert_end (M_list_t *d)
size_t	M_list_len (const M_list_t *d)
size_t	M_list_count (const M_list_t *d, const void *val, M_uint32 type)
M_bool	M_list_index_of (const M_list_t *d, const void *val, M_uint32 type, size_t *idx)
const void *	M_list_first (const M_list_t *d)
const void *	M_list_last (const M_list_t *d)
const void *	M_list_at (const M_list_t *d, size_t idx)
void *	M_list_take_first (M_list_t *d)
void *	M_list_take_last (M_list_t *d)
void *	M_list_take_at (M_list_t *d, size_t idx)
M_bool	M_list_remove_first (M_list_t *d)
M_bool	M_list_remove_last (M_list_t *d)
M_bool	M_list_remove_at (M_list_t *d, size_t idx)
size_t	M_list_remove_val (M_list_t *d, const void *val, M_uint32 type)
M_bool	M_list_remove_range (M_list_t *d, size_t start, size_t end)
void	M_list_remove_duplicates (M_list_t *d, M_uint32 type)
size_t	M_list_replace_val (M_list_t *d, const void *val, const void *new_val, M_uint32 type)
M_bool	M_list_replace_at (M_list_t *d, const void *val, size_t idx)
M_bool	M_list_swap (M_list_t *d, size_t idx1, size_t idx2)
M_list_t *	M_list_duplicate (const M_list_t *d) M_MALLOC
void	M_list_merge (M_list_t **dest, M_list_t *src, M_bool include_duplicates, M_uint32 type) M_FREE(2)

Detailed Description

Dynamic list (array) for storing values.

This should not be used directly. It is a base implementation that should be used by a type safe wrapper. For example: M_list_str.

The list can uses a set of callback functions to determine behavior. Such as if it should duplicate or free values.

The list can be used in multiple ways:

• Unsorted.
• Sorted.
• Queue (FIFO) (really just unsorted).
• Priority Queue (really just sorted).
• Stack (LIFO) (which cannot be sorted).
• Set.

A list is indexable. Find is also supported.

Indexes in the list are 0 at head to len-1 at end (head ... end). Functions like M_list_first will return head and M_list_last will return end.

The index start changes in STACK mode. In STACK mode indexing is opposite. Head is len-1 and end is 0 (head ... end). Entries are still added to end. Functions like M_list_first will return end and M_list_last will return head. This is to accommodate STACKS where entries are inserted and removed from the same end.

The list is designed for efficient head removal. A value removed from head will not cause a memmove. Instead a start offset will be noted. If there is space before head (due to removals) then additions at head will be efficient as the empty space will be used and a memmove will be avoided. memmoves will occur when the size (not necessarly number of elements) of the list changes (expand and shrink) and for removals in the middle of the list.

Sorted notes:

• Sorting can be set as stable. Insert will also be stable.
• Sorting on insert and find (M_list_index_of()) is done using binary insert/search.
• When M_list_insert_end() is called after M_list_insert_begin() mergesort/qsort will be used to sort the list.
• Sorting can use an optional thunk parameter but it can only be set by using M_list_change_sorting().

---

Data Structure Documentation

M_list_callbacks

struct M_list_callbacks

Structure of callbacks that can be registered to override default behavior for list implementation.

Data Fields
M_sort_compar_t	equality	Callback to check if two items in the list are equal. If NULL unsorted list
M_list_duplicate_func	duplicate_insert	Callback to duplicate a value on insert. If NULL is pass-thru pointer
M_list_duplicate_func	duplicate_copy	Callback to duplicate a value on copy. If NULL is pass-thru pointer
M_list_free_func	value_free	Callback to free a value. If NULL is pass-thru pointer

Typedef Documentation

M_list_t

typedef struct M_list M_list_t

M_list_duplicate_func

typedef void *(* M_list_duplicate_func) (const void *)

Function definition to duplicate a value.

M_list_free_func

typedef void(* M_list_free_func) (void *)

Function definition to free a value.

Enumeration Type Documentation

M_list_flags_t

enum M_list_flags_t

Flags for controlling the behavior of the list.

Enumerator
M_LIST_NONE	List (array) mode. Default unless M_LIST_STACK is specified.
M_LIST_SORTED	Whether the data in the list should be kept in sorted order. callbacks cannot be NULL and the equality function must be set if this is M_TRUE. Sorting cannot be combined with M_LIST_STACK.
M_LIST_STABLE	Make insert, search and sort stable.
M_LIST_STACK	Last in First out mode.
M_LIST_SET_VAL	All elements are unique based on their value. Insert is increased by an additional O(n) operation (on top of the insert itself) in order to determine if a value is a duplicate for unsorted. Insert is increased by an additional O(log(n)) operation (on top of the insert itself) in order to determine if a value is a duplicate for sorted.
M_LIST_SET_PTR	All elements are unique based on their pointer. Insert is increased by an additional O(n) operation (on top of the insert itself) in order to determine if a value is a duplicate for unsorted. Insert is increased by an additional O(log(n)) operation (on top of the insert itself) in order to determine if a value is a duplicate for sorted.
M_LIST_NEVERSHRINK	Never allow the list to shrink.

M_list_match_type_t

enum M_list_match_type_t

Type of matching that should be used when searching/modifying a value in the list.

Enumerator
M_LIST_MATCH_VAL	Match based on the value (equality function).
M_LIST_MATCH_PTR	Math the pointer itself.
M_LIST_MATCH_ALL	Include all instances.

Function Documentation

M_list_create()

M_list_t * M_list_create	(	const struct M_list_callbacks *	callbacks,
		M_uint32	flags
	)

Create a new dynamic list.

A dynamic list is a dynamically expanding array. Meaning the array will expand to accommodate new elements. The list can be, optionally, kept in sorted order. The sorted order is determined by the equality callback function if sorting is enabled.

Parameters

[in]	callbacks	Register callbacks for overriding default behavior. May pass NULL if not overriding default behavior.
[in]	flags	M_list_flags_t flags controlling behavior.

Returns

Allocated dynamic list.

See also

M_list_destroy

M_list_destroy()

void M_list_destroy	(	M_list_t *	d,
		M_bool	destroy_vals
	)

Destroy the list.

Parameters

[in]	d	The list to destory.
[in]	destroy_vals	Whether the values held in the list should be destroyed. If the list is not duplicating the values it holds then destroying values may not be desirable.

M_list_change_sorting()

void M_list_change_sorting	(	M_list_t *	d,
		M_sort_compar_t	equality,
		M_uint32	sorted_flags,
		void *	thunk
	)

Change the sorting behavior of the list.

The list cannot have been created as a queue.

Parameters

[in,out]	d	The list.
[in]	equality	The equality function to use. Can be NULL to remove the equality function.
[in]	sorted_flags	M_list_flags_t to specify how sorting should be handled. Allows the following: M_LIST_SORTED M_LIST_STACK Omitting one of these flags will disable it.
[in]	thunk	Thunk passed to equality function.

M_list_insert()

M_bool M_list_insert	(	M_list_t *	d,
		const void *	val
	)

Insert a value into the list.

If sorted the value will be inserted in sorted order. Otherwise it will be appended to the end of the list.

Parameters

[in,out]	d	The list.
[in]	val	The value to insert.

Returns

M_TRUE on success otherwise M_FALSE.

M_list_insert_idx()

size_t M_list_insert_idx	(	const M_list_t *	d,
		const void *	val
	)

Get the index a value would be insert into the list at.

This does not actually insert the value into the list it only gets the position the value would be insert into the list if/when insert is called.

Parameters

[in]	d	The list.
[in]	val	The value to get the insertion index for.

Returns

The insertion index.

M_list_insert_at()

M_bool M_list_insert_at	(	M_list_t *	d,
		const void *	val,
		size_t	idx
	)

Insert a value into the list at a specific position.

This is only supported for non-sorted lists.

Parameters

[in,out]	d	The list.
[in]	val	The value to insert.
[in]	idx	The position to insert at. An index larger than the number of elements in the list will result in the item being inserted at the end.

Returns

M_TRUE on success otherwise M_FALSE.

M_list_insert_begin()

void M_list_insert_begin

(

M_list_t *

d

)

Start a grouped insertion.

This is only useful for sorted lists. This will defer sorting until M_list_insert_end() is called. This is to allow many items to be inserted at once without the sorting overhead being called for every insertion.

Parameters

[in,out]

d

The list.

See also

M_list_insert_end

M_list_insert_end()

void M_list_insert_end

(

M_list_t *

d

)

End a grouped insertion.

This is only useful for sorted lists. Cause all elements in the list (if sorting is enabled) to be sorted.

Parameters

[in,out]

d

The list.

See also

M_list_insert_begin

M_list_len()

size_t M_list_len

(

const M_list_t *

d

)

The length of the list.

Parameters

[in]

d

The list.

Returns

the length of the list.

M_list_count()

size_t M_list_count	(	const M_list_t *	d,
		const void *	val,
		M_uint32	type
	)

Count the number of times a value occurs in the list.

Parameters

[in]	d	The list.
[in]	val	The value to search for.
[in]	type	M_list_match_type_t type of how the val should be matched. valid values are: M_LIST_MATCH_VAL M_LIST_MATCH_PTR

Returns

The number of times val appears in the list.

M_list_index_of()

M_bool M_list_index_of	(	const M_list_t *	d,
		const void *	val,
		M_uint32	type,
		size_t *	idx
	)

Get the location of a value within the list.

This will return a location in the list which may not be the first occurrence in the list.

Parameters

[in]	d	The list.
[in]	val	The value to search for.
[in]	type	M_list_match_type_t type of how the val should be matched. valid values are: M_LIST_MATCH_VAL M_LIST_MATCH_PTR
[out]	idx	The index of the value within the list. Optional, pass NULL if not needed.

Returns

M_TRUE if the value was found within the list. Otherwise M_FALSE.

M_list_first()

const void * M_list_first

(

const M_list_t *

d

)

Get the first element.

The element will remain a member of the list.

Parameters

[in]

d

The list.

Returns

The element or NULL if there are no elements.

See also

M_list_at

M_list_last

M_list_last()

const void * M_list_last

(

const M_list_t *

d

)

Get the last element.

The element will remain a member of the list.

Parameters

[in]

d

The list.

Returns

The element or NULL if there are no elements.

See also

M_list_at

M_list_first

M_list_at()

const void * M_list_at	(	const M_list_t *	d,
		size_t	idx
	)

Get the element at a given index.

The element will remain a member of the list.

Parameters

[in]	d	The list.
[in]	idx	The location to retrieve the element from.

Returns

The element or NULL if index is out range.

See also

M_list_first

M_list_last

M_list_take_first()

void * M_list_take_first

(

M_list_t *

d

)

Take the first element.

The element will be removed from the list and returned. The caller is responsible for freeing the element.

Parameters

[in,out]

d

The list.

Returns

The element or NULL if there are no elements.

See also

M_list_take_at

M_list_last

M_list_take_last()

void * M_list_take_last

(

M_list_t *

d

)

Take the last element.

The element will be removed from the list and returned. The caller is responsible for freeing the element.

Parameters

[in,out]

d

The list.

Returns

The element or NULL if there are no elements.

See also

M_list_take_at

M_list_take_first

M_list_take_at()

void * M_list_take_at	(	M_list_t *	d,
		size_t	idx
	)

Take the element at a given index.

The element will be removed from the list and returned. The caller is responsible for freeing the element.

Parameters

[in,out]	d	The list.
[in]	idx	The location to retrieve the element from.

Returns

The element or NULL if index is out range.

See also

M_list_take_first

M_list_take_last

M_list_remove_first()

M_bool M_list_remove_first

(

M_list_t *

d

)

Remove the first element.

The value will be free'd using the value_free callback.

Parameters

[in,out]

d

The list.

Returns

M_TRUE if the element was removed. Otherwise M_FALSE.

See also

M_list_remove_at

M_list_remove_last

M_list_remove_last()

M_bool M_list_remove_last

(

M_list_t *

d

)

Remove the last element.

The value will be free'd using the value_free callback.

Parameters

[in,out]

d

The list.

Returns

M_TRUE if the element was removed. Otherwise M_FALSE.

See also

M_list_remove_at

M_list_remove_first

M_list_remove_at()

M_bool M_list_remove_at	(	M_list_t *	d,
		size_t	idx
	)

Remove an element at a given index from the list.

The value will be free'd using the value_free callback.

Parameters

[in,out]	d	The list.
[in]	idx	The index to remove.

Returns

M_TRUE if the element was removed. Otherwise M_FALSE.

\ see M_list_remove_first \ see M_list_remove_last \ see M_list_remove_val \ see M_list_remove_range

M_list_remove_val()

size_t M_list_remove_val	(	M_list_t *	d,
		const void *	val,
		M_uint32	type
	)

Remove element(s) from the list.

Searches the list for the occurrence of val and removes it from the list. The value will be free'd using the value_free callback.

Requires the equality callback to be set.

Parameters

[in,out]	d	The list.
[in]	val	The val to remove
[in]	type	M_list_match_type_t type of how the val should be matched.

Returns

The number of elements removed.

See also

M_list_remove_at

M_list_remove_range()

M_bool M_list_remove_range	(	M_list_t *	d,
		size_t	start,
		size_t	end
	)

Remove a range of elements form the list.

The values will be free'd using the value_free callback.

Parameters

[in,out]	d	The list.
[in]	start	The start index. Inclusive.
[in]	end	The end index. Inclusive.

Returns

M_TRUE if the range was removed. Otherwise M_FALSE.

See also

M_list_remove_at

M_list_remove_duplicates()

void M_list_remove_duplicates	(	M_list_t *	d,
		M_uint32	type
	)

Remove duplicate elements from the list.

Requires the equality callback to be set. The values will be free'd using the value_free callback.

Parameters

[in]	d	The list.
[in]	type	M_list_match_type_t type of how the val should be matched. valid values are: M_LIST_MATCH_VAL M_LIST_MATCH_PTR

M_list_replace_val()

size_t M_list_replace_val	(	M_list_t *	d,
		const void *	val,
		const void *	new_val,
		M_uint32	type
	)

Replace all matching values in the list with a different value.

The replaced values in the list will be free'd using the value_free callback.

Parameters

[in,out]	d	The list.
[in]	val	The val to be replaced.
[in]	new_val	The value to be replaced with.
[in]	type	M_list_match_type_t type of how the val should be matched.

Returns

The number of elements replaced.

M_list_replace_at()

M_bool M_list_replace_at	(	M_list_t *	d,
		const void *	val,
		size_t	idx
	)

Replace a value in the list with a different value.

The replaced value in the list will be free'd using the value_free callback.

Parameters

[in,out]	d	The list.
[in]	val	The val to that will appear in the list at the given idx.
[in]	idx	The index to replace.

Returns

M_TRUE if the value was replaced. Otherwise M_FALSE.

M_list_swap()

M_bool M_list_swap	(	M_list_t *	d,
		size_t	idx1,
		size_t	idx2
	)

Exchange the elements at the given locations.

This only applies to unsorted lists.

Parameters

[in,out]	d	The list.
[in]	idx1	The first index.
[in]	idx2	The second index.

Returns

M_TRUE if the elements were swapped.

M_list_duplicate()

M_list_t * M_list_duplicate

(

const M_list_t *

d

)

Duplicate an existing list.

Will copy all elements of the list as well as any callbacks, etc.

Parameters

[in]

d

list to duplicate.

Returns

New list.

M_list_merge()

void M_list_merge	(	M_list_t **	dest,
		M_list_t *	src,
		M_bool	include_duplicates,
		M_uint32	type
	)

Merge two lists together.

The second (src) list will be destroyed automatically upon completion of this function. Any value pointers for the list will be directly copied over to the destination list, they will not be duplicated.

Parameters

[in,out]	dest	Pointer by reference to the list receiving the values. if this is NULL, the pointer will simply be switched out for src.
[in,out]	src	Pointer to the list giving up its values.
[in]	include_duplicates	When M_TRUE any values in 'dest' that also exist in 'src' will be included in 'dest'. When M_FALSE any duplicate values will not be added to 'dest'.
[in]	type	M_list_match_type_t type of how the val should be matched. valid values are: M_LIST_MATCH_VAL M_LIST_MATCH_PTR