libosmocore 0.9.6-23.20170220git32ee5af8.fc42
Osmocom core library
Loading...
Searching...
No Matches
Simple doubly linked list implementation

Files

file  linuxlist.h
 Simple doubly linked list implementation.
 

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
 
#define LLIST_POISON1   ((void *) 0x00100100)
 
#define LLIST_POISON2   ((void *) 0x00200200)
 
#define LLIST_HEAD_INIT(name)
 
#define LLIST_HEAD(name)
 define a statically-initialized llist_head
 
#define INIT_LLIST_HEAD(ptr)
 initialize a llist_head to point back to self
 
#define llist_entry(ptr, type, member)
 Get the struct containing this list entry.
 
#define llist_for_each(pos, head)
 Iterate over a linked list.
 
#define __llist_for_each(pos, head)
 Iterate over a llist (no prefetch)
 
#define llist_for_each_prev(pos, head)
 Iterate over a llist backwards.
 
#define llist_for_each_safe(pos, n, head)
 Iterate over a list; safe against removal of llist entry.
 
#define llist_for_each_entry(pos, head, member)
 Iterate over llist of given type.
 
#define llist_for_each_entry_reverse(pos, head, member)
 Iterate backwards over llist of given type.
 
#define llist_for_each_entry_continue(pos, head, member)
 iterate over llist of given type continuing after existing point
 
#define llist_for_each_entry_safe(pos, n, head, member)
 iterate over llist of given type, safe against removal of non-consecutive(!) llist entries
 
#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)
 Insert a new entry between two known consecutive entries.
 
static void llist_add (struct llist_head *_new, struct llist_head *head)
 add a new entry into a linked list (at head)
 
static void llist_add_tail (struct llist_head *_new, struct llist_head *head)
 add a new entry into a linked list (at tail)
 
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.
 
static void llist_del_init (struct llist_head *entry)
 Delete entry from linked list and reinitialize it.
 
static void llist_move (struct llist_head *llist, struct llist_head *head)
 Delete from one llist and add as another's head.
 
static void llist_move_tail (struct llist_head *llist, struct llist_head *head)
 Delete from one llist and add as another's tail.
 
static int llist_empty (const struct llist_head *head)
 Test whether a linked list is empty.
 
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.
 
static void llist_splice_init (struct llist_head *llist, struct llist_head *head)
 join two llists and reinitialise the emptied llist.
 
static unsigned int llist_count (struct llist_head *head)
 count nr of llist items by iterating.
 

Variables

struct llist_headllist_head::next
 Pointer to next and previous item.
 
struct llist_headllist_head::prev
 

Detailed Description

Macro Definition Documentation

◆ __llist_for_each

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

Iterate over a llist (no prefetch)

Parameters
posThe llist_head to use as a loop counter
headThe 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]ptrthe pointer to the member.
[in]typethe type of the container struct this is embedded in.
[in]memberthe name of the member within the struct.

Referenced by osmo_timers_prepare(), osmo_timers_update(), and osmo_wqueue_bfd_cb().

◆ 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

Referenced by llist_del_init(), llist_splice_init(), log_target_create(), osmo_fsm_inst_alloc(), osmo_fsm_register(), osmo_timer_add(), osmo_timers_update(), and osmo_wqueue_init().

◆ llist_entry

#define llist_entry ( ptr,
type,
member )
Value:
container_of(ptr, type, member)
#define container_of(ptr, type, member)
cast a member of a structure out to the containing structure
Definition linuxlist.h:33

Get the struct containing this list entry.

Parameters
ptrThe llist_head pointer
typeThe type of the struct this is embedded in

member The name of the llist_head within the struct

Referenced by _osmo_fsm_inst_term_children(), and msgb_dequeue().

◆ 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
posThe llist_head to use as a loop counter
headThe head of the list over which to iterate

Referenced by llist_count().

◆ 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))
#define llist_entry(ptr, type, member)
Get the struct containing this list entry.
Definition linuxlist.h:215

Iterate over llist of given type.

Parameters
posThe 'type *' to use as a loop counter
headThe head of the list over which to iterate
memberThe name of the llist_head within struct pos

Referenced by log_check_level(), log_target_find(), log_targets_reopen(), osmo_counter_get_by_name(), osmo_counters_for_each(), osmo_fd_get_by_fd(), osmo_fd_is_registered(), osmo_signal_dispatch(), osmo_signal_unregister_handler(), osmo_stat_item_get_group_by_name_idx(), osmo_timers_update(), osmo_vlogp(), rate_ctr_for_each_group(), and rate_ctr_get_group_by_name_idx().

◆ 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
posThe 'type *' to use as a loop counter
headThe head of the list over which to iterate
memberThe 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
posThe 'type *' to use as a loop counter
headThe head of the list over which to iterate
memberThe 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
posThe 'type *' to use as a loop counter
nAnother type * to use as temporary storage
headThe head of the list over which to iterate
memberThe 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
posThe llist_head to use as a loop counter
headThe 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
posThe llist_head to use as a loop counter
nAnother llist_head to use as temporary storage
headThe 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)
Value:
struct llist_head name = LLIST_HEAD_INIT(name)
(double) linked list header structure
Definition linuxlist.h:47

define a statically-initialized llist_head

Parameters
[in]nameVariable 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)
Value:
{ &(name), &(name) }

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

Referenced by llist_del().

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.

Referenced by llist_add(), and llist_add_tail().

◆ 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
_newNew entry to be added
headllist_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_alloc_child(), osmo_stat_item_group_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 )
inlinestatic

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

Parameters
_newNew entry to be added
headHead 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().

Referenced by 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)
inlinestatic

count nr of llist items by iterating.

Parameters
headThe 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
entryThe 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_POISON1, and llist_head::next.

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

◆ llist_del_init()

static void llist_del_init ( struct llist_head * entry)
inlinestatic

Delete entry from linked list and reinitialize it.

Parameters
entryThe element to delete from the list

References INIT_LLIST_HEAD, and llist_head::next.

Referenced by osmo_timer_del().

◆ llist_empty()

static int llist_empty ( const struct llist_head * head)
inlinestatic

Test whether a linked list is empty.

Parameters
[in]headThe 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_timer_del(), osmo_wqueue_bfd_cb(), and osmo_wqueue_clear().

◆ 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
llistThe entry to move
headThe head that will precede our entry

References llist_add(), and llist_head::next.

◆ 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
llistThe entry to move
headThe head that will follow our entry

References llist_add_tail(), and llist_head::next.

◆ llist_splice()

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

Join two llists.

Parameters
llistThe new linked list to add
headThe place to add llist in the other list

References 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
llistThe new linked list to add.
headThe place to add it in the first llist.

The llist at @llist is reinitialised

References INIT_LLIST_HEAD, and llist_empty().