deps/libretro-common/lists/nested_list.c

   1 /* Copyright  (C) 2010-2020 The RetroArch team
   2  *
   3  * ---------------------------------------------------------------------------------------
   4  * The following license statement only applies to this file (nested_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 <string/stdstring.h>
  24 #include <lists/string_list.h>
  25 #include <array/rbuf.h>
  26 #include <array/rhmap.h>
  27
  28 #include <lists/nested_list.h>
  29
  30 struct nested_list_item
  31 {
  32    nested_list_item_t *parent_item;
  33    nested_list_t *parent_list;
  34    nested_list_t *children;
  35    char *id;
  36    const void *value;
  37 };
  38
  39 struct nested_list
  40 {
  41    nested_list_item_t **items;
  42    nested_list_item_t **item_map;
  43 };
  44
  45 /**************************************/
  46 /* Initialisation / De-Initialisation */
  47 /**************************************/
  48
  49 /* Forward declaration - required since
  50  * nested_list_free_list() is recursive */
  51 static void nested_list_free_list(nested_list_t *list);
  52
  53 /* Frees contents of a nested list item */
  54 static void nested_list_free_item(nested_list_item_t *item)
  55 {
  56    if (!item)
  57       return;
  58
  59    item->parent_item = NULL;
  60    item->parent_list = NULL;
  61
  62    if (item->children)
  63    {
  64       nested_list_free_list(item->children);
  65       item->children = NULL;
  66    }
  67
  68    if (item->id)
  69    {
  70       free(item->id);
  71       item->id = NULL;
  72    }
  73
  74    item->value = NULL;
  75    free(item);
  76 }
  77
  78 /* Frees contents of a nested list */
  79 static void nested_list_free_list(nested_list_t *list)
  80 {
  81    size_t i;
  82
  83    if (!list)
  84       return;
  85
  86    for (i = 0; i < RBUF_LEN(list->items); i++)
  87       nested_list_free_item(list->items[i]);
  88
  89    RBUF_FREE(list->items);
  90    RHMAP_FREE(list->item_map);
  91    free(list);
  92 }
  93
  94 /**
  95  * nested_list_init:
  96  *
  97  * Creates a new empty nested list. Returned pointer
  98  * must be freed using nested_list_free.
  99  *
 100  * Returns: Valid nested_list_t pointer if successful,
 101  * otherwise NULL.
 102  */
 103 nested_list_t *nested_list_init(void)
 104 {
 105    /* Create nested list */
 106    nested_list_t *list = (nested_list_t*)malloc(sizeof(*list));
 107
 108    if (!list)
 109       return NULL;
 110
 111    /* Initialise members */
 112    list->items    = NULL;
 113    list->item_map = NULL;
 114
 115    return list;
 116 }
 117
 118 /**
 119  * nested_list_free:
 120  * @list : pointer to nested_list_t object
 121  *
 122  * Frees specified nested list.
 123  */
 124 void nested_list_free(nested_list_t *list)
 125 {
 126    nested_list_free_list(list);
 127 }
 128
 129 /***********/
 130 /* Setters */
 131 /***********/
 132
 133 /* Creates and adds a new item to the specified
 134  * nested list. Returns NULL if item matching 'id'
 135  * already exists */
 136 static nested_list_item_t *nested_list_add_item_to_list(nested_list_t *list,
 137       nested_list_item_t *parent_item, const char *id, const void *value)
 138 {
 139    size_t num_items             = 0;
 140    nested_list_item_t *new_item = NULL;
 141    nested_list_t *child_list    = NULL;
 142
 143    if (!list || string_is_empty(id))
 144       goto end;
 145
 146    num_items = RBUF_LEN(list->items);
 147
 148    /* Ensure that item does not already exist */
 149    if (RHMAP_HAS_STR(list->item_map, id))
 150       goto end;
 151
 152    /* Attempt to allocate a buffer slot for the
 153     * new item */
 154    if (!RBUF_TRYFIT(list->items, num_items + 1))
 155       goto end;
 156
 157    /* Create new empty child list */
 158    child_list = nested_list_init();
 159    if (!child_list)
 160       goto end;
 161
 162    /* Create new list item */
 163    new_item = (nested_list_item_t*)malloc(sizeof(*new_item));
 164    if (!new_item)
 165    {
 166       nested_list_free(child_list);
 167       goto end;
 168    }
 169
 170    /* Assign members */
 171    new_item->parent_item = parent_item;
 172    new_item->parent_list = list;
 173    new_item->children    = child_list;
 174    new_item->id          = strdup(id);
 175    new_item->value       = value;
 176
 177    /* Increment item buffer size */
 178    RBUF_RESIZE(list->items, num_items + 1);
 179
 180    /* Add new item to buffer */
 181    list->items[num_items] = new_item;
 182
 183    /* Update map */
 184    RHMAP_SET_STR(list->item_map, id, new_item);
 185 end:
 186    return new_item;
 187 }
 188
 189 /**
 190  * nested_list_add_item:
 191  *
 192  * @list    : pointer to nested_list_t object
 193  * @address : a delimited list of item identifiers,
 194  *            corresponding to item 'levels'
 195  * @delim   : delimiter to use when splitting @address
 196  *            into individual ids
 197  * @value   : optional value (user data) associated with
 198  *            new list item. This is added to the last
 199  *            item specified by @address
 200  *
 201  * Appends a new item to the specified nested list.
 202  * If @delim is NULL, item is added to the top level
 203  * list (@list itself) with id equal to @address.
 204  * Otherwise, @address is split by @delim and each
 205  * id is added as new 'layer'. For example:
 206  *
 207  * > @address = "one:two:three", @delim = ":" will
 208  *   produce:
 209  *      top_level_list:one
 210  *                     `- "one" list:two
 211  *                                   `- "two" list:three
 212  *   where @value is assigned to the "two" list:three
 213  *   item.
 214  *
 215  * Returns: true if successful, otherwise false. Will
 216  * always return false if item specified by @address
 217  * already exists in the nested list.
 218  */
 219 bool nested_list_add_item(nested_list_t *list,
 220       const char *address, const char *delim, const void *value)
 221 {
 222    struct string_list id_list = {0};
 223    const char *top_id         = NULL;
 224    bool success               = false;
 225
 226    if (!list || string_is_empty(address))
 227       goto end;
 228
 229    /* If delim is NULL or address contains a single
 230     * token, then we are adding an item to the top
 231     * level list */
 232    if (string_is_empty(delim))
 233       top_id = address;
 234    else
 235    {
 236       string_list_initialize(&id_list);
 237       if (!string_split_noalloc(&id_list, address, delim) ||
 238           (id_list.size < 1))
 239          goto end;
 240
 241       if (id_list.size == 1)
 242          top_id = id_list.elems[0].data;
 243    }
 244
 245    if (!string_is_empty(top_id))
 246    {
 247       if (nested_list_add_item_to_list(list, NULL, top_id, value))
 248          success = true;
 249    }
 250    else
 251    {
 252       nested_list_t *current_list     = list;
 253       nested_list_item_t *parent_item = NULL;
 254       nested_list_item_t *next_item   = NULL;
 255       size_t i;
 256
 257       /* Loop over list item ids */
 258       for (i = 0; i < id_list.size; i++)
 259       {
 260          const char *id = id_list.elems[i].data;
 261
 262          if (string_is_empty(id))
 263             goto end;
 264
 265          /* If this is the last entry in the id list,
 266           * then we are adding the item itself */
 267          if (i == (id_list.size - 1))
 268          {
 269             if (nested_list_add_item_to_list(current_list,
 270                   parent_item, id, value))
 271                success = true;
 272
 273             break;
 274          }
 275          /* Otherwise, id corresponds to a 'category' */
 276          else
 277          {
 278             /* Check whether category item already exists */
 279             next_item = RHMAP_GET_STR(current_list->item_map, id);
 280
 281             /* Create it, if required */
 282             if (!next_item)
 283                next_item = nested_list_add_item_to_list(current_list,
 284                      parent_item, id, NULL);
 285
 286             if (!next_item)
 287                break;
 288
 289             /* Update pointers */
 290             parent_item  = next_item;
 291             current_list = next_item->children;
 292          }
 293       }
 294    }
 295
 296 end:
 297    string_list_deinitialize(&id_list);
 298    return success;
 299 }
 300
 301 /***********/
 302 /* Getters */
 303 /***********/
 304
 305 /**
 306  * nested_list_get_size:
 307  *
 308  * @list : pointer to nested_list_t object
 309  *
 310  * Fetches the current size (number of items) in
 311  * the specified list.
 312  *
 313  * Returns: list size.
 314  */
 315 size_t nested_list_get_size(nested_list_t *list)
 316 {
 317    if (!list)
 318       return 0;
 319
 320    return RBUF_LEN(list->items);
 321 }
 322
 323 /**
 324  * nested_list_get_item:
 325  *
 326  * @list    : pointer to nested_list_t object
 327  * @address : a delimited list of item identifiers,
 328  *            corresponding to item 'levels'
 329  * @delim   : delimiter to use when splitting @address
 330  *            into individual ids
 331  *
 332  * Searches for (and returns) the list item corresponding
 333  * to @address. If @delim is NULL, the top level list
 334  * (@list itself) is searched for an item with an id
 335  * equal to @address. Otherwise, @address is split by
 336  * @delim and each id is searched for in a subsequent
 337  * list level.
 338  *
 339  * Returns: valid nested_list_item_t pointer if item
 340  * is found, otherwise NULL.
 341  */
 342 nested_list_item_t *nested_list_get_item(nested_list_t *list,
 343       const char *address, const char *delim)
 344 {
 345    nested_list_item_t *search_item = NULL;
 346    struct string_list id_list      = {0};
 347    const char *top_id              = NULL;
 348
 349    if (!list || string_is_empty(address))
 350       goto end;
 351
 352    /* If delim is NULL or address contains a single
 353     * token, then we are fetching an item from the
 354     * top level list */
 355    if (string_is_empty(delim))
 356       top_id = address;
 357    else
 358    {
 359       string_list_initialize(&id_list);
 360       if (!string_split_noalloc(&id_list, address, delim) ||
 361           (id_list.size < 1))
 362          goto end;
 363
 364       if (id_list.size == 1)
 365          top_id = id_list.elems[0].data;
 366    }
 367
 368    if (!string_is_empty(top_id))
 369       search_item = RHMAP_GET_STR(list->item_map, top_id);
 370    else
 371    {
 372       /* Otherwise, search 'category' levels */
 373       nested_list_t *current_list   = list;
 374       nested_list_item_t *next_item = NULL;
 375       size_t i;
 376
 377       /* Loop over list item ids */
 378       for (i = 0; i < id_list.size; i++)
 379       {
 380          const char *id = id_list.elems[i].data;
 381
 382          if (string_is_empty(id))
 383             goto end;
 384
 385          /* If this is the last entry in the id list,
 386           * then we are searching for the item itself */
 387          if (i == (id_list.size - 1))
 388          {
 389             search_item = RHMAP_GET_STR(current_list->item_map, id);
 390             break;
 391          }
 392          /* Otherwise, id corresponds to a 'category' */
 393          else
 394          {
 395             next_item = RHMAP_GET_STR(current_list->item_map, id);
 396
 397             if (!next_item)
 398                break;
 399
 400             /* Update pointer */
 401             current_list = next_item->children;
 402          }
 403       }
 404    }
 405
 406 end:
 407    string_list_deinitialize(&id_list);
 408    return search_item;
 409 }
 410
 411 /**
 412  * nested_list_get_item_idx:
 413  *
 414  * @list : pointer to nested_list_t object
 415  * @idx  : item index
 416  *
 417  * Fetches the item corresponding to index @idx in
 418  * the top level list (@list itself) of the specified
 419  * nested list.
 420  *
 421  * Returns: valid nested_list_item_t pointer if item
 422  * exists, otherwise NULL.
 423  */
 424 nested_list_item_t *nested_list_get_item_idx(nested_list_t *list,
 425       size_t idx)
 426 {
 427    if (!list || (idx >= RBUF_LEN(list->items)))
 428       return NULL;
 429
 430    return list->items[idx];
 431 }
 432
 433 /**
 434  * nested_list_item_get_parent:
 435  *
 436  * @list_item : pointer to nested_list_item_t object
 437  *
 438  * Fetches the parent item of the specified nested
 439  * list item. If returned value is NULL, specified
 440  * nested list item belongs to a top level list.
 441  *
 442  * Returns: valid nested_list_item_t pointer if item
 443  * has a parent, otherwise NULL.
 444  */
 445 nested_list_item_t *nested_list_item_get_parent(nested_list_item_t *list_item)
 446 {
 447    if (!list_item)
 448       return NULL;
 449
 450    return list_item->parent_item;
 451 }
 452
 453 /**
 454  * nested_list_item_get_parent_list:
 455  *
 456  * @list_item : pointer to nested_list_item_t object
 457  *
 458  * Fetches a pointer to the nested list of which the
 459  * specified list item is a direct member.
 460  *
 461  * Returns: valid nested_list_t pointer if successful,
 462  * otherwise NULL.
 463  */
 464 nested_list_t *nested_list_item_get_parent_list(nested_list_item_t *list_item)
 465 {
 466    if (!list_item)
 467       return NULL;
 468
 469    return list_item->parent_list;
 470 }
 471
 472 /**
 473  * nested_list_item_get_children:
 474  *
 475  * @list_item : pointer to nested_list_item_t object
 476  *
 477  * Fetches a pointer to the nested list of child items
 478  * belonging to the specified list item.
 479  *
 480  * Returns: valid nested_list_t pointer if item has
 481  * children, otherwise NULL.
 482  */
 483 nested_list_t *nested_list_item_get_children(nested_list_item_t *list_item)
 484 {
 485    if (!list_item ||
 486        !list_item->children ||
 487        (RBUF_LEN(list_item->children->items) < 1))
 488       return NULL;
 489
 490    return list_item->children;
 491 }
 492
 493 /**
 494  * nested_list_item_get_id:
 495  *
 496  * @list_item : pointer to nested_list_item_t object
 497  *
 498  * Fetches the id string of the specified list item,
 499  * as set by nested_list_add_item().
 500  *
 501  * Returns: item id if successful, otherwise NULL.
 502  */
 503 const char *nested_list_item_get_id(nested_list_item_t *list_item)
 504 {
 505    if (!list_item)
 506       return NULL;
 507
 508    return list_item->id;
 509 }
 510
 511 /**
 512  * nested_list_item_get_address:
 513  *
 514  * @list_item : pointer to nested_list_item_t object
 515  * @delim     : delimiter to use when concatenating
 516  *              individual item ids into a an @address
 517  *              string
 518  * @address   : a delimited list of item identifiers,
 519  *              corresponding to item 'levels'
 520  * @len       : length of supplied @address char array
 521
 522  * Fetches a compound @address string corresponding to
 523  * the specified item's 'position' in the top level
 524  * nested list of which it is a member. The resultant
 525  * @address may be used to find the item when calling
 526  * nested_list_get_item() on the top level nested list.
 527  *
 528  * Returns: true if successful, otherwise false.
 529  */
 530 bool nested_list_item_get_address(nested_list_item_t *list_item,
 531       const char *delim, char *address, size_t len)
 532 {
 533    nested_list_item_t *current_item = list_item;
 534    struct string_list id_list       = {0};
 535    bool success                     = false;
 536    union string_list_elem_attr attr;
 537    size_t i;
 538
 539    if (!list_item ||
 540        string_is_empty(delim) ||
 541        !address ||
 542        (len < 1))
 543       goto end;
 544
 545    address[0] = '\0';
 546    attr.i     = 0;
 547
 548    /* If this is an item of the top level
 549     * list, just copy the item id directly */
 550    if (!list_item->parent_item)
 551    {
 552       strlcpy(address, list_item->id, len);
 553       success = true;
 554       goto end;
 555    }
 556
 557    /* ...otherwise we have to combine the ids
 558     * of the item and all of its 'ancestors' */
 559    string_list_initialize(&id_list);
 560
 561    /* Fetch all ids */
 562    do
 563    {
 564       const char *id = current_item->id;
 565
 566       if (string_is_empty(id) ||
 567           !string_list_append(&id_list, id, attr))
 568          goto end;
 569
 570       current_item = current_item->parent_item;
 571    }
 572    while (current_item);
 573
 574    if (id_list.size < 1)
 575       goto end;
 576
 577    /* Build address string */
 578    for (i = id_list.size; i > 0; i--)
 579    {
 580       const char *id = id_list.elems[i - 1].data;
 581
 582       if (string_is_empty(id))
 583          goto end;
 584
 585       strlcat(address, id, len);
 586       if (i > 1)
 587          strlcat(address, delim, len);
 588    }
 589
 590    success = true;
 591 end:
 592    string_list_deinitialize(&id_list);
 593    return success;
 594 }
 595
 596 /**
 597  * nested_list_item_get_value:
 598  *
 599  * @list_item : pointer to nested_list_item_t object
 600  *
 601  * Fetches the value (user data) associated with the
 602  * specified list item.
 603  *
 604  * Returns: pointer to user data if set, otherwise
 605  * NULL.
 606  */
 607 const void *nested_list_item_get_value(nested_list_item_t *list_item)
 608 {
 609    if (!list_item)
 610       return NULL;
 611
 612    return list_item->value;
 613 }