libosmocore  1.4.0.80-4fb27
Osmocom core library
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. 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 a new llist_head pointing to a given llist_head. More...
 
#define LLIST_HEAD(name)   struct llist_head name = LLIST_HEAD_INIT(name)
 Define a statically-initialized variable of type llist_head. More...
 
#define INIT_LLIST_HEAD(ptr)
 Initialize a llist_head to point back to itself. 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 linked 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 linked list (no prefetch). More...
 
#define llist_for_each_prev(pos, head)
 Iterate over a linked list backwards. More...
 
#define llist_for_each_safe(pos, n, head)
 Iterate over a linked list, safe against removal of llist entry. More...
 
#define llist_for_each_entry(pos, head, member)
 Iterate over a linked list of a given type. More...
 
#define llist_for_each_entry_reverse(pos, head, member)
 Iterate backwards over a linked list of a given type. More...
 
#define llist_for_each_entry_continue(pos, head, member)
 Iterate over a linked list of a given type, continuing after an 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)
 Iterate over an rcu-protected llist. More...
 
#define __llist_for_each_rcu(pos, head)
 
#define llist_for_each_safe_rcu(pos, n, head)
 Iterate over an rcu-protected llist, safe against removal of llist entry. More...
 
#define llist_for_each_entry_rcu(pos, head, member)
 Iterate over an rcu-protected llist of a given type. More...
 
#define llist_for_each_continue_rcu(pos, head)
 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)
 
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 a single entry from a linked list. More...
 
static void llist_del_init (struct llist_head *entry)
 Delete a single entry from a 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 linked lists. 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 (const struct llist_head *head)
 Count number 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 linked list (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;}))
unsigned char * head
start of underlying memory buffer
Definition: msgb.h:57

◆ container_of

#define container_of (   ptr,
  type,
  member 
)
Value:
({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type, member) );})
uint8_t type
see GSMTAP_TYPE_*
Definition: gsmtap.h:122

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 __add_timer(), 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 itself.

Parameters
[in]ptrllist_head to be initialized.

Referenced by alloc_entries(), llist_del_init(), llist_splice_init(), log_target_create(), osmo_fsm_inst_alloc(), osmo_fsm_register(), osmo_select_init(), osmo_sercomm_init(), osmo_timer_add(), osmo_timers_update(), osmo_use_count_create(), osmo_use_count_make_static_entries(), and osmo_wqueue_init().

◆ 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
ptrthe llist_head pointer.
typethe type of the struct this is embedded in.
memberthe name of the llist_head within the struct.

Referenced by _osmo_fsm_inst_term_children(), and msgb_dequeue().

◆ llist_first_entry

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

Get the first element from a linked list.

Parameters
ptrthe list head to take the element from.
typethe type of the struct this is embedded in.
memberthe 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
ptrthe list head to take the element from.
typethe type of the struct this is embedded in.
memberthe 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))
unsigned char * head
start of underlying memory buffer
Definition: msgb.h:57
static void prefetch(const void *x)
Definition: linuxlist.h:24

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(), and osmo_sercomm_tx_queue_depth().

◆ 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))
unsigned char * head
start of underlying memory buffer
Definition: msgb.h:57
static void prefetch(const void *x)
Definition: linuxlist.h:24

Iterate over an rcu-protected llist, continuing after existing point.

Parameters
posthe llist_head to use as a loop counter.
headthe head of the list over which to iterate.

◆ 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:217
unsigned char * head
start of underlying memory buffer
Definition: msgb.h:57
static void prefetch(const void *x)
Definition: linuxlist.h:24

Iterate over a linked list of a 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 the struct pos.

Referenced by flush_all_reporters(), handle_counter(), log_check_level(), log_target_find(), log_targets_reopen(), osmo_counter_get_by_name(), osmo_counters_for_each(), osmo_fd_fill_fds(), osmo_fd_get_by_fd(), osmo_fd_is_registered(), osmo_fsm_find_by_name(), osmo_fsm_inst_find_by_id(), osmo_fsm_inst_find_by_name(), osmo_signal_dispatch(), osmo_signal_unregister_handler(), osmo_stat_item_for_each_group(), osmo_stat_item_get_group_by_name_idx(), osmo_stat_item_handler(), osmo_stats_reporter_find(), osmo_timers_update(), osmo_use_count_find(), osmo_use_count_repurpose_zero_entry(), osmo_use_count_to_str_buf(), osmo_use_count_total(), osmo_vlogp(), rate_ctr_for_each_group(), rate_ctr_get_group_by_name_idx(), rate_ctr_get_unused_name_idx(), rate_ctr_handler(), and rate_ctr_timer_cb().

