Simple doubly linked list implementation

Files
file	linuxlist.h

Classes
struct	llist_head

Macros
#define	inline   __inline__
#define	container_of(ptr, type, member)
#define	LLIST_POISON1   ((void *) 0x00100100)
#define	LLIST_POISON2   ((void *) 0x00200200)
#define	LLIST_HEAD_INIT(name)   { &(name), &(name) }
#define	LLIST_HEAD(name)    struct llist_head name = LLIST_HEAD_INIT(name)
#define	INIT_LLIST_HEAD(ptr)
#define	llist_entry(ptr, type, member)    container_of(ptr, type, member)
#define	llist_first_entry(ptr, type, member)    llist_entry((ptr)->next, type, member)
#define	llist_last_entry(ptr, type, member)    llist_entry((ptr)->prev, type, member)
#define	llist_first_entry_or_null(ptr, type, member)    (!llist_empty(ptr) ? llist_first_entry(ptr, type, member) : NULL)
#define	llist_for_each(pos, head)
#define	__llist_for_each(pos, head)    for (pos = (head)->next; pos != (head); pos = pos->next)
#define	llist_for_each_prev(pos, head)
#define	llist_for_each_safe(pos, n, head)
#define	llist_for_each_entry(pos, head, member)
#define	llist_for_each_entry_reverse(pos, head, member)
#define	llist_for_each_entry_continue(pos, head, member)
#define	llist_for_each_entry_safe(pos, n, head, member)
#define	llist_for_each_rcu(pos, head)
#define	__llist_for_each_rcu(pos, head)
#define	llist_for_each_safe_rcu(pos, n, head)
#define	llist_for_each_entry_rcu(pos, head, member)
#define	llist_for_each_continue_rcu(pos, head)

Functions
static void	prefetch (const void *x)
static void	__llist_add (struct llist_head *_new, struct llist_head *prev, struct llist_head *next)
static void	llist_add (struct llist_head *_new, struct llist_head *head)
static void	llist_add_tail (struct llist_head *_new, struct llist_head *head)
static void	__llist_del (struct llist_head *prev, struct llist_head *next)
static void	llist_del (struct llist_head *entry)
static void	llist_del_init (struct llist_head *entry)
static void	llist_move (struct llist_head *llist, struct llist_head *head)
static void	llist_move_tail (struct llist_head *llist, struct llist_head *head)
static int	llist_empty (const struct llist_head *head)
static void	__llist_splice (struct llist_head *llist, struct llist_head *head)
static void	llist_splice (struct llist_head *llist, struct llist_head *head)
static void	llist_splice_init (struct llist_head *llist, struct llist_head *head)
static unsigned int	llist_count (struct llist_head *head)

Detailed Description

Macro Definition Documentation

__llist_for_each

#define __llist_for_each	(		pos,
			head
	)		for (pos = (head)->next; pos != (head); pos = pos->next)

Iterate over a llist (no prefetch)

Parameters

pos	The llist_head to use as a loop counter
head	The head of the list over which to iterate

This variant differs from llist_for_each() in that it's the simplest possible llist iteration code, no prefetching is done. Use this for code that knows the llist to be very short (empty or 1 entry) most of the time.

__llist_for_each_rcu

#define __llist_for_each_rcu	(		pos,
			head
	)

Value:

        for (pos = (head)->next; pos != (head); \
                pos = pos->next, ({ smp_read_barrier_depends(); 0;}))

container_of

#define container_of	(		ptr,
			type,
			member
	)

Value:

        ({                      \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type, member) );})

cast a member of a structure out to the containing structure

Parameters

[in]	ptr	the pointer to the member.
[in]	type	the type of the container struct this is embedded in.
[in]	member	the name of the member within the struct.

INIT_LLIST_HEAD

#define INIT_LLIST_HEAD

(

ptr

)

Value:

        do { \
        (ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

initialize a llist_head to point back to self

inline

#define inline   __inline__

llist_entry

#define llist_entry	(		ptr,
			type,
			member
	)		container_of(ptr, type, member)

Get the struct containing this list entry

Parameters

ptr	The llist_head pointer
type	The type of the struct this is embedded in

llist_first_entry

#define llist_first_entry	(		ptr,
			type,
			member
	)		llist_entry((ptr)->next, type, member)

Get the first element from a list

Parameters

ptr	the list head to take the element from.
type	the type of the struct this is embedded in.
member	the name of the list_head within the struct.

Note, that list is expected to be not empty.

llist_first_entry_or_null

#define llist_first_entry_or_null	(		ptr,
			type,
			member
	)		(!llist_empty(ptr) ? llist_first_entry(ptr, type, member) : NULL)

Get the first element from a list, or NULL

Parameters

ptr	the list head to take the element from.
type	the type of the struct this is embedded in.
member	the name of the list_head within the struct.

Note that if the list is empty, it returns NULL.

llist_for_each

#define llist_for_each	(		pos,
			head
	)

Value:

        for (pos = (head)->next, prefetch(pos->next); pos != (head); \
                pos = pos->next, prefetch(pos->next))

