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.
#define	vlc_list_foreach(pos, head, member)
	List iteration macro.
#define	vlc_list_foreach_const(pos, head, member)
#define	vlc_list_reverse_foreach(pos, head, member)
	List iteration macro.
#define	vlc_list_entry(ptr, type, member)   container_of(ptr, type, member)
	Converts a list node pointer to an element pointer.
#define	vlc_list_first_entry_or_null(head, type, member)    ((type *)vlc_list_first_or_null(head, offsetof (type, member)))
	Gets the first element.
#define	vlc_list_last_entry_or_null(head, type, member)    ((type *)vlc_list_last_or_null(head, offsetof (type, member)))
	Gets the last element.
#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.
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.
static void	vlc_list_add_after (struct vlc_list *restrict node, struct vlc_list *prev)
	Inserts an element after another.
static void	vlc_list_add_before (struct vlc_list *restrict node, struct vlc_list *next)
	Inserts an element before another.
static void	vlc_list_append (struct vlc_list *restrict node, struct vlc_list *head)
	Appends an element into a list.
static void	vlc_list_prepend (struct vlc_list *restrict node, struct vlc_list *head)
	Prepends an element into a list.
static void	vlc_list_remove (struct vlc_list *restrict node)
	Removes an element from a list.
static void	vlc_list_replace (const struct vlc_list *original, struct vlc_list *restrict substitute)
	Replaces an element with another one.
