efl

1
#ifdef HAVE_CONFIG_H
2
# include <config.h>
3
#endif
4

5
#include <stdlib.h>
6
#include <string.h>
7

8
#include "Ecore_Data.h"
9

10
/* Some tests showed that beyond that value heap sort is faster than merge sort
11
 * (in this implementation). This value has to be changed or at least review
12
 * if someone is changing the implementation. */
13
#define ECORE_MERGESORT_LIMIT 40000
14

15
/* Return information about the list */
16
static void *           _ecore_list_current(Ecore_List *list);
17

18
/* Adding functions */
19
static int              _ecore_list_insert(Ecore_List *list,
20
                                           Ecore_List_Node *node);
21
static int              _ecore_list_append_0(Ecore_List *list,
22
                                             Ecore_List_Node *node);
23
static int              _ecore_list_prepend_0(Ecore_List *list,
24
                                              Ecore_List_Node *node);
25

26
/* Remove functions */
27
static void *           _ecore_list_remove_0(Ecore_List *list);
28
static void *           _ecore_list_first_remove(Ecore_List *list);
29
static void *           _ecore_list_last_remove(Ecore_List *list);
30

31
/* Basic traversal functions */
32
static void *           _ecore_list_next(Ecore_List *list);
33
static void *           _ecore_list_last_goto(Ecore_List *list);
34
static void *           _ecore_list_first_goto(Ecore_List *list);
35
static void *           _ecore_list_goto(Ecore_List *list, const void *data);
36
static void *           _ecore_list_index_goto(Ecore_List *list, int idx);
37

38
/* Iterative functions */
39
static int              _ecore_list_for_each(Ecore_List *list,
40
                                             Ecore_For_Each function,
41
                                             void *user_data);
42
static void *           _ecore_list_find(Ecore_List *list,
43
                                         Ecore_Compare_Cb function,
44
                                         const void *user_data);
45

46
/* Sorting functions */
47
static Ecore_List_Node *_ecore_list_node_mergesort(Ecore_List_Node *first,
48
                                                   int n,
49
                                                   Ecore_Compare_Cb compare,
50
                                                   int order);
51
static Ecore_List_Node *_ecore_list_node_merge(Ecore_List_Node *first,
52
                                               Ecore_List_Node *second,
53
                                               Ecore_Compare_Cb compare,
54
                                               int order);
55
static Ecore_List_Node *_ecore_dlist_node_mergesort(Ecore_List_Node *first,
56
                                                    int n,
57
                                                    Ecore_Compare_Cb compare,
58
                                                    int order);
59
static Ecore_List_Node *_ecore_dlist_node_merge(Ecore_List_Node *first,
60
                                                Ecore_List_Node *second,
61
                                                Ecore_Compare_Cb compare,
62
                                                int order);
63

64
/* Private double linked list functions */
65
static void *_ecore_dlist_previous(Ecore_DList *list);
66
static void *_ecore_dlist_first_remove(Ecore_DList *list);
67
static void *_ecore_dlist_index_goto(Ecore_DList *list, int idx);
68

69
/**
70
   @defgroup Ecore_Data_List_Creation_Group List Creation/Destruction Functions
71

72
   Functions that create, initialize and destroy Ecore_Lists.
73
 */
74

75
/**
76
 * Create and initialize a new list.
77
 * @return  A new initialized list on success, @c NULL on failure.
78
 * @ingroup Ecore_Data_List_Creation_Group
79
 */
80
EAPI Ecore_List *
81
ecore_list_new(void)
82
{
83
   Ecore_List *list;
84

85
   list = (Ecore_List *)malloc(sizeof(Ecore_List));
86
   if (!list)
87
      return NULL;
88

89
   if (!ecore_list_init(list))
90
     {
91
        FREE(list);
92
        return NULL;
93
     }
94

95
   return list;
96
}
97

98
/**
99
 * Initialize a list to some sane starting values.
100
 * @param   list The list to initialize.
101
 * @return  @c TRUE if successful, @c FALSE if an error occurs.
102
 * @ingroup Ecore_Data_List_Creation_Group
103
 */
104
EAPI int
105
ecore_list_init(Ecore_List *list)
106
{
107
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
108

109
   memset(list, 0, sizeof(Ecore_List));
110

111
   return TRUE;
112
}
113

114
/**
115
 * Free a list and all of it's nodes.
116
 * @param   list The list to be freed.
117
 * @ingroup Ecore_Data_List_Creation_Group
118
 */
119
EAPI void
120
ecore_list_destroy(Ecore_List *list)
121
{
122
   void *data;
123

124
   CHECK_PARAM_POINTER("list", list);
125

126
   while (list->first)
127
     {
128
        data = _ecore_list_first_remove(list);
129
        if (list->free_func)
130
           list->free_func(data);
131
     }
132

133
   FREE(list);
134
}
135

136
/**
137
 * Set the function for freeing data.
138
 * @param  list      The list that will use this function when nodes are
139
 *                   destroyed.
140
 * @param  free_func The function that will free the key data.
141
 * @return @c TRUE on successful set, @c FALSE otherwise.
142
 */
143
EAPI int
144
ecore_list_free_cb_set(Ecore_List *list, Ecore_Free_Cb free_func)
145
{
146
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
147

148
   list->free_func = free_func;
149

150
   return TRUE;
151
}
152

153
/**
154
 * Checks the list for any nodes.
155
 * @param  list  The list to check for nodes
156
 * @return @c TRUE if no nodes in list, @c FALSE if the list contains nodes
157
 */
158
EAPI int
159
ecore_list_empty_is(Ecore_List *list)
160
{
161
   int ret = TRUE;
162

163
   CHECK_PARAM_POINTER_RETURN("list", list, TRUE);
164

165
   if (list->nodes)
166
      ret = FALSE;
167

168
   return ret;
169
}
170

171
/**
172
 * Returns the number of the current node.
173
 * @param  list The list to return the number of the current node.
174
 * @return The number of the current node in the list.
175
 */
176
EAPI int
177
ecore_list_index(Ecore_List *list)
178
{
179
   int ret;
180

181
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
182

183
   ret = list->index;
184

185
   return ret;
186
}
187

188
/**
189
 * Find the number of nodes in the list.
190
 * @param  list The list to find the number of nodes
191
 * @return The number of nodes in the list.
192
 */
193
EAPI int
194
ecore_list_count(Ecore_List *list)
195
{
196
   int ret = 0;
197

198
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
199

200
   ret = list->nodes;
201

202
   return ret;
203
}
204

205
/**
206
   @defgroup Ecore_Data_List_Add_Item_Group List Item Adding Functions
207

208
   Functions that are used to add nodes to an Ecore_List.
209
 */
210

211
/**
212
 * Append data to the list.
213
 * @param   list The list.
214
 * @param   data The data to append.
215
 * @return  @c FALSE if an error occurs, @c TRUE if appended successfully
216
 * @ingroup Ecore_Data_List_Add_Item_Group
217
 */
218
EAPI inline int
219
ecore_list_append(Ecore_List *list, void *data)
220
{
221
   int ret;
222
   Ecore_List_Node *node;
223

224
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
225

226
   node = ecore_list_node_new();
227
   node->data = data;
228

229
   ret = _ecore_list_append_0(list, node);
230

231
   return ret;
232
}
233

234
/* For adding items to the end of the list */
235
static int
236
_ecore_list_append_0(Ecore_List *list, Ecore_List_Node *end)
237
{
238
   if (list->last)
239
      list->last->next = end;
240

241
   list->last = end;
242

243
   if (!list->first)
244
     {
245
        list->first = end;
246
        list->index = 0;
247
        list->current = NULL;
248
     }
249

250
   if (list->index >= list->nodes)
251
      list->index++;
252

253
   list->nodes++;
254

255
   return TRUE;
256
}
257

258
/**
259
 * Prepend data to the beginning of the list.
260
 * @param  list The list.
261
 * @param  data The data to prepend.
262
 * @return @c FALSE if an error occurs, @c TRUE if prepended successfully.
263
 * @ingroup Ecore_Data_List_Add_Item_Group
264
 */
265
EAPI inline int
266
ecore_list_prepend(Ecore_List *list, void *data)
267
{
268
   int ret;
269
   Ecore_List_Node *node;
270

271
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
272

273
   node = ecore_list_node_new();
274
   node->data = data;
275

276
   ret = _ecore_list_prepend_0(list, node);
277

278
   return ret;
279
}
280

