src/misc/queue.c

   1 /*****************************************************************************
   2  * queue.c: generic queue (FIFO)
   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 #ifdef HAVE_CONFIG_H
  22 # include "config.h"
  23 #endif
  24
  25 #include <assert.h>
  26 #include <stdint.h>
  27 #include <stdlib.h>
  28
  29 #include <vlc_common.h>
  30 #include <vlc_queue.h>
  31
  32 /* Opaque struct type.
  33  *
  34  * ISO C uses the same representation for all pointer-to-struct types.
  35  * Still different pointer types are not compatible, i.e. cannot alias.
  36  * So use memcpy() to read/write pointer values.
  37  */
  38 struct vlc_queue_entry;
  39
  40 static void entry_set(struct vlc_queue_entry **pp, struct vlc_queue_entry *e)
  41 {
  42     memcpy(pp, &e, sizeof (e));
  43 }
  44
  45 static struct vlc_queue_entry *entry_get(struct vlc_queue_entry *const *pp)
  46 {
  47     struct vlc_queue_entry *e;
  48
  49     memcpy(&e, pp, sizeof (e));
  50     return e;
  51 }
  52
  53 static struct vlc_queue_entry **next_p(const struct vlc_queue_entry *e,
  54                                        ptrdiff_t offset)
  55 {
  56     return (struct vlc_queue_entry **)(((unsigned char *)e) + offset);
  57 }
  58
  59 static void next_set(struct vlc_queue_entry *e, struct vlc_queue_entry *next,
  60                      ptrdiff_t offset)
  61 {
  62     entry_set(next_p(e, offset), next);
  63 }
  64
  65 static struct vlc_queue_entry *next_get(const struct vlc_queue_entry *e,
  66                                         ptrdiff_t offset)
  67 {
  68     return entry_get(next_p(e, offset));
  69 }
  70
  71 void vlc_queue_Init(vlc_queue_t *q, ptrdiff_t next_offset)
  72 {
  73     q->first = NULL;
  74     q->lastp = &q->first;
  75     q->next_offset = next_offset;
  76     vlc_mutex_init(&q->lock);
  77     vlc_cond_init(&q->wait);
  78 }
  79
  80 void vlc_queue_EnqueueUnlocked(vlc_queue_t *q, void *entry)
  81 {
  82     struct vlc_queue_entry **lastp;
  83     const ptrdiff_t offset = q->next_offset;
  84
  85     vlc_mutex_assert(&q->lock);
  86     assert(entry_get(q->lastp) == NULL);
  87     entry_set(q->lastp, entry);
  88
  89     for (lastp = q->lastp; entry != NULL; entry = next_get(entry, offset))
  90         lastp = next_p(entry, offset);
  91
  92     q->lastp = lastp;
  93     vlc_queue_Signal(q);
  94 }
  95
  96 void *vlc_queue_DequeueUnlocked(vlc_queue_t *q)
  97 {
  98     vlc_mutex_assert(&q->lock);
  99
 100     void *entry = q->first;
 101     const ptrdiff_t offset = q->next_offset;
 102
 103     if (entry != NULL) {
 104         struct vlc_queue_entry *next = next_get(entry, offset);
 105
 106         next_set(entry, NULL, offset);
 107         q->first = next;
 108
 109         if (next == NULL)
 110             q->lastp = &q->first;
 111     }
 112
 113     return entry;
 114 }
 115
 116 void *vlc_queue_DequeueAllUnlocked(vlc_queue_t *q)
 117 {
 118     vlc_mutex_assert(&q->lock);
 119
 120     void *entry = q->first;
 121
 122     q->first = NULL;
 123     q->lastp = &q->first;
 124
 125     return entry;
 126 }
 127
 128 void vlc_queue_Enqueue(vlc_queue_t *q, void *entry)
 129 {
 130     vlc_queue_Lock(q);
 131     vlc_queue_EnqueueUnlocked(q, entry);
 132     vlc_queue_Unlock(q);
 133 }
 134
 135 void *vlc_queue_Dequeue(vlc_queue_t *q)
 136 {
 137     void *entry;
 138
 139     vlc_queue_Lock(q);
 140     vlc_testcancel();
 141
 142     while (vlc_queue_IsEmpty(q))
 143         vlc_queue_Wait(q);
 144
 145     entry = vlc_queue_DequeueUnlocked(q);
 146     vlc_queue_Unlock(q);
 147
 148     return entry;
 149 }
 150
 151 void *vlc_queue_DequeueAll(vlc_queue_t *q)
 152 {
 153     void *entry;
 154
 155     vlc_queue_Lock(q);
 156     entry = vlc_queue_DequeueAllUnlocked(q);
 157     vlc_queue_Unlock(q);
 158
 159     return entry;
 160 }