lib/llist.h File Reference

Detailed Description

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

In a empty initialized 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 prefered 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) (prerefered) 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 hughe performance and optimization 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>

Include dependency graph for llist.h:

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

Go to the source code of this file.

Classes

struct llist_struct

Defines

#define LLIST_AUTO(name)   llist name = {&name,&name}

Macro to instantiate a local llist.

#define LLIST_FOREACH(list, node)

Iterate forward over a list.

#define LLIST_FOREACH_REV(list, node)

Iterate backward over a list.

#define LLIST_FORRANGE(start, end, node)

Iterate forward over a range.

#define LLIST_FORRANGE_REV(rstart, rend, node)

Iterate backward over a range.

#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.

#define LLIST_WHILE_TAIL(list, tail)

Consume a list from tail.

Typedefs

typedef const llist * const_LList

typedef llist * LList

typedef struct llist_struct llist

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

The comparsion function function type.

typedef llist ** LList_ref

Functions

const_LList llist_cmpfn void LLIST_FOREACH (self, node)

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.

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.

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.

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.

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

Advance a pointer to a node to its next node.

LLIST_FUNC (LList llist_prev(const_LList self), return self->prev;)

Get previous node.

LLIST_FUNC (LList llist_next(const_LList self), return self->next;)

Get next node.

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.

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.

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.

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.

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.

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

Fix a node which got relocated in memory.

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

Remove a node from a list.

LLIST_FUNC (void llist_unlink_fast_(LList self), LList nxt=self->next, pre=self->prev;nxt->prev=pre;pre->next=nxt;)

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.

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.

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.

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

Check for the end of a list.

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

Check for the tail of a list.

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

Check for the head of a list.

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.

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 (LList llist_init(LList self), return self->next=self->prev=self;)

Initialize a new llist.

Variables

const_LList llist_cmpfn cmp

const_LList llist_cmpfn void * extra

return NULL

const_LList templ

Define Documentation

#define LLIST_AUTO ( name ) llist name = {&name,&name}

Macro to instantiate a local llist.

Parameters:

name

of the llist node

Definition at line 99 of file llist.h.

#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

Definition at line 121 of file llist.h.

Referenced by lumiera_config_lookup_item_find(), lumiera_config_lookup_item_tail_find(), lumiera_config_lookup_remove(), lumiera_mmapings_destroy(), and lumiera_mmapings_mmap_acquire().

#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 129 of file llist.h.

Referenced by lumiera_config_dump(), and lumiera_mmapings_mmap_acquire().

#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 139 of file llist.h.

#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 interated
	end	node after the last node be iterated
	node	pointer to the iterated node

Definition at line 151 of file llist.h.

#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 interated
	rend	node before the last node be iterated
	node	pointer to the iterated node

Definition at line 162 of file llist.h.

#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 174 of file llist.h.

#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 185 of file llist.h.

Referenced by lumiera_mmapings_destroy(), and lumiera_mrucache_destroy().

Typedef Documentation

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

The comparsion function function type.

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

Parameters:

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

Returns:: shall return a value less than zero, zero, biggier than zero when a is less than, equal to, biggier than b

Definition at line 545 of file llist.h.

Function Documentation

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

Initialize a new llist.

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

Parameters:

self

node to be initialized

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

Check if a node is not linked with some other node.

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	(	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	(	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	(	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 ( int llist_is_memberconst_LList self, const_LList member )

Check if a node is a member of a list.

Parameters:

	self	root node of the list
	member	node to be searched

LLIST_FUNC ( int llist_is_before_afterconst_LList self, const_LList before, const_LList after )

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	(	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	(	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	(	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	(	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	(	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 ( LList llist_insertlist_nextLList self, LList next )

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 ( LList llist_insertlist_prevLList self, LList prev )

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	(	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 advaced

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	(	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	(	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	(	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	(	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 ( LList llist_get_nth_stopLList self, int n, const_LList stop )

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 ( LList llist_sortLList self, llist_cmpfn cmp, void *extra )

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 ( LList llist_ufindLList self, const_LList templ, llist_cmpfn cmp, void *extra )

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 biggier 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 foound


Classes
struct	llist_struct
Defines
#define	LLIST_AUTO(name) llist name = {&name,&name}
	Macro to instantiate a local llist.
#define	LLIST_FOREACH(list, node)
	Iterate forward over a list.
#define	LLIST_FOREACH_REV(list, node)
	Iterate backward over a list.
#define	LLIST_FORRANGE(start, end, node)
	Iterate forward over a range.
#define	LLIST_FORRANGE_REV(rstart, rend, node)
	Iterate backward over a range.
#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.
#define	LLIST_WHILE_TAIL(list, tail)
	Consume a list from tail.
Typedefs
typedef const llist *	const_LList
typedef llist *	LList
typedef struct llist_struct	llist
typedef int(*	llist_cmpfn )(const_LList a, const_LList b, void *extra)
	The comparsion function function type.
typedef llist **	LList_ref
Functions
const_LList llist_cmpfn void	LLIST_FOREACH (self, node)
	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.
	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.
	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.
	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.
	LLIST_FUNC (void llist_forward(LList_ref self),self=(self)->next;)
	Advance a pointer to a node to its next node.
	LLIST_FUNC (LList llist_prev(const_LList self), return self->prev;)
	Get previous node.
	LLIST_FUNC (LList llist_next(const_LList self), return self->next;)
	Get next node.
	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.
	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.
	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.
	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.
	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.
	LLIST_FUNC (LList llist_relocate(LList self), return self->next->prev=self->prev->next=self;)
	Fix a node which got relocated in memory.
	LLIST_FUNC (LList llist_unlink(LList self), llist_unlink_fast_(self);return self->next=self->prev=self;)
	Remove a node from a list.
	LLIST_FUNC (void llist_unlink_fast_(LList self), LList nxt=self->next, pre=self->prev;nxt->prev=pre;pre->next=nxt;)
	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.
	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.
	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.
	LLIST_FUNC (int llist_is_end(const_LList self, const_LList end), return self==end;)
	Check for the end of a list.
	LLIST_FUNC (int llist_is_tail(const_LList self, const_LList tail), return self->prev==tail;)
	Check for the tail of a list.
	LLIST_FUNC (int llist_is_head(const_LList self, const_LList head), return self->next==head;)
	Check for the head of a list.
	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.
	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 (LList llist_init(LList self), return self->next=self->prev=self;)
	Initialize a new llist.
Variables
const_LList llist_cmpfn	cmp
const_LList llist_cmpfn void *	extra
return	NULL
const_LList	templ