281
/* For adding items to the beginning of the list */
282
static int
283
_ecore_list_prepend_0(Ecore_List *list, Ecore_List_Node *start)
284
{
285
   /* Put it at the beginning of the list */
286
   start->next = list->first;
287

288
   list->first = start;
289

290
   /* If no last node, then the first node is the last node */
291
   if (!list->last)
292
      list->last = list->first;
293

294
   list->nodes++;
295
   list->index++;
296

297
   return TRUE;
298
}
299

300
/**
301
 * Insert data in front of the current point in the list.
302
 * @param   list The list to hold the inserted @p data.
303
 * @param   data The data to insert into @p list.
304
 * @return  @c FALSE if there is an error, @c TRUE on success
305
 * @ingroup Ecore_Data_List_Add_Item_Group
306
 */
307
EAPI inline int
308
ecore_list_insert(Ecore_List *list, void *data)
309
{
310
   int ret;
311
   Ecore_List_Node *node;
312

313
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
314

315
   node = ecore_list_node_new();
316
   node->data = data;
317

318
   ret = _ecore_list_insert(list, node);
319

320
   return ret;
321
}
322

323
/* For adding items in front of the current position in the list */
324
static int
325
_ecore_list_insert(Ecore_List *list, Ecore_List_Node *new_node)
326
{
327
   /*
328
    * If the current point is at the beginning of the list, then it's the
329
    * same as prepending it to the list.
330
    */
331
   if (list->current == list->first)
332
      return _ecore_list_prepend_0(list, new_node);
333

334
   if (!list->current)
335
     {
336
        int ret_value;
337

338
        ret_value = _ecore_list_append_0(list, new_node);
339
        list->current = list->last;
340

341
        return ret_value;
342
     }
343

344
   /* Setup the fields of the new node */
345
   new_node->next = list->current;
346

347
   /* And hook the node into the list */
348
   _ecore_list_index_goto(list, ecore_list_index(list) - 1);
349

350
   list->current->next = new_node;
351

352
   /* Now move the current item to the inserted item */
353
   list->current = new_node;
354
   list->nodes++;
355

356
   return TRUE;
357
}
358
/**
359
 * Append a list to the list.
360
 * @param   list The list.
361
 * @param   append The list to append.
362
 * @return  @c FALSE if an error occurs, @c TRUE if appended successfully
363
 * @ingroup Ecore_Data_List_Add_Item_Group
364
 */
365

366
EAPI int
367
ecore_list_append_list(Ecore_List *list, Ecore_List *append)
368
{
369
   CHECK_PARAM_POINTER_RETURN("list",   list,   FALSE);
370
   CHECK_PARAM_POINTER_RETURN("append", append, FALSE);
371

372
   if (ecore_list_empty_is(append))
373
      return TRUE;
374

375
   if (ecore_list_empty_is(list))
376
     {
377
        list->first = append->first;
378
        list->current = list->first;
379
        list->last = append->last;
380
        list->nodes = append->nodes;
381
     }
382
   else
383
     {
384
        list->last->next = append->first;
385
        list->last = append->last;
386
        list->nodes += append->nodes;
387
     }
388

389
   ecore_list_init(append);
390
   return TRUE;
391
}
392

393
/**
394
 * Prepend a list to the beginning of the list.
395
 * @param  list The list.
396
 * @param  prepend The list to prepend.
397
 * @return @c FALSE if an error occurs, @c TRUE if prepended successfully.
398
 * @ingroup Ecore_Data_List_Add_Item_Group
399
 */
400
EAPI int
401
ecore_list_prepend_list(Ecore_List *list, Ecore_List *prepend)
402
{
403
   CHECK_PARAM_POINTER_RETURN("list",    list,    FALSE);
404
   CHECK_PARAM_POINTER_RETURN("prepend", prepend, FALSE);
405

406
   if (ecore_list_empty_is(prepend))
407
      return TRUE;
408

409
   if (ecore_list_empty_is(list))
410
     {
411
        list->first = prepend->first;
412
        list->current = NULL;
413
        list->last = prepend->last;
414
        list->nodes = prepend->nodes;
415
     }
416
   else
417
     {
418
        prepend->last->next = list->first;
419
        list->first = prepend->first;
420
        list->nodes += prepend->nodes;
421
        list->index += prepend->nodes;
422
     }
423

424
   ecore_list_init(prepend);
425
   return TRUE;
426
}
427

428
/**
429
   @defgroup Ecore_Data_List_Remove_Item_Group List Item Removing Functions
430

431
   Functions that remove nodes from an Ecore_List.
432
 */
433

434
/**
435
 * Remove the current item from the list.
436
 * @param   list The list to remove the current item
437
 * @return  A pointer to the removed data on success, @c NULL on failure.
438
 * @ingroup Ecore_Data_List_Remove_Item_Group
439
 */
440
EAPI inline void *
441
ecore_list_remove(Ecore_List *list)
442
{
443
   void *ret;
444

445
   CHECK_PARAM_POINTER_RETURN("list", list, NULL);
446

447
   ret = _ecore_list_remove_0(list);
448

449
   return ret;
450
}
451

452
/* Remove the current item from the list */
453
static void *
454
_ecore_list_remove_0(Ecore_List *list)
455
{
456
   void *ret = NULL;
457
   Ecore_List_Node *old;
458

459
   if (!list)
460
      return NULL;
461

462
   if (ecore_list_empty_is(list))
463
      return NULL;
464

465
   if (!list->current)
466
      return NULL;
467

468
   if (list->current == list->first)
469
      return _ecore_list_first_remove(list);
470

471
   if (list->current == list->last)
472
      return _ecore_list_last_remove(list);
473

474
   old = list->current;
475

476
   _ecore_list_index_goto(list, list->index - 1);
477

478
   list->current->next = old->next;
479
   old->next = NULL;
480
   ret = old->data;
481
   old->data = NULL;
482

483
   _ecore_list_next(list);
484

485
   ecore_list_node_destroy(old, NULL);
486
   list->nodes--;
487

488
   return ret;
489
}
490

491
/**
492
 * Remove and free the data in lists current position.
493
 * @param   list The list to remove and free the current item.
494
 * @return  @c TRUE on success, @c FALSE on error
495
 * @ingroup Ecore_Data_List_Remove_Item_Group
496
 */
497
EAPI int
498
ecore_list_remove_destroy(Ecore_List *list)
499
{
500
   void *data;
501

502
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
503

504
   data = _ecore_list_remove_0(list);
505
   if (list->free_func)
506
      list->free_func(data);
507

508
   return TRUE;
509
}
510

511
/**
512
 * Remove the first item from the list.
513
 * @param   list The list to remove the current item
514
 * @return  Returns a pointer to the removed data on success, @c NULL on
515
 *          failure.
516
 * @ingroup Ecore_Data_List_Remove_Item_Group
517
 */
518
EAPI inline void *
519
ecore_list_first_remove(Ecore_List *list)
520
{
521
   void *ret;
522

523
   CHECK_PARAM_POINTER_RETURN("list", list, NULL);
524

525
   ret = _ecore_list_first_remove(list);
526

527
   return ret;
528
}
529

530
/* Remove the first item from the list */
531
static void *
532
_ecore_list_first_remove(Ecore_List *list)
533
{
534
   void *ret = NULL;
535
   Ecore_List_Node *old;
536

537
   if (!list)
538
      return NULL;
539

540
   if (ecore_list_empty_is(list))
541
      return NULL;
542

543
   old = list->first;
544

545
   list->first = list->first->next;
546

547
   if (list->current == old)
548
      list->current = list->first;
549
   else
550
      (list->index ? list->index-- : 0);
551

552
   if (list->last == old)
553
      list->last = list->first;
554

555
   ret = old->data;
556
   old->data = NULL;
557

558
   ecore_list_node_destroy(old, NULL);
559
   list->nodes--;
560

561
   return ret;
562
}
563

564
/**
565
 * Remove the last item from the list.
566
 * @param   list The list to remove the last node from
567
 * @return  A pointer to the removed data on success, @c NULL on failure.
568
 * @ingroup Ecore_Data_List_Remove_Item_Group
569
 */
