llist.h File Reference

Go to the source code of this file.

Description

Intrusive cyclic double linked list There is only one node type which contains a forward and a backward pointer.

In a empty initialised node, this pointers point to the node itself. Note that these pointers can never ever become NULL. This lists are used by using one node as 'root' node where its both pointers are the head/tail pointer to the actual list. Care needs to be taken to ensure not to apply any operations meant to be applied to data nodes to the root node. This way is the preferred way to use this lists. Alternatively one can store only a chain of data nodes and use a LList pointer to point to the first item (which might be NULL in case no data is stored). When using the 2nd approach care must be taken since most functions below expect lists to have a root node.

This header can be used in 2 different ways: 1) (preferred) just including it provides all functions as static inlined functions. This is the default 2) #define LLIST_INTERFACE before including this header gives only the declarations #define LLIST_IMPLEMENTATION before including this header yields in definitions this can be used to generate a library. This is currently untested and not recommended. The rationale for using inlined functions is that most functions are very small and likely to be used in performance critical parts. Inlining can give a huge performance and optimisation improvement here. The few functions which are slightly larger are expected to be the less common used ones, so inlining them too shouldn't be a problem either

Definition in file llist.h.

#include <stddef.h>

Classes
struct	llist

Typedefs
typedef const llist *	const_LList
typedef llist *	LList
typedef int(*	llist_cmpfn) (const_LList a, const_LList b, void *extra)
	The comparison function function type. More...
typedef llist **	LList_ref

Macros
#define	LLIST_AUTO(name)   llist name = {&name,&name}
	Macro to instantiate a local llist. More...
#define	LLIST_DEFINED
#define	LLIST_FOREACH(list, node)
	Iterate forward over a list. More...
#define	LLIST_FOREACH_REV(list, node)
	Iterate backward over a list. More...
#define	LLIST_FORRANGE(start, end, node)
	Iterate forward over a range. More...
#define	LLIST_FORRANGE_REV(rstart, rend, node)
	Iterate backward over a range. More...
#define	LLIST_FUNC(proto, ...)   LLIST_MACRO proto { __VA_ARGS__ }
#define	llist_head   llist_next
#define	llist_insert_head(list, element)   llist_insert_next (list, element)
#define	llist_insert_tail(list, element)   llist_insert_prev (list, element)
#define	LLIST_MACRO   static
#define	llist_tail   llist_prev
#define	LLIST_TO_STRUCTP(llist, type, member)   ((type*)(((char*)(llist)) - offsetof(type, member)))
	cast back from a member of a structure to a pointer of the structure
#define	LLIST_WHILE_HEAD(list, head)
	Consume a list from head. More...
#define	LLIST_WHILE_TAIL(list, tail)
	Consume a list from tail. More...

