Queue

Typedefs
typedef struct M_queue	M_queue_t
typedef struct M_queue_foreach	M_queue_foreach_t

Functions
M_queue_t *	M_queue_create (M_sort_compar_t sort_cb, void(*free_cb)(void *))
void	M_queue_destroy (M_queue_t *queue)
M_bool	M_queue_insert (M_queue_t *queue, void *member)
M_bool	M_queue_remove (M_queue_t *queue, const void *member)
M_bool	M_queue_exists (const M_queue_t *queue, const void *member)
M_bool	M_queue_take (M_queue_t *queue, const void *member)
void *	M_queue_take_first (M_queue_t *queue)
size_t	M_queue_len (const M_queue_t *queue)
void *	M_queue_first (M_queue_t *queue)
void *	M_queue_last (M_queue_t *queue)
M_bool	M_queue_foreach (const M_queue_t *queue, M_queue_foreach_t **q_foreach, void **member)
void	M_queue_foreach_free (M_queue_foreach_t *q_foreach)

Detailed Description

Queue, meant for storing a list of pointers in either insertion order or sorted as per a user-defined callback. The usage is very similar to that of an M_llist_t, and infact an M_llist_t is used as one of the backing data types, but it also uses an M_hashtable_t in order to make lookups and removals of queue members by pointer O(1) rather than O(log n) for sorted lists or O(n) for unsorted lists.

Usage Example:

M_queue_t         *queue;
void              *member    = NULL;
M_queue_foreach_t *q_foreach = NULL;
 
queue = M_queue_create(M_sort_compar_str, M_free);
M_queue_insert(queue, M_strdup("b. hello world"));
M_queue_insert(queue, M_strdup("c. goodbye"));
M_queue_insert(queue, M_strdup("a! -- I should end up enumerated first"));
M_printf("queue members: %zu\n", M_queue_len(queue));
 
while (M_queue_foreach(queue, &q_foreach, &member)) {
    M_printf("removing member: %s\n", (const char *)member);
    M_queue_remove(queue, member);
}
 
M_printf("queue members: %zu\n", M_queue_len(queue));
M_queue_destroy(queue);

Typedef Documentation

M_queue_t

typedef struct M_queue M_queue_t

Data type used as the main queue object

M_queue_foreach_t

typedef struct M_queue_foreach M_queue_foreach_t

Data type used for enumeration of a queue

Function Documentation

M_queue_create()

M_queue_t * M_queue_create	(	M_sort_compar_t	sort_cb,
		void(*)(void *)	free_cb
	)

Create a queue (list of objects) that stores user-provided pointers. The pointers stored may be kept in insertion order or sorted, depending on how the queue is initialized.

Parameters

sort_cb	If the pointers should be stored in a sorted order, register this callback with the routine for sorting. If insertion order is desired, pass NULL.
free_cb	Upon removal of a pointer from the queue, this callback will be called. This applies to M_queue_destroy() and M_queue_remove(). If no free callback desired, pass NULL.

Returns

Allocated M_queue_t * on success that should be free'd with M_queue_destroy(), otherwise NULL.

M_queue_destroy()

void M_queue_destroy

(

M_queue_t *

queue

)

Destroy's an initialized M_queue_t * object.

Parameters

queue

Initialized queue object returned by M_queue_create()

M_queue_insert()

M_bool M_queue_insert	(	M_queue_t *	queue,
		void *	member
	)

Insert a user-supplied queue object (pointer) into the queue. The object specified should not already be in the queue.

Parameters

queue	Initialized queue object returned by M_queue_create()
member	User-supplied queue object (pointer) to insert, must not be NULL.

Returns

M_TRUE on success, M_FALSE on failure such as if the user-supplied object already exists in the queue

M_queue_remove()

M_bool M_queue_remove	(	M_queue_t *	queue,
		const void *	member
	)

Remove a user-supplied queue object (pointer) from the queue. If M_queue_create() registered the free_cb, the free_cb will be called upon removal.

Parameters

queue	Initialized queue object returned by M_queue_create()
member	User-supplied queue object (pointer) to remove.

Returns

M_TRUE on success, M_FALSE on failure such as object not found.

M_queue_exists()

M_bool M_queue_exists	(	const M_queue_t *	queue,
		const void *	member
	)

See if queue member still exists.

Parameters

queue	Initialized queue object returned by M_queue_create()
member	User-supplied queue object (pointer) to find.

Returns

M_TRUE if member exists, M_FALSE otherwise.

M_queue_take()

M_bool M_queue_take	(	M_queue_t *	queue,
		const void *	member
	)

Take control of a user-supplied queue object (pointer). This will remove the object from the list without freeing the object (assuming free_cb was registered). If no free_cb was registered in M_queue_create(), this has the same behavior as M_queue_remove().

Parameters

queue	Initialized queue object returned by M_queue_create()
member	User-supplied queue object (pointer) to take ownership of.

Returns

M_TRUE on success, M_FALSE on failure such as object not found.

M_queue_take_first()

void * M_queue_take_first

(

M_queue_t *

queue

)

Take control of the first queue member. This will remove the object from the list without freeing the object (assuming free_cb was registered).

Parameters

queue

Initialized queue object returned by M_queue_create()

Returns

pointer to first queue object, NULL if none

M_queue_len()

size_t M_queue_len

(

const M_queue_t *

queue

)

Retrieve the number of items in the specified queue.

Parameters

queue

Initialized queue object returned by M_queue_create()

Returns

count of items in the queue.

M_queue_first()

void * M_queue_first

(

M_queue_t *

queue

)

Retrieve the first queue entry in the specified queue.

Parameters

queue

Initialized queue object returned by M_queue_create()

Returns

First queue entry, NULL if no entries

M_queue_last()

void * M_queue_last

(

M_queue_t *

queue

)

Retrieve the last queue entry in the specified queue.

Parameters

queue

Initialized queue object returned by M_queue_create()

Returns

Last queue entry, NULL if no entries

M_queue_foreach()

M_bool M_queue_foreach	(	const M_queue_t *	queue,
		M_queue_foreach_t **	q_foreach,
		void **	member
	)

Enumerate across all members in the queue. This function is designed to be run in a while() loop until it returns M_FALSE. The q_foreach parameter will be automatically deallocated if this returns M_FALSE, otherwise if breaking out of the loop early, M_queue_foreach_free must be called.

During an enumeration, it is allowable to remove the current member from the queue. It is undefined behavior to remove any other member during an enumeration. Addition to the queue is also allowed during an enumeration, however it is not defined if the new value will end up in the enumerated set.

Parameters

queue	Initialized queue object returned by M_queue_create()
q_foreach	M_queue_foreach_t * passed By Reference, and initialized to NULL before the first call to M_queue_foreach(). The value returned is not meant to be interpreted and must be passed back in, unmodified to the next call of M_queue_foreach(). If breaking out of the loop prior to M_queue_foreach() returning M_FALSE, this object should be free'd with M_queue_foreach_free().
member	Pointer to member to be filled in, passed By Reference. This value will be populated with the current member in the enumeration. Must not be NULL.

Returns

M_TRUE if there are more members to enumerate, M_FALSE if no more members and no result was returned.

M_queue_foreach_free()

void M_queue_foreach_free

(

M_queue_foreach_t *

q_foreach

)

Free's the M_queue_foreach_t * filled in by M_queue_foreach. This only needs to be called if the enumeration was ended early and not allowed to run to completion. NOTE: This may currently be a no-op if q_foreach just references an internal pointer.

Parameters

q_foreach

M_queue_foreach_t * initialized by M_queue_foreach.