Doubly-linked list

Macros
#define	SYS_DLIST_FOR_EACH_NODE(__dl, __dn)
	Provide the primitive to iterate on a list Note: the loop is unsafe and thus __dn should not be removed. More...
#define	SYS_DLIST_ITERATE_FROM_NODE(__dl, __dn)
	Provide the primitive to iterate on a list, from a node in the list Note: the loop is unsafe and thus __dn should not be removed. More...
#define	SYS_DLIST_FOR_EACH_NODE_SAFE(__dl, __dn, __dns)
	Provide the primitive to safely iterate on a list Note: __dn can be removed, it will not break the loop. More...
#define	SYS_DLIST_CONTAINER(__dn, __cn, __n)    ((__dn != NULL) ? CONTAINER_OF(__dn, __typeof__(*__cn), __n) : NULL)
#define	SYS_DLIST_PEEK_HEAD_CONTAINER(__dl, __cn, __n)    SYS_DLIST_CONTAINER(sys_dlist_peek_head(__dl), __cn, __n)
#define	SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n)
#define	SYS_DLIST_FOR_EACH_CONTAINER(__dl, __cn, __n)
	Provide the primitive to iterate on a list under a container Note: the loop is unsafe and thus __cn should not be detached. More...
#define	SYS_DLIST_FOR_EACH_CONTAINER_SAFE(__dl, __cn, __cns, __n)
	Provide the primitive to safely iterate on a list under a container Note: __cn can be detached, it will not break the loop. More...
#define	SYS_DLIST_STATIC_INIT(ptr_to_list)   { {(ptr_to_list)}, {(ptr_to_list)} }

Typedefs
typedef struct _dnode	sys_dlist_t
typedef struct _dnode	sys_dnode_t

Functions
static void	sys_dlist_init (sys_dlist_t *list)
	initialize list to its empty state More...
static void	sys_dnode_init (sys_dnode_t *node)
	initialize node to its state when not in a list More...
static bool	sys_dnode_is_linked (const sys_dnode_t *node)
	check if a node is a member of any list More...
static bool	sys_dlist_is_head (sys_dlist_t *list, sys_dnode_t *node)
	check if a node is the list's head More...
static bool	sys_dlist_is_tail (sys_dlist_t *list, sys_dnode_t *node)
	check if a node is the list's tail More...
static bool	sys_dlist_is_empty (sys_dlist_t *list)
	check if the list is empty More...
static bool	sys_dlist_has_multiple_nodes (sys_dlist_t *list)
	check if more than one node present More...
static sys_dnode_t *	sys_dlist_peek_head (sys_dlist_t *list)
	get a reference to the head item in the list More...
static sys_dnode_t *	sys_dlist_peek_head_not_empty (sys_dlist_t *list)
	get a reference to the head item in the list More...
static sys_dnode_t *	sys_dlist_peek_next_no_check (sys_dlist_t *list, sys_dnode_t *node)
	get a reference to the next item in the list, node is not NULL More...
static sys_dnode_t *	sys_dlist_peek_next (sys_dlist_t *list, sys_dnode_t *node)
	get a reference to the next item in the list More...
static sys_dnode_t *	sys_dlist_peek_prev_no_check (sys_dlist_t *list, sys_dnode_t *node)
	get a reference to the previous item in the list, node is not NULL More...
static sys_dnode_t *	sys_dlist_peek_prev (sys_dlist_t *list, sys_dnode_t *node)
	get a reference to the previous item in the list More...
static sys_dnode_t *	sys_dlist_peek_tail (sys_dlist_t *list)
	get a reference to the tail item in the list More...
static void	sys_dlist_append (sys_dlist_t *list, sys_dnode_t *node)
	add node to tail of list More...
static void	sys_dlist_prepend (sys_dlist_t *list, sys_dnode_t *node)
	add node to head of list More...
static void	sys_dlist_insert (sys_dnode_t *successor, sys_dnode_t *node)
	Insert a node into a list. More...
static void	sys_dlist_insert_at (sys_dlist_t *list, sys_dnode_t *node, int(*cond)(sys_dnode_t *node, void *data), void *data)
	insert node at position More...
static void	sys_dlist_remove (sys_dnode_t *node)
	remove a specific node from a list More...
static sys_dnode_t *	sys_dlist_get (sys_dlist_t *list)
	get the first node in a list More...

Detailed Description

Macro Definition Documentation

SYS_DLIST_CONTAINER

