/src/vlc/include/vlc_queue.h

Source (jump to first uncovered line)
/*****************************************************************************
 * vlc_queue.h: generic queue functions
 *****************************************************************************
 * Copyright (C) 2020 Rémi Denis-Courmont
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
 *****************************************************************************/

#ifndef VLC_QUEUE_H
#define VLC_QUEUE_H

/**
 * @defgroup queue Thread-safe queues (FIFO)
 * @ingroup cext
 * @{
 * @file vlc_queue.h
 */

#include <stdbool.h>
#include <stdint.h>
#include <vlc_common.h>

/**
 * Opaque type for queue entry.
 */
struct vlc_queue_entry;

/**
 * Thread-safe queue (a.k.a. FIFO).
 */
typedef struct vlc_queue
{
    struct vlc_queue_entry *first;
    struct vlc_queue_entry **lastp;
    ptrdiff_t next_offset;
    vlc_mutex_t lock;
    vlc_cond_t wait;
} vlc_queue_t;

/**
 * Initializes a queue.
 *
 * @param queue storage space for the queue
 * @param next_offset offset of the pointer to the next element
 *                    within a queue entry (as per @c offsetof())
 */
VLC_API void vlc_queue_Init(vlc_queue_t *queue, ptrdiff_t next_offset);

/**
 * @defgroup queue_ll Queue internals
 *
 * Low-level queue functions.
 *
 * In some cases, the high-level queue functions do not exactly fit the
 * use case requirements, and it is necessary to access the queue internals.
 * This typically occurs when threads wait for elements to be added to the
 * queue at the same time as some other type of events.
 * @{
 */
/**
 * Locks a queue.
 *
 * No more than one thread can lock a queue at any given time, and no other
 * thread can modify the queue while it is locked.
 * Accordingly, if the queue is already locked by another thread, this function
 * waits.
 *
 * Use vlc_queue_Unlock() to release the lock.
 *
 * @warning Recursively locking a single queue is undefined.
 * Also locking more than one queue at a time may lead to lock inversion:
 * mind the locking order!
 */
static inline void vlc_queue_Lock(vlc_queue_t *q)
{
    vlc_mutex_lock(&q->lock);
}

/**
 * Unlocks a queue.
 *
 * This releases the lock on a queue, allowing other threads to manipulate the
 * queue. The behaviour is undefined if the calling thread is not holding the
 * queue lock.
 */
static inline void vlc_queue_Unlock(vlc_queue_t *q)
{
    vlc_mutex_unlock(&q->lock);
}

/**
 * Wakes one thread waiting for a queue entry up.
 */
static inline void vlc_queue_Signal(vlc_queue_t *q)
{
    vlc_cond_signal(&q->wait);
}

/**
 * Waits for a queue entry.
 *
 * @note This function is a cancellation point.
 * In case of cancellation, the queue will be locked,
 * as is consistent for condition variable semantics.
 *
 * @bug This function should probably not be aware of cancellation.
 */
static inline void vlc_queue_Wait(vlc_queue_t *q)
{
    vlc_cond_wait(&q->wait, &q->lock);
}

/**
 * Queues an entry (without locking).
 *
 * This function enqueues an entry, or rather a linked-list of entries, in a
 * thread-safe queue, without taking the queue lock.
 *
 * @warning It is assumed that the caller already holds the queue lock;
 * otherwise the behaviour is undefined.
 *
 * @param entry NULL-terminated list of entries to queue
 *              (if NULL, this function has no effects)
 */
VLC_API void vlc_queue_EnqueueUnlocked(vlc_queue_t *, void *entry);

/**
 * Dequeues the oldest entry (without locking).
 *
 * This function dequeues an entry from a thread-safe queue. It is assumed
 * that the caller already holds the queue lock; otherwise the behaviour is
 * undefined.
 *
 * @warning It is assumed that the caller already holds the queue lock;
 * otherwise the behaviour is undefined.
 *
 * @return the first entry in the queue, or NULL if the queue is empty
 */
VLC_API void *vlc_queue_DequeueUnlocked(vlc_queue_t *) VLC_USED;

