Double linked list

Simple double linked list implementation.

Some of the internal functions ("xxx") are useful when
manipulating whole lists rather than single entries, as
sometimes we already know the next/prev entries and we can
generate better code by using them directly rather than
using the generic single-entry routines.

NOTES
Implementation is taken from Linux Kernel

Functions

list_node_init

public

STATIC_INLINE void list_node_init(list_node_t *list)

list_head_init

public

STATIC_INLINE void list_head_init(list_head_t *list, const char* namefmt, ...) 
STATIC_INLINE void list_head_init(list_head_t *list, const char* namefmt, ...)

list_head_reset

public

STATIC_INLINE void list_head_reset(list_head_t *list) 

list_head_node

public

STATIC_INLINE list_node_t* list_head_node(list_head_t* head) 

list_head_copy

public

STATIC_INLINE void list_head_copy(list_head_t *dst, const list_head_t *src) 

__list_add

public

Insert a new entry between two known consecutive entries.

This is only for internal list manipulation where we know
the prev/next entries already!

STATIC_INLINE void __list_add(list_node_t *node,list_node_t *prev,list_node_t *next)

list_add

public

list_add - add a new entry

Insert a new entry after the specified head.
This is good for implementing stacks.

ARGUMENTS

• new - new entry to be added
  
• head - list head to add it after
  

STATIC_INLINE void list_add(list_node_t *node, list_head_t *head)

list_add_tail

public

list_add_tail - add a new entry

Insert a new entry before the specified head.
This is useful for implementing queues.

ARGUMENTS

• node - new entry to be added
  
• head - list head to add it before
  

STATIC_INLINE void list_add_tail(list_node_t *node, list_head_t *head)

list_insert_front

public

list_insert_front - insert entry after another

ARGUMENTS

• node - new entry to be added
  
• iter - node after which it has to be added
  

STATIC_INLINE void list_insert_front(list_node_t *node, list_node_t *iter)

list_insert_back

public

list_insert_back - insert entry before another

ARGUMENTS

• node - new entry to be added
  
• iter - node before which it has to be added
  

STATIC_INLINE void list_insert_back(list_node_t *node, list_node_t *iter)

__list_del

public

STATIC_INLINE void __list_del(list_node_t * prev, list_node_t * next)

__list_del_entry

public

list_del - deletes entry from list.
Note: list_empty() on entry does not return true after this, the entry is
in an undefined state.

ARGUMENTS

• entry - the element to delete from the list.
  

STATIC_INLINE void __list_del_entry(list_node_t *entry)

list_del

public

STATIC_INLINE void list_del(list_node_t *entry)

list_replace

public

list_replace - replace old entry by new one

If @old was empty, it will be overwritten.

ARGUMENTS

• old - the element to be replaced
  
• new - the new element to insert
  

STATIC_INLINE void list_replace(list_node_t *old,list_node_t *node)

list_replace_init

public

STATIC_INLINE void list_replace_init(list_node_t *old,list_node_t *node)

list_del_init

public

list_del_init - deletes entry from list and reinitialize it.

ARGUMENTS

• entry - the element to delete from the list.
  

STATIC_INLINE void list_del_init(list_node_t *entry)

list_move

public

list_move - delete from one list and add as another's head

ARGUMENTS

• list - the entry to move
  
• head - the head that will precede our entry
  

STATIC_INLINE void list_move(list_node_t *list, list_head_t *head)

list_move_tail

public

list_move_tail - delete from one list and add as another's tail

ARGUMENTS

• list - the entry to move
  
• head - the head that will follow our entry
  

STATIC_INLINE void list_move_tail(list_node_t *list,list_head_t *head)

list_is_last

public

list_is_last - tests whether node is the last entry in list head

ARGUMENTS

• node - the entry to test
  
• head - the head of the list
  

STATIC_INLINE int list_is_last(const list_node_t *node,const list_head_t *head)

list_is_first

public

list_is_first - tests whether node is the first entry in list head

