Linked List (Generic)

Data Structures
struct	M_llist_callbacks

Typedefs
typedef struct M_llist	M_llist_t
typedef struct M_llist_node	M_llist_node_t
typedef void *(*	M_llist_duplicate_func) (const void *)
typedef void(*	M_llist_free_func) (void *)

Enumerations
enum	M_llist_flags_t {   M_LLIST_NONE = 0 ,   M_LLIST_SORTED = 1 << 0 ,   M_LLIST_CIRCULAR = 1 << 1 }
enum	M_llist_match_type_t {   M_LLIST_MATCH_VAL = 0 ,   M_LLIST_MATCH_PTR = 1 << 0 ,   M_LLIST_MATCH_ALL = 1 << 1 }

Functions
M_llist_t *	M_llist_create (const struct M_llist_callbacks *callbacks, M_uint32 flags) M_MALLOC
M_bool	M_llist_change_sorting (M_llist_t *d, M_sort_compar_t equality_cb, void *equality_thunk)
void	M_llist_destroy (M_llist_t *d, M_bool destroy_vals) M_FREE(1)
M_llist_node_t *	M_llist_insert (M_llist_t *d, const void *val)
M_llist_node_t *	M_llist_insert_first (M_llist_t *d, const void *val)
M_llist_node_t *	M_llist_insert_before (M_llist_node_t *n, const void *val)
M_llist_node_t *	M_llist_insert_after (M_llist_node_t *n, const void *val)
void	M_llist_set_first (M_llist_node_t *n)
void	M_llist_set_last (M_llist_node_t *n)
M_bool	M_llist_move_before (M_llist_node_t *move, M_llist_node_t *before)
M_bool	M_llist_move_after (M_llist_node_t *move, M_llist_node_t *after)
size_t	M_llist_len (const M_llist_t *d)
size_t	M_llist_count (const M_llist_t *d, const void *val, M_uint32 type)
M_llist_node_t *	M_llist_first (const M_llist_t *d)
M_llist_node_t *	M_llist_last (const M_llist_t *d)
M_llist_node_t *	M_llist_find (const M_llist_t *d, const void *val, M_uint32 type)
void *	M_llist_take_node (M_llist_node_t *n)
M_bool	M_llist_remove_node (M_llist_node_t *n)
size_t	M_llist_remove_val (M_llist_t *d, const void *val, M_uint32 type)
void	M_llist_remove_duplicates (M_llist_t *d, M_uint32 type)
M_llist_node_t *	M_llist_node_next (const M_llist_node_t *n)
M_llist_node_t *	M_llist_node_prev (const M_llist_node_t *n)
void *	M_llist_node_val (const M_llist_node_t *n)
M_llist_t *	M_llist_duplicate (const M_llist_t *d) M_MALLOC
void	M_llist_merge (M_llist_t **dest, M_llist_t *src, M_bool include_duplicates, M_uint32 type) M_FREE(2)

Detailed Description

Linked list 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_llist_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).

A linked list is not indexable. Iteration and find are supported.

Sorted notes:

• Sorting is implemented as a skip list. This should provide near O(long(n)) performance. Performance nearing a sorted M_list_t.
• Sorting is stable. If an element with a matching value is already in the list then it will be inserted after. Find will always find the first matching element in the list.
• The Skip List implementation does not use a fixed maximum level size (a fixed maximum number of elements). The level cap will be increased when the number of elements increases past the optimum number of elements for a given level count.
• Level growth is bounded to one more than the current number of levels unless that would exceed the cap for the current number of elements.
• When removing elements any empty levels will be removed.

---

Data Structure Documentation

M_llist_callbacks

struct M_llist_callbacks

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

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

Typedef Documentation

M_llist_t

typedef struct M_llist M_llist_t

M_llist_node_t

typedef struct M_llist_node M_llist_node_t

M_llist_duplicate_func

typedef void *(* M_llist_duplicate_func) (const void *)

Function definition to duplicate a value.

M_llist_free_func