static bool	vlc_list_is_empty (const struct vlc_list *head)
	Checks if a list is empty.
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.
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.
static struct vlc_list_it	vlc_list_it_start (struct vlc_list *head)
static struct vlc_list_it	vlc_list_it_start_const (const struct vlc_list *head)
static struct vlc_list_it	vlc_list_it_reverse_start (struct vlc_list *head)
static struct vlc_list_it	vlc_list_it_reverse_start_const (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_it_prev (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, const struct vlc_list *node, size_t offset)
static void *	vlc_list_next_or_null (const struct vlc_list *head, const 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_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	[in] Head of list whose last element to get.

Returns

the first entry in a list or NULL if empty.

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) = container_of((vlc_list_it__##pos).current, \
                                   typeof (*(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	[in] Head pointer of the list to iterate.
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.

vlc_list_foreach_const

#define vlc_list_foreach_const	(		pos,
			head,
			member
	)

Value:

    for (struct vlc_list_it vlc_list_it__##pos = vlc_list_it_start_const(head); \
         vlc_list_it_continue(&(vlc_list_it__##pos)) \
          && ((pos) = container_of((vlc_list_it__##pos).current, \
                                   const typeof (*(pos)), member), true); \
         vlc_list_it_next(&(vlc_list_it__##pos)))

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	[in] Head of list whose last element to get.

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

vlc_list_reverse_foreach

#define vlc_list_reverse_foreach	(		pos,
			head,
			member
	)

Value:

    for (struct vlc_list_it vlc_list_it_##pos = vlc_list_it_reverse_start(head); \
         vlc_list_it_continue(&(vlc_list_it_##pos)) \
          && ((pos) = container_of((vlc_list_it_##pos).current, \
                                   typeof (*(pos)), member), true); \
         vlc_list_it_prev(&(vlc_list_it_##pos)))

List iteration macro.

This macro iterates over all elements (excluding the head) of a list, in reversed 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	[in] Head pointer of the list to iterate.
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.

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	[out] Node pointer of the element to insert
prev	Node pointer of the previous element.

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

Referenced by input_item_ReplaceInfos(), and 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	[out] Node pointer of the element to insert.
next	Node pointer of the next element.

References vlc_list::next, 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	[out] Node pointer of the element to insert.
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	[out] Node pointer of the element to append to the list.
head	Head pointer of the list to append the element to.

References vlc_list_add_before().

Referenced by aout_HotplugNotify(), EsOutAddLocked(), EsOutProgramAdd(), FetcherAddTask(), filter_chain_AppendInner(), httpd_HostCreate(), httpd_UrlNew(), httpdLoop(), info_category_ReplaceInfo(), info_category_VaAddInfo(), input_item_MergeInfos(), input_item_ReplaceInfos(), InputItemVaAddInfo(), PreparserAddTask(), vlc::list< NodeType >::push_back(), QueuePush(), sout_AnnounceRegisterSDP(), SpawnThread(), vlc_audio_meter_AddPlugin(), vlc_input_decoder_CreateSubDec(), vlc_media_source_provider_Add(), vlc_media_tree_AddListener(), vlc_ml_event_register_callback(), vlc_player_AddListener(), vlc_player_AddMetadataListener(), vlc_player_AddSmpteTimer(), vlc_player_AddTimer(), vlc_player_aout_AddListener(), vlc_player_destructor_AddInput(), vlc_player_destructor_AddStoppingInput(), vlc_player_vout_AddListener(), vlc_playlist_AddListener(), and vout_resource_Add().

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.

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

Referenced by AddressCreate(), aout_New(), CreateDecoder(), filter_chain_NewInner(), httpd_HostCreate(), info_category_New(), input_EsOutNew(), input_fetcher_New(), input_item_MergeInfos(), input_item_NewExt(), input_resource_New(), libvlc_MlCreate(), vlc_audio_meter_Init(), vlc_executor_New(), vlc_media_source_provider_New(), vlc_media_tree_Delete(), vlc_media_tree_New(), vlc_player_InitTimer(), vlc_player_New(), vlc_playlist_New(), and vlc_preparser_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	[in] Head of the list to be checked.

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 DestroyVout(), vlc::list_base< NodeType, ListType, Iterator, ConstIterator >::empty(), EsOutDelete(), EsOutVaPrivControlLocked(), filter_chain_IsEmpty(), httpd_HostDelete(), input_resource_HoldVouts(), input_resource_SetInput(), libvlc_MlRelease(), QueueTake(), RequestVoutRsc(), RunThread(), sout_AnnounceUnRegister(), vlc_executor_Delete(), vlc_input_decoder_Delete(), 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_UpdateTimerBestSource(), vlc_player_UpdateTimerSmpteSource(), 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	[in] List node of the element.
head	[in] Head of the list to be checked.

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	[in] List node of the element.
head	[in] Head of the list to be checked.

Return values

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

References vlc_list::next.

Referenced by filter_chain_VideoBufferNew(), and vlc_list_next_or_null().

vlc_list_it_continue()

static bool vlc_list_it_continue ( const struct vlc_list_it *restrict  it )

inlinestatic

References vlc_list_it::current.

Referenced by filter_chain_VideoFilter().

vlc_list_it_next()

static void vlc_list_it_next ( struct vlc_list_it *restrict  it )

inlinestatic

References vlc_list::next.

Referenced by filter_chain_VideoFilter().

vlc_list_it_prev()

static void vlc_list_it_prev ( struct vlc_list_it *restrict  it )

inlinestatic

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

vlc_list_it_reverse_start()

static struct vlc_list_it vlc_list_it_reverse_start ( struct vlc_list *  head )

inlinestatic

References vlc_list_it::head, and vlc_list::prev.

vlc_list_it_reverse_start_const()

static struct vlc_list_it vlc_list_it_reverse_start_const ( const struct vlc_list *  head )

inlinestatic

References vlc_list_it::head, and vlc_list::prev.

vlc_list_it_start()

static struct vlc_list_it vlc_list_it_start ( struct vlc_list *  head )

inlinestatic

References vlc_list_it::head, and vlc_list::next.

vlc_list_it_start_const()

static struct vlc_list_it vlc_list_it_start_const ( const struct vlc_list *  head )

inlinestatic

References vlc_list_it::head, and 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, const 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	[out] Node pointer of the element to prepend to the list.
head	Head pointer of the list to prepend the element to.

References vlc_list_add_after().

Referenced by vlc::list< NodeType >::push_front().

vlc_list_prev_or_null()

static void * vlc_list_prev_or_null ( const struct vlc_list *  head, const 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 aout_Destroy(), aout_HotplugNotify(), CancelAllTasks(), vlc::list< NodeType >::erase(), EsOutProgramDel(), EsOutTerminate(), EsTerminate(), FetcherRemoveTask(), filter_chain_DeleteFilter(), httpd_ClientDestroy(), httpd_HostDelete(), httpd_UrlDelete(), info_category_Delete(), info_category_DeleteInfo(), info_category_ReplaceInfo(), input_item_DelInfo(), input_item_ReplaceInfos(), PreparserRemoveTask(), QueueTake(), RemoveCcDecoder(), sout_AnnounceUnRegister(), vlc_audio_meter_RemovePlugin(), vlc_executor_Cancel(), 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_RemoveMetadataListener(), vlc_player_RemoveTimer(), vlc_player_vout_RemoveListener(), vlc_playlist_RemoveListener(), vlc_preparser_Cancel(), and vout_resource_Remove().

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

original	[in] Node pointer of the element to remove from the list.
substitute	[out] Node pointer of the replacement.

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

Referenced by spu_PrerenderText(), and SpuRenderSubpictures().