list.h File Reference

(2023-08-28, commit: 9fd4610)

#include <stdlib.h>

Include dependency graph for list.h:

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

Go to the source code of this file.

Classes
struct	crinitList

Macros
#define	container_of(ptr, type, member)   ((type *)((char *)(ptr)-offsetof(type, member)))
#define	CRINIT_LIST_INIT(list)    { &(list), &(list) }
#define	crinitListEntry(entry, type, member)   container_of(entry, type, member)
#define	crinitListFirstEntry(list, type, member)   crinitListEntry((list)->next, type, member)
#define	crinitListLastEntry(list, type, member)   crinitListEntry((list)->prev, type, member)
#define	crinitListPrevEntry(entry, member)   crinitListEntry((entry)->member.prev, __typeof(*(entry)), member)
#define	crinitListNextEntry(entry, member)   crinitListEntry((entry)->member.next, __typeof(*(entry)), member)
#define	crinitListEntryIsHead(entry, list, member)   (&(entry)->member == (list))
#define	crinitListForEachEntry(entry, list, member)
#define	crinitListForEachEntrySafe(entry, temp, list, member)

Typedefs
typedef struct crinitList	crinitList_t
typedef int(*	crinitListCmp_t) (crinitList_t *e1, crinitList_t *e2)

Functions
static void	crinitListInit (crinitList_t *list)
static void	crinitListInsert (crinitList_t *entry, crinitList_t *prev, crinitList_t *next)
static void	crinitListPrepend (crinitList_t *list, crinitList_t *entry)
static void	crinitListAppend (crinitList_t *list, crinitList_t *entry)
static void	crinitListInsertSorted (crinitList_t *list, crinitList_t *entry, crinitListCmp_t entryCmp)
static void	crinitListDelete (crinitList_t *entry)
static int	crinitListIsEmpty (const crinitList_t *list)

Detailed Description

Implementation of a doubly linked intrusive list.

Intrusive lists use a list structure containing a next pointer pointing to the next list element for singly linked list and a next and prev pointer pointing to the next and previous element for a doubly linked list. This list type gets embedded into the entry type struct which should be listed. With the help of a container_of macro the parent struct can be retrived for a given list entry. To construct a list a list head is generated, which is not embedded into the struct managed in the list. This head points to the first (head->next) and last (head-prev) entry in the list or to itself, if the list is empty. Thus iterating the list is as simple as starting at head->next and iterating through the entries with cur->next, until cur->next points to head again.

Macro Definition Documentation

container_of

#define container_of	(		ptr,
			type,
			member
	)		((type *)((char *)(ptr)-offsetof(type, member)))

Macro to find the container struct to a given struct field.

Parameters

ptr	Pointer to the field in the structure.
type	Type of the container wrapping the field.
member	Name of the field the pointer points to.

CRINIT_LIST_INIT

#define CRINIT_LIST_INIT

(

list

)

{ &(list), &(list) }

Initializes a new list head by pointing the previous and next pointer to itself.

Parameters

list	List to be initialized.

crinitListEntry

#define crinitListEntry	(		entry,
			type,
			member
	)		container_of(entry, type, member)

Return the struct containing this list pointer,

Parameters

entry	Pointer to the list entry.
type	Type of the containing struct.
member	Name of the list member within the container type.

crinitListEntryIsHead

#define crinitListEntryIsHead	(		entry,
			list,
			member
	)		(&(entry)->member == (list))

Returns wether the current container entry contains the list head.

Parameters

entry	Current container entry.
list	Pointer to the list head.
member	Name of the list member within the container type.

crinitListFirstEntry

#define crinitListFirstEntry	(		list,
			type,
			member
	)		crinitListEntry((list)->next, type, member)

Return the containing entry for the first list entry,

Parameters

list	Pointer to the list head.
type	Type of the containing struct.
member	Name of the list member within the container type.

crinitListForEachEntry

#define crinitListForEachEntry	(		entry,
			list,
			member
	)

Value:

    for ((entry) = crinitListFirstEntry(list, __typeof(*(entry)), member); \
         !crinitListEntryIsHead(entry, list, member); (entry) = crinitListNextEntry(entry, member))