570
EAPI inline void *
571
ecore_list_last_remove(Ecore_List *list)
572
{
573
   void *ret;
574

575
   CHECK_PARAM_POINTER_RETURN("list", list, NULL);
576

577
   ret = _ecore_list_last_remove(list);
578

579
   return ret;
580
}
581

582
/* Remove the last item from the list */
583
static void *
584
_ecore_list_last_remove(Ecore_List *list)
585
{
586
   void *ret = NULL;
587
   Ecore_List_Node *old, *prev;
588

589
   if (!list)
590
      return NULL;
591

592
   if (ecore_list_empty_is(list))
593
      return NULL;
594

595
   old = list->last;
596
   if (list->current == old)
597
      list->current = NULL;
598

599
   if (list->first == old)
600
      list->first = NULL;
601

602
   for (prev = list->first; prev && prev->next != old; prev = prev->next) ;
603
   list->last = prev;
604
   if (prev)
605
      prev->next = NULL;
606

607
   old->next = NULL;
608
   ret = old->data;
609
   old->data = NULL;
610

611
   ecore_list_node_destroy(old, NULL);
612
   list->nodes--;
613

614
   return ret;
615
}
616

617
/**
618
   @defgroup Ecore_Data_List_Traverse_Group List Traversal Functions
619

620
   Functions that can be used to traverse an Ecore_List.
621
 */
622

623
/**
624
 * Make the current item the item with the given index number.
625
 * @param   list  The list.
626
 * @param   idx The position to move the current item.
627
 * @return  A pointer to new current item on success, @c NULL on failure.
628
 * @ingroup Ecore_Data_List_Traverse_Group
629
 */
630
EAPI inline void *
631
ecore_list_index_goto(Ecore_List *list, int idx)
632
{
633
   void *ret;
634

635
   CHECK_PARAM_POINTER_RETURN("list", list, NULL);
636

637
   ret = _ecore_list_index_goto(list, idx);
638

639
   return ret;
640
}
641

642
/* This is the non-threadsafe version, use this inside internal functions that
643
 * already lock the list */
644
static void *
645
_ecore_list_index_goto(Ecore_List *list, int idx)
646
{
647
   int i;
648

649
   if (!list)
650
      return NULL;
651

652
   if (ecore_list_empty_is(list))
653
      return NULL;
654

655
   if (idx > ecore_list_count(list) || idx < 0)
656
      return NULL;
657

658
   if (idx < list->index)
659
     {
660
        _ecore_list_first_goto(list);
661
        i = 0;
662
     }
663
   else
664
      i = list->index;
665

666
   for (; i < idx && _ecore_list_next(list); i++) ;
667

668
   if (i >= list->nodes)
669
      return NULL;
670

671
   list->index = i;
672

673
   return list->current->data;
674
}
675

676
/**
677
 * Make the current item the node that contains @p data.
678
 * @param   list The list.
679
 * @param   data The data to find.
680
 * @return  A pointer to @p data on success, @c NULL on failure.
681
 * @ingroup Ecore_Data_List_Traverse_Group
682
 */
683
EAPI inline void *
684
ecore_list_goto(Ecore_List *list, const void *data)
685
{
686
   void *ret;
687

688
      CHECK_PARAM_POINTER_RETURN("list", list, NULL);
689

690
   ret = _ecore_list_goto(list, data);
691

692
   return ret;
693
}
694

695
/* Set the current position to the node containing data */
696
static void *
697
_ecore_list_goto(Ecore_List *list, const void *data)
698
{
699
   int idx;
700
   Ecore_List_Node *node;
701

702
   if (!list)
703
      return NULL;
704

705
   idx = 0;
706

707
   node = list->first;
708
   while (node && node->data)
709
     {
710
        Ecore_List_Node *next;
711

712
        if (node->data == data)
713
           break;
714

715
        next = node->next;
716

717
        node = next;
718

719
        idx++;
720
     }
721

722
   if (!node)
723
      return NULL;
724

725
   list->current = node;
726
   list->index = idx;
727

728
   return list->current->data;
729
}
730

731
/**
732
 * Make the current item the first item in the list
733
 * @param   list The list.
734
 * @return  A pointer to the first item on success, @c NULL on failure
735
 * @ingroup Ecore_Data_List_Traverse_Group
736
 */
737
EAPI inline void *
738
ecore_list_first_goto(Ecore_List *list)
739
{
740
   void *ret;
741

742
      CHECK_PARAM_POINTER_RETURN("list", list, NULL);
743

744
   ret = _ecore_list_first_goto(list);
745

746
   return ret;
747
}
748

749
/* Set the current position to the start of the list */
750
static void *
751
_ecore_list_first_goto(Ecore_List *list)
752
{
753
   if (!list || !list->first)
754
      return NULL;
755

756
   list->current = list->first;
757
   list->index = 0;
758

759
   return list->current->data;
760
}
761

762
/**
763
 * Make the current item the last item in the list.
764
 * @param   list The list.
765
 * @return  A pointer to the last item on success, @c NULL on failure.
766
 * @ingroup Ecore_Data_List_Traverse_Group
767
 */
768
EAPI inline void *
769
ecore_list_last_goto(Ecore_List *list)
770
{
771
   void *ret;
772

773
      CHECK_PARAM_POINTER_RETURN("list", list, NULL);
774

775
   ret = _ecore_list_last_goto(list);
776

777
   return ret;
778
}
779

780
/* Set the current position to the end of the list */
781
static void *
782
_ecore_list_last_goto(Ecore_List *list)
783
{
784
   if (!list || !list->last)
785
      return NULL;
786

787
   list->current = list->last;
788
   list->index = (list->nodes - 1);
789

790
   return list->current->data;
791
}
792

793
/**
794
 * Retrieve the data pointed to by the current item in @p list.
795
 * @param  list The list.
796
 * @return Returns the data at current position, can be @c NULL.
797
 */
798
EAPI inline void *
799
ecore_list_current(Ecore_List *list)
800
{
801
   void *ret;
802

803
   ret = _ecore_list_current(list);
804

805
   return ret;
806
}
807

808
/**
809
 * Retrieve the data pointed to by the first item in @p list.
810
 * @param  list The list.
811
 * @return Returns the data at current position, can be @c NULL.
812
 */
813
EAPI inline void *
814
ecore_list_first(Ecore_List *list)
815
{
816
   void *ret;
817

818
   if (!list->first)
819
      return NULL;
820

821
   ret = list->first->data;
822

823
   return ret;
824
}
825

826
/**
827
 * Retrieve the data pointed to by the last item in @p list.
828
 * @param  list The list.
829
 * @return Returns the data at current position, can be @c NULL.
830
 */
831
EAPI inline void *
832
ecore_list_last(Ecore_List *list)
833
{
834
   void *ret;
835

836
   if (!list->last)
837
      return NULL;
838

839
   ret = list->last->data;
840

841
   return ret;
842
}
843

844
/* Return the data of the current node without incrementing */
845
static void *
846
_ecore_list_current(Ecore_List *list)
847
{
848
   void *ret;
849

850
   if (!list->current)
851
      return NULL;
852

853
   ret = list->current->data;
854

855
   return ret;
856
}
857

858
/**
859
 * Retrieve the data pointed to by the current item, and make the next item
860
 * the current item.
861
 * @param   list The list to retrieve data from.
862
 * @return  The current item in the list on success, @c NULL on failure.
863
 */
864
EAPI inline void *
865
ecore_list_next(Ecore_List *list)
866
{
867
   void *data;
868

869
      CHECK_PARAM_POINTER_RETURN("list", list, NULL);
870

871
   data = _ecore_list_next(list);
872

873
   return data;
874
}
875

876
/* Return the data contained in the current node and go to the next node */
877
static void *
878
_ecore_list_next(Ecore_List *list)
879
{
880
   void *data;
881
   Ecore_List_Node *ret;
882
   Ecore_List_Node *next;
883

884
   if (!list->current)
885
      return NULL;
886

887
   ret = list->current;
888
   next = list->current->next;
889

890
   list->current = next;
891
   list->index++;
892

893
   data = ret->data;
894

895
   return data;
896
}
897

898
/**
899
 * Remove all nodes from @p list.
900
 * @param  list The list.
901
 * @return Returns @c TRUE on success, @c FALSE on error.
902
 * @note The data for each item on the list is not freed by
903
 *       @c ecore_list_clear().
904
 */
