deps/libretro-common/queues/generic_queue.c

   1 /* Copyright  (C) 2010-2020 The RetroArch team
   2  *
   3  * ---------------------------------------------------------------------------------------
   4  * The following license statement only applies to this file (generic_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 <boolean.h>
  24 #include <stddef.h>
  25 #include <stdlib.h>
  26
  27 #include <queues/generic_queue.h>
  28
  29 struct generic_queue_item_t
  30 {
  31    void *value;
  32    struct generic_queue_item_t *previous;
  33    struct generic_queue_item_t *next;
  34 };
  35
  36 struct generic_queue
  37 {
  38    struct generic_queue_item_t *first_item;
  39    struct generic_queue_item_t *last_item;
  40    size_t length;
  41 };
  42
  43 struct generic_queue_iterator
  44 {
  45    generic_queue_t *queue;
  46    struct generic_queue_item_t *item;
  47    bool forward;
  48 };
  49
  50 generic_queue_t *generic_queue_new(void)
  51 {
  52    return (generic_queue_t *)calloc(1, sizeof(generic_queue_t));
  53 }
  54
  55 void generic_queue_free(generic_queue_t *queue, void (*free_value)(void *value))
  56 {
  57    struct generic_queue_item_t *next_item;
  58
  59    if (!queue)
  60       return;
  61
  62    while (queue->first_item)
  63    {
  64       if (free_value)
  65          free_value(queue->first_item->value);
  66
  67       next_item = queue->first_item->next;
  68       free(queue->first_item);
  69       queue->first_item = next_item;
  70    }
  71
  72    free(queue);
  73 }
  74
  75 void generic_queue_push(generic_queue_t *queue, void *value)
  76 {
  77    struct generic_queue_item_t *new_item;
  78
  79    new_item = (struct generic_queue_item_t *)calloc(1, sizeof(struct generic_queue_item_t));
  80    new_item->value = value;
  81    new_item->previous = queue->last_item;
  82    new_item->next = NULL;
  83
  84    queue->last_item = new_item;
  85    queue->length++;
  86
  87    if (!queue->first_item)
  88       queue->first_item = new_item;
  89    else
  90       new_item->previous->next = new_item;
  91 }
  92
  93 void *generic_queue_pop(generic_queue_t *queue)
  94 {
  95    void *value;
  96    struct generic_queue_item_t *item;
  97
  98    if (!queue || !queue->last_item)
  99       return NULL;
 100
 101    item = queue->last_item;
 102    queue->last_item = queue->last_item->previous;
 103    queue->length--;
 104
 105    if (queue->length == 0)
 106       queue->first_item = NULL;
 107
 108    value = item->value;
 109    free(item);
 110
 111    return value;
 112 }
 113
 114 void *generic_queue_peek(generic_queue_t *queue)
 115 {
 116    if (!queue || !queue->last_item)
 117       return NULL;
 118
 119    return queue->last_item->value;
 120 }
 121
 122 void *generic_queue_peek_first(generic_queue_t *queue)
 123 {
 124    if (!queue || !queue->first_item)
 125       return NULL;
 126
 127    return queue->first_item->value;
 128 }
 129
 130 void generic_queue_shift(generic_queue_t *queue, void *value)
 131 {
 132    struct generic_queue_item_t *new_item;
 133
 134    if (!queue)
 135       return;
 136
 137    new_item = (struct generic_queue_item_t *)calloc(1, sizeof(struct generic_queue_item_t));
 138    new_item->value = value;
 139    new_item->previous = NULL;
 140    new_item->next = queue->first_item;
 141
 142    queue->first_item = new_item;
 143    queue->length++;
 144
 145    if (!queue->last_item)
 146       queue->last_item = new_item;
 147    else
 148       new_item->next->previous = new_item;
 149 }
 150
 151 void *generic_queue_unshift(generic_queue_t *queue)
 152 {
 153    void *value;
 154    struct generic_queue_item_t *item;
 155
 156    if (!queue || !queue->first_item)
 157       return NULL;
 158
 159    item = queue->first_item;
 160    queue->first_item = queue->first_item->next;
 161    queue->length--;
 162
 163    if (queue->length == 0)
 164       queue->last_item = NULL;
 165
 166    value = item->value;
 167    free(item);
 168
 169    return value;
 170 }
 171
 172 size_t generic_queue_length(generic_queue_t *queue)
 173 {
 174    if (queue)
 175       return queue->length;
 176
 177    return 0;
 178 }
 179
 180 void *generic_queue_remove(generic_queue_t *queue, void *value)
 181 {
 182    struct generic_queue_item_t *item;
 183
 184    if (!queue)
 185       return NULL;
 186
 187    for (item = queue->first_item; item; item = item->next)
 188    {
 189       if (item->value == value)
 190       {
 191          if (item->previous)
 192             item->previous->next = item->next;
 193          else
 194             queue->first_item = item->next;
 195
 196          if (item->next)
 197             item->next->previous = item->previous;
 198          else
 199             queue->last_item = item->previous;
 200
 201          free(item);
 202          queue->length--;
 203
 204          return value;
 205       }
 206    }
 207
 208    return NULL;
 209 }
 210
 211 generic_queue_iterator_t *generic_queue_iterator(generic_queue_t *queue, bool forward)
 212 {
 213    if (queue && queue->first_item)
 214    {
 215       generic_queue_iterator_t *iterator;
 216
 217       iterator = (generic_queue_iterator_t *)malloc(sizeof(generic_queue_iterator_t));
 218       iterator->queue = queue;
 219       iterator->item = forward ? queue->first_item : queue->last_item;
 220       iterator->forward = forward;
 221
 222       return iterator;
 223    }
 224
 225    return NULL;
 226 }
 227
 228 generic_queue_iterator_t *generic_queue_iterator_next(generic_queue_iterator_t *iterator)
 229 {
 230    if (iterator)
 231    {
 232       struct generic_queue_item_t *item;
 233
 234       item = iterator->forward ? iterator->item->next : iterator->item->previous;
 235       if (item)
 236       {
 237          iterator->item = item;
 238          return iterator;
 239       } else
 240       {
 241          free(iterator);
 242          return NULL;
 243       }
 244    }
 245
 246    return NULL;
 247 }
 248
 249 void *generic_queue_iterator_value(generic_queue_iterator_t *iterator)
 250 {
 251    if (iterator)
 252       return iterator->item->value;
 253
 254    return NULL;
 255 }
 256
 257 generic_queue_iterator_t *generic_queue_iterator_remove(generic_queue_iterator_t *iterator)
 258 {
 259    struct generic_queue_item_t *item;
 260
 261    if (!iterator)
 262       return NULL;
 263
 264    item = iterator->forward ? iterator->queue->first_item : iterator->queue->last_item;
 265    while (item)
 266    {
 267       if (iterator->item == item)
 268       {
 269          if (iterator->queue->first_item == item)
 270             iterator->queue->first_item = item->next;
 271          else
 272             item->previous->next = item->next;
 273
 274          if (iterator->queue->last_item == item)
 275             iterator->queue->last_item = item->previous;
 276          else
 277             item->next->previous = item->previous;
 278
 279          iterator->queue->length--;
 280
 281          iterator->item = iterator->forward ? item->next : item->previous;
 282          free(item);
 283          if (iterator->item)
 284          {
 285             return iterator;
 286          } else
 287          {
 288             free(iterator);
 289             return NULL;
 290          }
 291       }
 292
 293       item = iterator->forward ? item->next : item->previous;
 294    }
 295
 296    return iterator;
 297 }
 298
 299 void generic_queue_iterator_free(generic_queue_iterator_t *iterator)
 300 {
 301    if (iterator)
 302       free(iterator);
 303 }