Functions
const_LList llist_cmpfn void	LLIST_FOREACH (self, node)
	LLIST_FUNC (LList llist_init(LList self), return self->next=self->prev=self;)
	Initialise a new llist. More...
	LLIST_FUNC (int llist_is_empty(const_LList self), return self->next==self;)
	Check if a node is not linked with some other node.
	LLIST_FUNC (int llist_is_single(const_LList self), return self->next->next==self;)
	Check if self is the only node in a list or self is not in a list. More...
	LLIST_FUNC (int llist_is_head(const_LList self, const_LList head), return self->next==head;)
	Check for the head of a list. More...
	LLIST_FUNC (int llist_is_tail(const_LList self, const_LList tail), return self->prev==tail;)
	Check for the tail of a list. More...
	LLIST_FUNC (int llist_is_end(const_LList self, const_LList end), return self==end;)
	Check for the end of a list. More...
	LLIST_FUNC (int llist_is_member(const_LList self, const_LList member), for(const_LList i=member->next;i !=member;i=i->next) { if(i==self) return 1;} return 0;)
	Check if a node is a member of a list. More...
	LLIST_FUNC (int llist_is_before_after(const_LList self, const_LList before, const_LList after), for(const_LList i=before->next;i !=self;i=i->next) { if(i==after) return 1;} return 0;)
	Check the order of elements in a list. More...
	LLIST_FUNC (unsigned llist_count(const_LList self), unsigned cnt=0;const_LList i=self;for(;i->next !=self;++cnt, i=i->next);return cnt;)
	Count the nodes of a list. More...
	LLIST_FUNC (void llist_unlink_fast_(LList self), LList nxt=self->next, pre=self->prev;nxt->prev=pre;pre->next=nxt;)
	LLIST_FUNC (LList llist_unlink(LList self), llist_unlink_fast_(self);return self->next=self->prev=self;)
	Remove a node from a list. More...
	LLIST_FUNC (LList llist_relocate(LList self), return self->next->prev=self->prev->next=self;)
	Fix a node which got relocated in memory. More...
	LLIST_FUNC (LList llist_insert_next(LList self, LList next), llist_unlink_fast_(next);self->next->prev=next;next->prev=self;next->next=self->next;self->next=next;return self;)
	Insert a node after another. More...
	LLIST_FUNC (LList llist_insert_prev(LList self, LList prev), llist_unlink_fast_(prev);self->prev->next=prev;prev->next=self;prev->prev=self->prev;self->prev=prev;return self;)
	Insert a node before another. More...
	LLIST_FUNC (LList llist_insertlist_next(LList self, LList next), if(!llist_is_empty(next)) { self->next->prev=next->prev;next->prev->next=self->next;self->next=next->next;next->next->prev=self;next->prev=next->next=next;} return self;)
	Move the content of a list after a node in another list. More...
	LLIST_FUNC (LList llist_insertlist_prev(LList self, LList prev), if(!llist_is_empty(prev)) { self->prev->next=prev->next;prev->next->prev=self->prev;self->prev=prev->prev;prev->prev->next=self;prev->prev=prev->next=prev;} return self;)
	Move the content of a list before a node in another list. More...
	LLIST_FUNC (LList llist_advance(LList self), LList tmp=self->next->next;tmp->prev=self;self->next->prev=self->prev;self->prev->next=self->next;self->prev=self->next;self->next->next=self;self->next=tmp;return self;)
	Swap a node with its next node. More...
	LLIST_FUNC (LList llist_next(const_LList self), return self->next;)
	Get next node. More...
	LLIST_FUNC (LList llist_prev(const_LList self), return self->prev;)
	Get previous node. More...
	LLIST_FUNC (void llist_forward(LList_ref self), *self=(*self) ->next;)
	Advance a pointer to a node to its next node. More...
	LLIST_FUNC (LList llist_nth(LList self, int n), if(n >0) while(n--) self=llist_next(self);else while(n++) self=llist_prev(self);return self;)
	Get the nth element of a list. More...
	LLIST_FUNC (LList llist_get_nth_stop(LList self, int n, const_LList stop), if(n >0) while(n--) { self=llist_next(self);if(self==stop) return NULL;} else while(n++) { self=llist_prev(self);if(self==stop) return NULL;} return self;)
	Get the nth element of a list with a stop node. More...
	LLIST_FUNC (LList llist_sort(LList self, llist_cmpfn cmp, void *extra), llist left;llist right;llist_init(&left);llist_init(&right);unsigned n=0;if(!llist_is_single(self)) { llist_insert_prev(++n &1 ? &left :&right, head);llist_sort(&left, cmp, extra);llist_sort(&right, cmp, extra);while(!llist_is_empty(&left) &&!llist_is_empty(&right)) llist_insert_prev(self, cmp(left.next, right.next, extra)< 0 ? left.next :right.next);if(!llist_is_empty(&left)) llist_insertlist_prev(self, &left);if(!llist_is_empty(&right)) llist_insertlist_prev(self, &right);} return self;) LLIST_FUNC(LList llist_find(const_LList self
	Sort a list. More...
	LLIST_FUNC (LList llist_ufind(LList self, const_LList templ, llist_cmpfn cmp, void *extra), LLIST_FOREACH(self, node) { if(!cmp(node, templ, extra)) { if(llist_next(self) !=node) llist_insert_next(self, node);return node;} } return NULL;) LLIST_FUNC(LList llist_sfind(const_LList self
	Find a element in a unsorted list. More...

Variables
const_LList llist_cmpfn	cmp
const_LList llist_cmpfn void *	extra
return	NULL
const_LList	templ

Typedef Documentation

llist_cmpfn

typedef int(* llist_cmpfn) (const_LList a, const_LList b, void *extra)

The comparison function function type.

certain sort and find functions depend on a user supplied comparison function

Parameters

a	first operand for the comparison
b	second operand for the comparison
extra	user supplied data which passed through

Returns

shall return a value less than zero, zero, bigger than zero when a is less than, equal to, bigger than b

Definition at line 535 of file llist.h.

Macro Definition Documentation

LLIST_AUTO

#define LLIST_AUTO

(

name

)

llist name = {&name,&name}

Macro to instantiate a local llist.

Parameters

name	of the llist node

Definition at line 89 of file llist.h.

LLIST_FOREACH

#define LLIST_FOREACH	(		list,
			node
	)

Value:

for (LList node = llist_head (list);        \
         ! llist_is_end (node, list);           \
         llist_forward (&node))

Iterate forward over a list.

Parameters

list	the root node of the list to be iterated
node	pointer to the iterated node

Definition at line 119 of file llist.h.

Referenced by lumiera_config_dump().

LLIST_FOREACH_REV

#define LLIST_FOREACH_REV	(		list,
			node
	)

Value:

for (LList node = llist_tail (list);        \
         ! llist_is_end (node, list);           \
         llist_backward (&node))

Iterate backward over a list.

Parameters

list	the root node of the list to be iterated
node	pointer to the iterated node

Definition at line 129 of file llist.h.

LLIST_FORRANGE

#define LLIST_FORRANGE	(		start,
			end,
			node
	)

Value:

for (LList node = start;                    \
         node != end;                           \
         llist_forward (&node))

Iterate forward over a range.

Parameters

start	first node to be iterated
end	node after the last node be iterated
node	pointer to the iterated node

Definition at line 141 of file llist.h.

LLIST_FORRANGE_REV

#define LLIST_FORRANGE_REV	(		rstart,
			rend,
			node
	)

