1 /* EINA - EFL data type library 2 * Copyright (C) 2002-2008 Carsten Haitzler, Vincent Torri, Jorge Luis Zapata Muga 3 * 4 * This library is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU Lesser General Public 6 * License as published by the Free Software Foundation; either 7 * version 2.1 of the License, or (at your option) any later version. 8 * 9 * This library is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 * Lesser General Public License for more details. 13 * 14 * You should have received a copy of the GNU Lesser General Public 15 * License along with this library; 16 * if not, see <http://www.gnu.org/licenses/>. 17 */ 18 19 #ifndef EINA_LIST_H_ 20 #define EINA_LIST_H_ 21 22 #include <stdlib.h> 23 24 #include "eina_config.h" 25 26 // magic number checks for eina list nodes - this costs extra memory and a 27 // few cycles for some safety = aybe during debugging/devel only? 28 //#define EINA_LIST_MAGIC 1 29 30 #include "eina_types.h" 31 #include "eina_iterator.h" 32 #include "eina_accessor.h" 33 #ifdef EINA_LIST_MAGIC 34 # include "eina_magic.h" 35 #endif 36 37 /** 38 * @page eina_list_01_example_page Adding elements to Eina_List 39 * @dontinclude eina_list_01.c 40 * 41 * Creating an @ref Eina_List and adding elements to it is very easy and can be 42 * understood from an example: 43 * First thing is always to include Eina.h, for this example we also 44 * include stdio.h so we can use printf. 45 * @skip #include 46 * @until Eina.h 47 * 48 * Just some boilerplate code, declaring some variables and initializing eina. 49 * @until eina_init 50 * Here we add a sequence of elements to our list. By using append we add 51 * elements to the end of the list, so the list will look like this:@n 52 * @image rtf eina_list_example_01_a.png 53 * @image html eina_list_example_01_a.png 54 * @image latex eina_list_example_01_a.eps "" width=\textwidth 55 * @until roslin 56 * There are a couple of interesting things happening here, first is that we are 57 * passing a NULL pointer to the first @ref eina_list_append() call, when this 58 * is done a list is created. The other @b very important detail to notice is 59 * that the return value is attributed to the @a list variable, this needs to 60 * be done every time we use a a function that alters the contents of the list. 61 * 62 * Now that we have a list with some elements in it we can look at its contents. 63 * @until printf 64 * 65 * There are many ways of accessing elements in the list, including by its 66 * index: 67 * @until nth 68 * @note It should be noted that the index starts at 0. 69 * 70 * @ref eina_list_append() is not the only way to add elements to a a list. A 71 * common requirement is to add an element in a specific position this can be 72 * accomplished using @ref eina_list_append_relative() and 73 * @ref eina_list_append_relative_list(): 74 * @until zarek 75 * First @a "cain" is added after the second element (remember that indexes are 76 * 0 based) and then we add @a "zarek" after @a "cain". 77 * 78 * @ref Eina_List also has prepend analogs to append functions we have used so 79 * far: 80 * @until lampkin 81 * With this additions our list now looks like this:@n 82 * @image rtf eina_list_example_01_b.png 83 * @image html eina_list_example_01_b.png 84 * @image latex eina_list_example_01_b.eps "" width=\textwidth 85 * 86 * Once done using the list it needs to be freed, and since we are done with 87 * eina that also need to be shutdown: 88 * @until } 89 * 90 * The full source code can be found on the examples folder 91 * on the @ref eina_list_01_c "eina_list_01.c" file. 92 */ 93 94 /** 95 * @page eina_list_01_c Adding elements to Eina_List example 96 * 97 * @include eina_list_01.c 98 * @example eina_list_01.c 99 */ 100 101 /** 102 * @page eina_list_02_example_page Sorting Eina_List elements 103 * @dontinclude eina_list_02.c 104 * 105 * If you don't know how to create lists see 106 * @ref eina_list_01_example_page. 107 * 108 * @skip #include 109 * @until boomer 110 * This is the code we have already seen to create a list. Now if we need to 111 * search the list we can do it like this: 112 * @until return 113 * 114 * However if searching the list multiple times it probably is better to sort 115 * the list since the sorted_search functions are much faster: 116 * @until return 117 * 118 * Once the list is sorted it's not a good idea to use append/prepend functions 119 * since that would add the element in the wrong place, instead elements should 120 * be added with @ref eina_list_sorted_insert(): 121 * @until sorted_insert 122 * 123 * A noteworthy use case is adding an element to a list only if it doesn't exist 124 * already, this can accomplished by searching for the element that is closest 125 * to what is being added, and if that doesn't match add: 126 * @until append 127 * @note @ref eina_list_search_sorted_near_list() will tell you not only the 128 * nearest node to what was searched for but how it compares to your term, this 129 * way it is easy to know if you have to add before or after that node. 130 * 131 * It is sometimes useful to get a portion of the list as another list, here we 132 * take every element that comes after "boomer" and split it into "other_list": 133 * @until split_list 134 * 135 * It is also possible to add entire lists of elements using 136 * @ref eina_list_sorted_merge(): 137 * @until sorted_merge 138 * 139 * And as always release memory and shutdown eina before ending: 140 * @until } 141 * 142 * The full source code can be found on the examples folder 143 * on the @ref eina_list_02_c "eina_list_02.c" file. 144 */ 145 146 /** 147 * @page eina_list_02_c Sorting Eina_List elements example 148 * 149 * @include eina_list_02.c 150 * @example eina_list_02.c 151 */ 152 153 /** 154 * @page eina_list_03_example_page Reordering Eina_List elements 155 * @dontinclude eina_list_03.c 156 * 157 * If you don't know how to create lists see 158 * @ref eina_list_01_example_page. 159 * 160 * We start out with code that should be familiar by now: 161 * @skip #include 162 * @until gemenon 163 * 164 * You can move elements around in a list using @ref eina_list_move() or using 165 * @ref eina_list_promote_list() and @ref eina_list_demote_list() which move a 166 * list node to the head and end of the list respectively: 167 * @until demote 168 * 169 * Removing elements from a list can be done with ease: 170 * @until sagittarius 171 * 172 * To replace an element in the list it is not necessary to remove it and then 173 * re-add with the new value, it is possible to just change the value of a node: 174 * @until aquarius 175 * 176 * We will now take a peek to see if the list still has the right number of 177 * elements: 178 * @until printf 179 * 180 * Now that the list is in alphabetical order let's create a copy of it in 181 * reverse order and print every element to see if worked as expected: 182 * @until iterator_free 183 * @note Always remember to free your iterators when done using them. 184 * 185 * And as always release memory and shutdown eina before ending: 186 * @until } 187 * 188 * The full source code can be found on the examples folder 189 * on the @ref eina_list_03_c "eina_list_03.c" file. 190 */ 191 192 /** 193 * @page eina_list_03_c Reordering Eina_List elements example 194 * 195 * @include eina_list_03.c 196 * @example eina_list_03.c 197 */ 198 199 /** 200 * @page eina_list_04_example_page Eina_List and memory allocation 201 * @dontinclude eina_list_04.c 202 * 203 * If you don't know how to create lists see 204 * @ref eina_list_01_example_page. In this example we also use 205 * @ref Eina_Stringshare_Group, however it should be possible to understand the code 206 * regardless of previous knowledge about it. 207 * 208 * Here we have the usual list creation code with a twist, now we are using as 209 * data for the list memory that has to be freed later on. 210 * @skip #include 211 * @until Sharon 212 * 213 * This time we are going to iterate over our list in a different way: 214 * @until printf 215 * 216 * And now we are going to iterate over the list backwards: 217 * @until printf 218 * 219 * And now we need to free up the memory allocated during creation of the list: 220 * @until stringshare_del 221 * @note We don't need to use eina_list_free() since @ref EINA_LIST_FREE takes 222 * care of that. 223 * 224 * And shut everything down: 225 * @until } 226 * 227 * The full source code can be found on the examples folder 228 * on the @ref eina_list_04_c "eina_list_04.c" file. 229 */ 230 231 /** 232 * @page eina_list_04_c Eina_List and memory allocation example 233 * 234 * @include eina_list_04.c 235 * @example eina_list_04.c 236 */ 237 238 /** 239 * @addtogroup Eina_List_Group List 240 * 241 * @brief These functions provide double linked list management. 242 * 243 * Eina_List is a doubly linked list. It can store data of any type in the 244 * form of void pointers. It has convenience functions to do all the common 245 * operations which means it should rarely if ever be necessary to directly 246 * access the struct's fields. Nevertheless it can be useful to understand the 247 * inner workings of the data structure being used. 248 * 249 * @ref Eina_List nodes keep references to the previous node, the next node, its 250 * data and to an accounting structure. 251 * 252 * @image rtf eina_list.png 253 * @image html eina_list.png 254 * @image latex eina_list.eps width=5cm 255 * 256 * @ref Eina_List_Accounting is used to improve the performance of some 257 * functions. It is private and <b>should not</b> be modified. It contains a 258 * reference to the end of the list and the number of elements in the list. 259 * 260 * @note Every function that modifies the contents of the list returns a pointer 261 * to the head of the list and it is essential that this be pointer be used in 262 * any future references to the list. 263 * 264 * Most functions have two versions that have the same effect but operate on 265 * different arguments, the @a plain functions operate over data(e.g..: 266 * @ref eina_list_append_relative, @ref eina_list_remove, 267 * @ref eina_list_data_find), the @a list versions of these functions operate 268 * on @ref Eina_List nodes. 269 * 270 * @warning You must @b always use the pointer to the first element of the list 271 * as the list! 272 * @warning You must @b never use a pointer to an element in the middle of the 273 * list as the list! 274 * 275 * Here are some examples of @ref Eina_List usage: 276 * @li @ref eina_list_01_example_page 277 * @li @ref eina_list_02_example_page 278 * @li @ref eina_list_03_example_page 279 * @li @ref eina_list_04_example_page 280 */ 281 282 /** 283 * @addtogroup Eina_Data_Types_Group Data Types 284 * 285 * @{ 286 */ 287 288 /** 289 * @addtogroup Eina_Containers_Group Containers 290 * 291 * @{ 292 */ 293 294 /** 295 * @defgroup Eina_List_Group List 296 * 297 * @{ 298 */ 299 300 /** 301 * @typedef Eina_List 302 * Type for a generic double linked list. 303 */ 304 typedef struct _Eina_List Eina_List; 305 306 /** 307 * @typedef Eina_List_Accounting 308 * Cache used to store the last element of a list and the number of 309 * elements, for fast access. 310 */ 311 typedef struct _Eina_List_Accounting Eina_List_Accounting; 312 313 /** 314 * @struct _Eina_List 315 * Type for a generic double linked list. 316 */ 317 struct _Eina_List 318 { 319 void *data; /**< Pointer to list element payload */ 320 Eina_List *next; /**< Next member in the list */ 321 Eina_List *prev; /**< Previous member in the list */ 322 Eina_List_Accounting *accounting; /**< Private list accounting info - don't touch */ 323 #ifdef EINA_LIST_MAGIC 324 EINA_MAGIC 325 #endif 326 }; 327 328 /** 329 * @struct _Eina_List_Accounting 330 * Cache used to store the last element of a list and the number of 331 * elements, for fast access. It is for private use and must not be 332 * touched. 333 */ 334 struct _Eina_List_Accounting 335 { 336 Eina_List *last; /**< Pointer to the last element of the list - don't touch */ 337 unsigned int count; /**< Number of elements of the list - don't touch */ 338 EINA_MAGIC 339 }; 340 341 342 /** 343 * @brief Appends the given data to the given linked list. 344 * 345 * @param[in,out] list The given list. 346 * @param[in] data The data to append. 347 * @return A list pointer, or @c NULL on error. 348 * 349 * This function appends @p data to @p list. If @p list is @c NULL, a 350 * new list is returned. On success, a new list pointer that should be 351 * used in place of the one given to this function is 352 * returned. Otherwise, the old pointer is returned. 353 * 354 * The following example code demonstrates how to ensure that the 355 * given data has been successfully appended. 356 * 357 * @code 358 * Eina_List *list = NULL; 359 * extern void *my_data; 360 * 361 * list = eina_list_append(list, my_data); 362 * @endcode 363 * 364 * @warning @p list must be a pointer to the first element of the list(or NULL). 365 */ 366 EAPI Eina_List *eina_list_append(Eina_List *list, const void *data) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 367 368 369 /** 370 * @brief Prepends the given data to the given linked list. 371 * 372 * @param[in,out] list The given list. 373 * @param[in] data The data to prepend. 374 * @return A list pointer, or @c NULL on error. 375 * 376 * This function prepends @p data to @p list. If @p list is @c NULL, a 377 * new list is returned. On success, a new list pointer that should be 378 * used in place of the one given to this function is 379 * returned. Otherwise, the old pointer is returned. 380 * 381 * The following example code demonstrates how to ensure that the 382 * given data has been successfully prepended. 383 * 384 * Example: 385 * @code 386 * Eina_List *list = NULL; 387 * extern void *my_data; 388 * 389 * list = eina_list_prepend(list, my_data); 390 * @endcode 391 * 392 * @warning @p list must be a pointer to the first element of the list. 393 */ 394 EAPI Eina_List *eina_list_prepend(Eina_List *list, const void *data) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 395 396 397 /** 398 * @brief Inserts the given data into the given linked list after the specified data. 399 * 400 * @param[in,out] list The given linked list. 401 * @param[in] data The data to insert. 402 * @param[in] relative The data to insert after. 403 * @return A list pointer, or @c NULL on error. 404 * 405 * This function inserts @p data into @p list after @p relative. If 406 * @p relative is not in the list, @p data is appended to 407 * the list. If @p list is @c NULL, a new list is returned. If there 408 * are multiple instances of @p relative in the list, @p data is 409 * inserted after the first instance. On success, a new list pointer 410 * that should be used in place of the one given to this function is 411 * returned. Otherwise, the old pointer is returned. 412 * 413 * The following example code demonstrates how to ensure that the 414 * given data has been successfully inserted. 415 * 416 * @code 417 * Eina_List *list = NULL; 418 * extern void *my_data; 419 * extern void *relative_member; 420 * 421 * list = eina_list_append(list, relative_member); 422 * list = eina_list_append_relative(list, my_data, relative_member); 423 * @endcode 424 * 425 * @warning @p list must be a pointer to the first element of the list. 426 */ 427 EAPI Eina_List *eina_list_append_relative(Eina_List *list, const void *data, const void *relative) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 428 429 430 /** 431 * @brief Appends a list node to a linked list after the specified member. 432 * 433 * @param[in,out] list The given linked list. 434 * @param[in] data The data to insert. 435 * @param[in] relative The list node to insert after. 436 * @return A list pointer, or @c NULL on error. 437 * 438 * This function inserts @p data into @p list after the list node 439 * @p relative. If @p list or @p relative are @c NULL, @p data is just 440 * appended to @p list using eina_list_append(). If @p list is 441 * @c NULL, a new list is returned. If there are multiple instances 442 * of @p relative in the list, @p data is inserted after the first 443 * instance. On success, a new list pointer that should be used in 444 * place of the one given to this function is returned. Otherwise, the 445 * old pointer is returned. 446 * 447 * @warning @p list must be a pointer to the first element of the list. 448 */ 449 EAPI Eina_List *eina_list_append_relative_list(Eina_List *list, const void *data, Eina_List *relative) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 450 451 452 /** 453 * @brief Prepends a data pointer to a linked list before the specified member. 454 * 455 * @param[in,out] list The given linked list. 456 * @param[in] data The data to insert. 457 * @param[in] relative The member that data will be inserted before. 458 * @return A list pointer, or @c NULL on error. 459 * 460 * This function inserts @p data to @p list before @p relative. If 461 * @p relative is not in the list, @p data is prepended to the list 462 * with eina_list_prepend(). If @p list is @c NULL, a new list is 463 * returned. If there are multiple instances of @p relative in the 464 * list, @p data is inserted before the first instance. On success, a 465 * new list pointer that should be used in place of the one given to 466 * this function is returned. Otherwise, the old pointer is returned. 467 * 468 * The following code example demonstrates how to ensure that the 469 * given data has been successfully inserted. 470 * 471 * @code 472 * Eina_List *list = NULL; 473 * extern void *my_data; 474 * extern void *relative_member; 475 * 476 * list = eina_list_append(list, relative_member); 477 * list = eina_list_prepend_relative(list, my_data, relative_member); 478 * @endcode 479 * 480 * @warning @p list must be a pointer to the first element of the list. 481 */ 482 EAPI Eina_List *eina_list_prepend_relative(Eina_List *list, const void *data, const void *relative) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 483 484 485 /** 486 * @brief Prepends a list node to a linked list before the specified member. 487 * 488 * @param[in,out] list The given linked list. 489 * @param[in] data The data to insert. 490 * @param[in] relative The list node to insert before. 491 * @return A list pointer, or @c NULL on error. 492 * 493 * This function inserts @p data to @p list before the list node 494 * @p relative. If @p list or @p relative are @c NULL, @p data is just 495 * prepended to @p list using eina_list_prepend(). If @p list is 496 * @c NULL, a new list is returned. If there are multiple instances 497 * of @p relative in the list, @p data is inserted before the first 498 * instance. On success, a new list pointer that should be used in 499 * place of the one given to this function is returned. Otherwise, the 500 * old pointer is returned. 501 * 502 * @warning @p list must be a pointer to the first element of the list. 503 */ 504 EAPI Eina_List *eina_list_prepend_relative_list(Eina_List *list, const void *data, Eina_List *relative) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 505 506 507 /** 508 * @brief Inserts a new node into a sorted list. 509 * 510 * @param[in,out] list The given linked list, @b must be sorted. 511 * @param[in] func The function called for the sort. 512 * @param[in] data The data to be inserted in sorted order. 513 * @return A list pointer, or @c NULL on error. 514 * 515 * This function inserts values into a linked list assuming it was 516 * sorted and the result will be sorted. If @p list is @c NULL, a new 517 * list is returned. On success, a new list pointer that should be used 518 * in place of the one given to this function is returned. Otherwise, 519 * the old pointer is returned. 520 * 521 * @note O(log2(n)) comparisons (calls to @p func) average/worst case 522 * performance as it uses eina_list_search_sorted_near_list() and thus 523 * is bounded to that. As said in eina_list_search_sorted_near_list(), 524 * lists do not have O(1) access time, so walking to the correct node 525 * can be costly, consider worst case to be almost O(n) pointer 526 * dereference (list walk). 527 * 528 * @warning @p list must be a pointer to the first element of the list. 529 */ 530 EAPI Eina_List *eina_list_sorted_insert(Eina_List *list, Eina_Compare_Cb func, const void *data) EINA_ARG_NONNULL(2, 3) EINA_WARN_UNUSED_RESULT; 531 532 533 /** 534 * @brief Removes the first instance of the specified data from the given list. 535 * 536 * @param[in,out] list The given list. 537 * @param[in] data The specified data. 538 * @return A list pointer, or @c NULL on error. 539 * 540 * This function removes the first instance of @p data from @p list. If 541 * @p data is not in the given list or is @c NULL, nothing is done and 542 * the specified @p list returned. If @p list is @c NULL, @c NULL is 543 * returned, otherwise a new list pointer that should be used in place 544 * of the one passed to this function is returned. 545 * 546 * @warning @p list must be a pointer to the first element of the list. 547 */ 548 EAPI Eina_List *eina_list_remove(Eina_List *list, const void *data) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 549 550 551 /** 552 * @brief Removes the specified list node. 553 * 554 * @param[in,out] list The given linked list. 555 * @param[in] remove_list The list node which is to be removed. 556 * @return A list pointer, or @c NULL on error. 557 * 558 * This function removes the list node @p remove_list from @p list and 559 * frees the list node structure @p remove_list. If @p list is 560 * @c NULL, this function returns @c NULL. If @p remove_list is 561 * @c NULL, it returns @p list; otherwise, a new list pointer that 562 * should be used in place of the one passed to this function. 563 * 564 * The following code gives an example. (Notice we use 565 * EINA_LIST_FOREACH rather than EINA_LIST_FOREACH_SAFE because we stop 566 * the loop after removing the current node.) 567 * 568 * @code 569 * extern Eina_List *list; 570 * Eina_List *l; 571 * extern void *my_data; 572 * void *data 573 * 574 * EINA_LIST_FOREACH(list, l, data) 575 * { 576 * if (data == my_data) 577 * { 578 * list = eina_list_remove_list(list, l); 579 * break; 580 * } 581 * } 582 * @endcode 583 * 584 * @warning @p list must be a pointer to the first element of the list. 585 */ 586 EAPI Eina_List *eina_list_remove_list(Eina_List *list, Eina_List *remove_list) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 587 588 589 /** 590 * @brief Moves the specified data to the head of the list. 591 * 592 * @param[in,out] list The given linked list. 593 * @param[in] move_list The list node to move. 594 * @return A new list handle to replace the old one, or @c NULL on error. 595 * 596 * This function moves @p move_list to the front of @p list. If list is 597 * @c NULL, @c NULL is returned. If @p move_list is @c NULL, @p list is 598 * returned. Otherwise, a new list pointer that should be used in place 599 * of the one passed to this function is returned. 600 * 601 * Example: 602 * @code 603 * extern Eina_List *list; 604 * Eina_List *l; 605 * extern void *my_data; 606 * void *data; 607 * 608 * EINA_LIST_FOREACH(list, l, data) 609 * { 610 * if (data == my_data) 611 * { 612 * list = eina_list_promote_list(list, l); 613 * break; 614 * } 615 * } 616 * @endcode 617 * 618 * @warning @p list must be a pointer to the first element of the list. 619 */ 620 EAPI Eina_List *eina_list_promote_list(Eina_List *list, Eina_List *move_list) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 621 622 623 /** 624 * @brief Moves the specified data to the tail of the list. 625 * 626 * @param[in,out] list The given linked list. 627 * @param[in] move_list The list node to move. 628 * @return A new list handle to replace the old one, or @c NULL on error. 629 * 630 * This function move @p move_list to the end of @p list. If list is @c 631 * NULL, @c NULL is returned. If @p move_list is @c NULL, @p list is 632 * returned. Otherwise, a new list pointer that should be used in place 633 * of the one passed to this function is returned. 634 * 635 * Example: 636 * @code 637 * extern Eina_List *list; 638 * Eina_List *l; 639 * extern void *my_data; 640 * void *data; 641 * 642 * EINA_LIST_FOREACH(list, l, data) 643 * { 644 * if (data == my_data) 645 * { 646 * list = eina_list_demote_list(list, l); 647 * break; 648 * } 649 * } 650 * @endcode 651 * 652 * @warning @p list must be a pointer to the first element of the list. 653 */ 654 EAPI Eina_List *eina_list_demote_list(Eina_List *list, Eina_List *move_list); 655 656 657 /** 658 * @brief Finds a member of a list and returns it. 659 * 660 * @param[in] list The linked list to search. 661 * @param[in] data The data member to find in the list. 662 * @return The data member pointer if found, or @c NULL otherwise. 663 * 664 * This function searches in @p list from beginning to end for the 665 * first member whose data pointer is @p data. If it is found, @p data 666 * will be returned, otherwise @c NULL will be returned. 667 * 668 * Example: 669 * @code 670 * extern Eina_List *list; 671 * extern void *my_data; 672 * 673 * if (eina_list_data_find(list, my_data) == my_data) 674 * { 675 * printf("Found member %p\n", my_data); 676 * } 677 * @endcode 678 * 679 * @warning @p list must be a pointer to the first element of the list. 680 */ 681 EAPI void *eina_list_data_find(const Eina_List *list, const void *data) EINA_PURE EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 682 683 684 /** 685 * @brief Finds a member of a list and returns it as a list node. 686 * 687 * @param[in] list The list to search for data. 688 * @param[in] data The data pointer to find in the list. 689 * @return A list node containing the data member on success, @c NULL 690 * otherwise. 691 * 692 * This function searches @p list from beginning to end for the 693 * first member whose data pointer is @p data. If it is found, the 694 * list node containing the specified member is returned, otherwise 695 * @c NULL is returned. 696 * 697 * @warning @p list must be a pointer to the first element of the list. 698 */ 699 EAPI Eina_List *eina_list_data_find_list(const Eina_List *list, const void *data) EINA_PURE EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 700 701 702 /** 703 * @brief Moves a data pointer from one list to another. 704 * 705 * @param[in,out] to The list to move the data to. 706 * @param[in,out] from The list to move from. 707 * @param[in] data The data member to move. 708 * @return #EINA_TRUE on success, #EINA_FALSE otherwise. 709 * 710 * This function is a shortcut for doing the following: 711 * to = eina_list_append(to, data); 712 * from = eina_list_remove(from, data); 713 * 714 * @warning @p list must be a pointer to the first element of the list. 715 */ 716 EAPI Eina_Bool eina_list_move(Eina_List **to, Eina_List **from, void *data); 717 718 719 /** 720 * @brief Moves a list node from one list to another. 721 * 722 * @param[in,out] to The list to move the data to. 723 * @param[in,out] from The list to move from. 724 * @param[in] data The list node containing the data to move. 725 * @return #EINA_TRUE on success, #EINA_FALSE otherwise. 726 * 727 * This function is a shortcut for doing the following: 728 * to = eina_list_append(to, data->data); 729 * from = eina_list_remove_list(from, data); 730 * 731 * @warning @p list must be a pointer to the first element of the list. 732 */ 733 EAPI Eina_Bool eina_list_move_list(Eina_List **to, Eina_List **from, Eina_List *data); 734 735 736 /** 737 * @brief Frees an entire list and all the nodes, ignoring the data contained. 738 739 * @param[in,out] list The list to free. 740 * @return A @c NULL pointer. 741 * 742 * This function frees all the nodes of @p list. It does not free the 743 * data of the nodes. To free them, use #EINA_LIST_FREE. 744 */ 745 EAPI Eina_List *eina_list_free(Eina_List *list); 746 747 /** 748 * @brief Gets the nth member's data pointer in a list, or @c NULL on 749 * error. 750 * 751 * @param[in] list The list to get the specified member number from. 752 * @param[in] n The number of the element (0 being the first). 753 * @return The data pointer stored in the specified element. 754 * 755 * This function returns the data pointer of element number @p n, in 756 * the @p list. The first element in the array is element number 0. If 757 * the element number @p n does not exist, @c NULL is 758 * returned. Otherwise, the data of the found element is returned. 759 * 760 * @note Worst case is O(n). 761 * 762 * @warning @p list must be a pointer to the first element of the list. 763 */ 764 EAPI void *eina_list_nth(const Eina_List *list, unsigned int n) EINA_PURE EINA_WARN_UNUSED_RESULT; 765 766 /** 767 * @brief Gets the nth member's list node in a list. 768 * 769 * @param[in] list The list to get the specified member number from. 770 * @param[in] n The number of the element (0 being the first). 771 * @return The list node stored in the numbered element, or @c NULL on 772 * error. 773 * 774 * This function returns the list node of element number @p n, in 775 * @p list. The first element in the array is element number 0. If the 776 * element number @p n does not exist or @p list is @c NULL or @p n is 777 * greater than the count of elements in @p list minus 1, @c NULL is 778 * returned. Otherwise the list node stored in the numbered element is 779 * returned. 780 * 781 * @note Worst case is O(n). 782 * 783 * @warning @p list must be a pointer to the first element of the list. 784 */ 785 EAPI Eina_List *eina_list_nth_list(const Eina_List *list, unsigned int n) EINA_PURE EINA_WARN_UNUSED_RESULT; 786 787 788 /** 789 * @brief Reverses all the elements in the list. 790 * 791 * @param[in,out] list The list to reverse. 792 * @return The list head after it has been reversed, or @c NULL on 793 * error. 794 * 795 * This function reverses the order of all elements in @p list, so the 796 * last member is now first, and so on. If @p list is @c NULL, this 797 * function returns @c NULL. 798 * 799 * @note @b in-place: this will change the given list, so you should 800 * now point to the new list head that is returned by this function. 801 * 802 * @warning @p list must be a pointer to the first element of the list. 803 * 804 * @see eina_list_reverse_clone() 805 * @see eina_list_iterator_reversed_new() 806 */ 807 EAPI Eina_List *eina_list_reverse(Eina_List *list) EINA_WARN_UNUSED_RESULT; 808 809 810 /** 811 * @brief Clones (copies) all the elements in the list in reverse order. 812 * 813 * @param[in] list The list to reverse. 814 * @return The new list that has been reversed, or @c NULL on error. 815 * 816 * This function reverses the order of all elements in @p list, so the 817 * last member is now first, and so on. If @p list is @c NULL, this 818 * function returns @c NULL. This returns a copy of the given list. 819 * 820 * @note @b copy: this will copy the list and you should then 821 * eina_list_free() when it is not required anymore. 822 * 823 * @warning @p list must be a pointer to the first element of the list. 824 * 825 * @see eina_list_reverse() 826 * @see eina_list_clone() 827 */ 828 EAPI Eina_List *eina_list_reverse_clone(const Eina_List *list) EINA_WARN_UNUSED_RESULT; 829 830 831 /** 832 * @brief Clones (copies) all the elements in the list in exactly same order. 833 * 834 * @param[in] list The list to clone. 835 * @return The new list that has been cloned, or @c NULL on error. 836 * 837 * This function clone in order of all elements in @p list. If @p list 838 * is @c NULL, this function returns @c NULL. This returns a copy of 839 * the given list. 840 * 841 * @note @b copy: this will copy the list and you should then 842 * eina_list_free() when it is not required anymore. 843 * 844 * @warning @p list must be a pointer to the first element of the list. 845 * 846 * @see eina_list_reverse_clone() 847 */ 848 EAPI Eina_List *eina_list_clone(const Eina_List *list) EINA_WARN_UNUSED_RESULT; 849 850 851 /** 852 * @brief Sorts a list according to the ordering func will return. 853 * 854 * @param[in] list The list handle to sort. 855 * @param[in] limit The maximum number of list elements to sort. 856 * @param[in] func A function pointer that can handle comparing the list data 857 * nodes. 858 * @return The new head of list. 859 * 860 * This function sorts @p list. If @p limit is 0 or greater than the number of 861 * elements in @p list, all the elements are sorted. @p func is used to 862 * compare two elements of @p list. If @p func is @c NULL, this function returns 863 * @p list. 864 * 865 * @note @b in-place: this will change the given list, so you should 866 * now point to the new list head that is returned by this function. 867 * 868 * @note Worst case is O(n * log2(n)) comparisons (calls to func()). 869 * That means that for 1,000,000 list sort will do 20,000,000 comparisons. 870 * 871 * Example: 872 * @code 873 * int 874 * sort_cb(const void *d1, const void *d2) 875 * { 876 * const char *txt = d1; 877 * const char *txt2 = d2; 878 * 879 * if(!txt) return(1); 880 * if(!txt2) return(-1); 881 * 882 * return(strcmp(txt, txt2)); 883 * } 884 * extern Eina_List *list; 885 * 886 * list = eina_list_sort(list, eina_list_count(list), sort_cb); 887 * @endcode 888 * 889 * @warning @p list must be a pointer to the first element of the list. 890 */ 891 EAPI Eina_List *eina_list_sort(Eina_List *list, unsigned int limit, Eina_Compare_Cb func) EINA_ARG_NONNULL(3) EINA_WARN_UNUSED_RESULT; 892 893 894 /** 895 * @brief Shuffles list. 896 * 897 * @param[in] list The list handle to shuffle. 898 * @param[in] func A function pointer that can return an int between 2 inclusive values 899 * @return The new head of list. 900 * 901 * This function shuffles @p list. 902 * @p func is used to generate random list indexes within the range of 903 * unshuffled list items. If @p func is @c NULL, rand is used. 904 * 905 * @note @b in-place: This will change the given list, so you should 906 * now point to the new list head that is returned by this function. 907 * 908 * @since 1.8 909 * 910 * @warning @p list must be a pointer to the first element of the list. 911 */ 912 EAPI Eina_List *eina_list_shuffle(Eina_List *list, Eina_Random_Cb func) EINA_WARN_UNUSED_RESULT; 913 914 915 /** 916 * @brief Merges two list. 917 * 918 * @param[in] left Head list to merge. 919 * @param[in] right Tail list to merge. 920 * @return A new merged list. 921 * 922 * This function puts right at the end of left and returns the head. 923 * 924 * Both left and right do not exist anymore after the merge. 925 * 926 * @note Merge cost is O(n), being @b n the size of the smallest 927 * list. This is due the need to fix accounting of that segment, 928 * making count and last access O(1). 929 * 930 * @warning @p list must be a pointer to the first element of the list. 931 */ 932 EAPI Eina_List *eina_list_merge(Eina_List *left, Eina_List *right) EINA_WARN_UNUSED_RESULT; 933 934 935 /** 936 * @brief Merges two sorted list according to the ordering func will return. 937 * 938 * @param[in] left First list to merge. 939 * @param[in] right Second list to merge. 940 * @param[in] func A function pointer that can handle comparing the list data 941 * nodes. 942 * @return A new sorted list. 943 * 944 * This function compares the head of @p left and @p right, and choose the 945 * smallest one to be head of the returned list. It will continue this process 946 * for all entry of both list. 947 * 948 * Both left and right lists are not valid anymore after the merge and should 949 * not be used. If @p func is @c NULL, it will return @c NULL. 950 * 951 * Example: 952 * @code 953 * int 954 * sort_cb(void *d1, void *d2) 955 * { 956 * const char *txt = NULL; 957 * const char *txt2 = NULL; 958 * 959 * if(!d1) return(1); 960 * if(!d2) return(-1); 961 * 962 * return(strcmp((const char*)d1, (const char*)d2)); 963 * } 964 * extern Eina_List *sorted1; 965 * extern Eina_List *sorted2; 966 * 967 * list = eina_list_sorted_merge(sorted1, sorted2, sort_cb); 968 * @endcode 969 * 970 * @warning @p list must be a pointer to the first element of the list. 971 */ 972 EAPI Eina_List *eina_list_sorted_merge(Eina_List *left, Eina_List *right, Eina_Compare_Cb func) EINA_ARG_NONNULL(3) EINA_WARN_UNUSED_RESULT; 973 974 975 /** 976 * @brief Splits a list into 2 lists. 977 * 978 * @param[in] list List to split. 979 * @param[in] relative The list will be split after @p relative. 980 * @param[out] right The head of the new right list. 981 * @return The new left list 982 * 983 * This function splits @p list into two lists ( left and right ) after the node @p relative. @p Relative 984 * will become the last node of the left list. If @p list or @p right are @c NULL list is returns. 985 * If @p relative is NULL right is set to @p list and @c NULL is returns. 986 * If @p relative is the last node of @p list list is returns and @p right is set to @c NULL. 987 * 988 * list does not exist anymore after the split. 989 * 990 * @warning @p list must be a pointer to the first element of the list. 991 */ 992 EAPI Eina_List *eina_list_split_list(Eina_List *list, Eina_List *relative, Eina_List **right) EINA_WARN_UNUSED_RESULT; 993 994 995 /** 996 * @brief Returns node nearest to data from the sorted list. 997 * 998 * @param[in] list The list to search for data, @b must be sorted. 999 * @param[in] func A function pointer that can handle comparing the list data nodes. 1000 * @param[in] data reference value to search. 1001 * @param[out] result_cmp If provided returns the result of 1002 * func(node->data, data) node being the last (returned) node. If node 1003 * was found (exact match), then it is 0. If returned node is smaller 1004 * than requested data, it is less than 0 and if it's bigger it's 1005 * greater than 0. It is the last value returned by func(). 1006 * @return The nearest node, @c NULL if not found. 1007 * 1008 * This function searches for a node containing @p data as its data in @p list, 1009 * if such a node exists it will be returned and @p result_cmp will be @p 0. If 1010 * the data of no node in @p list is equal to @p data, the node with the nearest 1011 * value to that will be returned and @p result_cmp will be the return value of 1012 * @p func with @p data and the returned node's data as arguments. 1013 * 1014 * This function is useful for inserting an element in the list only in case it 1015 * isn't already present in the list, the naive way of doing this would be: 1016 * @code 1017 * void *ptr = eina_list_data_find(list, "my data"); 1018 * if (!ptr) 1019 * eina_list_sorted_insert(list, "my data"); 1020 * @endcode 1021 * 1022 * However this has the downside of walking through the list twice, once to 1023 * check if the data is already present and another to insert the element in the 1024 * correct position. This can be done more efficiently: 1025 * @code 1026 * int cmp_result; 1027 * l = eina_list_search_sorted_near_list(list, cmp_func, "my data", 1028 * &cmp_result); 1029 * if (cmp_result > 0) 1030 * list = eina_list_prepend_relative_list(list, "my data", l); 1031 * else if (cmp_result < 0) 1032 * list = eina_list_append_relative_list(list, "my data", l); 1033 * @endcode 1034 * 1035 * If @a cmp_result is 0 the element is already in the list and we need not 1036 * insert it, if @a cmp_result is greater than zero @a "my @a data" needs to 1037 * come after @a l (the nearest node present), if less than zero before. 1038 * 1039 * @note O(log2(n)) average/worst case performance, for 1,000,000 1040 * elements it will do a maximum of 20 comparisons. This is much 1041 * faster than the 1,000,000 comparisons made naively walking the list 1042 * from head to tail, so depending on the number of searches and 1043 * insertions, it may be worth to eina_list_sort() the list and do the 1044 * searches later. As lists do not have O(1) access time, walking to 1045 * the correct node can be costly, consider worst case to be almost 1046 * O(n) pointer dereference (list walk). 1047 * 1048 * @warning @p list must be a pointer to the first element of the list. 1049 * 1050 * @see eina_list_search_sorted_list() 1051 * @see eina_list_sort() 1052 * @see eina_list_sorted_merge() 1053 */ 1054 EAPI Eina_List *eina_list_search_sorted_near_list(const Eina_List *list, Eina_Compare_Cb func, const void *data, int *result_cmp); 1055 1056 1057 /** 1058 * @brief Returns node if data is in the sorted list. 1059 * 1060 * @param[in] list The list to search for data, @b must be sorted. 1061 * @param[in] func A function pointer that can handle comparing the list data nodes. 1062 * @param[in] data reference value to search. 1063 * @return The node if func(node->data, data) == 0, @c NULL if not found. 1064 * 1065 * This can be used to check if some value is inside the list and get 1066 * the container node in this case. It should be used when list is 1067 * known to be sorted as it will do binary search for results. 1068 * 1069 * Example: imagine user gives a string, you check if it's in the list 1070 * before duplicating its contents. 1071 * 1072 * @note O(log2(n)) average/worst case performance, for 1,000,000 1073 * elements it will do a maximum of 20 comparisons. This is much 1074 * faster than the 1,000,000 comparisons made by 1075 * eina_list_search_unsorted_list(), so depending on the number of 1076 * searches and insertions, it may be worth to eina_list_sort() the 1077 * list and do the searches later. As said in 1078 * eina_list_search_sorted_near_list(), lists do not have O(1) access 1079 * time, so walking to the correct node can be costly, consider worst 1080 * case to be almost O(n) pointer dereference (list walk). 1081 * 1082 * @warning @p list must be a pointer to the first element of the list. 1083 * 1084 * @see eina_list_search_sorted() 1085 * @see eina_list_sort() 1086 * @see eina_list_sorted_merge() 1087 * @see eina_list_search_unsorted_list() 1088 * @see eina_list_search_sorted_near_list() 1089 */ 1090 EAPI Eina_List *eina_list_search_sorted_list(const Eina_List *list, Eina_Compare_Cb func, const void *data); 1091 1092 1093 /** 1094 * @brief Returns node data if it is in the sorted list. 1095 * 1096 * @param[in] list The list to search for data, @b must be sorted. 1097 * @param[in] func A function pointer that can handle comparing the list data nodes. 1098 * @param[in] data reference value to search. 1099 * @return The node value (@c node->data) if func(node->data, data) == 0, 1100 * @c NULL if not found. 1101 * 1102 * This can be used to check if some value is inside the list and get 1103 * the existing instance in this case. It should be used when list is 1104 * known to be sorted as it will do binary search for results. 1105 * 1106 * Example: imagine user gives a string, you check if it's in the list 1107 * before duplicating its contents. 1108 * 1109 * @note O(log2(n)) average/worst case performance, for 1,000,000 1110 * elements it will do a maximum of 20 comparisons. This is much 1111 * faster than the 1,000,000 comparisons made by 1112 * eina_list_search_unsorted(), so depending on the number of 1113 * searches and insertions, it may be worth to eina_list_sort() the 1114 * list and do the searches later. As said in 1115 * eina_list_search_sorted_near_list(), lists do not have O(1) access 1116 * time, so walking to the correct node can be costly, consider worst 1117 * case to be almost O(n) pointer dereference (list walk). 1118 * 1119 * @warning @p list must be a pointer to the first element of the list. 1120 * 1121 * @see eina_list_search_sorted_list() 1122 * @see eina_list_sort() 1123 * @see eina_list_sorted_merge() 1124 * @see eina_list_search_unsorted_list() 1125 */ 1126 EAPI void *eina_list_search_sorted(const Eina_List *list, Eina_Compare_Cb func, const void *data); 1127 1128 1129 /** 1130 * @brief Returns node if data is in the unsorted list. 1131 * 1132 * @param[in] list The list to search for data, may be unsorted. 1133 * @param[in] func A function pointer that can handle comparing the list data nodes. 1134 * @param[in] data reference value to search. 1135 * @return The node if func(node->data, data) == 0, @c NULL if not found. 1136 * 1137 * This can be used to check if some value is inside the list and get 1138 * the container node in this case. 1139 * 1140 * Example: imagine user gives a string, you check if it's in the list 1141 * before duplicating its contents. 1142 * 1143 * @note this is expensive and may walk the whole list, it's order-N, 1144 * that is for 1,000,000 elements list it may walk and compare 1145 * 1,000,000 nodes. 1146 * 1147 * @warning @p list must be a pointer to the first element of the list. 1148 * 1149 * @see eina_list_search_sorted_list() 1150 * @see eina_list_search_unsorted() 1151 */ 1152 EAPI Eina_List *eina_list_search_unsorted_list(const Eina_List *list, Eina_Compare_Cb func, const void *data); 1153 1154 1155 /** 1156 * @brief Returns node data if it is in the unsorted list. 1157 * 1158 * @param[in] list The list to search for data, may be unsorted. 1159 * @param[in] func A function pointer that can handle comparing the list data nodes. 1160 * @param[in] data reference value to search. 1161 * @return The node value (@c node->data) if func(node->data, data) == 0, 1162 * @c NULL if not found. 1163 * 1164 * This can be used to check if some value is inside the list and get 1165 * the existing instance in this case. 1166 * 1167 * Example: imagine user gives a string, you check if it's in the list 1168 * before duplicating its contents. 1169 * 1170 * @note this is expensive and may walk the whole list, it's order-N, 1171 * that is, for 1,000,000 elements list it may walk and compare 1172 * 1,000,000 nodes. 1173 * 1174 * @warning @p list must be a pointer to the first element of the list. 1175 * 1176 * @see eina_list_search_sorted() 1177 * @see eina_list_search_unsorted_list() 1178 */ 1179 EAPI void *eina_list_search_unsorted(const Eina_List *list, Eina_Compare_Cb func, const void *data); 1180 1181 1182 /** 1183 * @brief Gets the last list node in the list. 1184 * 1185 * @param[in] list The list to get the last list node from. 1186 * @return The last list node in the list. 1187 * 1188 * This function returns the last list node in the list @p list. If 1189 * @p list is @c NULL or empty, @c NULL is returned. 1190 * 1191 * This is a order-1 operation (it takes the same short time 1192 * regardless of the length of the list). 1193 * 1194 * @warning @p list must be a pointer to the first element of the list. 1195 */ 1196 static inline Eina_List *eina_list_last(const Eina_List *list) EINA_PURE EINA_WARN_UNUSED_RESULT; 1197 1198 1199 /** 1200 * @brief Gets the next list node after the specified list node. 1201 * 1202 * @param[in] list The list node to get the next list node from 1203 * @return The next list node on success, @c NULL otherwise. 1204 * 1205 * This function returns the next list node after the current one in 1206 * @p list. It is equivalent to list->next. If @p list is @c NULL or 1207 * if no next list node exists, it returns @c NULL. 1208 * 1209 * @warning @p list must be a pointer to the first element of the list. 1210 */ 1211 static inline Eina_List *eina_list_next(const Eina_List *list) EINA_PURE EINA_WARN_UNUSED_RESULT; 1212 1213 1214 /** 1215 * @brief Gets the list node prior to the specified list node. 1216 * 1217 * @param[in] list The list node to get the previous list node from. 1218 * @return The previous list node on success, @c NULL otherwise. 1219 * 1220 * This function returns the previous list node before the current one 1221 * in @p list. It is equivalent to list->prev. If @p list is @c NULL or 1222 * if no previous list node exists, it returns @c NULL. 1223 * 1224 * @warning @p list must be a pointer to the first element of the list. 1225 */ 1226 static inline Eina_List *eina_list_prev(const Eina_List *list) EINA_PURE EINA_WARN_UNUSED_RESULT; 1227 1228 1229 /** 1230 * @brief Gets the list node data member. 1231 * 1232 * @param[in] list The list node to get the data member of. 1233 * @return The data member from the list node. 1234 * 1235 * This function returns the data member of the specified list node @p 1236 * list. It is equivalent to list->data. If @p list is @c NULL, this 1237 * function returns @c NULL. 1238 * 1239 * @warning @p list must be a pointer to the first element of the list. 1240 */ 1241 static inline void *eina_list_data_get(const Eina_List *list) EINA_PURE EINA_WARN_UNUSED_RESULT; 1242 1243 1244 /** 1245 * @brief Sets the list node data member. 1246 * 1247 * @param[in,out] list The list node to set the data member of. 1248 * @param[in] data The data to be set. 1249 * @return The previous data value. 1250 * 1251 * This function sets the data member @p data of the specified list node 1252 * @p list. It returns the previous data of the node. If @p list is 1253 * @c NULL, this function returns @c NULL. 1254 * 1255 * @warning @p list must be a pointer to the first element of the list. 1256 */ 1257 static inline void *eina_list_data_set(Eina_List *list, const void *data); 1258 1259 1260 /** 1261 * @brief Gets the count of the number of items in a list. 1262 * 1263 * @param[in] list The list whose count to return. 1264 * @return The number of members in the list. 1265 * 1266 * This function returns the quantity of members that @p list 1267 * contains. If the list is @c NULL, @c 0 is returned. 1268 * 1269 * NB: This is an order-1 operation and takes the same time regardless 1270 * of the length of the list. 1271 * 1272 * @warning @p list must be a pointer to the first element of the list. 1273 */ 1274 static inline unsigned int eina_list_count(const Eina_List *list) EINA_PURE; 1275 1276 1277 /** 1278 * @brief Returns the last list node's data. 1279 * 1280 * @param[in] list The list. 1281 * @return The node's data, or @c NULL on being passed a @c NULL pointer 1282 * 1283 * This function is a shortcut for typing eina_list_data_get(eina_list_last()) 1284 * @since 1.8 1285 */ 1286 static inline void *eina_list_last_data_get(const Eina_List *list); 1287 1288 1289 /** 1290 * @brief Returns a new iterator associated with a list. 1291 * 1292 * @param[in] list The list. 1293 * @return A new iterator, or @c NULL on memory allocation failure. 1294 * 1295 * This function returns a newly allocated iterator associated with @p 1296 * list. If @p list is @c NULL or the count member of @p list is less than 1297 * or equal to 0, this function still returns a valid iterator that 1298 * will always return false on eina_iterator_next(), thus keeping API 1299 * sane. 1300 * 1301 * @warning @p list must be a pointer to the first element of the list. 1302 * 1303 * @warning if the list structure changes then the iterator becomes 1304 * invalid! That is, if you add or remove nodes this iterator 1305 * behavior is undefined and your program may crash! 1306 */ 1307 EAPI Eina_Iterator *eina_list_iterator_new(const Eina_List *list) EINA_MALLOC EINA_WARN_UNUSED_RESULT; 1308 1309 1310 /** 1311 * @brief Returns a new reversed iterator associated with a list. 1312 * 1313 * @param[in] list The list. 1314 * @return A new iterator, or @c NULL on memory allocation failure. 1315 * 1316 * This function returns a newly allocated iterator associated with @p 1317 * list. If @p list is @c NULL or the count member of @p list is less than 1318 * or equal to 0, this function still returns a valid iterator that 1319 * will always return false on eina_iterator_next(), thus keeping API 1320 * sane. 1321 * 1322 * Unlike eina_list_iterator_new(), this will walk the list backwards. 1323 * 1324 * @warning @p list must be a pointer to the first element of the list. 1325 * 1326 * @warning if the list structure changes then the iterator becomes 1327 * invalid! That is, if you add or remove nodes this iterator 1328 * behavior is undefined and your program may crash! 1329 */ 1330 EAPI Eina_Iterator *eina_list_iterator_reversed_new(const Eina_List *list) EINA_MALLOC EINA_WARN_UNUSED_RESULT; 1331 1332 1333 /** 1334 * @brief Returns a new accessor associated with a list. 1335 * 1336 * @param[in] list The list. 1337 * @return A new accessor, or @c NULL on error. 1338 * 1339 * This function returns a newly allocated accessor associated with 1340 * @p list. If @p list is @c NULL or the count member of @p list is 1341 * less or equal than 0, this function returns @c NULL. If the memory can 1342 * not be allocated, @c NULL is returned; otherwise, a valid accessor is 1343 * returned. 1344 * 1345 * @warning @p list must be a pointer to the first element of the list. 1346 */ 1347 EAPI Eina_Accessor *eina_list_accessor_new(const Eina_List *list) EINA_MALLOC EINA_WARN_UNUSED_RESULT; 1348 1349 1350 /** 1351 * @brief Finds the member of the list and returns the index. 1352 * 1353 * @param[in] list The list. 1354 * @param[in] data The data member. 1355 * @return The index of data member if found, @c -1 otherwise. 1356 * 1357 * This function searches in @p list from beginning to end for the 1358 * first member whose data pointer is @p data. If it is found, the 1359 * index of the data will be returned, otherwise @c -1 will be returned. 1360 * 1361 * @warning @p list must be a pointer to the first element of the list. 1362 * 1363 * @since 1.14 1364 */ 1365 EAPI int eina_list_data_idx(const Eina_List *list, void *data); 1366 1367 1368 /** 1369 * @def EINA_LIST_FOREACH 1370 * @brief Definition for the macro to iterate over a list. 1371 * 1372 * @param[in] list The list to iterate over. 1373 * @param[out] l A list that is used as an iterator and points to the current node. 1374 * @param[out] _data Current item's data. 1375 * 1376 * This macro iterates over @p list from the first element to 1377 * the last. @p data is the data related to the current element. 1378 * @p l is an #Eina_List used as the list iterator. 1379 * 1380 * The following diagram illustrates this macro iterating over a list of four 1381 * elements("one", "two", "three" and "four"): 1382 * @image latex eina-list-foreach.eps "" width=\textwidth 1383 * @image html eina-list-foreach.png 1384 * 1385 * It can be used to free list data, as in the following example: 1386 * 1387 * @code 1388 * Eina_List *list; 1389 * Eina_List *l; 1390 * char *data; 1391 * 1392 * // list is already filled, 1393 * // its elements are just duplicated strings, 1394 * // EINA_LIST_FOREACH will be used to free those strings 1395 * 1396 * EINA_LIST_FOREACH(list, l, data) 1397 * free(data); 1398 * eina_list_free(list); 1399 * @endcode 1400 * 1401 * @note This is not the optimal way to release memory allocated to 1402 * a list, since it iterates over the list twice. 1403 * For an optimized algorithm, use EINA_LIST_FREE(). 1404 * 1405 * @warning @p list must be a pointer to the first element of the list. 1406 * 1407 * @warning Be careful when deleting list nodes. 1408 * If you remove the current node and continue iterating, 1409 * the code will fail because the macro will not be able 1410 * to get the next node. Notice that it's OK to remove any 1411 * node if you stop the loop after that. 1412 * For destructive operations such as this, consider 1413 * using EINA_LIST_FOREACH_SAFE(). 1414 */ 1415 #define EINA_LIST_FOREACH(list, l, _data)\ 1416 for (l = list, \ 1417 _data = eina_list_data_get(l), \ 1418 l ? (EINA_PREFETCH(((Eina_List *)l)->next), EINA_PREFETCH(_data)) : EINA_PREFETCH(l); \ 1419 \ 1420 l; \ 1421 \ 1422 l = eina_list_next(l), \ 1423 _data = eina_list_data_get(l), \ 1424 l ? (EINA_PREFETCH(((Eina_List *)l)->next), EINA_PREFETCH(_data)) : EINA_PREFETCH(l)) 1425 1426 /** 1427 * @def EINA_LIST_REVERSE_FOREACH 1428 * @brief Definition for the macro to iterate over a list in the reverse order. 1429 * 1430 * @param[in] list The list to iterate over. 1431 * @param[out] l A list that is used as an iterator and points to the current node. 1432 * @param[out] _data Current item's data. 1433 * 1434 * This macro works like EINA_LIST_FOREACH, but iterates from the 1435 * last element of a list to the first. 1436 * @p data is the data related to the current element, while @p l 1437 * is an #Eina_List that is used as the list iterator. 1438 * 1439 * The following diagram illustrates this macro iterating over a list of four 1440 * elements("one", "two", "three" and "four"): 1441 * @image latex eina-list-reverse-foreach.eps "" width=\textwidth 1442 * @image html eina-list-reverse-foreach.png 1443 * 1444 * It can be used to free list data, as in the following example: 1445 * 1446 * @code 1447 * Eina_List *list; 1448 * Eina_List *l; 1449 * char *data; 1450 * 1451 * // list is already filled, 1452 * // its elements are just duplicated strings, 1453 * // EINA_LIST_REVERSE_FOREACH will be used to free those strings 1454 * 1455 * EINA_LIST_REVERSE_FOREACH(list, l, data) 1456 * free(data); 1457 * eina_list_free(list); 1458 * @endcode 1459 * 1460 * @note This is not the optimal way to release memory allocated to 1461 * a list, since it iterates over the list twice. 1462 * For an optimized algorithm, use EINA_LIST_FREE(). 1463 * 1464 * @warning @p list must be a pointer to the first element of the list. 1465 * 1466 * @warning Be careful when deleting list nodes. 1467 * If you remove the current node and continue iterating, 1468 * the code will fail because the macro will not be able 1469 * to get the next node. Notice that it's OK to remove any 1470 * node if you stop the loop after that. 1471 * For destructive operations such as this, consider 1472 * using EINA_LIST_REVERSE_FOREACH_SAFE(). 1473 */ 1474 #define EINA_LIST_REVERSE_FOREACH(list, l, _data)\ 1475 for (l = eina_list_last(list), \ 1476 _data = eina_list_data_get(l), \ 1477 l ? (EINA_PREFETCH(((Eina_List *)l)->prev), EINA_PREFETCH(_data)) : EINA_PREFETCH(l); \ 1478 l; \ 1479 l = eina_list_prev(l), \ 1480 _data = eina_list_data_get(l), \ 1481 l ? (EINA_PREFETCH(((Eina_List *)l)->prev), EINA_PREFETCH(_data)) : EINA_PREFETCH(l)) 1482 1483 /** 1484 * @def EINA_LIST_FOREACH_SAFE 1485 * @brief Definition for the macro to iterate over a list with support for node deletion. 1486 * 1487 * @param[in] list The list to iterate over. 1488 * @param[out] l A list that is used as an iterator and points to the current node. 1489 * @param[out] l_next A list that is used as an iterator and points to the next node. 1490 * @param[out] data Current item's data. 1491 * 1492 * This macro iterates over @p list from the first element to 1493 * the last. @p data is the data related to the current element. 1494 * @p l is an #Eina_List used as the list iterator. 1495 * 1496 * Since this macro stores a pointer to the next list node in @p l_next, 1497 * deleting the current node and continuing looping is safe. 1498 * 1499 * The following diagram illustrates this macro iterating over a list of four 1500 * elements ("one", "two", "three" and "four"): 1501 * @image latex eina-list-foreach-safe.eps "" width=\textwidth 1502 * @image html eina-list-foreach-safe.png 1503 * 1504 * This macro can be used to free list nodes, as in the following example: 1505 * 1506 * @code 1507 * Eina_List *list; 1508 * Eina_List *l; 1509 * Eina_List *l_next; 1510 * char *data; 1511 * 1512 * // list is already filled, 1513 * // its elements are just duplicated strings, 1514 * // EINA_LIST_FOREACH_SAFE will be used to free elements that match "key". 1515 * 1516 * EINA_LIST_FOREACH_SAFE(list, l, l_next, data) 1517 * if (strcmp(data, "key") == 0) 1518 * { 1519 * free(data); 1520 * list = eina_list_remove_list(list, l); 1521 * } 1522 * @endcode 1523 * 1524 * @warning @p list must be a pointer to the first element of the list. 1525 */ 1526 #define EINA_LIST_FOREACH_SAFE(list, l, l_next, data) \ 1527 for (l = list, \ 1528 l_next = eina_list_next(l), \ 1529 EINA_PREFETCH(l_next), \ 1530 data = eina_list_data_get(l); \ 1531 EINA_PREFETCH(data), \ 1532 l; \ 1533 l = l_next, \ 1534 l_next = eina_list_next(l), \ 1535 EINA_PREFETCH(l_next), \ 1536 data = eina_list_data_get(l), \ 1537 EINA_PREFETCH(data)) 1538 1539 /** 1540 * @def EINA_LIST_REVERSE_FOREACH_SAFE 1541 * @brief Definition for the macro to iterate over a list in the reverse order with support 1542 * for deletion. 1543 * 1544 * @param[in] list The list to iterate over. 1545 * @param[out] l A list that is used as an iterator and points to the current node. 1546 * @param[out] l_prev A list that is used as an iterator and points to the previous node. 1547 * @param[out] data Current item's data. 1548 * 1549 * This macro works like EINA_LIST_FOREACH_SAFE, but iterates from the 1550 * last element of a list to the first. 1551 * @p data is the data related to the current element, while @p l 1552 * is an #Eina_List that is used as the list iterator. 1553 * 1554 * Since this macro stores a pointer to the previous list node in @p l_prev, 1555 * deleting the current node and continuing looping is safe. 1556 * 1557 * The following diagram illustrates this macro iterating over a list of four 1558 * elements ("one", "two", "three" and "four"): 1559 * @image latex eina-list-reverse-foreach-safe.eps "" width=\textwidth 1560 * @image html eina-list-reverse-foreach-safe.png 1561 * 1562 * This macro can be used to free list nodes, as in the following example: 1563 * 1564 * @code 1565 * Eina_List *list; 1566 * Eina_List *l; 1567 * Eina_List *l_prev; 1568 * char *data; 1569 * 1570 * // list is already filled, 1571 * // its elements are just duplicated strings, 1572 * // EINA_LIST_REVERSE_FOREACH_SAFE will be used to free elements that match "key". 1573 * 1574 * EINA_LIST_REVERSE_FOREACH_SAFE(list, l, l_prev, data) 1575 * if (strcmp(data, "key") == 0) 1576 * { 1577 * free(data); 1578 * list = eina_list_remove_list(list, l); 1579 * } 1580 * @endcode 1581 * 1582 * @warning @p list must be a pointer to the first element of the list. 1583 */ 1584 #define EINA_LIST_REVERSE_FOREACH_SAFE(list, l, l_prev, data) \ 1585 for (l = eina_list_last(list), \ 1586 l_prev = eina_list_prev(l), \ 1587 EINA_PREFETCH(l_prev), \ 1588 data = eina_list_data_get(l); \ 1589 EINA_PREFETCH(data), \ 1590 l; \ 1591 l = l_prev, \ 1592 l_prev = eina_list_prev(l), \ 1593 EINA_PREFETCH(l_prev), \ 1594 data = eina_list_data_get(l), \ 1595 EINA_PREFETCH(data)) 1596 1597 /** 1598 * @def EINA_LIST_FREE 1599 * @brief Definition for the macro to remove each list node while having access to each node's data. 1600 * 1601 * @param[in,out] list The list that will be cleared. 1602 * @param[out] data Current node's data. 1603 * 1604 * This macro will call #eina_list_remove_list for each list node, and store 1605 * the data contained in the current node in @p data. 1606 * 1607 * The following diagram illustrates this macro iterating over a list of four 1608 * elements ("one", "two", "three" and "four"): 1609 * @image latex eina-list-free.eps "" width=\textwidth 1610 * @image html eina-list-free.png 1611 * 1612 * If you do not need to release node data, it is easier to call #eina_list_free(). 1613 * 1614 * @code 1615 * Eina_List *list; 1616 * char *data; 1617 * 1618 * // list is already filled, 1619 * // its elements are just duplicated strings, 1620 * 1621 * EINA_LIST_FREE(list, data) 1622 * free(data); 1623 * @endcode 1624 * 1625 * @warning @p list must be a pointer to the first element of the list. 1626 * 1627 * @see eina_list_free() 1628 */ 1629 #define EINA_LIST_FREE(list, data) \ 1630 for (data = eina_list_data_get(list), \ 1631 list ? EINA_PREFETCH(((Eina_List *)list)->next) : EINA_PREFETCH(list); \ 1632 list; \ 1633 list = eina_list_remove_list(list, list), \ 1634 list ? EINA_PREFETCH(((Eina_List *)list)->next) : EINA_PREFETCH(list), \ 1635 data = eina_list_data_get(list)) 1636 1637 #include "eina_inline_list.x" 1638 1639 /** 1640 * @} 1641 */ 1642 1643 /** 1644 * @} 1645 */ 1646 1647 /** 1648 * @} 1649 */ 1650 1651 #endif /* EINA_LIST_H_ */ 1652