Iterates over all entries in the list.

Parameters

entry	Current container entry.
list	Pointer to the list head.
member	Name of the list member within the container type.

crinitListForEachEntrySafe

#define crinitListForEachEntrySafe	(		entry,
			temp,
			list,
			member
	)

Value:

    for ((entry) = crinitListFirstEntry(list, __typeof(*(entry)), member), \
        (temp) = crinitListNextEntry(entry, member);                       \
         !crinitListEntryIsHead(entry, list, member); (entry) = (temp), (temp) = crinitListNextEntry(temp, member))

Safely iterates over all entries in the list.

This macro additionally keeps track of the next entry of the current entry, so the loop won't break if the current entry gets removed from the list.

Parameters

entry	Current container entry.
temp	Temporary pointer, pointing to the next entry of the current container entry.
list	Pointer to the list head.
member	Name of the list member within the container type.

crinitListLastEntry

#define crinitListLastEntry	(		list,
			type,
			member
	)		crinitListEntry((list)->prev, type, member)

Return the containing entry for the last list entry,

Parameters

list	Pointer to the list head.
type	Type of the containing struct.
member	Name of the list member within the container type.

crinitListNextEntry

#define crinitListNextEntry	(		entry,
			member
	)		crinitListEntry((entry)->member.next, __typeof(*(entry)), member)

Return the next containing entry for the current entry,

Parameters

entry	Current container entry.
member	Name of the list member within the container type.

crinitListPrevEntry

#define crinitListPrevEntry	(		entry,
			member
	)		crinitListEntry((entry)->member.prev, __typeof(*(entry)), member)

Return the previous containing entry for the current entry,

Parameters

entry	Current container entry.
member	Name of the list member within the container type.

Typedef Documentation

crinitList_t

typedef struct crinitList crinitList_t

Simple intrusive list struct.

crinitListCmp_t

typedef int(* crinitListCmp_t) (crinitList_t *e1, crinitList_t *e2)

Type for a list entry compare function.

The comparison function shall return a value > 0, if the container type of e2 is larger than the one of e2, a value < 0 if less than the one of e2 and 0 if they are equal.

Function Documentation

crinitListAppend()

static void crinitListAppend ( crinitList_t *  list, crinitList_t *  entry  )

inlinestatic

Appends a new entry at the end of the list.

Parameters

list	Pointer to the list.
entry	Entry to be appended.

crinitListDelete()

static void crinitListDelete ( crinitList_t *  entry )

inlinestatic

Deletes the current entry from the list.

Removes the entry from the list by updating the next pointer of the previous and the prev pointer of the next entry, while setting the next and prev pointers of the entry itself to null. However this will cause a stack error if either entry, entry->next or entry->prev is NULL.

Parameters

entry

Entry to be removed from the list.

crinitListInit()

static void crinitListInit ( crinitList_t *  list )

inlinestatic

Initializes a new list head by pointing the previous and next pointer to itself.

Parameters

list	Pointer to list to be initialized.

crinitListInsert()

static void crinitListInsert ( crinitList_t *  entry, crinitList_t *  prev, crinitList_t *  next  )

inlinestatic

Insert a new list entry.

Parameters

entry	Entry to be inserted.
prev	Entry to be inserted after.
next	Entry to be inserted before.

crinitListInsertSorted()

static void crinitListInsertSorted ( crinitList_t *  list, crinitList_t *  entry, crinitListCmp_t  entryCmp  )

inlinestatic

Insert sorted based on a simple comparison callback.

Parameters

list	List to insert the entry into.
entry	Entry to be inserted.
entryCmp	Compare callback.

crinitListIsEmpty()

static int crinitListIsEmpty ( const crinitList_t *  list )

inlinestatic

Returns wether the list is empty or not.

Checks if the list is empty by checking if the next pointer of the list points to the list itself.

Parameters

list	The list to be checked.

Returns

int Returns true if list is empty, false otherwise.

crinitListPrepend()

static void crinitListPrepend ( crinitList_t *  list, crinitList_t *  entry  )

inlinestatic

Insert a new entry at the beginning of the list.

Parameters

list	Pointer to the list.
entry	Entry to be appended.