Value:

for (LList node = rstart;                   \
         node != rend;                          \
         llist_backward (&node))

Iterate backward over a range.

Parameters

rstart	first node to be iterated
rend	node before the last node be iterated
node	pointer to the iterated node

Definition at line 152 of file llist.h.

LLIST_WHILE_HEAD

#define LLIST_WHILE_HEAD	(		list,
			head
	)

Value:

for (LList head = llist_head (list);        \
         !llist_is_empty (list);                \
         head = llist_head (list))

Consume a list from head.

The body of this statement should remove the head from the list, else it would be a infinite loop

Parameters

list	the root node of the list to be consumed
head	pointer to the head node

Definition at line 164 of file llist.h.

LLIST_WHILE_TAIL

#define LLIST_WHILE_TAIL	(		list,
			tail
	)

Value:

for (LList tail = llist_tail (list);        \
         !llist_is_empty (list);                \
         tail = llist_tail (list))

Consume a list from tail.

The body of this statement should remove the tail from the list, else it would be a infinite loop

Parameters

list	the root node of the list to be consumed
tail	pointer to the tail node

Definition at line 175 of file llist.h.

---

Class Documentation

llist_struct

struct llist_struct

Class Members
struct llist_struct *	next
struct llist_struct *	prev

Collaboration diagram for llist:

Function Documentation

LLIST_FUNC() [1/22]

LLIST_FUNC	(	LList	llist_initLList self,
		return self->	next = self->prev=self;
	)

Initialise a new llist.

Must not be applied to a list node which is not empty! Lists need to be initialised before any other operation on them is called.

Parameters

self	node to be initialised

LLIST_FUNC() [2/22]

LLIST_FUNC	(	int	llist_is_singleconst_LList self,
		return self->next->	next = =self;
	)

Check if self is the only node in a list or self is not in a list.

Parameters

self	node to be checked

LLIST_FUNC() [3/22]

LLIST_FUNC	(	int	llist_is_headconst_LList self, const_LList head,
		return self->	next = =head;
	)

Check for the head of a list.

Parameters

self	root of the list
head	expected head of the list

LLIST_FUNC() [4/22]

LLIST_FUNC	(	int	llist_is_tailconst_LList self, const_LList tail,
		return self->	prev = =tail;
	)

