Linked lists

Collaboration diagram for Linked lists:

Files
file	vlc_list.h
	This provides convenience helpers for linked lists.

Data Structures
struct	vlc_list
	Doubly-linked list node. More...
struct	vlc_list_it
	List iterator. More...

Macros
#define	VLC_LIST_INITIALIZER(h)   { h, h }
	Static initializer for a list head. More...
#define	vlc_list_entry_aligned_size(p)   ((sizeof (*(p)) + sizeof (max_align_t) - 1) / sizeof (max_align_t))
#define	vlc_list_entry_dummy(p)   (0 ? (p) : ((void *)(&(max_align_t[vlc_list_entry_aligned_size(p)]){})))
#define	vlc_list_offset_p(p, member)   ((p) = vlc_list_entry_dummy(p), (char *)(&(p)->member) - (char *)(p))
#define	vlc_list_entry_p(node, p, member)   (0 ? (p) : (void *)(((char *)(node)) - vlc_list_offset_p(p, member)))
#define	vlc_list_foreach(pos, head, member)
	List iteration macro. More...
#define	vlc_list_entry(ptr, type, member)   container_of(ptr, type, member)
	Converts a list node pointer to an element pointer. More...
#define	vlc_list_first_entry_or_null(head, type, member)   ((type *)vlc_list_first_or_null(head, offsetof (type, member)))
	Gets the first element. More...
#define	vlc_list_last_entry_or_null(head, type, member)   ((type *)vlc_list_last_or_null(head, offsetof (type, member)))
	Gets the last element. More...
#define	vlc_list_prev_entry_or_null(head, entry, type, member)
#define	vlc_list_next_entry_or_null(head, entry, type, member)

Functions
static void	vlc_list_init (struct vlc_list *restrict head)
	Initializes an empty list head. More...
static void	vlc_list_add_between (struct vlc_list *restrict node, struct vlc_list *prev, struct vlc_list *next)
	Inserts an element in a list. More...
static void	vlc_list_add_after (struct vlc_list *restrict node, struct vlc_list *prev)
	Inserts an element after another. More...
static void	vlc_list_add_before (struct vlc_list *restrict node, struct vlc_list *next)
	Inserts an element before another. More...
static void	vlc_list_append (struct vlc_list *restrict node, struct vlc_list *head)
	Appends an element into a list. More...
static void	vlc_list_prepend (struct vlc_list *restrict node, struct vlc_list *head)
	Prepends an element into a list. More...
static void	vlc_list_remove (struct vlc_list *restrict node)
	Removes an element from a list. More...
static void	vlc_list_replace (const struct vlc_list *original, struct vlc_list *restrict substitute)
	Replaces an element with another one. More...
static bool	vlc_list_is_empty (const struct vlc_list *head)
	Checks if a list is empty. More...
static bool	vlc_list_is_first (const struct vlc_list *node, const struct vlc_list *head)
	Checks if an element is first in a list. More...
static bool	vlc_list_is_last (const struct vlc_list *node, const struct vlc_list *head)
	Checks if an element is last in a list. More...
static struct vlc_list_it	vlc_list_it_start (const struct vlc_list *head)
static bool	vlc_list_it_continue (const struct vlc_list_it *restrict it)
static void	vlc_list_it_next (struct vlc_list_it *restrict it)
static void *	vlc_list_first_or_null (const struct vlc_list *head, size_t offset)
static void *	vlc_list_last_or_null (const struct vlc_list *head, size_t offset)
static void *	vlc_list_prev_or_null (const struct vlc_list *head, struct vlc_list *node, size_t offset)
static void *	vlc_list_next_or_null (const struct vlc_list *head, struct vlc_list *node, size_t offset)

Detailed Description

Macro Definition Documentation

vlc_list_entry

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

Converts a list node pointer to an element pointer.

Parameters

ptr	list node pointer
type	list data element type name
member	list node member within the data element compound type

vlc_list_entry_aligned_size

#define vlc_list_entry_aligned_size

(

p

)

((sizeof (*(p)) + sizeof (max_align_t) - 1) / sizeof (max_align_t))

vlc_list_entry_dummy

#define vlc_list_entry_dummy

(

p

)

(0 ? (p) : ((void *)(&(max_align_t[vlc_list_entry_aligned_size(p)]){})))

vlc_list_entry_p

#define vlc_list_entry_p	(		node,
			p,
			member
	)		(0 ? (p) : (void *)(((char *)(node)) - vlc_list_offset_p(p, member)))

vlc_list_first_entry_or_null

#define vlc_list_first_entry_or_null	(		head,
			type,
			member
	)		((type *)vlc_list_first_or_null(head, offsetof (type, member)))

Gets the first element.

Parameters

head	Head of list whose last element to get [IN].

Returns

the first entry in a list or NULL if empty.

Referenced by info_category_Delete(), and QueueTake().

vlc_list_foreach

#define vlc_list_foreach	(		pos,
			head,
			member
	)

Value:

