src/lib/eina_list.c

   1 /* EINA - EFL data type library
   2  * Copyright (C) 2002-2008 Carsten Haitzler, Gustavo Sverzut Barbieri, Tilman Sauerbeck,
   3  *                         Vincent Torri, Cedric Bail, Jorge Luis Zapata Muga,
   4  *                         Corey Donohoe, Arnaud de Turckheim, Alexandre Becoulet
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library;
  18  * if not, see <http://www.gnu.org/licenses/>.
  19  *
  20  * This file incorporates work covered by the following copyright and
  21  * permission notice:
  22  *
  23  * Copyright (C) 2004 ncn
  24  * Copyright (C) 2006 Sebastian Dransfeld
  25  * Copyright (C) 2007 Christopher Michael
  26  *
  27  *  Permission is hereby granted, free of charge, to any person obtaining a copy
  28  *  of this software and associated documentation files (the "Software"), to
  29  *  deal in the Software without restriction, including without limitation the
  30  *  rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  31  *  sell copies of the Software, and to permit persons to whom the Software is
  32  *  furnished to do so, subject to the following conditions:
  33
  34  *  The above copyright notice and this permission notice shall be included in
  35  *  all copies of the Software and its Copyright notices. In addition publicly
  36  *  documented acknowledgment must be given that this software has been used if no
  37  *  source code of this software is made available publicly. This includes
  38  *  acknowledgments in either Copyright notices, Manuals, Publicity and Marketing
  39  *  documents or any documentation provided with any product containing this
  40  *  software. This License does not apply to any software that links to the
  41  *  libraries provided by this software (statically or dynamically), but only to
  42  *  the software provided.
  43
  44  *  Please see the OLD-COPYING.PLAIN for a plain-english explanation of this notice
  45  *  and it's intent.
  46
  47  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  48  *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  49  *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  50  *  THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  51  *  IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  52  *  CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  53  */
  54
  55
  56 /**
  57  * @page tutorial_list_page List Tutorial
  58  *
  59  * to be written...
  60  *
  61  */
  62
  63 #ifdef HAVE_CONFIG_H
  64 # include "config.h"
  65 #endif
  66
  67 #include <stdlib.h>
  68 #include <stdio.h>
  69 #include <string.h>
  70
  71 #ifdef HAVE_EVIL
  72 # include <Evil.h>
  73 #endif
  74
  75 #include "eina_config.h"
  76 #include "eina_private.h"
  77 #include "eina_error.h"
  78 #include "eina_mempool.h"
  79
  80 /* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */
  81 #include "eina_safety_checks.h"
  82 #include "eina_list.h"
  83
  84
  85 /*============================================================================*
  86  *                                  Local                                     *
  87  *============================================================================*/
  88
  89 /**
  90  * @cond LOCAL
  91  */
  92
  93 #define EINA_MAGIC_CHECK_LIST(d, ...)                           \
  94   do {                                                          \
  95     if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST))                  \
  96     {                                                           \
  97         EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST);                    \
  98         return __VA_ARGS__;                                     \
  99     }                                                           \
 100   } while(0);
 101
 102 #define EINA_MAGIC_CHECK_LIST_ITERATOR(d, ...)                  \
 103   do {                                                          \
 104     if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST_ITERATOR))         \
 105     {                                                           \
 106         EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST_ITERATOR);           \
 107         return __VA_ARGS__;                                     \
 108     }                                                           \
 109   } while(0);
 110
 111 #define EINA_MAGIC_CHECK_LIST_ACCESSOR(d, ...)                  \
 112   do {                                                          \
 113     if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST_ACCESSOR))         \
 114     {                                                           \
 115         EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST_ACCESSOR);           \
 116         return __VA_ARGS__;                                     \
 117     }                                                           \
 118   } while(0);
 119
 120 #define EINA_MAGIC_CHECK_LIST_ACCOUNTING(d)                     \
 121   do {                                                          \
 122     if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_LIST_ACCOUNTING))       \
 123     {                                                           \
 124         EINA_MAGIC_FAIL(d, EINA_MAGIC_LIST_ACCOUNTING);         \
 125         return;                                                 \
 126     }                                                           \
 127   } while(0);
 128
 129 #define EINA_LIST_SORT_STACK_SIZE 32
 130
 131 typedef struct _Eina_Iterator_List Eina_Iterator_List;
 132 typedef struct _Eina_Accessor_List Eina_Accessor_List;
 133
 134 struct _Eina_Iterator_List
 135 {
 136    Eina_Iterator iterator;
 137
 138    const Eina_List *head;
 139    const Eina_List *current;
 140
 141    EINA_MAGIC
 142 };
 143
 144 struct _Eina_Accessor_List
 145 {
 146    Eina_Accessor accessor;
 147
 148    const Eina_List *head;
 149    const Eina_List *current;
 150
 151    unsigned int index;
 152
 153    EINA_MAGIC
 154 };
 155
 156 static Eina_Mempool *_eina_list_mp = NULL;
 157 static Eina_Mempool *_eina_list_accounting_mp = NULL;
 158 static int _eina_list_log_dom = -1;
 159
 160 #define ERR(...) EINA_LOG_DOM_ERR(_eina_list_log_dom, __VA_ARGS__)
 161 #define DBG(...) EINA_LOG_DOM_DBG(_eina_list_log_dom, __VA_ARGS__)
 162
 163 static inline Eina_List_Accounting*
 164 _eina_list_mempool_accounting_new(__UNUSED__ Eina_List *list)
 165 {
 166    Eina_List_Accounting *tmp;
 167
 168    tmp = eina_mempool_malloc(_eina_list_accounting_mp, sizeof (Eina_List_Accounting));
 169    if (!tmp) return NULL;
 170
 171    EINA_MAGIC_SET(tmp, EINA_MAGIC_LIST_ACCOUNTING);
 172
 173    return tmp;
 174 }
 175 static inline void
 176 _eina_list_mempool_accounting_free(Eina_List_Accounting *accounting)
 177 {
 178    EINA_MAGIC_CHECK_LIST_ACCOUNTING(accounting);
 179
 180    EINA_MAGIC_SET(accounting, EINA_MAGIC_NONE);
 181    eina_mempool_free(_eina_list_accounting_mp, accounting);
 182 }
 183
 184 static inline Eina_List*
 185 _eina_list_mempool_list_new(__UNUSED__ Eina_List *list)
 186 {
 187    Eina_List *tmp;
 188
 189    tmp = eina_mempool_malloc(_eina_list_mp, sizeof (Eina_List));
 190    if (!tmp) return NULL;
 191
 192    EINA_MAGIC_SET(tmp, EINA_MAGIC_LIST);
 193
 194    return tmp;
 195 }
 196 static inline void
 197 _eina_list_mempool_list_free(Eina_List *list)
 198 {
 199    EINA_MAGIC_CHECK_LIST(list);
 200
 201    list->accounting->count--;
 202    if (list->accounting->count == 0)
 203      _eina_list_mempool_accounting_free(list->accounting);
 204
 205    EINA_MAGIC_SET(list, EINA_MAGIC_NONE);
 206    eina_mempool_free(_eina_list_mp, list);
 207 }
 208
 209 static Eina_List *
 210 _eina_list_setup_accounting(Eina_List *list)
 211 {
 212    EINA_MAGIC_CHECK_LIST(list, NULL);
 213
 214    list->accounting = _eina_list_mempool_accounting_new(list);
 215    if (!list->accounting) goto on_error;
 216
 217    list->accounting->last = list;
 218    list->accounting->count = 1;
 219
 220    return list;
 221
 222  on_error:
 223    _eina_list_mempool_list_free(list);
 224    return NULL;
 225 }
 226
 227 static inline void
 228 _eina_list_update_accounting(Eina_List *list, Eina_List *new_list)
 229 {
 230    EINA_MAGIC_CHECK_LIST(list);
 231    EINA_MAGIC_CHECK_LIST(new_list);
 232
 233    list->accounting->count++;
 234    new_list->accounting = list->accounting;
 235 }
 236
 237 #if 0
 238 static Eina_Mempool2 _eina_list_mempool =
 239 {
 240    sizeof(Eina_List),
 241    320,
 242    0, NULL, NULL
 243 };
 244 static Eina_Mempool2 _eina_list_accounting_mempool =
 245 {
 246    sizeof(Eina_List_Accounting),
 247    80,
 248    0, NULL, NULL
 249 };
 250 #endif
 251
 252 static Eina_Bool
 253 eina_list_iterator_next(Eina_Iterator_List *it, void **data)
 254 {
 255    EINA_MAGIC_CHECK_LIST_ITERATOR(it, EINA_FALSE);
 256
 257    if (it->current == NULL) return EINA_FALSE;
 258    *data = eina_list_data_get(it->current);
 259
 260    it->current = eina_list_next(it->current);
 261
 262    return EINA_TRUE;
 263 }
 264
 265 static Eina_Bool
 266 eina_list_iterator_prev(Eina_Iterator_List *it, void **data)
 267 {
 268    EINA_MAGIC_CHECK_LIST_ITERATOR(it, EINA_FALSE);
 269
 270    if (it->current == NULL) return EINA_FALSE;
 271    *data = eina_list_data_get(it->current);
 272
 273    it->current = eina_list_prev(it->current);
 274
 275    return EINA_TRUE;
 276 }
 277
 278 static Eina_List *
 279 eina_list_iterator_get_container(Eina_Iterator_List *it)
 280 {
 281    EINA_MAGIC_CHECK_LIST_ITERATOR(it, NULL);
 282
 283    return (Eina_List *) it->head;
 284 }
 285
 286 static void
 287 eina_list_iterator_free(Eina_Iterator_List *it)
 288 {
 289    EINA_MAGIC_CHECK_LIST_ITERATOR(it);
 290
 291    MAGIC_FREE(it);
 292 }
 293
 294 static Eina_Bool
 295 eina_list_accessor_get_at(Eina_Accessor_List *it, unsigned int index, void **data)
 296 {
 297    const Eina_List *over;
 298    unsigned int middle;
 299    unsigned int i;
 300
 301    EINA_MAGIC_CHECK_LIST_ACCESSOR(it, EINA_FALSE);
 302
 303    if (index >= eina_list_count(it->head)) return EINA_FALSE;
 304
 305    if (it->index == index)
 306      {
 307         over = it->current;
 308      }
 309    else if (index > it->index)
 310      {
 311         /* After current position. */
 312         middle = ((eina_list_count(it->head) - it->index) >> 1) + it->index;
 313
 314         if (index > middle)
 315           {
 316              /* Go backward from the end. */
 317              for (i = eina_list_count(it->head) - 1, over = eina_list_last(it->head);
 318                   i > index && over != NULL;
 319                   --i, over = eina_list_prev(over))
 320                ;
 321           }
 322         else
 323           {
 324              /* Go forward from current. */
 325              for (i = it->index, over = it->current;
 326                   i < index && over != NULL;
 327                   ++i, over = eina_list_next(over))
 328                ;
 329           }
 330      }
 331    else
 332      {
 333         /* Before current position. */
 334         middle = it->index >> 1;
 335
 336         if (index > middle)
 337           {
 338              /* Go backward from current. */
 339              for (i = it->index, over = it->current;
 340                   i > index && over != NULL;
 341                   --i, over = eina_list_prev(over))
 342                ;
 343           }
 344         else
 345           {
 346              /* Go forward from start. */
 347              for (i = 0, over = it->head;
 348                   i < index && over != NULL;
 349                   ++i, over = eina_list_next(over))
 350                ;
 351           }
 352      }
 353
 354    if (over == NULL) return EINA_FALSE;
 355
 356    it->current = over;
 357    it->index = index;
 358
 359    *data = eina_list_data_get(it->current);
 360    return EINA_TRUE;
 361 }
 362
 363 static Eina_List *
 364 eina_list_accessor_get_container(Eina_Accessor_List *it)
 365 {
 366    EINA_MAGIC_CHECK_LIST_ACCESSOR(it, NULL);
 367
 368    return (Eina_List *) it->head;
 369 }
 370
 371 static void
 372 eina_list_accessor_free(Eina_Accessor_List *it)
 373 {
 374    EINA_MAGIC_CHECK_LIST_ACCESSOR(it);
 375
 376    MAGIC_FREE(it);
 377 }
 378
 379 static Eina_List *
 380 eina_list_sort_rebuild_prev(Eina_List *list)
 381 {
 382    Eina_List *prev = NULL;
 383
 384    EINA_MAGIC_CHECK_LIST(list, NULL);
 385
 386    for (; list; list = list->next)
 387      {
 388        list->prev = prev;
 389        prev = list;
 390      }
 391
 392    return prev;
 393 }
 394
 395 static Eina_List *
 396 eina_list_sort_merge(Eina_List *a, Eina_List *b, Eina_Compare_Cb func)
 397 {
 398    Eina_List *first, *last;
 399
 400    if (func(a->data, b->data) < 0)
 401      a = (last = first = a)->next;
 402    else
 403      b = (last = first = b)->next;
 404
 405    while (a && b)
 406      if (func(a->data, b->data) < 0)
 407        a = (last = last->next = a)->next;
 408      else
 409        b = (last = last->next = b)->next;
 410
 411    last->next = a ? a : b;
 412
 413    return first;
 414 }
 415
 416 /**
 417  * @endcond
 418  */
 419
 420 /*============================================================================*
 421  *                                 Global                                     *
 422  *============================================================================*/
 423
 424 /*============================================================================*
 425  *                                   API                                      *
 426  *============================================================================*/
 427
 428 /**
 429  * @addtogroup Eina_List_Group List
 430  *
 431  * @brief These functions provide double linked list management.
 432  *
 433  * For more information, you can look at the @ref tutorial_list_page.
 434  *
 435  * @{
 436  */
 437
 438 /**
 439  * @internal
 440  * @brief Initialize the list module.
 441  *
 442  * @return #EINA_TRUE on success, #EINA_FALSE on failure.
 443  *
 444  * This function sets up the list module of Eina. It is called by
 445  * eina_init().
 446  *
 447  * This function creates mempool to speed up list node and accounting
 448  * management, using EINA_MEMPOOL environment variable if it is set to
 449  * choose the memory pool type to use.
 450  *
 451  * @see eina_init()
 452  */
 453 Eina_Bool
 454 eina_list_init(void)
 455 {
 456    const char *choice, *tmp;
 457
 458    _eina_list_log_dom = eina_log_domain_register("eina_list", EINA_LOG_COLOR_DEFAULT);
 459    if (_eina_list_log_dom < 0)
 460      {
 461         EINA_LOG_ERR("Could not register log domain: eina_list");
 462         return EINA_FALSE;
 463      }
 464
 465 #ifdef EINA_DEFAULT_MEMPOOL
 466    choice = "pass_through";
 467 #else
 468    choice = "chained_mempool";
 469 #endif
 470    tmp = getenv("EINA_MEMPOOL");
 471    if (tmp && tmp[0])
 472      choice = tmp;
 473
 474    _eina_list_mp = eina_mempool_add
 475      (choice, "list", NULL, sizeof(Eina_List), 320);
 476    if (!_eina_list_mp)
 477      {
 478         ERR("ERROR: Mempool for list cannot be allocated in list init.");
 479         goto on_init_fail;
 480      }
 481    _eina_list_accounting_mp = eina_mempool_add
 482      (choice, "list_accounting", NULL, sizeof(Eina_List_Accounting), 80);
 483    if (!_eina_list_accounting_mp)
 484      {
 485         ERR("ERROR: Mempool for list accounting cannot be allocated in list init.");
 486         eina_mempool_del(_eina_list_mp);
 487         goto on_init_fail;
 488      }
 489
 490    eina_magic_string_set(EINA_MAGIC_LIST, "Eina List");
 491    eina_magic_string_set(EINA_MAGIC_LIST_ITERATOR, "Eina List Iterator");
 492    eina_magic_string_set(EINA_MAGIC_LIST_ACCESSOR, "Eina List Accessor");
 493    eina_magic_string_set(EINA_MAGIC_LIST_ACCOUNTING, "Eina List Accounting");
 494
 495    return EINA_TRUE;
 496
 497  on_init_fail:
 498    eina_log_domain_unregister(_eina_list_log_dom);
 499    _eina_list_log_dom = -1;
 500    return EINA_FALSE;
 501 }
 502
 503 /**
 504  * @internal
 505  * @brief Shut down the list module.
 506  *
 507  * @return #EINA_TRUE on success, #EINA_FALSE on failure.
 508  *
 509  * This function shuts down the list module set up by
 510  * eina_list_init(). It is called by eina_shutdown().
 511  *
 512  * @see eina_shutdown()
 513  */
 514 Eina_Bool
 515 eina_list_shutdown(void)
 516 {
 517    eina_mempool_del(_eina_list_accounting_mp);
 518    eina_mempool_del(_eina_list_mp);
 519
 520    eina_log_domain_unregister(_eina_list_log_dom);
 521    _eina_list_log_dom = -1;
 522    return EINA_TRUE;
 523 }
 524
 525 /**
 526  * @brief Append the given data to the given linked list.
 527  *
 528  * @param list The given list.
 529  * @param data The data to append.
 530  * @return A list pointer.
 531  *
 532  * This function appends @p data to @p list. If @p list is @c NULL, a
 533  * new list is returned. On success, a new list pointer that should be
 534  * used in place of the one given to this function is
 535  * returned. Otherwise, the old pointer is returned.
 536  *
 537  * The following example code demonstrates how to ensure that the
 538  * given data has been successfully appended.
 539  *
 540  * @code
 541  * Eina_List *list = NULL;
 542  * extern void *my_data;
 543  *
 544  * list = eina_list_append(list, my_data);
 545  * if (eina_error_get())
 546  *   {
 547  *     fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
 548  *     exit(-1);
 549  *   }
 550  * @endcode
 551  */
 552 EAPI Eina_List *
 553 eina_list_append(Eina_List *list, const void *data)
 554 {
 555    Eina_List *l, *new_l;
 556
 557    eina_error_set(0);
 558    new_l = _eina_list_mempool_list_new(list);
 559    if (!new_l) return list;
 560    new_l->next = NULL;
 561    new_l->data = (void *)data;
 562    if (!list)
 563      {
 564         new_l->prev = NULL;
 565         return _eina_list_setup_accounting(new_l);
 566      }
 567
 568    EINA_MAGIC_CHECK_LIST(list, NULL);
 569
 570    l = list->accounting->last;
 571    list->accounting->last = new_l;
 572
 573    l->next = new_l;
 574    new_l->prev = l;
 575
 576    _eina_list_update_accounting(list, new_l);
 577    return list;
 578 }
 579
 580 /**
 581  * @brief Prepends the given data to the given linked list.
 582  *
 583  * @param list The given list.
 584  * @param data The data to prepend.
 585  * @return A list pointer.
 586  *
 587  * This function prepends @p data to @p list. If @p list is @c NULL, a
 588  * new list is returned. On success, a new list pointer that should be
 589  * used in place of the one given to this function is
 590  * returned. Otherwise, the old pointer is returned.
 591  *
 592  * The following example code demonstrates how to ensure that the
 593  * given data has been successfully prepended.
 594  *
 595  * Example:
 596  * @code
 597  * Eina_List *list = NULL;
 598  * extern void *my_data;
 599  *
 600  * list = eina_list_prepend(list, my_data);
 601  * if (eina_error_get())
 602  *   {
 603  *     fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
 604  *     exit(-1);
 605  *   }
 606  * @endcode
 607  */
 608 EAPI Eina_List *
 609 eina_list_prepend(Eina_List *list, const void *data)
 610 {
 611    Eina_List *new_l;
 612
 613    eina_error_set(0);
 614    new_l = _eina_list_mempool_list_new(list);
 615    if (!new_l) return list;
 616
 617    new_l->prev = NULL;
 618    new_l->next = list;
 619    new_l->data = (void *)data;
 620
 621    if (!list) return _eina_list_setup_accounting(new_l);
 622
 623    EINA_MAGIC_CHECK_LIST(list, NULL);
 624
 625    list->prev = new_l;
 626
 627    _eina_list_update_accounting(list, new_l);
 628
 629    return new_l;
 630 }
 631
 632 /**
 633  * @brief Insert the given data into the given linked list after the specified data.
 634  *
 635  * @param list The given linked list.
 636  * @param data The data to insert.
 637  * @param relative The data to insert after.
 638  * @return A list pointer.
 639  *
 640  * This function inserts @p data to @p list after @p relative. If
 641  * @p relative is not in the list, @p data is appended to the end of
 642  * the list.  If @p list is @c NULL, a  new list is returned. If there
 643  * are multiple instances of @p relative in the list, @p data is
 644  * inserted after the first instance.On success, a new list pointer
 645  * that should be used in place of the one given to this function is
 646  * returned. Otherwise, the old pointer is returned.
 647  *
 648  * The following example code demonstrates how to ensure that the
 649  * given data has been successfully inserted.
 650  *
 651  * @code
 652  * Eina_List *list = NULL;
 653  * extern void *my_data;
 654  * extern void *relative_member;
 655  *
 656  * list = eina_list_append(list, relative_member);
 657  * if (eina_error_get())
 658  *   {
 659  *     fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
 660  *     exit(-1);
 661  *   }
 662  * list = eina_list_append_relative(list, my_data, relative_member);
 663  * if (eina_error_get())
 664  *   {
 665  *     fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
 666  *     exit(-1);
 667  *   }
 668  * @endcode
 669  */
 670 EAPI Eina_List *
 671 eina_list_append_relative(Eina_List *list, const void *data, const void *relative)
 672 {
 673    Eina_List *l;
 674    void *list_data;
 675
 676    if (list) EINA_MAGIC_CHECK_LIST(list, NULL);
 677
 678    EINA_LIST_FOREACH(list, l, list_data)
 679      {
 680          if (list_data == relative)
 681              return eina_list_append_relative_list(list, data, l);
 682      }
 683
 684    return eina_list_append(list, data);
 685 }
 686
 687 /**
 688  * @brief Append a list node to a linked list after the specified member
 689  *
 690  * @param list The given linked list.
 691  * @param data The data to insert.
 692  * @param relative The list node to insert after.
 693  * @return A list pointer.
 694  *
 695  * This function inserts @p data to @p list after the list node
 696  * @p relative. If @p list or @p relative are @c NULL, @p data is just
 697  * appended to @p list using eina_list_append(). If @p list is
 698  * @c NULL, a  new list is returned. If there are multiple instances
 699  * of @p relative in the list, @p data is inserted after the first
 700  * instance. On success, a new list pointer that should be used in
 701  * place of the one given to this function is returned. Otherwise, the
 702  * old pointer is returned.
 703  */
 704 EAPI Eina_List *
 705 eina_list_append_relative_list(Eina_List *list, const void *data, Eina_List *relative)
 706 {
 707    Eina_List *new_l;
 708
 709    if ((!list) || (!relative)) return eina_list_append(list, data);
 710    eina_error_set(0);
 711    new_l = _eina_list_mempool_list_new(list);
 712    if (!new_l) return list;
 713
 714    EINA_MAGIC_CHECK_LIST(relative, NULL);
 715    new_l->next = relative->next;
 716    new_l->data = (void *)data;
 717
 718    if (relative->next)
 719      relative->next->prev = new_l;
 720
 721    relative->next = new_l;
 722    new_l->prev = relative;
 723
 724    _eina_list_update_accounting(list, new_l);
 725
 726    if (!new_l->next)
 727      new_l->accounting->last = new_l;
 728
 729    return list;
 730 }
 731
 732 /**
 733  * @brief Prepend a data pointer to a linked list before the specified member
 734  *
 735  * @param list The given linked list.
 736  * @param data The data to insert.
 737  * @param relative The data to insert before.
 738  * @return A list pointer.
 739  *
 740  * This function inserts @p data to @p list before @p relative. If
 741  * @p relative is not in the list, @p data is prepended to the list
 742  * with eina_list_prepend(). If @p list is @c NULL, a  new list is
 743  * returned. If there are multiple instances of @p relative in the
 744  * list, @p data is inserted before the first instance. On success, a
 745  * new list pointer that should be used in place of the one given to
 746  * this function is returned. Otherwise, the old pointer is returned.
 747  *
 748  * The following code example demonstrates how to ensure that the
 749  * given data has been successfully inserted.
 750  *
 751  * @code
 752  * Eina_List *list = NULL;
 753  * extern void *my_data;
 754  * extern void *relative_member;
 755  *
 756  * list = eina_list_append(list, relative_member);
 757  * if (eina_error_get_error())
 758  *   {
 759  *     fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
 760  *     exit(-1);
 761  *   }
 762  * list = eina_list_prepend_relative(list, my_data, relative_member);
 763  * if (eina_error_get())
 764  *   {
 765  *     fprintf(stderr, "ERROR: Memory is low. List allocation failed.\n");
 766  *     exit(-1);
 767  *   }
 768  * @endcode
 769  */
 770 EAPI Eina_List *
 771 eina_list_prepend_relative(Eina_List *list, const void *data, const void *relative)
 772 {
 773    Eina_List *l;
 774    void *list_data;
 775
 776    if (list) EINA_MAGIC_CHECK_LIST(list, NULL);
 777
 778    EINA_LIST_FOREACH(list, l, list_data)
 779      {
 780          if (list_data == relative)
 781              return eina_list_prepend_relative_list(list, data, l);
 782      }
 783    return eina_list_prepend(list, data);
 784 }
 785
 786 /**
 787  * @brief Prepend a list node to a linked list before the specified member
 788  *
 789  * @param list The given linked list.
 790  * @param data The data to insert.
 791  * @param relative The list node to insert before.
 792  * @return A list pointer.
 793  *
 794  * This function inserts @p data to @p list before the list node
 795  * @p relative. If @p list or @p relative are @c NULL, @p data is just
 796  * prepended to @p list using eina_list_prepend(). If @p list is
 797  * @c NULL, a  new list is returned. If there are multiple instances
 798  * of @p relative in the list, @p data is inserted before the first
 799  * instance. On success, a new list pointer that should be used in
 800  * place of the one given to this function is returned. Otherwise, the
 801  * old pointer is returned.
 802  */
 803 EAPI Eina_List *
 804 eina_list_prepend_relative_list(Eina_List *list, const void *data, Eina_List *relative)
 805 {
 806    Eina_List *new_l;
 807
 808    if ((!list) || (!relative)) return eina_list_prepend(list, data);
 809    eina_error_set(0);
 810    new_l = _eina_list_mempool_list_new(list);
 811    if (!new_l) return list;
 812
 813    EINA_MAGIC_CHECK_LIST(relative, NULL);
 814
 815    new_l->prev = relative->prev;
 816    new_l->next = relative;
 817    new_l->data = (void *)data;
 818
 819    if (relative->prev) relative->prev->next = new_l;
 820    relative->prev = new_l;
 821
 822    _eina_list_update_accounting(list, new_l);
 823
 824    if (new_l->prev)
 825      return list;
 826
 827    return new_l;
 828 }
 829
 830 /**
 831  * @brief Insert a new node into a sorted list.
 832  *
 833  * @param list The given linked list, @b must be sorted.
 834  * @param data The data to insert sorted.
 835  * @return A list pointer.
 836  *
 837  * This function inserts values into a linked list assuming it was
 838  * sorted and the result will be sorted. If @p list is @c NULLL, a new
 839  * list is returned. On success, a new list pointer that should be
 840  * used in place of the one given to this function is
 841  * returned. Otherwise, the old pointer is returned. See eina_error_get().
 842  *
 843  * @note O(log2(n)) comparisons (calls to func) average/worst case
 844  * performance as it uses eina_list_search_sorted_near_list() and thus
 845  * is bounded to that. As said in eina_list_search_sorted_near_list(),
 846  * lists do not have O(1) access time, so walking to the correct node
 847  * can be costly, consider worst case to be almost O(n) pointer
 848  * dereference (list walk).
 849  */
 850 EAPI Eina_List *
 851 eina_list_sorted_insert(Eina_List *list, Eina_Compare_Cb func, const void *data)
 852 {
 853    Eina_List *lnear;
 854    int cmp;
 855
 856    if (!list) return eina_list_append(NULL, data);
 857
 858    lnear = eina_list_search_sorted_near_list(list, func, data, &cmp);
 859    if (cmp < 0)
 860      return eina_list_append_relative_list(list, data, lnear);
 861    else
 862      return eina_list_prepend_relative_list(list, data, lnear);
 863 }
 864
 865 /**
 866  * @brief Remove the first instance of the specified data from the given list.
 867  *
 868  * @param list The given list.
 869  * @param data The specified data.
 870  * @return A list pointer.
 871  *
 872  * This function removes the first instance of @p data from
 873  * @p list. If the specified data is not in the given list (tihis
 874  * include the case where @p data is @c NULL), nothing is done. If
 875  * @p list is @c NULL, @c NULL is returned, otherwise a new list
 876  * pointer that should be used in place of the one passed to this
 877  * function.
 878  */
 879 EAPI Eina_List *
 880 eina_list_remove(Eina_List *list, const void *data)
 881 {
 882    Eina_List *l;
 883
 884    if (list) EINA_MAGIC_CHECK_LIST(list, NULL);
 885
 886    l = eina_list_data_find_list(list, data);
 887    return eina_list_remove_list(list, l);
 888 }
 889
 890 /**
 891  * @brief Remove the specified data.
 892  *
 893  * @param list The given linked list.
 894  * @param remove_list The list node which is to be removed.
 895  * @return A list pointer.
 896  *
 897  * This function removes the list node @p remove_list from @p list and
 898  * frees the list node structure @p remove_list. If @p list is
 899  * @c NULL, this function returns @c NULL. If @p remove_list is
 900  * @c NULL, it returns @p list, otherwise, a new list pointer that
 901  * should be used in place of the one passed to this function.
 902  *
 903  * The following code gives an example (notice we use EINA_LIST_FOREACH
 904  * instead of EINA_LIST_FOREACH_SAFE because we stop the loop after
 905  * removing the current node).
 906  *
 907  * @code
 908  * extern Eina_List *list;
 909  * Eina_List *l;
 910  * extern void *my_data;
 911  * void *data
 912  *
 913  * EINA_LIST_FOREACH(list, l, data)
 914  *   {
 915  *     if (data == my_data)
 916  *       {
 917  *         list = eina_list_remove_list(list, l);
 918  *         break;
 919  *       }
 920  *   }
 921  * @endcode
 922  */
 923 EAPI Eina_List *
 924 eina_list_remove_list(Eina_List *list, Eina_List *remove_list)
 925 {
 926    Eina_List *return_l;
 927
 928    if (!list) return NULL;
 929    if (!remove_list) return list;
 930
 931    EINA_MAGIC_CHECK_LIST(remove_list, NULL);
 932
 933    if (remove_list->next) remove_list->next->prev = remove_list->prev;
 934    if (remove_list->prev)
 935      {
 936         remove_list->prev->next = remove_list->next;
 937         return_l = list;
 938      }
 939    else
 940      return_l = remove_list->next;
 941    if (remove_list == remove_list->accounting->last)
 942      {
 943        EINA_MAGIC_CHECK_LIST(list, NULL);
 944        list->accounting->last = remove_list->prev;
 945      }
 946    _eina_list_mempool_list_free(remove_list);
 947    return return_l;
 948 }
 949
 950 /**
 951  * @brief Free an entire list and all the nodes, ignoring the data contained.
 952
 953  * @param list The list to free
 954  * @return A NULL pointer
 955  *
 956  * This function frees all the nodes of @p list. It does not free the
 957  * data of the nodes. To free them, use #EINA_LIST_FREE.
 958  */
 959 EAPI Eina_List *
 960 eina_list_free(Eina_List *list)
 961 {
 962    Eina_List *l, *free_l;
 963
 964    if (!list) return NULL;
 965
 966    EINA_MAGIC_CHECK_LIST(list, NULL);
 967
 968    for (l = list; l;)
 969      {
 970         free_l = l;
 971         l = l->next;
 972
 973         _eina_list_mempool_list_free(free_l);
 974      }
 975
 976    return NULL;
 977 }
 978
 979 /**
 980  * @brief Move the specified data to the head of the list.
 981  *
 982  * @param list The list handle to move the data.
 983  * @param move_list The list node to move.
 984  * @return A new list handle to replace the old one
 985  *
 986  * This function move @p move_list to the front of @p list. If list is
 987  * @c NULL, @c NULL is returned. If @p move_list is @c NULL,
 988  * @p list is returned. Otherwise, a new list pointer that should be
 989  * used in place of the one passed to this function.
 990  *
 991  * Example:
 992  * @code
 993  * extern Eina_List *list;
 994  * Eina_List *l;
 995  * extern void *my_data;
 996  * void *data;
 997  *
 998  * EINA_LIST_FOREACH(list, l, data)
 999  *   {
1000  *     if (data == my_data)
1001  *       {
1002  *         list = eina_list_promote_list(list, l);
1003  *         break;
1004  *       }
1005  *   }
1006  * @endcode
1007  */
1008 EAPI Eina_List *
1009 eina_list_promote_list(Eina_List *list, Eina_List *move_list)
1010 {
1011    if (!list) return NULL;
1012    if (!move_list) return list;
1013    /* Promoting head to be head. */
1014    if (move_list == list) return list;
1015    if (move_list->next == list) return move_list;
1016
1017    EINA_MAGIC_CHECK_LIST(list, NULL);
1018    EINA_MAGIC_CHECK_LIST(move_list, NULL);
1019
1020    /* Remove the promoted item from the list. */
1021    if (!move_list->prev)
1022       move_list->next->prev = NULL;
1023    else
1024      {
1025         move_list->prev->next = move_list->next;
1026         if (move_list == list->accounting->last)
1027            list->accounting->last = move_list->prev;
1028         else
1029            move_list->next->prev = move_list->prev;
1030      }
1031
1032    /* Add the promoted item in the list. */
1033    move_list->next = list;
1034    move_list->prev = list->prev;
1035    list->prev = move_list;
1036    if (move_list->prev)
1037       move_list->prev->next = move_list;
1038
1039    return move_list;
1040 }
1041
1042 /**
1043  * @brief Move the specified data to the tail of the list.
1044  *
1045  * @param list The list handle to move the data.
1046  * @param move_list The list node to move.
1047  * @return A new list handle to replace the old one
1048  *
1049  * This function move @p move_list to the back of @p list. If list is
1050  * @c NULL, @c NULL is returned. If @p move_list is @c NULL,
1051  * @p list is returned. Otherwise, a new list pointer that should be
1052  * used in place of the one passed to this function.
1053  *
1054  * Example:
1055  * @code
1056  * extern Eina_List *list;
1057  * Eina_List *l;
1058  * extern void *my_data;
1059  * void *data;
1060  *
1061  * EINA_LIST_FOREACH(list, l, data)
1062  *   {
1063  *     if (data == my_data)
1064  *       {
1065  *         list = eina_list_demote_list(list, l);
1066  *         break;
1067  *       }
1068  *   }
1069  * @endcode
1070  */
1071 EAPI Eina_List *
1072 eina_list_demote_list(Eina_List *list, Eina_List *move_list)
1073 {
1074    if (!list) return NULL;
1075    if (!move_list) return list;
1076    /* Demoting tail to be tail. */
1077    if (move_list == list->accounting->last) return list;
1078
1079    EINA_MAGIC_CHECK_LIST(list, NULL);
1080    EINA_MAGIC_CHECK_LIST(move_list, NULL);
1081
1082    /* Update pointer list if necessary. */
1083    if (list == move_list)
1084       list = move_list->next;
1085    /* Remove the demoted item from the list. */
1086    if (move_list->prev)
1087       move_list->prev->next = move_list->next;
1088    move_list->next->prev = move_list->prev;
1089    /* Add the demoted item in the list. */
1090    move_list->prev = list->accounting->last;
1091    move_list->prev->next = move_list;
1092    move_list->next = NULL;
1093    list->accounting->last = move_list;
1094
1095    return list;
1096 }
1097
1098 /**
1099  * @brief Find a member of a list and return the member.
1100  *
1101  * @param list The list to search for a data.
1102  * @param data The data pointer to find in the list.
1103  * @return The found member data pointer if foun, @c NULL otherwise.
1104  *
1105  * This function searches in @p list from beginning to end for the
1106  * first member whose data pointer is @p data. If it is found, @p data
1107  * will be returned, otherwise NULL will be returned.
1108  *
1109  * Example:
1110  * @code
1111  * extern Eina_List *list;
1112  * extern void *my_data;
1113  *
1114  * if (eina_list_data_find(list, my_data) == my_data)
1115  *   {
1116  *     printf("Found member %p\n", my_data);
1117  *   }
1118  * @endcode
1119  */
1120 EAPI void *
1121 eina_list_data_find(const Eina_List *list, const void *data)
1122 {
1123    if (eina_list_data_find_list(list, data)) return (void*) data;
1124    return NULL;
1125 }
1126
1127 /**
1128  * @brief Find a member of a list and return the list node containing that member.
1129  *
1130  * @param list The list to search for data.
1131  * @param data The data pointer to find in the list.
1132  * @return The found members list node on success, @c NULL otherwise.
1133  *
1134  * This function searches in @p list from beginning to end for the
1135  * first member whose data pointer is @p data. If it is found, the
1136  * list node containing the specified member is returned, otherwise
1137  * @c NULL is returned.
1138  */
1139 EAPI Eina_List *
1140 eina_list_data_find_list(const Eina_List *list, const void *data)
1141 {
1142    const Eina_List *l;
1143    void *list_data;
1144
1145    if (list) EINA_MAGIC_CHECK_LIST(list, NULL);
1146
1147    EINA_LIST_FOREACH(list, l, list_data)
1148      {
1149         if (list_data == data) return (Eina_List *)l;
1150      }
1151
1152    return NULL;
1153 }
1154
1155 /**
1156  * @brief Get the nth member's data pointer in a list.
1157  *
1158  * @param list The list to get the specified member number from.
1159  * @param n The number of the element (0 being the first).
1160  * @return The data pointer stored in the specified element.
1161  *
1162  * This function returns the data pointer of element number @p n, in
1163  * the @p list. The first element in the array is element number 0. If
1164  * the element number @p n does not exist, @c NULL is
1165  * returned. Otherwise, the data of the found element is returned.
1166  */
1167 EAPI void *
1168 eina_list_nth(const Eina_List *list, unsigned int n)
1169 {
1170    Eina_List *l;
1171
1172    l = eina_list_nth_list(list, n);
1173    return l ? l->data : NULL;
1174 }
1175
1176 /**
1177  * @brief Get the nth member's list node in a list.
1178  *
1179  * @param list The list to get the specfied member number from.
1180  * @param n The number of the element (0 being the first).
1181  * @return The list node stored in the numbered element.
1182  *
1183  * This function returns the list node of element number @p n, in
1184  * @ list. The first element in the array is element number 0. If the
1185  * element number @p n does not exist or @p list is @c NULL or @p n is
1186  * greater than the count of elements in @p list minus 1, @c NULL is
1187  * returned. Otherwise the list node stored in the numbered element is
1188  * returned.
1189  */
1190 EAPI Eina_List *
1191 eina_list_nth_list(const Eina_List *list, unsigned int n)
1192 {
1193    const Eina_List *l;
1194    unsigned int i;
1195
1196    if (list) EINA_MAGIC_CHECK_LIST(list, NULL);
1197
1198    /* check for non-existing nodes */
1199    if ((!list) || (n > (list->accounting->count - 1)))
1200      return NULL;
1201
1202    /* if the node is in the 2nd half of the list, search from the end
1203     * else, search from the beginning.
1204     */
1205    if (n > (list->accounting->count / 2))
1206      {
1207         for (i = list->accounting->count - 1,
1208              l = list->accounting->last;
1209              l;
1210              l = l->prev, i--)
1211           {
1212              if (i == n) return (Eina_List *)l;
1213           }
1214      }
1215    else
1216      {
1217         for (i = 0, l = list; l; l = l->next, i++)
1218           {
1219              if (i == n) return (Eina_List *)l;
1220           }
1221      }
1222    abort();
1223 }
1224
1225 /**
1226  * @brief Get the last list node in the list.
1227  *
1228  * @param list The list to get the last list node from.
1229  * @return The last list node in the list.
1230  *
1231  * This function returns the last list node in the list. If @p list is
1232  * @c NULL or empty, @c NULL is returned.
1233  *
1234  * This is a order-1 operation (it takes the same short time
1235  * regardless of the length of the list).
1236  */
1237 static inline Eina_List *eina_list_last(const Eina_List *list);
1238
1239 /**
1240  * @brief Get the next list node after the specified list node.
1241  *
1242  * @param list The list node to get the next list node from
1243  * @return The next list node on success, @c NULL otherwise.
1244  *
1245  * This function returns the next list node after the current one in
1246  * @p list. It is equivalent to list->next. If @p list is @c NULL or
1247  * if no next list node exists, it returns @c NULL.
1248  */
1249 static inline Eina_List *eina_list_next(const Eina_List *list);
1250
1251 /**
1252  * @brief Get the previous list node before the specified list node.
1253  *
1254  * @param list The list node to get the previous list node from.
1255  * @return The previous list node o success, @c NULL otherwise.
1256  * if no previous list node exists
1257  *
1258  * This function returns the previous list node before the current one
1259  * in @p list. It is equivalent to list->prev. If @p list is @c NULL or
1260  * if no previous list node exists, it returns @c NULL.
1261  */
1262 static inline Eina_List *eina_list_prev(const Eina_List *list);
1263
1264 /**
1265  * @brief Get the list node data member.
1266  *
1267  * @param list The list node to get the data member of.
1268  * @return The data member from the list node.
1269  *
1270  * This function returns the data member of the specified list node @p
1271  * list. It is equivalent to list->data. If @p list is @c NULL, this
1272  * function returns @c NULL.
1273  */
1274 static inline void *eina_list_data_get(const Eina_List *list);
1275
1276 /**
1277  * @brief Get the count of the number of items in a list.
1278  *
1279  * @param list The list whose count to return.
1280  * @return The number of members in the list.
1281  *
1282  * This function returns how many members @p list contains. If the
1283  * list is @c NULL, 0 is returned.
1284  *
1285  * NB: This is an order-1 operation and takes the same tiem regardless
1286  * of the length of the list.
1287  */
1288 static inline unsigned int eina_list_count(const Eina_List *list);
1289
1290 /**
1291  * @brief Reverse all the elements in the list.
1292  *
1293  * @param list The list to reverse.
1294  * @return The list head after it has been reversed.
1295  *
1296  * This function reverses the order of all elements in @p list, so the
1297  * last member is now first, and so on. If @p list is @c NULL, this
1298  * functon returns @c NULL.
1299  *
1300  * @note @b in-place: this will change the given list, so you should
1301  * now point to the new list head that is returned by this function.
1302  *
1303  * @see eina_list_reverse_clone()
1304  * @see eina_list_iterator_reversed_new()
1305  */
1306 EAPI Eina_List *
1307 eina_list_reverse(Eina_List *list)
1308 {
1309    Eina_List *l1, *l2;
1310
1311    if (!list) return NULL;
1312
1313    EINA_MAGIC_CHECK_LIST(list, NULL);
1314
1315    l1 = list;
1316    l2 = list->accounting->last;
1317    while (l1 != l2)
1318      {
1319         void *data;
1320
1321         data = l1->data;
1322         l1->data = l2->data;
1323         l2->data = data;
1324         l1 = l1->next;
1325         if (l1 == l2) break;
1326         l2 = l2->prev;
1327      }
1328
1329    return list;
1330 }
1331
1332 /**
1333  * @brief Clone (copy) all the elements in the list in reverse order.
1334  *
1335  * @param list The list to reverse.
1336  * @return The new list that has been reversed.
1337  *
1338  * This function reverses the order of all elements in @p list, so the
1339  * last member is now first, and so on. If @p list is @c NULL, this
1340  * functon returns @c NULL. This returns a copy of the given list.
1341  *
1342  * @note @b copy: this will copy the list and you should then
1343  * eina_list_free() when it is not required anymore.
1344  *
1345  * @see eina_list_reverse()
1346  * @see eina_list_clone()
1347  */
1348 EAPI Eina_List *
1349 eina_list_reverse_clone(const Eina_List *list)
1350 {
1351    const Eina_List *l;
1352    Eina_List *clone;
1353    void *data;
1354
1355    if (!list) return NULL;
1356
1357    EINA_MAGIC_CHECK_LIST(list, NULL);
1358
1359    clone = NULL;
1360    EINA_LIST_FOREACH(list, l, data)
1361      clone = eina_list_prepend(clone, data);
1362
1363    return clone;
1364 }
1365
1366 /**
1367  * @brief Clone (copy) all the elements in the list in exact order.
1368  *
1369  * @param list The list to clone.
1370  * @return The new list that has been cloned.
1371  *
1372  * This function clone in order of all elements in @p list. If @p list
1373  * is @c NULL, this functon returns @c NULL. This returns a copy of
1374  * the given list.
1375  *
1376  * @note @b copy: this will copy the list and you should then
1377  * eina_list_free() when it is not required anymore.
1378  *
1379  * @see eina_list_reverse_clone()
1380  */
1381 EAPI Eina_List *
1382 eina_list_clone(const Eina_List *list)
1383 {
1384    const Eina_List *l;
1385    Eina_List *clone;
1386    void *data;
1387
1388    if (!list) return NULL;
1389
1390    EINA_MAGIC_CHECK_LIST(list, NULL);
1391
1392    clone = NULL;
1393    EINA_LIST_FOREACH(list, l, data)
1394      clone = eina_list_append(clone, data);
1395
1396    return clone;
1397 }
1398
1399 /**
1400  * @brief Sort a list according to the ordering func will return.
1401  *
1402  * @param list The list handle to sort.
1403  * @param size The length of the list to sort.
1404  * @param func A function pointer that can handle comparing the list data
1405  * nodes.
1406  * @return the new head of list.
1407  *
1408  * This function sorts @p list. @p size if the number of the first
1409  * element to sort. If @p size is 0 or greater than the number of
1410  * elements in @p list, all the elemnts are sorted. @p func is used to
1411  * compare two elements of @p list. If @p list or @p func are @c NULL,
1412  * this function returns @c NULL.
1413  *
1414  * @note @b in-place: this will change the given list, so you should
1415  * now point to the new list head that is returned by this function.
1416  *
1417  * @note worst case is O(n * log2(n)) comparisons (calls to func()),
1418  * O(n) comparisons average case. That means that for 1,000,000 list
1419  * elements, sort will usually do 1,000,000 comparisons, but may do up
1420  * to 20,000,000.
1421  *
1422  * Example:
1423  * @code
1424  * int
1425  * sort_cb(const void *d1, const void *d2)
1426  * {
1427  *    const char *txt = NULL;
1428  *    const char *txt2 = NULL;
1429  *
1430  *    if(!d1) return(1);
1431  *    if(!d2) return(-1);
1432  *
1433  *    return(strcmp((const char*)d1, (const char*)d2));
1434  * }
1435  * extern Eina_List *list;
1436  *
1437  * list = eina_list_sort(list, eina_list_count(list), sort_cb);
1438  * @endcode
1439  */
1440 EAPI Eina_List *
1441 eina_list_sort(Eina_List *list, unsigned int size, Eina_Compare_Cb func)
1442 {
1443    unsigned int i = 0;
1444    unsigned int n = 0;
1445    Eina_List *tail = list;
1446    Eina_List *unsort = NULL;
1447    Eina_List *stack[EINA_LIST_SORT_STACK_SIZE];
1448
1449    EINA_SAFETY_ON_NULL_RETURN_VAL(func, list);
1450    if (!list) return NULL;
1451    EINA_MAGIC_CHECK_LIST(list, NULL);
1452
1453    /* if the caller specified an invalid size, sort the whole list */
1454    if ((size == 0) ||
1455        (size > list->accounting->count))
1456      size = list->accounting->count;
1457
1458    if (size != list->accounting->count)
1459      {
1460         unsort = eina_list_nth_list(list, size);
1461         if (unsort)
1462           unsort->prev->next = NULL;
1463      }
1464
1465    while (tail)
1466      {
1467        unsigned int idx, tmp;
1468
1469        Eina_List *a = tail;
1470        Eina_List *b = tail->next;
1471
1472        if (!b)
1473          {
1474            stack[i++] = a;
1475            break;
1476          }
1477
1478        tail = b->next;
1479
1480        if (func(a->data, b->data) < 0)
1481          ((stack[i++] = a)->next = b)->next = 0;
1482        else
1483          ((stack[i++] = b)->next = a)->next = 0;
1484
1485        tmp = n++;
1486        for (idx = n ^ tmp; idx &= idx - 1; i--)
1487          stack[i-2] = eina_list_sort_merge(stack[i-2], stack[i-1], func);
1488      }
1489
1490    while (i-- > 1)
1491      stack[i-1] = eina_list_sort_merge(stack[i-1], stack[i], func);
1492
1493    list = stack[0];
1494    tail = eina_list_sort_rebuild_prev(list);
1495
1496    if (unsort)
1497      {
1498        tail->next = unsort;
1499        unsort->prev = tail;
1500      }
1501    else
1502      list->accounting->last = tail;
1503
1504    return list;
1505 }
1506
1507 /**
1508  * @brief Merge two list.
1509  *
1510  * @param left Head list to merge.
1511  * @param right Tail list to merge.
1512  * @return A new merged list.
1513  *
1514  * This function put right at the end of left and return the head.
1515  *
1516  * Both left and right does not exist anymore after the merge.
1517  *
1518  * @note merge cost is O(n), being @b n the size of the smallest
1519  * list. This is due the need to fix accounting of that segment,
1520  * making count and last access O(1).
1521  */
1522 EAPI Eina_List *
1523 eina_list_merge(Eina_List *left, Eina_List *right)
1524 {
1525    unsigned int n_left, n_right;
1526
1527    if (!left) return right;
1528    if (!right) return left;
1529
1530    left->accounting->last->next = right;
1531    right->prev = left->accounting->last;
1532
1533    n_left = left->accounting->count;
1534    n_right = right->accounting->count;
1535
1536    if (n_left >= n_right)
1537      {
1538         Eina_List *itr = right;
1539         left->accounting->last = right->accounting->last;
1540         left->accounting->count += n_right;
1541
1542         _eina_list_mempool_accounting_free(right->accounting);
1543
1544         do
1545           {
1546              itr->accounting = left->accounting;
1547              itr = itr->next;
1548           }
1549         while (itr);
1550      }
1551    else
1552      {
1553         Eina_List *itr = left->accounting->last;
1554         right->accounting->count += n_left;
1555
1556         _eina_list_mempool_accounting_free(left->accounting);
1557
1558         do
1559           {
1560              itr->accounting = right->accounting;
1561              itr = itr->prev;
1562           }
1563         while (itr);
1564      }
1565
1566    return left;
1567 }
1568
1569 /**
1570  * @brief Merge two sorted list according to the ordering func will return.
1571  *
1572  * @param left First list to merge.
1573  * @param right Second list to merge.
1574  * @param func A function pointer that can handle comparing the list data
1575  * nodes.
1576  * @return A new sorted list.
1577  *
1578  * This function compare the head of @p left and @p right, and choose the
1579  * smallest one to be head of the returned list. It will continue this process
1580  * for all entry of both list.
1581  *
1582  * Both left and right does not exist anymore after the merge.
1583  * If @p func is NULL, it will return NULL.
1584  *
1585  * Example:
1586  * @code
1587  * int
1588  * sort_cb(void *d1, void *d2)
1589  * {
1590  *   const char *txt = NULL;
1591  *    const char *txt2 = NULL;
1592  *
1593  *    if(!d1) return(1);
1594  *    if(!d2) return(-1);
1595  *
1596  *    return(strcmp((const char*)d1, (const char*)d2));
1597  * }
1598  * extern Eina_List *sorted1;
1599  * extern Eina_List *sorted2;
1600  *
1601  * list = eina_list_sorted_merge(sorted1, sorted2, sort_cb);
1602  * @endcode
1603  */
1604 EAPI Eina_List *
1605 eina_list_sorted_merge(Eina_List *left, Eina_List *right, Eina_Compare_Cb func)
1606 {
1607    Eina_List *ret;
1608    Eina_List *current;
1609
1610    EINA_SAFETY_ON_NULL_RETURN_VAL(func, NULL);
1611
1612    if (!left) return right;
1613    if (!right) return left;
1614
1615    if (func(left->data, right->data) < 0)
1616      {
1617         ret = left;
1618         current = left;
1619         left = left->next;
1620         ret->accounting->count += right->accounting->count;
1621
1622         _eina_list_mempool_accounting_free(right->accounting);
1623      }
1624    else
1625      {
1626         ret = right;
1627         current = right;
1628         right = right->next;
1629         ret->accounting->count += left->accounting->count;
1630
1631         _eina_list_mempool_accounting_free(left->accounting);
1632      }
1633
1634    while (left && right)
1635      {
1636         if (func(left->data, right->data) < 0)
1637           {
1638              current->next = left;
1639              left->prev = current;
1640              left = left->next;
1641           }
1642         else
1643           {
1644              current->next = right;
1645              right->prev = current;
1646              right = right->next;
1647           }
1648
1649         current = current->next;
1650         current->accounting = ret->accounting;
1651      }
1652
1653    if (left)
1654      {
1655         current->next = left;
1656         left->prev = current;
1657         current->accounting = ret->accounting;
1658      }
1659
1660    if (right)
1661      {
1662         current->next = right;
1663         right->prev = current;
1664         current->accounting = ret->accounting;
1665      }
1666
1667    while (current->next)
1668      {
1669         current = current->next;
1670         current->accounting = ret->accounting;
1671      }
1672
1673    ret->accounting->last = current;
1674
1675    return ret;
1676 }
1677
1678 /**
1679  * @brief Returns node nearest to data is in the sorted list.
1680  *
1681  * @param list The list to search for data, @b must be sorted.
1682  * @param func A function pointer that can handle comparing the list data nodes.
1683  * @param data reference value to search.
1684  * @param result_cmp if provided returns the result of
1685  * func(node->data, data) node being the last (returned) node. If node
1686  * was found (exact match), then it is 0. If returned node is smaller
1687  * than requested data, it is less than 0 and if it's bigger it's
1688  * greater than 0. It is the last value returned by func().
1689  * @return the nearest node, NULL if not found.
1690  *
1691  * This can be used to check if some value is inside the list and get
1692  * the nearest container node in this case. It should be used when list is
1693  * known to be sorted as it will do binary search for results.
1694  *
1695  * Example: imagine user gives a string, you check if it's in the list
1696  * before duplicating its contents, otherwise you want to insert it
1697  * sorted. In this case you get the result of this function and either
1698  * append or prepend the value.
1699  *
1700  * @note O(log2(n)) average/worst case performance, for 1,000,000
1701  * elements it will do a maximum of 20 comparisons. This is much
1702  * faster than the 1,000,000 comparisons made naively walking the list
1703  * from head to tail, so depending on the number of searches and
1704  * insertions, it may be worth to eina_list_sort() the list and do he
1705  * searches later. As lists do not have O(1) access time, walking to
1706  * the correct node can be costly, consider worst case to be almost
1707  * O(n) pointer dereference (list walk).
1708  *
1709  * @see eina_list_search_sorted_list()
1710  * @see eina_list_sort()
1711  * @see eina_list_sorted_merge()
1712  */
1713 EAPI Eina_List *
1714 eina_list_search_sorted_near_list(const Eina_List *list, Eina_Compare_Cb func, const void *data, int *result_cmp)
1715 {
1716    const Eina_List *ct;
1717    unsigned int inf, sup, cur;
1718    int cmp;
1719
1720    if (!list)
1721      {
1722         if (result_cmp) *result_cmp = 0;
1723         return NULL;
1724      }
1725
1726    if (list->accounting->count == 1)
1727      {
1728         if (result_cmp) *result_cmp = func(list->data, data);
1729         return (Eina_List *)list;
1730      }
1731
1732    /* list walk is expensive, do quick check: tail */
1733    ct = list->accounting->last;
1734    cmp = func(ct->data, data);
1735    if (cmp <= 0)
1736      goto end;
1737
1738    /* list walk is expensive, do quick check: head */
1739    ct = list;
1740    cmp = func(ct->data, data);
1741    if (cmp >= 0)
1742      goto end;
1743
1744    /* inclusive bounds */
1745    inf = 1;
1746    sup = list->accounting->count - 2;
1747    cur = 1;
1748    ct = list->next;
1749
1750    /* no loop, just compare if comparison value is important to caller */
1751    if (inf > sup)
1752      {
1753         if (result_cmp) cmp = func(ct->data, data);
1754         goto end;
1755      }
1756
1757    while (inf <= sup)
1758      {
1759         unsigned int tmp = cur;
1760         cur = inf + ((sup - inf) >> 1);
1761         if      (tmp < cur) for (; tmp != cur; tmp++, ct = ct->next);
1762         else if (tmp > cur) for (; tmp != cur; tmp--, ct = ct->prev);
1763
1764         cmp = func(ct->data, data);
1765         if (cmp == 0)
1766           break;
1767         else if (cmp < 0)
1768           inf = cur + 1;
1769         else if (cmp > 0)
1770           {
1771              if (cur > 0)
1772                sup = cur - 1;
1773              else break;
1774           }
1775         else break;
1776      }
1777
1778  end:
1779    if (result_cmp) *result_cmp = cmp;
1780    return (Eina_List *)ct;
1781 }
1782
1783 /**
1784  * @brief Returns node if data is in the sorted list.
1785  *
1786  * @param list The list to search for data, @b must be sorted.
1787  * @param func A function pointer that can handle comparing the list data nodes.
1788  * @param data reference value to search.
1789  * @return the node if func(node->data, data) == 0, NULL if not found.
1790  *
1791  * This can be used to check if some value is inside the list and get
1792  * the container node in this case. It should be used when list is
1793  * known to be sorted as it will do binary search for results.
1794  *
1795  * Example: imagine user gives a string, you check if it's in the list
1796  * before duplicating its contents.
1797  *
1798  * @note O(log2(n)) average/worst case performance, for 1,000,000
1799  * elements it will do a maximum of 20 comparisons. This is much
1800  * faster than the 1,000,000 comparisons made by
1801  * eina_list_search_unsorted_list(), so depending on the number of
1802  * searches and insertions, it may be worth to eina_list_sort() the
1803  * list and do he searches later. As said in
1804  * eina_list_search_sorted_near_list(), lists do not have O(1) access
1805  * time, so walking to the correct node can be costly, consider worst
1806  * case to be almost O(n) pointer dereference (list walk).
1807  *
1808  * @see eina_list_search_sorted()
1809  * @see eina_list_sort()
1810  * @see eina_list_sorted_merge()
1811  * @see eina_list_search_unsorted_list()
1812  * @see eina_list_search_sorted_near_list()
1813  */
1814 EAPI Eina_List *
1815 eina_list_search_sorted_list(const Eina_List *list, Eina_Compare_Cb func, const void *data)
1816 {
1817    Eina_List *lnear;
1818    int cmp;
1819
1820    lnear = eina_list_search_sorted_near_list(list, func, data, &cmp);
1821    if (!lnear) return NULL;
1822    if (cmp == 0)
1823      return lnear;
1824    return NULL;
1825 }
1826
1827
1828 /**
1829  * @brief Returns node data if it is in the sorted list.
1830  *
1831  * @param list The list to search for data, @b must be sorted.
1832  * @param func A function pointer that can handle comparing the list data nodes.
1833  * @param data reference value to search.
1834  * @return the node value (@c node->data) if func(node->data, data) == 0,
1835  * NULL if not found.
1836  *
1837  * This can be used to check if some value is inside the list and get
1838  * the existing instance in this case. It should be used when list is
1839  * known to be sorted as it will do binary search for results.
1840  *
1841  * Example: imagine user gives a string, you check if it's in the list
1842  * before duplicating its contents.
1843  *
1844  * @note O(log2(n)) average/worst case performance, for 1,000,000
1845  * elements it will do a maximum of 20 comparisons. This is much
1846  * faster than the 1,000,000 comparisons made by
1847  * eina_list_search_unsorted(), so depending on the number of
1848  * searches and insertions, it may be worth to eina_list_sort() the
1849  * list and do he searches later. As said in
1850  * eina_list_search_sorted_near_list(), lists do not have O(1) access
1851  * time, so walking to the correct node can be costly, consider worst
1852  * case to be almost O(n) pointer dereference (list walk).
1853  *
1854  * @see eina_list_search_sorted_list()
1855  * @see eina_list_sort()
1856  * @see eina_list_sorted_merge()
1857  * @see eina_list_search_unsorted_list()
1858  */
1859 EAPI void *
1860 eina_list_search_sorted(const Eina_List *list, Eina_Compare_Cb func, const void *data)
1861 {
1862    return eina_list_data_get(eina_list_search_sorted_list(list, func, data));
1863 }
1864
1865 /**
1866  * @brief Returns node if data is in the unsorted list.
1867  *
1868  * @param list The list to search for data, may be unsorted.
1869  * @param func A function pointer that can handle comparing the list data nodes.
1870  * @param data reference value to search.
1871  * @return the node if func(node->data, data) == 0, NULL if not found.
1872  *
1873  * This can be used to check if some value is inside the list and get
1874  * the container node in this case.
1875  *
1876  * Example: imagine user gives a string, you check if it's in the list
1877  * before duplicating its contents.
1878  *
1879  * @note this is expensive and may walk the whole list, it's order-N,
1880  * that is for 1,000,000 elements list it may walk and compare
1881  * 1,000,000 nodes.
1882  *
1883  * @see eina_list_search_sorted_list()
1884  * @see eina_list_search_unsorted()
1885  */
1886 EAPI Eina_List *
1887 eina_list_search_unsorted_list(const Eina_List *list, Eina_Compare_Cb func, const void *data)
1888 {
1889    const Eina_List *l;
1890    void *d;
1891
1892    EINA_LIST_FOREACH(list, l, d)
1893      {
1894        if (!func(d, data))
1895          return (Eina_List*) l;
1896      }
1897    return NULL;
1898 }
1899
1900 /**
1901  * @brief Returns node data if it is in the unsorted list.
1902  *
1903  * @param list The list to search for data, may be unsorted.
1904  * @param func A function pointer that can handle comparing the list data nodes.
1905  * @param data reference value to search.
1906  * @return the node value (@c node->data) if func(node->data, data) == 0,
1907  * NULL if not found.
1908  *
1909  * This can be used to check if some value is inside the list and get
1910  * the existing instance in this case.
1911  *
1912  * Example: imagine user gives a string, you check if it's in the list
1913  * before duplicating its contents.
1914  *
1915  * @note this is expensive and may walk the whole list, it's order-N,
1916  * that is for 1,000,000 elements list it may walk and compare
1917  * 1,000,000 nodes.
1918  *
1919  * @see eina_list_search_sorted()
1920  * @see eina_list_search_unsorted_list()
1921  */
1922 EAPI void *
1923 eina_list_search_unsorted(const Eina_List *list, Eina_Compare_Cb func, const void *data)
1924 {
1925    return eina_list_data_get(eina_list_search_unsorted_list(list, func, data));
1926 }
1927
1928
1929 /**
1930  * @brief Returned a new iterator asociated to a list.
1931  *
1932  * @param list The list.
1933  * @return A new iterator.
1934  *
1935  * This function returns a newly allocated iterator associated to @p
1936  * list. If @p list is @c NULL or the count member of @p list is less
1937  * or equal than 0, this function still returns a valid iterator that
1938  * will always return false on eina_iterator_next(), thus keeping API
1939  * sane.
1940  *
1941  * If the memory can not be allocated, NULL is returned and
1942  * #EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is
1943  * returned.
1944  *
1945  * @warning if the list structure changes then the iterator becomes
1946  *    invalid! That is, if you add or remove nodes this iterator
1947  *    behavior is undefined and your program may crash!
1948  */
1949 EAPI Eina_Iterator *
1950 eina_list_iterator_new(const Eina_List *list)
1951 {
1952    Eina_Iterator_List *it;
1953
1954    eina_error_set(0);
1955    it = calloc(1, sizeof (Eina_Iterator_List));
1956    if (!it) {
1957       eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1958       return NULL;
1959    }
1960
1961    EINA_MAGIC_SET(it, EINA_MAGIC_LIST_ITERATOR);
1962    EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1963
1964    it->head = list;
1965    it->current = list;
1966
1967    it->iterator.next = FUNC_ITERATOR_NEXT(eina_list_iterator_next);
1968    it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(eina_list_iterator_get_container);
1969    it->iterator.free = FUNC_ITERATOR_FREE(eina_list_iterator_free);
1970
1971    return &it->iterator;
1972 }
1973
1974 /**
1975  * @brief Returned a new reversed iterator asociated to a list.
1976  *
1977  * @param list The list.
1978  * @return A new iterator.
1979  *
1980  * This function returns a newly allocated iterator associated to @p
1981  * list. If @p list is @c NULL or the count member of @p list is less
1982  * or equal than 0, this function still returns a valid iterator that
1983  * will always return false on eina_iterator_next(), thus keeping API
1984  * sane.
1985  *
1986  * Unlike eina_list_iterator_new(), this will walk the list backwards.
1987  *
1988  * If the memory can not be allocated, NULL is returned and
1989  * #EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is
1990  * returned.
1991  *
1992  * @warning if the list structure changes then the iterator becomes
1993  *    invalid! That is, if you add or remove nodes this iterator
1994  *    behavior is undefined and your program may crash!
1995  */
1996 EAPI Eina_Iterator *
1997 eina_list_iterator_reversed_new(const Eina_List *list)
1998 {
1999    Eina_Iterator_List *it;
2000
2001    eina_error_set(0);
2002    it = calloc(1, sizeof (Eina_Iterator_List));
2003    if (!it) {
2004       eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
2005       return NULL;
2006    }
2007
2008    EINA_MAGIC_SET(it, EINA_MAGIC_LIST_ITERATOR);
2009    EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
2010
2011    it->head = eina_list_last(list);
2012    it->current = it->head;
2013
2014    it->iterator.next = FUNC_ITERATOR_NEXT(eina_list_iterator_prev);
2015    it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(eina_list_iterator_get_container);
2016    it->iterator.free = FUNC_ITERATOR_FREE(eina_list_iterator_free);
2017
2018    return &it->iterator;
2019 }
2020
2021 /**
2022  * @brief Returned a new accessor asociated to a list.
2023  *
2024  * @param list The list.
2025  * @return A new accessor.
2026  *
2027  * This function returns a newly allocated accessor associated to
2028  * @p list. If @p list is @c NULL or the count member of @p list is
2029  * less or equal than 0, this function returns NULL. If the memory can
2030  * not be allocated, NULL is returned and #EINA_ERROR_OUT_OF_MEMORY is
2031  * set. Otherwise, a valid accessor is returned.
2032  */
2033 EAPI Eina_Accessor *
2034 eina_list_accessor_new(const Eina_List *list)
2035 {
2036    Eina_Accessor_List *it;
2037
2038    eina_error_set(0);
2039    it = calloc(1, sizeof (Eina_Accessor_List));
2040    if (!it) {
2041       eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
2042       return NULL;
2043    }
2044
2045    EINA_MAGIC_SET(it, EINA_MAGIC_LIST_ACCESSOR);
2046    EINA_MAGIC_SET(&it->accessor, EINA_MAGIC_ACCESSOR);
2047
2048    it->head = list;
2049    it->current = list;
2050    it->index = 0;
2051
2052    it->accessor.get_at = FUNC_ACCESSOR_GET_AT(eina_list_accessor_get_at);
2053    it->accessor.get_container = FUNC_ACCESSOR_GET_CONTAINER(eina_list_accessor_get_container);
2054    it->accessor.free = FUNC_ACCESSOR_FREE(eina_list_accessor_free);
2055
2056    return &it->accessor;
2057 }
2058
2059 /**
2060  * @}
2061  */