#define SYS_DLIST_CONTAINER	(		__dn,
			__cn,
			__n
	)		((__dn != NULL) ? CONTAINER_OF(__dn, __typeof__(*__cn), __n) : NULL)

#include <include/sys/dlist.h>

SYS_DLIST_FOR_EACH_CONTAINER

#define SYS_DLIST_FOR_EACH_CONTAINER	(		__dl,
			__cn,
			__n
	)

#include <include/sys/dlist.h>

Value:

        for (__cn = SYS_DLIST_PEEK_HEAD_CONTAINER(__dl, __cn, __n);     \
             __cn != NULL;                                              \
             __cn = SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n))

Provide the primitive to iterate on a list under a container Note: the loop is unsafe and thus __cn should not be detached.

User MUST add the loop statement curly braces enclosing its own code:

SYS_DLIST_FOR_EACH_CONTAINER(l, c, n) {
    <user code>
}

Parameters

__dl	A pointer on a sys_dlist_t to iterate on
__cn	A pointer to peek each entry of the list
__n	The field name of sys_dnode_t within the container struct

SYS_DLIST_FOR_EACH_CONTAINER_SAFE

#define SYS_DLIST_FOR_EACH_CONTAINER_SAFE	(		__dl,
			__cn,
			__cns,
			__n
	)

#include <include/sys/dlist.h>

Value:

        for (__cn = SYS_DLIST_PEEK_HEAD_CONTAINER(__dl, __cn, __n),     \
             __cns = SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n);    \
             __cn != NULL; __cn = __cns,                                \
             __cns = SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n))

Provide the primitive to safely iterate on a list under a container Note: __cn can be detached, it will not break the loop.

User MUST add the loop statement curly braces enclosing its own code:

SYS_DLIST_FOR_EACH_CONTAINER_SAFE(l, c, cn, n) {
    <user code>
}

Parameters

__dl	A pointer on a sys_dlist_t to iterate on
__cn	A pointer to peek each entry of the list
__cns	A pointer for the loop to run safely
__n	The field name of sys_dnode_t within the container struct

SYS_DLIST_FOR_EACH_NODE

#define SYS_DLIST_FOR_EACH_NODE	(		__dl,
			__dn
	)

#include <include/sys/dlist.h>

Value:

        for (__dn = sys_dlist_peek_head(__dl); __dn != NULL;            \
             __dn = sys_dlist_peek_next(__dl, __dn))

Provide the primitive to iterate on a list Note: the loop is unsafe and thus __dn should not be removed.

User MUST add the loop statement curly braces enclosing its own code:

SYS_DLIST_FOR_EACH_NODE(l, n) {
    <user code>
}

This and other SYS_DLIST_*() macros are not thread safe.

Parameters

__dl	A pointer on a sys_dlist_t to iterate on
__dn	A sys_dnode_t pointer to peek each node of the list

SYS_DLIST_FOR_EACH_NODE_SAFE

#define SYS_DLIST_FOR_EACH_NODE_SAFE	(		__dl,
			__dn,
			__dns
	)

#include <include/sys/dlist.h>

Value:

        for (__dn = sys_dlist_peek_head(__dl),                          \
                     __dns = sys_dlist_peek_next(__dl, __dn);           \
             __dn != NULL; __dn = __dns,                                \
                     __dns = sys_dlist_peek_next(__dl, __dn))

Provide the primitive to safely iterate on a list Note: __dn can be removed, it will not break the loop.

User MUST add the loop statement curly braces enclosing its own code:

SYS_DLIST_FOR_EACH_NODE_SAFE(l, n, s) {
    <user code>
}

This and other SYS_DLIST_*() macros are not thread safe.

Parameters

__dl	A pointer on a sys_dlist_t to iterate on
__dn	A sys_dnode_t pointer to peek each node of the list
__dns	A sys_dnode_t pointer for the loop to run safely

SYS_DLIST_ITERATE_FROM_NODE

#define SYS_DLIST_ITERATE_FROM_NODE	(		__dl,
			__dn
	)

#include <include/sys/dlist.h>

Value:

        for (__dn = __dn ? sys_dlist_peek_next_no_check(__dl, __dn) \
                         : sys_dlist_peek_head(__dl); \
             __dn != NULL; \
             __dn = sys_dlist_peek_next(__dl, __dn))

Provide the primitive to iterate on a list, from a node in the list Note: the loop is unsafe and thus __dn should not be removed.

User MUST add the loop statement curly braces enclosing its own code:

