List - uint64

Typedefs
typedef struct M_list_u64	M_list_u64_t

Enumerations
enum	M_list_u64_flags_t {   M_LIST_U64_NONE = 1 << 0 ,   M_LIST_U64_SORTASC = 1 << 1 ,   M_LIST_U64_SORTDESC = 1 << 2 ,   M_LIST_U64_STABLE = 1 << 3 ,   M_LIST_U64_STACK = 1 << 4 ,   M_LIST_U64_SET = 1 << 5 ,   M_LIST_U64_NEVERSHRINK = 1 << 6 }
enum	M_list_u64_match_type_t {   M_LIST_U64_MATCH_VAL = 0 ,   M_LIST_U64_MATCH_ALL = 1 << 0 }

Functions
M_list_u64_t *	M_list_u64_create (M_uint32 flags) M_MALLOC
void	M_list_u64_destroy (M_list_u64_t *d) M_FREE(1)
void	M_list_u64_change_sorting (M_list_u64_t *d, M_uint32 flags)
M_bool	M_list_u64_insert (M_list_u64_t *d, M_uint64 val)
size_t	M_list_u64_insert_idx (const M_list_u64_t *d, M_uint64 *val)
M_bool	M_list_u64_insert_at (M_list_u64_t *d, M_uint64 val, size_t idx)
void	M_list_u64_insert_begin (M_list_u64_t *d)
void	M_list_u64_insert_end (M_list_u64_t *d)
size_t	M_list_u64_len (const M_list_u64_t *d)
size_t	M_list_u64_count (const M_list_u64_t *d, M_uint64 val)
M_bool	M_list_u64_index_of (const M_list_u64_t *d, M_uint64 val, size_t *idx)
M_uint64	M_list_u64_first (const M_list_u64_t *d)
M_uint64	M_list_u64_last (const M_list_u64_t *d)
M_uint64	M_list_u64_at (const M_list_u64_t *d, size_t idx)
M_uint64	M_list_u64_take_first (M_list_u64_t *d)
M_uint64	M_list_u64_take_last (M_list_u64_t *d)
M_uint64	M_list_u64_take_at (M_list_u64_t *d, size_t idx)
M_bool	M_list_u64_remove_first (M_list_u64_t *d)
M_bool	M_list_u64_remove_last (M_list_u64_t *d)
M_bool	M_list_u64_remove_at (M_list_u64_t *d, size_t idx)
size_t	M_list_u64_remove_val (M_list_u64_t *d, M_uint64 val, M_uint32 type)
M_bool	M_list_u64_remove_range (M_list_u64_t *d, size_t start, size_t end)
void	M_list_u64_remove_duplicates (M_list_u64_t *d)
size_t	M_list_u64_replace_val (M_list_u64_t *d, M_uint64 val, M_uint64 new_val, M_uint32 type)
M_bool	M_list_u64_replace_at (M_list_u64_t *d, M_uint64 val, size_t idx)
M_bool	M_list_u64_swap (M_list_u64_t *d, size_t idx1, size_t idx2)
M_list_u64_t *	M_list_u64_duplicate (const M_list_u64_t *d) M_MALLOC
void	M_list_u64_merge (M_list_u64_t **dest, M_list_u64_t *src, M_bool include_duplicates) M_FREE(2)

Detailed Description

Dynamic list (array) for storing unsigned 64 bit integer values.

The list can be used in multiple ways:

• Unsorted.
• Sorted.
• Queue (FIFO) (really just unsorted).
• 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 shink) and for removals in the middle of the list.

Sorted notes:

• Sorting on insert and find (M_list_u64_index_of()) is done using binary insert/search.
• When M_list_insert_end() is called after M_list_insert_begin() qsort will be used to sort the list.

Typedef Documentation

M_list_u64_t

typedef struct M_list_u64 M_list_u64_t

Enumeration Type Documentation

M_list_u64_flags_t

enum M_list_u64_flags_t

Flags for controlling the behavior of the list.

Enumerator
M_LIST_U64_NONE	Not sorting, asc compare.
M_LIST_U64_SORTASC	Sort asc.
M_LIST_U64_SORTDESC	Sort desc.
M_LIST_U64_STABLE	Make insert, search and sort stable.
M_LIST_U64_STACK	Last in First out mode.
M_LIST_U64_SET	Don't allow duplicates in the list. 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_U64_NEVERSHRINK	Never allow the list to shrink.

M_list_u64_match_type_t

enum M_list_u64_match_type_t

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

Enumerator
M_LIST_U64_MATCH_VAL	Match based on the value (equality function).
M_LIST_U64_MATCH_ALL	Include all instances.

Function Documentation

M_list_u64_create()

M_list_u64_t * M_list_u64_create