/**
 * Dequeues all entries (without locking).
 *
 * This is equivalent to calling vlc_queue_DequeueUnlocked() repeatedly until
 * the queue is emptied. However this function is much faster than that, as it
 * does not need to update the linked-list pointers.
 *
 * @warning It is assumed that the caller already holds the queue lock;
 * otherwise the behaviour is undefined.
 *
 * @return a linked-list of all entries (possibly NULL if none)
 */
VLC_API void *vlc_queue_DequeueAllUnlocked(vlc_queue_t *) VLC_USED;

/**
 * Checks if a queue is empty (without locking).
 *
 * @warning It is assumed that the caller already holds the queue lock;
 * otherwise the behaviour is undefined.
 *
 * @retval false the queue contains one or more entries
 * @retval true the queue is empty
 */
VLC_USED static inline bool vlc_queue_IsEmpty(const vlc_queue_t *q)
{
    return q->first == NULL;
}

/** @} */

/**
 * Queues an entry.
 *
 * This function enqueues an entry, or rather a linked-list of entries, in a
 * thread-safe queue.
 *
 * @param entry list of entries (if NULL, this function has no effects)
 */
VLC_API void vlc_queue_Enqueue(vlc_queue_t *, void *entry);

/**
 * Dequeues the oldest entry.
 *
 * This function dequeues an entry from a thread-safe queue. If the queue is
 * empty, it will wait until at least one entry is available.
 *
 * @param queue queue object to dequeue an entry from
 *
 * @return the first entry in the queue, or NULL if the queue is empty
 */
VLC_API void *vlc_queue_Dequeue(vlc_queue_t *queue) VLC_USED;

/**
 * Dequeues all entries.
 *
 * This is equivalent to calling vlc_queue_Dequeue() repeatedly until the queue
 * is emptied. However this function is much faster than that, as it
 * does not need to update the linked-list pointers.
 *
 * @return a linked-list of all entries (possibly NULL if none)
 */
VLC_API void *vlc_queue_DequeueAll(vlc_queue_t *) VLC_USED;

/**
 * @defgroup queue_killable Killable queues
 *
 * Thread-safe queues with an end flag.
 *
 * @{
 */

/**
 * Marks a queue ended.
 */
static inline void vlc_queue_Kill(vlc_queue_t *q,
                                  bool *restrict tombstone)
{
    vlc_queue_Lock(q);
    *tombstone = true;
    vlc_queue_Signal(q);
    vlc_queue_Unlock(q);
}

/**
 * Dequeues one entry from a killable queue.
 *
 * @return an entry, or NULL if the queue is empty and has been ended.
 */
static inline void *vlc_queue_DequeueKillable(vlc_queue_t *q,
                                              const bool *tombstone)
{
    void *entry;

    vlc_queue_Lock(q);
    while (vlc_queue_IsEmpty(q) && !*tombstone)
        vlc_queue_Wait(q);

    entry = vlc_queue_DequeueUnlocked(q);
    vlc_queue_Unlock(q);
    return entry;
}

/** @} */

/** @} */
#endif

Coverage Report

Created: 2023-06-07 07:26

