src/lib/data/evas_list.c

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