src/lib/ecore/ecore_list.c

   1 #include "ecore_private.h"
   2 #include "Ecore.h"
   3 #include "Ecore_Data.h"
   4
   5 /* Some tests showed that beyond that value heap sort is faster than merge sort
   6  * (in this implementation). This value has to be changed or at least review
   7  * if someone is changing the implementation. */
   8 #define ECORE_MERGESORT_LIMIT 40000
   9
  10 /* Return information about the list */
  11 static void *_ecore_list_current(Ecore_List * list);
  12
  13 /* Adding functions */
  14 static int _ecore_list_insert(Ecore_List * list, Ecore_List_Node *node);
  15 static int _ecore_list_append_0(Ecore_List * list, Ecore_List_Node *node);
  16 static int _ecore_list_prepend_0(Ecore_List * list, Ecore_List_Node *node);
  17
  18 /* Remove functions */
  19 static void *_ecore_list_remove_0(Ecore_List * list);
  20 static void *_ecore_list_first_remove(Ecore_List * list);
  21 static void *_ecore_list_last_remove(Ecore_List * list);
  22
  23 /* Basic traversal functions */
  24 static void *_ecore_list_next(Ecore_List * list);
  25 static void *_ecore_list_last_goto(Ecore_List * list);
  26 static void *_ecore_list_first_goto(Ecore_List * list);
  27 static void *_ecore_list_goto(Ecore_List * list, const void *data);
  28 static void *_ecore_list_index_goto(Ecore_List *list, int index);
  29
  30 /* Iterative functions */
  31 static int _ecore_list_for_each(Ecore_List *list, Ecore_For_Each function,
  32                                 void *user_data);
  33 static void *_ecore_list_find(Ecore_List *list, Ecore_Compare_Cb function,
  34                               const void *user_data);
  35
  36 /* Sorting functions */
  37 static Ecore_List_Node *_ecore_list_node_mergesort(Ecore_List_Node *first,
  38                                   int n, Ecore_Compare_Cb compare, int order);
  39 static Ecore_List_Node *_ecore_list_node_merge(Ecore_List_Node *first,
  40                                                Ecore_List_Node *second,
  41                                                Ecore_Compare_Cb compare,
  42                                                int order);
  43 static Ecore_List_Node *_ecore_dlist_node_mergesort(Ecore_List_Node *first,
  44                                   int n, Ecore_Compare_Cb compare, int order);
  45 static Ecore_List_Node *_ecore_dlist_node_merge(Ecore_List_Node *first,
  46                                                Ecore_List_Node *second,
  47                                                Ecore_Compare_Cb compare,
  48                                                int order);
  49
  50 /* Private double linked list functions */
  51 static void *_ecore_dlist_previous(Ecore_DList * list);
  52 static void *_ecore_dlist_first_remove(Ecore_DList *list);
  53 static void *_ecore_dlist_index_goto(Ecore_DList *list, int index);
  54
  55 /* XXX: Begin deprecated code */
  56 EAPI void *
  57 _ecore_list2_append(void *in_list, void *in_item)
  58 {
  59    Ecore_List2 *l, *new_l;
  60    Ecore_List2 *list, *item;
  61
  62    list = in_list;
  63    item = in_item;
  64    new_l = item;
  65    new_l->next = NULL;
  66    if (!list)
  67      {
  68         new_l->prev = NULL;
  69         new_l->last = new_l;
  70         return new_l;
  71      }
  72    if (list->last) l = list->last;
  73    else for (l = list; l; l = l->next);
  74    l->next = new_l;
  75    new_l->prev = l;
  76    list->last = new_l;
  77    return list;
  78 }
  79
  80 EAPI void *
  81 _ecore_list2_prepend(void *in_list, void *in_item)
  82 {
  83    Ecore_List2 *new_l;
  84    Ecore_List2 *list, *item;
  85
  86    list = in_list;
  87    item = in_item;
  88    new_l = item;
  89    new_l->prev = NULL;
  90    if (!list)
  91      {
  92         new_l->next = NULL;
  93         new_l->last = new_l;
  94         return new_l;
  95      }
  96    new_l->next = list;
  97    list->prev = new_l;
  98    new_l->last = list->last;
  99    list->last = NULL;
 100    return new_l;
 101 }
 102
 103 EAPI void *
 104 _ecore_list2_append_relative(void *in_list, void *in_item, void *in_relative)
 105 {
 106    Ecore_List2 *l;
 107    Ecore_List2 *list, *item, *relative;
 108
 109    list = in_list;
 110    item = in_item;
 111    relative = in_relative;
 112    for (l = list; l; l = l->next)
 113      {
 114         if (l == relative)
 115           {
 116              Ecore_List2 *new_l;
 117
 118              new_l = item;
 119              if (l->next)
 120                {
 121                   new_l->next = l->next;
 122                   l->next->prev = new_l;
 123                }
 124
 125              else new_l->next = NULL;
 126              l->next = new_l;
 127              new_l->prev = l;
 128              if (!new_l->next)
 129                list->last = new_l;
 130              return list;
 131           }
 132      }
 133    return _ecore_list2_append(list, item);
 134 }
 135
 136 EAPI void *
 137 _ecore_list2_prepend_relative(void *in_list, void *in_item, void *in_relative)
 138 {
 139    Ecore_List2 *l;
 140    Ecore_List2 *list, *item, *relative;
 141
 142    list = in_list;
 143    item = in_item;
 144    relative = in_relative;
 145    for (l = list; l; l = l->next)
 146      {
 147         if (l == relative)
 148           {
 149              Ecore_List2 *new_l;
 150
 151              new_l = item;
 152              new_l->prev = l->prev;
 153              new_l->next = l;
 154              l->prev = new_l;
 155              if (new_l->prev)
 156                {
 157                   new_l->prev->next = new_l;
 158                   if (!new_l->next)
 159                     list->last = new_l;
 160                   return list;
 161                }
 162              else
 163                {
 164                   if (!new_l->next)
 165                     new_l->last = new_l;
 166                   else
 167                     {
 168                        new_l->last = list->last;
 169                        list->last = NULL;
 170                     }
 171                   return new_l;
 172                }
 173           }
 174      }
 175    return _ecore_list2_prepend(list, item);
 176 }
 177
 178 EAPI void *
 179 _ecore_list2_remove(void *in_list, void *in_item)
 180 {
 181    Ecore_List2 *return_l;
 182    Ecore_List2 *list, *item;
 183
 184    /* checkme */
 185    if(!in_list)
 186      return in_list;
 187
 188    list = in_list;
 189    item = in_item;
 190    if (!item) return list;
 191    if (item->next)
 192      item->next->prev = item->prev;
 193    if (item->prev)
 194      {
 195         item->prev->next = item->next;
 196         return_l = list;
 197      }
 198    else
 199      {
 200         return_l = item->next;
 201         if (return_l)
 202           return_l->last = list->last;
 203      }
 204    if (item == list->last)
 205      list->last = item->prev;
 206    item->next = NULL;
 207    item->prev = NULL;
 208    return return_l;
 209 }
 210
 211 EAPI void *
 212 _ecore_list2_find(void *in_list, void *in_item)
 213 {
 214    Ecore_List2 *l;
 215    Ecore_List2 *list, *item;
 216
 217    list = in_list;
 218    item = in_item;
 219    for (l = list; l; l = l->next)
 220      {
 221         if (l == item) return item;
 222      }
 223    return NULL;
 224 }
 225 /* XXX: End deprecated code */
 226
 227 /**
 228 @defgroup Ecore_Data_List_Creation_Group List Creation/Destruction Functions
 229
 230 Functions that create, initialize and destroy Ecore_Lists.
 231 */
 232
 233 /**
 234  * Create and initialize a new list.
 235  * @return  A new initialized list on success, @c NULL on failure.
 236  * @ingroup Ecore_Data_List_Creation_Group
 237  */
 238 EAPI Ecore_List *
 239 ecore_list_new(void)
 240 {
 241    Ecore_List *list;
 242
 243    list = (Ecore_List *)malloc(sizeof(Ecore_List));
 244    if (!list)
 245      return NULL;
 246
 247    if (!ecore_list_init(list))
 248      {
 249         FREE(list);
 250         return NULL;
 251      }
 252
 253    return list;
 254 }
 255
 256 /**
 257  * Initialize a list to some sane starting values.
 258  * @param   list The list to initialize.
 259  * @return  @c TRUE if successful, @c FALSE if an error occurs.
 260  * @ingroup Ecore_Data_List_Creation_Group
 261  */
 262 EAPI int
 263 ecore_list_init(Ecore_List *list)
 264 {
 265    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
 266
 267    memset(list, 0, sizeof(Ecore_List));
 268
 269    return TRUE;
 270 }
 271
 272 /**
 273  * Free a list and all of it's nodes.
 274  * @param   list The list to be freed.
 275  * @ingroup Ecore_Data_List_Creation_Group
 276  */
 277 EAPI void
 278 ecore_list_destroy(Ecore_List *list)
 279 {
 280    void *data;
 281
 282    CHECK_PARAM_POINTER("list", list);
 283
 284    while (list->first)
 285      {
 286         data = _ecore_list_first_remove(list);
 287         if (list->free_func)
 288           list->free_func(data);
 289      }
 290
 291    FREE(list);
 292 }
 293
 294 /**
 295  * Set the function for freeing data.
 296  * @param  list      The list that will use this function when nodes are
 297  *                   destroyed.
 298  * @param  free_func The function that will free the key data.
 299  * @return @c TRUE on successful set, @c FALSE otherwise.
 300  */
 301 EAPI int
 302 ecore_list_free_cb_set(Ecore_List *list, Ecore_Free_Cb free_func)
 303 {
 304    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
 305
 306    list->free_func = free_func;
 307
 308    return TRUE;
 309 }
 310
 311 /**
 312  * Checks the list for any nodes.
 313  * @param  list  The list to check for nodes
 314  * @return @c TRUE if no nodes in list, @c FALSE if the list contains nodes
 315  */
 316 EAPI int
 317 ecore_list_empty_is(Ecore_List *list)
 318 {
 319    int ret = TRUE;
 320
 321    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
 322
 323    if (list->nodes)
 324      ret = FALSE;
 325
 326    return ret;
 327 }
 328
 329 /**
 330  * Returns the number of the current node.
 331  * @param  list The list to return the number of the current node.
 332  * @return The number of the current node in the list.
 333  */
 334 EAPI int
 335 ecore_list_index(Ecore_List *list)
 336 {
 337    int ret;
 338
 339    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
 340
 341    ret = list->index;
 342
 343    return ret;
 344 }
 345
 346 /**
 347  * Find the number of nodes in the list.
 348  * @param  list The list to find the number of nodes
 349  * @return The number of nodes in the list.
 350  */
 351 EAPI int
 352 ecore_list_count(Ecore_List *list)
 353 {
 354    int ret = 0;
 355
 356    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
 357
 358    ret = list->nodes;
 359
 360    return ret;
 361 }
 362
 363 /**
 364 @defgroup Ecore_Data_List_Add_Item_Group List Item Adding Functions
 365
 366 Functions that are used to add nodes to an Ecore_List.
 367 */
 368
 369 /**
 370  * Append data to the list.
 371  * @param   list The list.
 372  * @param   data The data to append.
 373  * @return  @c FALSE if an error occurs, @c TRUE if appended successfully
 374  * @ingroup Ecore_Data_List_Add_Item_Group
 375  */
 376 EAPI inline int
 377 ecore_list_append(Ecore_List *list, void *data)
 378 {
 379    int ret;
 380    Ecore_List_Node *node;
 381
 382    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
 383
 384    node = ecore_list_node_new();
 385    node->data = data;
 386
 387    ret = _ecore_list_append_0(list, node);
 388
 389    return ret;
 390 }
 391
 392 /* For adding items to the end of the list */
 393 static int
 394 _ecore_list_append_0(Ecore_List *list, Ecore_List_Node *end)
 395 {
 396    if (list->last)
 397      list->last->next = end;
 398
 399    list->last = end;
 400
 401    if (list->first == NULL)
 402      {
 403         list->first = end;
 404         list->index = 0;
 405         list->current = NULL;
 406      }
 407
 408    if (list->index >= list->nodes)
 409      list->index++;
 410
 411    list->nodes++;
 412
 413    return TRUE;
 414 }
 415
 416 /**
 417  * Prepend data to the beginning of the list.
 418  * @param  list The list.
 419  * @param  data The data to prepend.
 420  * @return @c FALSE if an error occurs, @c TRUE if prepended successfully.
 421  * @ingroup Ecore_Data_List_Add_Item_Group
 422  */
 423 EAPI inline int
 424 ecore_list_prepend(Ecore_List *list, void *data)
 425 {
 426    int ret;
 427    Ecore_List_Node *node;
 428
 429    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
 430
 431    node = ecore_list_node_new();
 432    node->data = data;
 433
 434    ret = _ecore_list_prepend_0(list, node);
 435
 436    return ret;
 437 }
 438
 439 /* For adding items to the beginning of the list */
 440 static int
 441 _ecore_list_prepend_0(Ecore_List *list, Ecore_List_Node *start)
 442 {
 443    /* Put it at the beginning of the list */
 444    start->next = list->first;
 445
 446    list->first = start;
 447
 448    /* If no last node, then the first node is the last node */
 449    if (list->last == NULL)
 450      list->last = list->first;
 451
 452    list->nodes++;
 453    list->index++;
 454
 455    return TRUE;
 456 }
 457
 458 /**
 459  * Insert data in front of the current point in the list.
 460  * @param   list The list to hold the inserted @p data.
 461  * @param   data The data to insert into @p list.
 462  * @return  @c FALSE if there is an error, @c TRUE on success
 463  * @ingroup Ecore_Data_List_Add_Item_Group
 464  */
 465 EAPI inline int
 466 ecore_list_insert(Ecore_List *list, void *data)
 467 {
 468    int ret;
 469    Ecore_List_Node *node;
 470
 471    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
 472
 473    node = ecore_list_node_new();
 474    node->data = data;
 475
 476    ret = _ecore_list_insert(list, node);
 477
 478    return ret;
 479 }
 480
 481 /* For adding items in front of the current position in the list */
 482 static int
 483 _ecore_list_insert(Ecore_List *list, Ecore_List_Node *new_node)
 484 {
 485    /*
 486     * If the current point is at the beginning of the list, then it's the
 487     * same as prepending it to the list.
 488     */
 489    if (list->current == list->first)
 490      return _ecore_list_prepend_0(list, new_node);
 491
 492    if (list->current == NULL)
 493      {
 494         int ret_value;
 495
 496         ret_value = _ecore_list_append_0(list, new_node);
 497         list->current = list->last;
 498
 499         return ret_value;
 500      }
 501
 502    /* Setup the fields of the new node */
 503    new_node->next = list->current;
 504
 505    /* And hook the node into the list */
 506    _ecore_list_index_goto(list, ecore_list_index(list) - 1);
 507
 508    list->current->next = new_node;
 509
 510    /* Now move the current item to the inserted item */
 511    list->current = new_node;
 512    list->nodes++;
 513
 514    return TRUE;
 515 }
 516 /**
 517  * Append a list to the list.
 518  * @param   list The list.
 519  * @param   append The list to append.
 520  * @return  @c FALSE if an error occurs, @c TRUE if appended successfully
 521  * @ingroup Ecore_Data_List_Add_Item_Group
 522  */
 523
 524 EAPI int
 525 ecore_list_append_list(Ecore_List *list, Ecore_List *append)
 526 {
 527    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
 528    CHECK_PARAM_POINTER_RETURN("append", append, FALSE);
 529
 530    if (ecore_list_empty_is(append)) return TRUE;
 531
 532    if (ecore_list_empty_is(list))
 533      {
 534         list->first = append->first;
 535         list->current = list->first;
 536         list->last = append->last;
 537         list->nodes = append->nodes;
 538      }
 539    else
 540      {
 541         list->last->next = append->first;
 542         list->last = append->last;
 543         list->nodes += append->nodes;
 544      }
 545    ecore_list_init(append);
 546    return TRUE;
 547 }
 548
 549 /**
 550  * Prepend a list to the beginning of the list.
 551  * @param  list The list.
 552  * @param  prepend The list to prepend.
 553  * @return @c FALSE if an error occurs, @c TRUE if prepended successfully.
 554  * @ingroup Ecore_Data_List_Add_Item_Group
 555  */
 556 EAPI int
 557 ecore_list_prepend_list(Ecore_List *list, Ecore_List *prepend)
 558 {
 559    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
 560    CHECK_PARAM_POINTER_RETURN("prepend", prepend, FALSE);
 561
 562    if (ecore_list_empty_is(prepend)) return TRUE;
 563
 564    if (ecore_list_empty_is(list))
 565      {
 566         list->first = prepend->first;
 567         list->current = NULL;
 568         list->last = prepend->last;
 569         list->nodes = prepend->nodes;
 570      }
 571    else
 572      {
 573         prepend->last->next = list->first;
 574         list->first = prepend->first;
 575         list->nodes += prepend->nodes;
 576         list->index += prepend->nodes;
 577      }
 578    ecore_list_init(prepend);
 579    return TRUE;
 580 }
 581
 582 /**
 583 @defgroup Ecore_Data_List_Remove_Item_Group List Item Removing Functions
 584
 585 Functions that remove nodes from an Ecore_List.
 586 */
 587
 588 /**
 589  * Remove the current item from the list.
 590  * @param   list The list to remove the current item
 591  * @return  A pointer to the removed data on success, @c NULL on failure.
 592  * @ingroup Ecore_Data_List_Remove_Item_Group
 593  */
 594 EAPI inline void *
 595 ecore_list_remove(Ecore_List *list)
 596 {
 597    void *ret;
 598
 599    CHECK_PARAM_POINTER_RETURN("list", list, NULL);
 600
 601    ret = _ecore_list_remove_0(list);
 602
 603    return ret;
 604 }
 605
 606 /* Remove the current item from the list */
 607 static void *
 608 _ecore_list_remove_0(Ecore_List *list)
 609 {
 610    void *ret = NULL;
 611    Ecore_List_Node *old;
 612
 613    if (!list)
 614      return NULL;
 615
 616    if (ecore_list_empty_is(list))
 617      return NULL;
 618
 619    if (!list->current)
 620      return NULL;
 621
 622    if (list->current == list->first)
 623      return _ecore_list_first_remove(list);
 624
 625    if (list->current == list->last)
 626      return _ecore_list_last_remove(list);
 627
 628    old = list->current;
 629
 630    _ecore_list_index_goto(list, list->index - 1);
 631
 632    list->current->next = old->next;
 633    old->next = NULL;
 634    ret = old->data;
 635    old->data = NULL;
 636
 637    _ecore_list_next(list);
 638
 639    ecore_list_node_destroy(old, NULL);
 640    list->nodes--;
 641
 642    return ret;
 643 }
 644
 645 /**
 646  * Remove and free the data in lists current position.
 647  * @param   list The list to remove and free the current item.
 648  * @return  @c TRUE on success, @c FALSE on error
 649  * @ingroup Ecore_Data_List_Remove_Item_Group
 650  */
 651 EAPI int
 652 ecore_list_remove_destroy(Ecore_List *list)
 653 {
 654    void *data;
 655
 656    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
 657
 658    data = _ecore_list_remove_0(list);
 659    if (list->free_func)
 660      list->free_func(data);
 661
 662    return TRUE;
 663 }
 664
 665 /**
 666  * Remove the first item from the list.
 667  * @param   list The list to remove the current item
 668  * @return  Returns a pointer to the removed data on success, @c NULL on
 669  *          failure.
 670  * @ingroup Ecore_Data_List_Remove_Item_Group
 671  */
 672 EAPI inline void *
 673 ecore_list_first_remove(Ecore_List *list)
 674 {
 675    void *ret;
 676
 677    CHECK_PARAM_POINTER_RETURN("list", list, NULL);
 678
 679    ret = _ecore_list_first_remove(list);
 680
 681    return ret;
 682 }
 683
 684 /* Remove the first item from the list */
 685 static void *
 686 _ecore_list_first_remove(Ecore_List *list)
 687 {
 688    void *ret = NULL;
 689    Ecore_List_Node *old;
 690
 691    if (!list)
 692      return NULL;
 693
 694    if (ecore_list_empty_is(list))
 695      return NULL;
 696
 697    old = list->first;
 698
 699    list->first = list->first->next;
 700
 701    if (list->current == old)
 702      list->current = list->first;
 703    else
 704      (list->index ? list->index-- : 0);
 705
 706    if (list->last == old)
 707      list->last = list->first;
 708
 709    ret = old->data;
 710    old->data = NULL;
 711
 712    ecore_list_node_destroy(old, NULL);
 713    list->nodes--;
 714
 715    return ret;
 716 }
 717
 718 /**
 719  * Remove the last item from the list.
 720  * @param   list The list to remove the last node from
 721  * @return  A pointer to the removed data on success, @c NULL on failure.
 722  * @ingroup Ecore_Data_List_Remove_Item_Group
 723  */
 724 EAPI inline void *
 725 ecore_list_last_remove(Ecore_List *list)
 726 {
 727    void *ret;
 728
 729    CHECK_PARAM_POINTER_RETURN("list", list, NULL);
 730
 731    ret = _ecore_list_last_remove(list);
 732
 733    return ret;
 734 }
 735
 736 /* Remove the last item from the list */
 737 static void *
 738 _ecore_list_last_remove(Ecore_List *list)
 739 {
 740    void *ret = NULL;
 741    Ecore_List_Node *old, *prev;
 742
 743    if (!list)
 744      return NULL;
 745
 746    if (ecore_list_empty_is(list))
 747      return NULL;
 748
 749    old = list->last;
 750    if (list->current == old)
 751      list->current = NULL;
 752
 753    if (list->first == old)
 754      list->first = NULL;
 755    for (prev = list->first; prev && prev->next != old; prev = prev->next);
 756    list->last = prev;
 757    if (prev)
 758      prev->next = NULL;
 759
 760    old->next = NULL;
 761    ret = old->data;
 762    old->data = NULL;
 763
 764    ecore_list_node_destroy(old, NULL);
 765    list->nodes--;
 766
 767    return ret;
 768 }
 769
 770 /**
 771 @defgroup Ecore_Data_List_Traverse_Group List Traversal Functions
 772
 773 Functions that can be used to traverse an Ecore_List.
 774 */
 775
 776 /**
 777  * Make the current item the item with the given index number.
 778  * @param   list  The list.
 779  * @param   index The position to move the current item.
 780  * @return  A pointer to new current item on success, @c NULL on failure.
 781  * @ingroup Ecore_Data_List_Traverse_Group
 782  */
 783 EAPI inline void *
 784 ecore_list_index_goto(Ecore_List *list, int index)
 785 {
 786    void *ret;
 787
 788    CHECK_PARAM_POINTER_RETURN("list", list, NULL);
 789
 790    ret = _ecore_list_index_goto(list, index);
 791
 792    return ret;
 793 }
 794
 795 /* This is the non-threadsafe version, use this inside internal functions that
 796  * already lock the list */
 797 static void *
 798 _ecore_list_index_goto(Ecore_List *list, int index)
 799 {
 800    int i;
 801
 802    if (!list)
 803      return NULL;
 804
 805    if (ecore_list_empty_is(list))
 806      return NULL;
 807
 808    if (index > ecore_list_count(list) || index < 0)
 809      return NULL;
 810
 811    if (index < list->index)
 812      {
 813         _ecore_list_first_goto(list);
 814         i = 0;
 815      }
 816    else
 817      i = list->index;
 818
 819    for (; i < index && _ecore_list_next(list); i++);
 820
 821    if (i >= list->nodes)
 822      return NULL;
 823
 824    list->index = i;
 825
 826    return list->current->data;
 827 }
 828
 829 /**
 830  * Make the current item the node that contains @p data.
 831  * @param   list The list.
 832  * @param   data The data to find.
 833  * @return  A pointer to @p data on success, @c NULL on failure.
 834  * @ingroup Ecore_Data_List_Traverse_Group
 835  */
 836 EAPI inline void *
 837 ecore_list_goto(Ecore_List *list, const void *data)
 838 {
 839    void *ret;
 840
 841    CHECK_PARAM_POINTER_RETURN("list", list, NULL);
 842
 843    ret = _ecore_list_goto(list, data);
 844
 845    return ret;
 846 }
 847
 848 /* Set the current position to the node containing data */
 849 static void *
 850 _ecore_list_goto(Ecore_List *list, const void *data)
 851 {
 852    int index;
 853    Ecore_List_Node *node;
 854
 855    if (!list)
 856      return NULL;
 857
 858    index = 0;
 859
 860    node = list->first;
 861    while (node && node->data)
 862      {
 863         Ecore_List_Node *next;
 864
 865         if (node->data == data)
 866           break;
 867
 868         next = node->next;
 869
 870         node = next;
 871
 872         index++;
 873      }
 874
 875    if (!node)
 876      return NULL;
 877
 878    list->current = node;
 879    list->index = index;
 880
 881    return list->current->data;
 882 }
 883
 884 /**
 885  * Make the current item the first item in the list
 886  * @param   list The list.
 887  * @return  A pointer to the first item on success, @c NULL on failure
 888  * @ingroup Ecore_Data_List_Traverse_Group
 889  */
 890 EAPI inline void *
 891 ecore_list_first_goto(Ecore_List *list)
 892 {
 893    void *ret;
 894
 895    CHECK_PARAM_POINTER_RETURN("list", list, NULL);
 896
 897    ret = _ecore_list_first_goto(list);
 898
 899    return ret;
 900 }
 901
 902 /* Set the current position to the start of the list */
 903 static void *
 904 _ecore_list_first_goto(Ecore_List *list)
 905 {
 906    if (!list || !list->first)
 907      return NULL;
 908
 909    list->current = list->first;
 910    list->index = 0;
 911
 912    return list->current->data;
 913 }
 914
 915 /**
 916  * Make the current item the last item in the list.
 917  * @param   list The list.
 918  * @return  A pointer to the last item on success, @c NULL on failure.
 919  * @ingroup Ecore_Data_List_Traverse_Group
 920  */
 921 EAPI inline void *
 922 ecore_list_last_goto(Ecore_List *list)
 923 {
 924    void *ret;
 925
 926    CHECK_PARAM_POINTER_RETURN("list", list, NULL);
 927
 928    ret = _ecore_list_last_goto(list);
 929
 930    return ret;
 931 }
 932
 933 /* Set the current position to the end of the list */
 934 static void *
 935 _ecore_list_last_goto(Ecore_List *list)
 936 {
 937    if (!list || !list->last)
 938      return NULL;
 939
 940    list->current = list->last;
 941    list->index = (list->nodes - 1);
 942
 943    return list->current->data;
 944 }
 945
 946 /**
 947  * Retrieve the data pointed to by the current item in @p list.
 948  * @param  list The list.
 949  * @return Returns the data at current position, can be @c NULL.
 950  */
 951 EAPI inline void *
 952 ecore_list_current(Ecore_List *list)
 953 {
 954    void *ret;
 955
 956    ret = _ecore_list_current(list);
 957
 958    return ret;
 959 }
 960
 961 /**
 962  * Retrieve the data pointed to by the first item in @p list.
 963  * @param  list The list.
 964  * @return Returns the data at current position, can be @c NULL.
 965  */
 966 EAPI inline void *
 967 ecore_list_first(Ecore_List *list)
 968 {
 969    void *ret;
 970
 971    if (!list->first)
 972      return NULL;
 973    ret = list->first->data;
 974
 975    return ret;
 976 }
 977
 978 /**
 979  * Retrieve the data pointed to by the last item in @p list.
 980  * @param  list The list.
 981  * @return Returns the data at current position, can be @c NULL.
 982  */
 983 EAPI inline void *
 984 ecore_list_last(Ecore_List *list)
 985 {
 986    void *ret;
 987
 988    if (!list->last)
 989      return NULL;
 990    ret = list->last->data;
 991
 992    return ret;
 993 }
 994
 995 /* Return the data of the current node without incrementing */
 996 static void *
 997 _ecore_list_current(Ecore_List *list)
 998 {
 999    void *ret;
1000
1001    if (!list->current)
1002      return NULL;
1003
1004    ret = list->current->data;
1005
1006    return ret;
1007 }
1008
1009 /**
1010  * Retrieve the data pointed to by the current item, and make the next item
1011  * the current item.
1012  * @param   list The list to retrieve data from.
1013  * @return  The current item in the list on success, @c NULL on failure.
1014  */
1015 EAPI inline void *
1016 ecore_list_next(Ecore_List *list)
1017 {
1018    void *data;
1019
1020    CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1021
1022    data = _ecore_list_next(list);
1023
1024    return data;
1025 }
1026
1027 /* Return the data contained in the current node and go to the next node */
1028 static void *
1029 _ecore_list_next(Ecore_List *list)
1030 {
1031    void *data;
1032    Ecore_List_Node *ret;
1033    Ecore_List_Node *next;
1034
1035    if (!list->current)
1036      return NULL;
1037
1038    ret = list->current;
1039    next = list->current->next;
1040
1041    list->current = next;
1042    list->index++;
1043
1044    data = ret->data;
1045
1046    return data;
1047 }
1048
1049 /**
1050  * Remove all nodes from @p list.
1051  * @param  list The list.
1052  * @return Returns @c TRUE on success, @c FALSE on error.
1053  * @note The data for each item on the list is not freed by
1054  *       @c ecore_list_clear().
1055  */
1056 EAPI int
1057 ecore_list_clear(Ecore_List *list)
1058 {
1059    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1060
1061    while (!ecore_list_empty_is(list))
1062      _ecore_list_first_remove(list);
1063
1064    return TRUE;
1065 }
1066
1067 /**
1068  * Execute function for each node in @p list.
1069  * @param   list     The list.
1070  * @param   function The function to pass each node from @p list to.
1071  * @return  Returns @c TRUE on success, @c FALSE on failure.
1072  * @ingroup Ecore_Data_List_Traverse_Group
1073  */
1074 EAPI int
1075 ecore_list_for_each(Ecore_List *list, Ecore_For_Each function, void *user_data)
1076 {
1077    int ret;
1078
1079    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1080
1081    ret = _ecore_list_for_each(list, function, user_data);
1082
1083    return ret;
1084 }
1085
1086 /* The real meat of executing the function for each data node */
1087 static int
1088 _ecore_list_for_each(Ecore_List *list, Ecore_For_Each function, void *user_data)
1089 {
1090    void *value;
1091
1092    if (!list || !function)
1093      return FALSE;
1094
1095    _ecore_list_first_goto(list);
1096    while ((value = _ecore_list_next(list)) != NULL)
1097      function(value, user_data);
1098
1099    return TRUE;
1100 }
1101
1102 /**
1103  * Find data in @p list using the compare function @p func
1104  * @param list      The list.
1105  * @param function  The function to test each node of @p list with
1106  * @param user_data Data to match against (used by @p function)
1107  * @return the first matching data node, or NULL if none match
1108  */
1109 EAPI void *
1110 ecore_list_find(Ecore_List *list, Ecore_Compare_Cb function, const void *user_data)
1111 {
1112   CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1113
1114   return _ecore_list_find(list, function, user_data);
1115 }
1116
1117 /* The real meat of finding a node via a compare cb */
1118 static void *
1119 _ecore_list_find(Ecore_List *list, Ecore_Compare_Cb function, const void *user_data)
1120 {
1121   void *value;
1122   if (!list || !function) return NULL;
1123
1124   _ecore_list_first_goto(list);
1125   while ((value = _ecore_list_current(list)) != NULL)
1126   {
1127     if (!function(value, user_data)) return value;
1128     ecore_list_next(list);
1129   }
1130
1131   return NULL;
1132 }
1133
1134 /**
1135  * Sort data in @p list using the compare function @p compare
1136  * @param list      The list.
1137  * @param compare   The function to compare the data of @p list
1138  * @param order     The sort direction, possible values are ECORE_SORT_MIN and
1139  *                  ECORE_SORT_MAX
1140  * @return          true on success
1141  *
1142  * This is a wrapper function for mergesort and heapsort. It
1143  * tries to choose the fastest algorithm depending on the
1144  * number of notes. Note: The sort may be unstable.
1145  */
1146 EAPI int
1147 ecore_list_sort(Ecore_List *list, Ecore_Compare_Cb compare, char order)
1148 {
1149    CHECK_PARAM_POINTER_RETURN("list", list, 0);
1150
1151    if (list->nodes < 2)
1152      return 1;
1153    if (list->nodes < ECORE_MERGESORT_LIMIT)
1154      return ecore_list_mergesort(list, compare, order);
1155    if (!ecore_list_heapsort(list, compare, order))
1156      return ecore_list_mergesort(list, compare, order);
1157
1158    return 1;
1159 }
1160
1161 /**
1162  * Sort data in @p list using the compare function @p compare
1163  * @param list      The list.
1164  * @param compare   The function to compare the data of @p list
1165  * @param order     The sort direction, possible values are ECORE_SORT_MIN and
1166  *                  ECORE_SORT_MAX
1167  * @return          true on success
1168  *
1169  * Mergesort is a stable, in-place sorting algorithm
1170  */
1171 EAPI int
1172 ecore_list_mergesort(Ecore_List *list, Ecore_Compare_Cb compare, char order)
1173 {
1174    Ecore_List_Node *node;
1175
1176    CHECK_PARAM_POINTER_RETURN("list", list, 0);
1177    if (list->nodes < 2)
1178      return 1;
1179
1180    if (order == ECORE_SORT_MIN)
1181      order = 1;
1182    else
1183      order = -1;
1184
1185    node = _ecore_list_node_mergesort(list->first, list->nodes, compare, order);
1186    list->first = node;
1187
1188    /* maybe there is a better way to do that but our last node has changed */
1189    while (node->next)
1190      node = node->next;
1191    list->last = node;
1192
1193    _ecore_list_first_goto(list);
1194
1195    return 1;
1196 }
1197
1198 /**
1199  * Merge the @p l2 into the @p list using the compare function @p compare.
1200  * Both lists need to be sorted else a corrupt list could be the result.
1201  * @param list      The list.
1202  * @param l2        The second list, this list will be empty after the merge
1203  * @param compare   The function to compare the data of @p list and @p l2
1204  * @param order     The sort direction, possible values are ECORE_SORT_MIN and
1205  *                  ECORE_SORT_MAX
1206  */
1207 EAPI void
1208 ecore_list_merge(Ecore_List *list, Ecore_List *l2, Ecore_Compare_Cb compare, char order)
1209 {
1210    CHECK_PARAM_POINTER("list", list);
1211    CHECK_PARAM_POINTER("l2", l2);
1212
1213    if (ecore_list_empty_is(l2)) return;
1214
1215    if (ecore_list_empty_is(list))
1216      {
1217        ecore_list_append_list(list, l2);
1218        return;
1219      }
1220
1221    if (order == ECORE_SORT_MIN)
1222      order = 1;
1223    else
1224      order = -1;
1225
1226    list->first = _ecore_list_node_merge(list->first, l2->first, compare, order);
1227
1228    if ((order * compare(list->last->data, l2->last->data)) < 0)
1229      list->last = l2->last;
1230
1231    list->nodes += l2->nodes;
1232    ecore_list_init(l2);
1233 }
1234
1235 /* this is the internal recrusive function for the merge sort */
1236 static Ecore_List_Node *
1237 _ecore_list_node_mergesort(Ecore_List_Node *first, int n,
1238                            Ecore_Compare_Cb compare, int order)
1239 {
1240    Ecore_List_Node *middle;
1241    Ecore_List_Node *premid;
1242    int mid;
1243    int i;
1244
1245    mid = n / 2;
1246
1247    if (n < 2)
1248      return first;
1249    else if (n == 2)
1250      {
1251         if (compare(first->data, first->next->data) * order > 0)
1252           {
1253                 /* swap the data */
1254                 void *data;
1255                 data = first->next->data;
1256                 first->next->data = first->data;
1257                 first->data = data;
1258           }
1259       return first;
1260     }
1261
1262    /* first find the premiddle node*/
1263    for (premid = first, i = 0; i < mid - 1; i++)
1264      premid = premid->next;
1265
1266    /* split the list */
1267    middle = premid->next;
1268    premid->next = NULL;
1269
1270    /* sort the the partial lists */
1271    first = _ecore_list_node_mergesort(first, mid, compare, order);
1272    middle = _ecore_list_node_mergesort(middle, n - mid, compare, order);
1273
1274    return _ecore_list_node_merge(first, middle, compare, order);
1275 }
1276
1277 /* this function is used to merge the partial sorted lists */
1278 static Ecore_List_Node *
1279 _ecore_list_node_merge(Ecore_List_Node *first, Ecore_List_Node *second,
1280                        Ecore_Compare_Cb compare, int order)
1281 {
1282    Ecore_List_Node *list;
1283    Ecore_List_Node *l;
1284
1285    /* select the first node outside the loop, because we need to keep
1286     * a pointer to it */
1287    if (compare(first->data, second->data) * order > 0)
1288      {
1289         list = l = second;
1290         second = second->next;
1291      }
1292    else
1293      {
1294         list = l = first;
1295         first = first->next;
1296      }
1297
1298    /* and now start the merging */
1299    while (first && second)
1300      {
1301         if (compare(first->data, second->data) * order > 0)
1302           {
1303                 l = l->next = second;
1304                 second = second->next;
1305           }
1306         else
1307           {
1308                 l = l->next = first;
1309                 first = first->next;
1310           }
1311      }
1312
1313    /* append the rest or set it to NULL */
1314    if (first)
1315      l->next = first;
1316    else if (second)
1317      l->next = second;
1318    else
1319      l->next = NULL;
1320
1321    return list;
1322 }
1323
1324 /**
1325  * Sort data in @p list using the compare function @p compare
1326  * @param list      The list.
1327  * @param compare   The function to compare the data of @p list
1328  * @param order     The sort direction, possible values are ECORE_SORT_MIN and
1329  *                  ECORE_SORT_MAX
1330  * @return          true on success
1331  *
1332  * Heapsort is a unstable sorting algorithm, it needs to allocate extra memomry,
1333  * but there for it is for a great number of nodes faster than mergesort
1334  */
1335 EAPI int
1336 ecore_list_heapsort(Ecore_List *list, Ecore_Compare_Cb compare, char order)
1337 {
1338    Ecore_Sheap *heap;
1339    Ecore_List_Node *node;
1340    void *data;
1341
1342    CHECK_PARAM_POINTER_RETURN("list", list, 0);
1343    /*
1344     * Push the data into a heap.
1345     */
1346    heap = ecore_sheap_new(compare, list->nodes);
1347    if (!heap)
1348      return 0;
1349
1350    ecore_sheap_order_set(heap, order);
1351    _ecore_list_first_goto(list);
1352    while ((data = _ecore_list_next(list)))
1353      {
1354         ecore_sheap_insert(heap, data);
1355      }
1356
1357    /*
1358     * Extract in sorted order.
1359     */
1360    node = list->first;
1361    while (node)
1362      {
1363         node->data = ecore_sheap_extract(heap);
1364         node = node->next;
1365      }
1366
1367    ecore_sheap_destroy(heap);
1368
1369    _ecore_list_first_goto(list);
1370    return 1;
1371 }
1372
1373 /* Initialize a node to starting values */
1374 EAPI int
1375 ecore_list_node_init(Ecore_List_Node *node)
1376 {
1377    CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
1378
1379    node->next = NULL;
1380    node->data = NULL;
1381
1382    return TRUE;
1383 }
1384
1385 /**
1386 @defgroup Ecore_Data_List_Node_Group List Node Functions
1387
1388 Functions that are used in the creation, maintenance and destruction of
1389 Ecore_List nodes.
1390 */
1391
1392 /**
1393  * Allocates and initializes a new list node.
1394  * @return  A new Ecore_List_Node on success, @c NULL otherwise.
1395  * @ingroup Ecore_Data_List_Node_Group
1396  */
1397 EAPI Ecore_List_Node *
1398 ecore_list_node_new()
1399 {
1400    Ecore_List_Node *new_node;
1401
1402    new_node = malloc(sizeof(Ecore_List_Node));
1403
1404    if (!ecore_list_node_init(new_node))
1405      {
1406         FREE(new_node);
1407         return NULL;
1408      }
1409
1410    return new_node;
1411 }
1412
1413 /**
1414  * Calls the function to free the data and the node.
1415  * @param   node      Node to destroy.
1416  * @param   free_func Function to call if @p node points to data to free.
1417  * @return  @c TRUE.
1418  * @ingroup Ecore_Data_List_Node_Group
1419  */
1420 EAPI int
1421 ecore_list_node_destroy(Ecore_List_Node *node, Ecore_Free_Cb free_func)
1422 {
1423    CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
1424
1425    if (free_func && node->data)
1426      free_func(node->data);
1427
1428    FREE(node);
1429
1430    return TRUE;
1431 }
1432
1433 /**
1434  * @defgroup Ecore_Data_DList_Creation_Group Doubly Linked List Creation/Destruction Functions
1435  *
1436  * Functions used to create, initialize and destroy @c Ecore_DLists.
1437  */
1438
1439 /**
1440  * Creates and initialises a new doubly linked list.
1441  * @return  A new initialised doubly linked list on success, @c NULL
1442  *          on failure.
1443  * @ingroup Ecore_Data_DList_Creation_Group
1444  */
1445 EAPI Ecore_DList *
1446 ecore_dlist_new()
1447 {
1448    Ecore_DList *list = NULL;
1449
1450    list = (Ecore_DList *)malloc(sizeof(Ecore_DList));
1451    if (!list)
1452      return NULL;
1453
1454    if (!ecore_dlist_init(list))
1455      {
1456         IF_FREE(list);
1457         return NULL;
1458      }
1459
1460    return list;
1461 }
1462
1463 /**
1464  * Initialises a list to some sane starting values.
1465  * @param   list The doubly linked list to initialise.
1466  * @return  @c TRUE if successful, @c FALSE if an error occurs.
1467  * @ingroup Ecore_Data_DList_Creation_Group
1468  */
1469 EAPI int
1470 ecore_dlist_init(Ecore_DList *list)
1471 {
1472    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1473
1474    memset(list, 0, sizeof(Ecore_DList));
1475
1476    return TRUE;
1477 }
1478
1479 /**
1480  * Frees a doubly linked list and all of its nodes.
1481  * @param   list The doubly linked list to be freed.
1482  * @ingroup Ecore_Data_DList_Creation_Group
1483  */
1484 EAPI void
1485 ecore_dlist_destroy(Ecore_DList *list)
1486 {
1487    void *data;
1488    CHECK_PARAM_POINTER("list", list);
1489
1490    while (list->first)
1491      {
1492         data = _ecore_dlist_first_remove(list);
1493         if (list->free_func)
1494           list->free_func(data);
1495      }
1496
1497    FREE(list);
1498 }
1499
1500 /**
1501  * Sets the function used for freeing data stored in a doubly linked list.
1502  * @param   list      The doubly linked list that will use this function when
1503  *                    nodes are destroyed.
1504  * @param   free_func The function that will free the key data
1505  * @return  @c TRUE on success, @c FALSE on failure.
1506  * @ingroup Ecore_Data_DList_Creation_Group
1507  */
1508 EAPI int
1509 ecore_dlist_free_cb_set(Ecore_DList *list, Ecore_Free_Cb free_func)
1510 {
1511    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1512
1513    return ecore_list_free_cb_set(ECORE_LIST(list), free_func);
1514 }
1515
1516 /**
1517  * Returns whether there is anything in the given doubly linked list.
1518  * @param  list The given doubly linked list.
1519  * @return @c TRUE if there are nodes, @c FALSE otherwise.
1520  */
1521 EAPI int
1522 ecore_dlist_empty_is(Ecore_DList *list)
1523 {
1524    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1525
1526    return ecore_list_empty_is(ECORE_LIST(list));
1527 }
1528
1529 /**
1530  * Retrieves the index of the current node of the given doubly linked list.
1531  * @param  list The given doubly linked list.
1532  * @return The index of the current node.
1533  */
1534 EAPI inline int
1535 ecore_dlist_index(Ecore_DList *list)
1536 {
1537    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1538
1539    return ecore_list_index(ECORE_LIST(list));
1540 }
1541
1542 /**
1543  * @defgroup Ecore_Data_DList_Add_Item_Group Doubly Linked List Adding Functions
1544  *
1545  * Functions that are used to add nodes to an Ecore_DList.
1546  */
1547
1548 /**
1549  * Appends data to the given doubly linked list.
1550  * @param   list The given doubly linked list.
1551  * @param   data The data to append.
1552  * @return  @c TRUE if the data is successfully appended, @c FALSE otherwise.
1553  * @ingroup Ecore_Data_DList_Add_Item_Group
1554  */
1555 EAPI int
1556 ecore_dlist_append(Ecore_DList *list, void *data)
1557 {
1558    int ret;
1559    Ecore_DList_Node *prev;
1560    Ecore_DList_Node *node;
1561
1562    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1563
1564    node = ecore_dlist_node_new();
1565    ECORE_LIST_NODE(node)->data = data;
1566
1567    prev = ECORE_DLIST_NODE(ECORE_LIST(list)->last);
1568    ret = _ecore_list_append_0(ECORE_LIST(list), ECORE_LIST_NODE(node));
1569    if (ret)
1570      node->previous = prev;
1571
1572    return ret;
1573 }
1574
1575 /**
1576  * Adds data to the very beginning of the given doubly linked list.
1577  * @param   list The given doubly linked list.
1578  * @param   data The data to prepend.
1579  * @return  @c TRUE if the data is successfully prepended, @c FALSE otherwise.
1580  * @ingroup Ecore_Data_DList_Add_Item_Group
1581  */
1582 EAPI int
1583 ecore_dlist_prepend(Ecore_DList *list, void *data)
1584 {
1585    int ret;
1586    Ecore_DList_Node *prev;
1587    Ecore_DList_Node *node;
1588
1589    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1590
1591    node = ecore_dlist_node_new();
1592    ECORE_LIST_NODE(node)->data = data;
1593
1594    prev = ECORE_DLIST_NODE(ECORE_LIST(list)->first);
1595    ret = _ecore_list_prepend_0(ECORE_LIST(list), ECORE_LIST_NODE(node));
1596    if (ret && prev)
1597      prev->previous = node;
1598
1599    return ret;
1600 }
1601
1602 /**
1603  * Inserts data at the current point in the given doubly linked list.
1604  * @param   list The given doubly linked list.
1605  * @param   data The data to be inserted.
1606  * @return  @c TRUE on success, @c FALSE otherwise.
1607  * @ingroup Ecore_Data_DList_Add_Item_Group
1608  */
1609 EAPI int
1610 ecore_dlist_insert(Ecore_DList *list, void *data)
1611 {
1612    int ret = TRUE;
1613    Ecore_DList_Node *prev;
1614    Ecore_DList_Node *node;
1615
1616    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1617
1618    /*
1619     * Identify and shortcut the end cases.
1620     */
1621    if (!ECORE_LIST(list)->current)
1622      return ecore_dlist_append(list, data);
1623    if (ECORE_LIST(list)->current == ECORE_LIST(list)->first)
1624      return ecore_dlist_prepend(list, data);
1625
1626    node = ecore_dlist_node_new();
1627    ECORE_LIST_NODE(node)->data = data;
1628
1629    /* Setup the fields of the new node */
1630    ECORE_LIST_NODE(node)->next = ECORE_LIST(list)->current;
1631
1632    /* And hook the node into the list */
1633    prev = ECORE_DLIST_NODE(ECORE_LIST(list)->current)->previous;
1634    ECORE_LIST_NODE(prev)->next = ECORE_LIST_NODE(node);
1635    ECORE_DLIST_NODE(ECORE_LIST(list)->current)->previous = node;
1636    node->previous = prev;
1637
1638    /* Now move the current item to the inserted item */
1639    ECORE_LIST(list)->current = ECORE_LIST_NODE(node);
1640    ECORE_LIST(list)->nodes++;
1641
1642    return ret;
1643 }
1644
1645 /**
1646  * Appends a list to the given doubly linked list.
1647  * @param   list The given doubly linked list.
1648  * @param   append The list to append.
1649  * @return  @c TRUE if the data is successfully appended, @c FALSE otherwise.
1650  * @ingroup Ecore_Data_DList_Add_Item_Group
1651  */
1652 EAPI int
1653 ecore_dlist_append_list(Ecore_DList *list, Ecore_DList *append)
1654 {
1655    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1656    CHECK_PARAM_POINTER_RETURN("append", append, FALSE);
1657
1658    if (ecore_dlist_empty_is(append)) return TRUE;
1659
1660    if (ecore_dlist_empty_is(list))
1661      {
1662         list->first = append->first;
1663         list->current = NULL;
1664         list->last = append->last;
1665         list->nodes = append->nodes;
1666      }
1667    else
1668      {
1669         list->last->next = append->first;
1670         ECORE_DLIST_NODE(append->first)->previous = ECORE_DLIST_NODE(list->last);
1671         list->last = append->last;
1672         list->nodes += append->nodes;
1673      }
1674    ecore_dlist_init(append);
1675    return TRUE;
1676 }
1677
1678 /**
1679  * Adds a list to the very beginning of the given doubly linked list.
1680  * @param   list The given doubly linked list.
1681  * @param   prepend The list to prepend.
1682  * @return  @c TRUE if the data is successfully prepended, @c FALSE otherwise.
1683  * @ingroup Ecore_Data_DList_Add_Item_Group
1684  */
1685 EAPI int
1686 ecore_dlist_prepend_list(Ecore_DList *list, Ecore_DList *prepend)
1687 {
1688    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1689    CHECK_PARAM_POINTER_RETURN("prepend", prepend, FALSE);
1690
1691    if (ecore_dlist_empty_is(prepend)) return TRUE;
1692
1693    if (ecore_dlist_empty_is(list))
1694      {
1695         list->first = prepend->first;
1696         list->current = NULL;
1697         list->last = prepend->last;
1698         list->nodes = prepend->nodes;
1699      }
1700    else
1701      {
1702         prepend->last->next = list->first;
1703         ECORE_DLIST_NODE(list->first)->previous = ECORE_DLIST_NODE(prepend->last);
1704         list->first = prepend->first;
1705         list->nodes += prepend->nodes;
1706         list->index += prepend->nodes;
1707      }
1708    ecore_dlist_init(prepend);
1709    return TRUE;
1710 }
1711
1712 /**
1713  * @defgroup Ecore_Data_DList_Remove_Item_Group Doubly Linked List Removing Functions
1714  *
1715  * Functions that remove nodes from an @c Ecore_DList.
1716  */
1717
1718 /**
1719  * Removes the current item from the given doubly linked list.
1720  * @param   list The given doubly linked list.
1721  * @return  A pointer to the removed data on success, @c NULL otherwise.
1722  * @ingroup Ecore_Data_DList_Remove_Item_Group
1723  */
1724 EAPI void *
1725 ecore_dlist_remove(Ecore_DList *list)
1726 {
1727    void *ret;
1728    Ecore_List *l2 = ECORE_LIST(list);
1729    Ecore_DList_Node *node;
1730
1731    CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1732
1733    if (l2->current)
1734      {
1735         node = ECORE_DLIST_NODE(list->current->next);
1736         if (node)
1737           node->previous = ECORE_DLIST_NODE(l2->current)->previous;
1738      }
1739    ret = _ecore_list_remove_0(list);
1740
1741    return ret;
1742 }
1743
1744 /**
1745  * Removes the first item from the given doubly linked list.
1746  * @param   list The given doubly linked list.
1747  * @return  A pointer to the removed data on success, @c NULL on failure.
1748  * @ingroup Ecore_Data_DList_Remove_Item_Group
1749  */
1750 EAPI void *
1751 ecore_dlist_first_remove(Ecore_DList *list)
1752 {
1753    void *ret;
1754
1755    CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1756
1757    ret = _ecore_dlist_first_remove(list);
1758
1759    return ret;
1760 }
1761
1762 /**
1763  * Removes and frees the data at the current position in the given doubly
1764  * linked list.
1765  * @param   list The given doubly linked list.
1766  * @return  @c TRUE on success, @c FALSE otherwise.
1767  * @ingroup Ecore_Data_DList_Remove_Item_Group
1768  */
1769 EAPI int
1770 ecore_dlist_remove_destroy(Ecore_DList *list)
1771 {
1772    void *data;
1773
1774    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1775
1776    data = ecore_dlist_remove(list);
1777    if (!data)
1778      return FALSE;
1779
1780    if (list->free_func)
1781      list->free_func(data);
1782
1783    return TRUE;
1784 }
1785
1786 static void *
1787 _ecore_dlist_first_remove(Ecore_DList *list)
1788 {
1789    void *ret;
1790
1791    if (!list)
1792      return NULL;
1793
1794    ret = _ecore_list_first_remove(list);
1795    if (ret && ECORE_LIST(list)->first)
1796      ECORE_DLIST_NODE(ECORE_LIST(list)->first)->previous = NULL;
1797
1798    return ret;
1799 }
1800
1801 /**
1802  * Removes the last item from the given doubly linked list.
1803  * @param   list The given doubly linked list.
1804  * @return  A pointer to the removed data on success, @c NULL otherwise.
1805  * @ingroup Ecore_Data_DList_Remove_Item_Group
1806  */
1807 EAPI void *
1808 ecore_dlist_last_remove(Ecore_DList *list)
1809 {
1810    void *ret;
1811    Ecore_List_Node *node;
1812
1813    CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1814
1815    if (ecore_list_empty_is(list))
1816      return NULL;
1817
1818    node = list->last;
1819    list->last = ECORE_LIST_NODE(ECORE_DLIST_NODE(node)->previous);
1820    if (list->last)
1821      list->last->next = NULL;
1822    if (list->first == node)
1823      list->first = NULL;
1824    if (list->current == node)
1825      list->current = NULL;
1826
1827    ret = node->data;
1828    ecore_list_node_destroy(node, NULL);
1829
1830    list->nodes--;
1831    if (list->index >= list->nodes)
1832      list->index--;
1833
1834    return ret;
1835 }
1836
1837 /**
1838  * Moves the current item to the index number in the given doubly linked list.
1839  * @param  list  The given doubly linked list.
1840  * @param  index The position to move the current item
1841  * @return The node at specified index on success, @c NULL on error.
1842  */
1843 EAPI void *
1844 ecore_dlist_index_goto(Ecore_DList *list, int index)
1845 {
1846    void *ret;
1847
1848    CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1849
1850    ret = _ecore_dlist_index_goto(list, index);
1851
1852    return ret;
1853 }
1854
1855 /* This is the non-threadsafe version, use this inside internal functions that
1856  * already lock the list */
1857 static void *
1858 _ecore_dlist_index_goto(Ecore_DList *list, int index)
1859 {
1860    int i, increment;
1861
1862    if (!list)
1863      return NULL;
1864
1865    if (ecore_list_empty_is(ECORE_LIST(list)))
1866      return NULL;
1867
1868    if (index > ecore_list_count(ECORE_LIST(list)) || index < 0)
1869      return NULL;
1870
1871    if (ECORE_LIST(list)->index >= ECORE_LIST(list)->nodes)
1872      _ecore_list_last_goto(ECORE_LIST(list));
1873
1874    if (index < ECORE_LIST(list)->index)
1875      increment = -1;
1876    else
1877      increment = 1;
1878
1879    for (i = ECORE_LIST(list)->index; i != index; i += increment)
1880      {
1881         if (increment > 0)
1882           _ecore_list_next(list);
1883         else
1884           _ecore_dlist_previous(list);
1885      }
1886
1887    return _ecore_list_current(list);
1888 }
1889
1890 /**
1891  * @brief Move the current item to the node that contains data
1892  * @param list: the list to move the current item in
1893  * @param data: the data to find and set the current item to
1894  *
1895  * @return Returns specified data on success, NULL on error
1896  */
1897 EAPI void *
1898 ecore_dlist_goto(Ecore_DList *list, void *data)
1899 {
1900    void *ret;
1901
1902    CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1903
1904    ret = _ecore_list_goto(ECORE_LIST(list), data);
1905
1906    return ret;
1907 }
1908
1909 /**
1910  * @brief Move the current pointer to the first item in the list
1911  * @param list: the list to change the current to the first item
1912  *
1913  * @return Returns a pointer to the first item on success, NULL on failure.
1914  */
1915 EAPI void *
1916 ecore_dlist_first_goto(Ecore_DList *list)
1917 {
1918    void *ret;
1919
1920    CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1921
1922    ret = _ecore_list_first_goto(list);
1923
1924    return ret;
1925 }
1926
1927 /**
1928  * @brief Move the pointer to the current item to the last item
1929  * @param list: the list to move the current item pointer to the last
1930  * @return Returns a pointer to the last item in the list , NULL if empty.
1931  */
1932 EAPI void *
1933 ecore_dlist_last_goto(Ecore_DList *list)
1934 {
1935    void *ret;
1936
1937    CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1938
1939    ret = _ecore_list_last_goto(ECORE_LIST(list));
1940
1941    return ret;
1942 }
1943
1944 /**
1945  * @brief Return the data in the current list item
1946  * @param list: the list to the return the current data
1947  * @return Returns value of the current data item, NULL if no current item
1948  */
1949 EAPI void *
1950 ecore_dlist_current(Ecore_DList *list)
1951 {
1952    void *ret;
1953
1954    ret = _ecore_list_current(ECORE_LIST(list));
1955
1956    return ret;
1957 }
1958
1959 /**
1960  * @brief Move to the next item in the list and return current item
1961  * @param list: the list to move to the next item in.
1962  * @return Returns data in the current list node, or NULL on error
1963  */
1964 EAPI void *
1965 ecore_dlist_next(Ecore_DList *list)
1966 {
1967    void *data;
1968
1969    data = _ecore_list_next(list);
1970
1971    return data;
1972 }
1973
1974 /**
1975  * @brief Move to the previous item and return current item
1976  * @param list: the list to move to the previous item in.
1977  * @return Returns data in the current list node, or NULL on error
1978  */
1979 EAPI void *
1980 ecore_dlist_previous(Ecore_DList *list)
1981 {
1982    void *data;
1983
1984    data = _ecore_dlist_previous(list);
1985
1986    return data;
1987 }
1988
1989 static void *
1990 _ecore_dlist_previous(Ecore_DList *list)
1991 {
1992    void *data = NULL;
1993
1994    if (!list)
1995      return NULL;
1996
1997    if (ECORE_LIST(list)->current)
1998      {
1999         data = ECORE_LIST(list)->current->data;
2000         ECORE_LIST(list)->current = ECORE_LIST_NODE(ECORE_DLIST_NODE(
2001                                                                      ECORE_LIST(list)->current)->previous);
2002         ECORE_LIST(list)->index--;
2003      }
2004    else
2005      _ecore_list_last_goto(ECORE_LIST(list));
2006
2007    return data;
2008 }
2009
2010 /**
2011  * @brief Remove all nodes from the list.
2012  * @param list: the list to remove all nodes from
2013  *
2014  * @return Returns TRUE on success, FALSE on errors
2015  */
2016 EAPI int
2017 ecore_dlist_clear(Ecore_DList *list)
2018 {
2019    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
2020
2021    ecore_list_clear(ECORE_LIST(list));
2022
2023    return TRUE;
2024 }
2025
2026 /**
2027  * Sort data in @p list using the compare function @p compare
2028  * @param list      The list.
2029  * @param compare   The function to compare the data of @p list
2030  * @param order     The sort direction, possible values are ECORE_SORT_MIN and
2031  *                  ECORE_SORT_MAX
2032  * @return          true on success
2033  *
2034  * This is a wrapper function for mergesort and heapsort. It
2035  * tries to choose the fastest algorithm depending on the
2036  * number of notes. Note: The sort may be unstable.
2037  */
2038 EAPI int
2039 ecore_dlist_sort(Ecore_List *list, Ecore_Compare_Cb compare, char order)
2040 {
2041    CHECK_PARAM_POINTER_RETURN("list", list, 0);
2042
2043    if (list->nodes < 2)
2044      return 1;
2045    if (list->nodes < ECORE_MERGESORT_LIMIT)
2046      return ecore_dlist_mergesort(list, compare, order);
2047    if (!ecore_dlist_heapsort(list, compare, order))
2048      return ecore_dlist_mergesort(list, compare, order);
2049
2050    return 1;
2051 }
2052
2053 /**
2054  * Sort data in @p list using the compare function @p compare
2055  * @param list      The list.
2056  * @param compare   The function to compare the data of @p list
2057  * @param order     The sort direction, possible values are ECORE_SORT_MIN and
2058  *                  ECORE_SORT_MAX
2059  * @return          true on success
2060  *
2061  * Mergesort is a stable, in-place sorting algorithm
2062  */
2063 EAPI int
2064 ecore_dlist_mergesort(Ecore_DList *list, Ecore_Compare_Cb compare, char order)
2065 {
2066    Ecore_List_Node *node;
2067
2068    CHECK_PARAM_POINTER_RETURN("list", list, 0);
2069    if (list->nodes < 2)
2070      return 1;
2071
2072    if (order == ECORE_SORT_MIN)
2073      order = 1;
2074    else
2075      order = -1;
2076
2077    node = _ecore_dlist_node_mergesort(list->first, list->nodes, compare, order);
2078    list->first = node;
2079
2080    /* maybe there is a better way to do that but our last node has changed */
2081    while (node->next)
2082      node = node->next;
2083    list->last = node;
2084
2085    _ecore_list_first_goto(list);
2086
2087    return 1;
2088 }
2089
2090 /**
2091  * Merge the @p l2 into the @p list using the compare function @p compare.
2092  * Both lists need to be sorted else a corrupt list could be the result.
2093  * @param list      The list.
2094  * @param l2        The second list, this list will be empty after the merge
2095  * @param compare   The function to compare the data of @p list and @p l2
2096  * @param order     The sort direction, possible values are ECORE_SORT_MIN and
2097  *                  ECORE_SORT_MAX
2098  */
2099 EAPI void
2100 ecore_dlist_merge(Ecore_DList *list, Ecore_DList *l2, Ecore_Compare_Cb compare, char order)
2101 {
2102    CHECK_PARAM_POINTER("list", list);
2103    CHECK_PARAM_POINTER("l2", l2);
2104
2105    if (ecore_dlist_empty_is(l2)) return;
2106
2107    if (ecore_dlist_empty_is(list))
2108      {
2109        ecore_dlist_append_list(list, l2);
2110        return;
2111      }
2112
2113    if (order == ECORE_SORT_MIN)
2114      order = 1;
2115    else
2116      order = -1;
2117
2118    list->first = _ecore_dlist_node_merge(list->first, l2->first, compare, order);
2119
2120    if ((order * compare(list->last->data, l2->last->data)) < 0)
2121      list->last = l2->last;
2122
2123    list->nodes += l2->nodes;
2124    ecore_dlist_init(l2);
2125 }
2126
2127 /* this is the internal recrusive function for the merge sort */
2128 static Ecore_List_Node *
2129 _ecore_dlist_node_mergesort(Ecore_List_Node *first, int n,
2130                            Ecore_Compare_Cb compare, int order)
2131 {
2132    Ecore_List_Node *middle;
2133    Ecore_List_Node *premid;
2134    int mid;
2135    int i;
2136
2137    mid = n/2;
2138
2139    if (n < 2)
2140      return first;
2141    else if (n == 2)
2142      {
2143         if (compare(first->data, first->next->data) * order > 0)
2144           {
2145                 /* swap the data */
2146                 void *data;
2147                 data = first->next->data;
2148                 first->next->data = first->data;
2149                 first->data = data;
2150           }
2151       return first;
2152     }
2153
2154    /* first find the premiddle node*/
2155    for (premid = first, i = 0; i < mid - 1; i++)
2156      premid = premid->next;
2157
2158    /* split the list */
2159    middle = premid->next;
2160    premid->next = NULL;
2161    ECORE_DLIST_NODE(middle)->previous = NULL;
2162
2163    /* sort the the partial lists */
2164    first = _ecore_dlist_node_mergesort(first, mid, compare, order);
2165    middle = _ecore_dlist_node_mergesort(middle, n - mid, compare, order);
2166
2167    return _ecore_dlist_node_merge(first, middle, compare, order);
2168 }
2169
2170 /* this function is used to merge the partial sorted lists */
2171 static Ecore_List_Node *
2172 _ecore_dlist_node_merge(Ecore_List_Node *first, Ecore_List_Node *second,
2173                        Ecore_Compare_Cb compare, int order)
2174 {
2175    Ecore_List_Node *list;
2176    Ecore_List_Node *l;
2177
2178    /* select the first node outside the loop, because we need to keep
2179     * a pointer to it */
2180    if (compare(first->data, second->data) * order > 0)
2181      {
2182         list = l = second;
2183         second = second->next;
2184      }
2185    else
2186      {
2187         list = l = first;
2188         first = first->next;
2189      }
2190
2191    /* and now start the merging */
2192    while (first && second)
2193      {
2194         if (compare(first->data, second->data) * order > 0)
2195           {
2196                 ECORE_DLIST_NODE(second)->previous = ECORE_DLIST_NODE(l);
2197                 l = l->next = second;
2198                 second = second->next;
2199           }
2200         else
2201           {
2202                 ECORE_DLIST_NODE(first)->previous = ECORE_DLIST_NODE(l);
2203                 l = l->next = first;
2204                 first = first->next;
2205           }
2206      }
2207
2208    /* append the rest or set it to NULL */
2209    if (first)
2210      {
2211         ECORE_DLIST_NODE(first)->previous = ECORE_DLIST_NODE(l);
2212         l->next = first;
2213      }
2214    else if (second)
2215      {
2216         ECORE_DLIST_NODE(second)->previous = ECORE_DLIST_NODE(l);
2217         l->next = second;
2218      }
2219    else
2220      l->next = NULL;
2221
2222    return list;
2223 }
2224
2225 /*
2226  * @brief Initialize a node to sane starting values
2227  * @param node: the node to initialize
2228  * @return Returns TRUE on success, FALSE on errors
2229  */
2230 EAPI int
2231 ecore_dlist_node_init(Ecore_DList_Node *node)
2232 {
2233    int ret;
2234
2235    CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
2236
2237    ret = ecore_list_node_init(ECORE_LIST_NODE(node));
2238    if (ret)
2239      node->previous = NULL;
2240
2241    return ret;
2242 }
2243
2244 /*
2245  * @brief Allocate and initialize a new list node
2246  * @return Returns NULL on error, new list node on success
2247  */
2248 EAPI Ecore_DList_Node *
2249 ecore_dlist_node_new()
2250 {
2251    Ecore_DList_Node *new_node;
2252
2253    new_node = malloc(sizeof(Ecore_DList_Node));
2254
2255    if (!new_node)
2256      return NULL;
2257
2258    if (!ecore_dlist_node_init(new_node))
2259      {
2260         FREE(new_node);
2261         return NULL;
2262      }
2263
2264    return new_node;
2265 }
2266
2267 /*
2268  * @brief Call the data's free callback function, then free the node
2269  * @param node: the node to be freed
2270  * @param free_func: the callback function to execute on the data
2271  * @return Returns TRUE on success, FALSE on error
2272  */
2273 EAPI int
2274 ecore_dlist_node_destroy(Ecore_DList_Node * node, Ecore_Free_Cb free_func)
2275 {
2276    CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
2277
2278    return ecore_list_node_destroy(ECORE_LIST_NODE(node), free_func);
2279 }