typedef void(* M_llist_free_func) (void *)

Function definition to free a value.

Enumeration Type Documentation

M_llist_flags_t

enum M_llist_flags_t

Flags for controlling the behavior of the list.

Enumerator
M_LLIST_NONE	LList mode (unsorted).
M_LLIST_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.
M_LLIST_CIRCULAR	Whether the nodes are linked in a circular manner. Last node points to first. This cannot be used while sorted.

M_llist_match_type_t

enum M_llist_match_type_t

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

Enumerator
M_LLIST_MATCH_VAL	Match based on the value (equality function).
M_LLIST_MATCH_PTR	Math the pointer itself.
M_LLIST_MATCH_ALL	Include all instances.

Function Documentation

M_llist_create()

M_llist_t * M_llist_create	(	const struct M_llist_callbacks *	callbacks,
		M_uint32	flags
	)

Create a new list.

A list is a linked list. 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_llist_flags_t flags controlling behavior.

Returns

Allocated linked list.

See also

M_llist_destroy

M_llist_change_sorting()

M_bool M_llist_change_sorting	(	M_llist_t *	d,
		M_sort_compar_t	equality_cb,
		void *	equality_thunk
	)

Use the provided callback and thunk for sorting.

Warning

This function will only succeed if the original linked list was created with sort enabled (M_LLIST_SORTED), and no items have been added to the list yet.

Parameters

d	the llist to update
equality_cb	callback that should be used for sorting
equality_thunk	thunk to pass to callback, may be NULL. Ownership of thunk remains with caller.

Returns

M_TRUE on success, M_FALSE if error

M_llist_destroy()

void M_llist_destroy	(	M_llist_t *	d,
		M_bool	destroy_vals
	)

Destroy the list.

Parameters

[in]	d	The llist 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_llist_insert()

