src/tests/evas_list.c

   1 #ifdef HAVE_CONFIG_H
   2 # include "config.h"
   3 #endif
   4
   5 #include <stdlib.h>
   6
   7 #include "Evas_Data.h"
   8 #include <evas_mempool.h>
   9
  10 typedef struct _Evas_List_Accounting Evas_List_Accounting;
  11
  12 struct _Evas_List_Accounting
  13 {
  14    Evas_List *last;
  15    int count;
  16 };
  17
  18 static int _evas_list_alloc_error = 0;
  19
  20 static Evas_Mempool _evas_list_mempool =
  21 {
  22    sizeof(Evas_List),
  23    320,
  24    0, NULL, NULL
  25 };
  26 static Evas_Mempool _evas_list_accounting_mempool =
  27 {
  28    sizeof(Evas_List_Accounting),
  29    80,
  30    0, NULL, NULL
  31 };
  32
  33 /**
  34  * @defgroup Evas_List_Data_Group Linked List Creation Functions
  35  *
  36  * Functions that add data to an Evas_List.
  37  */
  38
  39 /**
  40  * Appends the given data to the given linked list.
  41  *
  42  * The following example code demonstrates how to ensure that the
  43  * given data has been successfully appended.
  44  *
  45  * @code
  46  * Evas_List *list = NULL;
  47  * extern void *my_data;
  48  *
  49  * list = evas_list_append(list, my_data);
  50  * if (evas_list_alloc_error())
  51  *   {
  52  *     fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
  53  *     exit(-1);
  54  *   }
  55  * @endcode
  56  *
  57  * @param   list The given list.  If @c NULL is given, then a new list
  58  *               is created.
  59  * @param   data The data to append.
  60  * @return  A new list pointer that should be used in place of the one
  61  *          given to this function if successful.  Otherwise, the old
  62  *          pointer is returned.
  63  * @ingroup Evas_List_Data_Group
  64  */
  65 EAPI Evas_List *
  66 evas_list_append(Evas_List *list, const void *data)
  67 {
  68    Evas_List *l, *new_l;
  69
  70    _evas_list_alloc_error = 0;
  71    new_l = evas_mempool_malloc(&_evas_list_mempool, sizeof(Evas_List));
  72    if (!new_l)
  73      {
  74         _evas_list_alloc_error = 1;
  75         return list;
  76      }
  77
  78    new_l->next = NULL;
  79    new_l->data = (void *)data;
  80    if (!list)
  81      {
  82         new_l->prev = NULL;
  83         new_l->accounting = evas_mempool_malloc(&_evas_list_accounting_mempool,
  84                                                 sizeof(Evas_List_Accounting));
  85         if (!new_l->accounting)
  86           {
  87              _evas_list_alloc_error = 1;
  88              evas_mempool_free(&_evas_list_mempool, new_l);
  89              return list;
  90           }
  91
  92         new_l->accounting->last = new_l;
  93         new_l->accounting->count = 1;
  94         return new_l;
  95      }
  96
  97    l = list->accounting->last;
  98    l->next = new_l;
  99    new_l->prev = l;
 100    new_l->accounting = list->accounting;
 101    list->accounting->last = new_l;
 102    list->accounting->count++;
 103    return list;
 104 }
 105
 106 /**
 107  * Prepends the given data to the given linked list.
 108  *
 109  * The following example code demonstrates how to ensure that the
 110  * given data has been successfully prepended.
 111  *
 112  * Example:
 113  * @code
 114  * Evas_List *list = NULL;
 115  * extern void *my_data;
 116  *
 117  * list = evas_list_prepend(list, my_data);
 118  * if (evas_list_alloc_error())
 119  *   {
 120  *     fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
 121  *     exit(-1);
 122  *   }
 123  * @endcode
 124  *
 125  * @param   list The given list.
 126  * @param   data The given data.
 127  * @return  A new list pointer that should be used in place of the one
 128  *          given to this function, if successful.  Otherwise, the old
 129  *          pointer is returned.
 130  * @ingroup Evas_List_Data_Group
 131  */
 132 EAPI Evas_List *
 133 evas_list_prepend(Evas_List *list, const void *data)
 134 {
 135    Evas_List *new_l;
 136
 137    _evas_list_alloc_error = 0;
 138    new_l = evas_mempool_malloc(&_evas_list_mempool, sizeof(Evas_List));
 139    if (!new_l)
 140      {
 141         _evas_list_alloc_error = 1;
 142         return list;
 143      }
 144
 145    new_l->prev = NULL;
 146    new_l->data = (void *)data;
 147    if (!list)
 148      {
 149         new_l->next = NULL;
 150         new_l->accounting = evas_mempool_malloc(&_evas_list_accounting_mempool,
 151                                                 sizeof(Evas_List_Accounting));
 152         if (!new_l->accounting)
 153           {
 154              _evas_list_alloc_error = 1;
 155              evas_mempool_free(&_evas_list_mempool, new_l);
 156              return list;
 157           }
 158
 159         new_l->accounting->last = new_l;
 160         new_l->accounting->count = 1;
 161         return new_l;
 162      }
 163
 164    new_l->next = list;
 165    list->prev = new_l;
 166    new_l->accounting = list->accounting;
 167    list->accounting->count++;
 168    return new_l;
 169 }
 170
 171 /**
 172  * Inserts the given data into the given linked list after the specified data.
 173  *
 174  * If @p relative is not in the list, @p data is appended to the end of the
 175  * list.  If there are multiple instances of @p relative in the list,
 176  * @p data is inserted after the first instance.
 177  *
 178  * The following example code demonstrates how to ensure that the
 179  * given data has been successfully inserted.
 180  *
 181  * @code
 182  * Evas_List *list = NULL;
 183  * extern void *my_data;
 184  * extern void *relative_member;
 185  *
 186  * list = evas_list_append(list, relative_member);
 187  * if (evas_list_alloc_error())
 188  *   {
 189  *     fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
 190  *     exit(-1);
 191  *   }
 192  * list = evas_list_append_relative(list, my_data, relative_member);
 193  * if (evas_list_alloc_error())
 194  *   {
 195  *     fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
 196  *     exit(-1);
 197  *   }
 198  * @endcode
 199  *
 200  * @param   list The given linked list.
 201  * @param   data The given data.
 202  * @param   relative The data to insert after.
 203  * @return  A new list pointer that should be used in place of the one
 204  *          given to this function if successful.  Otherwise, the old pointer
 205  *          is returned.
 206  * @ingroup Evas_List_Data_Group
 207  */
 208 EAPI Evas_List *
 209 evas_list_append_relative(Evas_List *list,
 210                           const void *data,
 211                           const void *relative)
 212 {
 213    Evas_List *l;
 214
 215    for (l = list; l; l = l->next)
 216      {
 217         if (l->data == relative)
 218            return evas_list_append_relative_list(list, data, l);
 219      }
 220    return evas_list_append(list, data);
 221 }
 222
 223 EAPI Evas_List *
 224 evas_list_append_relative_list(Evas_List *list,
 225                                const void *data,
 226                                Evas_List *relative)
 227 {
 228    Evas_List *new_l;
 229
 230    if ((!list) || (!relative))
 231       return evas_list_append(list, data);
 232
 233    _evas_list_alloc_error = 0;
 234    new_l = evas_mempool_malloc(&_evas_list_mempool, sizeof(Evas_List));
 235    if (!new_l)
 236      {
 237         _evas_list_alloc_error = 1;
 238         return list;
 239      }
 240
 241    new_l->data = (void *)data;
 242    if (relative->next)
 243      {
 244         new_l->next = relative->next;
 245         relative->next->prev = new_l;
 246      }
 247    else
 248       new_l->next = NULL;
 249
 250    relative->next = new_l;
 251    new_l->prev = relative;
 252    new_l->accounting = list->accounting;
 253    list->accounting->count++;
 254    if (!new_l->next)
 255       new_l->accounting->last = new_l;
 256
 257    return list;
 258 }
 259
 260 /**
 261  * Prepend a data pointer to a linked list before the member specified
 262  * @param list The list handle to prepend @p data too
 263  * @param data The data pointer to prepend to list @p list before @p relative
 264  * @param relative The data pointer before which to insert @p data
 265  * @return A new list handle to replace the old one
 266
 267  * Inserts the given data into the given linked list before the member
 268  * specified.
 269  *
 270  * If @p relative is not in the list, @p data is prepended to the
 271  * start of the list.  If there are multiple instances of @p relative
 272  * in the list, @p data is inserted before the first instance.
 273  *
 274  * The following code example demonstrates how to ensure that the
 275  * given data has been successfully inserted.
 276  *
 277  * @code
 278  * Evas_List *list = NULL;
 279  * extern void *my_data;
 280  * extern void *relative_member;
 281  *
 282  * list = evas_list_append(list, relative_member);
 283  * if (evas_list_alloc_error())
 284  *   {
 285  *     fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
 286  *     exit(-1);
 287  *   }
 288  * list = evas_list_prepend_relative(list, my_data, relative_member);
 289  * if (evas_list_alloc_error())
 290  *   {
 291  *     fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
 292  *     exit(-1);
 293  *   }
 294  * @endcode
 295  *
 296  * @param   list The given linked list.
 297  * @param   data The given data.
 298  * @param   relative The data to insert before.
 299  * @return  A new list pointer that should be used in place of the one
 300  *          given to this function if successful.  Otherwise the old pointer
 301  *          is returned.
 302  * @ingroup Evas_List_Data_Group
 303  */
 304 EAPI Evas_List *
 305 evas_list_prepend_relative(Evas_List *list,
 306                            const void *data,
 307                            const void *relative)
 308 {
 309    Evas_List *l;
 310
 311    _evas_list_alloc_error = 0;
 312    for (l = list; l; l = l->next)
 313      {
 314         if (l->data == relative)
 315            return evas_list_prepend_relative_list(list, data, l);
 316      }
 317    return evas_list_prepend(list, data);
 318 }
 319
 320 EAPI Evas_List *
 321 evas_list_prepend_relative_list(Evas_List *list,
 322                                 const void *data,
 323                                 Evas_List *relative)
 324 {
 325    Evas_List *new_l;
 326
 327    if ((!list) || (!relative))
 328       return evas_list_prepend(list, data);
 329
 330    _evas_list_alloc_error = 0;
 331    new_l = evas_mempool_malloc(&_evas_list_mempool, sizeof(Evas_List));
 332    if (!new_l)
 333      {
 334         _evas_list_alloc_error = 1;
 335         return list;
 336      }
 337
 338    new_l->data = (void *)data;
 339    new_l->prev = relative->prev;
 340    new_l->next = relative;
 341    if (relative->prev)
 342       relative->prev->next = new_l;
 343
 344    relative->prev = new_l;
 345    new_l->accounting = list->accounting;
 346    list->accounting->count++;
 347    if (new_l->prev)
 348       return list;
 349
 350    return new_l;
 351 }
 352
 353 /**
 354  * @defgroup Evas_List_Remove_Group Linked List Remove Functions
 355  *
 356  * Functions that remove data from linked lists.
 357  */
 358
 359 /**
 360  * Removes the first instance of the specified data from the given list.
 361  *
 362  * If the specified data is not in the given list, nothing is done.
 363  *
 364  * @param   list The given list.
 365  * @param   data The specified data.
 366  * @return  A new list pointer that should be used in place of the one
 367  *          passed to this functions.
 368  * @ingroup Evas_List_Remove_Group
 369  */
 370 EAPI Evas_List *
 371 evas_list_remove(Evas_List *list, const void *data)
 372 {
 373    Evas_List *l;
 374
 375    for (l = list; l; l = l->next)
 376      {
 377         if (l->data == data)
 378            return evas_list_remove_list(list, l);
 379      }
 380    return list;
 381 }
 382
 383 /**
 384  * Removes the specified data
 385  *
 386  * Remove a specified member from a list
 387  * @param list The list handle to remove @p remove_list from
 388  * @param remove_list The list node which is to be removed
 389  * @return A new list handle to replace the old one
 390  *
 391  * Calling this function takes the list node @p remove_list and removes it
 392  * from the list @p list, freeing the list node structure @p remove_list.
 393  *
 394  * Example:
 395  * @code
 396  * extern Evas_List *list;
 397  * Evas_List *l;
 398  * extern void *my_data;
 399  *
 400  * for (l = list; l; l= l->next)
 401  *   {
 402  *     if (l->data == my_data)
 403  *       {
 404  *         list = evas_list_remove_list(list, l);
 405  *         break;
 406  *       }
 407  *   }
 408  * @endcode
 409  * @ingroup Evas_List_Remove_Group
 410  */
 411 EAPI Evas_List *
 412 evas_list_remove_list(Evas_List *list, Evas_List *remove_list)
 413 {
 414    Evas_List *return_l;
 415
 416    if (!list)
 417       return NULL;
 418
 419    if (!remove_list)
 420       return list;
 421
 422    if (remove_list->next)
 423       remove_list->next->prev = remove_list->prev;
 424
 425    if (remove_list->prev)
 426      {
 427         remove_list->prev->next = remove_list->next;
 428         return_l = list;
 429      }
 430    else
 431       return_l = remove_list->next;
 432
 433    if (remove_list == list->accounting->last)
 434       list->accounting->last = remove_list->prev;
 435
 436    list->accounting->count--;
 437    if (list->accounting->count == 0)
 438              evas_mempool_free(&_evas_list_accounting_mempool, list->accounting);
 439
 440              evas_mempool_free(&_evas_list_mempool,            remove_list);
 441    return return_l;
 442 }
 443
 444 /**
 445  * Moves the specified data to the head of the list
 446  *
 447  * Move a specified member to the head of the list
 448  * @param list The list handle to move @p inside
 449  * @param move_list The list node which is to be moved
 450  * @return A new list handle to replace the old one
 451  *
 452  * Calling this function takes the list node @p move_list and moves it
 453  * to the front of the @p list.
 454  *
 455  * Example:
 456  * @code
 457  * extern Evas_List *list;
 458  * Evas_List *l;
 459  * extern void *my_data;
 460  *
 461  * for (l = list; l; l= l->next)
 462  *   {
 463  *     if (l->data == my_data)
 464  *       {
 465  *         list = evas_list_promote_list(list, l);
 466  *         break;
 467  *       }
 468  *   }
 469  * @endcode
 470  * @ingroup Evas_List_Promote_Group
 471  */
 472 EAPI Evas_List *
 473 evas_list_promote_list(Evas_List *list, Evas_List *move_list)
 474 {
 475    Evas_List *return_l;
 476
 477    if (!list)
 478       return NULL;
 479
 480    if (!move_list)
 481       return list;
 482
 483    if (move_list == list)
 484       return list;
 485
 486    if (move_list->next)
 487       move_list->next->prev = move_list->prev;
 488
 489    if (move_list->prev)
 490      {
 491         move_list->prev->next = move_list->next;
 492         return_l = list;
 493      }
 494    else
 495       return_l = move_list->next;
 496
 497    if (move_list == list->accounting->last)
 498       list->accounting->last = move_list->prev;
 499
 500    move_list->prev = return_l->prev;
 501    if (return_l->prev)
 502       return_l->prev->next = move_list;
 503
 504    return_l->prev = move_list;
 505    move_list->next = return_l;
 506    return move_list;
 507 }
 508
 509
 510
 511 /**
 512  * @defgroup Evas_List_Find_Group Linked List Find Functions
 513  *
 514  * Functions that find specified data in a linked list.
 515  */
 516
 517 /**
 518  * Find a member of a list and return the member
 519  * @param list The list handle to search for @p data
 520  * @param data The data pointer to find in the list @p list
 521  * @return The found member data pointer
 522  *
 523  * A call to this function will search the list @p list from beginning to end
 524  * for the first member whose data pointer is @p data. If it is found, @p data
 525  * will be returned, otherwise NULL will be returned.
 526  *
 527  * Example:
 528  * @code
 529  * extern Evas_List *list;
 530  * extern void *my_data;
 531  *
 532  * if (evas_list_find(list, my_data) == my_data)
 533  *   {
 534  *     printf("Found member %p\n", my_data);
 535  *   }
 536  * @endcode
 537  * @ingroup Evas_List_Find_Group
 538  */
 539 EAPI void *
 540 evas_list_find(const Evas_List *list, const void *data)
 541 {
 542    const Evas_List *l;
 543
 544    for (l = list; l; l = l->next)
 545      {
 546         if (l->data == data)
 547            return (void *)data;
 548      }
 549    return NULL;
 550 }
 551
 552 /**
 553  * Find a member of a list and return the list node containing that member
 554  * @param list The list handle to search for @p data
 555  * @param data The data pointer to find in the list @p list
 556  * @return The found members list node
 557  *
 558  * A call to this function will search the list @p list from beginning to end
 559  * for the first member whose data pointer is @p data. If it is found, the
 560  * list node containing the specified member will be returned, otherwise NULL
 561  * will be returned.
 562  *
 563  * Example:
 564  * @code
 565  * extern Evas_List *list;
 566  * extern void *my_data;
 567  * Evas_List *found_node;
 568  *
 569  * found_node = evas_list_find_list(list, my_data);
 570  * if (found_node)
 571  *   {
 572  *     printf("Found member %p\n", found_node->data);
 573  *   }
 574  * @endcode
 575  * @ingroup Evas_List_Find_Group
 576  */
 577 EAPI Evas_List *
 578 evas_list_find_list(const Evas_List *list, const void *data)
 579 {
 580    const Evas_List *l;
 581
 582    for (l = list; l; l = l->next)
 583      {
 584         if (l->data == data)
 585            return (Evas_List *)l;
 586      }
 587    return NULL;
 588 }
 589
 590 /**
 591  * Free an entire list and all the nodes, ignoring the data contained
 592  * @param list The list to free
 593  * @return A NULL pointer
 594  *
 595  * This function will free all the list nodes in list specified by @p list.
 596  *
 597  * Example:
 598  * @code
 599  * extern Evas_List *list;
 600  *
 601  * list = evas_list_free(list);
 602  * @endcode
 603  * @ingroup Evas_List_Remove_Group
 604  */
 605 EAPI Evas_List *
 606 evas_list_free(Evas_List *list)
 607 {
 608    Evas_List *l, *free_l;
 609
 610    if (!list)
 611       return NULL;
 612
 613              evas_mempool_free(&_evas_list_accounting_mempool, list->accounting);
 614    for (l = list; l; )
 615      {
 616         free_l = l;
 617         l = l->next;
 618              evas_mempool_free(&_evas_list_mempool, free_l);
 619      }
 620    return NULL;
 621 }
 622
 623 /**
 624  * @defgroup Evas_List_Traverse_Group Linked List Traverse Functions
 625  *
 626  * Functions that you can use to traverse a linked list.
 627  */
 628
 629 /**
 630  * Get the last list node in the list
 631  * @param list The list to get the last list node from
 632  * @return The last list node in the list @p list
 633  *
 634  * This function will return the last list node in the list (or NULL if the
 635  * list is empty).
 636  *
 637  * NB: This is a order-1 operation (it takes the same short time regardless of
 638  * the length of the list).
 639  *
 640  * Example:
 641  * @code
 642  * extern Evas_List *list;
 643  * Evas_List *last, *l;
 644  *
 645  * last = evas_list_last(list);
 646  * printf("The list in reverse:\n");
 647  * for (l = last; l; l = l->prev)
 648  *   {
 649  *     printf("%p\n", l->data);
 650  *   }
 651  * @endcode
 652  * @ingroup Evas_List_Traverse_Group
 653  */
 654 EAPI Evas_List *
 655 evas_list_last(const Evas_List *list)
 656 {
 657    if (!list)
 658       return NULL;
 659
 660    return list->accounting->last;
 661 }
 662
 663 /**
 664  * Get the next list node after the specified list node
 665  * @param list The list node to get the next list node from
 666  * @return The next list node, or NULL if no next list node exists
 667  *
 668  * This function returns the next list node after the current one. It is
 669  * equivalent to list->next.
 670  *
 671  * Example:
 672  * @code
 673  * extern Evas_List *list;
 674  * Evas_List *l;
 675  *
 676  * printf("The list:\n");
 677  * for (l = list; l; l = evas_list_next(l))
 678  *   {
 679  *     printf("%p\n", l->data);
 680  *   }
 681  * @endcode
 682  * @ingroup Evas_List_Traverse_Group
 683  */
 684 EAPI Evas_List *
 685 evas_list_next(const Evas_List *list)
 686 {
 687    if (!list)
 688       return NULL;
 689
 690    return list->next;
 691 }
 692
 693 /**
 694  * Get the previous list node before the specified list node
 695  * @param list The list node to get the previous list node from
 696  * @return The previous list node, or NULL if no previous list node exists
 697  *
 698  * This function returns the previous list node before the current one. It is
 699  * equivalent to list->prev.
 700  *
 701  * Example:
 702  * @code
 703  * extern Evas_List *list;
 704  * Evas_List *last, *l;
 705  *
 706  * last = evas_list_last(list);
 707  * printf("The list in reverse:\n");
 708  * for (l = last; l; l = evas_list_prev(l))
 709  *   {
 710  *     printf("%p\n", l->data);
 711  *   }
 712  * @endcode
 713  * @ingroup Evas_List_Traverse_Group
 714  */
 715 EAPI Evas_List *
 716 evas_list_prev(const Evas_List *list)
 717 {
 718    if (!list)
 719       return NULL;
 720
 721    return list->prev;
 722 }
 723
 724 /**
 725  * @defgroup Evas_List_General_Group Linked List General Functions
 726  *
 727  * Miscellaneous functions that work on linked lists.
 728  */
 729
 730 /**
 731  * Get the list node data member
 732  * @param list The list node to get the data member of
 733  * @return The data member from the list node @p list
 734  *
 735  * This function returns the data member of the specified list node @p list.
 736  * It is equivalent to list->data.
 737  *
 738  * Example:
 739  * @code
 740  * extern Evas_List *list;
 741  * Evas_List *l;
 742  *
 743  * printf("The list:\n");
 744  * for (l = list; l; l = evas_list_next(l))
 745  *   {
 746  *     printf("%p\n", evas_list_data(l));
 747  *   }
 748  * @endcode
 749  * @ingroup Evas_List_General_Group
 750  */
 751 EAPI void *
 752 evas_list_data(const Evas_List *list)
 753 {
 754    if (!list)
 755       return NULL;
 756
 757    return list->data;
 758 }
 759
 760 /**
 761  * Get the count of the number of items in a list
 762  * @param list The list whose count to return
 763  * @return The number of members in the list @p list
 764  *
 765  * This function returns how many members in the specified list: @p list. If
 766  * the list is empty (NULL), 0 is returned.
 767  *
 768  * NB: This is an order-1 operation and takes the same time regardless of the
 769  * length of the list.
 770  *
 771  * Example:
 772  * @code
 773  * extern Evas_List *list;
 774  *
 775  * printf("The list has %i members\n", evas_list_count(list));
 776  * @endcode
 777  * @ingroup Evas_List_General_Group
 778  */
 779 EAPI int
 780 evas_list_count(const Evas_List *list)
 781 {
 782    if (!list)
 783       return 0;
 784
 785    return list->accounting->count;
 786 }
 787
 788 /**
 789  * Get the nth member's data pointer in a list
 790  * @param list The list to get member number @p n from
 791  * @param n The number of the element (0 being the first)
 792  * @return The data pointer stored in the specified element
 793  *
 794  * This function returns the data pointer of element number @p n, in the list
 795  * @p list. The first element in the array is element number 0. If the element
 796  * number @p n does not exist, NULL will be returned.
 797  *
 798  * Example:
 799  * @code
 800  * extern Evas_List *list;
 801  * extern int number;
 802  * void *data;
 803  *
 804  * data = evas_list_nth(list, number);
 805  * if (data)
 806  *   printf("Element number %i has data %p\n", number, data);
 807  * @endcode
 808  * @ingroup Evas_List_Find_Group
 809  */
 810 EAPI void *
 811 evas_list_nth(const Evas_List *list, int n)
 812 {
 813    Evas_List *l;
 814
 815    l = evas_list_nth_list(list, n);
 816    return l ? l->data : NULL;
 817 }
 818
 819 /**
 820  * Get the nth member's list node in a list
 821  * @param list The list to get member number @p n from
 822  * @param n The number of the element (0 being the first)
 823  * @return The list node stored in the numbered element
 824  *
 825  * This function returns the list node of element number @p n, in the list
 826  * @p list. The first element in the array is element number 0. If the element
 827  * number @p n does not exist, NULL will be returned.
 828  *
 829  * Example:
 830  * @code
 831  * extern Evas_List *list;
 832  * extern int number;
 833  * Evas_List *nth_list;
 834  *
 835  * nth_list = evas_list_nth_list(list, number);
 836  * if (nth_list)
 837  *   printf("Element number %i has data %p\n", number, nth_list->data);
 838  * @endcode
 839  * @ingroup Evas_List_Find_Group
 840  */
 841 EAPI Evas_List *
 842 evas_list_nth_list(const Evas_List *list, int n)
 843 {
 844    int i;
 845    const Evas_List *l;
 846
 847    /* check for non-existing nodes */
 848    if ((!list) || (n < 0) ||
 849        (n > (list->accounting->count - 1)))
 850       return NULL;
 851
 852    /* if the node is in the 2nd half of the list, search from the end
 853     * else, search from the beginning.
 854     */
 855    if (n > (list->accounting->count / 2))
 856       for (i = list->accounting->count - 1,
 857            l = list->accounting->last;
 858            l;
 859            l = l->prev, i--)
 860         {
 861            if (i == n)
 862               return (Evas_List *)l;
 863         }
 864    else
 865       for (i = 0, l = list; l; l = l->next, i++)
 866         {
 867            if (i == n)
 868               return (Evas_List *)l;
 869         }
 870
 871    return NULL;
 872 }
 873
 874 /**
 875  * @defgroup Evas_List_Ordering_Group Linked List Ordering Functions
 876  *
 877  * Functions that change the ordering of data in a linked list.
 878  */
 879
 880 /**
 881  * Reverse all the elements in the list
 882  * @param list The list to reverse
 883  * @return The list after it has been reversed
 884  *
 885  * This takes a list @p list, and reverses the order of all elements in the
 886  * list, so the last member is now first, and so on.
 887  *
 888  * Example:
 889  * @code
 890  * extern Evas_List *list;
 891  *
 892  * list = evas_list_reverse(list);
 893  * @endcode
 894  * @ingroup Evas_List_Ordering_Group
 895  */
 896 EAPI Evas_List *
 897 evas_list_reverse(Evas_List *list)
 898 {
 899    Evas_List *l1, *l2;
 900
 901    if (!list)
 902       return NULL;
 903
 904    l1 = list;
 905    l2 = list->accounting->last;
 906    while (l1 != l2)
 907      {
 908         void *data;
 909
 910         data = l1->data;
 911         l1->data = l2->data;
 912         l2->data = data;
 913         l1 = l1->next;
 914         if (l1 == l2)
 915            break;
 916
 917         l2 = l2->prev;
 918      }
 919
 920    return list;
 921 }
 922
 923 /**
 924  * Sort a list according to the ordering func will return
 925  * @param list The list handle to sort
 926  * @param size The length of the list to sort
 927  * @param func A function pointer that can handle comparing the list data
 928  * nodes
 929  * @return A new sorted list
 930  *
 931  * This function sorts your list.  The data in your nodes can be arbitrary,
 932  * you just have to be smart enough to know what kind of data is in your
 933  * lists
 934  *
 935  * Example:
 936  * @code
 937  * int
 938  * sort_cb(void *d1, void *d2)
 939  * {
 940  *   const char *txt = NULL;
 941  *    const char *txt2 = NULL;
 942  *
 943  *    if(!d1) return(1);
 944  *    if(!d2) return(-1);
 945  *
 946  *    return(strcmp((const char*)d1, (const char*)d2));
 947  * }
 948  * extern Evas_List *list;
 949  *
 950  * list = evas_list_sort(list, evas_list_count(list), sort_cb);
 951  * if (evas_list_alloc_error())
 952  *   {
 953  *     fprintf(stderr, "ERROR: Memory is low. List Sorting failed.\n");
 954  *     exit(-1);
 955  *   }
 956  * @endcode
 957  * @ingroup Evas_List_Ordering_Group
 958  */
 959 EAPI Evas_List *
 960 evas_list_sort(Evas_List *list, int size, int (*func)(void *, void *))
 961 {
 962    Evas_List *last;
 963    unsigned int list_number;
 964    unsigned int middle;
 965    unsigned int list_size;
 966
 967    if (!list || !func)
 968       return NULL;
 969
 970    /* if the caller specified an invalid size, sort the whole list */
 971    if ((size <= 0) ||
 972        (size > list->accounting->count))
 973       size = list->accounting->count;
 974
 975    last = list->accounting->last;
 976    middle = size - size / 2;
 977
 978    for (list_number = middle, list_size = 1;
 979         list_size < middle * 2;
 980         list_number >>= 1, list_size <<= 1)
 981      {
 982         Evas_List *head1 = list;
 983         unsigned int limit = size;
 984         unsigned int process_list;
 985         unsigned int pass_number;
 986         unsigned int split_size = list_size;
 987
 988         for (process_list = 0; process_list < list_number + 1; ++process_list)
 989           {
 990              Evas_List *head2;
 991              unsigned int size_sum;
 992              int size1, size2;
 993              int i;
 994
 995              size1 = limit < split_size ? limit : split_size;
 996              limit -= size1;
 997
 998              size2 = limit < split_size ? limit : split_size;
 999              limit -= size2;
1000
1001              size_sum = size1 + size2;
1002
1003              for (head2 = head1, i = 0; i < size1; ++i)
1004                 head2 = evas_list_next (head2);
1005
1006              for (pass_number = 0; pass_number < size_sum; ++pass_number)
1007                {
1008                   Evas_List *next;
1009                   Evas_List *prev1;
1010                   Evas_List *prev2;
1011
1012                   if (size1 == 0 || !head1) /* List1 is empty, head1 is already at the end of the list. So only need to update head2 */
1013                     {
1014                        for (; pass_number < size_sum; ++pass_number)
1015                           head2 = evas_list_next (head2);
1016                        break;
1017                     }
1018                   else
1019                   if (size2 == 0 || !head2) /* List2 is empty, just leave */
1020                      break;
1021                   else
1022                   if (func (head1->data, head2->data) < 0)
1023                     {
1024                        head1 = evas_list_next (head1);
1025                        --size1;
1026                     }
1027                   else
1028                     {
1029                        next = evas_list_next (head2);
1030                        prev1 = evas_list_prev (head1);
1031                        prev2 = evas_list_prev (head2);
1032
1033                        if (next)
1034                           next->prev = prev2;
1035
1036                        if (prev1)
1037                           prev1->next = head2;
1038
1039                        if (prev2)
1040                           prev2->next = next;
1041
1042                        head2->prev = prev1;
1043                        head2->next = head1;
1044                        head1->prev = head2;
1045
1046                        --size2;
1047
1048                        if (head1 == list)
1049                           list = head2;
1050
1051                        if (head2 == last)
1052                           last = prev2;
1053
1054                        head2 = next;
1055                     }
1056                }
1057              head1 = head2;
1058           }
1059      }
1060
1061    list->accounting->last = last;
1062    return list;
1063 }
1064 /**
1065  * Return the memory allocation failure flag after any operation needin allocation
1066  * @return The state of the allocation flag
1067  *
1068  * This function returns the state of the memory allocation flag. This flag is
1069  * set if memory allocations during evas_list_append(), evas_list_prepend(),
1070  * evas_list_append_relative(), or evas_list_prepend_relative() fail. If they
1071  * do fail, 1 will be returned, otherwise 0 will be returned. The flag will
1072  * remain in its current state until the next call that requires allocation
1073  * is called, and is then reset.
1074  *
1075  * Example:
1076  * @code
1077  * Evas_List *list = NULL;
1078  * extern void *my_data;
1079  *
1080  * list = evas_list_append(list, my_data);
1081  * if (evas_list_alloc_error())
1082  *   {
1083  *     fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
1084  *     exit(-1);
1085  *   }
1086  * @endcode
1087  * @ingroup Evas_List_General_Group
1088  */
1089 EAPI int
1090 evas_list_alloc_error(void)
1091 {
1092    return _evas_list_alloc_error;
1093 }