Doubly-linked list

A linked list allowing traversal in both directions. More...

Data Structures
struct	cstl_dlist_node
	Node to anchor an element within a list. More...
struct	cstl_dlist
	List object. More...

Macros
#define	CSTL_DLIST_INITIALIZER(NAME, TYPE, MEMB)
	Constant initialization of a list object.
#define	DECLARE_CSTL_DLIST(NAME, TYPE, MEMB)
	(Statically) declare and initialize a list

Enumerations
enum	cstl_dlist_foreach_dir_t { CSTL_DLIST_FOREACH_DIR_FWD , CSTL_DLIST_FOREACH_DIR_REV }
	The direction in which to traverse the list during cstl_dlist_foreach() More...

Functions
static void	cstl_dlist_init (struct cstl_dlist *const l, const size_t off)
	Initialize a list object.
static size_t	cstl_dlist_size (const struct cstl_dlist *const l)
	Get the number of objects in the list.
void	cstl_dlist_insert (struct cstl_dlist *l, void *before, void *obj)
	Insert a new object into the list.
void	cstl_dlist_erase (struct cstl_dlist *l, void *obj)
	Remove an object from the list.
void *	cstl_dlist_front (struct cstl_dlist *l)
	Get a pointer to the first object in the list.
void *	cstl_dlist_back (struct cstl_dlist *l)
	Get a pointer to the last object in the list.
void	cstl_dlist_push_front (struct cstl_dlist *l, void *obj)
	Insert a new object at the front of the list.
void	cstl_dlist_push_back (struct cstl_dlist *l, void *obj)
	Insert a new object at the back of the list.
void *	cstl_dlist_pop_front (struct cstl_dlist *l)
	Remove the first item in the list and return it.
void *	cstl_dlist_pop_back (struct cstl_dlist *l)
	Remove the last item in the list and return it.
void	cstl_dlist_reverse (struct cstl_dlist *l)
	Reverse the order of items in the list.
void	cstl_dlist_sort (struct cstl_dlist *l, cstl_compare_func_t *cmp, void *priv)
	Sort the items in a list.
void	cstl_dlist_concat (struct cstl_dlist *list, struct cstl_dlist *more)
	Append one list to the end of another.
int	cstl_dlist_foreach (struct cstl_dlist *l, cstl_visit_func_t *visit, void *priv, cstl_dlist_foreach_dir_t dir)
	Call a user-supplied function for each object in a list.
void *	cstl_dlist_find (const struct cstl_dlist *l, const void *obj, cstl_compare_func_t *cmp, void *priv, cstl_dlist_foreach_dir_t dir)
	Perform a linear search for an object.
void	cstl_dlist_clear (struct cstl_dlist *l, cstl_xtor_func_t *clr)
	Remove objects from and reinitialize a list.
void	cstl_dlist_swap (struct cstl_dlist *a, struct cstl_dlist *b)
	Swap the list objects at the two given locations.

Detailed Description

A linked list allowing traversal in both directions.

Macro Definition Documentation

CSTL_DLIST_INITIALIZER

#define CSTL_DLIST_INITIALIZER	(		NAME,
			TYPE,
			MEMB
	)

Value:

    {                                                   \
        .h = {                                          \
            .p = &NAME.h,                               \
            .n = &NAME.h,                               \
        },                                              \
        .size = 0,                                      \
        .off = offsetof(TYPE, MEMB),                    \
    }

Constant initialization of a list object.

Parameters

NAME	The name of the variable being initialized
TYPE	The type of object that the list will hold
MEMB	The name of the cstl_dlist_node member within TYPE.

See also

cstl_dlist_node for a description of the relationship between TYPE and MEMB

Definition at line 78 of file dlist.h.

DECLARE_CSTL_DLIST

#define DECLARE_CSTL_DLIST	(		NAME,
			TYPE,
			MEMB
	)

