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 #ifdef HAVE_CONFIG_H
  57 # include "config.h"
  58 #endif
  59
  60 #include <stdlib.h>
  61 #include <stdio.h>
  62 #include <string.h>
  63
  64 #ifdef HAVE_EVIL
  65 # include <Evil.h>
  66 #endif
  67
  68 #include "eina_config.h"
  69 #include "eina_private.h"
  70 #include "eina_error.h"
  71 #include "eina_log.h"
  72 #include "eina_mempool.h"
  73
  74 /* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */
  75 #include "eina_safety_checks.h"
  76 #include "eina_list.h"
  77
  78
  79 /*============================================================================*
  80  *                                  Local                                     *
  81  *============================================================================*/
  82
  83 /**
  84  * @cond LOCAL
  85  */
  86
  87 static const char EINA_MAGIC_LIST_STR[] = "Eina List";
  88 static const char EINA_MAGIC_LIST_ITERATOR_STR[] = "Eina List Iterator";
  89 static const char EINA_MAGIC_LIST_ACCESSOR_STR[] = "Eina List Accessor";
  90 static const char EINA_MAGIC_LIST_ACCOUNTING_STR[] = "Eina List Accounting";
  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 #ifdef ERR
 161 #undef ERR
 162 #endif
 163 #define ERR(...) EINA_LOG_DOM_ERR(_eina_list_log_dom, __VA_ARGS__)
 164
 165 #ifdef DBG
 166 #undef DBG
 167 #endif
 168 #define DBG(...) EINA_LOG_DOM_DBG(_eina_list_log_dom, __VA_ARGS__)
 169
 170 static inline Eina_List_Accounting *
 171 _eina_list_mempool_accounting_new(__UNUSED__ Eina_List *list)
 172 {
 173    Eina_List_Accounting *tmp;
 174
 175    tmp =
 176       eina_mempool_malloc(_eina_list_accounting_mp,
 177                           sizeof (Eina_List_Accounting));
 178    if (!tmp)
 179      return NULL;
 180
 181    EINA_MAGIC_SET(tmp, EINA_MAGIC_LIST_ACCOUNTING);
 182
 183    return tmp;
 184 }
 185 static inline void
 186 _eina_list_mempool_accounting_free(Eina_List_Accounting *accounting)
 187 {
 188    EINA_MAGIC_CHECK_LIST_ACCOUNTING(accounting);
 189
 190    EINA_MAGIC_SET(accounting, EINA_MAGIC_NONE);
 191    eina_mempool_free(_eina_list_accounting_mp, accounting);
 192 }
 193
 194 static inline Eina_List *
 195 _eina_list_mempool_list_new(__UNUSED__ Eina_List *list)
 196 {
 197    Eina_List *tmp;
 198
 199    tmp = eina_mempool_malloc(_eina_list_mp, sizeof (Eina_List));
 200    if (!tmp)
 201      return NULL;
 202
 203    EINA_MAGIC_SET(tmp, EINA_MAGIC_LIST);
 204
 205    return tmp;
 206 }
 207 static inline void
 208 _eina_list_mempool_list_free(Eina_List *list)
 209 {
 210    EINA_MAGIC_CHECK_LIST(list);
 211
 212    list->accounting->count--;
 213    if (list->accounting->count == 0)
 214      _eina_list_mempool_accounting_free(list->accounting);
 215
 216    EINA_MAGIC_SET(list, EINA_MAGIC_NONE);
 217    eina_mempool_free(_eina_list_mp, list);
 218 }
 219
 220 static Eina_List *
 221 _eina_list_setup_accounting(Eina_List *list)
 222 {
 223    EINA_MAGIC_CHECK_LIST(list, NULL);
 224
 225    list->accounting = _eina_list_mempool_accounting_new(list);
 226    if (!list->accounting)
 227      goto on_error;
 228
 229    list->accounting->last = list;
 230    list->accounting->count = 1;
 231
 232    return list;
 233
 234 on_error:
 235    _eina_list_mempool_list_free(list);
 236    return NULL;
 237 }
 238
 239 static inline void
 240 _eina_list_update_accounting(Eina_List *list, Eina_List *new_list)
 241 {
 242    EINA_MAGIC_CHECK_LIST(list);
 243    EINA_MAGIC_CHECK_LIST(new_list);
 244
 245    list->accounting->count++;
 246    new_list->accounting = list->accounting;
 247 }
 248
 249 #if 0
 250 static Eina_Mempool2 _eina_list_mempool =
 251 {
 252    sizeof(Eina_List),
 253    320,
 254    0, NULL, NULL
 255 };
 256 static Eina_Mempool2 _eina_list_accounting_mempool =
 257 {
 258    sizeof(Eina_List_Accounting),
 259    80,
 260    0, NULL, NULL
 261 };
 262 #endif
 263
 264 static Eina_Bool
 265 eina_list_iterator_next(Eina_Iterator_List *it, void **data)
 266 {
 267    EINA_MAGIC_CHECK_LIST_ITERATOR(it, EINA_FALSE);
 268
 269    if (!it->current)
 270      return EINA_FALSE;
 271
 272    *data = eina_list_data_get(it->current);
 273
 274    it->current = eina_list_next(it->current);
 275
 276    return EINA_TRUE;
 277 }
 278
 279 static Eina_Bool
 280 eina_list_iterator_prev(Eina_Iterator_List *it, void **data)
 281 {
 282    EINA_MAGIC_CHECK_LIST_ITERATOR(it, EINA_FALSE);
 283
 284    if (!it->current)
 285      return EINA_FALSE;
 286
 287    *data = eina_list_data_get(it->current);
 288
 289    it->current = eina_list_prev(it->current);
 290
 291    return EINA_TRUE;
 292 }
 293
 294 static Eina_List *
 295 eina_list_iterator_get_container(Eina_Iterator_List *it)
 296 {
 297    EINA_MAGIC_CHECK_LIST_ITERATOR(it, NULL);
 298
 299    return (Eina_List *)it->head;
 300 }
 301
 302 static void
 303 eina_list_iterator_free(Eina_Iterator_List *it)
 304 {
 305    EINA_MAGIC_CHECK_LIST_ITERATOR(it);
 306
 307    MAGIC_FREE(it);
 308 }
 309
 310 static Eina_Bool
 311 eina_list_accessor_get_at(Eina_Accessor_List *it, unsigned int idx, void **data)
 312 {
 313    const Eina_List *over;
 314    unsigned int middle;
 315    unsigned int i;
 316
 317    EINA_MAGIC_CHECK_LIST_ACCESSOR(it, EINA_FALSE);
 318
 319    if (idx >= eina_list_count(it->head))
 320      return EINA_FALSE;
 321
 322    if (it->index == idx)
 323      over = it->current;
 324    else if (idx > it->index)
 325      {
 326         /* After current position. */
 327         middle = ((eina_list_count(it->head) - it->index) >> 1) + it->index;
 328
 329         if (idx > middle)
 330           /* Go backward from the end. */
 331           for (i = eina_list_count(it->head) - 1,
 332                over = eina_list_last(it->head);
 333                i > idx && over;
 334                --i, over = eina_list_prev(over))
 335             ;
 336         else
 337           /* Go forward from current. */
 338           for (i = it->index, over = it->current;
 339                i < idx && over;
 340                ++i, over = eina_list_next(over))
 341             ;
 342      }
 343    else
 344      {
 345         /* Before current position. */
 346         middle = it->index >> 1;
 347
 348         if (idx > middle)
 349           /* Go backward from current. */
 350           for (i = it->index, over = it->current;
 351                i > idx && over;
 352                --i, over = eina_list_prev(over))
 353             ;
 354         else
 355           /* Go forward from start. */
 356           for (i = 0, over = it->head;
 357                i < idx && over;
 358                ++i, over = eina_list_next(over))
 359             ;
 360      }
 361
 362    if (!over)
 363      return EINA_FALSE;
 364
 365    it->current = over;
 366    it->index = idx;
 367
 368    *data = eina_list_data_get(it->current);
 369    return EINA_TRUE;
 370 }
 371
 372 static Eina_List *
 373 eina_list_accessor_get_container(Eina_Accessor_List *it)
 374 {
 375    EINA_MAGIC_CHECK_LIST_ACCESSOR(it, NULL);
 376
 377    return (Eina_List *)it->head;
 378 }
 379
 380 static void
 381 eina_list_accessor_free(Eina_Accessor_List *it)
 382 {
 383    EINA_MAGIC_CHECK_LIST_ACCESSOR(it);
 384
 385    MAGIC_FREE(it);
 386 }
 387
 388 static Eina_List *
 389 eina_list_sort_rebuild_prev(Eina_List *list)
 390 {
 391    Eina_List *prev = NULL;
 392
 393    EINA_MAGIC_CHECK_LIST(list, NULL);
 394
 395    for (; list; list = list->next)
 396      {
 397         list->prev = prev;
 398         prev = list;
 399      }
 400
 401    return prev;
 402 }
 403
 404 static Eina_List *
 405 eina_list_sort_merge(Eina_List *a, Eina_List *b, Eina_Compare_Cb func)
 406 {
 407    Eina_List *first, *last;
 408
 409    if (func(a->data, b->data) < 0)
 410      a = (last = first = a)->next;
 411    else
 412      b = (last = first = b)->next;
 413
 414    while (a && b)
 415      if (func(a->data, b->data) < 0)
 416        a = (last = last->next = a)->next;
 417      else
 418        b = (last = last->next = b)->next;
 419
 420    last->next = a ? a : b;
 421
 422    return first;
 423 }
 424
 425 /**
 426  * @endcond
 427  */
 428
 429 /*============================================================================*
 430  *                                 Global                                     *
 431  *============================================================================*/
 432
 433 /**
 434  * @internal
 435  * @brief Initialize the list module.
 436  *
 437  * @return #EINA_TRUE on success, #EINA_FALSE on failure.
 438  *
 439  * This function sets up the list module of Eina. It is called by
 440  * eina_init().
 441  *
 442  * This function creates mempool to speed up list node and accounting
 443  * management, using EINA_MEMPOOL environment variable if it is set to
 444  * choose the memory pool type to use.
 445  *
 446  * @see eina_init()
 447  */
 448 Eina_Bool
 449 eina_list_init(void)
 450 {
 451    const char *choice, *tmp;
 452
 453    _eina_list_log_dom = eina_log_domain_register("eina_list",
 454                                                  EINA_LOG_COLOR_DEFAULT);
 455    if (_eina_list_log_dom < 0)
 456      {
 457         EINA_LOG_ERR("Could not register log domain: eina_list");
 458         return EINA_FALSE;
 459      }
 460
 461 #ifdef EINA_DEFAULT_MEMPOOL
 462    choice = "pass_through";
 463 #else
 464    choice = "chained_mempool";
 465 #endif
 466    tmp = getenv("EINA_MEMPOOL");
 467    if (tmp && tmp[0])
 468      choice = tmp;
 469
 470    _eina_list_mp = eina_mempool_add
 471       (choice, "list", NULL, sizeof(Eina_List), 128);
 472    if (!_eina_list_mp)
 473      {
 474         ERR("ERROR: Mempool for list cannot be allocated in list init.");
 475         goto on_init_fail;
 476      }
 477
 478    _eina_list_accounting_mp = eina_mempool_add
 479       (choice, "list_accounting", NULL, sizeof(Eina_List_Accounting), 16);
 480    if (!_eina_list_accounting_mp)
 481      {
 482         ERR(
 483            "ERROR: Mempool for list accounting cannot be allocated in list init.");
 484         eina_mempool_del(_eina_list_mp);
 485         goto on_init_fail;
 486      }
 487
 488 #define EMS(n) eina_magic_string_static_set(n, n ## _STR)
 489    EMS(EINA_MAGIC_LIST);
 490    EMS(EINA_MAGIC_LIST_ITERATOR);
 491    EMS(EINA_MAGIC_LIST_ACCESSOR);
 492    EMS(EINA_MAGIC_LIST_ACCOUNTING);
 493 #undef EMS
 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  *                                   API                                      *
 527  *============================================================================*/
 528
 529 EAPI Eina_List *
 530 eina_list_append(Eina_List *list, const void *data)
 531 {
 532    Eina_List *l, *new_l;
 533
 534    eina_error_set(0);
 535    new_l = _eina_list_mempool_list_new(list);
 536    if (!new_l)
 537      return list;
 538
 539    new_l->next = NULL;
 540    new_l->data = (void *)data;
 541    if (!list)
 542      {
 543         new_l->prev = NULL;
 544         return _eina_list_setup_accounting(new_l);
 545      }
 546
 547    EINA_MAGIC_CHECK_LIST(list, NULL);
 548
 549    l = list->accounting->last;
 550    list->accounting->last = new_l;
 551
 552    l->next = new_l;
 553    new_l->prev = l;
 554
 555    _eina_list_update_accounting(list, new_l);
 556    return list;
 557 }
 558
 559 EAPI Eina_List *
 560 eina_list_prepend(Eina_List *list, const void *data)
 561 {
 562    Eina_List *new_l;
 563
 564    eina_error_set(0);
 565    new_l = _eina_list_mempool_list_new(list);
 566    if (!new_l)
 567      return list;
 568
 569    new_l->prev = NULL;
 570    new_l->next = list;
 571    new_l->data = (void *)data;
 572
 573    if (!list)
 574      return _eina_list_setup_accounting(new_l);
 575
 576    EINA_MAGIC_CHECK_LIST(list, NULL);
 577
 578    list->prev = new_l;
 579
 580    _eina_list_update_accounting(list, new_l);
 581
 582    return new_l;
 583 }
 584
 585 EAPI Eina_List *
 586 eina_list_append_relative(Eina_List *list,
 587                           const void *data,
 588                           const void *relative)
 589 {
 590    Eina_List *l;
 591    void *list_data;
 592
 593    if (list)
 594      EINA_MAGIC_CHECK_LIST(list, NULL);
 595
 596    EINA_LIST_FOREACH(list, l, list_data)
 597      {
 598         if (list_data == relative)
 599           return eina_list_append_relative_list(list, data, l);
 600      }
 601
 602    return eina_list_append(list, data);
 603 }
 604
 605 EAPI Eina_List *
 606 eina_list_append_relative_list(Eina_List *list,
 607                                const void *data,
 608                                Eina_List *relative)
 609 {
 610    Eina_List *new_l;
 611
 612    if ((!list) || (!relative))
 613      return eina_list_append(list, data);
 614
 615    eina_error_set(0);
 616    new_l = _eina_list_mempool_list_new(list);
 617    if (!new_l)
 618      return list;
 619
 620    EINA_MAGIC_CHECK_LIST(relative, NULL);
 621    new_l->next = relative->next;
 622    new_l->data = (void *)data;
 623
 624    if (relative->next)
 625      relative->next->prev = new_l;
 626
 627    relative->next = new_l;
 628    new_l->prev = relative;
 629
 630    _eina_list_update_accounting(list, new_l);
 631
 632    if (!new_l->next)
 633      new_l->accounting->last = new_l;
 634
 635    return list;
 636 }
 637
 638 EAPI Eina_List *
 639 eina_list_prepend_relative(Eina_List *list,
 640                            const void *data,
 641                            const void *relative)
 642 {
 643    Eina_List *l;
 644    void *list_data;
 645
 646    if (list)
 647      EINA_MAGIC_CHECK_LIST(list, NULL);
 648
 649    EINA_LIST_FOREACH(list, l, list_data)
 650      {
 651         if (list_data == relative)
 652           return eina_list_prepend_relative_list(list, data, l);
 653      }
 654    return eina_list_prepend(list, data);
 655 }
 656
 657 EAPI Eina_List *
 658 eina_list_prepend_relative_list(Eina_List *list,
 659                                 const void *data,
 660                                 Eina_List *relative)
 661 {
 662    Eina_List *new_l;
 663
 664    if ((!list) || (!relative))
 665      return eina_list_prepend(list, data);
 666
 667    eina_error_set(0);
 668    new_l = _eina_list_mempool_list_new(list);
 669    if (!new_l)
 670      return list;
 671
 672    EINA_MAGIC_CHECK_LIST(relative, NULL);
 673
 674    new_l->prev = relative->prev;
 675    new_l->next = relative;
 676    new_l->data = (void *)data;
 677
 678    if (relative->prev)
 679      relative->prev->next = new_l;
 680
 681    relative->prev = new_l;
 682
 683    _eina_list_update_accounting(list, new_l);
 684
 685    if (new_l->prev)
 686      return list;
 687
 688    return new_l;
 689 }
 690
 691 EAPI Eina_List *
 692 eina_list_sorted_insert(Eina_List *list, Eina_Compare_Cb func, const void *data)
 693 {
 694    Eina_List *lnear;
 695    int cmp;
 696
 697    if (!list)
 698      return eina_list_append(NULL, data);
 699
 700    lnear = eina_list_search_sorted_near_list(list, func, data, &cmp);
 701    if (cmp < 0)
 702      return eina_list_append_relative_list(list, data, lnear);
 703    else
 704      return eina_list_prepend_relative_list(list, data, lnear);
 705 }
 706
 707 EAPI Eina_List *
 708 eina_list_remove(Eina_List *list, const void *data)
 709 {
 710    Eina_List *l;
 711
 712    if (list)
 713      EINA_MAGIC_CHECK_LIST(list, NULL);
 714
 715    l = eina_list_data_find_list(list, data);
 716    return eina_list_remove_list(list, l);
 717 }
 718
 719 EAPI Eina_List *
 720 eina_list_remove_list(Eina_List *list, Eina_List *remove_list)
 721 {
 722    Eina_List *return_l;
 723
 724    if (!list)
 725      return NULL;
 726
 727    if (!remove_list)
 728      return list;
 729
 730    EINA_MAGIC_CHECK_LIST(remove_list, NULL);
 731
 732    if (remove_list->next)
 733      remove_list->next->prev = remove_list->prev;
 734
 735    if (remove_list->prev)
 736      {
 737         remove_list->prev->next = remove_list->next;
 738         return_l = list;
 739      }
 740    else
 741      return_l = remove_list->next;
 742
 743    if (remove_list == remove_list->accounting->last)
 744      {
 745         EINA_MAGIC_CHECK_LIST(list, NULL);
 746         list->accounting->last = remove_list->prev;
 747      }
 748
 749    _eina_list_mempool_list_free(remove_list);
 750    return return_l;
 751 }
 752
 753 EAPI Eina_List *
 754 eina_list_free(Eina_List *list)
 755 {
 756    Eina_List *l, *free_l;
 757
 758    if (!list)
 759      return NULL;
 760
 761    EINA_MAGIC_CHECK_LIST(list, NULL);
 762
 763    for (l = list; l; )
 764      {
 765         free_l = l;
 766         l = l->next;
 767
 768         _eina_list_mempool_list_free(free_l);
 769      }
 770
 771    return NULL;
 772 }
 773
 774 EAPI Eina_List *
 775 eina_list_promote_list(Eina_List *list, Eina_List *move_list)
 776 {
 777    if (!list)
 778      return NULL;
 779
 780    if (!move_list)
 781      {
 782         return list; /* Promoting head to be head. */
 783
 784      }
 785
 786    if (move_list == list)
 787      return list;
 788
 789    if (move_list->next == list)
 790      return move_list;
 791
 792    EINA_MAGIC_CHECK_LIST(list,      NULL);
 793    EINA_MAGIC_CHECK_LIST(move_list, NULL);
 794
 795    /* Remove the promoted item from the list. */
 796    if (!move_list->prev)
 797      move_list->next->prev = NULL;
 798    else
 799      {
 800         move_list->prev->next = move_list->next;
 801         if (move_list == list->accounting->last)
 802           list->accounting->last = move_list->prev;
 803         else
 804           move_list->next->prev = move_list->prev;
 805      }
 806
 807    /* Add the promoted item in the list. */
 808    move_list->next = list;
 809    move_list->prev = list->prev;
 810    list->prev = move_list;
 811    if (move_list->prev)
 812      move_list->prev->next = move_list;
 813
 814    return move_list;
 815 }
 816
 817 EAPI Eina_List *
 818 eina_list_demote_list(Eina_List *list, Eina_List *move_list)
 819 {
 820    if (!list)
 821      return NULL;
 822
 823    if (!move_list)
 824      {
 825         return list; /* Demoting tail to be tail. */
 826
 827      }
 828
 829    if (move_list == list->accounting->last)
 830      return list;
 831
 832    EINA_MAGIC_CHECK_LIST(list,      NULL);
 833    EINA_MAGIC_CHECK_LIST(move_list, NULL);
 834
 835    /* Update pointer list if necessary. */
 836    if (list == move_list)
 837      {
 838         list = move_list->next; /* Remove the demoted item from the list. */
 839
 840      }
 841
 842    if (move_list->prev)
 843      move_list->prev->next = move_list->next;
 844
 845    move_list->next->prev = move_list->prev;
 846    /* Add the demoted item in the list. */
 847    move_list->prev = list->accounting->last;
 848    move_list->prev->next = move_list;
 849    move_list->next = NULL;
 850    list->accounting->last = move_list;
 851
 852    return list;
 853 }
 854
 855 EAPI void *
 856 eina_list_data_find(const Eina_List *list, const void *data)
 857 {
 858    if (eina_list_data_find_list(list, data))
 859      return (void *)data;
 860
 861    return NULL;
 862 }
 863
 864 EAPI Eina_Bool
 865 eina_list_move(Eina_List **to, Eina_List **from, void *data)
 866 {
 867    Eina_List *l;
 868
 869    EINA_SAFETY_ON_NULL_RETURN_VAL(to, EINA_FALSE);
 870    EINA_SAFETY_ON_NULL_RETURN_VAL(from, EINA_FALSE);
 871    EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE);
 872
 873    if (*to) EINA_MAGIC_CHECK_LIST(*to, EINA_FALSE);
 874    EINA_MAGIC_CHECK_LIST(*from, EINA_FALSE);
 875
 876    l = eina_list_data_find_list(*from, data);
 877    EINA_SAFETY_ON_NULL_RETURN_VAL(l, EINA_FALSE);
 878
 879    *to = eina_list_append(*to, data);
 880    *from = eina_list_remove_list(*from, l);
 881    return EINA_TRUE;
 882 }
 883
 884 EAPI Eina_Bool
 885 eina_list_move_list(Eina_List **to, Eina_List **from, Eina_List *data)
 886 {
 887    EINA_SAFETY_ON_NULL_RETURN_VAL(to, EINA_FALSE);
 888    EINA_SAFETY_ON_NULL_RETURN_VAL(from, EINA_FALSE);
 889
 890    if (*to) EINA_MAGIC_CHECK_LIST(*to, EINA_FALSE);
 891    EINA_MAGIC_CHECK_LIST(*from, EINA_FALSE);
 892    EINA_MAGIC_CHECK_LIST(data, EINA_FALSE);
 893
 894    *to = eina_list_append(*to, data->data);
 895    *from = eina_list_remove_list(*from, data);
 896    return EINA_TRUE;
 897 }
 898
 899 EAPI Eina_List *
 900 eina_list_data_find_list(const Eina_List *list, const void *data)
 901 {
 902    const Eina_List *l;
 903    void *list_data;
 904
 905    if (list)
 906      EINA_MAGIC_CHECK_LIST(list, NULL);
 907
 908    EINA_LIST_FOREACH(list, l, list_data)
 909      {
 910         if (list_data == data)
 911           return (Eina_List *)l;
 912      }
 913
 914    return NULL;
 915 }
 916
 917 EAPI void *
 918 eina_list_nth(const Eina_List *list, unsigned int n)
 919 {
 920    Eina_List *l;
 921
 922    l = eina_list_nth_list(list, n);
 923    return l ? l->data : NULL;
 924 }
 925
 926 EAPI Eina_List *
 927 eina_list_nth_list(const Eina_List *list, unsigned int n)
 928 {
 929    const Eina_List *l;
 930    unsigned int i;
 931
 932    if (list)
 933      EINA_MAGIC_CHECK_LIST(list, NULL);
 934
 935    /* check for non-existing nodes */
 936    if ((!list) || (n > (list->accounting->count - 1)))
 937      return NULL;
 938
 939    /* if the node is in the 2nd half of the list, search from the end
 940     * else, search from the beginning.
 941     */
 942    if (n > (list->accounting->count / 2))
 943      for (i = list->accounting->count - 1,
 944           l = list->accounting->last;
 945           l;
 946           l = l->prev, i--)
 947        {
 948           if (i == n)
 949             return (Eina_List *)l;
 950        }
 951    else
 952      for (i = 0, l = list; l; l = l->next, i++)
 953        {
 954           if (i == n)
 955             return (Eina_List *)l;
 956        }
 957
 958    abort();
 959 }
 960
 961 EAPI Eina_List *
 962 eina_list_reverse(Eina_List *list)
 963 {
 964    Eina_List *l1, *l2;
 965
 966    if (!list)
 967      return NULL;
 968
 969    EINA_MAGIC_CHECK_LIST(list, NULL);
 970
 971    l1 = list;
 972    l2 = list->accounting->last;
 973    while (l1 != l2)
 974      {
 975         void *data;
 976
 977         data = l1->data;
 978         l1->data = l2->data;
 979         l2->data = data;
 980         l1 = l1->next;
 981         if (l1 == l2)
 982           break;
 983
 984         l2 = l2->prev;
 985      }
 986
 987    return list;
 988 }
 989
 990 EAPI Eina_List *
 991 eina_list_reverse_clone(const Eina_List *list)
 992 {
 993    const Eina_List *l;
 994    Eina_List *lclone;
 995    void *data;
 996
 997    if (!list)
 998      return NULL;
 999
1000    EINA_MAGIC_CHECK_LIST(list, NULL);
1001
1002    lclone = NULL;
1003    EINA_LIST_FOREACH(list, l, data)
1004       lclone = eina_list_prepend(lclone, data);
1005
1006    return lclone;
1007 }
1008
1009 EAPI Eina_List *
1010 eina_list_clone(const Eina_List *list)
1011 {
1012    const Eina_List *l;
1013    Eina_List *lclone;
1014    void *data;
1015
1016    if (!list)
1017      return NULL;
1018
1019    EINA_MAGIC_CHECK_LIST(list, NULL);
1020
1021    lclone = NULL;
1022    EINA_LIST_FOREACH(list, l, data)
1023       lclone = eina_list_append(lclone, data);
1024
1025    return lclone;
1026 }
1027
1028 EAPI Eina_List *
1029 eina_list_sort(Eina_List *list, unsigned int limit, Eina_Compare_Cb func)
1030 {
1031    unsigned int i = 0;
1032    unsigned int n = 0;
1033    Eina_List *tail = list;
1034    Eina_List *unsort = NULL;
1035    Eina_List *stack[EINA_LIST_SORT_STACK_SIZE];
1036
1037    EINA_SAFETY_ON_NULL_RETURN_VAL(func, list);
1038    if (!list)
1039      return NULL;
1040
1041    EINA_MAGIC_CHECK_LIST(list, NULL);
1042
1043    /* if the caller specified an invalid limit, sort the whole list */
1044    if ((limit == 0) ||
1045        (limit > list->accounting->count))
1046      limit = list->accounting->count;
1047
1048    if (limit != list->accounting->count)
1049      {
1050         unsort = eina_list_nth_list(list, limit);
1051         if (unsort)
1052           unsort->prev->next = NULL;
1053      }
1054
1055    while (tail)
1056      {
1057         unsigned int idx, tmp;
1058
1059         Eina_List *a = tail;
1060         Eina_List *b = tail->next;
1061
1062         if (!b)
1063           {
1064              stack[i++] = a;
1065              break;
1066           }
1067
1068         tail = b->next;
1069
1070         if (func(a->data, b->data) < 0)
1071           ((stack[i++] = a)->next = b)->next = 0;
1072         else
1073           ((stack[i++] = b)->next = a)->next = 0;
1074
1075         tmp = n++;
1076         for (idx = n ^ tmp; idx &= idx - 1; i--)
1077           stack[i - 2] = eina_list_sort_merge(stack[i - 2], stack[i - 1], func);
1078      }
1079
1080    while (i-- > 1)
1081      stack[i - 1] = eina_list_sort_merge(stack[i - 1], stack[i], func);
1082
1083    list = stack[0];
1084    tail = eina_list_sort_rebuild_prev(list);
1085
1086    if (unsort)
1087      {
1088         tail->next = unsort;
1089         unsort->prev = tail;
1090      }
1091    else
1092      list->accounting->last = tail;
1093
1094    return list;
1095 }
1096
1097 EAPI Eina_List *
1098 eina_list_merge(Eina_List *left, Eina_List *right)
1099 {
1100    unsigned int n_left, n_right;
1101
1102    if (!left)
1103      return right;
1104
1105    if (!right)
1106      return left;
1107
1108    left->accounting->last->next = right;
1109    right->prev = left->accounting->last;
1110
1111    n_left = left->accounting->count;
1112    n_right = right->accounting->count;
1113
1114    if (n_left >= n_right)
1115      {
1116         Eina_List *itr = right;
1117         left->accounting->last = right->accounting->last;
1118         left->accounting->count += n_right;
1119
1120         _eina_list_mempool_accounting_free(right->accounting);
1121
1122         do
1123           {
1124              itr->accounting = left->accounting;
1125              itr = itr->next;
1126           }
1127         while (itr);
1128      }
1129    else
1130      {
1131         Eina_List *itr = left->accounting->last;
1132         right->accounting->count += n_left;
1133
1134         _eina_list_mempool_accounting_free(left->accounting);
1135
1136         do
1137           {
1138              itr->accounting = right->accounting;
1139              itr = itr->prev;
1140           }
1141         while (itr);
1142      }
1143
1144    return left;
1145 }
1146
1147
1148 EAPI Eina_List *
1149 eina_list_split_list(Eina_List *list, Eina_List *relative, Eina_List **right)
1150 {
1151    Eina_List *next;
1152    Eina_List *itr;
1153
1154    if(!right)
1155      return list;
1156
1157    *right = NULL;
1158
1159    if (!list)
1160      return NULL;
1161
1162    if (!relative)
1163      {
1164         *right = list;
1165         return NULL;
1166      }
1167
1168    if (relative == eina_list_last(list))
1169      return list;
1170
1171    next = eina_list_next(relative);
1172    next->prev = NULL;
1173    next->accounting = _eina_list_mempool_accounting_new(next);
1174    next->accounting->last = list->accounting->last;
1175    next->accounting->count = 0;
1176    *right = next;
1177
1178    itr = next;
1179    do
1180      {
1181         itr->accounting = next->accounting;
1182         next->accounting->count++;
1183         itr = itr->next;
1184      }
1185    while (itr);
1186
1187    relative->next = NULL;
1188    list->accounting->last = relative;
1189    list->accounting->count = list->accounting->count - next->accounting->count;
1190
1191    return list;
1192 }
1193
1194 EAPI Eina_List *
1195 eina_list_sorted_merge(Eina_List *left, Eina_List *right, Eina_Compare_Cb func)
1196 {
1197    Eina_List *ret;
1198    Eina_List *current;
1199
1200    EINA_SAFETY_ON_NULL_RETURN_VAL(func, NULL);
1201
1202    if (!left)
1203      return right;
1204
1205    if (!right)
1206      return left;
1207
1208    if (func(left->data, right->data) < 0)
1209      {
1210         ret = left;
1211         current = left;
1212         left = left->next;
1213         ret->accounting->count += right->accounting->count;
1214
1215         _eina_list_mempool_accounting_free(right->accounting);
1216      }
1217    else
1218      {
1219         ret = right;
1220         current = right;
1221         right = right->next;
1222         ret->accounting->count += left->accounting->count;
1223
1224         _eina_list_mempool_accounting_free(left->accounting);
1225      }
1226
1227    while (left && right)
1228      {
1229         if (func(left->data, right->data) < 0)
1230           {
1231              current->next = left;
1232              left->prev = current;
1233              left = left->next;
1234           }
1235         else
1236           {
1237              current->next = right;
1238              right->prev = current;
1239              right = right->next;
1240           }
1241
1242         current = current->next;
1243         current->accounting = ret->accounting;
1244      }
1245
1246    if (left)
1247      {
1248         current->next = left;
1249         left->prev = current;
1250         current->accounting = ret->accounting;
1251      }
1252
1253    if (right)
1254      {
1255         current->next = right;
1256         right->prev = current;
1257         current->accounting = ret->accounting;
1258      }
1259
1260    while (current->next)
1261      {
1262         current = current->next;
1263         current->accounting = ret->accounting;
1264      }
1265
1266    ret->accounting->last = current;
1267
1268    return ret;
1269 }
1270
1271 EAPI Eina_List *
1272 eina_list_search_sorted_near_list(const Eina_List *list,
1273                                   Eina_Compare_Cb func,
1274                                   const void *data,
1275                                   int *result_cmp)
1276 {
1277    const Eina_List *ct;
1278    unsigned int inf, sup, cur;
1279    int cmp;
1280
1281    if (!list)
1282      {
1283         if (result_cmp)
1284           *result_cmp = 0;
1285
1286         return NULL;
1287      }
1288
1289    if (list->accounting->count == 1)
1290      {
1291         if (result_cmp)
1292           *result_cmp = func(list->data, data);
1293
1294         return (Eina_List *)list;
1295      }
1296
1297    /* list walk is expensive, do quick check: tail */
1298    ct = list->accounting->last;
1299    cmp = func(ct->data, data);
1300    if (cmp <= 0)
1301      goto end;
1302
1303    /* list walk is expensive, do quick check: head */
1304    ct = list;
1305    cmp = func(ct->data, data);
1306    if (cmp >= 0)
1307      goto end;
1308
1309    /* inclusive bounds */
1310    inf = 1;
1311    sup = list->accounting->count - 2;
1312    cur = 1;
1313    ct = list->next;
1314
1315    /* no loop, just compare if comparison value is important to caller */
1316    if (inf > sup)
1317      {
1318         if (result_cmp)
1319           cmp = func(ct->data, data);
1320
1321         goto end;
1322      }
1323
1324    while (inf <= sup)
1325      {
1326         unsigned int tmp = cur;
1327         cur = inf + ((sup - inf) >> 1);
1328         if      (tmp < cur)
1329           for (; tmp != cur; tmp++, ct = ct->next) ;
1330         else if (tmp > cur)
1331           for (; tmp != cur; tmp--, ct = ct->prev) ;
1332
1333         cmp = func(ct->data, data);
1334         if (cmp == 0)
1335           break;
1336         else if (cmp < 0)
1337           inf = cur + 1;
1338         else if (cmp > 0)
1339           {
1340              if (cur > 0)
1341                sup = cur - 1;
1342              else
1343                break;
1344           }
1345         else
1346           break;
1347      }
1348
1349 end:
1350    if (result_cmp)
1351      *result_cmp = cmp;
1352
1353    return (Eina_List *)ct;
1354 }
1355
1356 EAPI Eina_List *
1357 eina_list_search_sorted_list(const Eina_List *list,
1358                              Eina_Compare_Cb func,
1359                              const void *data)
1360 {
1361    Eina_List *lnear;
1362    int cmp;
1363
1364    lnear = eina_list_search_sorted_near_list(list, func, data, &cmp);
1365    if (!lnear)
1366      return NULL;
1367
1368    if (cmp == 0)
1369      return lnear;
1370
1371    return NULL;
1372 }
1373
1374
1375 EAPI void *
1376 eina_list_search_sorted(const Eina_List *list,
1377                         Eina_Compare_Cb func,
1378                         const void *data)
1379 {
1380    return eina_list_data_get(eina_list_search_sorted_list(list, func, data));
1381 }
1382
1383 EAPI Eina_List *
1384 eina_list_search_unsorted_list(const Eina_List *list,
1385                                Eina_Compare_Cb func,
1386                                const void *data)
1387 {
1388    const Eina_List *l;
1389    void *d;
1390
1391    EINA_LIST_FOREACH(list, l, d)
1392      {
1393         if (!func(d, data))
1394           return (Eina_List *)l;
1395      }
1396    return NULL;
1397 }
1398
1399 EAPI void *
1400 eina_list_search_unsorted(const Eina_List *list,
1401                           Eina_Compare_Cb func,
1402                           const void *data)
1403 {
1404    return eina_list_data_get(eina_list_search_unsorted_list(list, func, data));
1405 }
1406
1407
1408 EAPI Eina_Iterator *
1409 eina_list_iterator_new(const Eina_List *list)
1410 {
1411    Eina_Iterator_List *it;
1412
1413    eina_error_set(0);
1414    it = calloc(1, sizeof (Eina_Iterator_List));
1415    if (!it)
1416      {
1417         eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1418         return NULL;
1419      }
1420
1421    EINA_MAGIC_SET(it,            EINA_MAGIC_LIST_ITERATOR);
1422    EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1423
1424    it->head = list;
1425    it->current = list;
1426
1427    it->iterator.version = EINA_ITERATOR_VERSION;
1428    it->iterator.next = FUNC_ITERATOR_NEXT(eina_list_iterator_next);
1429    it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
1430       eina_list_iterator_get_container);
1431    it->iterator.free = FUNC_ITERATOR_FREE(eina_list_iterator_free);
1432
1433    return &it->iterator;
1434 }
1435
1436 EAPI Eina_Iterator *
1437 eina_list_iterator_reversed_new(const Eina_List *list)
1438 {
1439    Eina_Iterator_List *it;
1440
1441    eina_error_set(0);
1442    it = calloc(1, sizeof (Eina_Iterator_List));
1443    if (!it)
1444      {
1445         eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1446         return NULL;
1447      }
1448
1449    EINA_MAGIC_SET(it,            EINA_MAGIC_LIST_ITERATOR);
1450    EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1451
1452    it->head = eina_list_last(list);
1453    it->current = it->head;
1454
1455    it->iterator.version = EINA_ITERATOR_VERSION;
1456    it->iterator.next = FUNC_ITERATOR_NEXT(eina_list_iterator_prev);
1457    it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
1458       eina_list_iterator_get_container);
1459    it->iterator.free = FUNC_ITERATOR_FREE(eina_list_iterator_free);
1460
1461    return &it->iterator;
1462 }
1463
1464 EAPI Eina_Accessor *
1465 eina_list_accessor_new(const Eina_List *list)
1466 {
1467    Eina_Accessor_List *ac;
1468
1469    eina_error_set(0);
1470    ac = calloc(1, sizeof (Eina_Accessor_List));
1471    if (!ac)
1472      {
1473         eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1474         return NULL;
1475      }
1476
1477    EINA_MAGIC_SET(ac,            EINA_MAGIC_LIST_ACCESSOR);
1478    EINA_MAGIC_SET(&ac->accessor, EINA_MAGIC_ACCESSOR);
1479
1480    ac->head = list;
1481    ac->current = list;
1482    ac->index = 0;
1483
1484    ac->accessor.version = EINA_ACCESSOR_VERSION;
1485    ac->accessor.get_at = FUNC_ACCESSOR_GET_AT(eina_list_accessor_get_at);
1486    ac->accessor.get_container = FUNC_ACCESSOR_GET_CONTAINER(
1487       eina_list_accessor_get_container);
1488    ac->accessor.free = FUNC_ACCESSOR_FREE(eina_list_accessor_free);
1489
1490    return &ac->accessor;
1491 }