Check for the tail of a list.

Parameters

self	root of the list
tail	expected tail of the list

LLIST_FUNC() [5/22]

LLIST_FUNC	(	int	llist_is_endconst_LList self, const_LList end,
		return	self = =end;
	)

Check for the end of a list.

The end is by definition one past the tail of a list, which is the root node itself.

Parameters

self	root node of the list
end	expected end of the list

LLIST_FUNC() [6/22]

LLIST_FUNC	(	int	llist_is_memberconst_LList self, const_LList member,
		for(const_LList i=member->next;i !=member;i=i->next) { if(i==self) return 1;} return 0;
	)

Check if a node is a member of a list.

Parameters

self	root node of the list
member	node to be searched

LLIST_FUNC() [7/22]

LLIST_FUNC	(	int	llist_is_before_afterconst_LList self, const_LList before, const_LList after,
		for(const_LList i=before->next;i !=self;i=i->next) { if(i==after) return 1;} return 0;
	)

Check the order of elements in a list.

Parameters

self	root node of the list
before	expected to be before after
after	expected to be after before

LLIST_FUNC() [8/22]

LLIST_FUNC	(	unsigned	llist_countconst_LList self,
		unsigned	cnt = 0;const_LList i=self;for(;i->next !=self;++cnt, i=i->next);return cnt;
	)

Count the nodes of a list.

Parameters

self	root node of the list

Returns

number of nodes in self

LLIST_FUNC() [9/22]

LLIST_FUNC	(	LList	llist_unlinkLList self,
		llist_unlink_fast_(self);return self->	next = self->prev=self;
	)

Remove a node from a list.

Parameters

self	node to be removed

Returns

self

LLIST_FUNC() [10/22]

LLIST_FUNC	(	LList	llist_relocateLList self,
		return self->next->	prev = self->prev->next=self;
	)

Fix a node which got relocated in memory.

It is supported to realloc/move list nodes in memory but one must call 'list_relocate' after doing so. IMPORTANT: it is not possible to relocate nodes which are empty this way, nor can this be determined after the relocation, so either llist_init them afterwards or insert a bogus node before moving the node and relocating it and remove it afterwards.

Parameters

self	node which got relocated

Returns

self

LLIST_FUNC() [11/22]

LLIST_FUNC	(	LList	llist_insert_nextLList self, LList next,
		llist_unlink_fast_(next);self->next->	prev = next;next->prev=self;next->next=self->next;self->next=next;return self;
	)

Insert a node after another.

Parameters

self	node after which we want to insert
next	node which shall be inserted after self. Could already linked to a list from where it will be removed.

Returns

self

LLIST_FUNC() [12/22]

LLIST_FUNC	(	LList	llist_insert_prevLList self, LList prev,
		llist_unlink_fast_(prev);self->prev->	next = prev;prev->next=self;prev->prev=self->prev;self->prev=prev;return self;
	)

Insert a node before another.

Parameters

self	node before which we want to insert
prev	node which shall be inserted before self. Could already linked to a list from where it will be removed.

Returns

self

LLIST_FUNC() [13/22]

LLIST_FUNC	(	LList	llist_insertlist_nextLList self, LList next,
		if(!llist_is_empty(next)) { self->next->prev=next->prev;next->prev->next=self->next;self->next=next->next;next->next->prev=self;next->prev=next->next=next;} return self;
	)

Move the content of a list after a node in another list.

Parameters

self	node after which we want to insert a list
next	rootnode of the list which shall be inserted after self

Returns

self next is a empty list after this call

LLIST_FUNC() [14/22]

LLIST_FUNC	(	LList	llist_insertlist_prevLList self, LList prev,
		if(!llist_is_empty(prev)) { self->prev->next=prev->next;prev->next->prev=self->prev;self->prev=prev->prev;prev->prev->next=self;prev->prev=prev->next=prev;} return self;
	)

Move the content of a list before a node in another list.

Parameters

self	node before which we want to insert a list
prev	rootnode of the list which shall be inserted before self

Returns

self prev is a empty list after this call

LLIST_FUNC() [15/22]