Iterate over a linked list

Parameters

pos	The llist_head to use as a loop counter
head	The head of the list over which to iterate

llist_for_each_continue_rcu

#define llist_for_each_continue_rcu	(		pos,
			head
	)

Value:

        for ((pos) = (pos)->next, prefetch((pos)->next); (pos) != (head); \
                (pos) = (pos)->next, ({ smp_read_barrier_depends(); 0;}), prefetch((pos)->next))

llist_for_each_continue_rcu - iterate over an rcu-protected llist continuing after existing point. @pos: the &struct llist_head to use as a loop counter. @head: the head for your llist.

llist_for_each_entry

#define llist_for_each_entry	(		pos,
			head,
			member
	)

Value:

        for (pos = llist_entry((head)->next, typeof(*pos), member),     \
                     prefetch(pos->member.next);                        \
             &pos->member != (head);                                    \
             pos = llist_entry(pos->member.next, typeof(*pos), member), \
                     prefetch(pos->member.next))

Iterate over llist of given type

Parameters

pos	The 'type *' to use as a loop counter
head	The head of the list over which to iterate
member	The name of the llist_head within struct pos

llist_for_each_entry_continue

#define llist_for_each_entry_continue	(		pos,
			head,
			member
	)

Value:

        for (pos = llist_entry(pos->member.next, typeof(*pos), member), \
                     prefetch(pos->member.next);                        \
             &pos->member != (head);                                    \
             pos = llist_entry(pos->member.next, typeof(*pos), member), \
                     prefetch(pos->member.next))

iterate over llist of given type continuing after existing point

Parameters

pos	The 'type *' to use as a loop counter
head	The head of the list over which to iterate
member	The name of the llist_head within struct pos

llist_for_each_entry_rcu

#define llist_for_each_entry_rcu	(		pos,
			head,
			member
	)

Value:

        for (pos = llist_entry((head)->next, typeof(*pos), member),     \
                     prefetch(pos->member.next);                        \
             &pos->member != (head);                                    \
             pos = llist_entry(pos->member.next, typeof(*pos), member), \
                     ({ smp_read_barrier_depends(); 0;}),               \
                     prefetch(pos->member.next))

llist_for_each_entry_rcu - iterate over rcu llist of given type @pos: the type * to use as a loop counter. @head: the head for your llist. @member: the name of the llist_struct within the struct.

llist_for_each_entry_reverse

#define llist_for_each_entry_reverse	(		pos,
			head,
			member
	)

Value:

        for (pos = llist_entry((head)->prev, typeof(*pos), member),     \
                     prefetch(pos->member.prev);                        \
             &pos->member != (head);                                    \
             pos = llist_entry(pos->member.prev, typeof(*pos), member), \
                     prefetch(pos->member.prev))

Iterate backwards over llist of given type.

Parameters

pos	The 'type *' to use as a loop counter
head	The head of the list over which to iterate
member	The name of the llist_head within struct pos

llist_for_each_entry_safe

#define llist_for_each_entry_safe	(		pos,
			n,
			head,
			member
	)

Value:

        for (pos = llist_entry((head)->next, typeof(*pos), member),     \
                n = llist_entry(pos->member.next, typeof(*pos), member);        \
             &pos->member != (head);                                    \
             pos = n, n = llist_entry(n->member.next, typeof(*n), member))

iterate over llist of given type, safe against removal of non-consecutive(!) llist entries

Parameters

pos	The 'type *' to use as a loop counter
n	Another type * to use as temporary storage
head	The head of the list over which to iterate
member	The name of the llist_head within struct pos

llist_for_each_prev

#define llist_for_each_prev	(		pos,
			head
	)

Value:

        for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
                pos = pos->prev, prefetch(pos->prev))

Iterate over a llist backwards

Parameters

pos	The llist_head to use as a loop counter
head	The head of the list over which to iterate

llist_for_each_rcu

#define llist_for_each_rcu	(		pos,
			head
	)

Value:

        for (pos = (head)->next, prefetch(pos->next); pos != (head); \
                pos = pos->next, ({ smp_read_barrier_depends(); 0;}), prefetch(pos->next))

llist_for_each_rcu - iterate over an rcu-protected llist @pos: the &struct llist_head to use as a loop counter. @head: the head for your llist.

llist_for_each_safe

#define llist_for_each_safe	(		pos,
			n,
			head
	)

Value:

        for (pos = (head)->next, n = pos->next; pos != (head); \
                pos = n, n = pos->next)

Iterate over a list; safe against removal of llist entry

Parameters

pos	The llist_head to use as a loop counter
n	Another llist_head to use as temporary storage
head	The head of the list over which to iterate

llist_for_each_safe_rcu

#define llist_for_each_safe_rcu	(		pos,
			n,
			head
	)

Value:

        for (pos = (head)->next, n = pos->next; pos != (head); \
                pos = n, ({ smp_read_barrier_depends(); 0;}), n = pos->next)