905
EAPI int
906
ecore_list_clear(Ecore_List *list)
907
{
908
      CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
909

910
   while (!ecore_list_empty_is(list))
911
      _ecore_list_first_remove(list);
912

913
   return TRUE;
914
}
915

916
/**
917
 * Execute function for each node in @p list.
918
 * @param   list     The list.
919
 * @param   function The function to pass each node from @p list to.
920
 * @return  Returns @c TRUE on success, @c FALSE on failure.
921
 * @ingroup Ecore_Data_List_Traverse_Group
922
 */
923
EAPI int
924
ecore_list_for_each(Ecore_List *list, Ecore_For_Each function, void *user_data)
925
{
926
   int ret;
927

928
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
929

930
   ret = _ecore_list_for_each(list, function, user_data);
931

932
   return ret;
933
}
934

935
/* The real meat of executing the function for each data node */
936
static int
937
_ecore_list_for_each(Ecore_List *list, Ecore_For_Each function, void *user_data)
938
{
939
   void *value;
940

941
   if (!list || !function)
942
      return FALSE;
943

944
   _ecore_list_first_goto(list);
945
   while ((value = _ecore_list_next(list)))
946
      function(value, user_data);
947

948
   return TRUE;
949
}
950

951
/**
952
 * Find data in @p list using the compare function @p func
953
 * @param list      The list.
954
 * @param function  The function to test each node of @p list with
955
 * @param user_data Data to match against (used by @p function)
956
 * @return the first matching data node, or NULL if none match
957
 */
958
EAPI void *
959
ecore_list_find(Ecore_List *list,
960
                Ecore_Compare_Cb function,
961
                const void *user_data)
962
{
963
   CHECK_PARAM_POINTER_RETURN("list", list, NULL);
964

965
   return _ecore_list_find(list, function, user_data);
966
}
967

968
/* The real meat of finding a node via a compare cb */
969
static void *
970
_ecore_list_find(Ecore_List *list,
971
                 Ecore_Compare_Cb function,
972
                 const void *user_data)
973
{
974
   void *value;
975
   if (!list || !function)
976
      return NULL;
977

978
   _ecore_list_first_goto(list);
979
   while ((value = _ecore_list_current(list)))
980
     {
981
        if (!function(value, user_data))
982
           return value;
983

984
        ecore_list_next(list);
985
     }
986

987
   return NULL;
988
}
989

990
/**
991
 * Sort data in @p list using the compare function @p compare
992
 * @param list      The list.
993
 * @param compare   The function to compare the data of @p list
994
 * @param order     The sort direction, possible values are ECORE_SORT_MIN and
995
 *                  ECORE_SORT_MAX
996
 * @return          true on success
997
 *
998
 * This is a wrapper function for mergesort and heapsort. It
999
 * tries to choose the fastest algorithm depending on the
1000
 * number of notes. Note: The sort may be unstable.
1001
 */
1002
EAPI int
1003
ecore_list_sort(Ecore_List *list, Ecore_Compare_Cb compare, char order)
1004
{
1005
   CHECK_PARAM_POINTER_RETURN("list", list, 0);
1006

1007
   if (list->nodes < 2)
1008
      return 1;
1009

1010
   if (list->nodes < ECORE_MERGESORT_LIMIT)
1011
      return ecore_list_mergesort(list, compare, order);
1012

1013
   if (!ecore_list_heapsort(list, compare, order))
1014
      return ecore_list_mergesort(list, compare, order);
1015

1016
   return 1;
1017
}
1018

1019
/**
1020
 * Sort data in @p list using the compare function @p compare
1021
 * @param list      The list.
1022
 * @param compare   The function to compare the data of @p list
1023
 * @param order     The sort direction, possible values are ECORE_SORT_MIN and
1024
 *                  ECORE_SORT_MAX
1025
 * @return          true on success
1026
 *
1027
 * Mergesort is a stable, in-place sorting algorithm
1028
 */
1029
EAPI int
1030
ecore_list_mergesort(Ecore_List *list, Ecore_Compare_Cb compare, char order)
1031
{
1032
   Ecore_List_Node *node;
1033

1034
   CHECK_PARAM_POINTER_RETURN("list", list, 0);
1035
   if (list->nodes < 2)
1036
      return 1;
1037

1038
   if (order == ECORE_SORT_MIN)
1039
      order = 1;
1040
   else
1041
      order = -1;
1042

1043
   node = _ecore_list_node_mergesort(list->first, list->nodes, compare, order);
1044
   list->first = node;
1045

1046
   /* maybe there is a better way to do that but our last node has changed */
1047
   while (node->next)
1048
      node = node->next;
1049
   list->last = node;
1050

1051
   _ecore_list_first_goto(list);
1052

1053
   return 1;
1054
}
1055

1056
/**
1057
 * Merge the @p l2 into the @p list using the compare function @p compare.
1058
 * Both lists need to be sorted else a corrupt list could be the result.
1059
 * @param list      The list.
1060
 * @param l2        The second list, this list will be empty after the merge
1061
 * @param compare   The function to compare the data of @p list and @p l2
1062
 * @param order     The sort direction, possible values are ECORE_SORT_MIN and
1063
 *                  ECORE_SORT_MAX
1064
 */
1065
EAPI void
1066
ecore_list_merge(Ecore_List *list,
1067
                 Ecore_List *l2,
1068
                 Ecore_Compare_Cb compare,
1069
                 char order)
1070
{
1071
   CHECK_PARAM_POINTER("list", list);
1072
   CHECK_PARAM_POINTER("l2",   l2);
1073

1074
   if (ecore_list_empty_is(l2))
1075
      return;
1076

1077
   if (ecore_list_empty_is(list))
1078
     {
1079
        ecore_list_append_list(list, l2);
1080
        return;
1081
     }
1082

1083
   if (order == ECORE_SORT_MIN)
1084
      order = 1;
1085
   else
1086
      order = -1;
1087

1088
   list->first = _ecore_list_node_merge(list->first, l2->first, compare, order);
1089

1090
   if ((order * compare(list->last->data, l2->last->data)) < 0)
1091
      list->last = l2->last;
1092

1093
   list->nodes += l2->nodes;
1094
   ecore_list_init(l2);
1095
}
1096

1097
/* this is the internal recrusive function for the merge sort */
1098
static Ecore_List_Node *
1099
_ecore_list_node_mergesort(Ecore_List_Node *first, int n,
1100
                           Ecore_Compare_Cb compare, int order)
1101
{
1102
   Ecore_List_Node *middle;
1103
   Ecore_List_Node *premid;
1104
   int mid;
1105
   int i;
1106

1107
   mid = n / 2;
1108

1109
   if (n < 2)
1110
      return first;
1111
   else if (n == 2)
1112
     {
1113
        if (compare(first->data, first->next->data) * order > 0)
1114
          {
1115
             /* swap the data */
1116
             void *data;
1117
             data = first->next->data;
1118
             first->next->data = first->data;
1119
             first->data = data;
1120
          }
1121

1122
        return first;
1123
     }
1124

1125
   /* first find the premiddle node*/
1126
   for (premid = first, i = 0; i < mid - 1; i++)
1127
      premid = premid->next;
1128

1129
   /* split the list */
1130
   middle = premid->next;
1131
   premid->next = NULL;
1132

1133
   /* sort the the partial lists */
1134
   first = _ecore_list_node_mergesort(first, mid, compare, order);
1135
   middle = _ecore_list_node_mergesort(middle, n - mid, compare, order);
1136

1137
   return _ecore_list_node_merge(first, middle, compare, order);
1138
}
1139

1140
/* this function is used to merge the partial sorted lists */
1141
static Ecore_List_Node *
1142
_ecore_list_node_merge(Ecore_List_Node *first, Ecore_List_Node *second,
1143
                       Ecore_Compare_Cb compare, int order)