(

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.

Parameters

[in]

flags

M_list_u64_flags_t flags for controlling behavior.

Returns

Allocated dynamic list for storing strings.

See also

M_list_u64_destroy

M_list_u64_destroy()

void M_list_u64_destroy

(

M_list_u64_t *

d

)

Destory the list.

Parameters

[in]

d

The list to destory.

M_list_u64_change_sorting()

void M_list_u64_change_sorting	(	M_list_u64_t *	d,
		M_uint32	flags
	)

Change the sorting behavior of the list.

Parameters

[in,out]	d	The list.
[in]	flags	M_list_u64_flags_t flags that control sorting.

M_list_u64_insert()

M_bool M_list_u64_insert	(	M_list_u64_t *	d,
		M_uint64	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_u64_insert_idx()

size_t M_list_u64_insert_idx	(	const M_list_u64_t *	d,
		M_uint64 *	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_u64_insert_at()

M_bool M_list_u64_insert_at	(	M_list_u64_t *	d,
		M_uint64	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_u64_insert_begin()

void M_list_u64_insert_begin

(

M_list_u64_t *

d

)

Start a grouped insertion.

This is only useful for sorted lists. This will defer sorting until M_list_u64_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_u64_insert_end

M_list_u64_insert_end()

void M_list_u64_insert_end

(

M_list_u64_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_u64_insert_begin

M_list_u64_len()

size_t M_list_u64_len

(

const M_list_u64_t *

d

)

The length of the list.

Parameters

[in]

d

The list.

Returns

the length of the list.

M_list_u64_count()

size_t M_list_u64_count	(	const M_list_u64_t *	d,
		M_uint64	val
	)

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

Parameters

[in]	d	The list.
[in]	val	The value to search for.

Returns

The number of times val appears in the list.

M_list_u64_index_of()

M_bool M_list_u64_index_of	(	const M_list_u64_t *	d,
		M_uint64	val,
		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.
[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_u64_first()

M_uint64 M_list_u64_first

(

const M_list_u64_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_u64_at

M_list_u64_last

M_list_u64_last()

M_uint64 M_list_u64_last

(

const M_list_u64_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_u64_at()

M_uint64 M_list_u64_at	(	const M_list_u64_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_u64_first

M_list_u64_last

M_list_u64_take_first()

M_uint64 M_list_u64_take_first

(

M_list_u64_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_u64_take_at

M_list_u64_last

M_list_u64_take_last()

M_uint64 M_list_u64_take_last

(

M_list_u64_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_u64_take_at

M_list_u64_take_first

M_list_u64_take_at()

M_uint64 M_list_u64_take_at	(	M_list_u64_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_u64_take_first

M_list_u64_take_last

M_list_u64_remove_first()

M_bool M_list_u64_remove_first

(

M_list_u64_t *

d

)

Remove the first element.

Parameters

[in,out]

d

The list.

Returns

M_TRUE if the element was removed. Otherwise M_FALSE.

See also

M_list_u64_remove_at

M_list_u64_remove_last

M_list_u64_remove_last()

M_bool M_list_u64_remove_last

(

M_list_u64_t *

d

)

Remove the last element.

Parameters

[in,out]

d

The list.

Returns

M_TRUE if the element was removed. Otherwise M_FALSE.

See also

M_list_u64_remove_at

M_list_u64_remove_first

M_list_u64_remove_at()

M_bool M_list_u64_remove_at	(	M_list_u64_t *	d,
		size_t	idx
	)

Remove an element at a given index from the list.

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_u64_remove_first \ see M_list_u64_remove_last \ see M_list_u64_remove_val \ see M_list_u64_remove_range

M_list_u64_remove_val()

size_t M_list_u64_remove_val	(	M_list_u64_t *	d,
		M_uint64	val,
		M_uint32	type
	)

Remove element(s) from the list.

Searches the list for the occurrence of val and removes it from the list.

Parameters

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

Returns

The number of elements removed.

See also

M_list_u64_remove_at

M_list_u64_remove_range()

M_bool M_list_u64_remove_range	(	M_list_u64_t *	d,
		size_t	start,
		size_t	end
	)

Remove a range of elements form the list.

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.

M_list_u64_remove_duplicates()

void M_list_u64_remove_duplicates

(

M_list_u64_t *

d

)

Remove duplicate elements from the list.

Parameters

[in]

d

The list.

M_list_u64_replace_val()

size_t M_list_u64_replace_val	(	M_list_u64_t *	d,
		M_uint64	val,
		M_uint64	new_val,
		M_uint32	type
	)

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

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_u64_match_type_t type of how the val should be matched.

Returns

The number of elements replaced.

M_list_u64_replace_at()

M_bool M_list_u64_replace_at	(	M_list_u64_t *	d,
		M_uint64	val,
		size_t	idx
	)

Replace a value in the list with a different value.

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_u64_swap()

M_bool M_list_u64_swap	(	M_list_u64_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_u64_duplicate()

M_list_u64_t * M_list_u64_duplicate

(

const M_list_u64_t *

d

)

Duplicate an existing list.

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

Parameters

[in]

d

list to duplicate.

Returns

New list.

M_list_u64_merge()

void M_list_u64_merge	(	M_list_u64_t **	dest,
		M_list_u64_t *	src,
		M_bool	include_duplicates
	)

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'.