deps/libretro-common/queues/message_queue.c

   1 /* Copyright  (C) 2010-2020 The RetroArch team
   2  *
   3  * ---------------------------------------------------------------------------------------
   4  * The following license statement only applies to this file (message_queue.c).
   5  * ---------------------------------------------------------------------------------------
   6  *
   7  * Permission is hereby granted, free of charge,
   8  * to any person obtaining a copy of this software and associated documentation files (the "Software"),
   9  * to deal in the Software without restriction, including without limitation the rights to
  10  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software,
  11  * and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
  12  *
  13  * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
  16  * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  18  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  19  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  21  */
  22
  23 #include <stdlib.h>
  24 #include <string.h>
  25
  26 #include <boolean.h>
  27 #include <queues/message_queue.h>
  28 #include <compat/strl.h>
  29 #include <compat/posix_string.h>
  30
  31 static bool msg_queue_initialize_internal(msg_queue_t *queue, size_t size)
  32 {
  33    struct queue_elem **elems = (struct queue_elem**)calloc(size + 1,
  34          sizeof(struct queue_elem*));
  35
  36    if (!elems)
  37       return false;
  38
  39    queue->tmp_msg            = NULL;
  40    queue->elems              = elems;
  41    queue->ptr                = 1;
  42    queue->size               = size + 1;
  43
  44    return true;
  45 }
  46
  47 /**
  48  * msg_queue_new:
  49  * @size              : maximum size of message
  50  *
  51  * Creates a message queue with maximum size different messages.
  52  *
  53  * Returns: NULL if allocation error, pointer to a message queue
  54  * if successful. Has to be freed manually.
  55  **/
  56 msg_queue_t *msg_queue_new(size_t size)
  57 {
  58    msg_queue_t *queue        = (msg_queue_t*)malloc(sizeof(*queue));
  59
  60    if (!queue)
  61       return NULL;
  62
  63    if (!msg_queue_initialize_internal(queue, size))
  64    {
  65       free(queue);
  66       return NULL;
  67    }
  68
  69    return queue;
  70 }
  71
  72 bool msg_queue_initialize(msg_queue_t *queue, size_t size)
  73 {
  74    if (!queue)
  75       return false;
  76    return msg_queue_initialize_internal(queue, size);
  77 }
  78
  79 /**
  80  * msg_queue_free:
  81  * @queue             : pointer to queue object
  82  *
  83  * Frees message queue..
  84  **/
  85 void msg_queue_free(msg_queue_t *queue)
  86 {
  87    if (!queue)
  88       return;
  89    msg_queue_clear(queue);
  90    free(queue->elems);
  91    free(queue);
  92 }
  93
  94 bool msg_queue_deinitialize(msg_queue_t *queue)
  95 {
  96    if (!queue)
  97       return false;
  98    msg_queue_clear(queue);
  99    free(queue->elems);
 100    queue->elems   = NULL;
 101    queue->tmp_msg = NULL;
 102    queue->ptr     = 0;
 103    queue->size    = 0;
 104    return true;
 105 }
 106
 107 /**
 108  * msg_queue_push:
 109  * @queue             : pointer to queue object
 110  * @msg               : message to add to the queue
 111  * @prio              : priority level of the message
 112  * @duration          : how many times the message can be pulled
 113  *                      before it vanishes (E.g. show a message for
 114  *                      3 seconds @ 60fps = 180 duration).
 115  *
 116  * Push a new message onto the queue.
 117  **/
 118 void msg_queue_push(msg_queue_t *queue, const char *msg,
 119       unsigned prio, unsigned duration,
 120       char *title,
 121       enum message_queue_icon icon, enum message_queue_category category)
 122 {
 123    size_t tmp_ptr = 0;
 124    struct queue_elem *new_elem = NULL;
 125
 126    if (!queue || queue->ptr >= queue->size)
 127       return;
 128
 129    new_elem                      = (struct queue_elem*)malloc(
 130       sizeof(struct queue_elem));
 131    if (!new_elem)
 132       return;
 133
 134    new_elem->duration            = duration;
 135    new_elem->prio                = prio;
 136    new_elem->msg                 = msg   ? strdup(msg)   : NULL;
 137    new_elem->title               = title ? strdup(title) : NULL;
 138    new_elem->icon                = icon;
 139    new_elem->category            = category;
 140
 141    queue->elems[queue->ptr]      = new_elem;
 142
 143    tmp_ptr                       = queue->ptr++;
 144
 145    while (tmp_ptr > 1)
 146    {
 147       struct queue_elem *parent  = queue->elems[tmp_ptr >> 1];
 148       struct queue_elem *child   = queue->elems[tmp_ptr];
 149
 150       if (child->prio <= parent->prio)
 151          break;
 152
 153       queue->elems[tmp_ptr >> 1] = child;
 154       queue->elems[tmp_ptr]      = parent;
 155
 156       tmp_ptr >>= 1;
 157    }
 158 }
 159
 160 /**
 161  * msg_queue_clear:
 162  * @queue             : pointer to queue object
 163  *
 164  * Clears out everything in the queue.
 165  **/
 166 void msg_queue_clear(msg_queue_t *queue)
 167 {
 168    size_t i;
 169
 170    if (!queue)
 171       return;
 172
 173    for (i = 1; i < queue->ptr; i++)
 174    {
 175       if (queue->elems[i])
 176       {
 177          free(queue->elems[i]->msg);
 178          free(queue->elems[i]->title);
 179          free(queue->elems[i]);
 180          queue->elems[i] = NULL;
 181       }
 182    }
 183    queue->ptr = 1;
 184    free(queue->tmp_msg);
 185    queue->tmp_msg = NULL;
 186 }
 187
 188 /**
 189  * msg_queue_pull:
 190  * @queue             : pointer to queue object
 191  *
 192  * Pulls highest priority message in queue.
 193  *
 194  * Returns: NULL if no message in queue, otherwise a string
 195  * containing the message.
 196  **/
 197 const char *msg_queue_pull(msg_queue_t *queue)
 198 {
 199    struct queue_elem *front  = NULL, *last = NULL;
 200    size_t tmp_ptr = 1;
 201
 202    (void)tmp_ptr;
 203
 204    /* Nothing in queue. */
 205    if (!queue || queue->ptr == 1)
 206       return NULL;
 207
 208    front = (struct queue_elem*)queue->elems[1];
 209    front->duration--;
 210    if (front->duration > 0)
 211       return front->msg;
 212
 213    free(queue->tmp_msg);
 214    queue->tmp_msg = front->msg;
 215    front->msg = NULL;
 216
 217    last  = (struct queue_elem*)queue->elems[--queue->ptr];
 218    queue->elems[1] = last;
 219    free(front->title);
 220    free(front);
 221
 222    for (;;)
 223    {
 224       struct queue_elem *parent = NULL;
 225       struct queue_elem *child  = NULL;
 226       size_t switch_index       = tmp_ptr;
 227       bool left                 = (tmp_ptr * 2 <= queue->ptr)
 228          && (queue->elems[tmp_ptr] < queue->elems[tmp_ptr * 2]);
 229       bool right                = (tmp_ptr * 2 + 1 <= queue->ptr)
 230          && (queue->elems[tmp_ptr] < queue->elems[tmp_ptr * 2 + 1]);
 231
 232       if (!left && !right)
 233          break;
 234
 235       if (left && !right)
 236          switch_index <<= 1;
 237       else if (right && !left)
 238          switch_index += switch_index + 1;
 239       else
 240       {
 241          if (queue->elems[tmp_ptr * 2]
 242                >= queue->elems[tmp_ptr * 2 + 1])
 243             switch_index <<= 1;
 244          else
 245             switch_index += switch_index + 1;
 246       }
 247
 248       parent = (struct queue_elem*)queue->elems[tmp_ptr];
 249       child  = (struct queue_elem*)queue->elems[switch_index];
 250       queue->elems[tmp_ptr]      = child;
 251       queue->elems[switch_index] = parent;
 252       tmp_ptr                    = switch_index;
 253    }
 254
 255    return queue->tmp_msg;
 256 }
 257
 258 /**
 259  * msg_queue_extract:
 260  * @queue             : pointer to queue object
 261  * @queue_entry       : pointer to external queue entry struct
 262  *
 263  * Removes highest priority message from queue, copying
 264  * contents into queue_entry struct.
 265  *
 266  * Returns: false if no messages in queue, otherwise true
 267  **/
 268 bool msg_queue_extract(msg_queue_t *queue, msg_queue_entry_t *queue_entry)
 269 {
 270    struct queue_elem *front  = NULL, *last = NULL;
 271    size_t tmp_ptr = 1;
 272
 273    /* Ensure arguments are valid and queue is not
 274     * empty */
 275    if (!queue || queue->ptr == 1 || !queue_entry)
 276       return false;
 277
 278    front = (struct queue_elem*)queue->elems[1];
 279    last  = (struct queue_elem*)queue->elems[--queue->ptr];
 280    queue->elems[1] = last;
 281
 282    /* Copy element parameters */
 283    queue_entry->duration = front->duration;
 284    queue_entry->prio     = front->prio;
 285    queue_entry->icon     = front->icon;
 286    queue_entry->category = front->category;
 287    queue_entry->msg[0]   = '\0';
 288    queue_entry->title[0] = '\0';
 289
 290    if (front->msg)
 291       strlcpy(queue_entry->msg, front->msg, sizeof(queue_entry->msg));
 292
 293    if (front->title)
 294       strlcpy(queue_entry->title, front->title, sizeof(queue_entry->title));
 295
 296    /* Delete element */
 297    free(front->msg);
 298    free(front->title);
 299    free(front);
 300
 301    for (;;)
 302    {
 303       struct queue_elem *parent = NULL;
 304       struct queue_elem *child  = NULL;
 305       size_t switch_index       = tmp_ptr;
 306       bool left                 = (tmp_ptr * 2 <= queue->ptr)
 307          && (queue->elems[tmp_ptr] < queue->elems[tmp_ptr * 2]);
 308       bool right                = (tmp_ptr * 2 + 1 <= queue->ptr)
 309          && (queue->elems[tmp_ptr] < queue->elems[tmp_ptr * 2 + 1]);
 310
 311       if (!left && !right)
 312          break;
 313
 314       if (left && !right)
 315          switch_index <<= 1;
 316       else if (right && !left)
 317          switch_index += switch_index + 1;
 318       else
 319       {
 320          if (queue->elems[tmp_ptr * 2]
 321                >= queue->elems[tmp_ptr * 2 + 1])
 322             switch_index <<= 1;
 323          else
 324             switch_index += switch_index + 1;
 325       }
 326
 327       parent = (struct queue_elem*)queue->elems[tmp_ptr];
 328       child  = (struct queue_elem*)queue->elems[switch_index];
 329       queue->elems[tmp_ptr]      = child;
 330       queue->elems[switch_index] = parent;
 331       tmp_ptr                    = switch_index;
 332    }
 333
 334    return true;
 335 }
 336
 337 /**
 338  * msg_queue_size:
 339  * @queue             : pointer to queue object
 340  *
 341  * Fetches number of messages in queue.
 342  *
 343  * Returns: Number of messages in queue.
 344  **/
 345 size_t msg_queue_size(msg_queue_t *queue)
 346 {
 347    if (!queue || queue->ptr <= 1)
 348       return 0;
 349
 350    return queue->ptr - 1;
 351 }