Line	Count	Source (jump to first uncovered line)
1		/*****************************************************************************
2		* vlc_queue.h: generic queue functions
3		*****************************************************************************
4		* Copyright (C) 2020 Rémi Denis-Courmont
5		*
6		* This program is free software; you can redistribute it and/or modify it
7		* under the terms of the GNU Lesser General Public License as published by
8		* the Free Software Foundation; either version 2.1 of the License, or
9		* (at your option) any later version.
10		*
11		* This program is distributed in the hope that it will be useful,
12		* but WITHOUT ANY WARRANTY; without even the implied warranty of
13		* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14		* GNU Lesser General Public License for more details.
15		*
16		* You should have received a copy of the GNU Lesser General Public License
17		* along with this program; if not, write to the Free Software Foundation,
18		* Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
19		*****************************************************************************/
20
21		#ifndef VLC_QUEUE_H
22		#define VLC_QUEUE_H
23
24		/**
25		* @defgroup queue Thread-safe queues (FIFO)
26		* @ingroup cext
27		* @{
28		* @file vlc_queue.h
29		*/
30
31		#include <stdbool.h>
32		#include <stdint.h>
33		#include <vlc_common.h>
34
35		/**
36		* Opaque type for queue entry.
37		*/
38		struct vlc_queue_entry;
39
40		/**
41		* Thread-safe queue (a.k.a. FIFO).
42		*/
43		typedef struct vlc_queue
44		{
45		struct vlc_queue_entry *first;
46		struct vlc_queue_entry **lastp;
47		ptrdiff_t next_offset;
48		vlc_mutex_t lock;
49		vlc_cond_t wait;
50		} vlc_queue_t;
51
52		/**
53		* Initializes a queue.
54		*
55		* @param queue storage space for the queue
56		* @param next_offset offset of the pointer to the next element
57		* within a queue entry (as per @c offsetof())
58		*/
59		VLC_API void vlc_queue_Init(vlc_queue_t *queue, ptrdiff_t next_offset);
60
61		/**
62		* @defgroup queue_ll Queue internals
63		*
64		* Low-level queue functions.
65		*
66		* In some cases, the high-level queue functions do not exactly fit the
67		* use case requirements, and it is necessary to access the queue internals.
68		* This typically occurs when threads wait for elements to be added to the
69		* queue at the same time as some other type of events.
70		* @{
71		*/
72		/**
73		* Locks a queue.
74		*
75		* No more than one thread can lock a queue at any given time, and no other
76		* thread can modify the queue while it is locked.
77		* Accordingly, if the queue is already locked by another thread, this function
78		* waits.
79		*
80		* Use vlc_queue_Unlock() to release the lock.
81		*
82		* @warning Recursively locking a single queue is undefined.
83		* Also locking more than one queue at a time may lead to lock inversion:
84		* mind the locking order!
85		*/
86		static inline void vlc_queue_Lock(vlc_queue_t *q)
87	0	{
88	0	vlc_mutex_lock(&q->lock);
89	0	}
90
91		/**
92		* Unlocks a queue.
93		*
94		* This releases the lock on a queue, allowing other threads to manipulate the
95		* queue. The behaviour is undefined if the calling thread is not holding the
96		* queue lock.
97		*/
98		static inline void vlc_queue_Unlock(vlc_queue_t *q)
99	0	{
100	0	vlc_mutex_unlock(&q->lock);
101	0	}
102
103		/**
104		* Wakes one thread waiting for a queue entry up.
105		*/
106		static inline void vlc_queue_Signal(vlc_queue_t *q)
107	0	{
108	0	vlc_cond_signal(&q->wait);
109	0	}
110
111		/**
112		* Waits for a queue entry.
113		*
114		* @note This function is a cancellation point.
115		* In case of cancellation, the queue will be locked,
116		* as is consistent for condition variable semantics.
117		*
118		* @bug This function should probably not be aware of cancellation.
119		*/
120		static inline void vlc_queue_Wait(vlc_queue_t *q)
121	0	{
122	0	vlc_cond_wait(&q->wait, &q->lock);
123	0	}
124
125		/**
126		* Queues an entry (without locking).
127		*
128		* This function enqueues an entry, or rather a linked-list of entries, in a
129		* thread-safe queue, without taking the queue lock.
130		*
131		* @warning It is assumed that the caller already holds the queue lock;
132		* otherwise the behaviour is undefined.
133		*
134		* @param entry NULL-terminated list of entries to queue
135		* (if NULL, this function has no effects)
136		*/
137		VLC_API void vlc_queue_EnqueueUnlocked(vlc_queue_t , void entry);
138
139		/**
140		* Dequeues the oldest entry (without locking).
141		*
142		* This function dequeues an entry from a thread-safe queue. It is assumed
143		* that the caller already holds the queue lock; otherwise the behaviour is
144		* undefined.
145		*
146		* @warning It is assumed that the caller already holds the queue lock;
147		* otherwise the behaviour is undefined.
148		*
149		* @return the first entry in the queue, or NULL if the queue is empty
150		*/
151		VLC_API void vlc_queue_DequeueUnlocked(vlc_queue_t ) VLC_USED;
152
153		/**
154		* Dequeues all entries (without locking).
155		*
156		* This is equivalent to calling vlc_queue_DequeueUnlocked() repeatedly until
157		* the queue is emptied. However this function is much faster than that, as it
158		* does not need to update the linked-list pointers.
159		*
160		* @warning It is assumed that the caller already holds the queue lock;
161		* otherwise the behaviour is undefined.
162		*
163		* @return a linked-list of all entries (possibly NULL if none)
164		*/
165		VLC_API void vlc_queue_DequeueAllUnlocked(vlc_queue_t ) VLC_USED;
166
167		/**
168		* Checks if a queue is empty (without locking).
169		*
170		* @warning It is assumed that the caller already holds the queue lock;
171		* otherwise the behaviour is undefined.
172		*
173		* @retval false the queue contains one or more entries
174		* @retval true the queue is empty
175		*/
176		VLC_USED static inline bool vlc_queue_IsEmpty(const vlc_queue_t *q)
177	0	{
178	0	return q->first == NULL;
179	0	}
180
181		/** @} */
182
183		/**
184		* Queues an entry.
185		*
186		* This function enqueues an entry, or rather a linked-list of entries, in a
187		* thread-safe queue.
188		*
189		* @param entry list of entries (if NULL, this function has no effects)
190		*/
191		VLC_API void vlc_queue_Enqueue(vlc_queue_t , void entry);
192
193		/**
194		* Dequeues the oldest entry.
195		*
196		* This function dequeues an entry from a thread-safe queue. If the queue is
197		* empty, it will wait until at least one entry is available.
198		*
199		* @param queue queue object to dequeue an entry from
200		*
201		* @return the first entry in the queue, or NULL if the queue is empty
202		*/
203		VLC_API void vlc_queue_Dequeue(vlc_queue_t queue) VLC_USED;
204
205		/**
206		* Dequeues all entries.
207		*
208		* This is equivalent to calling vlc_queue_Dequeue() repeatedly until the queue
209		* is emptied. However this function is much faster than that, as it
210		* does not need to update the linked-list pointers.
211		*
212		* @return a linked-list of all entries (possibly NULL if none)
213		*/
214		VLC_API void vlc_queue_DequeueAll(vlc_queue_t ) VLC_USED;
215
216		/**
217		* @defgroup queue_killable Killable queues
218		*
219		* Thread-safe queues with an end flag.
220		*
221		* @{
222		*/
223
224		/**
225		* Marks a queue ended.
226		*/
227		static inline void vlc_queue_Kill(vlc_queue_t *q,
228		bool *restrict tombstone)
229	0	{
230	0	vlc_queue_Lock(q);
231	0	*tombstone = true;
232	0	vlc_queue_Signal(q);
233	0	vlc_queue_Unlock(q);
234	0	} Unexecuted instantiation: demux-run.c:vlc_queue_Kill Unexecuted instantiation: decoder.c:vlc_queue_Kill
235
236		/**
237		* Dequeues one entry from a killable queue.
238		*
239		* @return an entry, or NULL if the queue is empty and has been ended.
240		*/
241		static inline void vlc_queue_DequeueKillable(vlc_queue_t q,
242		const bool *tombstone)
243	0	{
244	0	void *entry;
245	0
246	0	vlc_queue_Lock(q);
247	0	while (vlc_queue_IsEmpty(q) && !*tombstone)
248	0	vlc_queue_Wait(q);
249	0
250	0	entry = vlc_queue_DequeueUnlocked(q);
251	0	vlc_queue_Unlock(q);
252	0	return entry;
253	0	} Unexecuted instantiation: demux-run.c:vlc_queue_DequeueKillable Unexecuted instantiation: decoder.c:vlc_queue_DequeueKillable
254
255		/** @} */
256
257		/** @} */
258		#endif