1 /* Copyright (C) 2010-2020 The RetroArch team
3 * ---------------------------------------------------------------------------------------
4 * The following license statement only applies to this file (nested_list.c).
5 * ---------------------------------------------------------------------------------------
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:
13 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
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.
23 #include <string/stdstring.h>
24 #include <lists/string_list.h>
25 #include <array/rbuf.h>
26 #include <array/rhmap.h>
28 #include <lists/nested_list.h>
30 struct nested_list_item
32 nested_list_item_t *parent_item;
33 nested_list_t *parent_list;
34 nested_list_t *children;
41 nested_list_item_t **items;
42 nested_list_item_t **item_map;
45 /**************************************/
46 /* Initialisation / De-Initialisation */
47 /**************************************/
49 /* Forward declaration - required since
50 * nested_list_free_list() is recursive */
51 static void nested_list_free_list(nested_list_t *list);
53 /* Frees contents of a nested list item */
54 static void nested_list_free_item(nested_list_item_t *item)
59 item->parent_item = NULL;
60 item->parent_list = NULL;
64 nested_list_free_list(item->children);
65 item->children = NULL;
78 /* Frees contents of a nested list */
79 static void nested_list_free_list(nested_list_t *list)
86 for (i = 0; i < RBUF_LEN(list->items); i++)
87 nested_list_free_item(list->items[i]);
89 RBUF_FREE(list->items);
90 RHMAP_FREE(list->item_map);
97 * Creates a new empty nested list. Returned pointer
98 * must be freed using nested_list_free.
100 * Returns: Valid nested_list_t pointer if successful,
103 nested_list_t *nested_list_init(void)
105 /* Create nested list */
106 nested_list_t *list = (nested_list_t*)malloc(sizeof(*list));
111 /* Initialise members */
113 list->item_map = NULL;
120 * @list : pointer to nested_list_t object
122 * Frees specified nested list.
124 void nested_list_free(nested_list_t *list)
126 nested_list_free_list(list);
133 /* Creates and adds a new item to the specified
134 * nested list. Returns NULL if item matching 'id'
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)
139 size_t num_items = 0;
140 nested_list_item_t *new_item = NULL;
141 nested_list_t *child_list = NULL;
143 if (!list || string_is_empty(id))
146 num_items = RBUF_LEN(list->items);
148 /* Ensure that item does not already exist */
149 if (RHMAP_HAS_STR(list->item_map, id))
152 /* Attempt to allocate a buffer slot for the
154 if (!RBUF_TRYFIT(list->items, num_items + 1))
157 /* Create new empty child list */
158 child_list = nested_list_init();
162 /* Create new list item */
163 new_item = (nested_list_item_t*)malloc(sizeof(*new_item));
166 nested_list_free(child_list);
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;
177 /* Increment item buffer size */
178 RBUF_RESIZE(list->items, num_items + 1);
180 /* Add new item to buffer */
181 list->items[num_items] = new_item;
184 RHMAP_SET_STR(list->item_map, id, new_item);
190 * nested_list_add_item:
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
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:
207 * > @address = "one:two:three", @delim = ":" will
211 * `- "two" list:three
212 * where @value is assigned to the "two" list:three
215 * Returns: true if successful, otherwise false. Will
216 * always return false if item specified by @address
217 * already exists in the nested list.
219 bool nested_list_add_item(nested_list_t *list,
220 const char *address, const char *delim, const void *value)
222 struct string_list id_list = {0};
223 const char *top_id = NULL;
224 bool success = false;
226 if (!list || string_is_empty(address))
229 /* If delim is NULL or address contains a single
230 * token, then we are adding an item to the top
232 if (string_is_empty(delim))
236 string_list_initialize(&id_list);
237 if (!string_split_noalloc(&id_list, address, delim) ||
241 if (id_list.size == 1)
242 top_id = id_list.elems[0].data;
245 if (!string_is_empty(top_id))
247 if (nested_list_add_item_to_list(list, NULL, top_id, value))
252 nested_list_t *current_list = list;
253 nested_list_item_t *parent_item = NULL;
254 nested_list_item_t *next_item = NULL;
257 /* Loop over list item ids */
258 for (i = 0; i < id_list.size; i++)
260 const char *id = id_list.elems[i].data;
262 if (string_is_empty(id))
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))
269 if (nested_list_add_item_to_list(current_list,
270 parent_item, id, value))
275 /* Otherwise, id corresponds to a 'category' */
278 /* Check whether category item already exists */
279 next_item = RHMAP_GET_STR(current_list->item_map, id);
281 /* Create it, if required */
283 next_item = nested_list_add_item_to_list(current_list,
284 parent_item, id, NULL);
289 /* Update pointers */
290 parent_item = next_item;
291 current_list = next_item->children;
297 string_list_deinitialize(&id_list);
306 * nested_list_get_size:
308 * @list : pointer to nested_list_t object
310 * Fetches the current size (number of items) in
311 * the specified list.
313 * Returns: list size.
315 size_t nested_list_get_size(nested_list_t *list)
320 return RBUF_LEN(list->items);
324 * nested_list_get_item:
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
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
339 * Returns: valid nested_list_item_t pointer if item
340 * is found, otherwise NULL.
342 nested_list_item_t *nested_list_get_item(nested_list_t *list,
343 const char *address, const char *delim)
345 nested_list_item_t *search_item = NULL;
346 struct string_list id_list = {0};
347 const char *top_id = NULL;
349 if (!list || string_is_empty(address))
352 /* If delim is NULL or address contains a single
353 * token, then we are fetching an item from the
355 if (string_is_empty(delim))
359 string_list_initialize(&id_list);
360 if (!string_split_noalloc(&id_list, address, delim) ||
364 if (id_list.size == 1)
365 top_id = id_list.elems[0].data;
368 if (!string_is_empty(top_id))
369 search_item = RHMAP_GET_STR(list->item_map, top_id);
372 /* Otherwise, search 'category' levels */
373 nested_list_t *current_list = list;
374 nested_list_item_t *next_item = NULL;
377 /* Loop over list item ids */
378 for (i = 0; i < id_list.size; i++)
380 const char *id = id_list.elems[i].data;
382 if (string_is_empty(id))
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))
389 search_item = RHMAP_GET_STR(current_list->item_map, id);
392 /* Otherwise, id corresponds to a 'category' */
395 next_item = RHMAP_GET_STR(current_list->item_map, id);
401 current_list = next_item->children;
407 string_list_deinitialize(&id_list);
412 * nested_list_get_item_idx:
414 * @list : pointer to nested_list_t object
417 * Fetches the item corresponding to index @idx in
418 * the top level list (@list itself) of the specified
421 * Returns: valid nested_list_item_t pointer if item
422 * exists, otherwise NULL.
424 nested_list_item_t *nested_list_get_item_idx(nested_list_t *list,
427 if (!list || (idx >= RBUF_LEN(list->items)))
430 return list->items[idx];
434 * nested_list_item_get_parent:
436 * @list_item : pointer to nested_list_item_t object
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.
442 * Returns: valid nested_list_item_t pointer if item
443 * has a parent, otherwise NULL.
445 nested_list_item_t *nested_list_item_get_parent(nested_list_item_t *list_item)
450 return list_item->parent_item;
454 * nested_list_item_get_parent_list:
456 * @list_item : pointer to nested_list_item_t object
458 * Fetches a pointer to the nested list of which the
459 * specified list item is a direct member.
461 * Returns: valid nested_list_t pointer if successful,
464 nested_list_t *nested_list_item_get_parent_list(nested_list_item_t *list_item)
469 return list_item->parent_list;
473 * nested_list_item_get_children:
475 * @list_item : pointer to nested_list_item_t object
477 * Fetches a pointer to the nested list of child items
478 * belonging to the specified list item.
480 * Returns: valid nested_list_t pointer if item has
481 * children, otherwise NULL.
483 nested_list_t *nested_list_item_get_children(nested_list_item_t *list_item)
486 !list_item->children ||
487 (RBUF_LEN(list_item->children->items) < 1))
490 return list_item->children;
494 * nested_list_item_get_id:
496 * @list_item : pointer to nested_list_item_t object
498 * Fetches the id string of the specified list item,
499 * as set by nested_list_add_item().
501 * Returns: item id if successful, otherwise NULL.
503 const char *nested_list_item_get_id(nested_list_item_t *list_item)
508 return list_item->id;
512 * nested_list_item_get_address:
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
518 * @address : a delimited list of item identifiers,
519 * corresponding to item 'levels'
520 * @len : length of supplied @address char array
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.
528 * Returns: true if successful, otherwise false.
530 bool nested_list_item_get_address(nested_list_item_t *list_item,
531 const char *delim, char *address, size_t len)
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;
540 string_is_empty(delim) ||
548 /* If this is an item of the top level
549 * list, just copy the item id directly */
550 if (!list_item->parent_item)
552 strlcpy(address, list_item->id, len);
557 /* ...otherwise we have to combine the ids
558 * of the item and all of its 'ancestors' */
559 string_list_initialize(&id_list);
564 const char *id = current_item->id;
566 if (string_is_empty(id) ||
567 !string_list_append(&id_list, id, attr))
570 current_item = current_item->parent_item;
572 while (current_item);
574 if (id_list.size < 1)
577 /* Build address string */
578 for (i = id_list.size; i > 0; i--)
580 const char *id = id_list.elems[i - 1].data;
582 if (string_is_empty(id))
585 strlcat(address, id, len);
587 strlcat(address, delim, len);
592 string_list_deinitialize(&id_list);
597 * nested_list_item_get_value:
599 * @list_item : pointer to nested_list_item_t object
601 * Fetches the value (user data) associated with the
602 * specified list item.
604 * Returns: pointer to user data if set, otherwise
607 const void *nested_list_item_get_value(nested_list_item_t *list_item)
612 return list_item->value;