ARGUMENTS

• node - the entry to test
  
• head - the head of the list
  

STATIC_INLINE int list_is_first(const list_node_t *node,const list_head_t *head)

list_is_head

public

list_is_head - tests whether node is the list head

ARGUMENTS

• node - the entry to test
  
• head - the head of the list
  

STATIC_INLINE int list_is_head(const list_node_t *node,const list_head_t *head)

list_empty

public

list_empty - tests whether a list is empty

ARGUMENTS

• head - the list to test.
  

STATIC_INLINE int list_empty(const list_head_t *head)

list_empty_careful

public

list_empty_careful - tests whether a list is empty and not being modified

Description:
tests whether a list is empty and checks that no other CPU might be
in the process of modifying either member (next or prev)

NOTE: using list_empty_careful() without synchronization
can only be safe if the only activity that can happen
to the list entry is list_del_init(). Eg. it cannot be used
if another CPU could re-list_add() it.

ARGUMENTS

• head - the list to test
  

STATIC_INLINE int list_empty_careful(const list_node_t *head)

list_node_alone

public

list_node_alone - tests if node is not inserted into list

ARGUMENTS

• head - the list to test.
  

STATIC_INLINE int list_node_alone(const list_node_t *node)

list_rotate_left

public

list_rotate_left - rotate the list to the left

ARGUMENTS

• head - the head of the list
  

STATIC_INLINE void list_rotate_left(list_head_t *head)

list_is_singular

public

list_is_singular - tests whether a list has just one entry.

ARGUMENTS

• head - the list to test.
  

STATIC_INLINE int list_is_singular(const list_head_t *head)

__list_cut_position

public

STATIC_INLINE void __list_cut_position(list_head_t *list,list_head_t *head, list_node_t *entry)

list_cut_position

public

list_cut_position - cut a list into two
and if so we won't cut the list

This helper moves the initial part of @head, up to and
including @entry, from @head to @list. You should
pass on @entry an element you know is on @head. @list
should be an empty list or a list you do not care about
losing its data.

ARGUMENTS

• list - a new list to add all removed entries
  
• head - a list with entries
  
• entry - an entry within head, could be the head itself
  

STATIC_INLINE void list_cut_position(list_head_t *list,list_head_t *head, list_node_t *entry)

__list_splice

public

STATIC_INLINE void __list_splice(const list_head_t *list,list_node_t *prev,list_node_t *next)

list_splice

public

list_splice - join two lists, this is designed for stacks

ARGUMENTS

• list - the new list to add.
  
• head - the place to add it in the first list.
  

STATIC_INLINE void list_splice(const list_head_t *list,list_node_t *node)

list_splice_tail

public

list_splice_tail - join two lists, each list being a queue

ARGUMENTS

• list - the new list to add.
  
• head - the place to add it in the first list.
  

STATIC_INLINE void list_splice_tail(list_head_t *list,list_node_t *node)

list_splice_init

public

list_splice_init - join two lists and reinitialise the emptied list.

The list at @list is reinitialised

ARGUMENTS

• list - the new list to add.
  
• node - the place to add it in the first list.
  

STATIC_INLINE void list_splice_init(list_head_t *list,list_node_t *node)

list_splice_tail_init

public

list_splice_tail_init - join two lists and reinitialise the emptied list

Each of the lists is a queue.
The list at @list is reinitialised

ARGUMENTS

• list - the new list to add.
  
• node - the place to add it in the first list.
  

STATIC_INLINE void list_splice_tail_init(list_head_t *list,list_node_t *node)

list_merge_impl

public

STATIC_INLINE void list_merge_impl(list_head_t *head, list_head_t *list1,list_head_t *list2) 

list_merge

public

Merge lists into new list - reinitializes lists 1 and 2 and
adds them to new list sequentally because consequent calls of
list_splice will provide inconsistent list.

ARGUMENTS

• head - destination list
  
• list1 - first list to add
  
• list2 - second list to add
  