1144
{
1145
   Ecore_List_Node *list;
1146
   Ecore_List_Node *l;
1147

1148
   /* select the first node outside the loop, because we need to keep
1149
    * a pointer to it */
1150
   if (compare(first->data, second->data) * order > 0)
1151
     {
1152
        list = l = second;
1153
        second = second->next;
1154
     }
1155
   else
1156
     {
1157
        list = l = first;
1158
        first = first->next;
1159
     }
1160

1161
   /* and now start the merging */
1162
   while (first && second)
1163
     {
1164
        if (compare(first->data, second->data) * order > 0)
1165
          {
1166
             l = l->next = second;
1167
             second = second->next;
1168
          }
1169
        else
1170
          {
1171
             l = l->next = first;
1172
             first = first->next;
1173
          }
1174
     }
1175

1176
   /* append the rest or set it to NULL */
1177
   if (first)
1178
      l->next = first;
1179
   else if (second)
1180
      l->next = second;
1181
   else
1182
      l->next = NULL;
1183

1184
   return list;
1185
}
1186

1187
/**
1188
 * Sort data in @p list using the compare function @p compare
1189
 * @param list      The list.
1190
 * @param compare   The function to compare the data of @p list
1191
 * @param order     The sort direction, possible values are ECORE_SORT_MIN and
1192
 *                  ECORE_SORT_MAX
1193
 * @return          true on success
1194
 *
1195
 * Heapsort is a unstable sorting algorithm, it needs to allocate extra memomry,
1196
 * but there for it is for a great number of nodes faster than mergesort
1197
 */
1198
EAPI int
1199
ecore_list_heapsort(Ecore_List *list, Ecore_Compare_Cb compare, char order)
1200
{
1201
   Ecore_Sheap *heap;
1202
   Ecore_List_Node *node;
1203
   void *data;
1204

1205
   CHECK_PARAM_POINTER_RETURN("list", list, 0);
1206
   /*
1207
    * Push the data into a heap.
1208
    */
1209
   heap = ecore_sheap_new(compare, list->nodes);
1210
   if (!heap)
1211
      return 0;
1212

1213
   ecore_sheap_order_set(heap, order);
1214
   _ecore_list_first_goto(list);
1215
   while ((data = _ecore_list_next(list)))
1216
     {
1217
        ecore_sheap_insert(heap, data);
1218
     }
1219

1220
   /*
1221
    * Extract in sorted order.
1222
    */
1223
   node = list->first;
1224
   while (node)
1225
     {
1226
        node->data = ecore_sheap_extract(heap);
1227
        node = node->next;
1228
     }
1229

1230
   ecore_sheap_destroy(heap);
1231

1232
   _ecore_list_first_goto(list);
1233
   return 1;
1234
}
1235

1236
/* Initialize a node to starting values */
1237
EAPI int
1238
ecore_list_node_init(Ecore_List_Node *node)
1239
{
1240
   CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
1241

1242
   node->next = NULL;
1243
   node->data = NULL;
1244

1245
   return TRUE;
1246
}
1247

1248
/**
1249
   @defgroup Ecore_Data_List_Node_Group List Node Functions
1250

1251
   Functions that are used in the creation, maintenance and destruction of
1252
   Ecore_List nodes.
1253
 */
1254

1255
/**
1256
 * Allocates and initializes a new list node.
1257
 * @return  A new Ecore_List_Node on success, @c NULL otherwise.
1258
 * @ingroup Ecore_Data_List_Node_Group
1259
 */
1260
EAPI Ecore_List_Node *
1261
ecore_list_node_new()
1262
{
1263
   Ecore_List_Node *new_node;
1264

1265
   new_node = malloc(sizeof(Ecore_List_Node));
1266

1267
   if (!ecore_list_node_init(new_node))
1268
     {
1269
        FREE(new_node);
1270
        return NULL;
1271
     }
1272

1273
   return new_node;
1274
}
1275

1276
/**
1277
 * Calls the function to free the data and the node.
1278
 * @param   node      Node to destroy.
1279
 * @param   free_func Function to call if @p node points to data to free.
1280
 * @return  @c TRUE.
1281
 * @ingroup Ecore_Data_List_Node_Group
1282
 */
1283
EAPI int
1284
ecore_list_node_destroy(Ecore_List_Node *node, Ecore_Free_Cb free_func)
1285
{
1286
   CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
1287

1288
   if (free_func && node->data)
1289
      free_func(node->data);
1290

1291
   FREE(node);
1292

1293
   return TRUE;
1294
}
1295

1296
/**
1297
 * @defgroup Ecore_Data_DList_Creation_Group Doubly Linked List Creation/Destruction Functions
1298
 *
1299
 * Functions used to create, initialize and destroy @c Ecore_DLists.
1300
 */
1301

1302
/**
1303
 * Creates and initialises a new doubly linked list.
1304
 * @return  A new initialised doubly linked list on success, @c NULL
1305
 *          on failure.
1306
 * @ingroup Ecore_Data_DList_Creation_Group
1307
 */
1308
EAPI Ecore_DList *
1309
ecore_dlist_new()
1310
{
1311
   Ecore_DList *list = NULL;
1312

1313
   list = (Ecore_DList *)malloc(sizeof(Ecore_DList));
1314
   if (!list)
1315
      return NULL;
1316

1317
   if (!ecore_dlist_init(list))
1318
     {
1319
        IF_FREE(list);
1320
        return NULL;
1321
     }
1322

1323
   return list;
1324
}
1325

1326
/**
1327
 * Initialises a list to some sane starting values.
1328
 * @param   list The doubly linked list to initialise.
1329
 * @return  @c TRUE if successful, @c FALSE if an error occurs.
1330
 * @ingroup Ecore_Data_DList_Creation_Group
1331
 */
1332
EAPI int
1333
ecore_dlist_init(Ecore_DList *list)
1334
{
1335
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1336

1337
   memset(list, 0, sizeof(Ecore_DList));
1338

1339
   return TRUE;
1340
}
1341

1342
/**
1343
 * Frees a doubly linked list and all of its nodes.
1344
 * @param   list The doubly linked list to be freed.
1345
 * @ingroup Ecore_Data_DList_Creation_Group
1346
 */
1347
EAPI void
1348
ecore_dlist_destroy(Ecore_DList *list)
1349
{
1350
   void *data;
1351
   CHECK_PARAM_POINTER("list", list);
1352

1353
   while (list->first)
1354
     {
1355
        data = _ecore_dlist_first_remove(list);
1356
        if (list->free_func)
1357
           list->free_func(data);
1358
     }
1359

1360
   FREE(list);
1361
}
1362

1363
/**
1364
 * Sets the function used for freeing data stored in a doubly linked list.
1365
 * @param   list      The doubly linked list that will use this function when
1366
 *                    nodes are destroyed.
1367
 * @param   free_func The function that will free the key data
1368
 * @return  @c TRUE on success, @c FALSE on failure.
1369
 * @ingroup Ecore_Data_DList_Creation_Group
1370
 */
1371
EAPI int
1372
ecore_dlist_free_cb_set(Ecore_DList *list, Ecore_Free_Cb free_func)
1373
{
1374
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1375

1376
   return ecore_list_free_cb_set(ECORE_LIST(list), free_func);
1377
}
1378

1379
/**
1380
 * Returns whether there is anything in the given doubly linked list.
1381
 * @param  list The given doubly linked list.
1382
 * @return @c TRUE if there are nodes, @c FALSE otherwise.
1383
 */
1384
EAPI int
1385
ecore_dlist_empty_is(Ecore_DList *list)
1386
{
1387
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1388

1389
   return ecore_list_empty_is(ECORE_LIST(list));
1390
}
1391

1392
/**
1393
 * Retrieves the index of the current node of the given doubly linked list.
1394
 * @param  list The given doubly linked list.
1395
 * @return The index of the current node.
1396
 */
1397
EAPI inline int
1398
ecore_dlist_index(Ecore_DList *list)
1399
{
1400
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1401

1402
   return ecore_list_index(ECORE_LIST(list));
1403
}
1404

1405
/**
1406
 * @defgroup Ecore_Data_DList_Add_Item_Group Doubly Linked List Adding Functions
1407
 *
1408
 * Functions that are used to add nodes to an Ecore_DList.
1409
 */
1410

1411
/**
1412
 * Appends data to the given doubly linked list.
1413
 * @param   list The given doubly linked list.
1414
 * @param   data The data to append.
1415
 * @return  @c TRUE if the data is successfully appended, @c FALSE otherwise.
1416
 * @ingroup Ecore_Data_DList_Add_Item_Group
1417
 */