M_llist_node_t * M_llist_insert	(	M_llist_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

Pointer to M_llist_node_t container object of new node on success, otherwise NULL.

See also

M_llist_insert_first

M_llist_insert_first()

M_llist_node_t * M_llist_insert_first	(	M_llist_t *	d,
		const void *	val
	)

Insert a value into the list as the first node.

Only applies to unsorted lists.

Parameters

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

Returns

Pointer to M_llist_node_t container object of new node on success, otherwise NULL

See also

M_llist_insert

M_llist_insert_before()

M_llist_node_t * M_llist_insert_before	(	M_llist_node_t *	n,
		const void *	val
	)

Insert a value into the list before a given node.

Only applies to unsorted lists.

Parameters

[in,out]	n	The node to insert before. Cannot be NULL.
[in]	val	The value to insert.

Returns

Pointer to M_llist_node_t container object of new node on success, otherwise NULL

See also

M_llist_insert_after

M_llist_insert_after()

M_llist_node_t * M_llist_insert_after	(	M_llist_node_t *	n,
		const void *	val
	)

Insert a value into the list after a given node.

Only applies to unsorted lists.

Parameters

[in,out]	n	The node to insert after. Cannot be NULL.
[in]	val	The value to insert.

Returns

Pointer to M_llist_node_t container object of new node on success, otherwise NULL

See also

M_llist_insert_before

M_llist_set_first()

void M_llist_set_first

(

M_llist_node_t *

n

)

Set the node as the first node.

Only applies to unsorted or circular lists.

Parameters

[in]

n

The node that should be considered first.

M_llist_set_last()

void M_llist_set_last

(

M_llist_node_t *

n

)

Set the node as the last node.

Only applies to unsorted or circular lists.

Parameters

[in]

n

The node that should be considered last.

M_llist_move_before()

M_bool M_llist_move_before	(	M_llist_node_t *	move,
		M_llist_node_t *	before
	)

Move a node before another node in the list.

Parameters

[in]	move	The node to move.
[in]	before	The node that move should be placed before.

Returns

M_TRUE on sucess, otherwise M_FALSE.

M_llist_move_after()

M_bool M_llist_move_after	(	M_llist_node_t *	move,
		M_llist_node_t *	after
	)

Move a node after another node in the list.

Parameters

[in]	move	The node to move.
[in]	after	The node that move should be placed after.

Returns

M_TRUE on sucess, otherwise M_FALSE.

M_llist_len()

size_t M_llist_len

(

const M_llist_t *

d

)

The length of the list.

Parameters

[in]

d

The list.

Returns

the length of the list.

M_llist_count()

size_t M_llist_count	(	const M_llist_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_llist_match_type_t type of how the val should be matched. valid values are: M_LLIST_MATCH_VAL M_LLIST_MATCH_PTR

Returns

The number of times val appears in the list.

M_llist_first()

M_llist_node_t * M_llist_first

(

const M_llist_t *

d

)

Get the first node in the list.

Parameters

[in]

d

The list.

Returns

Node or NULL.

See also

M_llist_last

M_llist_find

M_llist_last()

M_llist_node_t * M_llist_last

(

const M_llist_t *

d

)

Get the last node in the list.

Parameters

[in]

d

The list.

Returns

Node or NULL.

See also

M_llist_first

M_llist_find

M_llist_find()

M_llist_node_t * M_llist_find	(	const M_llist_t *	d,
		const void *	val,
		M_uint32	type
	)

Find a node for the given value in the list.

Parameters

[in]	d	The list.
[in]	val	The value to search for.
[in]	type	M_llist_match_type_t type of how the val should be matched. valid values are: M_LLIST_MATCH_VAL M_LLIST_MATCH_PTR

Returns

Node or NULL.

See also

M_llist_first

M_llist_last

M_llist_take_node()

void * M_llist_take_node

(

M_llist_node_t *

n

)

Take the node from the list and return its value.

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

Parameters

[in]

n

The node.

Returns

The node's value.

See also

M_llist_node_val

M_llist_remove_node()

M_bool M_llist_remove_node

(

M_llist_node_t *

n

)

Remove a node from the list.

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

Parameters

[in]

n

The node.

Returns

M_TRUE on success otherwise M_FALSE.

See also

M_llist_remove_val

M_llist_remove_val()

size_t M_llist_remove_val	(	M_llist_t *	d,
		const void *	val,
		M_uint32	type
	)

Remove node(s) from the list matching a given value.

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

Parameters

[in,out]	d	The list.
[in]	val	The value to search for.
[in]	type	M_llist_match_type_t type of how the val should be matched. valid values are: M_LLIST_MATCH_VAL M_LLIST_MATCH_PTR M_LLIST_MATCH_ALL

Returns

M_TRUE on success otherwise M_FALSE.

See also

M_llist_remove_node

M_llist_remove_duplicates()

void M_llist_remove_duplicates	(	M_llist_t *	d,
		M_uint32	type
	)

Remove duplicate values 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_llist_match_type_t type of how the val should be matched. valid values are: M_LLIST_MATCH_VAL M_LLIST_MATCH_PTR

M_llist_node_next()

M_llist_node_t * M_llist_node_next

(

const M_llist_node_t *

n

)

Get the next node, the one after a given node.

Parameters

[in]

n

The node.

Returns

Node or NULL.

See also

M_llist_node_prev

M_llist_node_prev()

M_llist_node_t * M_llist_node_prev

(

const M_llist_node_t *

n

)

Get the previous node, the one before a given node.

Parameters

[in]

n

The node.

Returns

Node or NULL.

See also

M_llist_node_next

M_llist_node_val()

void * M_llist_node_val

(

const M_llist_node_t *

n

)

Get the value for a node.

Parameters

[in]

n

The node.

Returns

The node's value.

See also

M_llist_take_node

M_llist_duplicate()

M_llist_t * M_llist_duplicate

(

const M_llist_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_llist_merge()

void M_llist_merge	(	M_llist_t **	dest,
		M_llist_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_llist_match_type_t type of how the val should be matched. valid values are: M_LLIST_MATCH_VAL M_LLIST_MATCH_PTR