SYS_DLIST_ITERATE_FROM_NODE(l, n) {
    <user code>
}

Like SYS_DLIST_FOR_EACH_NODE(), but __dn already contains a node in the list where to start searching for the next entry from. If NULL, it starts from the head.

This and other SYS_DLIST_*() macros are not thread safe.

Parameters

__dl	A pointer on a sys_dlist_t to iterate on
__dn	A sys_dnode_t pointer to peek each node of the list; it contains the starting node, or NULL to start from the head

SYS_DLIST_PEEK_HEAD_CONTAINER

#define SYS_DLIST_PEEK_HEAD_CONTAINER	(		__dl,
			__cn,
			__n
	)		SYS_DLIST_CONTAINER(sys_dlist_peek_head(__dl), __cn, __n)

#include <include/sys/dlist.h>

SYS_DLIST_PEEK_NEXT_CONTAINER

#define SYS_DLIST_PEEK_NEXT_CONTAINER	(		__dl,
			__cn,
			__n
	)

#include <include/sys/dlist.h>

Value:

        ((__cn != NULL) ? \
         SYS_DLIST_CONTAINER(sys_dlist_peek_next(__dl, &(__cn->__n)),   \
                                      __cn, __n) : NULL)

SYS_DLIST_STATIC_INIT

#define SYS_DLIST_STATIC_INIT

(

ptr_to_list

)

{ {(ptr_to_list)}, {(ptr_to_list)} }

#include <include/sys/dlist.h>

Typedef Documentation

sys_dlist_t

typedef struct _dnode sys_dlist_t

#include <include/sys/dlist.h>

sys_dnode_t

typedef struct _dnode sys_dnode_t

#include <include/sys/dlist.h>

Function Documentation

sys_dlist_append()

static void sys_dlist_append ( sys_dlist_t *  list, sys_dnode_t *  node  )

inlinestatic

#include <include/sys/dlist.h>

add node to tail of list

This and other sys_dlist_*() functions are not thread safe.

Parameters

list	the doubly-linked list to operate on
node	the element to append

Returns

N/A

sys_dlist_get()

static sys_dnode_t * sys_dlist_get ( sys_dlist_t *  list )

inlinestatic

#include <include/sys/dlist.h>

get the first node in a list

This and other sys_dlist_*() functions are not thread safe.

Parameters

list	the doubly-linked list to operate on

Returns

the first node in the list, NULL if list is empty

sys_dlist_has_multiple_nodes()

static bool sys_dlist_has_multiple_nodes ( sys_dlist_t *  list )

inlinestatic

#include <include/sys/dlist.h>

check if more than one node present

This and other sys_dlist_*() functions are not thread safe.

Parameters

list	the doubly-linked list to operate on

Returns

true if multiple nodes, false otherwise

sys_dlist_init()

static void sys_dlist_init ( sys_dlist_t *  list )

inlinestatic

#include <include/sys/dlist.h>

initialize list to its empty state

Parameters

list	the doubly-linked list

Returns

N/A

sys_dlist_insert()

static void sys_dlist_insert ( sys_dnode_t *  successor, sys_dnode_t *  node  )

inlinestatic

#include <include/sys/dlist.h>

Insert a node into a list.

Insert a node before a specified node in a dlist.

Parameters

successor	the position before which "node" will be inserted
node	the element to insert

sys_dlist_insert_at()

static void sys_dlist_insert_at ( sys_dlist_t *  list, sys_dnode_t *  node, int(*)(sys_dnode_t *node, void *data)  cond, void *  data  )

inlinestatic

#include <include/sys/dlist.h>

insert node at position

Insert a node in a location depending on a external condition. The cond() function checks if the node is to be inserted before the current node against which it is checked. This and other sys_dlist_*() functions are not thread safe.

Parameters

list	the doubly-linked list to operate on
node	the element to insert
cond	a function that determines if the current node is the correct insert point
data	parameter to cond()

Returns

N/A

sys_dlist_is_empty()

static bool sys_dlist_is_empty ( sys_dlist_t *  list )

inlinestatic

#include <include/sys/dlist.h>

check if the list is empty

Parameters

list	the doubly-linked list to operate on

Returns

true if empty, false otherwise

sys_dlist_is_head()

static bool sys_dlist_is_head ( sys_dlist_t *  list, sys_dnode_t *  node  )

inlinestatic

#include <include/sys/dlist.h>

check if a node is the list's head

Parameters

list	the doubly-linked list to operate on
node	the node to check