1418
EAPI int
1419
ecore_dlist_append(Ecore_DList *list, void *data)
1420
{
1421
   int ret;
1422
   Ecore_DList_Node *prev;
1423
   Ecore_DList_Node *node;
1424

1425
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1426

1427
   node = ecore_dlist_node_new();
1428
   ECORE_LIST_NODE(node)->data = data;
1429

1430
   prev = ECORE_DLIST_NODE(ECORE_LIST(list)->last);
1431
   ret = _ecore_list_append_0(ECORE_LIST(list), ECORE_LIST_NODE(node));
1432
   if (ret)
1433
      node->previous = prev;
1434

1435
   return ret;
1436
}
1437

1438
/**
1439
 * Adds data to the very beginning of the given doubly linked list.
1440
 * @param   list The given doubly linked list.
1441
 * @param   data The data to prepend.
1442
 * @return  @c TRUE if the data is successfully prepended, @c FALSE otherwise.
1443
 * @ingroup Ecore_Data_DList_Add_Item_Group
1444
 */
1445
EAPI int
1446
ecore_dlist_prepend(Ecore_DList *list, void *data)
1447
{
1448
   int ret;
1449
   Ecore_DList_Node *prev;
1450
   Ecore_DList_Node *node;
1451

1452
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1453

1454
   node = ecore_dlist_node_new();
1455
   ECORE_LIST_NODE(node)->data = data;
1456

1457
   prev = ECORE_DLIST_NODE(ECORE_LIST(list)->first);
1458
   ret = _ecore_list_prepend_0(ECORE_LIST(list), ECORE_LIST_NODE(node));
1459
   if (ret && prev)
1460
      prev->previous = node;
1461

1462
   return ret;
1463
}
1464

1465
/**
1466
 * Inserts data at the current point in the given doubly linked list.
1467
 * @param   list The given doubly linked list.
1468
 * @param   data The data to be inserted.
1469
 * @return  @c TRUE on success, @c FALSE otherwise.
1470
 * @ingroup Ecore_Data_DList_Add_Item_Group
1471
 */
1472
EAPI int
1473
ecore_dlist_insert(Ecore_DList *list, void *data)
1474
{
1475
   int ret = TRUE;
1476
   Ecore_DList_Node *prev;
1477
   Ecore_DList_Node *node;
1478

1479
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1480

1481
   /*
1482
    * Identify and shortcut the end cases.
1483
    */
1484
   if (!ECORE_LIST(list)->current)
1485
      return ecore_dlist_append(list, data);
1486

1487
   if (ECORE_LIST(list)->current == ECORE_LIST(list)->first)
1488
      return ecore_dlist_prepend(list, data);
1489

1490
   node = ecore_dlist_node_new();
1491
   ECORE_LIST_NODE(node)->data = data;
1492

1493
   /* Setup the fields of the new node */
1494
   ECORE_LIST_NODE(node)->next = ECORE_LIST(list)->current;
1495

1496
   /* And hook the node into the list */
1497
   prev = ECORE_DLIST_NODE(ECORE_LIST(list)->current)->previous;
1498
   ECORE_LIST_NODE(prev)->next = ECORE_LIST_NODE(node);
1499
   ECORE_DLIST_NODE(ECORE_LIST(list)->current)->previous = node;
1500
   node->previous = prev;
1501

1502
   /* Now move the current item to the inserted item */
1503
   ECORE_LIST(list)->current = ECORE_LIST_NODE(node);
1504
   ECORE_LIST(list)->nodes++;
1505

1506
   return ret;
1507
}
1508

1509
/**
1510
 * Appends a list to the given doubly linked list.
1511
 * @param   list The given doubly linked list.
1512
 * @param   append The list to append.
1513
 * @return  @c TRUE if the data is successfully appended, @c FALSE otherwise.
1514
 * @ingroup Ecore_Data_DList_Add_Item_Group
1515
 */
1516
EAPI int
1517
ecore_dlist_append_list(Ecore_DList *list, Ecore_DList *append)
1518
{
1519
   CHECK_PARAM_POINTER_RETURN("list",   list,   FALSE);
1520
   CHECK_PARAM_POINTER_RETURN("append", append, FALSE);
1521

1522
   if (ecore_dlist_empty_is(append))
1523
      return TRUE;
1524

1525
   if (ecore_dlist_empty_is(list))
1526
     {
1527
        list->first = append->first;
1528
        list->current = NULL;
1529
        list->last = append->last;
1530
        list->nodes = append->nodes;
1531
     }
1532
   else
1533
     {
1534
        list->last->next = append->first;
1535
        ECORE_DLIST_NODE(append->first)->previous = ECORE_DLIST_NODE(list->last);
1536
        list->last = append->last;
1537
        list->nodes += append->nodes;
1538
     }
1539

1540
   ecore_dlist_init(append);
1541
   return TRUE;
1542
}
1543

1544
/**
1545
 * Adds a list to the very beginning of the given doubly linked list.
1546
 * @param   list The given doubly linked list.
1547
 * @param   prepend The list to prepend.
1548
 * @return  @c TRUE if the data is successfully prepended, @c FALSE otherwise.
1549
 * @ingroup Ecore_Data_DList_Add_Item_Group
1550
 */
1551
EAPI int
1552
ecore_dlist_prepend_list(Ecore_DList *list, Ecore_DList *prepend)
1553
{
1554
   CHECK_PARAM_POINTER_RETURN("list",    list,    FALSE);
1555
   CHECK_PARAM_POINTER_RETURN("prepend", prepend, FALSE);
1556

1557
   if (ecore_dlist_empty_is(prepend))
1558
      return TRUE;
1559

1560
   if (ecore_dlist_empty_is(list))
1561
     {
1562
        list->first = prepend->first;
1563
        list->current = NULL;
1564
        list->last = prepend->last;
1565
        list->nodes = prepend->nodes;
1566
     }
1567
   else
1568
     {
1569
        prepend->last->next = list->first;
1570
        ECORE_DLIST_NODE(list->first)->previous = ECORE_DLIST_NODE(
1571
              prepend->last);
1572
        list->first = prepend->first;
1573
        list->nodes += prepend->nodes;
1574
        list->index += prepend->nodes;
1575
     }
1576

1577
   ecore_dlist_init(prepend);
1578
   return TRUE;
1579
}
1580

1581
/**
1582
 * @defgroup Ecore_Data_DList_Remove_Item_Group Doubly Linked List Removing Functions
1583
 *
1584
 * Functions that remove nodes from an @c Ecore_DList.
1585
 */
1586

1587
/**
1588
 * Removes the current item from the given doubly linked list.
1589
 * @param   list The given doubly linked list.
1590
 * @return  A pointer to the removed data on success, @c NULL otherwise.
1591
 * @ingroup Ecore_Data_DList_Remove_Item_Group
1592
 */
1593
EAPI void *
1594
ecore_dlist_remove(Ecore_DList *list)
1595
{
1596
   void *ret;
1597
   Ecore_List *l2 = ECORE_LIST(list);
1598
   Ecore_DList_Node *node;
1599

1600
   CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1601

1602
   if (l2->current)
1603
     {
1604
        node = ECORE_DLIST_NODE(list->current->next);
1605
        if (node)
1606
           node->previous = ECORE_DLIST_NODE(l2->current)->previous;
1607
     }
1608

1609
   ret = _ecore_list_remove_0(list);
1610

1611
   return ret;
1612
}
1613

1614
/**
1615
 * Removes the first item from the given doubly linked list.
1616
 * @param   list The given doubly linked list.
1617
 * @return  A pointer to the removed data on success, @c NULL on failure.
1618
 * @ingroup Ecore_Data_DList_Remove_Item_Group
1619
 */
1620
EAPI void *
1621
ecore_dlist_first_remove(Ecore_DList *list)
1622
{
1623
   void *ret;
1624

1625
   CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1626

1627
   ret = _ecore_dlist_first_remove(list);
1628

1629
   return ret;
1630
}
1631

1632
/**
1633
 * Removes and frees the data at the current position in the given doubly
1634
 * linked list.
1635
 * @param   list The given doubly linked list.
1636
 * @return  @c TRUE on success, @c FALSE otherwise.
1637
 * @ingroup Ecore_Data_DList_Remove_Item_Group
1638
 */
