This module provides a double linked list implementation. More...

Typedefs
typedef struct dlist	dlist_t
	Opaque type for list.
Functions
dlist_t *	dlist_new ()
	Constructor that allocates a new (empty) list.
dlist_t *	dlist_slice (dlist_t *l, unsigned from, unsigned to, dcopy_cb_t cp)
	Constructor that allocates a list basing on slicing.
dlist_t *	dlist_copy (dlist_t *l, dcopy_cb_t cp)
	Constructor that makes a shallow copy of the list.
dlist_t *	dlist_sort (dlist_t *l, dcmp_cb_t cmp)
	Sort the list.
void	dlist_free (dlist_t *l, dfree_cb_t f)
	Free the given list.
dlist_t *	dlist_append (dlist_t l, void o)
	Append an object.
dlist_t *	dlist_push (dlist_t l, void o)
	Push an object.
dlist_t *	dlist_pop (dlist_t l, void *o)
	Pop an object.
int	dlist_empty (dlist_t *l)
	Check if the list is empty.
dlist_t *	dlist_foreach (dlist_t l, diter_cb_t f, void ud)
	Run a callback on each element of the list.
dlist_t *	dlist_filter (dlist_t l, dfilter_cb_t f, void ud)
	Filter elements of the list.
diter_t *	dlist_iter_new (dlist_t *l, dcprm_t cprm)
	Build an iterator for the list.
void	dlist_iter_free (diter_t *i)
	Destroy the iterator.

Detailed Description

This module provides a double linked list implementation.

Using this module is pretty straightforward. Those lists can be used to achieve all list-related operations, like push, append, and pop. This can also be used to implement a stack semantics.

Allocation and deallocation:

There are two ways of allocating a dlist_t object: by use of the normal constructor dlist_new() or by the dlist_slice(), which allows to get a new, indipendent list as a piece of the one given as parameter.

For ones who are familiar with Python, this is similar to the slice operation on iterable elements. Note that a list produced by means of dlist_slice is a shallow copy: it must be deallocated indipendendently from the original one, while the contained objects must be freed just one time! You should avoid double free corruptions.

Assignment semantics:

In order to make the implementation more simple, every provided function (except dlist_free) returns a pointer to a dlist_t object. This entails that every operation on the lists corresponds to an assignment:

dlist_t *lst = dlist_new();
int value = 3;

// Append the value to the list
lst = dlist_append(lst, (void *)value);

// Extract the first value stored in the list
lst = dlist_pop(lst, (void **)&value);

dlist_free(lst);

Function Documentation

dlist_t* dlist_append	(	dlist_t *	l,
		void *	o
	)

Append an object.

The object is inserted in the last position of the list. This operation has cost O(1).

Parameters:

[in]	l	The list on which the new object must be appended;
[in]	o	The object to append;

Returns:: The new head of the list.

dlist_t* dlist_copy	(	dlist_t *	l,
		dcopy_cb_t	cp
	)

Constructor that makes a shallow copy of the list.

Parameters:

[in]	l	The list to be copied;
[in]	cp	The copy-constructor callback to be used for copying items. Provide NULL in order to copy values directly.

Returns:: The new list.

int dlist_empty ( dlist_t * l )

Check if the list is empty.

Parameters:

[in] l The list to be checked;

Returns:: 1 if the list is empty, 0 otherwise.

dlist_t* dlist_filter	(	dlist_t *	l,
		dfilter_cb_t	f,
		void *	ud
	)

Filter elements of the list.

This function allows to selectively remove elements from the list by iterating on each element as dlist_foreach does.

Parameters:

[in]	l	The list on which iterate;
[in]	f	The function to be called on each object stored in the list;
[in]	ud	Some generic user data;

Returns:: The new head of the list.

See also:: dfilter_cb_t for further information.

You may feel not comfortable with this approach for object iteration. If so you may prefer iterators:

See also:: diter_t data type;; dlist_iter_new function;; dlist_iter_free function.

dlist_t* dlist_foreach	(	dlist_t *	l,
		diter_cb_t	f,
		void *	ud
	)

Run a callback on each element of the list.

Parameters:

l	The list on which iterate;
f	The function to be applied to each object stored in the list;
ud	Some generic user data;

Returns:: The new head of the list.

See also:: diter_cb_t callback type;

You may feel not comfortable with this approach for object iteration. If so you may prefer iterators:

See also:: diter_t data type;; dlist_iter_new function;; dlist_iter_free function.

void dlist_free	(	dlist_t *	l,
		dfree_cb_t	f
	)

Free the given list.

Parameters:

[in]	l	The list to be deallocated;
[in]	f	The callback used to deallocate stored values (you may provide NULL if the elements must not be freed).

void dlist_iter_free ( diter_t * i )

Destroy the iterator.

Parameters:

[in] i The iterator to destroy.

See also:: diter_t for further information.

diter_t* dlist_iter_new	(	dlist_t **	l,
		dcprm_t *	cprm
	)

Build an iterator for the list.

Warning:: As you may have noticed, this function requires as parameter a pointer pointer. This inherently means that the list you'll be passed may be modified by the iterator. Be aware of this and don't mess with the list while iterating on it!

Parameters:

[in]	l	A pointer to the list on which the iterator must be built;
[in]	cprm	An optional copy/remove semantics for the objects stored in the list. The destructor is used for diter_remove(), while diter_replace() uses both the copy-constructor and the destructor.

Returns:: The iterator.

See also:: dcprm_t;; diter_t for further information.

dlist_t* dlist_new ( )

Constructor that allocates a new (empty) list.

Returns:: The new list.

dlist_t* dlist_pop	(	dlist_t *	l,
		void **	o
	)

Pop an object.

The object stored in the first position gets removed from the list and the o pointer gets updated. If the list is empty the o pointer is set to null.

Parameters:

[in]	l	The list from which the object will be removed;
[in]	o	A pointer to the location in which the removed object address will be stored;

Returns:: The new head of the list.

dlist_t* dlist_push	(	dlist_t *	l,
		void *	o
	)

Push an object.

The object is inserted in the first position of the list. This operation has cost O(1).

Parameters:

[in]	l	The list on which the new object must be pushed;
[in]	o	The object to pushed;

Returns:: The new head of the list.

dlist_t* dlist_slice	(	dlist_t *	l,
		unsigned	from,
		unsigned	to,
		dcopy_cb_t	cp
	)

Constructor that allocates a list basing on slicing.

This function returns a newly allocated list, independent from the one passed as first parameter, that must be freed with dlist_free, however contained elements are exactly the ones that have been selected from l.

In other words this function achieves a shallow copy of part of the original list.

Parameters:

[in]	l	The list to be sliced;
[in]	from	The index of the first element to be taken;
[in]	to	The index of the first element to be excluded;
[in]	cp	Copy-constructor callback to be used for copying items. Provide NULL in order to copy values directly.

Returns:: The newly allocated list.

dlist_t* dlist_sort	(	dlist_t *	l,
		dcmp_cb_t	cmp
	)

Sort the list.

Given a list, sort it with the order given by the cmp callback.

Parameters:

[in]	l	The list to be sorted;
[in]	cmp	The comparsion function to be used for sorting;

Returns:: The new head of the list.

Typedefs

Functions

Detailed Description

Allocation and deallocation:

Assignment semantics:

Function Documentation