dlist.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	DlNode_t_

Macros
#define	DlInitHead(_head)
#define	DlIsListEmpty(_head)   ((_head)->Next == _head)
#define	OFFSET_OF(_type, _field)   ((size_t)&((_type *)0)->_field)
#define	CONTAINING_RECORD(_address, _type, _field)   ((_type *)((unsigned char *)(_address) - OFFSET_OF(_type, _field)))
#define	DlForEachNode(_head, _node)   for ((_node) = (_head)->Next; (_node) != (_head); (_node) = (_node)->Next)
#define	DlForEachNodeReverse(_head, _node)   for ((_node) = (_head)->Prev; (_node) != (_head); (_node) = (_node)->Prev)

Typedefs
typedef struct DlNode_t_	DlNode_t

Functions
void	DlAddNodeToHead (DlNode_t *Head, DlNode_t *Node)
void	DlAddNodeToTail (DlNode_t *Head, DlNode_t *Node)
DlNode_t *	DlRemoveNodeFromHead (DlNode_t *Head)
DlNode_t *	DlRemoveNodeFromTail (DlNode_t *Head)
void	DlInsertNodeAfter (DlNode_t *Marker, DlNode_t *Node)
void	DlInsertNodeBefore (DlNode_t *Marker, DlNode_t *Node)
void	DlRemoveNode (DlNode_t *Node)

Macro Definition Documentation

CONTAINING_RECORD

#define CONTAINING_RECORD	(		_address,
			_type,
			_field
	)		((_type *)((unsigned char *)(_address) - OFFSET_OF(_type, _field)))

Given here in case you do not have an equivalent macro.

Parameters

_address	The real address of the _field you have.
_type	The structure type.
_field	The name of the field you want the offset to.

Returns

A typed pointer to the structure containing the _field at _address.

Definition at line 184 of file dlist.h.

DlForEachNode

#define DlForEachNode	(		_head,
			_node
	)		for ((_node) = (_head)->Next; (_node) != (_head); (_node) = (_node)->Next)

Macro to ease walking through all of the nodes in a list. Runs in O(n) time.

Parameters

_head	A pointer to the list head. Cannot be NULL.
_node	An DlNode_t pointer that you need to define before calling this macro.

Definition at line 197 of file dlist.h.

DlForEachNodeReverse

#define DlForEachNodeReverse	(		_head,
			_node
	)		for ((_node) = (_head)->Prev; (_node) != (_head); (_node) = (_node)->Prev)

Macro to ease walking through all of the nodes in a list. Runs in O(n) time.

Parameters

_head	A pointer to the list head. Cannot be NULL.
_node	An DlNode_t pointer that you need to define before calling this macro.

Definition at line 208 of file dlist.h.

DlInitHead

#define DlInitHead

(

_head

)

Value:

{                               \
    (_head)->Next = (_head);    \
    (_head)->Prev = (_head);    \
}

Macro to initialize a list head.

Parameters

_head

Pointer to the list head.

Definition at line 73 of file dlist.h.

DlIsListEmpty

#define DlIsListEmpty

(

_head

)

((_head)->Next == _head)

Check if the list is empty.

Parameters

_head

A pointer to the existing list head.

Returns

true if the list is empty, false otherwise.

Definition at line 128 of file dlist.h.

OFFSET_OF

#define OFFSET_OF	(		_type,
			_field
	)		((size_t)&((_type *)0)->_field)

Given here in case you do not have an equivalent macro.

Parameters

_type	The structure type.
_field	The name of the field you want the offset to.

Returns

The offset into _type where _field starts, in bytes.

Definition at line 170 of file dlist.h.

Typedef Documentation

DlNode_t

typedef struct DlNode_t_ DlNode_t

The doubly linked list structure.

This is designed to be embedded within your data structure(s).

These lists require more storage overhead than a singly linked list (two pointers per item), but almost all operations take O(1) time.

Function Documentation

DlAddNodeToHead()

void DlAddNodeToHead	(	DlNode_t *	Head,
		DlNode_t *	Node
	)

Add a node to the list head. Runs in O(1) time.

Parameters

Head	A pointer to the existing list head.
Node	A pointer to the node you are adding.

Definition at line 68 of file dlist.c.

DlAddNodeToTail()

void DlAddNodeToTail	(	DlNode_t *	Head,
		DlNode_t *	Node
	)

Add a node to the list tail. Runs in O(1) time.

Parameters

Head	A pointer to the existing list head.
Node	A pointer to the node you are adding.

Definition at line 75 of file dlist.c.

DlInsertNodeAfter()

void DlInsertNodeAfter	(	DlNode_t *	Marker,
		DlNode_t *	Node
	)

Inserts a new node into the list right after the marker element. Runs in O(1) time.

Parameters

Marker	The node you are inserting after. Cannot be NULL.
Node	The node you are inserting. Cannot be NULL.

Definition at line 44 of file dlist.c.

DlInsertNodeBefore()

void DlInsertNodeBefore	(	DlNode_t *	Marker,
		DlNode_t *	Node
	)

Inserts a new node into the list right before the marker element. Runs in O(1) time.

Parameters

Marker	Node you are inserting before. Cannot be NULL.
Node	The node you are inserting. Cannot be NULL.

Definition at line 61 of file dlist.c.

DlRemoveNode()

void DlRemoveNode

(

DlNode_t *

Node

)

Removes a node from the list. Runs in O(1) time.

Parameters

Node	The node you are removing.

Definition at line 82 of file dlist.c.

DlRemoveNodeFromHead()

DlNode_t* DlRemoveNodeFromHead

(

DlNode_t *

Head

)

Removes the node from the list head. Runs in O(1) time.

Parameters

Head	A pointer to the existing list head.

Returns

The node removed, or NULL for an empty list.

Definition at line 92 of file dlist.c.

DlRemoveNodeFromTail()

DlNode_t* DlRemoveNodeFromTail

(

DlNode_t *

Head

)

Removes the node from the list tail. Runs in O(1) time.

Parameters

Head	A pointer to the existing list head.

Returns

The node removed, or NULL for an empty list.

Definition at line 112 of file dlist.c.