1639
EAPI int
1640
ecore_dlist_remove_destroy(Ecore_DList *list)
1641
{
1642
   void *data;
1643

1644
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1645

1646
   data = ecore_dlist_remove(list);
1647
   if (!data)
1648
      return FALSE;
1649

1650
   if (list->free_func)
1651
      list->free_func(data);
1652

1653
   return TRUE;
1654
}
1655

1656
static void *
1657
_ecore_dlist_first_remove(Ecore_DList *list)
1658
{
1659
   void *ret;
1660

1661
   if (!list)
1662
      return NULL;
1663

1664
   ret = _ecore_list_first_remove(list);
1665
   if (ret && ECORE_LIST(list)->first)
1666
      ECORE_DLIST_NODE(ECORE_LIST(list)->first)->previous = NULL;
1667

1668
   return ret;
1669
}
1670

1671
/**
1672
 * Removes the last item from the given doubly linked list.
1673
 * @param   list The given doubly linked list.
1674
 * @return  A pointer to the removed data on success, @c NULL otherwise.
1675
 * @ingroup Ecore_Data_DList_Remove_Item_Group
1676
 */
1677
EAPI void *
1678
ecore_dlist_last_remove(Ecore_DList *list)
1679
{
1680
   void *ret;
1681
   Ecore_List_Node *node;
1682

1683
   CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1684

1685
   if (ecore_list_empty_is(list))
1686
      return NULL;
1687

1688
   node = list->last;
1689
   list->last = ECORE_LIST_NODE(ECORE_DLIST_NODE(node)->previous);
1690
   if (list->last)
1691
      list->last->next = NULL;
1692

1693
   if (list->first == node)
1694
      list->first = NULL;
1695

1696
   if (list->current == node)
1697
      list->current = NULL;
1698

1699
   ret = node->data;
1700
   ecore_list_node_destroy(node, NULL);
1701

1702
   list->nodes--;
1703
   if (list->index >= list->nodes)
1704
      list->index--;
1705

1706
   return ret;
1707
}
1708

1709
/**
1710
 * Moves the current item to the index number in the given doubly linked list.
1711
 * @param  list  The given doubly linked list.
1712
 * @param  idx The position to move the current item
1713
 * @return The node at specified index on success, @c NULL on error.
1714
 */
1715
EAPI void *
1716
ecore_dlist_index_goto(Ecore_DList *list, int idx)
1717
{
1718
   void *ret;
1719

1720
   CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1721

1722
   ret = _ecore_dlist_index_goto(list, idx);
1723

1724
   return ret;
1725
}
1726

1727
/* This is the non-threadsafe version, use this inside internal functions that
1728
 * already lock the list */
1729
static void *
1730
_ecore_dlist_index_goto(Ecore_DList *list, int idx)
1731
{
1732
   int i, increment;
1733

1734
   if (!list)
1735
      return NULL;
1736

1737
   if (ecore_list_empty_is(ECORE_LIST(list)))
1738
      return NULL;
1739

1740
   if (idx > ecore_list_count(ECORE_LIST(list)) || idx < 0)
1741
      return NULL;
1742

1743
   if (ECORE_LIST(list)->index >= ECORE_LIST(list)->nodes)
1744
      _ecore_list_last_goto(ECORE_LIST(list));
1745

1746
   if (idx < ECORE_LIST(list)->index)
1747
      increment = -1;
1748
   else
1749
      increment = 1;
1750

1751
   for (i = ECORE_LIST(list)->index; i != idx; i += increment)
1752
     {
1753
        if (increment > 0)
1754
           _ecore_list_next(list);
1755
        else
1756
           _ecore_dlist_previous(list);
1757
     }
1758

1759
   return _ecore_list_current(list);
1760
}
1761

1762
/**
1763
 * @brief Move the current item to the node that contains data
1764
 * @param list: the list to move the current item in
1765
 * @param data: the data to find and set the current item to
1766
 *
1767
 * @return Returns specified data on success, NULL on error
1768
 */
1769
EAPI void *
1770
ecore_dlist_goto(Ecore_DList *list, void *data)
1771
{
1772
   void *ret;
1773

1774
   CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1775

1776
   ret = _ecore_list_goto(ECORE_LIST(list), data);
1777

1778
   return ret;
1779
}
1780

1781
/**
1782
 * @brief Move the current pointer to the first item in the list
1783
 * @param list: the list to change the current to the first item
1784
 *
1785
 * @return Returns a pointer to the first item on success, NULL on failure.
1786
 */
1787
EAPI void *
1788
ecore_dlist_first_goto(Ecore_DList *list)
1789
{
1790
   void *ret;
1791

1792
   CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1793

1794
   ret = _ecore_list_first_goto(list);
1795

1796
   return ret;
1797
}
1798

1799
/**
1800
 * @brief Move the pointer to the current item to the last item
1801
 * @param list: the list to move the current item pointer to the last
1802
 * @return Returns a pointer to the last item in the list , NULL if empty.
1803
 */
1804
EAPI void *
1805
ecore_dlist_last_goto(Ecore_DList *list)
1806
{
1807
   void *ret;
1808

1809
   CHECK_PARAM_POINTER_RETURN("list", list, NULL);
1810

1811
   ret = _ecore_list_last_goto(ECORE_LIST(list));
1812

1813
   return ret;
1814
}
1815

1816
/**
1817
 * @brief Return the data in the current list item
1818
 * @param list: the list to the return the current data
1819
 * @return Returns value of the current data item, NULL if no current item
1820
 */
1821
EAPI void *
1822
ecore_dlist_current(Ecore_DList *list)
1823
{
1824
   void *ret;
1825

1826
   ret = _ecore_list_current(ECORE_LIST(list));
1827

1828
   return ret;
1829
}
1830

1831
/**
1832
 * @brief Move to the next item in the list and return current item
1833
 * @param list: the list to move to the next item in.
1834
 * @return Returns data in the current list node, or NULL on error
1835
 */
1836
EAPI void *
1837
ecore_dlist_next(Ecore_DList *list)
1838
{
1839
   void *data;
1840

1841
   data = _ecore_list_next(list);
1842

1843
   return data;
1844
}
1845

1846
/**
1847
 * @brief Move to the previous item and return current item
1848
 * @param list: the list to move to the previous item in.
1849
 * @return Returns data in the current list node, or NULL on error
1850
 */
1851
EAPI void *
1852
ecore_dlist_previous(Ecore_DList *list)
1853
{
1854
   void *data;
1855

1856
   data = _ecore_dlist_previous(list);
1857

1858
   return data;
1859
}
1860

1861
static void *
1862
_ecore_dlist_previous(Ecore_DList *list)
1863
{
1864
   void *data = NULL;
1865

1866
   if (!list)
1867
      return NULL;
1868

1869
   if (ECORE_LIST(list)->current)
1870
     {
1871
        data = ECORE_LIST(list)->current->data;
1872
                                     ECORE_LIST(list)->
1873
        current = ECORE_LIST_NODE(ECORE_DLIST_NODE(
1874
                                     ECORE_LIST(list)->
1875
                                     current)->previous);
1876
                                     ECORE_LIST(list)->index
1877
        --;
1878
     }
1879
   else
1880
      _ecore_list_last_goto(
1881
         ECORE_LIST(list));
1882

1883
   return data;
1884
}
1885

1886
/**
1887
 * @brief Remove all nodes from the list.
1888
 * @param list: the list to remove all nodes from
1889
 *
1890
 * @return Returns TRUE on success, FALSE on errors
1891
 */
1892
EAPI int
1893
ecore_dlist_clear(Ecore_DList *list)
1894
{
1895
   CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
1896

1897
   ecore_list_clear(ECORE_LIST(list));
1898

1899
   return TRUE;
1900
}
1901

1902
/**
1903
 * Sort data in @p list using the compare function @p compare
1904
 * @param list      The list.
1905
 * @param compare   The function to compare the data of @p list
1906
 * @param order     The sort direction, possible values are ECORE_SORT_MIN and
1907
 *                  ECORE_SORT_MAX
1908
 * @return          true on success
1909
 *
1910
 * This is a wrapper function for mergesort and heapsort. It
1911
 * tries to choose the fastest algorithm depending on the
1912
 * number of notes. Note: The sort may be unstable.
1913
 */