◆ 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))
#define llist_entry(ptr, type, member)
Get the struct containing this list entry.
Definition: linuxlist.h:217
unsigned char * head
start of underlying memory buffer
Definition: msgb.h:57
static void prefetch(const void *x)
Definition: linuxlist.h:24

Iterate over a linked list of a given type, continuing after an 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 the 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))
#define llist_entry(ptr, type, member)
Get the struct containing this list entry.
Definition: linuxlist.h:217
unsigned char * head
start of underlying memory buffer
Definition: msgb.h:57
static void prefetch(const void *x)
Definition: linuxlist.h:24

Iterate over an rcu-protected llist of a 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_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))
#define llist_entry(ptr, type, member)
Get the struct containing this list entry.
Definition: linuxlist.h:217
unsigned char * head
start of underlying memory buffer
Definition: msgb.h:57
static void prefetch(const void *x)
Definition: linuxlist.h:24

Iterate backwards over a linked list of a 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 the 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))
#define llist_entry(ptr, type, member)
Get the struct containing this list entry.
Definition: linuxlist.h:217
write Write running configuration to or terminal n Write configuration to the copy running config startup Copy configuration n Copy running config to n Copy running config to startup write Write running configuration to or terminal n Write to terminal n
unsigned char * head
start of underlying memory buffer
Definition: msgb.h:57

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 the struct pos.

Referenced by log_fini(), and osmo_fd_disp_fds().

◆ 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))
unsigned char * head
start of underlying memory buffer
Definition: msgb.h:57
static void prefetch(const void *x)
Definition: linuxlist.h:24

Iterate over a linked list 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))
unsigned char * head
start of underlying memory buffer
Definition: msgb.h:57
static void prefetch(const void *x)
Definition: linuxlist.h:24

Iterate over an rcu-protected llist.

Parameters
posthe llist_head to use as a loop counter.
headthe head of the list over which to iterate.

◆ 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)
write Write running configuration to or terminal n Write configuration to the copy running config startup Copy configuration n Copy running config to n Copy running config to startup write Write running configuration to or terminal n Write to terminal n
unsigned char * head
start of underlying memory buffer
Definition: msgb.h:57

Iterate over a linked 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)
write Write running configuration to or terminal n Write configuration to the copy running config startup Copy configuration n Copy running config to n Copy running config to startup write Write running configuration to or terminal n Write to terminal n
unsigned char * head
start of underlying memory buffer
Definition: msgb.h:57

Iterate over an rcu-protected llist, 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_HEAD

#define LLIST_HEAD (   name)    struct llist_head name = LLIST_HEAD_INIT(name)

Define a statically-initialized variable of type llist_head.

Parameters
[in]namevariable (symbol) name.

◆ LLIST_HEAD_INIT

#define LLIST_HEAD_INIT (   name)    { &(name), &(name) }

Define a new llist_head pointing to a given llist_head.

Parameters
[in]nameanother llist_head to be pointed.

◆ llist_last_entry

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

Get the last element from a list.

Parameters
ptrthe list head to take the element from.
typethe type of the struct this is embedded in.
memberthe 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.

Referenced by llist_del().

◆ LLIST_POISON2

#define LLIST_POISON2   ((void *) 0x00200200)

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

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

◆ __llist_splice()

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

◆ 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
_newthe entry to be added.
headllist_head to prepend the element to.

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

Add a new entry into a linked list (at tail).

Parameters
_newthe entry to be added.
headllist_head to append the element to.

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

References __llist_add(), and llist_head::prev.

Referenced by _osmo_use_count_get_put(), alloc_entry(), llist_move_tail(), log_add_target(), msgb_enqueue(), osmo_counter_alloc(), osmo_fd_register(), osmo_fsm_register(), osmo_signal_register_handler(), osmo_use_count_create(), and osmo_use_count_make_static_entries().

◆ llist_count()

static unsigned int llist_count ( const struct llist_head head)
inlinestatic

Count number 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.

Referenced by osmo_counters_count().

◆ llist_del()

static void llist_del ( struct llist_head entry)
inlinestatic

◆ llist_del_init()

static void llist_del_init ( struct llist_head entry)
inlinestatic

Delete a single entry from a linked list and reinitialize it.

Parameters
entrythe element to delete and reinitialize.

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)
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_stats_timer_cb(), osmo_timer_del(), osmo_wqueue_bfd_cb(), osmo_wqueue_clear(), and rate_ctr_group_free().

◆ 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_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
llistthe entry to move.
headthe 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 linked lists.

Parameters
llistthe new linked list to add.
headthe place to add llist within 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
llistthe new linked list to add.
headthe place to add it within the first llist.

The llist is reinitialised.

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

◆ prefetch()

static void prefetch ( const void *  x)
inlinestatic