STATIC_INLINE void list_merge(list_head_t *head, list_head_t *list1,list_head_t *list2) 

list_entry

list_entry - get the struct for this entry

ARGUMENTS

• ptr - the &struct list_head pointer.
  
• type - the type of the struct this is embedded in.
  
• member - the name of the list_struct within the struct.
  

#define list_entry(ptr, type, member)

list_first_entry

list_first_entry - get the first element from a list

Note, that list is expected to be not empty.

ARGUMENTS

• head - the list head to take the element from.
  
• type - the type of the struct this is embedded in.
  
• member - the name of the list_struct within the struct.
  

#define list_first_entry(type, head, member)

list_last_entry

list_last_entry - get the last element from a list

Note, that list is expected to be not empty.

ARGUMENTS

• head - the list head to take the element from.
  
• type - the type of the struct this is embedded in.
  
• member - the name of the list_struct within the struct.
  

#define list_last_entry(type, head, member)

list_next_entry

list_next_entry - get the element from a list after node

Note, that node is expected not tot be last.

ARGUMENTS

• ptr - pointer to current entry
  
• type - the type of the struct this is embedded in.
  
• member - the name of the list_struct within the struct.
  

#define list_next_entry(type, ptr, member)

list_prev_entry

list_prev_entry - get the element from a list before node

Note, that node is expected not being first.

ARGUMENTS

• ptr - pointer to current entry
  
• type - the type of the struct this is embedded in.
  
• member - the name of the list_struct within the struct.
  

#define list_prev_entry(type, ptr, member)

list_for_each

list_for_each - iterate over a list

ARGUMENTS

• pos - the &struct list_head to use as a loop cursor.
  
• head - the head for your list.
  

#define list_for_each(pos, head)

__list_for_each

list_for_each - iterate over a list

This variant doesn't differ from list_for_each() any more.
We don't do prefetching in either case.

ARGUMENTS

• pos - the &struct list_head to use as a loop cursor.
  
• head - the head for your list.
  

#define __list_for_each(pos, head)

list_for_each_prev

list_for_each_prev - iterate over a list backwards

ARGUMENTS

• pos - the &struct list_head to use as a loop cursor.
  
• head - the head for your list.
  

#define list_for_each_prev(pos, head)

list_for_each_safe

list_for_each_safe - iterate over a list safe against removal of list entry

ARGUMENTS

• pos - the &struct list_head to use as a loop cursor.
  
• n - another &struct list_head to use as temporary storage
  
• head - the head for your list.
  

#define list_for_each_safe(pos, n, head)

list_for_each_prev_safe

iterate over a list backwards safe against removal of list entry

ARGUMENTS

• pos - the &struct list_head to use as a loop cursor.
  
• n - another &struct list_head to use as temporary storage
  
• head - the head for your list.
  

#define list_for_each_prev_safe(pos, n, head)

list_for_each_continue

list_for_each_continue - iterate over a list starting from pre-determined position

ARGUMENTS

• pos - the &struct list_head to use as a loop cursor. Starting position
  
• head - the head for your list.
  

#define list_for_each_continue(pos, head)

list_for_each_continue_reverse

list_for_each_prev - iterate over a list backwards starting from position

ARGUMENTS

• pos - the &struct list_head to use as a loop cursor. Starting position
  
• head - the head for your list.
  

#define list_for_each_continue_reverse(pos, head)

list_for_each_entry

list_for_each_entry - iterate over list of given type

ARGUMENTS

• pos - the type to use as a loop cursor.
  
• head - the head for your list.
  
• member - the name of the list_struct within the struct.
  

#define list_for_each_entry(type, pos, head, member)

list_for_each_entry_reverse

list_for_each_entry_reverse - iterate backwards over list of given type.

ARGUMENTS

• pos - the type to use as a loop cursor.
  
• head - the head for your list.
  
• member - the name of the list_struct within the struct.
  

#define list_for_each_entry_reverse(type, pos, head, member)

