deps/libretro-common/lists/linked_list.c

   1 /* Copyright  (C) 2010-2020 The RetroArch team
   2  *
   3  * ---------------------------------------------------------------------------------------
   4  * The following license statement only applies to this file (linked_list.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 <lists/linked_list.h>
  28
  29 struct linked_list_item_t
  30 {
  31    void *value;
  32    struct linked_list_item_t *previous;
  33    struct linked_list_item_t *next;
  34 };
  35
  36 struct linked_list
  37 {
  38    struct linked_list_item_t *first_item;
  39    struct linked_list_item_t *last_item;
  40    size_t length;
  41 };
  42
  43 struct linked_list_iterator
  44 {
  45    linked_list_t *list;
  46    struct linked_list_item_t *item;
  47    bool forward;
  48 };
  49
  50 linked_list_t *linked_list_new(void)
  51 {
  52    linked_list_t *list;
  53
  54    list = (linked_list_t *)calloc(sizeof(linked_list_t), 1);
  55    return list;
  56 }
  57
  58 void linked_list_free(linked_list_t *list, void (*free_value)(void *value))
  59 {
  60    if (!list)
  61    {
  62       return;
  63    }
  64
  65    while (list->first_item)
  66    {
  67       struct linked_list_item_t *next;
  68
  69       next = list->first_item->next;
  70       if (free_value)
  71          free_value(list->first_item->value);
  72       free(list->first_item);
  73
  74       list->first_item = next;
  75    }
  76
  77    free (list);
  78 }
  79
  80 void linked_list_add(linked_list_t *list, void *value)
  81 {
  82    struct linked_list_item_t *new_item;
  83
  84    if (!list)
  85       return;
  86
  87    new_item = (struct linked_list_item_t *)malloc(sizeof(struct linked_list_item_t));
  88    new_item->value = value;
  89    new_item->previous = list->last_item;
  90    new_item->next = NULL;
  91
  92    if (list->length == 0)
  93       list->first_item = new_item;
  94    else
  95       list->last_item->next = new_item;
  96
  97    list->last_item = new_item;
  98    list->length++;
  99 }
 100
 101 void linked_list_insert(linked_list_t *list, size_t index, void *value)
 102 {
 103    size_t i;
 104    struct linked_list_item_t *previous_item;
 105    struct linked_list_item_t *next_item;
 106    struct linked_list_item_t *new_item;
 107
 108    if (!list || index > list->length)
 109       return;
 110
 111    previous_item = NULL;
 112    next_item = list->first_item;
 113    for (i = 1; i <= index; i++)
 114    {
 115       previous_item = next_item;
 116       next_item = next_item->next;
 117    }
 118
 119    new_item = (struct linked_list_item_t *)malloc(sizeof(struct linked_list_item_t));
 120    new_item->value = value;
 121
 122    if (previous_item)
 123       previous_item->next = new_item;
 124    else
 125       list->first_item = new_item;
 126    new_item->previous = previous_item;
 127
 128    if (next_item)
 129       next_item->previous = new_item;
 130    else
 131       list->last_item = new_item;
 132    new_item->next = next_item;
 133
 134    list->length++;
 135 }
 136
 137 void *linked_list_get(linked_list_t *list, size_t index)
 138 {
 139    size_t i;
 140    struct linked_list_item_t *item;
 141
 142    if (!list)
 143       return NULL;
 144
 145    if (index >= list->length)
 146       return NULL;
 147
 148    item = list->first_item;
 149    for (i = 1; i <= index; i++)
 150       item = item->next;
 151
 152    return item->value;
 153 }
 154
 155 void *linked_list_get_first_matching(linked_list_t *list, bool (*matches)(void *item, void *usrptr), void *usrptr)
 156 {
 157    struct linked_list_item_t *item;
 158
 159    if (!list || !matches)
 160       return NULL;
 161
 162    for (item = list->first_item; item; item = item->next)
 163    {
 164       if (matches(item->value, usrptr))
 165          return item->value;
 166    }
 167
 168    return NULL;
 169 }
 170
 171 void *linked_list_get_last_matching(linked_list_t *list, bool (*matches)(void *item, void *usrptr), void *usrptr)
 172 {
 173    struct linked_list_item_t *item;
 174
 175    if (!list || !matches)
 176       return NULL;
 177
 178    for (item = list->last_item; item; item = item->previous)
 179    {
 180       if (matches(item->value, usrptr))
 181          return item->value;
 182    }
 183
 184    return NULL;
 185 }
 186
 187 static void _linked_list_remove_item(linked_list_t *list, struct linked_list_item_t *item)
 188 {
 189    struct linked_list_item_t *previous_item;
 190    struct linked_list_item_t *next_item;
 191
 192    previous_item = item->previous;
 193    next_item = item->next;
 194    free(item);
 195    list->length--;
 196
 197    if (previous_item)
 198       previous_item->next = next_item;
 199    else
 200       list->first_item = next_item;
 201
 202    if (next_item)
 203       next_item->previous = previous_item;
 204    else
 205       list->last_item = previous_item;
 206 }
 207
 208 void *linked_list_remove_at(linked_list_t *list, size_t index)
 209 {
 210    size_t i = 0;
 211    struct linked_list_item_t *item;
 212    void *value;
 213
 214    if (!list || list->length == 0 || index >= list->length)
 215       return NULL;
 216
 217    item = list->first_item;
 218    for (i = 1; i <= index; i++)
 219       item = item->next;
 220
 221    value = item->value;
 222    _linked_list_remove_item(list, item);
 223    return value;
 224 }
 225
 226 void *linked_list_remove_first(linked_list_t *list, void *value)
 227 {
 228    struct linked_list_item_t *item;
 229
 230    if (!list)
 231       return NULL;
 232
 233    for (item = list->first_item; item; item = item->next)
 234    {
 235       if (item->value == value)
 236          break;
 237    }
 238
 239    if (item)
 240    {
 241       _linked_list_remove_item(list, item);
 242       return value;
 243    }
 244
 245    return NULL;
 246 }
 247
 248 void *linked_list_remove_last(linked_list_t *list, void *value)
 249 {
 250    struct linked_list_item_t *item;
 251
 252    if (!list)
 253       return NULL;
 254
 255    for (item = list->last_item; item; item = item->previous)
 256    {
 257       if (item->value == value)
 258          break;
 259    }
 260
 261    if (item)
 262    {
 263       _linked_list_remove_item(list, item);
 264       return value;
 265    }
 266
 267    return NULL;
 268 }
 269
 270 void *linked_list_remove_all(linked_list_t *list, void *value)
 271 {
 272    struct linked_list_item_t *item;
 273    bool found = false;
 274
 275    if (!list)
 276       return NULL;
 277
 278    for (item = list->first_item; item;)
 279    {
 280       if (item->value == value)
 281       {
 282          struct linked_list_item_t *next_item;
 283
 284          next_item = item->next;
 285          _linked_list_remove_item(list, item);
 286          found = true;
 287          item = next_item;
 288       } else
 289       {
 290          item = item->next;
 291       }
 292    }
 293
 294    return found ? value : NULL;
 295 }
 296
 297 void *linked_list_remove_first_matching(linked_list_t *list, bool (*matches)(void *value))
 298 {
 299    struct linked_list_item_t *item;
 300
 301    if (!list)
 302       return NULL;
 303
 304    for (item = list->first_item; item; item = item->next)
 305    {
 306       if (matches(item->value))
 307          break;
 308    }
 309
 310    if (item)
 311    {
 312       void *value;
 313
 314       value = item->value;
 315       _linked_list_remove_item(list, item);
 316       return value;
 317    }
 318
 319    return NULL;
 320 }
 321
 322 void *linked_list_remove_last_matching(linked_list_t *list, bool (*matches)(void *value))
 323 {
 324    struct linked_list_item_t *item;
 325
 326    if (!list)
 327       return NULL;
 328
 329    for (item = list->last_item; item; item = item->previous)
 330    {
 331       if (matches(item->value))
 332          break;
 333    }
 334
 335    if (item)
 336    {
 337       void *value;
 338
 339       value = item->value;
 340       _linked_list_remove_item(list, item);
 341       return value;
 342    }
 343
 344    return NULL;
 345 }
 346
 347 void linked_list_remove_all_matching(linked_list_t *list, bool (*matches)(void *value))
 348 {
 349    struct linked_list_item_t *item;
 350
 351    if (!list)
 352       return;
 353
 354    for (item = list->first_item; item;)
 355    {
 356       if (matches(item->value))
 357       {
 358          struct linked_list_item_t *next_item;
 359
 360          next_item = item->next;
 361          _linked_list_remove_item(list, item);
 362          item = next_item;
 363       } else
 364       {
 365          item = item->next;
 366       }
 367    }
 368 }
 369
 370 bool linked_list_set_at(linked_list_t *list, size_t index, void *value)
 371 {
 372    struct linked_list_item_t *item;
 373    size_t i;
 374
 375    if (!list || list->length == 0 || index >= list->length)
 376       return false;
 377
 378    item = list->first_item;
 379    for (i = 1; i <= index; i++)
 380       item = item->next;
 381
 382    if (item)
 383    {
 384       item->value = value;
 385       return true;
 386    }
 387
 388    return false;
 389 }
 390
 391 size_t linked_list_size(linked_list_t *list)
 392 {
 393    if (list)
 394       return list->length;
 395
 396    return 0;
 397 }
 398
 399 linked_list_iterator_t *linked_list_iterator(linked_list_t *list, bool forward)
 400 {
 401    linked_list_iterator_t *iterator;
 402
 403    if (!list || !list->first_item)
 404       return NULL;
 405
 406    iterator = (linked_list_iterator_t *)malloc(sizeof(linked_list_iterator_t));
 407    iterator->list = list;
 408    iterator->item = forward ? list->first_item : list->last_item;
 409    iterator->forward = forward;
 410
 411    return iterator;
 412 }
 413
 414 linked_list_iterator_t *linked_list_iterator_next(linked_list_iterator_t *iterator)
 415 {
 416    struct linked_list_item_t *item;
 417
 418    if (!iterator)
 419       return NULL;
 420
 421    item = iterator->forward ? iterator->item->next : iterator->item->previous;
 422    if (item)
 423    {
 424       iterator->item = item;
 425       return iterator;
 426    } else
 427    {
 428       free(iterator);
 429       return NULL;
 430    }
 431 }
 432
 433 void *linked_list_iterator_value(linked_list_iterator_t *iterator)
 434 {
 435    if (iterator)
 436       return iterator->item->value;
 437
 438    return NULL;
 439 }
 440
 441 linked_list_iterator_t *linked_list_iterator_remove(linked_list_iterator_t *iterator)
 442 {
 443    struct linked_list_item_t *next_item;
 444
 445    if (!iterator)
 446       return NULL;
 447
 448    next_item = iterator->forward ? iterator->item->next : iterator->item->previous;
 449    _linked_list_remove_item(iterator->list, iterator->item);
 450
 451    if (next_item)
 452    {
 453       iterator->item = next_item;
 454       return iterator;
 455    } else
 456    {
 457       free(iterator);
 458       return NULL;
 459    }
 460 }
 461
 462 void linked_list_iterator_free(linked_list_iterator_t *iterator)
 463 {
 464    if (iterator)
 465       free(iterator);
 466 }
 467
 468 void linked_list_foreach(linked_list_t *list, void (*fn)(size_t index, void *value))
 469 {
 470    size_t i;
 471    struct linked_list_item_t *item;
 472
 473    if (!list || !fn)
 474       return;
 475
 476    i = 0;
 477    for (item = list->first_item; item; item = item->next)
 478       fn(i++, item->value);
 479 }