VLC  4.0.0-dev
vlc_queue.h
Go to the documentation of this file.
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;
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 {
88  vlc_mutex_lock(&q->lock);
89 }
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 {
100  vlc_mutex_unlock(&q->lock);
101 }
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 {
108  vlc_cond_signal(&q->wait);
109 }
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 {
122  vlc_cond_wait(&q->wait, &q->lock);
123 }
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  */
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  */
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  */
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 {
178  return q->first == NULL;
179 }
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  */
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  */
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  */
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 {
230  vlc_queue_Lock(q);
231  *tombstone = true;
232  vlc_queue_Signal(q);
233  vlc_queue_Unlock(q);
234 }
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  bool *restrict tombstone)
243 {
244  void *entry;
245 
246  vlc_queue_Lock(q);
247  while (vlc_queue_IsEmpty(q) && !*tombstone)
248  vlc_queue_Wait(q);
249 
251  vlc_queue_Unlock(q);
252  return entry;
253 }
254 
255 /** @} */
256 
257 /** @} */
258 #endif
#define VLC_USED
Definition: fourcc_gen.c:32
#define VLC_API
Definition: fourcc_gen.c:31
void vlc_cond_signal(vlc_cond_t *cond)
Wakes up one thread waiting on a condition variable.
Definition: threads.c:203
void vlc_cond_wait(vlc_cond_t *cond, vlc_mutex_t *mutex)
Waits on a condition variable.
Definition: threads.c:290
void vlc_mutex_unlock(vlc_mutex_t *mtx)
Releases a mutex.
Definition: threads.c:159
void vlc_mutex_lock(vlc_mutex_t *mtx)
Acquires a mutex.
Definition: threads.c:105
static void * vlc_queue_DequeueKillable(vlc_queue_t *q, bool *restrict tombstone)
Dequeues one entry from a killable queue.
Definition: vlc_queue.h:242
static void vlc_queue_Kill(vlc_queue_t *q, bool *restrict tombstone)
Marks a queue ended.
Definition: vlc_queue.h:228
void * vlc_queue_DequeueAllUnlocked(vlc_queue_t *) VLC_USED
Dequeues all entries (without locking).
Definition: queue.c:116
static void vlc_queue_Lock(vlc_queue_t *q)
Locks a queue.
Definition: vlc_queue.h:87
static void vlc_queue_Wait(vlc_queue_t *q)
Waits for a queue entry.
Definition: vlc_queue.h:121
void * vlc_queue_DequeueUnlocked(vlc_queue_t *) VLC_USED
Dequeues the oldest entry (without locking).
Definition: queue.c:96
void vlc_queue_EnqueueUnlocked(vlc_queue_t *, void *entry)
Queues an entry (without locking).
Definition: queue.c:80
static void vlc_queue_Signal(vlc_queue_t *q)
Wakes one thread waiting for a queue entry up.
Definition: vlc_queue.h:107
static void vlc_queue_Unlock(vlc_queue_t *q)
Unlocks a queue.
Definition: vlc_queue.h:99
static VLC_USED bool vlc_queue_IsEmpty(const vlc_queue_t *q)
Checks if a queue is empty (without locking).
Definition: vlc_queue.h:177
void * vlc_queue_DequeueAll(vlc_queue_t *) VLC_USED
Dequeues all entries.
Definition: queue.c:151
void vlc_queue_Enqueue(vlc_queue_t *, void *entry)
Queues an entry.
Definition: queue.c:128
struct vlc_queue vlc_queue_t
Thread-safe queue (a.k.a.
void vlc_queue_Init(vlc_queue_t *queue, ptrdiff_t next_offset)
Initializes a queue.
Definition: queue.c:71
void * vlc_queue_Dequeue(vlc_queue_t *queue) VLC_USED
Dequeues the oldest entry.
Definition: queue.c:135
Definition: fourcc_gen.c:52
Condition variable.
Definition: vlc_threads.h:320
Mutex.
Definition: vlc_threads.h:193
Thread-safe queue (a.k.a.
Definition: vlc_queue.h:45
struct vlc_queue_entry * first
Definition: vlc_queue.h:46
struct vlc_queue_entry ** lastp
Definition: vlc_queue.h:47
vlc_cond_t wait
Definition: vlc_queue.h:50
vlc_mutex_t lock
Definition: vlc_queue.h:49
ptrdiff_t next_offset
Definition: vlc_queue.h:48
This file is a collection of common definitions and types.