1 /* EINA - EFL data type library 2 * Copyright (C) 2002-2008 Carsten Haitzler, Vincent Torri 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_INLIST_H_ 20 #define EINA_INLIST_H_ 21 22 #include "eina_types.h" 23 #include "eina_iterator.h" 24 #include "eina_accessor.h" 25 #include <stddef.h> 26 27 /** 28 * @page eina_inlist_01_example_page Eina_Inlist basic usage 29 * @dontinclude eina_inlist_01.c 30 * 31 * To see the full source for this example, click here: @ref 32 * eina_inlist_01_c 33 * 34 * As explained before, inline lists mean its nodes pointers are part of same 35 * memory block/blob. This is done by using the macro @ref EINA_INLIST inside the 36 * data structure that will be used: 37 * 38 * @skip struct 39 * @until }; 40 * 41 * The resulting node representing this struct can be exemplified by the 42 * following picture: 43 * 44 * @image html eina_inlist-node_eg1-my-struct.png 45 * @image rtf eina_inlist-node_eg1-my-struct.png 46 * @image latex eina_inlist-node_eg1-my-struct.eps 47 * 48 * Let's define a comparison function that will be used later during the 49 * sorting of the list: 50 * 51 * @skip int 52 * @until } 53 * 54 * The @ref Eina_Inlist can be used exactly the same way as @ref Eina_List when 55 * appending, prepending and removing items. But since we already have the node 56 * pointers inside the structure, they need to be retrieved with the macro @ref 57 * EINA_INLIST_GET : 58 * 59 * @skip malloc 60 * @until append 61 * 62 * Notice that @ref eina_inlist_append always receives the head of the list as 63 * first argument, and its return value should be used as the list pointer 64 * (head): 65 * 66 * @skip malloc 67 * @until append 68 * 69 * After appending 3 items, the list now should look similar to this: 70 * 71 * @image html eina_inlist-node_eg1-inlist.png 72 * @image rtf eina_inlist-node_eg1-inlist.png 73 * @image latex eina_inlist-node_eg1-inlist.eps "" width=\textwidth 74 * 75 * The macro @ref EINA_INLIST_FOREACH can be used to iterate over the list: 76 * 77 * @skip printf 78 * @until cur->a 79 * 80 * @ref eina_inlist_promote(), @ref eina_inlist_demote(), @ref 81 * eina_inlist_append_relative() and similar functions all work in the same way 82 * as the @ref Eina_List : 83 * 84 * @skip eina_inlist_promote 85 * @until eina_inlist_demote 86 * 87 * Now let's use the @c sort_cb function declared above to sort our list: 88 * 89 * @skipline eina_inlist_sort 90 * 91 * Removing an element from the inlist is also similar to @ref Eina_List : 92 * 93 * @skip inlist_remove 94 * @until free 95 * 96 * Another way of walking through the inlist. 97 * 98 * @skip for 99 * @until } 100 * 101 * Notice that in the previous piece of code, since we only have the pointers to 102 * the inlist nodes, we have to use the @ref EINA_INLIST_CONTAINER_GET macro 103 * that will return the pointer to the entire structure. Of course, in this case 104 * it is the same as the list pointer, since the @ref EINA_INLIST macro was used 105 * in the beginning of the structure. 106 * 107 * Now to finish this example, lets delete this list: 108 * 109 * @skip while 110 * @until } 111 * @example eina_inlist_01.c 112 */ 113 114 /** 115 * @page eina_inlist_02_example_page Eina_Inlist advanced usage - lists and inlists 116 * @dontinclude eina_inlist_02.c 117 * 118 * This example describes the usage of @ref Eina_Inlist mixed with @ref 119 * Eina_List . We create and add elements to an inlist, and the even members 120 * are also added to a normal list. Later we remove the elements divisible by 3 121 * from this normal list. 122 * 123 * The struct that is going to be used is the same used in @ref 124 * eina_inlist_01_example_page , since we still need the @ref EINA_INLIST macro to 125 * declare the inlist node info: 126 * 127 * @skip struct 128 * @until }; 129 * 130 * The resulting node representing this struct can be exemplified by the 131 * following picture: 132 * 133 * @image html eina_inlist-node_eg2-my-struct.png 134 * @image rtf eina_inlist-node_eg2-my-struct.png 135 * @image latex eina_inlist-node_eg2-my-struct.eps 136 * 137 * Now we need some pointers and auxiliary variables that will help us iterate on 138 * the lists: 139 * 140 * @skip struct 141 * @until l_next; 142 * 143 * Allocating 100 elements and putting them into an inlist, and the even 144 * elements also go to the normal list: 145 * 146 * @skip for 147 * @until } 148 * 149 * After this point, what we have are two distinct lists that share some 150 * elements. The first list (inlist) is defined by the pointers inside the 151 * elements data structure, while the second list (normal list) has its own node 152 * data structure that is kept outside of the elements. 153 * 154 * The two lists, sharing some elements, can be represented by the following 155 * picture: 156 * 157 * @image rtf eina_inlist-node_eg2-list-inlist.png 158 * @image html eina_inlist-node_eg2-list-inlist.png 159 * @image latex eina_inlist-node_eg2-list-inlist.eps "" width=\textwidth 160 * 161 * Accessing both lists is done normally, as if they didn't have any elements in 162 * common: 163 * 164 * @skip printf 165 * @until eina_list_count 166 * 167 * We can remove elements from the normal list, but we just don't free them 168 * because they are still stored in the inlist: 169 * 170 * @skip EINA_LIST_FOREACH_SAFE 171 * @until eina_list_count 172 * 173 * To finish this example, we want to free both lists, we can't just free all 174 * elements on the second list (normal list) because they are still being used 175 * in the inlist. So we first discard the normal list without freeing its 176 * elements, then we free all elements in the inlist (that contains all elements 177 * allocated until now): 178 * 179 * @skip eina_list_free 180 * @until } 181 * 182 * Here is the full source code for this example: @ref eina_inlist_02_c 183 * @example eina_inlist_02.c 184 */ 185 186 /** 187 * @page eina_inlist_03_example_page Eina_Inlist advanced usage - multi-inlists 188 * @dontinclude eina_inlist_03.c 189 * 190 * This example describes the usage of multiple inlists storing the same data. 191 * It means that some data may appear in more than one inlist at the same time. 192 * We will demonstrate this by creating an inlist with 100 numbers, and adding 193 * the odd numbers to the second inlist, then remove the numbers divisible by 3 194 * from the second list. 195 * 196 * To accomplish this, it is necessary to have two inlist pointers in the struct 197 * that is going to be stored. We are using the default inlist member @ref 198 * EINA_INLIST, and adding another member @c even that is of type @ref 199 * Eina_Inlist too: 200 * 201 * @skip struct 202 * @until }; 203 * 204 * The representation for this struct is: 205 * 206 * @image html eina_inlist-node_eg3-my-struct.png 207 * @image rtf eina_inlist-node_eg3-my-struct.png 208 * @image latex eina_inlist-node_eg3-my-struct.eps 209 * 210 * And we will define some convenience macros that are equivalent to @ref 211 * EINA_INLIST_GET and @ref EINA_INLIST_CONTAINER_GET : 212 * 213 * @skip define 214 * @until offsetof 215 * 216 * We need two pointers, one for each list, and a pointer that will be used as 217 * an iterator: 218 * 219 * @skipline Eina_Inlist 220 * 221 * Now we allocate and add to the first list every number from 0 to 99. These 222 * nodes data also have the @ref Eina_Inlist node info for the second list (@c 223 * even). We will use them to add just the even numbers to the second list, the 224 * @c list_even. Also notice that we are using our macro @c EVEN_INLIST_GET to 225 * get the pointer to the even list node info: 226 * 227 * @skip for 228 * @until } 229 * 230 * And the resulting lists will be as follow: 231 * 232 * @image rtf eina_inlist-node_eg3-two-inlists.png 233 * @image html eina_inlist-node_eg3-two-inlists.png 234 * @image latex eina_inlist-node_eg3-two-inlists.eps "" width=\textwidth 235 * 236 * For the first list, we can use the macro @ref EINA_INLIST_FOREACH to iterate 237 * over its elements: 238 * 239 * @skip FOREACH 240 * @until printf 241 * 242 * But for the second list, we have to do it manually. Of course we could create 243 * a similar macro to @ref EINA_INLIST_FOREACH, but since this macro is more 244 * complex than the other two and we are using it only once, it's better to just 245 * do it manually: 246 * 247 * @skip for 248 * @until } 249 * 250 * Let's just check that the two lists have the expected number of elements: 251 * 252 * @skip list count 253 * @until list_even count 254 * 255 * And removing the numbers divisible by 3 only from the second list: 256 * 257 * @skip itr 258 * @until list_even count 259 * 260 * Now that we don't need the two lists anymore, we can just free all the items. 261 * Since all of the allocated data was put into the first list, and both lists 262 * are made of pointers to inside the data structures, we can free only the 263 * first list (that contains all the elements) and the second list will be gone 264 * with it: 265 * 266 * @skip while 267 * @until free 268 * 269 * To see the full source code for this example, click here: @ref 270 * eina_inlist_03_c 271 * @example eina_inlist_03.c 272 */ 273 274 /** 275 * @page eina_inlist_01_c eina_inlist_01.c Eina_Inlist basic usage source 276 * @include eina_inlist_01.c 277 */ 278 279 /** 280 * @page eina_inlist_02_c eina_inlist_02.c Eina_Inlist advanced usage - lists and inlists source 281 * @include eina_inlist_02.c 282 */ 283 284 /** 285 * @page eina_inlist_03_c eina_inlist_03.c Eina_Inlist advanced usage - multi-inlists source 286 * @include eina_inlist_03.c 287 */ 288 289 /** 290 * @addtogroup Eina_Inline_List_Group Inline List 291 * 292 * @brief These functions provide inline list management. 293 * 294 * Inline lists mean its nodes pointers are part of same memory as 295 * data. This has the benefit of fragmenting memory less and avoiding 296 * @c node->data indirection, but has the drawback of higher cost for some 297 * common operations like count and sort. 298 * 299 * It is possible to have inlist nodes to be part of regular lists, created with 300 * @ref eina_list_append() or @ref eina_list_prepend(). It's also possible to 301 * have a structure with two inlist pointers, thus be part of two different 302 * inlists at the same time, but the current convenience macros provided won't 303 * work for both of them. Consult @ref inlist_advanced for more info. 304 * 305 * Inline lists have their purposes, but if you don't know what those purposes are, go with 306 * regular lists instead. 307 * 308 * Tip: When using inlists in more than one place (that is, passing them around 309 * functions or keeping a pointer to them in a structure) it's more correct 310 * to keep a pointer to the first container, and not a pointer to the first 311 * inlist item (mostly they are the same, but that's not always correct). 312 * This lets the compiler to do type checking and let the programmer know 313 * exactly what type this list is. 314 * 315 * A simple example demonstrating the basic usage of an inlist can be found 316 * here: @ref eina_inlist_01_example_page 317 * 318 * @section inlist_algo Algorithm 319 * 320 * The basic structure can be represented by the following picture: 321 * 322 * @image html eina_inlist-node.png 323 * @image rtf eina_inlist-node.png 324 * @image latex eina_inlist-node.eps 325 * 326 * One data structure will also have the node information, with three pointers: 327 * @a prev, @a next and @a last. The @a last pointer is just valid for the first 328 * element (the list head), otherwise each insertion in the list would have to 329 * be done updating every node with the correct pointer. This means that it's 330 * always very important to keep a pointer to the first element of the list, 331 * since it is the only one that has the correct information to allow a proper 332 * O(1) append to the list. 333 * 334 * @section inlist_perf Performance 335 * 336 * Due to the nature of the inlist, there's no accounting information, and no 337 * easy access to the last element from each list node. This means that @ref 338 * eina_inlist_count() is order-N, while @ref eina_list_count() is order-1 (constant 339 * time). 340 * 341 * @section inlist_advanced Advanced Usage 342 * 343 * The basic usage considers a struct that will have the user data, and also 344 * have an inlist node information (prev, next and last pointers) created with 345 * @ref EINA_INLIST during the struct declaration. This allows one to use the 346 * convenience macros @ref EINA_INLIST_GET(), @ref EINA_INLIST_CONTAINER_GET(), 347 * @ref EINA_INLIST_FOREACH() and so. This happens because the @ref EINA_INLIST 348 * macro declares a struct member with the name @a __inlist, and all the other 349 * macros assume that this struct member has this name. 350 * 351 * It may be the case that someone needs to have some inlist nodes added to a 352 * @ref Eina_List too. If this happens, the inlist nodes can be added to the 353 * @ref Eina_List without any problems. This example demonstrates this case: 354 * @ref eina_inlist_02_example_page 355 * 356 * It's also possible to have some data that is part of two different inlists. 357 * If this is the case, then it won't be possible to use the convenience macros 358 * to both of the lists. It will be necessary to create a new set of macros that 359 * will allow access to the second list node info. An example for this usage can 360 * be found here: 361 * @ref eina_inlist_03_example_page 362 * 363 * List of examples: 364 * @li @ref eina_inlist_01_example_page 365 * @li @ref eina_inlist_02_example_page 366 * @li @ref eina_inlist_03_example_page 367 */ 368 369 /** 370 * @addtogroup Eina_Data_Types_Group Data Types 371 * 372 * @{ 373 */ 374 375 /** 376 * @addtogroup Eina_Containers_Group Containers 377 * 378 * @{ 379 */ 380 381 /** 382 * @defgroup Eina_Inline_List_Group Inline List 383 * 384 * @{ 385 */ 386 387 /** 388 * @typedef Eina_Inlist 389 * Inlined list type. 390 */ 391 typedef struct _Eina_Inlist Eina_Inlist; 392 393 /** 394 * @typedef Eina_Inlist_Sorted_State 395 * @since 1.1.0 396 * State of sorted Eina_Inlist 397 */ 398 typedef struct _Eina_Inlist_Sorted_State Eina_Inlist_Sorted_State; 399 400 /** 401 * @struct _Eina_Inlist 402 * Inlined list type. 403 */ 404 struct _Eina_Inlist 405 { 406 Eina_Inlist *next; /**< next node */ 407 Eina_Inlist *prev; /**< previous node */ 408 Eina_Inlist *last; /**< last node */ 409 }; 410 /** Used for declaring an inlist member in a struct */ 411 #define EINA_INLIST Eina_Inlist __in_list 412 /** Utility macro to get the inlist object of a struct */ 413 #define EINA_INLIST_GET(Inlist) (& ((Inlist)->__in_list)) 414 /** Utility macro to get the container object of an inlist */ 415 #define EINA_INLIST_CONTAINER_GET(ptr, \ 416 type) ((type *)(void *)((char *)ptr - \ 417 offsetof(type, __in_list))) 418 419 420 /** 421 * @brief Adds a new node to end of a list. 422 * 423 * @note This code is meant to be fast: appends are O(1) and do not 424 * walk @a in_list. 425 * 426 * @note @a in_item is considered to be in no list. If it was in another 427 * list before, eina_inlist_remove() it before adding. No 428 * check of @a new_l prev and next pointers is done, so it's safe 429 * to have them uninitialized. 430 * 431 * @param[in,out] in_list Existing list head or @c NULL to create a new list. 432 * @param[in] in_item New list node, must not be @c NULL. 433 * 434 * @return The new list head. Use it and not @a in_list anymore. 435 */ 436 EAPI Eina_Inlist *eina_inlist_append(Eina_Inlist *in_list, 437 Eina_Inlist *in_item) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 438 439 /** 440 * @brief Adds a new node to beginning of list. 441 * 442 * @note This code is meant to be fast: appends are O(1) and do not 443 * walk @a in_list. 444 * 445 * @note @a new_l is considered to be in no list. If it was in another 446 * list before, eina_inlist_remove() it before adding. No 447 * check of @a new_l prev and next pointers is done, so it's safe 448 * to have them uninitialized. 449 * 450 * @param[in,out] in_list Existing list head or @c NULL to create a new list. 451 * @param[in] in_item New list node, must not be @c NULL. 452 * 453 * @return The new list head. Use it and not @a in_list anymore. 454 */ 455 EAPI Eina_Inlist *eina_inlist_prepend(Eina_Inlist *in_list, 456 Eina_Inlist *in_item) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 457 458 /** 459 * @brief Adds a new node after the given relative item in list. 460 * 461 * @note This code is meant to be fast: appends are O(1) and do not 462 * walk @a in_list. 463 * 464 * @note @a in_item_l is considered to be in no list. If it was in another 465 * list before, eina_inlist_remove() it before adding. No 466 * check of @a in_item prev and next pointers is done, so it's safe 467 * to have them uninitialized. 468 * 469 * @note @a in_relative is considered to be inside @a in_list, no checks are 470 * done to confirm that and giving nodes from different lists 471 * will lead to problems. Giving NULL @a in_relative is the same as 472 * eina_list_append(). 473 * 474 * @param[in,out] in_list Existing list head or @c NULL to create a new list. 475 * @param[in] in_item New list node, must not be @c NULL. 476 * @param[in] in_relative Reference node, @a in_item will be added after it. 477 * 478 * @return The new list head. Use it and not @a list anymore. 479 */ 480 EAPI Eina_Inlist *eina_inlist_append_relative(Eina_Inlist *in_list, 481 Eina_Inlist *in_item, 482 Eina_Inlist *in_relative) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 483 484 /** 485 * @brief Adds a new node before the given relative item in list. 486 * 487 * @note This code is meant to be fast: appends are O(1) and do not 488 * walk @a in_list. 489 * 490 * @note @a in_item is considered to be in no list. If it was in another 491 * list before, eina_inlist_remove() it before adding. No 492 * check of @a in_item prev and next pointers is done, so it's safe 493 * to have them uninitialized. 494 * 495 * @note @a in_relative is considered to be inside @a in_list, no checks are 496 * done to confirm that and giving nodes from different lists 497 * will lead to problems. Giving NULL @a in_relative is the same as 498 * eina_list_prepend(). 499 * 500 * @param[in,out] in_list Existing list head or @c NULL to create a new list. 501 * @param[in] in_item New list node, must not be @c NULL. 502 * @param[in] in_relative Reference node, @a in_item will be added before it. 503 * 504 * @return The new list head. Use it and not @a in_list anymore. 505 */ 506 EAPI Eina_Inlist *eina_inlist_prepend_relative(Eina_Inlist *in_list, 507 Eina_Inlist *in_item, 508 Eina_Inlist *in_relative) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 509 510 /** 511 * @brief Removes node from list. 512 * 513 * @note This code is meant to be fast: appends are O(1) and do not 514 * walk @a list. 515 * 516 * @note @a in_item is considered to be inside @a in_list, no checks are 517 * done to confirm that and giving nodes from different lists 518 * will lead to problems, especially if @a in_item is the head since 519 * it will be different from @a list and the wrong new head will 520 * be returned. 521 * 522 * @param[in,out] in_list Existing list head, must not be @c NULL. 523 * @param[in] in_item Existing list node, must not be @c NULL. 524 * 525 * @return The new list head. Use it and not @a list anymore. 526 */ 527 EAPI Eina_Inlist *eina_inlist_remove(Eina_Inlist *in_list, 528 Eina_Inlist *in_item) EINA_ARG_NONNULL(1, 2) EINA_WARN_UNUSED_RESULT; 529 530 /** 531 * @brief Finds given node in list, returns itself if found, NULL if not. 532 * 533 * @warning This is an expensive call and has O(n) cost, possibly 534 * walking the whole list. 535 * 536 * @param[in] in_list Existing list to search @a in_item in, must not be @c NULL. 537 * @param[in] in_item What to search for, must not be @c NULL. 538 * 539 * @return @a in_item if found, @c NULL if not. 540 */ 541 EAPI Eina_Inlist *eina_inlist_find(Eina_Inlist *in_list, 542 Eina_Inlist *in_item) EINA_ARG_NONNULL(2) EINA_WARN_UNUSED_RESULT; 543 544 /** 545 * @brief Moves existing node to beginning of list. 546 * 547 * @note This code is meant to be fast: appends are O(1) and do not 548 * walk @a list. 549 * 550 * @note @a item is considered to be inside @a list. No checks are 551 * done to confirm this, and giving nodes from different lists 552 * will lead to problems. 553 * 554 * @param[in] list Existing list head or @c NULL to create a new list. 555 * @param[in] item List node to move to beginning (head), must not be @c NULL. 556 * 557 * @return The new list head. Use it and not @a list anymore. 558 */ 559 EAPI Eina_Inlist *eina_inlist_promote(Eina_Inlist *list, 560 Eina_Inlist *item) EINA_ARG_NONNULL(1, 2) EINA_WARN_UNUSED_RESULT; 561 562 /** 563 * @brief Moves existing node to end of list. 564 * 565 * @note This code is meant to be fast: appends are O(1) and do not 566 * walk @a list. 567 * 568 * @note @a item is considered to be inside @a list. No checks are 569 * done to confirm this, and giving nodes from different lists 570 * will lead to problems. 571 * 572 * @param[in] list Existing list head or @c NULL to create a new list. 573 * @param[in] item List node to move to end (tail), must not be @c NULL. 574 * 575 * @return The new list head. Use it and not @a list anymore. 576 */ 577 EAPI Eina_Inlist *eina_inlist_demote(Eina_Inlist *list, 578 Eina_Inlist *item) EINA_ARG_NONNULL(1, 2) EINA_WARN_UNUSED_RESULT; 579 580 /** 581 * @brief Gets the first list node in the list. 582 * 583 * @param[in] list The list to get the first list node from. 584 * @return The first list node in the list. 585 * 586 * This function returns the first list node in the list @p list. If 587 * @p list is @c NULL, @c NULL is returned. 588 * 589 * This is a O(N) operation (it takes time proportional 590 * to the length of the list). 591 * 592 * @since 1.8 593 */ 594 static inline Eina_Inlist *eina_inlist_first(const Eina_Inlist *list) EINA_PURE EINA_WARN_UNUSED_RESULT; 595 596 /** 597 * @brief Gets the last list node in the list. 598 * 599 * @param[in] list The list to get the last list node from. 600 * @return The last list node in the list. 601 * 602 * This function returns the last list node in the list @p list. If 603 * @p list is @c NULL, @c NULL is returned. 604 * 605 * This is a O(N) operation (it takes time proportional 606 * to the length of the list). 607 * 608 * @since 1.8 609 */ 610 static inline Eina_Inlist *eina_inlist_last(const Eina_Inlist *list) EINA_PURE EINA_WARN_UNUSED_RESULT; 611 612 /** 613 * @brief Gets the count of the number of items in a list. 614 * 615 * @param[in] list The list whose count to return. 616 * @return The number of members in the list. 617 * 618 * This function returns how many members @p list contains. If the 619 * list is @c NULL, @c 0 is returned. 620 * 621 * @warning This is an order-N operation and so the time will depend 622 * on the number of elements on the list, so, it might become 623 * slow for big lists! 624 */ 625 EAPI unsigned int eina_inlist_count(const Eina_Inlist *list) EINA_WARN_UNUSED_RESULT; 626 627 628 /** 629 * @brief Returns a new iterator associated to @a list. 630 * 631 * @param[in] in_list The list. 632 * @return A new iterator. 633 * 634 * This function returns a newly allocated iterator associated to @p 635 * in_list. If @p in_list is @c NULL or the count member of @p in_list is less 636 * or equal than 0, this function still returns a valid iterator that 637 * will always return false on eina_iterator_next(), thus keeping API 638 * sane. 639 * 640 * If the memory can not be allocated, @c NULL is returned. 641 * Otherwise, a valid iterator is returned. 642 * 643 * @warning if the list structure changes then the iterator becomes 644 * invalid, and if you add or remove nodes iterator 645 * behavior is undefined, and your program may crash! 646 */ 647 EAPI Eina_Iterator *eina_inlist_iterator_new(const Eina_Inlist *in_list) EINA_MALLOC EINA_WARN_UNUSED_RESULT; 648 649 /** 650 * @brief Returns a new accessor associated to a list. 651 * 652 * @param[in] in_list The list. 653 * @return A new accessor. 654 * 655 * This function returns a newly allocated accessor associated to 656 * @p in_list. If @p in_list is @c NULL or the count member of @p in_list is 657 * less or equal than @c 0, this function returns @c NULL. If the memory can 658 * not be allocated, @c NULL is returned and Otherwise, a valid accessor is 659 * returned. 660 */ 661 EAPI Eina_Accessor *eina_inlist_accessor_new(const Eina_Inlist *in_list) EINA_MALLOC EINA_WARN_UNUSED_RESULT; 662 663 /** 664 * @brief Inserts a new node into a sorted list. 665 * 666 * @param[in,out] list The given linked list, @b must be sorted. 667 * @param[in] item List node to insert, must not be @c NULL. 668 * @param[in] func The function called for the sort. 669 * @return A list pointer. 670 * 671 * This function inserts item into a linked list assuming it was 672 * sorted and the result will be sorted. If @p list is @c NULL, item 673 * is returned. On success, a new list pointer that should be 674 * used in place of the one given to this function is 675 * returned. Otherwise, the old pointer is returned. 676 * 677 * @note O(log2(n)) comparisons (calls to @p func) average/worst case 678 * performance. As said in eina_list_search_sorted_near_list(), 679 * lists do not have O(1) access time, so walking to the correct node 680 * can be costly, consider worst case to be almost O(n) pointer 681 * dereference (list walk). 682 * 683 * @since 1.1.0 684 */ 685 EAPI Eina_Inlist *eina_inlist_sorted_insert(Eina_Inlist *list, Eina_Inlist *item, Eina_Compare_Cb func) EINA_ARG_NONNULL(2, 3) EINA_WARN_UNUSED_RESULT; 686 687 /** 688 * @brief Creates state with valid data in it. 689 * 690 * @return A valid Eina_Inlist_Sorted_State. 691 * 692 * @since 1.1.0 693 * 694 * See eina_inlist_sorted_state_insert() for more information. 695 */ 696 EAPI Eina_Inlist_Sorted_State *eina_inlist_sorted_state_new(void); 697 698 /** 699 * @brief Forces an Eina_Inlist_Sorted_State to match the content of a list. 700 * 701 * @param[in,out] state The state to update 702 * @param[in] list The list to match 703 * @return The number of item in the actually in the list 704 * 705 * @since 1.1.0 706 * 707 * See eina_inlist_sorted_state_insert() for more information. This function is 708 * useful if you didn't use eina_inlist_sorted_state_insert() at some point, but 709 * still think you have a sorted list. It will only correctly work on a sorted list. 710 */ 711 EAPI int eina_inlist_sorted_state_init(Eina_Inlist_Sorted_State *state, Eina_Inlist *list); 712 713 /** 714 * @brief Frees an Eina_Inlist_Sorted_State. 715 * 716 * @param[in,out] state The state to destroy 717 * 718 * @since 1.1.0 719 * 720 * See eina_inlist_sorted_state_insert() for more information. 721 */ 722 EAPI void eina_inlist_sorted_state_free(Eina_Inlist_Sorted_State *state); 723 724 /** 725 * @brief Inserts a new node into a sorted list. 726 * 727 * @param[in,out] list The given linked list, @b must be sorted. 728 * @param[in] item list node to insert, must not be @c NULL. 729 * @param[in] func The function called for the sort. 730 * @param[in,out] state The current array for initial dichotomic search 731 * @return A list pointer. 732 * @since 1.1.0 733 * 734 * This function inserts item into a linked list assuming @p state matches 735 * the exact content order of the list. It uses @p state to do a fast 736 * first step dichotomic search before starting to walk the inlist itself. 737 * This makes this code much faster than eina_inlist_sorted_insert() as it 738 * doesn't need to walk the list at all. The result is of course a sorted 739 * list with an updated state. If @p list is @c NULL, item 740 * is returned. On success, a new list pointer that should be 741 * used in place of the one given to this function is 742 * returned. Otherwise, the old pointer is returned. 743 * 744 * @note O(log2(n)) comparisons (calls to @p func) average/worst case 745 * performance. As said in eina_list_search_sorted_near_list(), 746 * lists do not have O(1) access time, so walking to the correct node 747 * can be costly, but this version tries to minimize that by making it a 748 * O(log2(n)) for number small number. After n == 256, it starts to add a 749 * linear cost again. Consider worst case to be almost O(n) pointer 750 * dereference (list walk). 751 */ 752 EAPI Eina_Inlist *eina_inlist_sorted_state_insert(Eina_Inlist *list, 753 Eina_Inlist *item, 754 Eina_Compare_Cb func, 755 Eina_Inlist_Sorted_State *state); 756 /** 757 * @brief Sorts a list according to the ordering func will return. 758 * 759 * @param[in,out] head The list handle to sort. 760 * @param[in] func A function pointer that can handle comparing the list data 761 * nodes. 762 * @return the new head of list. 763 * 764 * This function sorts all the elements of @p head. @p func is used to 765 * compare two elements of @p head. If @p head or @p func are @c NULL, 766 * this function returns @c NULL. 767 * 768 * @note @b in-place: this will change the given list, so you should 769 * now point to the new list head that is returned by this function. 770 * 771 * @note Worst case is O(n * log2(n)) comparisons (calls to func()). 772 * That means that for 1,000,000 list elements, sort will do 20,000,000 773 * comparisons. 774 * 775 * Example: 776 * @code 777 * typedef struct _Sort_Ex Sort_Ex; 778 * struct _Sort_Ex 779 * { 780 * EINA_INLIST; 781 * const char *text; 782 * }; 783 * 784 * int 785 * sort_cb(const Inlist *l1, const Inlist *l2) 786 * { 787 * const Sort_Ex *x1; 788 * const Sort_Ex *x2; 789 * 790 * x1 = EINA_INLIST_CONTAINER_GET(l1, Sort_Ex); 791 * x2 = EINA_INLIST_CONTAINER_GET(l2, Sort_Ex); 792 * 793 * return(strcmp(x1->text, x2->text)); 794 * } 795 * extern Eina_Inlist *list; 796 * 797 * list = eina_inlist_sort(list, sort_cb); 798 * @endcode 799 */ 800 EAPI Eina_Inlist *eina_inlist_sort(Eina_Inlist *head, Eina_Compare_Cb func); 801 802 /* These two macros are helpers for the _FOREACH ones, don't use them */ 803 /** 804 * @def _EINA_INLIST_OFFSET 805 * @param[in,out] ref The reference to be used. 806 */ 807 #define _EINA_INLIST_OFFSET(ref) ((char *)&(ref)->__in_list - (char *)(ref)) 808 809 #if !defined(__cplusplus) 810 /** 811 * @def _EINA_INLIST_CONTAINER 812 * @param[in,out] ref The reference to be used. 813 * @param[out] ptr The pointer to be used. 814 */ 815 #define _EINA_INLIST_CONTAINER(ref, ptr) (void *)((char *)(ptr) - \ 816 _EINA_INLIST_OFFSET(ref)) 817 #else 818 /* 819 * In C++ we can't assign a "type*" pointer to void* so we rely on GCC's typeof 820 * operator. 821 */ 822 # define _EINA_INLIST_CONTAINER(ref, ptr) (__typeof__(ref))((char *)(ptr) - \ 823 _EINA_INLIST_OFFSET(ref)) 824 #endif 825 826 /** 827 * @def EINA_INLIST_FOREACH 828 * @param[in,out] list The list to iterate on. 829 * @param[out] it The pointer to the list item, i.e. a pointer to each 830 * item that is part of the list. 831 */ 832 #define EINA_INLIST_FOREACH(list, it) \ 833 for (it = NULL, it = (list ? _EINA_INLIST_CONTAINER(it, list) : NULL); it; \ 834 it = (EINA_INLIST_GET(it)->next ? _EINA_INLIST_CONTAINER(it, EINA_INLIST_GET(it)->next) : NULL)) 835 836 /** 837 * @def EINA_INLIST_FOREACH_SAFE 838 * @param[in,out] list The list to iterate on. 839 * @param[out] list2 Auxiliary Eina_Inlist variable so we can save the 840 * pointer to the next element, allowing us to free/remove 841 * the current one. Note that this macro is only safe if the 842 * next element is not removed. Only the current one is 843 * allowed to be removed. 844 * @param[out] it The pointer to the list item, i.e. a pointer to each 845 * item that is part of the list. 846 */ 847 #define EINA_INLIST_FOREACH_SAFE(list, list2, it) \ 848 for (it = NULL, it = (list ? _EINA_INLIST_CONTAINER(it, list) : NULL), list2 = it ? EINA_INLIST_GET(it)->next : NULL; \ 849 it; \ 850 it = NULL, it = list2 ? _EINA_INLIST_CONTAINER(it, list2) : NULL, list2 = list2 ? list2->next : NULL) 851 852 /** 853 * @def EINA_INLIST_REVERSE_FOREACH 854 * @param[in,out] list The list to traverse in reverse order. 855 * @param[out] it The pointer to the list item, i.e. a pointer to each 856 * item that is part of the list. 857 */ 858 #define EINA_INLIST_REVERSE_FOREACH(list, it) \ 859 for (it = NULL, it = (list ? _EINA_INLIST_CONTAINER(it, list->last) : NULL); \ 860 it; it = (EINA_INLIST_GET(it)->prev ? _EINA_INLIST_CONTAINER(it, EINA_INLIST_GET(it)->prev) : NULL)) 861 862 /** 863 * @def EINA_INLIST_REVERSE_FOREACH_FROM 864 * @param[in,out] list The last list to traverse in reverse order. 865 * @param[in] it The pointer to the list item, i.e. a pointer to each 866 * item that is part of the list. 867 * @see EINA_INLIST_REVERSE_FOREACH() 868 * 869 * @since 1.8 870 * 871 * EINA_INLIST_REVERSE_FOREACH() starts from last list of the given list. 872 * This starts from given list, not the last one. 873 */ 874 #define EINA_INLIST_REVERSE_FOREACH_FROM(list, it) \ 875 for (it = NULL, it = (list ? _EINA_INLIST_CONTAINER(it, list) : NULL); \ 876 it; it = (EINA_INLIST_GET(it)->prev ? _EINA_INLIST_CONTAINER(it, EINA_INLIST_GET(it)->prev) : NULL)) 877 878 /** 879 * @def EINA_INLIST_FREE 880 * @param[in,out] list The list to free. 881 * @param[in] it The pointer to the list item, i.e. a pointer to each item 882 * that is part of the list. 883 * 884 * NOTE: it is the duty of the body loop to properly remove the item from the 885 * inlist and free it. This function will turn into a infinite loop if you 886 * don't remove all items from the list. 887 * @since 1.8 888 */ 889 #define EINA_INLIST_FREE(list, it) \ 890 for (it = (__typeof__(it)) list; list; it = (__typeof__(it)) list) 891 892 #include "eina_inline_inlist.x" 893 894 /** 895 * @} 896 */ 897 898 /** 899 * @} 900 */ 901 902 /** 903 * @} 904 */ 905 906 #endif /*EINA_INLIST_H_*/ 907