Value:

    struct cstl_dlist NAME =                            \
        CSTL_DLIST_INITIALIZER(NAME, TYPE, MEMB)

(Statically) declare and initialize a list

Parameters

NAME	The name of the variable being declared
TYPE	The type of object that the list will hold
MEMB	The name of the cstl_dlist_node member within TYPE.

See also

cstl_dlist_node for a description of the relationship between TYPE and MEMB

Definition at line 97 of file dlist.h.

Enumeration Type Documentation

cstl_dlist_foreach_dir_t

enum cstl_dlist_foreach_dir_t

The direction in which to traverse the list during cstl_dlist_foreach()

Enumerator
CSTL_DLIST_FOREACH_DIR_FWD	Traverse the list from front to back.
CSTL_DLIST_FOREACH_DIR_REV	Traverse the list from back to front.

Definition at line 238 of file dlist.h.

Function Documentation

cstl_dlist_back()

void * cstl_dlist_back

(

struct cstl_dlist *

l

)

Get a pointer to the last object in the list.

Parameters

[in]

l

A pointer to a list

Returns

A pointer to the last object in the list

Return values

NULL	The list is empty

Definition at line 83 of file dlist.c.

cstl_dlist_clear()

void cstl_dlist_clear	(	struct cstl_dlist *	l,
		cstl_xtor_func_t *	clr
	)

Remove objects from and reinitialize a list.

Parameters

[in]	l	The list to be cleared
[in]	clr	The function to be called for each object in the list

All objects are removed from the list and the clr function is called for each object that was in the list. The order in which the objects are removed and clr is called is not specified, but the callee may take ownership of an object at the time that clr is called for that object and not before.

Upon return from this function, the list contains no objects, and it is as it was immediately after being initialized. No further operations on the list are necessary to make it ready to go out of scope or be destroyed.

Definition at line 207 of file dlist.c.

cstl_dlist_concat()

void cstl_dlist_concat	(	struct cstl_dlist *	list,
		struct cstl_dlist *	more
	)

Append one list to the end of another.

Parameters

[in]	list	The list to which to append more objects
[in]	more	The list of objects to append

Upon return list will have all of the objects from more appended to its end.

Definition at line 272 of file dlist.c.

cstl_dlist_erase()

void cstl_dlist_erase	(	struct cstl_dlist *	l,
		void *	obj
	)

Remove an object from the list.

Parameters

[in]	l	The list in which the object currently resides
[in]	obj	A pointer to the object to be removed

Definition at line 70 of file dlist.c.

cstl_dlist_find()

void * cstl_dlist_find	(	const struct cstl_dlist *	l,
		const void *	obj,
		cstl_compare_func_t *	cmp,
		void *	priv,
		cstl_dlist_foreach_dir_t	dir
	)

Perform a linear search for an object.

Parameters

[in]	l	The list to be searched
[in]	obj	A pointer to an object to search for in the list
[in]	cmp	A function to compare objects in the list
[in]	priv	A pointer to be passed to each invocation of the compare function
[in]	dir	The direction in which to traverse/search the list

The function will traverse the list in the specified direction, comparing the user-supplied object with objects in the list. When the comparison function returns 0, the associated object is returned.

Returns

A pointer to the sought object

Return values

NULL	The sought object was not found

Definition at line 165 of file dlist.c.

cstl_dlist_foreach()

int cstl_dlist_foreach	(	struct cstl_dlist *	l,
		cstl_visit_func_t *	visit,
		void *	priv,
		cstl_dlist_foreach_dir_t	dir
	)

Call a user-supplied function for each object in a list.

Parameters

[in]	l	The list containing the objects to visit
[in]	visit	A pointer to the function to call for each object
[in]	priv	A pointer to be passed to each invocation of the function
[in]	dir	The direction in which to traverse the list

The user-supplied function must return 0 in order to continue visiting objects in the list. The visiting of objects will stop at the first occurrence of a non-zero return from the visit function.