llist_for_each_safe_rcu - iterate over an rcu-protected llist safe against removal of llist entry @pos: the &struct llist_head to use as a loop counter.
: another &struct llist_head to use as temporary storage @head: the head for your llist.

LLIST_HEAD

#define LLIST_HEAD

(

name

)

struct llist_head name = LLIST_HEAD_INIT(name)

define a statically-initialized llist_head

Parameters

[in]

name

Variable name

This is a helper macro that will define a named variable of type llist_head and initialize it

LLIST_HEAD_INIT

#define LLIST_HEAD_INIT

(

name

)

{ &(name), &(name) }

llist_last_entry

#define llist_last_entry	(		ptr,
			type,
			member
	)		llist_entry((ptr)->prev, type, member)

Get the last element from a list

Parameters

ptr	the list head to take the element from.
type	the type of the struct this is embedded in.
member	the name of the llist_head within the struct.

Note, that list is expected to be not empty.

LLIST_POISON1

#define LLIST_POISON1   ((void *) 0x00100100)

These are non-NULL pointers that will result in page faults under normal circumstances, used to verify that nobody uses non-initialized llist entries.

LLIST_POISON2

#define LLIST_POISON2   ((void *) 0x00200200)

Function Documentation

__llist_add()

static void __llist_add ( struct llist_head *  _new, struct llist_head *  prev, struct llist_head *  next  )

inlinestatic

Insert a new entry between two known consecutive entries.

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

References llist_head::next, and llist_head::prev.

Referenced by llist_add(), and llist_add_tail().

__llist_del()

static void __llist_del ( struct llist_head *  prev, struct llist_head *  next  )

inlinestatic

References llist_head::next, and llist_head::prev.

Referenced by llist_del(), llist_del_init(), llist_move(), and llist_move_tail().

__llist_splice()

static void __llist_splice ( struct llist_head *  llist, struct llist_head *  head  )

inlinestatic

References llist_head::next, and llist_head::prev.

Referenced by llist_splice(), and llist_splice_init().

llist_add()

static void llist_add ( struct llist_head *  _new, struct llist_head *  head  )

inlinestatic

add a new entry into a linked list (at head)

Parameters

_new	New entry to be added
head	llist_head to add it after

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

References __llist_add(), and llist_head::next.

Referenced by llist_move().

llist_add_tail()

static void llist_add_tail ( struct llist_head *  _new, struct llist_head *  head  )

inlinestatic

add a new entry into a linked list (at tail)

Parameters

_new	New entry to be added
head	Head of linked list to whose tail we shall add _new

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

References __llist_add(), and llist_head::prev.

Referenced by llist_move_tail().

llist_count()

static unsigned int llist_count ( struct llist_head *  head )

inlinestatic

count nr of llist items by iterating.

Parameters

head	The llist head to count items of.

Returns

Number of items.

This function is not efficient, mostly useful for small lists and non time critical cases like unit tests.

References llist_for_each.

llist_del()

static void llist_del ( struct llist_head *  entry )

inlinestatic

Delete entry from linked list

Parameters

entry

The element to delete from the llist

Note: llist_empty on entry does not return true after this, the entry is in an undefined state.

References __llist_del(), LLIST_POISON1, LLIST_POISON2, llist_head::next, and llist_head::prev.

llist_del_init()

static void llist_del_init ( struct llist_head *  entry )

inlinestatic

Delete entry from linked list and reinitialize it

Parameters

entry

The element to delete from the list

References __llist_del(), INIT_LLIST_HEAD, llist_head::next, and llist_head::prev.

llist_empty()

static int llist_empty ( const struct llist_head *  head )

inlinestatic

Test whether a linked list is empty

Parameters

[in]

head

The llist to test.

Returns

1 if the list is empty, 0 otherwise

References llist_head::next.

Referenced by llist_splice(), and llist_splice_init().

llist_move()

static void llist_move ( struct llist_head *  llist, struct llist_head *  head  )

inlinestatic

Delete from one llist and add as another's head

Parameters

llist	The entry to move
head	The head that will precede our entry

References __llist_del(), llist_add(), llist_head::next, and llist_head::prev.

llist_move_tail()

static void llist_move_tail ( struct llist_head *  llist, struct llist_head *  head  )

inlinestatic

Delete from one llist and add as another's tail

Parameters

llist	The entry to move
head	The head that will follow our entry

References __llist_del(), llist_add_tail(), llist_head::next, and llist_head::prev.

llist_splice()

static void llist_splice ( struct llist_head *  llist, struct llist_head *  head  )

inlinestatic

Join two llists

Parameters

llist	The new linked list to add
head	The place to add llist in the other list

References __llist_splice(), and llist_empty().

llist_splice_init()

static void llist_splice_init ( struct llist_head *  llist, struct llist_head *  head  )

inlinestatic

join two llists and reinitialise the emptied llist.

Parameters

llist	The new linked list to add.
head	The place to add it in the first llist.

The llist at @llist is reinitialised

References __llist_splice(), INIT_LLIST_HEAD, and llist_empty().

prefetch()

static void prefetch ( const void *  x )

inlinestatic