slist.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	SlNode_t_

Macros
#define	SlInitHead(_head)   (_head)->Next = NULL;
#define	SlAddNodeToHead(_head, _node)   SlInsertNodeAfter(_head, _node)
#define	SlIsListEmpty(_head)   ((_head)->Next == NULL)
#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	SlForEachNode(_head, _node)   for ((_node) = (_head)->Next; (_node) != NULL; (_node) = (_node)->Next)

Typedefs
typedef struct SlNode_t_	SlNode_t

Functions
void	SlAddNodeToTail (SlNode_t *Head, SlNode_t *Node)
SlNode_t *	SlRemoveNodeFromHead (SlNode_t *Head)
SlNode_t *	SlRemoveNodeFromTail (SlNode_t *Head)
void	SlInsertNodeAfter (SlNode_t *Marker, SlNode_t *Node)
void	SlInsertNodeBefore (SlNode_t *Head, SlNode_t *Marker, SlNode_t *Node)
void	SlRemoveNode (SlNode_t *Head, SlNode_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 180 of file slist.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 166 of file slist.h.

SlAddNodeToHead

#define SlAddNodeToHead	(		_head,
			_node
	)		SlInsertNodeAfter(_head, _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 79 of file slist.h.

SlForEachNode

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

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

This will work for an empty list.

Parameters

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

Definition at line 195 of file slist.h.

SlInitHead

#define SlInitHead

(

_head

)

(_head)->Next = NULL;

Macro to initialize a list head.

Parameters

_head

A pointer to the list head.

Definition at line 68 of file slist.h.

SlIsListEmpty

#define SlIsListEmpty

(

_head

)

((_head)->Next == NULL)

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 120 of file slist.h.

Typedef Documentation

SlNode_t

typedef struct SlNode_t_ SlNode_t

The singly linked list structure.

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

These lists offer the smallest storage overhead (one pointer per item), but many operations may take O(n) time.

Function Documentation

SlAddNodeToTail()

void SlAddNodeToTail	(	SlNode_t *	Head,
		SlNode_t *	Node
	)

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

Parameters

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

Definition at line 44 of file slist.c.

SlInsertNodeAfter()

void SlInsertNodeAfter	(	SlNode_t *	Marker,
		SlNode_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 68 of file slist.c.

SlInsertNodeBefore()

void SlInsertNodeBefore	(	SlNode_t *	Head,
		SlNode_t *	Marker,
		SlNode_t *	Node
	)

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

Parameters

Head	Pointer to the list head.
Marker	Node you are inserting before. Cannot be NULL.
Node	The node you are inserting. Cannot be NULL.

Definition at line 87 of file slist.c.

SlRemoveNode()

void SlRemoveNode	(	SlNode_t *	Head,
		SlNode_t *	Node
	)

Removes a node from the list. Runs in O(n) time worst case.

Parameters

Head	Pointer to the list head.
Node	The node you are removing.

Definition at line 127 of file slist.c.

SlRemoveNodeFromHead()

SlNode_t* SlRemoveNodeFromHead

(

SlNode_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 162 of file slist.c.

SlRemoveNodeFromTail()

SlNode_t* SlRemoveNodeFromTail

(

SlNode_t *

Head

)

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

Parameters

Head	A pointer to the existing list head.

Returns

The node removed, or NULL for an empty list.

Definition at line 181 of file slist.c.