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 )(LList a, LList b)
 Sort a list.
typedef llist ** LList_ref

Functions

 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 (void llist_init(LList self), self->next=self->prev=self;)
 Initialize a new llist.

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 97 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 119 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 127 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 137 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 149 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 160 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 172 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 183 of file llist.h.

Referenced by lumiera_mmapings_destroy(), and lumiera_mrucache_destroy().

Typedef Documentation

typedef int(* llist_cmpfn)(LList a, LList b)

Sort a list.

Parameters:
self list to be sorted
cmp function takeing 2 LLists simple recursive mergesort

Definition at line 540 of file llist.h.

Function Documentation

LLIST_FUNC ( void   llist_initLList self,
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

Generated on Tue Jan 6 17:20:48 2009 for Lumiera by  doxygen 1.5.6