include/vlc_queue.h

   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 {
  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  */
 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 {
 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  */
 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 offset offset of the next pointer within a queue entry
 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 *) 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 {
 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
 250     entry = vlc_queue_DequeueUnlocked(q);
 251     vlc_queue_Unlock(q);
 252     return entry;
 253 }
 254
 255 /** @} */
 256
 257 /** @} */
 258 #endif