Simple doubly linked list implementation

## Files

file | linuxlist.h

## Data Structures

struct | llist_head
| (double) linked list header structure More...

## Macros

#define | inline __inline__
#define | container_of(ptr, type, member)
| cast a member of a structure out to the containing structure More...
#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. More...
#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 a statically-initialized llist_head More...
#define | INIT_LLIST_HEAD(ptr)
| initialize a llist_head to point back to self More...
#define | llist_entry(ptr, type, member) container_of(ptr, type, member)
| Get the struct containing this list entry. More...
#define | llist_first_entry(ptr, type, member) llist_entry((ptr)->next, type, member)
| Get the first element from a list. More...
#define | llist_last_entry(ptr, type, member) llist_entry((ptr)->prev, type, member)
| Get the last element from a list. More...
#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. More...
#define | llist_for_each(pos, head)
| Iterate over a linked list. More...
#define | __llist_for_each(pos, head) for (pos = (head)->next; pos != (head); pos = pos->next)
| Iterate over a llist (no prefetch) More...
#define | llist_for_each_prev(pos, head)
| Iterate over a llist backwards. More...
#define | llist_for_each_safe(pos, n, head)
| Iterate over a list; safe against removal of llist entry. More...
#define | llist_for_each_entry(pos, head, member)
| Iterate over llist of given type. More...
#define | llist_for_each_entry_reverse(pos, head, member)
| Iterate backwards over llist of given type. More...
#define | llist_for_each_entry_continue(pos, head, member)
| iterate over llist of given type continuing after existing point More...
#define | llist_for_each_entry_safe(pos, n, head, member)
| iterate over llist of given type, safe against removal of non-consecutive(!) llist entries More...
#define | llist_for_each_rcu(pos, head)
| llist_for_each_rcu - iterate over an rcu-protected llist @pos: the &struct llist_head to use as a loop counter. More...
#define | __llist_for_each_rcu(pos, head)
#define | llist_for_each_safe_rcu(pos, n, head)
| 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. More...
#define | llist_for_each_entry_rcu(pos, head, member)
| llist_for_each_entry_rcu - iterate over rcu llist of given type @pos: the type * to use as a loop counter. More...
#define | llist_for_each_continue_rcu(pos, head)
| llist_for_each_continue_rcu - iterate over an rcu-protected llist continuing after existing point. More...

## Functions

static void | prefetch (const void *x)
static void | __llist_add (struct llist_head *_new, struct llist_head *prev, struct llist_head *next)
| Insert a new entry between two known consecutive entries. More...
static void | llist_add (struct llist_head *_new, struct llist_head *head)
| add a new entry into a linked list (at head) More...
static void | llist_add_tail (struct llist_head *_new, struct llist_head *head)
| add a new entry into a linked list (at tail) More...
static void | __llist_del (struct llist_head *prev, struct llist_head *next)
static void | llist_del (struct llist_head *entry)
| Delete entry from linked list. More...
static void | llist_del_init (struct llist_head *entry)
| Delete entry from linked list and reinitialize it. More...
static void | llist_move (struct llist_head *llist, struct llist_head *head)
| Delete from one llist and add as another's head. More...
static void | llist_move_tail (struct llist_head *llist, struct llist_head *head)
| Delete from one llist and add as another's tail. More...
static int | llist_empty (const struct llist_head *head)
| Test whether a linked list is empty. More...
static void | __llist_splice (struct llist_head *llist, struct llist_head *head)
static void | llist_splice (struct llist_head *llist, struct llist_head *head)
| Join two llists. More...
static void | llist_splice_init (struct llist_head *llist, struct llist_head *head)
| join two llists and reinitialise the emptied llist. More...
static unsigned int | llist_count (struct llist_head *head)
| count nr of llist items by iterating. More...

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

inline static

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
| ) |  |

inline static

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
| ) |  |

inline static

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
| ) |  |

inline static

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(), osmo_fsm_inst_alloc(), osmo_fsm_inst_change_parent(), osmo_stat_item_group_alloc(), osmo_stats_reporter_alloc(), osmo_timers_update(), and rate_ctr_group_alloc().

## llist_add_tail()

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

inline static

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 alloc_entry(), llist_move_tail(), log_add_target(), msgb_enqueue(), osmo_counter_alloc(), osmo_fd_register(), osmo_fsm_register(), and osmo_signal_register_handler().

## llist_count()

static unsigned int llist_count | ( | struct llist_head * | head | ) |

inline static

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.

Referenced by osmo_counters_count().

## llist_del()

static void llist_del | ( | struct llist_head * | entry | ) |

inline static

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.

Referenced by _osmo_fsm_inst_term(), log_del_target(), msgb_dequeue(), osmo_counter_free(), osmo_fd_unregister(), osmo_fsm_inst_free(), osmo_fsm_inst_unlink_parent(), osmo_fsm_unregister(), osmo_signal_unregister_handler(), osmo_stat_item_group_free(), osmo_stats_reporter_free(), and rate_ctr_group_free().

## llist_del_init()

static void llist_del_init | ( | struct llist_head * | entry | ) |

inline static

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.

Referenced by osmo_timer_del().

## llist_empty()

static int llist_empty | ( | const struct llist_head * | head | ) |

inline static

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 _osmo_fsm_inst_term_children(), llist_splice(), llist_splice_init(), msgb_dequeue(), osmo_stats_timer_cb(), osmo_timer_del(), osmo_wqueue_bfd_cb(), and osmo_wqueue_clear().

## llist_move()

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

inline static

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
| ) |  |

inline static

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
| ) |  |

inline static

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
| ) |  |

inline static

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 | ) |

inline static

type
uint8_t type
see GSMTAP_TYPE_*
Definition: gsmtap.h:4
llist_entry
#define llist_entry(ptr, type, member)
Get the struct containing this list entry.
Definition: linuxlist.h:214
msgb::head
unsigned char * head
start of underlying memory buffer
Definition: msgb.h:57
prefetch
static void prefetch(const void *x)
Definition: linuxlist.h:24