vlc | branch: master | Rémi Denis-Courmont <[email protected]> | Sat Apr 11 20:50:03 2020 +0300| [40fccf9121fbaa5fdbcbbaae60151bf673d0008c] | committer: Rémi Denis-Courmont
queue: add generic queue/FIFO helpers Currently, the FIFO helpers are tied to block_t. This has proven problematic in the past: some code uses block_t only for the sake of block_fifo_t. It will get worse with the introduction of separate vlc_frame_t and vlc_data_t. This provides a generic C implementation of a thread-safe queue. It is very much meant to be wrapped with more type-specific helpers. > http://git.videolan.org/gitweb.cgi/vlc.git/?a=commit;h=40fccf9121fbaa5fdbcbbaae60151bf673d0008c --- include/vlc_queue.h | 217 ++++++++++++++++++++++++++++++++++++++++++++++++++++ src/Makefile.am | 2 + src/libvlccore.sym | 7 ++ src/misc/queue.c | 160 ++++++++++++++++++++++++++++++++++++++ 4 files changed, 386 insertions(+) diff --git a/include/vlc_queue.h b/include/vlc_queue.h new file mode 100644 index 0000000000..44222c1ae0 --- /dev/null +++ b/include/vlc_queue.h @@ -0,0 +1,217 @@ +/***************************************************************************** + * 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 offset offset of the next pointer within a queue entry + * + * @return the first entry in the queue, or NULL if the queue is empty + */ +VLC_API void *vlc_queue_Dequeue(vlc_queue_t *) 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; + +/** @} */ +#endif diff --git a/src/Makefile.am b/src/Makefile.am index 163e241ee1..13c142acb4 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -83,6 +83,7 @@ pluginsinclude_HEADERS = \ ../include/vlc_playlist_export.h \ ../include/vlc_plugin.h \ ../include/vlc_probe.h \ + ../include/vlc_queue.h \ ../include/vlc_rand.h \ ../include/vlc_services_discovery.h \ ../include/vlc_fingerprinter.h \ @@ -376,6 +377,7 @@ libvlccore_la_SOURCES = \ misc/mime.c \ misc/objects.c \ misc/objres.c \ + misc/queue.c \ misc/variables.h \ misc/variables.c \ misc/xml.c \ diff --git a/src/libvlccore.sym b/src/libvlccore.sym index dada8e692f..b44431d3fd 100644 --- a/src/libvlccore.sym +++ b/src/libvlccore.sym @@ -668,6 +668,13 @@ vlc_fifo_DequeueUnlocked vlc_fifo_DequeueAllUnlocked vlc_fifo_GetCount vlc_fifo_GetBytes +vlc_queue_Init +vlc_queue_EnqueueUnlocked +vlc_queue_DequeueUnlocked +vlc_queue_DequeueAllUnlocked +vlc_queue_Enqueue +vlc_queue_Dequeue +vlc_queue_DequeueAll vlc_gl_Create vlc_gl_Release vlc_gl_Hold diff --git a/src/misc/queue.c b/src/misc/queue.c new file mode 100644 index 0000000000..2ea374a5c1 --- /dev/null +++ b/src/misc/queue.c @@ -0,0 +1,160 @@ +/***************************************************************************** + * queue.c: generic queue (FIFO) + ***************************************************************************** + * 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. + *****************************************************************************/ + +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + +#include <assert.h> +#include <stdint.h> +#include <stdlib.h> + +#include <vlc_common.h> +#include <vlc_queue.h> + +/* Opaque struct type. + * + * ISO C uses the same representation for all pointer-to-struct types. + * Still different pointer types are not compatible, i.e. cannot alias. + * So use memcpy() to read/write pointer values. + */ +struct vlc_queue_entry; + +static void entry_set(struct vlc_queue_entry **pp, struct vlc_queue_entry *e) +{ + memcpy(pp, &e, sizeof (e)); +} + +static struct vlc_queue_entry *entry_get(struct vlc_queue_entry *const *pp) +{ + struct vlc_queue_entry *e; + + memcpy(&e, pp, sizeof (e)); + return e; +} + +static struct vlc_queue_entry **next_p(const struct vlc_queue_entry *e, + ptrdiff_t offset) +{ + return (struct vlc_queue_entry **)(((unsigned char *)e) + offset); +} + +static void next_set(struct vlc_queue_entry *e, struct vlc_queue_entry *next, + ptrdiff_t offset) +{ + return entry_set(next_p(e, offset), next); +} + +static struct vlc_queue_entry *next_get(const struct vlc_queue_entry *e, + ptrdiff_t offset) +{ + return entry_get(next_p(e, offset)); +} + +void vlc_queue_Init(vlc_queue_t *q, ptrdiff_t next_offset) +{ + q->first = NULL; + q->lastp = &q->first; + q->next_offset = next_offset; + vlc_mutex_init(&q->lock); + vlc_cond_init(&q->wait); +} + +void vlc_queue_EnqueueUnlocked(vlc_queue_t *q, void *entry) +{ + struct vlc_queue_entry **lastp; + const ptrdiff_t offset = q->next_offset; + + vlc_mutex_assert(&q->lock); + assert(entry_get(q->lastp) == NULL); + entry_set(q->lastp, entry); + + for (lastp = q->lastp; entry != NULL; entry = next_get(entry, offset)) + lastp = next_p(entry, offset); + + q->lastp = lastp; + vlc_queue_Signal(q); +} + +void *vlc_queue_DequeueUnlocked(vlc_queue_t *q) +{ + vlc_mutex_assert(&q->lock); + + void *entry = q->first; + const ptrdiff_t offset = q->next_offset; + + if (entry != NULL) { + struct vlc_queue_entry *next = next_get(entry, offset); + + next_set(entry, NULL, offset); + q->first = next; + + if (next == NULL) + q->lastp = &q->first; + } + + return entry; +} + +void *vlc_queue_DequeueAllUnlocked(vlc_queue_t *q) +{ + vlc_mutex_assert(&q->lock); + + void *entry = q->first; + + q->first = NULL; + q->lastp = &q->first; + + return entry; +} + +void vlc_queue_Enqueue(vlc_queue_t *q, void *entry) +{ + vlc_queue_Lock(q); + vlc_queue_EnqueueUnlocked(q, entry); + vlc_queue_Unlock(q); +} + +void *vlc_queue_Dequeue(vlc_queue_t *q) +{ + void *entry; + + vlc_queue_Lock(q); + vlc_testcancel(); + + while (vlc_queue_IsEmpty(q)) + vlc_queue_Wait(q); + + entry = vlc_queue_DequeueUnlocked(q); + vlc_queue_Unlock(q); + + return entry; +} + +void *vlc_queue_DequeueAll(vlc_queue_t *q) +{ + void *entry; + + vlc_queue_Lock(q); + entry = vlc_queue_DequeueAllUnlocked(q); + vlc_queue_Unlock(q); + + return entry; +} _______________________________________________ vlc-commits mailing list [email protected] https://mailman.videolan.org/listinfo/vlc-commits