list_prepare_entry

list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()

Prepares a pos entry for use as a start point in list_for_each_entry_continue().

ARGUMENTS

• pos - the type to use as a start point
  
• head - the head of the list
  
• member - the name of the list_struct within the struct.
  

#define list_prepare_entry(type, pos, head, member)

list_for_each_entry_continue

list_for_each_entry_continue - continue iteration over list of given type

Continue to iterate over list of given type, continuing after
the current position.

ARGUMENTS

• pos - the type to use as a loop cursor.
  
• head - the head for your list.
  
• member - the name of the list_struct within the struct.
  

#define list_for_each_entry_continue(type, pos, head, member)

list_for_each_entry_continue_reverse

list_for_each_entry_continue_reverse - iterate backwards from the given point

Start to iterate over list of given type backwards, continuing after
the current position.

ARGUMENTS

• pos - the type to use as a loop cursor.
  
• head - the head for your list.
  
• member - the name of the list_struct within the struct.
  

#define list_for_each_entry_continue_reverse(type, pos, head, member)

list_for_each_entry_from

list_for_each_entry_from - iterate over list of given type from the current point

Iterate over list of given type, continuing from current position.

ARGUMENTS

• pos - the type to use as a loop cursor.
  
• head - the head for your list.
  
• member - the name of the list_struct within the struct.
  

#define list_for_each_entry_from(type, pos, head, member)

list_for_each_entry_safe

list_for_each_entry_safe - iterate over list of given type safe against removal of list entry

ARGUMENTS

• pos - the type to use as a loop cursor.
  
• n - another type to use as temporary storage
  
• head - the head for your list.
  
• member - the name of the list_struct within the struct.
  

#define list_for_each_entry_safe(type, pos, n, head, member)

list_for_each_entry_safe_continue

list_for_each_entry_safe_continue - continue list iteration safe against removal

Iterate over list of given type, continuing after current point,
safe against removal of list entry.

ARGUMENTS

• pos - the type to use as a loop cursor.
  
• n - another type to use as temporary storage
  
• head - the head for your list.
  
• member - the name of the list_struct within the struct.
  

#define list_for_each_entry_safe_continue(type, pos, n, head, member)

list_for_each_entry_safe_from

list_for_each_entry_safe_from - iterate over list from current point safe against removal

Iterate over list of given type from current point, safe against
removal of list entry.

ARGUMENTS

• pos - the type to use as a loop cursor.
  
• n - another type to use as temporary storage
  
• head - the head for your list.
  
• member - the name of the list_struct within the struct.
  

#define list_for_each_entry_safe_from(type, pos, n, head, member)

list_for_each_entry_safe_reverse

list_for_each_entry_safe_reverse - iterate backwards over list safe against removal

Iterate backwards over list of given type, safe against removal
of list entry.

ARGUMENTS

• pos - the type to use as a loop cursor.
  
• n - another type to use as temporary storage
  
• head - the head for your list.
  
• member - the name of the list_struct within the struct.
  

#define list_for_each_entry_safe_reverse(type, pos, n, head, member)

list_safe_reset_next

list_safe_reset_next - reset a stale list_for_each_entry_safe loop

list_safe_reset_next is not safe to use in general if the list may be
modified concurrently (eg. the lock is dropped in the loop body). An
exception to this is if the cursor element (pos) is pinned in the list,
and list_safe_reset_next is called after re-taking the lock and before
completing the current iteration of the loop body.

ARGUMENTS

• pos - the loop cursor used in the list_for_each_entry_safe loop
  
• n - temporary storage used in list_for_each_entry_safe
  
• member - the name of the list_struct within the struct.
  

#define list_safe_reset_next(type, pos, n, member)

Types

typedef struct list_node

typedef struct list_node {
    struct list_node *next, *prev;
} list_node_t;

typedef struct list_head

typedef struct list_head {
    list_node_t l_head;

    char l_name[LISTNAMELEN];
} list_head_t;