src/lib/eina_inlist.c

   1 /* EINA - EFL data type library
   2  * Copyright (C) 2002-2008 Carsten Haitzler, Vincent Torri
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2.1 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library;
  16  * if not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19 #ifdef HAVE_CONFIG_H
  20 # include "config.h"
  21 #endif
  22
  23 #include <stdlib.h>
  24 #include <assert.h>
  25
  26 #include <stdio.h>
  27
  28 #include "eina_config.h"
  29 #include "eina_private.h"
  30 #include "eina_error.h"
  31 #include "eina_log.h"
  32
  33 /* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */
  34 #include "eina_safety_checks.h"
  35 #include "eina_inlist.h"
  36
  37 /* FIXME: TODO please, refactor this :) */
  38
  39 /*============================================================================*
  40 *                                  Local                                     *
  41 *============================================================================*/
  42
  43 /**
  44  * @cond LOCAL
  45  */
  46
  47 #define EINA_INLIST_SORT_STACK_SIZE 32
  48
  49 typedef struct _Eina_Iterator_Inlist Eina_Iterator_Inlist;
  50 typedef struct _Eina_Accessor_Inlist Eina_Accessor_Inlist;
  51
  52 struct _Eina_Iterator_Inlist
  53 {
  54    Eina_Iterator iterator;
  55    const Eina_Inlist *head;
  56    const Eina_Inlist *current;
  57 };
  58
  59 struct _Eina_Accessor_Inlist
  60 {
  61    Eina_Accessor accessor;
  62
  63    const Eina_Inlist *head;
  64    const Eina_Inlist *current;
  65
  66    unsigned int index;
  67 };
  68
  69 struct _Eina_Inlist_Sorted_State
  70 {
  71    Eina_Inlist *jump_table[EINA_INLIST_JUMP_SIZE];
  72
  73    unsigned short jump_limit;
  74    int jump_div;
  75
  76    int inserted;
  77 };
  78
  79 static Eina_Bool
  80 eina_inlist_iterator_next(Eina_Iterator_Inlist *it, void **data) {
  81    if (!it->current)
  82       return EINA_FALSE;
  83
  84    if (data)
  85       *data = (void *)it->current;
  86
  87    it->current = it->current->next;
  88
  89    return EINA_TRUE;
  90 }
  91
  92 static Eina_Inlist *
  93 eina_inlist_iterator_get_container(Eina_Iterator_Inlist *it) {
  94    return (Eina_Inlist *)it->head;
  95 }
  96
  97 static void
  98 eina_inlist_iterator_free(Eina_Iterator_Inlist *it) {
  99    free(it);
 100 }
 101
 102 static Eina_Bool
 103 eina_inlist_accessor_get_at(Eina_Accessor_Inlist *it,
 104                             unsigned int idx,
 105                             void **data) {
 106    const Eina_Inlist *over;
 107    unsigned int middle;
 108    unsigned int i;
 109
 110    if (it->index == idx)
 111       over = it->current;
 112    else if (idx > it->index)
 113       /* Looking after current. */
 114       for (i = it->index, over = it->current;
 115            i < idx && over;
 116            ++i, over = over->next)
 117          ;
 118    else
 119      {
 120         middle = it->index >> 1;
 121
 122         if (idx > middle)
 123            /* Looking backward from current. */
 124            for (i = it->index, over = it->current;
 125                 i > idx && over;
 126                 --i, over = over->prev)
 127               ;
 128         else
 129            /* Looking from the start. */
 130            for (i = 0, over = it->head;
 131                 i < idx && over;
 132                 ++i, over = over->next)
 133               ;
 134      }
 135
 136    if (!over)
 137       return EINA_FALSE;
 138
 139    it->current = over;
 140    it->index = idx;
 141
 142    if (data)
 143       *data = (void *)over;
 144
 145    return EINA_TRUE;
 146 }
 147
 148 static Eina_Inlist *
 149 eina_inlist_accessor_get_container(Eina_Accessor_Inlist *it) {
 150    return (Eina_Inlist *)it->head;
 151 }
 152
 153 static void
 154 eina_inlist_accessor_free(Eina_Accessor_Inlist *it) {
 155    free(it);
 156 }
 157
 158 static Eina_Inlist *
 159 eina_inlist_sort_merge(Eina_Inlist *a, Eina_Inlist *b, Eina_Compare_Cb func)
 160 {
 161    Eina_Inlist *first, *last;
 162
 163    if (func(a, b) < 0)
 164       a = (last = first = a)->next;
 165    else
 166       b = (last = first = b)->next;
 167
 168    while (a && b)
 169       if (func(a, b) < 0)
 170          a = (last = last->next = a)->next;
 171       else
 172          b = (last = last->next = b)->next;
 173
 174    last->next = a ? a : b;
 175
 176    return first;
 177 }
 178
 179 static Eina_Inlist *
 180 eina_inlist_sort_rebuild_prev(Eina_Inlist *list)
 181 {
 182    Eina_Inlist *prev = NULL;
 183
 184    for (; list; list = list->next)
 185      {
 186         list->prev = prev;
 187         prev = list;
 188      }
 189
 190    return prev;
 191 }
 192
 193 static void
 194 _eina_inlist_sorted_state_compact(Eina_Inlist_Sorted_State *state)
 195 {
 196    unsigned short i, j;
 197
 198    /* compress the jump table */
 199    state->jump_div *= 2;
 200    state->jump_limit /= 2;
 201
 202    for (i = 2, j = 1;
 203         i < EINA_INLIST_JUMP_SIZE;
 204         i += 2, j++)
 205      state->jump_table[j] = state->jump_table[i];
 206 }
 207
 208 /**
 209  * @endcond
 210  */
 211
 212
 213 /*============================================================================*
 214 *                                 Global                                     *
 215 *============================================================================*/
 216
 217 /*============================================================================*
 218 *                                   API                                      *
 219 *============================================================================*/
 220
 221 EAPI Eina_Inlist *
 222 eina_inlist_append(Eina_Inlist *list, Eina_Inlist *new_l)
 223 {
 224    Eina_Inlist *l;
 225
 226    EINA_SAFETY_ON_NULL_RETURN_VAL(new_l, list);
 227
 228    new_l->next = NULL;
 229    if (!list)
 230      {
 231         new_l->prev = NULL;
 232         new_l->last = new_l;
 233         return new_l;
 234      }
 235
 236    if (list->last)
 237       l = list->last;
 238    else
 239       for (l = list; (l) && (l->next); l = l->next)
 240          ;
 241
 242    l->next = new_l;
 243    new_l->prev = l;
 244    list->last = new_l;
 245    return list;
 246 }
 247
 248 EAPI Eina_Inlist *
 249 eina_inlist_prepend(Eina_Inlist *list, Eina_Inlist *new_l)
 250 {
 251    EINA_SAFETY_ON_NULL_RETURN_VAL(new_l, list);
 252
 253    new_l->prev = NULL;
 254    if (!list)
 255      {
 256         new_l->next = NULL;
 257         new_l->last = new_l;
 258         return new_l;
 259      }
 260
 261    new_l->next = list;
 262    list->prev = new_l;
 263    new_l->last = list->last;
 264    list->last = NULL;
 265    return new_l;
 266 }
 267
 268 EAPI Eina_Inlist *
 269 eina_inlist_append_relative(Eina_Inlist *list,
 270                             Eina_Inlist *new_l,
 271                             Eina_Inlist *relative)
 272 {
 273    EINA_SAFETY_ON_NULL_RETURN_VAL(new_l, list);
 274
 275    if (relative)
 276      {
 277         if (relative->next)
 278           {
 279              new_l->next = relative->next;
 280              relative->next->prev = new_l;
 281           }
 282         else
 283            new_l->next = NULL;
 284
 285         relative->next = new_l;
 286         new_l->prev = relative;
 287         if (!new_l->next)
 288            list->last = new_l;
 289
 290         return list;
 291      }
 292
 293    return eina_inlist_append(list, new_l);
 294 }
 295
 296 EAPI Eina_Inlist *
 297 eina_inlist_prepend_relative(Eina_Inlist *list,
 298                              Eina_Inlist *new_l,
 299                              Eina_Inlist *relative)
 300 {
 301    EINA_SAFETY_ON_NULL_RETURN_VAL(new_l, list);
 302
 303    if (relative)
 304      {
 305         new_l->prev = relative->prev;
 306         new_l->next = relative;
 307         relative->prev = new_l;
 308         if (new_l->prev)
 309           {
 310              new_l->prev->next = new_l;
 311              /* new_l->next could not be NULL, as it was set to 'relative' */
 312              assert(new_l->next);
 313              return list;
 314           }
 315         else
 316           {
 317              /* new_l->next could not be NULL, as it was set to 'relative' */
 318              assert(new_l->next);
 319
 320              new_l->last = list->last;
 321              list->last = NULL;
 322              return new_l;
 323           }
 324      }
 325
 326    return eina_inlist_prepend(list, new_l);
 327 }
 328
 329 EAPI Eina_Inlist *
 330 eina_inlist_remove(Eina_Inlist *list, Eina_Inlist *item)
 331 {
 332    Eina_Inlist *return_l;
 333
 334    /* checkme */
 335    EINA_SAFETY_ON_NULL_RETURN_VAL(list, NULL);
 336    EINA_SAFETY_ON_NULL_RETURN_VAL(item, list);
 337    if (EINA_UNLIKELY((item != list) && (!item->prev) && (!item->next)))
 338      {
 339         eina_error_set(EINA_ERROR_SAFETY_FAILED);
 340         EINA_LOG_ERR("safety check failed: item %p does not appear to be part of an inlist!", item);
 341         return list;
 342      }
 343
 344    if (item->next)
 345       item->next->prev = item->prev;
 346
 347    if (item->prev)
 348      {
 349         item->prev->next = item->next;
 350         return_l = list;
 351      }
 352    else
 353      {
 354         return_l = item->next;
 355         if (return_l)
 356            return_l->last = list->last;
 357      }
 358
 359    if (item == list->last)
 360       list->last = item->prev;
 361
 362    item->next = NULL;
 363    item->prev = NULL;
 364    return return_l;
 365 }
 366
 367 EAPI Eina_Inlist *
 368 eina_inlist_promote(Eina_Inlist *list, Eina_Inlist *item)
 369 {
 370    EINA_SAFETY_ON_NULL_RETURN_VAL(list, NULL);
 371    EINA_SAFETY_ON_NULL_RETURN_VAL(item, list);
 372
 373    if (item == list)
 374       return list;
 375
 376    if (item->next)
 377       item->next->prev = item->prev;
 378
 379    item->prev->next = item->next;
 380
 381    if (list->last == item)
 382       list->last = item->prev;
 383
 384    item->next = list;
 385    item->prev = NULL;
 386    item->last = list->last;
 387
 388    list->prev = item;
 389    list->last = NULL;
 390
 391    return item;
 392 }
 393
 394 EAPI Eina_Inlist *
 395 eina_inlist_demote(Eina_Inlist *list, Eina_Inlist *item)
 396 {
 397    Eina_Inlist *l;
 398
 399    EINA_SAFETY_ON_NULL_RETURN_VAL(list, NULL);
 400    EINA_SAFETY_ON_NULL_RETURN_VAL(item, list);
 401
 402    if (list->last == item)
 403       return list;
 404
 405    if (!list->last)
 406      {
 407         for (l = list; l->next; l = l->next)
 408            ;
 409         list->last = l;
 410      }
 411
 412    l = list;
 413    if (item->prev)
 414       item->prev->next = item->next;
 415    else
 416       l = item->next;
 417
 418    item->next->prev = item->prev;
 419
 420    list->last->next = item;
 421    item->prev = list->last;
 422    item->next = NULL;
 423
 424    l->last = item;
 425    return l;
 426 }
 427
 428 EAPI Eina_Inlist *
 429 eina_inlist_find(Eina_Inlist *list, Eina_Inlist *item)
 430 {
 431    Eina_Inlist *l;
 432
 433    EINA_SAFETY_ON_NULL_RETURN_VAL(item, NULL);
 434
 435    for (l = list; l; l = l->next) {
 436         if (l == item)
 437            return item;
 438      }
 439    return NULL;
 440 }
 441
 442 EAPI unsigned int
 443 eina_inlist_count(const Eina_Inlist *list)
 444 {
 445    const Eina_Inlist *l;
 446    unsigned int i = 0;
 447
 448    for (l = list; l; l = l->next)
 449       i++;
 450
 451    return i;
 452 }
 453
 454 EAPI int
 455 eina_inlist_sorted_state_init(Eina_Inlist_Sorted_State *state, Eina_Inlist *list)
 456 {
 457    Eina_Inlist *ct = NULL;
 458    int count = 0;
 459    int jump_count = 1;
 460
 461    /*
 462     * prepare a jump table to avoid doing unnecessary rewalk
 463     * of the inlist as much as possible.
 464     */
 465    for (ct = list; ct; ct = ct->next, jump_count++, count++)
 466      {
 467         if (jump_count == state->jump_div)
 468           {
 469              if (state->jump_limit == EINA_INLIST_JUMP_SIZE)
 470                {
 471                   _eina_inlist_sorted_state_compact(state);
 472                }
 473
 474              state->jump_table[state->jump_limit] = ct;
 475              state->jump_limit++;
 476              jump_count = 0;
 477           }
 478      }
 479
 480    state->inserted = count;
 481    return count;
 482 }
 483
 484 EAPI Eina_Inlist_Sorted_State *
 485 eina_inlist_sorted_state_new(void)
 486 {
 487    Eina_Inlist_Sorted_State *r;
 488
 489    r = calloc(1, sizeof (Eina_Inlist_Sorted_State));
 490    if (!r) return NULL;
 491
 492    r->jump_div = 1;
 493
 494    return r;
 495 }
 496
 497 EAPI void
 498 eina_inlist_sorted_state_free(Eina_Inlist_Sorted_State *state)
 499 {
 500    free(state);
 501 }
 502
 503 static void
 504 _eina_inlist_sorted_state_insert(Eina_Inlist_Sorted_State *state,
 505                                  unsigned short idx,
 506                                  int offset)
 507 {
 508    Eina_Inlist *last;
 509    int jump_count;
 510    int start;
 511
 512    state->inserted++;
 513
 514    if (offset != 0) idx++;
 515    for (; idx < state->jump_limit; idx++)
 516      {
 517         state->jump_table[idx] = state->jump_table[idx]->prev;
 518      }
 519
 520    start = state->jump_limit - 3;
 521    if (start < 0)
 522      start = 0;
 523
 524    last = state->jump_table[start];
 525    start++;
 526
 527    /* Correctly rebuild end of list */
 528    for (jump_count = 0; last->next != NULL; last = last->next, jump_count++)
 529      {
 530         if (jump_count == state->jump_div)
 531           {
 532              if (state->jump_limit == start)
 533                {
 534                   if (state->jump_limit == EINA_INLIST_JUMP_SIZE)
 535                     {
 536                        _eina_inlist_sorted_state_compact(state);
 537                        start = state->jump_limit - 1;
 538                        continue ;
 539                     }
 540                   else
 541                     {
 542                        state->jump_limit++;
 543                     }
 544                }
 545
 546              state->jump_table[start++] = last;
 547              jump_count = 0;
 548           }
 549      }
 550 }
 551
 552 EAPI Eina_Inlist *
 553 eina_inlist_sorted_insert(Eina_Inlist *list,
 554                           Eina_Inlist *item,
 555                           Eina_Compare_Cb func)
 556 {
 557    Eina_Inlist *ct = NULL;
 558    Eina_Inlist_Sorted_State state;
 559    int cmp = 0;
 560    int inf, sup;
 561    int cur = 0;
 562    int count;
 563
 564    EINA_SAFETY_ON_NULL_RETURN_VAL(item, list);
 565    EINA_SAFETY_ON_NULL_RETURN_VAL(func, list);
 566
 567    if (!list) return eina_inlist_append(NULL, item);
 568
 569    if (!list->next)
 570      {
 571         cmp = func(list, item);
 572
 573         if (cmp < 0)
 574           return eina_inlist_append(list, item);
 575         return eina_inlist_prepend(list, item);
 576      }
 577
 578    state.jump_div = 1;
 579    state.jump_limit = 0;
 580    count = eina_inlist_sorted_state_init(&state, list);
 581
 582    /*
 583     * now do a dychotomic search directly inside the jump_table.
 584     */
 585    inf = 0;
 586    sup = state.jump_limit - 1;
 587    cur = 0;
 588    ct = state.jump_table[cur];
 589    cmp = func(ct, item);
 590
 591    while (inf <= sup)
 592      {
 593         cur = inf + ((sup - inf) >> 1);
 594         ct = state.jump_table[cur];
 595
 596         cmp = func(ct, item);
 597         if (cmp == 0)
 598           break ;
 599         else if (cmp < 0)
 600           inf = cur + 1;
 601         else if (cmp > 0)
 602           {
 603              if (cur > 0)
 604                sup = cur - 1;
 605              else
 606                break;
 607           }
 608         else
 609           break;
 610      }
 611
 612    /* If at the beginning of the table and cmp < 0,
 613     * insert just after the head */
 614    if (cur == 0 && cmp > 0)
 615      return eina_inlist_prepend_relative(list, item, ct);
 616
 617    /* If at the end of the table and cmp >= 0,
 618     * just append the item to the list */
 619    if (cmp < 0 && ct == list->last)
 620      return eina_inlist_append(list, item);
 621
 622    /*
 623     * Now do a dychotomic search between two entries inside the jump_table
 624     */
 625    cur *= state.jump_div;
 626    inf = cur - state.jump_div - 1;
 627    sup = cur + state.jump_div + 1;
 628
 629    if (sup > count - 1) sup = count - 1;
 630    if (inf < 0) inf = 0;
 631
 632    while (inf <= sup)
 633      {
 634         int tmp = cur;
 635
 636         cur = inf + ((sup - inf) >> 1);
 637         if (tmp < cur)
 638           for (; tmp != cur; tmp++, ct = ct->next);
 639         else if (tmp > cur)
 640           for (; tmp != cur; tmp--, ct = ct->prev);
 641
 642         cmp = func(ct, item);
 643         if (cmp == 0)
 644           break ;
 645         else if (cmp < 0)
 646           inf = cur + 1;
 647         else if (cmp > 0)
 648           {
 649              if (cur > 0)
 650                sup = cur - 1;
 651              else
 652                break;
 653           }
 654         else
 655           break;
 656      }
 657
 658    if (cmp <= 0)
 659      return eina_inlist_append_relative(list, item, ct);
 660    return eina_inlist_prepend_relative(list, item, ct);
 661 }
 662
 663 EAPI Eina_Inlist *
 664 eina_inlist_sorted_state_insert(Eina_Inlist *list,
 665                                 Eina_Inlist *item,
 666                                 Eina_Compare_Cb func,
 667                                 Eina_Inlist_Sorted_State *state)
 668 {
 669    Eina_Inlist *ct = NULL;
 670    int cmp = 0;
 671    int inf, sup;
 672    int cur = 0;
 673    int count;
 674    unsigned short head;
 675    unsigned int offset;
 676
 677    if (!list)
 678      {
 679         state->inserted = 1;
 680         state->jump_limit = 1;
 681         state->jump_table[0] = item;
 682         return eina_inlist_append(NULL, item);
 683      }
 684
 685    if (!list->next)
 686      {
 687         cmp = func(list, item);
 688
 689         state->jump_limit = 2;
 690         state->inserted = 2;
 691
 692         if (cmp < 0)
 693           {
 694              state->jump_table[1] = item;
 695              return eina_inlist_append(list, item);
 696           }
 697         state->jump_table[1] = state->jump_table[0];
 698         state->jump_table[0] = item;
 699         return eina_inlist_prepend(list, item);
 700      }
 701
 702    count = state->inserted;
 703
 704    /*
 705     * now do a dychotomic search directly inside the jump_table.
 706     */
 707    inf = 0;
 708    sup = state->jump_limit - 1;
 709    cur = 0;
 710    ct = state->jump_table[cur];
 711    cmp = func(ct, item);
 712
 713    while (inf <= sup)
 714      {
 715         cur = inf + ((sup - inf) >> 1);
 716         ct = state->jump_table[cur];
 717
 718         cmp = func(ct, item);
 719         if (cmp == 0)
 720           break ;
 721         else if (cmp < 0)
 722           inf = cur + 1;
 723         else if (cmp > 0)
 724           {
 725              if (cur > 0)
 726                sup = cur - 1;
 727              else
 728                break;
 729           }
 730         else
 731           break;
 732      }
 733
 734    /* If at the beginning of the table and cmp < 0,
 735     * insert just after the head */
 736    if (cur == 0 && cmp > 0)
 737      {
 738         ct = eina_inlist_prepend_relative(list, item, ct);
 739         _eina_inlist_sorted_state_insert(state, 0, 0);
 740         return ct;
 741      }
 742
 743    /* If at the end of the table and cmp >= 0,
 744     * just append the item to the list */
 745    if (cmp < 0 && ct == list->last)
 746      {
 747         ct = eina_inlist_append(list, item);
 748         _eina_inlist_sorted_state_insert(state, state->jump_limit - 1, 1);
 749         return ct;
 750      }
 751
 752    /*
 753     * Now do a dychotomic search between two entries inside the jump_table
 754     */
 755    cur *= state->jump_div;
 756    inf = cur - state->jump_div - 1;
 757    sup = cur + state->jump_div + 1;
 758
 759    if (sup > count - 1) sup = count - 1;
 760    if (inf < 0) inf = 0;
 761
 762    while (inf <= sup)
 763      {
 764         int tmp = cur;
 765
 766         cur = inf + ((sup - inf) >> 1);
 767         if (tmp < cur)
 768           for (; tmp != cur; tmp++, ct = ct->next);
 769         else if (tmp > cur)
 770           for (; tmp != cur; tmp--, ct = ct->prev);
 771
 772         cmp = func(ct, item);
 773         if (cmp == 0)
 774           break ;
 775         else if (cmp < 0)
 776           inf = cur + 1;
 777         else if (cmp > 0)
 778           {
 779              if (cur > 0)
 780                sup = cur - 1;
 781              else
 782                break;
 783           }
 784         else
 785           break;
 786      }
 787
 788    if (cmp <= 0)
 789      {
 790         cur++;
 791
 792         ct = eina_inlist_append_relative(list, item, ct);
 793      }
 794    else
 795      {
 796         ct = eina_inlist_prepend_relative(list, item, ct);
 797      }
 798
 799    head = cur / state->jump_div;
 800    offset = cur % state->jump_div;
 801
 802    _eina_inlist_sorted_state_insert(state, head, offset);
 803    return ct;
 804 }
 805
 806 EAPI Eina_Inlist *
 807 eina_inlist_sort(Eina_Inlist *head, Eina_Compare_Cb func)
 808 {
 809   unsigned int i = 0;
 810   unsigned int n = 0;
 811   Eina_Inlist *tail = head;
 812   Eina_Inlist *unsort = NULL;
 813   Eina_Inlist *stack[EINA_INLIST_SORT_STACK_SIZE];
 814
 815   EINA_SAFETY_ON_NULL_RETURN_VAL(head, NULL);
 816   EINA_SAFETY_ON_NULL_RETURN_VAL(func, head);
 817
 818   while (tail)
 819     {
 820       unsigned int idx, tmp;
 821
 822       Eina_Inlist *a = tail;
 823       Eina_Inlist *b = tail->next;
 824
 825       if (!b)
 826         {
 827           stack[i++] = a;
 828           break;
 829         }
 830
 831       tail = b->next;
 832
 833       if (func(a, b) < 0)
 834         ((stack[i++] = a)->next = b)->next = 0;
 835       else
 836         ((stack[i++] = b)->next = a)->next = 0;
 837
 838       tmp = n++;
 839       for (idx = n ^ tmp; idx &= idx - 1; i--)
 840         stack[i - 2] = eina_inlist_sort_merge(stack[i - 2], stack[i - 1], func);
 841      }
 842
 843    while (i-- > 1)
 844       stack[i - 1] = eina_inlist_sort_merge(stack[i - 1], stack[i], func);
 845
 846    head = stack[0];
 847    tail = eina_inlist_sort_rebuild_prev(head);
 848
 849    if (unsort)
 850      {
 851         tail->next = unsort;
 852         unsort->prev = tail;
 853      }
 854
 855    head->last = tail;
 856
 857    return head;
 858
 859 }
 860
 861 EAPI Eina_Iterator *
 862 eina_inlist_iterator_new(const Eina_Inlist *list)
 863 {
 864    Eina_Iterator_Inlist *it;
 865
 866    eina_error_set(0);
 867    it = calloc(1, sizeof (Eina_Iterator_Inlist));
 868    if (!it)
 869      {
 870         eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 871         return NULL;
 872      }
 873
 874    it->head = list;
 875    it->current = list;
 876
 877    it->iterator.version = EINA_ITERATOR_VERSION;
 878    it->iterator.next = FUNC_ITERATOR_NEXT(eina_inlist_iterator_next);
 879    it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
 880          eina_inlist_iterator_get_container);
 881    it->iterator.free = FUNC_ITERATOR_FREE(eina_inlist_iterator_free);
 882
 883    EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
 884
 885    return &it->iterator;
 886 }
 887
 888 EAPI Eina_Accessor *
 889 eina_inlist_accessor_new(const Eina_Inlist *list)
 890 {
 891    Eina_Accessor_Inlist *ac;
 892
 893         eina_error_set(0);
 894    ac = calloc(1, sizeof (Eina_Accessor_Inlist));
 895    if (!ac)
 896      {
 897         eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 898         return NULL;
 899      }
 900
 901    ac->head = list;
 902    ac->current = list;
 903    ac->index = 0;
 904
 905    ac->accessor.version = EINA_ACCESSOR_VERSION;
 906    ac->accessor.get_at = FUNC_ACCESSOR_GET_AT(eina_inlist_accessor_get_at);
 907    ac->accessor.get_container = FUNC_ACCESSOR_GET_CONTAINER(
 908          eina_inlist_accessor_get_container);
 909    ac->accessor.free = FUNC_ACCESSOR_FREE(eina_inlist_accessor_free);
 910
 911    EINA_MAGIC_SET(&ac->accessor, EINA_MAGIC_ACCESSOR);
 912
 913    return &ac->accessor;
 914 }