[vlc-devel] [PATCH 3/4] queue: add generic queue/FIFO helpers
Rémi Denis-Courmont
remi at remlab.net
Sat Apr 11 20:41:05 CEST 2020
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.
---
include/vlc_queue.h | 218 ++++++++++++++++++++++++++++++++++++++++++++
src/Makefile.am | 2 +
src/libvlccore.sym | 7 ++
src/misc/queue.c | 157 +++++++++++++++++++++++++++++++
4 files changed, 384 insertions(+)
create mode 100644 include/vlc_queue.h
create mode 100644 src/misc/queue.c
diff --git a/include/vlc_queue.h b/include/vlc_queue.h
new file mode 100644
index 0000000000..eed69510dc
--- /dev/null
+++ b/include/vlc_queue.h
@@ -0,0 +1,218 @@
+/*****************************************************************************
+ * 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 <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;
+ vlc_mutex_t lock;
+ vlc_cond_t wait;
+} vlc_queue_t;
+
+/**
+ * Initializes a queue.
+ */
+VLC_API void vlc_queue_Init(vlc_queue_t *);
+
+/**
+ * @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)
+ * @param offset offset of the next pointer within a queue entry
+ */
+VLC_API void vlc_queue_EnqueueUnlocked(vlc_queue_t *, void *entry,
+ ptrdiff_t offset);
+
+/**
+ * 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.
+ *
+ * @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_DequeueUnlocked(vlc_queue_t *, ptrdiff_t offset)
+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)
+ * @param offset offset of the next pointer within a queue entry
+ */
+VLC_API void vlc_queue_Enqueue(vlc_queue_t *, void *entry, ptrdiff_t offset);
+
+/**
+ * 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 *, ptrdiff_t offset)
+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 895285ac01..42a2adec23 100644
--- a/src/libvlccore.sym
+++ b/src/libvlccore.sym
@@ -673,6 +673,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..665dfc7031
--- /dev/null
+++ b/src/misc/queue.c
@@ -0,0 +1,157 @@
+/*****************************************************************************
+ * 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)
+{
+ q->first = NULL;
+ q->lastp = &q->first;
+ vlc_mutex_init(&q->lock);
+ vlc_cond_init(&q->wait);
+}
+
+void vlc_queue_EnqueueUnlocked(vlc_queue_t *q, void *entry, ptrdiff_t offset)
+{
+ struct vlc_queue_entry **lastp;
+
+ 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, ptrdiff_t offset)
+{
+ vlc_mutex_assert(&q->lock);
+
+ void *entry = q->first;
+
+ 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, ptrdiff_t offset)
+{
+ vlc_queue_Lock(q);
+ vlc_queue_EnqueueUnlocked(q, entry, offset);
+ vlc_queue_Unlock(q);
+}
+
+void *vlc_queue_Dequeue(vlc_queue_t *q, ptrdiff_t offset)
+{
+ void *entry;
+
+ vlc_queue_Lock(q);
+ vlc_testcancel();
+
+ while (vlc_queue_IsEmpty(q))
+ vlc_queue_Wait(q);
+
+ entry = vlc_queue_DequeueUnlocked(q, offset);
+ 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;
+}
--
2.26.0
More information about the vlc-devel
mailing list