src/SDL_dataqueue.c

   1 /*
   2   Simple DirectMedia Layer
   3   Copyright (C) 1997-2020 Sam Lantinga <slouken@libsdl.org>
   4
   5   This software is provided 'as-is', without any express or implied
   6   warranty.  In no event will the authors be held liable for any damages
   7   arising from the use of this software.
   8
   9   Permission is granted to anyone to use this software for any purpose,
  10   including commercial applications, and to alter it and redistribute it
  11   freely, subject to the following restrictions:
  12
  13   1. The origin of this software must not be misrepresented; you must not
  14      claim that you wrote the original software. If you use this software
  15      in a product, an acknowledgment in the product documentation would be
  16      appreciated but is not required.
  17   2. Altered source versions must be plainly marked as such, and must not be
  18      misrepresented as being the original software.
  19   3. This notice may not be removed or altered from any source distribution.
  20 */
  21 #include "./SDL_internal.h"
  22
  23 #include "SDL.h"
  24 #include "./SDL_dataqueue.h"
  25
  26 typedef struct SDL_DataQueuePacket
  27 {
  28     size_t datalen;  /* bytes currently in use in this packet. */
  29     size_t startpos;  /* bytes currently consumed in this packet. */
  30     struct SDL_DataQueuePacket *next;  /* next item in linked list. */
  31     Uint8 data[SDL_VARIABLE_LENGTH_ARRAY];  /* packet data */
  32 } SDL_DataQueuePacket;
  33
  34 struct SDL_DataQueue
  35 {
  36     SDL_DataQueuePacket *head; /* device fed from here. */
  37     SDL_DataQueuePacket *tail; /* queue fills to here. */
  38     SDL_DataQueuePacket *pool; /* these are unused packets. */
  39     size_t packet_size;   /* size of new packets */
  40     size_t queued_bytes;  /* number of bytes of data in the queue. */
  41 };
  42
  43 static void
  44 SDL_FreeDataQueueList(SDL_DataQueuePacket *packet)
  45 {
  46     while (packet) {
  47         SDL_DataQueuePacket *next = packet->next;
  48         SDL_free(packet);
  49         packet = next;
  50     }
  51 }
  52
  53
  54 /* this all expects that you managed thread safety elsewhere. */
  55
  56 SDL_DataQueue *
  57 SDL_NewDataQueue(const size_t _packetlen, const size_t initialslack)
  58 {
  59     SDL_DataQueue *queue = (SDL_DataQueue *) SDL_malloc(sizeof (SDL_DataQueue));
  60
  61     if (!queue) {
  62         SDL_OutOfMemory();
  63         return NULL;
  64     } else {
  65         const size_t packetlen = _packetlen ? _packetlen : 1024;
  66         const size_t wantpackets = (initialslack + (packetlen - 1)) / packetlen;
  67         size_t i;
  68
  69         SDL_zerop(queue);
  70         queue->packet_size = packetlen;
  71
  72         for (i = 0; i < wantpackets; i++) {
  73             SDL_DataQueuePacket *packet = (SDL_DataQueuePacket *) SDL_malloc(sizeof (SDL_DataQueuePacket) + packetlen);
  74             if (packet) { /* don't care if this fails, we'll deal later. */
  75                 packet->datalen = 0;
  76                 packet->startpos = 0;
  77                 packet->next = queue->pool;
  78                 queue->pool = packet;
  79             }
  80         }
  81     }
  82
  83     return queue;
  84 }
  85
  86 void
  87 SDL_FreeDataQueue(SDL_DataQueue *queue)
  88 {
  89     if (queue) {
  90         SDL_FreeDataQueueList(queue->head);
  91         SDL_FreeDataQueueList(queue->pool);
  92         SDL_free(queue);
  93     }
  94 }
  95
  96 void
  97 SDL_ClearDataQueue(SDL_DataQueue *queue, const size_t slack)
  98 {
  99     const size_t packet_size = queue ? queue->packet_size : 1;
 100     const size_t slackpackets = (slack + (packet_size-1)) / packet_size;
 101     SDL_DataQueuePacket *packet;
 102     SDL_DataQueuePacket *prev = NULL;
 103     size_t i;
 104
 105     if (!queue) {
 106         return;
 107     }
 108
 109     packet = queue->head;
 110
 111     /* merge the available pool and the current queue into one list. */
 112     if (packet) {
 113         queue->tail->next = queue->pool;
 114     } else {
 115         packet = queue->pool;
 116     }
 117
 118     /* Remove the queued packets from the device. */
 119     queue->tail = NULL;
 120     queue->head = NULL;
 121     queue->queued_bytes = 0;
 122     queue->pool = packet;
 123
 124     /* Optionally keep some slack in the pool to reduce malloc pressure. */
 125     for (i = 0; packet && (i < slackpackets); i++) {
 126         prev = packet;
 127         packet = packet->next;
 128     }
 129
 130     if (prev) {
 131         prev->next = NULL;
 132     } else {
 133         queue->pool = NULL;
 134     }
 135
 136     SDL_FreeDataQueueList(packet);  /* free extra packets */
 137 }
 138
 139 static SDL_DataQueuePacket *
 140 AllocateDataQueuePacket(SDL_DataQueue *queue)
 141 {
 142     SDL_DataQueuePacket *packet;
 143
 144     SDL_assert(queue != NULL);
 145
 146     packet = queue->pool;
 147     if (packet != NULL) {
 148         /* we have one available in the pool. */
 149         queue->pool = packet->next;
 150     } else {
 151         /* Have to allocate a new one! */
 152         packet = (SDL_DataQueuePacket *) SDL_malloc(sizeof (SDL_DataQueuePacket) + queue->packet_size);
 153         if (packet == NULL) {
 154             return NULL;
 155         }
 156     }
 157
 158     packet->datalen = 0;
 159     packet->startpos = 0;
 160     packet->next = NULL;
 161
 162     SDL_assert((queue->head != NULL) == (queue->queued_bytes != 0));
 163     if (queue->tail == NULL) {
 164         queue->head = packet;
 165     } else {
 166         queue->tail->next = packet;
 167     }
 168     queue->tail = packet;
 169     return packet;
 170 }
 171
 172
 173 int
 174 SDL_WriteToDataQueue(SDL_DataQueue *queue, const void *_data, const size_t _len)
 175 {
 176     size_t len = _len;
 177     const Uint8 *data = (const Uint8 *) _data;
 178     const size_t packet_size = queue ? queue->packet_size : 0;
 179     SDL_DataQueuePacket *orighead;
 180     SDL_DataQueuePacket *origtail;
 181     size_t origlen;
 182     size_t datalen;
 183
 184     if (!queue) {
 185         return SDL_InvalidParamError("queue");
 186     }
 187
 188     orighead = queue->head;
 189     origtail = queue->tail;
 190     origlen = origtail ? origtail->datalen : 0;
 191
 192     while (len > 0) {
 193         SDL_DataQueuePacket *packet = queue->tail;
 194         SDL_assert(!packet || (packet->datalen <= packet_size));
 195         if (!packet || (packet->datalen >= packet_size)) {
 196             /* tail packet missing or completely full; we need a new packet. */
 197             packet = AllocateDataQueuePacket(queue);
 198             if (!packet) {
 199                 /* uhoh, reset so we've queued nothing new, free what we can. */
 200                 if (!origtail) {
 201                     packet = queue->head;  /* whole queue. */
 202                 } else {
 203                     packet = origtail->next;  /* what we added to existing queue. */
 204                     origtail->next = NULL;
 205                     origtail->datalen = origlen;
 206                 }
 207                 queue->head = orighead;
 208                 queue->tail = origtail;
 209                 queue->pool = NULL;
 210
 211                 SDL_FreeDataQueueList(packet);  /* give back what we can. */
 212                 return SDL_OutOfMemory();
 213             }
 214         }
 215
 216         datalen = SDL_min(len, packet_size - packet->datalen);
 217         SDL_memcpy(packet->data + packet->datalen, data, datalen);
 218         data += datalen;
 219         len -= datalen;
 220         packet->datalen += datalen;
 221         queue->queued_bytes += datalen;
 222     }
 223
 224     return 0;
 225 }
 226
 227 size_t
 228 SDL_PeekIntoDataQueue(SDL_DataQueue *queue, void *_buf, const size_t _len)
 229 {
 230     size_t len = _len;
 231     Uint8 *buf = (Uint8 *) _buf;
 232     Uint8 *ptr = buf;
 233     SDL_DataQueuePacket *packet;
 234
 235     if (!queue) {
 236         return 0;
 237     }
 238
 239     for (packet = queue->head; len && packet; packet = packet->next) {
 240         const size_t avail = packet->datalen - packet->startpos;
 241         const size_t cpy = SDL_min(len, avail);
 242         SDL_assert(queue->queued_bytes >= avail);
 243
 244         SDL_memcpy(ptr, packet->data + packet->startpos, cpy);
 245         ptr += cpy;
 246         len -= cpy;
 247     }
 248
 249     return (size_t) (ptr - buf);
 250 }
 251
 252 size_t
 253 SDL_ReadFromDataQueue(SDL_DataQueue *queue, void *_buf, const size_t _len)
 254 {
 255     size_t len = _len;
 256     Uint8 *buf = (Uint8 *) _buf;
 257     Uint8 *ptr = buf;
 258     SDL_DataQueuePacket *packet;
 259
 260     if (!queue) {
 261         return 0;
 262     }
 263
 264     while ((len > 0) && ((packet = queue->head) != NULL)) {
 265         const size_t avail = packet->datalen - packet->startpos;
 266         const size_t cpy = SDL_min(len, avail);
 267         SDL_assert(queue->queued_bytes >= avail);
 268
 269         SDL_memcpy(ptr, packet->data + packet->startpos, cpy);
 270         packet->startpos += cpy;
 271         ptr += cpy;
 272         queue->queued_bytes -= cpy;
 273         len -= cpy;
 274
 275         if (packet->startpos == packet->datalen) {  /* packet is done, put it in the pool. */
 276             queue->head = packet->next;
 277             SDL_assert((packet->next != NULL) || (packet == queue->tail));
 278             packet->next = queue->pool;
 279             queue->pool = packet;
 280         }
 281     }
 282
 283     SDL_assert((queue->head != NULL) == (queue->queued_bytes != 0));
 284
 285     if (queue->head == NULL) {
 286         queue->tail = NULL;  /* in case we drained the queue entirely. */
 287     }
 288
 289     return (size_t) (ptr - buf);
 290 }
 291
 292 size_t
 293 SDL_CountDataQueue(SDL_DataQueue *queue)
 294 {
 295     return queue ? queue->queued_bytes : 0;
 296 }
 297
 298 void *
 299 SDL_ReserveSpaceInDataQueue(SDL_DataQueue *queue, const size_t len)
 300 {
 301     SDL_DataQueuePacket *packet;
 302
 303     if (!queue) {
 304         SDL_InvalidParamError("queue");
 305         return NULL;
 306     } else if (len == 0) {
 307         SDL_InvalidParamError("len");
 308         return NULL;
 309     } else if (len > queue->packet_size) {
 310         SDL_SetError("len is larger than packet size");
 311         return NULL;
 312     }
 313
 314     packet = queue->head;
 315     if (packet) {
 316         const size_t avail = queue->packet_size - packet->datalen;
 317         if (len <= avail) {  /* we can use the space at end of this packet. */
 318             void *retval = packet->data + packet->datalen;
 319             packet->datalen += len;
 320             queue->queued_bytes += len;
 321             return retval;
 322         }
 323     }
 324
 325     /* Need a fresh packet. */
 326     packet = AllocateDataQueuePacket(queue);
 327     if (!packet) {
 328         SDL_OutOfMemory();
 329         return NULL;
 330     }
 331
 332     packet->datalen = len;
 333     queue->queued_bytes += len;
 334     return packet->data;
 335 }
 336
 337 /* vi: set ts=4 sw=4 expandtab: */
 338