Returns

The value returned from the user-supplied function from the last object visited or 0

Definition at line 117 of file dlist.c.

cstl_dlist_front()

void * cstl_dlist_front

(

struct cstl_dlist *

l

)

Get a pointer to the first object in the list.

Parameters

[in]

l

A pointer to a list

Returns

A pointer to the first object in the list

Return values

NULL	The list is empty

Definition at line 75 of file dlist.c.

cstl_dlist_init()

static void cstl_dlist_init ( struct cstl_dlist *const  l, const size_t  off  )

inlinestatic

Initialize a list object.

Parameters

[in,out]	l	A pointer to the object to be initialized
[in]	off	The offset of the cstl_dlist_node object within the object(s) that will be stored in the list

Definition at line 108 of file dlist.h.

cstl_dlist_insert()

void cstl_dlist_insert	(	struct cstl_dlist *	l,
		void *	before,
		void *	obj
	)

Insert a new object into the list.

Parameters

[in]	l	A pointer to the list into which to insert the object
[in]	before	A pointer to an object already in the list
[in]	obj	A pointer to an object to insert into the list

The new object will be inserted after the object pointed to by before

Definition at line 52 of file dlist.c.

cstl_dlist_pop_back()

void * cstl_dlist_pop_back

(

struct cstl_dlist *

l

)

Remove the last item in the list and return it.

Parameters

[in]

l

A pointer to a list

Returns

A pointer to the removed object

Return values

NULL	The list was empty and no object was removed

Definition at line 109 of file dlist.c.

cstl_dlist_pop_front()

void * cstl_dlist_pop_front

(

struct cstl_dlist *

l

)

Remove the first item in the list and return it.

Parameters

[in]

l

A pointer to a list

Returns

A pointer to the removed object

Return values

NULL	The list was empty and no object was removed

Definition at line 101 of file dlist.c.

cstl_dlist_push_back()

void cstl_dlist_push_back	(	struct cstl_dlist *	l,
		void *	obj
	)

Insert a new object at the back of the list.

Parameters

[in]	l	A pointer to a list
[in]	obj	A pointer to the object to be inserted

Definition at line 96 of file dlist.c.

cstl_dlist_push_front()

void cstl_dlist_push_front	(	struct cstl_dlist *	l,
		void *	obj
	)

Insert a new object at the front of the list.

Parameters

[in]	l	A pointer to a list
[in]	obj	A pointer to the object to be inserted

Definition at line 91 of file dlist.c.

cstl_dlist_reverse()

void cstl_dlist_reverse

(

struct cstl_dlist *

l

)

Reverse the order of items in the list.

Parameters

[in]

l

A pointer to the list

Definition at line 219 of file dlist.c.

cstl_dlist_size()

static size_t cstl_dlist_size ( const struct cstl_dlist *const  l )

inlinestatic

Get the number of objects in the list.

Parameters

[in]

l

A pointer to the list

Returns

The number of objects in the list

Definition at line 126 of file dlist.h.

cstl_dlist_sort()

void cstl_dlist_sort	(	struct cstl_dlist *	l,
		cstl_compare_func_t *	cmp,
		void *	priv
	)

Sort the items in a list.

Parameters

[in]	l	A pointer to the list
[in]	cmp	A pointer to a function to compare objects
[in]	priv	A pointer to be passed to each invocation of the comparison function

The items are sorted from least to greatest, according to the provided comparison function.

Definition at line 292 of file dlist.c.

cstl_dlist_swap()

void cstl_dlist_swap	(	struct cstl_dlist *	a,
		struct cstl_dlist *	b
	)

Swap the list objects at the two given locations.

Parameters

[in,out]	a	A pointer to a list
[in,out]	b	A pointer to a(nother) list

The lists at the given locations will be swapped such that upon return, a will contain the list previously pointed to by b and vice versa.

Definition at line 184 of file dlist.c.