diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/eina/src/tests/ecore_list.c | 2162 |
1 files changed, 2162 insertions, 0 deletions
diff --git a/libraries/eina/src/tests/ecore_list.c b/libraries/eina/src/tests/ecore_list.c new file mode 100644 index 0000000..7da4417 --- /dev/null +++ b/libraries/eina/src/tests/ecore_list.c | |||
@@ -0,0 +1,2162 @@ | |||
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 | } | ||