list.h File Reference

Provides a highly-concurrent, optionally resizable, optimized-for-inserts list. More...

#include "qev.h"

Go to the source code of this file.

Typedefs
typedef struct qev_list	qev_list_t
	Bitch, stop looking at me.
typedef void(*	qev_list_cb )(void *item, void *data)
	A callback for iterating the list: takes the item in the list and any supplied data.

Functions
qev_list_t *	qev_list_new (const gint32 size, const qev_free_fn free_fn)
	Create a new list. More...
struct qev_list *	qev_list_new_resizable (const gint32 min_size, const gint32 max_size, const qev_free_fn free_fn)
	Create a new list that expands in size as necessary. More...
void	qev_list_free (qev_list_t *list)
	Cleans up the list and frees everything in it. More...
gboolean	qev_list_add (qev_list_t *list, void *thing, gint32 *idx)
	Insert an item into the list. More...
gboolean	qev_list_try_add (qev_list_t *list, void *thing, gint32 *idx)
	Insert an item into the list without blocking. More...
void	qev_list_remove (qev_list_t *list, gint32 *idx)
	Remove an item from the list. More...
void *	qev_list_steal (qev_list_t *list, gint32 *idx)
	Steal an item from the list without calling free_fn on it. More...
void	qev_list_empty (qev_list_t *list)
	Empties out the entire list. More...
void	qev_list_foreach (qev_list_t *list, qev_list_cb cb, guint threads, gboolean unlocked, void *data)
	Iterates through the list, calling cb on each item. More...
guint32	qev_list_size (qev_list_t *list)
	The number of items in the list. More...

Detailed Description

Provides a highly-concurrent, optionally resizable, optimized-for-inserts list.

Author

Andrew Stone andre.nosp@m.w@cl.nosp@m.ovar..nosp@m.com

Copyright

2012-2014 Clear Channel Inc.

Function Documentation

gboolean qev_list_add	(	qev_list_t *	list,
		void *	thing,
		gint32 *	idx
	)

Insert an item into the list.

Note

This call will block as necessary for resize operations to ensure that any item that can be inserted will be inserted. Use qev_list_try_add() to not block.

Parameters

list	The list to insert into
thing	The thing to add to the list. MAY NOT BE NULL.
idx	A pointer to a gint32 that exists for the liftetime of thing; this value will change as the item is moved around in the queue, and it MUST be treated as read-only. If you don't care about the item's position, NULL is fine. [allow-null]

Returns

If the item was inserted into the list.

void qev_list_empty

(

qev_list_t *

list

)

Empties out the entire list.

Attention

This operation does not allow any other concurrent operations.

Parameters

list	The list to empty

void qev_list_foreach	(	qev_list_t *	list,
		qev_list_cb	cb,
		guint	threads,
		gboolean	unlocked,
		void *	data
	)

Iterates through the list, calling cb on each item.

Optionally, the iterator can use the jobs pool to speed up iterating. Even more optionally, if you know that you can safely iterate through the list without a lock, you can disable that functionality.

Note

While iterating through the list, doing any operations on the list from the iterator thread(s) is an error and will typically result in some form of deadlock or undefined behavior. In other words, don't do that.

The list is iterated in reverse, and since this list tries to operate using minimal locking, it's possible to see the same element numerous times. Iterating forward through the list makes it possible to miss some elements as they might be moved in front of the iterator; going in reverse is the only way to be sure to hit them all at least once.

Parameters

list	The list to iterate
cb	The function to call on each item
threads	The number of threads to use. 0/1 means only use the current thread. >1 means use the jobs pool to run faster.
unlocked	If the iterators should run unlocked.
data	Data to pass to each callback

void qev_list_free

(

qev_list_t *

list

)

Cleans up the list and frees everything in it.

free_fn will be called on every item in the list.

Parameters

list	The list to free

qev_list_t* qev_list_new	(	const gint32	size,
		const qev_free_fn	free_fn
	)

Create a new list.

Parameters

size	The maximum size for the list
free_fn	Function used to free elements when removed from the list

Returns

The new list

struct qev_list* qev_list_new_resizable	(	const gint32	min_size,
		const gint32	max_size,
		const qev_free_fn	free_fn
	)

Create a new list that expands in size as necessary.

The allocated size of the list will NEVER shrink below min_size or grow larger than max_size.

Note

It's a good idea to use powers of 2 for sizes.

Parameters

min_size	The minimum size that the list may be.
max_size	The maximum size that the list may grow to.
free_fn	Function used to free elements when removed from the list

Returns

The new list

void qev_list_remove	(	qev_list_t *	list,
		gint32 *	idx
	)

Remove an item from the list.

Parameters

list	The list to remove the thing from
idx	Pointer to the index at which the item lives. This MUST be the same value passed to qev_list_add.

guint32 qev_list_size

(

qev_list_t *

list

)

The number of items in the list.

Parameters

list	The list to remove the thing from

Returns

The size of the list.

void* qev_list_steal	(	qev_list_t *	list,
		gint32 *	idx
	)

Steal an item from the list without calling free_fn on it.

Parameters

list	The list to remove the thing from
idx	Pointer to the index at which the item lives. This MUST be the same value passed to qev_list_add.

Returns

The item that used to exist at idx.

gboolean qev_list_try_add	(	qev_list_t *	list,
		void *	thing,
		gint32 *	idx
	)

Insert an item into the list without blocking.

If the item cannot be inserted, even if max_size is larger than the current size, FALSE will be returned. Use qev_list_add() to wait for the item to be added if it can be.

Parameters

list	The list to insert into
thing	The thing to add to the list. MAY NOT BE NULL.
idx	A pointer to a gint32 that exists for the liftetime of thing; this value will change as the item is moved around in the queue, and it MUST be treated as read-only. If you don't care about the item's position, NULL is fine. [allow-null]

Returns

If the item was inserted into the list.