1914
EAPI int
1915
ecore_dlist_sort(Ecore_List *list, Ecore_Compare_Cb compare, char order)
1916
{
1917
   CHECK_PARAM_POINTER_RETURN("list", list, 0);
1918

1919
   if (list->nodes < 2)
1920
      return 1;
1921

1922
   if (list->nodes < ECORE_MERGESORT_LIMIT)
1923
      return ecore_dlist_mergesort(list, compare, order);
1924

1925
   if (!ecore_dlist_heapsort(list, compare, order))
1926
      return ecore_dlist_mergesort(list, compare, order);
1927

1928
   return 1;
1929
}
1930

1931
/**
1932
 * Sort data in @p list using the compare function @p compare
1933
 * @param list      The list.
1934
 * @param compare   The function to compare the data of @p list
1935
 * @param order     The sort direction, possible values are ECORE_SORT_MIN and
1936
 *                  ECORE_SORT_MAX
1937
 * @return          true on success
1938
 *
1939
 * Mergesort is a stable, in-place sorting algorithm
1940
 */
1941
EAPI int
1942
ecore_dlist_mergesort(Ecore_DList *list, Ecore_Compare_Cb compare, char order)
1943
{
1944
   Ecore_List_Node *node;
1945

1946
   CHECK_PARAM_POINTER_RETURN("list", list, 0);
1947
   if (list->nodes < 2)
1948
      return 1;
1949

1950
   if (order == ECORE_SORT_MIN)
1951
      order = 1;
1952
   else
1953
      order = -1;
1954

1955
   node = _ecore_dlist_node_mergesort(list->first, list->nodes, compare, order);
1956
   list->first = node;
1957

1958
   /* maybe there is a better way to do that but our last node has changed */
1959
   while (node->next)
1960
      node = node->next;
1961
   list->last = node;
1962

1963
   _ecore_list_first_goto(list);
1964

1965
   return 1;
1966
}
1967

1968
/**
1969
 * Merge the @p l2 into the @p list using the compare function @p compare.
1970
 * Both lists need to be sorted else a corrupt list could be the result.
1971
 * @param list      The list.
1972
 * @param l2        The second list, this list will be empty after the merge
1973
 * @param compare   The function to compare the data of @p list and @p l2
1974
 * @param order     The sort direction, possible values are ECORE_SORT_MIN and
1975
 *                  ECORE_SORT_MAX
1976
 */
1977
EAPI void
1978
ecore_dlist_merge(Ecore_DList *list,
1979
                  Ecore_DList *l2,
1980
                  Ecore_Compare_Cb compare,
1981
                  char order)
1982
{
1983
   CHECK_PARAM_POINTER("list", list);
1984
   CHECK_PARAM_POINTER("l2",   l2);
1985

1986
   if (ecore_dlist_empty_is(l2))
1987
      return;
1988

1989
   if (ecore_dlist_empty_is(list))
1990
     {
1991
        ecore_dlist_append_list(list, l2);
1992
        return;
1993
     }
1994

1995
   if (order == ECORE_SORT_MIN)
1996
      order = 1;
1997
   else
1998
      order = -1;
1999

2000
   list->first = _ecore_dlist_node_merge(list->first, l2->first, compare, order);
2001

2002
   if ((order * compare(list->last->data, l2->last->data)) < 0)
2003
      list->last = l2->last;
2004

2005
   list->nodes += l2->nodes;
2006
   ecore_dlist_init(l2);
2007
}
2008

2009
/* this is the internal recrusive function for the merge sort */
2010
static Ecore_List_Node *
2011
_ecore_dlist_node_mergesort(Ecore_List_Node *first, int n,
2012
                            Ecore_Compare_Cb compare, int order)
2013
{
2014
   Ecore_List_Node *middle;
2015
   Ecore_List_Node *premid;
2016
   int mid;
2017
   int i;
2018

2019
   mid = n / 2;
2020

2021
   if (n < 2)
2022
      return first;
2023
   else if (n == 2)
2024
     {
2025
        if (compare(first->data, first->next->data) * order > 0)
2026
          {
2027
             /* swap the data */
2028
             void *data;
2029
             data = first->next->data;
2030
             first->next->data = first->data;
2031
             first->data = data;
2032
          }
2033

2034
        return first;
2035
     }
2036

2037
   /* first find the premiddle node*/
2038
   for (premid = first, i = 0; i < mid - 1; i++)
2039
      premid = premid->next;
2040

2041
   /* split the list */
2042
   middle = premid->next;
2043
   premid->next = NULL;
2044
             ECORE_DLIST_NODE(middle)->previous = NULL;
2045

2046
   /* sort the the partial lists */
2047
   first = _ecore_dlist_node_mergesort(first, mid, compare, order);
2048
   middle = _ecore_dlist_node_mergesort(middle, n - mid, compare, order);
2049

2050
   return _ecore_dlist_node_merge(first, middle, compare, order);
2051
}
2052

2053
/* this function is used to merge the partial sorted lists */
2054
static Ecore_List_Node *
2055
_ecore_dlist_node_merge(Ecore_List_Node *first, Ecore_List_Node *second,
2056
                        Ecore_Compare_Cb compare, int order)
2057
{
2058
   Ecore_List_Node *list;
2059
   Ecore_List_Node *l;
2060

2061
   /* select the first node outside the loop, because we need to keep
2062
    * a pointer to it */
2063
   if (compare(first->data, second->data) * order > 0)
2064
     {
2065
        list = l = second;
2066
        second = second->next;
2067
     }
2068
   else
2069
     {
2070
        list = l = first;
2071
        first = first->next;
2072
     }
2073

2074
   /* and now start the merging */
2075
   while (first && second)
2076
     {
2077
        if (compare(first->data, second->data) * order > 0)
2078
          {
2079
             ECORE_DLIST_NODE(second)->previous = ECORE_DLIST_NODE(l);
2080
             l = l->next = second;
2081
             second = second->next;
2082
          }
2083
        else
2084
          {
2085
             ECORE_DLIST_NODE(first)->previous = ECORE_DLIST_NODE(l);
2086
             l = l->next = first;
2087
             first = first->next;
2088
          }
2089
     }
2090

2091
   /* append the rest or set it to NULL */
2092
   if (first)
2093
     {
2094
             ECORE_DLIST_NODE(first)->previous = ECORE_DLIST_NODE(l);
2095
        l->next = first;
2096
     }
2097
   else if (second)
2098
     {
2099
             ECORE_DLIST_NODE(second)->previous = ECORE_DLIST_NODE(l);
2100
        l->next = second;
2101
     }
2102
   else
2103
      l->next = NULL;
2104

2105
   return list;
2106
}
2107

2108
/*
2109
 * @brief Initialize a node to sane starting values
2110
 * @param node: the node to initialize
2111
 * @return Returns TRUE on success, FALSE on errors
2112
 */
2113
EAPI int
2114
ecore_dlist_node_init(Ecore_DList_Node *node)
2115
{
2116
   int ret;
2117

2118
   CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
2119

2120
   ret = ecore_list_node_init(ECORE_LIST_NODE(node));
2121
   if (ret)
2122
      node->previous = NULL;
2123

2124
   return ret;
2125
}
2126

2127
/*
2128
 * @brief Allocate and initialize a new list node
2129
 * @return Returns NULL on error, new list node on success
2130
 */
2131
EAPI Ecore_DList_Node *
2132
ecore_dlist_node_new()
2133
{
2134
   Ecore_DList_Node *new_node;
2135

2136
   new_node = malloc(sizeof(Ecore_DList_Node));
2137

2138
   if (!new_node)
2139
      return NULL;
2140

2141
   if (!ecore_dlist_node_init(new_node))
2142
     {
2143
        FREE(new_node);
2144
        return NULL;
2145
     }
2146

2147
   return new_node;
2148
}
2149

2150
/*
2151
 * @brief Call the data's free callback function, then free the node
2152
 * @param node: the node to be freed
2153
 * @param free_func: the callback function to execute on the data
2154
 * @return Returns TRUE on success, FALSE on error
2155
 */
2156
EAPI int
2157
ecore_dlist_node_destroy(Ecore_DList_Node *node, Ecore_Free_Cb free_func)
2158
{
2159
   CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
2160

2161
   return ecore_list_node_destroy(ECORE_LIST_NODE(node), free_func);
2162
}
2163