Returns

true if node is the head, false otherwise

sys_dlist_is_tail()

static bool sys_dlist_is_tail ( sys_dlist_t *  list, sys_dnode_t *  node  )

inlinestatic

#include <include/sys/dlist.h>

check if a node is the list's tail

Parameters

list	the doubly-linked list to operate on
node	the node to check

Returns

true if node is the tail, false otherwise

sys_dlist_peek_head()

static sys_dnode_t * sys_dlist_peek_head ( sys_dlist_t *  list )

inlinestatic

#include <include/sys/dlist.h>

get a reference to the head item in the list

Parameters

list	the doubly-linked list to operate on

Returns

a pointer to the head element, NULL if list is empty

sys_dlist_peek_head_not_empty()

static sys_dnode_t * sys_dlist_peek_head_not_empty ( sys_dlist_t *  list )

inlinestatic

#include <include/sys/dlist.h>

get a reference to the head item in the list

The list must be known to be non-empty.

Parameters

list	the doubly-linked list to operate on

Returns

a pointer to the head element

sys_dlist_peek_next()

static sys_dnode_t * sys_dlist_peek_next ( sys_dlist_t *  list, sys_dnode_t *  node  )

inlinestatic

#include <include/sys/dlist.h>

get a reference to the next item in the list

Parameters

list	the doubly-linked list to operate on
node	the node from which to get the next element in the list

Returns

a pointer to the next element from a node, NULL if node is the tail or NULL (when node comes from reading the head of an empty list).

sys_dlist_peek_next_no_check()

static sys_dnode_t * sys_dlist_peek_next_no_check ( sys_dlist_t *  list, sys_dnode_t *  node  )

inlinestatic

#include <include/sys/dlist.h>

get a reference to the next item in the list, node is not NULL

Faster than sys_dlist_peek_next() if node is known not to be NULL.

Parameters

list	the doubly-linked list to operate on
node	the node from which to get the next element in the list

Returns

a pointer to the next element from a node, NULL if node is the tail

sys_dlist_peek_prev()

static sys_dnode_t * sys_dlist_peek_prev ( sys_dlist_t *  list, sys_dnode_t *  node  )

inlinestatic

#include <include/sys/dlist.h>

get a reference to the previous item in the list

Parameters

list	the doubly-linked list to operate on
node	the node from which to get the previous element in the list

Returns

a pointer to the previous element from a node, NULL if node is the tail or NULL (when node comes from reading the head of an empty list).

sys_dlist_peek_prev_no_check()

static sys_dnode_t * sys_dlist_peek_prev_no_check ( sys_dlist_t *  list, sys_dnode_t *  node  )

inlinestatic

#include <include/sys/dlist.h>

get a reference to the previous item in the list, node is not NULL

Faster than sys_dlist_peek_prev() if node is known not to be NULL.

Parameters

list	the doubly-linked list to operate on
node	the node from which to get the previous element in the list

Returns

a pointer to the previous element from a node, NULL if node is the tail

sys_dlist_peek_tail()

static sys_dnode_t * sys_dlist_peek_tail ( sys_dlist_t *  list )

inlinestatic

#include <include/sys/dlist.h>

get a reference to the tail item in the list

Parameters

list	the doubly-linked list to operate on

Returns

a pointer to the tail element, NULL if list is empty

sys_dlist_prepend()

static void sys_dlist_prepend ( sys_dlist_t *  list, sys_dnode_t *  node  )

inlinestatic

#include <include/sys/dlist.h>

add node to head of list

This and other sys_dlist_*() functions are not thread safe.

Parameters

list	the doubly-linked list to operate on
node	the element to append

Returns

N/A

sys_dlist_remove()

static void sys_dlist_remove ( sys_dnode_t *  node )

inlinestatic

#include <include/sys/dlist.h>

remove a specific node from a list

The list is implicit from the node. The node must be part of a list. This and other sys_dlist_*() functions are not thread safe.

Parameters

node	the node to remove

Returns

N/A

sys_dnode_init()

static void sys_dnode_init ( sys_dnode_t *  node )

inlinestatic

#include <include/sys/dlist.h>

initialize node to its state when not in a list

Parameters

node

the node

Returns

N/A

sys_dnode_is_linked()

static bool sys_dnode_is_linked ( const sys_dnode_t *  node )

inlinestatic

#include <include/sys/dlist.h>

check if a node is a member of any list

Parameters

node

the node

Returns

true if node is linked into a list, false if it is not