LLIST_FUNC	(	LList	llist_advanceLList self,
		LList	tmp = self->next->next;tmp->prev=self;self->next->prev=self->prev;self->prev->next=self->next;self->prev=self->next;self->next->next=self;self->next=tmp;return self;
	)

Swap a node with its next node.

Swap a node with its previous node.

Parameters

self	node to be advanced

Returns

self advancing will not stop at tail, one has to check that if this is intended

Parameters

self	node to be retreated

Returns

self retreating will not stop at head, one has to check that if this is intended

LLIST_FUNC() [16/22]

LLIST_FUNC	(	LList	llist_nextconst_LList self,
		return self->next;
	)

Get next node.

Parameters

self	current node

Returns

node after self Will not stop at tail

LLIST_FUNC() [17/22]

LLIST_FUNC	(	LList	llist_prevconst_LList self,
		return self->prev;
	)

Get previous node.

Parameters

self	current node

Returns

node before self Will not stop at head

LLIST_FUNC() [18/22]

LLIST_FUNC	(	void	llist_forwardLList_ref self,
		*	self = (*self) ->next;
	)

Advance a pointer to a node to its next node.

Retreat a pointer to a node to its previous node.

Parameters

self	pointer-to-pointer to the current node *self will point to the next node after this call
self	pointer-to-pointer to the current node *self will point to the previous node after this call

LLIST_FUNC() [19/22]

LLIST_FUNC	(	LList	llist_nthLList self, int n,
		if(n >0) while(n--)	self = llist_next(self);else while(n++) self=llist_prev(self);return self;
	)

Get the nth element of a list.

Parameters

self	list to be queried
n	nth element after (positive n) or before (negative n) self this function does not stop at head/tail.

LLIST_FUNC() [20/22]

LLIST_FUNC	(	LList	llist_get_nth_stopLList self, int n, const_LList stop,
		if(n >0) while(n--) { self=llist_next(self);if(self==stop) return NULL;} else while(n++) { self=llist_prev(self);if(self==stop) return NULL;} return self;
	)

Get the nth element of a list with a stop node.

Parameters

self	list to be queried
n	nth element after (positive n) or before (negative n) self
stop	node which will abort the iteration

LLIST_FUNC() [21/22]

LLIST_FUNC	(	LList	llist_sortLList self, llist_cmpfn cmp, void *extra,
		llist left;llist right;llist_init &left;llist_init &right;unsigned	n = 0; if (!llist_is_single (self)) { llist_insert_prev (++n & 1 ? &left : &right, head); llist_sort (&left, cmp, extra); llist_sort (&right, cmp, extra); while (!llist_is_empty (&left) && !llist_is_empty (&right)) llist_insert_prev (self, cmp (left.next, right.next, extra) < 0 ? left.next : right.next); if (!llist_is_empty (&left)) llist_insertlist_prev (self, &left); if (!llist_is_empty (&right)) llist_insertlist_prev (self, &right); } return self;
	)

Sort a list.

recursive mergesort, needs much extra stackspace (crappy implementation yet) but it reasonable fast

Parameters

self	list to be sorted
cmp	function for comparing 2 nodes
extra	generic data passed to the cmp function Find a element in list. searches the list for a element. Does not change the list order.
self	list to be searched
templ	template for the element being searched
cmp	function for comparing 2 nodes

Returns

pointer to the found LList element or NULL if nothing found

LLIST_FUNC() [22/22]

LLIST_FUNC	(	LList	llist_ufindLList self, const_LList templ, llist_cmpfn cmp, void *extra,
		LLIST_FOREACH(self, node) { if(!cmp(node, templ, extra)) { if(llist_next(self) !=node) llist_insert_next(self, node);return node;} } return NULL;
	)

Find a element in a unsorted list.

searches the list until it finds the searched element and moves it then to the head. Useful if the order of the list is not required and few elements are frequently searched.

Parameters

self	list to be searched
templ	template for the element being searched
cmp	function for comparing 2 nodes

Returns

pointer to the found LList element (head) or NULL if nothing found Find a element in a sorted list. searches the list until it find the searched element, exits searching when found an element bigger than the searched one.

Parameters

self	list to be searched
templ	template for the element being searched
cmp	function for comparing 2 nodes

Returns

pointer to the found LList element or NULL if nothing found