| 1 | /* Copyright (C) 2010-2020 The RetroArch team |
| 2 | * |
| 3 | * --------------------------------------------------------------------------------------- |
| 4 | * The following license statement only applies to this file (linked_list.h). |
| 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 | #ifndef __LIBRETRO_SDK_LINKED_LIST_H |
| 24 | #define __LIBRETRO_SDK_LINKED_LIST_H |
| 25 | |
| 26 | #include <retro_common_api.h> |
| 27 | |
| 28 | #include <boolean.h> |
| 29 | #include <stddef.h> |
| 30 | |
| 31 | RETRO_BEGIN_DECLS |
| 32 | |
| 33 | /** |
| 34 | * Represents a linked list. Contains any number of elements. |
| 35 | */ |
| 36 | typedef struct linked_list linked_list_t; |
| 37 | |
| 38 | /** |
| 39 | * Represents an iterator for iterating over a linked list. The iterator can |
| 40 | * go through the linked list forwards or backwards. |
| 41 | */ |
| 42 | typedef struct linked_list_iterator linked_list_iterator_t; |
| 43 | |
| 44 | /** |
| 45 | * Creates a new linked list with no elements. |
| 46 | * |
| 47 | * @return New linked list |
| 48 | */ |
| 49 | linked_list_t *linked_list_new(void); |
| 50 | |
| 51 | /** |
| 52 | * @brief frees the memory used by the linked list |
| 53 | * |
| 54 | * Frees all of the memory used by this linked list. The values of all |
| 55 | * remaining elements are freed using the "free_value" function. Does |
| 56 | * nothing if "list" is NULL. |
| 57 | * |
| 58 | * @param list linked list to free |
| 59 | * @param free_value function to use to free remaining values |
| 60 | */ |
| 61 | void linked_list_free(linked_list_t *list, void (*free_value)(void *value)); |
| 62 | |
| 63 | /** |
| 64 | * @brief adds an element to the linked list |
| 65 | * |
| 66 | * Add a new element to the end of this linked list. Does nothing if |
| 67 | * "list" is NULL. |
| 68 | * |
| 69 | * @param list list to add the element to |
| 70 | * @param value new value to add to the linked list |
| 71 | */ |
| 72 | void linked_list_add(linked_list_t *list, void *value); |
| 73 | |
| 74 | /** |
| 75 | * @brief inserts a value into the linked list |
| 76 | * |
| 77 | * Inserts a value into the linked list at the specified index. Does |
| 78 | * nothing if "list" is NULL. |
| 79 | * |
| 80 | * @param list list to insert the value into |
| 81 | * @param index index where the value should be inserted at (can be equal to list size) |
| 82 | * @param value value to insert into the linked list |
| 83 | */ |
| 84 | void linked_list_insert(linked_list_t *list, size_t index, void *value); |
| 85 | |
| 86 | /** |
| 87 | * @brief Get the value in the linked list at the provided index. |
| 88 | * |
| 89 | * Return the value vstored in the linked list at the provided index. Does |
| 90 | * nothing if "list" is NULL. |
| 91 | * |
| 92 | * @param list list to get the value from |
| 93 | * @param index index of the value to return |
| 94 | * @return value in the list at the provided index |
| 95 | */ |
| 96 | void *linked_list_get(linked_list_t *list, size_t index); |
| 97 | |
| 98 | /** |
| 99 | * @brief Get the first value that is matched by the provided function |
| 100 | * |
| 101 | * Return the first value that the function matches. The matches function |
| 102 | * parameters are value from the linked list and the provided state. |
| 103 | * |
| 104 | * @param list list to get the value from |
| 105 | * @param matches function to test the values with |
| 106 | * @param usrptr user data to pass to the matches function |
| 107 | * @return first value that matches otherwise NULL |
| 108 | */ |
| 109 | void *linked_list_get_first_matching(linked_list_t *list, bool (*matches)(void *item, void *usrptr), void *usrptr); |
| 110 | |
| 111 | /** |
| 112 | * @brief Get the last value that is matched by the provided function |
| 113 | * |
| 114 | * Return the last value that the function matches. The matches function |
| 115 | * parameters are value from the linked list and the provided state. |
| 116 | * |
| 117 | * @param list list to get the value from |
| 118 | * @param matches function to test the values with |
| 119 | * @param usrptr user data to pass to the matches function |
| 120 | * @return last value that matches otherwise NULL |
| 121 | */ |
| 122 | void *linked_list_get_last_matching(linked_list_t *list, bool (*matches)(void *item, void *usrptr), void *usrptr); |
| 123 | |
| 124 | /** |
| 125 | * @brief Remove the element at the provided index |
| 126 | * |
| 127 | * Removes the element of the linked list at the provided index. |
| 128 | * |
| 129 | * @param list linked list to remove the element from |
| 130 | * @param index index of the element to remove |
| 131 | * @return value of the element that was removed, NULL if list is NULL or |
| 132 | * index is invalid |
| 133 | */ |
| 134 | void *linked_list_remove_at(linked_list_t *list, size_t index); |
| 135 | |
| 136 | /** |
| 137 | * @brief Remove the first element with the provided value |
| 138 | * |
| 139 | * Removes the first element with a value equal to the provided value. |
| 140 | * Does nothing if "list" is NULL. |
| 141 | * |
| 142 | * @param list linked list to remove the element from |
| 143 | * @param value value of the element to remove |
| 144 | * @return value if a matching element was removed |
| 145 | */ |
| 146 | void *linked_list_remove_first(linked_list_t *list, void *value); |
| 147 | |
| 148 | /** |
| 149 | * @brief Remove the last element with the provided value |
| 150 | * |
| 151 | * Removes the last element with a value equal to the provided value. |
| 152 | * Does nothing if "list" is NULL. |
| 153 | * |
| 154 | * @param list linked list to remove the element from |
| 155 | * @param value value of the element to remove |
| 156 | * @return value if a matching element was removed |
| 157 | */ |
| 158 | void *linked_list_remove_last(linked_list_t *list, void *value); |
| 159 | |
| 160 | /** |
| 161 | * @brief Remove all elements with the provided value |
| 162 | * |
| 163 | * Removes all elements with a value equal to the provided value. |
| 164 | * Does nothing if "list" is NULL. |
| 165 | * |
| 166 | * @param list linked list to remove the elements from |
| 167 | * @param value value of the elements to remove |
| 168 | * @return value if any matching element(s) where removed |
| 169 | */ |
| 170 | void *linked_list_remove_all(linked_list_t *list, void *value); |
| 171 | |
| 172 | /** |
| 173 | * @brief Remove the first matching element |
| 174 | * |
| 175 | * Removes the first matching element from the linked list. The "matches" function |
| 176 | * is used to test for matching element values. Does nothing if "list" is NULL. |
| 177 | * |
| 178 | * @param list linked list to remove the element from |
| 179 | * @param matches function to use for testing element values for a match |
| 180 | * @return value if a matching element was removed |
| 181 | */ |
| 182 | void *linked_list_remove_first_matching(linked_list_t *list, bool (*matches)(void *value)); |
| 183 | |
| 184 | /** |
| 185 | * @brief Remove the last matching element |
| 186 | * |
| 187 | * Removes the last matching element from the linked list. The "matches" function |
| 188 | * is used to test for matching element values. |
| 189 | * |
| 190 | * @param list linked list to remove the element from |
| 191 | * @param matches function to use for testing element value for a match |
| 192 | * @return value if a matching element was removed |
| 193 | */ |
| 194 | void *linked_list_remove_last_matching(linked_list_t *list, bool (*matches)(void *value)); |
| 195 | |
| 196 | /** |
| 197 | * @brief Remove all matching elements |
| 198 | * |
| 199 | * Removes all matching elements from the linked list. The "matches" function |
| 200 | * is used to test for matching element values. Does nothing if "list" is NULL. |
| 201 | * |
| 202 | * @param list linked list to remove the elements from |
| 203 | * @param matches function to use for testing element values for a match |
| 204 | */ |
| 205 | void linked_list_remove_all_matching(linked_list_t *list, bool (*matches)(void *value)); |
| 206 | |
| 207 | /** |
| 208 | * @brief Replace the value of the element at the provided index |
| 209 | * |
| 210 | * Replaces the value of the element at the provided index. The linked list must |
| 211 | * contain an element at the index. |
| 212 | * |
| 213 | * @param list linked list to replace the value in |
| 214 | * @param index index of the element to replace the value of |
| 215 | * @param value new value for the selected element |
| 216 | * @return whether an element was updated |
| 217 | */ |
| 218 | bool linked_list_set_at(linked_list_t *list, size_t index, void *value); |
| 219 | |
| 220 | /** |
| 221 | * @brief Get the size of the linked list |
| 222 | * |
| 223 | * Returns the number of elements in the linked list. |
| 224 | * |
| 225 | * @param linked list to get the size of |
| 226 | * @return number of elements in the linked list, 0 if linked list is NULL |
| 227 | */ |
| 228 | size_t linked_list_size(linked_list_t *list); |
| 229 | |
| 230 | /** |
| 231 | * @brief Get an iterator for the linked list |
| 232 | * |
| 233 | * Returns a new iterator for the linked list. Can be either a forward or backward |
| 234 | * iterator. |
| 235 | * |
| 236 | * @param list linked list to iterate over |
| 237 | * @param forward true for a forward iterator, false for backwards |
| 238 | * @return new iterator for the linked list in the specified direction, NULL if |
| 239 | * "list" is NULL |
| 240 | */ |
| 241 | linked_list_iterator_t *linked_list_iterator(linked_list_t *list, bool forward); |
| 242 | |
| 243 | /** |
| 244 | * @brief Move to the next element in the linked list |
| 245 | * |
| 246 | * Moves the iterator to the next element in the linked list. The direction is |
| 247 | * specified when retrieving a new iterator. |
| 248 | * |
| 249 | * @param iterator iterator for the current element |
| 250 | * @return iterator for the next element, NULL if iterator is NULL or "iterator" |
| 251 | * is at the last element |
| 252 | */ |
| 253 | linked_list_iterator_t *linked_list_iterator_next(linked_list_iterator_t *iterator); |
| 254 | |
| 255 | /** |
| 256 | * @brief Get the value of the element for the iterator |
| 257 | * |
| 258 | * Returns the value of the element that the iterator is at. |
| 259 | * |
| 260 | * @param iterator iterator for the current element |
| 261 | * @return value of the element for the iterator |
| 262 | */ |
| 263 | void *linked_list_iterator_value(linked_list_iterator_t *iterator); |
| 264 | |
| 265 | /** |
| 266 | * @brief Remove the element that the iterator is at |
| 267 | * |
| 268 | * Removes the element that the iterator is at. The iterator is updated to the |
| 269 | * next element. |
| 270 | * |
| 271 | * @param iterator iterator for the current element |
| 272 | * @return updated iterator or NULL if the last element was removed |
| 273 | */ |
| 274 | linked_list_iterator_t *linked_list_iterator_remove(linked_list_iterator_t *iterator); |
| 275 | |
| 276 | /** |
| 277 | * @brief Release the memory for the iterator |
| 278 | * |
| 279 | * Frees the memory for the provided iterator. Does nothing if "iterator" is NULL. |
| 280 | * |
| 281 | * @param iterator iterator to free |
| 282 | */ |
| 283 | void linked_list_iterator_free(linked_list_iterator_t *iterator); |
| 284 | |
| 285 | /** |
| 286 | * @brief Apply the provided function to all values in the linked list |
| 287 | * |
| 288 | * Apply the provied function to all values in the linked list. The values are applied |
| 289 | * in the forward direction. Does nothing if "list" is NULL. |
| 290 | * |
| 291 | * @param list linked list to apply the function to |
| 292 | * @param fn function to apply to all elements |
| 293 | */ |
| 294 | void linked_list_foreach(linked_list_t *list, void (*fn)(size_t index, void *value)); |
| 295 | |
| 296 | RETRO_END_DECLS |
| 297 | |
| 298 | #endif |