for (struct vlc_list_it vlc_list_it_##pos = vlc_list_it_start(head); \
         vlc_list_it_continue(&(vlc_list_it_##pos)) \
          && ((pos) = vlc_list_entry_p((vlc_list_it_##pos).current, \
                                       pos, member), true); \
         vlc_list_it_next(&(vlc_list_it_##pos)))

List iteration macro.

This macro iterates over all elements (excluding the head) of a list, in order from the first to the last.

For each iteration, it sets the cursor variable to the current element.

Parameters

pos	Cursor pointer variable identifier.
head	Head pointer of the list to iterate [IN].
member	Identifier of the member of the data type serving as list node.

Note

It it safe to delete the current item while iterating. It is however not safe to delete another item.

Referenced by background_worker_RequestProbe(), BackgroundWorkerCancelLocked(), EsOutChangePosition(), EsOutProgramChangePause(), EsOutProgramDel(), EsOutProgramFind(), EsOutProgramsChangeRate(), EsOutProgramUpdateScrambled(), EsOutSetRecord(), EsOutTerminate(), EsOutVaControlLocked(), httpd_HostCreate(), httpd_HostDelete(), httpd_UrlDelete(), httpd_UrlNew(), httpdLoop(), QueueRemoveAll(), vlc_list_HasInput(), vlc_media_source_provider_Find(), vlc_media_tree_Delete(), vlc_ml_event_send(), vlc_player_destructor_Thread(), vlc_player_SendSmpteTimerSourceUpdates(), vlc_player_SendTimerSourceUpdates(), and vlc_player_UpdateTimerState().

VLC_LIST_INITIALIZER

#define VLC_LIST_INITIALIZER

(

h

)

{ h, h }

Static initializer for a list head.

vlc_list_last_entry_or_null

#define vlc_list_last_entry_or_null	(		head,
			type,
			member
	)		((type *)vlc_list_last_or_null(head, offsetof (type, member)))

Gets the last element.

Parameters

head	Head of list whose last element to get [IN].

Returns

the last entry in a list or NULL if empty.

vlc_list_next_entry_or_null

#define vlc_list_next_entry_or_null	(		head,
			entry,
			type,
			member
	)

Value:

((type *)vlc_list_next_or_null(head, &(entry)->member, \
                                       offsetof (type, member)))

vlc_list_offset_p

#define vlc_list_offset_p	(		p,
			member
	)		((p) = vlc_list_entry_dummy(p), (char *)(&(p)->member) - (char *)(p))

vlc_list_prev_entry_or_null

#define vlc_list_prev_entry_or_null	(		head,
			entry,
			type,
			member
	)

Value:

((type *)vlc_list_prev_or_null(head, &(entry)->member, \
                                       offsetof (type, member)))

Function Documentation

vlc_list_add_after()

static void vlc_list_add_after ( struct vlc_list *restrict  node, struct vlc_list *  prev  )

inlinestatic

Inserts an element after another.

Parameters

node	Node pointer of the element to insert [OUT].
prev	Node pointer of the previous element.

References vlc_list::next, and vlc_list_add_between().

Referenced by vlc_list_prepend().

vlc_list_add_before()

static void vlc_list_add_before ( struct vlc_list *restrict  node, struct vlc_list *  next  )

inlinestatic

Inserts an element before another.

Parameters

node	Node pointer of the element to insert [OUT].
prev	Node pointer of the next element.

References vlc_list::prev, and vlc_list_add_between().

Referenced by vlc_list_append().

vlc_list_add_between()

static void vlc_list_add_between ( struct vlc_list *restrict  node, struct vlc_list *  prev, struct vlc_list *  next  )

inlinestatic

Inserts an element in a list.

Parameters

node	Node pointer of the element to insert [OUT].
prev	Node pointer of the previous element.
next	Node pointer of the next element.

References vlc_list::next, and vlc_list::prev.

Referenced by vlc_list_add_after(), vlc_list_add_before(), and vlc_list_replace().

vlc_list_append()

static void vlc_list_append ( struct vlc_list *restrict  node, struct vlc_list *  head  )

inlinestatic

Appends an element into a list.

Parameters

node	Node pointer of the element to append to the list [OUT].
head	Head pointer of the list to append the element to.

References vlc_list_add_before().

Referenced by EsOutAddSlaveLocked(), EsOutProgramAdd(), httpd_HostCreate(), httpd_UrlNew(), httpdLoop(), info_category_ReplaceInfo(), info_category_VaAddInfo(), QueuePush(), SpawnThread(), vlc_media_source_provider_Add(), vlc_media_tree_AddListener(), vlc_ml_event_register_callback(), vlc_player_AddListener(), vlc_player_AddSmpteTimer(), vlc_player_AddTimer(), vlc_player_aout_AddListener(), vlc_player_destructor_AddInput(), vlc_player_destructor_AddStoppingInput(), vlc_player_vout_AddListener(), and vlc_playlist_AddListener().

vlc_list_first_or_null()

static void* vlc_list_first_or_null ( const struct vlc_list *  head, size_t  offset  )

inlinestatic

References vlc_list::next, and vlc_list_is_empty().

vlc_list_init()

static void vlc_list_init ( struct vlc_list *restrict  head )

inlinestatic

Initializes an empty list head.

Referenced by background_worker_Create(), httpd_HostCreate(), info_category_New(), input_EsOutNew(), input_item_MergeInfos(), libvlc_MlCreate(), vlc_media_source_provider_New(), vlc_media_tree_Delete(), vlc_media_tree_New(), vlc_player_InitTimer(), vlc_player_New(), and vlc_playlist_New().

vlc_list_is_empty()

static bool vlc_list_is_empty ( const struct vlc_list *  head )

inlinestatic

Checks if a list is empty.

Parameters

head	Head of the list to be checked [IN].

Return values

false	The list is not empty.
true	The list is empty.

Note

Obviously the list must have been initialized. Otherwise, the behaviour is undefined.

References vlc_list::next.

Referenced by EsOutDelete(), EsOutVaControlLocked(), httpd_HostDelete(), httpdLoop(), libvlc_MlRelease(), QueueTake(), vlc_list_first_or_null(), vlc_list_last_or_null(), vlc_player_Delete(), vlc_player_DestroyTimer(), vlc_player_destructor_IsEmpty(), vlc_player_destructor_Thread(), vlc_player_UpdateTimer(), and vlc_playlist_Delete().

vlc_list_is_first()

static bool vlc_list_is_first ( const struct vlc_list *  node, const struct vlc_list *  head  )

inlinestatic

Checks if an element is first in a list.

Parameters

node	List node of the element [IN].
head	Head of the list to be checked [IN].

Return values

false	The element is not first (or is in another list).
true	The element is first.

References vlc_list::prev.

Referenced by vlc_list_prev_or_null().

vlc_list_is_last()

static bool vlc_list_is_last ( const struct vlc_list *  node, const struct vlc_list *  head  )

inlinestatic

Checks if an element is last in a list.

Parameters

node	List node of the element [IN].
head	Head of the list to be checked [IN].

Return values

false	The element is not last (or is in another list).
true	The element is last.

References vlc_list::next.

Referenced by vlc_list_next_or_null().

vlc_list_it_continue()

static bool vlc_list_it_continue ( const struct vlc_list_it *restrict  it )

inlinestatic

vlc_list_it_next()

static void vlc_list_it_next ( struct vlc_list_it *restrict  it )

inlinestatic

References vlc_list::next.

vlc_list_it_start()

static struct vlc_list_it vlc_list_it_start ( const struct vlc_list *  head )

static

References vlc_list::next.

vlc_list_last_or_null()

static void* vlc_list_last_or_null ( const struct vlc_list *  head, size_t  offset  )

inlinestatic

References vlc_list::prev, and vlc_list_is_empty().

vlc_list_next_or_null()

static void* vlc_list_next_or_null ( const struct vlc_list *  head, struct vlc_list *  node, size_t  offset  )

inlinestatic

References vlc_list::next, and vlc_list_is_last().

vlc_list_prepend()

static void vlc_list_prepend ( struct vlc_list *restrict  node, struct vlc_list *  head  )

inlinestatic

Prepends an element into a list.

Parameters

node	Node pointer of the element to prepend to the list [OUT].
head	Head pointer of the list to prepend the element to.

References vlc_list_add_after().

vlc_list_prev_or_null()

static void* vlc_list_prev_or_null ( const struct vlc_list *  head, struct vlc_list *  node, size_t  offset  )

inlinestatic

References vlc_list::prev, and vlc_list_is_first().

vlc_list_remove()

static void vlc_list_remove ( struct vlc_list *restrict  node )

inlinestatic

Removes an element from a list.

Parameters

node	Node of the element to remove from a list.

Warning

The element must be inside a list. Otherwise the behaviour is undefined.

References vlc_list::next, and vlc_list::prev.

Referenced by EsOutProgramDel(), EsOutTerminate(), EsTerminate(), httpd_ClientDestroy(), httpd_HostDelete(), httpd_UrlDelete(), info_category_Delete(), info_category_DeleteInfo(), info_category_ReplaceInfo(), QueueRemoveAll(), QueueTake(), RemoveThread(), vlc_media_source_provider_Remove(), vlc_media_tree_RemoveListener(), vlc_ml_event_unregister_callback(), vlc_ml_event_unregister_from_callback(), vlc_player_aout_RemoveListener(), vlc_player_destructor_AddJoinableInput(), vlc_player_destructor_AddStoppingInput(), vlc_player_destructor_Thread(), vlc_player_RemoveListener(), vlc_player_RemoveTimer(), vlc_player_vout_RemoveListener(), and vlc_playlist_RemoveListener().

vlc_list_replace()

static void vlc_list_replace ( const struct vlc_list *  original, struct vlc_list *restrict  substitute  )

inlinestatic

Replaces an element with another one.

Parameters

origin	Node pointer of the element to remove from the list [IN].
substitute	Node pointer of the replacement [OUT].

References vlc_list::next, vlc_list::prev, and vlc_list_add_between().