summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorVincent Torri <vincent.torri@gmail.com>2011-01-16 17:55:41 +0000
committerVincent Torri <vincent.torri@gmail.com>2011-01-16 17:55:41 +0000
commitf057ba0ded3b5418f983ed60f6b19b5753c698e7 (patch)
tree3e224f634aed27e298b2d5135e6aff659662d27c
parent9a3c897c8ee9a24a8e517c6c6f1f38f109c6722e (diff)
put again eina tests in the source tree
SVN revision: 56193
-rw-r--r--Makefile.am66
-rw-r--r--configure.ac22
-rw-r--r--src/Makefile.am16
-rw-r--r--src/tests/Ecore_Data.h557
-rw-r--r--src/tests/Evas_Data.h195
-rw-r--r--src/tests/Makefile.am120
-rw-r--r--src/tests/ecore_hash.c949
-rw-r--r--src/tests/ecore_list.c2162
-rw-r--r--src/tests/ecore_sheap.c467
-rw-r--r--src/tests/ecore_strings.c160
-rw-r--r--src/tests/eina_bench.c105
-rw-r--r--src/tests/eina_bench.h36
-rw-r--r--src/tests/eina_bench_array.c699
-rw-r--r--src/tests/eina_bench_convert.c183
-rw-r--r--src/tests/eina_bench_hash.c426
-rw-r--r--src/tests/eina_bench_mempool.c188
-rw-r--r--src/tests/eina_bench_quad.c318
-rw-r--r--src/tests/eina_bench_rectangle_pool.c76
-rw-r--r--src/tests/eina_bench_sort.c222
-rw-r--r--src/tests/eina_bench_stringshare.c177
-rw-r--r--src/tests/eina_bench_stringshare_e17.c118
-rw-r--r--src/tests/eina_suite.c174
-rw-r--r--src/tests/eina_suite.h55
-rw-r--r--src/tests/eina_test_accessor.c243
-rw-r--r--src/tests/eina_test_array.c191
-rw-r--r--src/tests/eina_test_benchmark.c76
-rw-r--r--src/tests/eina_test_binshare.c199
-rw-r--r--src/tests/eina_test_convert.c165
-rw-r--r--src/tests/eina_test_counter.c108
-rw-r--r--src/tests/eina_test_error.c59
-rw-r--r--src/tests/eina_test_file.c88
-rw-r--r--src/tests/eina_test_fp.c93
-rw-r--r--src/tests/eina_test_hash.c206
-rw-r--r--src/tests/eina_test_inlist.c142
-rw-r--r--src/tests/eina_test_iterator.c465
-rw-r--r--src/tests/eina_test_lalloc.c89
-rw-r--r--src/tests/eina_test_list.c347
-rw-r--r--src/tests/eina_test_log.c235
-rw-r--r--src/tests/eina_test_magic.c96
-rw-r--r--src/tests/eina_test_main.c62
-rw-r--r--src/tests/eina_test_matrixsparse.c489
-rw-r--r--src/tests/eina_test_mempool.c187
-rw-r--r--src/tests/eina_test_module.c70
-rw-r--r--src/tests/eina_test_module_dummy.c22
-rw-r--r--src/tests/eina_test_quadtree.c195
-rw-r--r--src/tests/eina_test_rbtree.c452
-rw-r--r--src/tests/eina_test_rectangle.c115
-rw-r--r--src/tests/eina_test_sched.c85
-rw-r--r--src/tests/eina_test_str.c181
-rw-r--r--src/tests/eina_test_strbuf.c409
-rw-r--r--src/tests/eina_test_stringshare.c201
-rw-r--r--src/tests/eina_test_tiler.c184
-rw-r--r--src/tests/eina_test_ustr.c242
-rw-r--r--src/tests/eina_test_ustringshare.c119
-rw-r--r--src/tests/evas_hash.c536
-rw-r--r--src/tests/evas_list.c1093
-rw-r--r--src/tests/evas_mempool.c200
-rw-r--r--src/tests/evas_mempool.h21
-rw-r--r--src/tests/evas_object_list.c183
-rw-r--r--src/tests/evas_stringshare.c275
-rw-r--r--src/tests/strlog46999
61 files changed, 62611 insertions, 2 deletions
diff --git a/Makefile.am b/Makefile.am
index df7c06b..8ea9ca9 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -41,18 +41,82 @@ eina.spec.in \
41m4/ac_attribute.m4 \ 41m4/ac_attribute.m4 \
42m4/efl_benchmark.m4 \ 42m4/efl_benchmark.m4 \
43m4/efl_compiler_flag.m4 \ 43m4/efl_compiler_flag.m4 \
44m4/efl_coverage.m4 \
44m4/efl_cpu.m4 \ 45m4/efl_cpu.m4 \
45m4/efl_doxygen.m4 \ 46m4/efl_doxygen.m4 \
46m4/efl_fnmatch.m4 \ 47m4/efl_fnmatch.m4 \
48m4/efl_tests.m4 \
47m4/efl_threads.m4 \ 49m4/efl_threads.m4 \
48m4/eina_bench.m4 \ 50m4/eina_bench.m4 \
49m4/eina_check.m4 \ 51m4/eina_check.m4 \
50m4/efl_path_max.m4 52m4/efl_path_max.m4
51 53
52.PHONY: doc 54.PHONY: doc coverage benchmark
53 55
54# Documentation 56# Documentation
55 57
56doc: 58doc:
57 @echo "entering doc/" 59 @echo "entering doc/"
58 @cd doc && make doc 60 @cd doc && make doc
61
62# Unit tests
63
64if EFL_ENABLE_TESTS
65
66check-local:
67 @./src/tests/eina_suite
68
69else
70
71check-local:
72 @echo "reconfigure with --enable-tests"
73
74endif
75
76# Coverage report
77
78if EFL_ENABLE_COVERAGE
79lcov-reset:
80 @rm -rf coverage
81 @find . -name "*.gcda" -exec rm {} \;
82 @lcov --directory . --zerocounters
83
84lcov-report:
85 @mkdir coverage
86 @lcov --compat-libtool --directory $(top_srcdir)/src --capture --output-file coverage/coverage.info
87 @lcov -l coverage/coverage.info |grep "\\.h" |cut -d " " -f 2 > coverage/remove
88 @lcov -r coverage/coverage.info `cat coverage/remove` > coverage/coverage.cleaned.info
89 @rm coverage/remove
90 @mv coverage/coverage.cleaned.info coverage/coverage.info
91 @genhtml -t "$(PACKAGE_STRING)" -o coverage coverage/coverage.info
92
93coverage:
94 @make lcov-reset
95 @make check
96 @make lcov-report
97else
98lcov-reset:
99 @echo "reconfigure with --enable-coverage"
100
101lcov-report:
102 @echo "reconfigure with --enable-coverage"
103
104coverage:
105 @echo "reconfigure with --enable-tests --enable-coverage"
106endif
107
108if EFL_ENABLE_BENCHMARK
109
110benchmark:
111 @cd src && make benchmark
112 @mkdir result || true
113 @cd result && ../src/tests/eina_bench `date +%F_%s`
114
115else
116
117benchmark:
118 @echo "reconfigure with --enable-benchmark"
119endif
120
121clean-local:
122 @rm -rf coverage benchmark
diff --git a/configure.ac b/configure.ac
index 97fb9ed..5774ad4 100644
--- a/configure.ac
+++ b/configure.ac
@@ -569,6 +569,20 @@ EINA_CHECK_MODULE([one-big], [${enable_one_big}], [one big])
569 569
570### Make the debug preprocessor configurable 570### Make the debug preprocessor configurable
571 571
572### Unit tests, coverage and benchmarking
573
574EFL_CHECK_TESTS([enable_tests="yes"], [enable_tests="no"])
575
576EFL_CHECK_COVERAGE([${enable_tests}], [enable_coverage="yes"], [enable_coverage="no"])
577EINA_CFLAGS="${EINA_CFLAGS} ${EFL_COVERAGE_CFLAGS}"
578EINA_LIBS="${EINA_LIBS} ${EFL_COVERAGE_LIBS}"
579if test "x$enable_coverage" = "xyes" ; then
580 EINA_CFLAGS="${EINA_CFLAGS} ${EFL_DEBUG_CFLAGS}"
581fi
582
583EFL_CHECK_BENCHMARK([enable_benchmark="yes"], [enable_benchmark="no"])
584EINA_BENCH_MODULE([glib], [${enable_benchmark}], [glib-2.0], [enable_benchmark_glib="yes"], [enable_benchmark_glib="no"])
585
572AC_SUBST(requirement_eina) 586AC_SUBST(requirement_eina)
573 587
574### Create the .pc.in file according to the major version 588### Create the .pc.in file according to the major version
@@ -605,6 +619,7 @@ src/modules/mp/pass_through/Makefile
605src/modules/mp/fixed_bitmap/Makefile 619src/modules/mp/fixed_bitmap/Makefile
606src/modules/mp/buddy/Makefile 620src/modules/mp/buddy/Makefile
607src/modules/mp/one_big/Makefile 621src/modules/mp/one_big/Makefile
622src/tests/Makefile
608]) 623])
609 624
610AC_OUTPUT 625AC_OUTPUT
@@ -638,6 +653,13 @@ echo " Iconv support........: ${have_iconv}"
638echo " File dirfd...........: ${have_dirfd}" 653echo " File dirfd...........: ${have_dirfd}"
639echo 654echo
640echo " Documentation........: ${build_doc}" 655echo " Documentation........: ${build_doc}"
656echo " Tests................: ${enable_tests}"
657echo " Coverage.............: ${enable_coverage}"
658echo " Benchmark............: ${enable_benchmark}"
659if test "x${enable_benchmark}" = "xyes" ; then
660echo " Glib...............: ${enable_benchmark_glib}"
661echo " E17 real data......: ${enable_benchmark_e17}"
662fi
641echo 663echo
642echo " CPU Specific Extensions:" 664echo " CPU Specific Extensions:"
643echo " MMX................: ${have_mmx}" 665echo " MMX................: ${have_mmx}"
diff --git a/src/Makefile.am b/src/Makefile.am
index 7e99d0b..0a6b2a3 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -1,3 +1,17 @@
1SUBDIRS = lib include modules 1SUBDIRS = lib include modules tests
2 2
3MAINTAINERCLEANFILES = Makefile.in 3MAINTAINERCLEANFILES = Makefile.in
4
5.PHONY: benchmark
6
7if EFL_ENABLE_BENCHMARK
8
9benchmark: all
10 cd tests && make eina_bench
11
12else
13
14benchmark:
15 @echo "reconfigure with --enable-benchmark"
16
17endif
diff --git a/src/tests/Ecore_Data.h b/src/tests/Ecore_Data.h
new file mode 100644
index 0000000..50d42f1
--- /dev/null
+++ b/src/tests/Ecore_Data.h
@@ -0,0 +1,557 @@
1#ifndef _ECORE_DATA_H
2# define _ECORE_DATA_H
3
4#include <stdio.h>
5/* we need this for size_t */
6#include <stddef.h>
7
8#ifdef EAPI
9# undef EAPI
10#endif
11
12#ifdef _WIN32
13# ifdef EFL_ECORE_BUILD
14# ifdef DLL_EXPORT
15# define EAPI __declspec(dllexport)
16# else
17# define EAPI
18# endif /* ! DLL_EXPORT */
19# else
20# define EAPI __declspec(dllimport)
21# endif /* ! EFL_ECORE_BUILD */
22#else
23# ifdef __GNUC__
24# if __GNUC__ >= 4
25# define EAPI __attribute__ ((visibility("default")))
26# else
27# define EAPI
28# endif
29# else
30# define EAPI
31# endif
32#endif /* ! _WIN32 */
33
34/**
35 * @file Ecore_Data.h
36 * @brief Contains threading, list, hash, debugging and tree functions.
37 */
38
39# ifdef __cplusplus
40extern "C" {
41# endif
42
43
44#ifndef TRUE
45# define TRUE 1
46#endif
47
48#ifndef FALSE
49# define FALSE 0
50#endif
51
52#ifdef FREE
53# undef FREE
54#endif
55#define FREE(ptr) free(ptr); ptr = NULL;
56
57#ifdef IF_FREE
58# undef IF_FREE
59#endif
60#define IF_FREE(ptr) if (ptr) {free(ptr); } ptr = NULL;
61
62/* convenience macros for checking pointer parameters for non-NULL */
63#undef CHECK_PARAM_POINTER_RETURN
64#define CHECK_PARAM_POINTER_RETURN(sparam, param, ret) \
65 if (!(param)) \
66 { \
67 printf("***** Developer Warning ***** :\n" \
68 "\tThis program is calling:\n\n" \
69 "\t%s();\n\n" \
70 "\tWith the parameter:\n\n" \
71 "\t%s\n\n" \
72 "\tbeing NULL. Please fix your program.", __FUNCTION__, sparam); \
73 if (getenv("ECORE_ERROR_ABORT")) { abort(); } \
74 return ret; \
75 }
76
77#undef CHECK_PARAM_POINTER
78#define CHECK_PARAM_POINTER(sparam, param) \
79 if (!(param)) \
80 { \
81 printf("***** Developer Warning ***** :\n" \
82 "\tThis program is calling:\n\n" \
83 "\t%s();\n\n" \
84 "\tWith the parameter:\n\n" \
85 "\t%s\n\n" \
86 "\tbeing NULL. Please fix your program.", __FUNCTION__, sparam); \
87 if (getenv("ECORE_ERROR_ABORT")) { abort(); } \
88 return; \
89 }
90
91
92# ifdef __sgi
93# define __FUNCTION__ "unknown"
94# ifndef __cplusplus
95# define inline
96# endif
97# endif
98
99# define ECORE_SORT_MIN 0
100# define ECORE_SORT_MAX 1
101
102typedef void (*Ecore_For_Each)(void *value, void *user_data);
103# define ECORE_FOR_EACH(function) ((Ecore_For_Each)function)
104
105typedef void (*Ecore_Free_Cb)(void *data);
106# define ECORE_FREE_CB(func) ((Ecore_Free_Cb)func)
107
108typedef unsigned int (*Ecore_Hash_Cb)(const void *key);
109# define ECORE_HASH_CB(function) ((Ecore_Hash_Cb)function)
110
111typedef int (*Ecore_Compare_Cb)(const void *data1, const void *data2);
112# define ECORE_COMPARE_CB(function) ((Ecore_Compare_Cb)function)
113
114typedef struct _ecore_list Ecore_List;
115# define ECORE_LIST(list) ((Ecore_List *)list)
116
117typedef struct _ecore_list_node Ecore_List_Node;
118# define ECORE_LIST_NODE(node) ((Ecore_List_Node *)node)
119
120typedef struct _ecore_strbuf Ecore_Strbuf;
121# define ECORE_STRBUF(buf) ((Ecore_Strbuf *)buf)
122
123struct _ecore_list_node
124{
125 void *data;
126 struct _ecore_list_node *next;
127};
128
129struct _ecore_list
130{
131 Ecore_List_Node *first; /* The first node in the list */
132 Ecore_List_Node *last; /* The last node in the list */
133 Ecore_List_Node *current; /* The current node in the list */
134
135 Ecore_Free_Cb free_func; /* The callback to free data in nodes */
136
137 int nodes; /* The number of nodes in the list */
138 int index; /* The position from the front of the
139 list of current node */
140};
141
142EAPI int ecore_direct_compare(const void *key1, const void *key2);
143EAPI int ecore_str_compare(const void *key1, const void *key2);
144
145EAPI unsigned int ecore_direct_hash(const void *key);
146EAPI unsigned int ecore_str_hash(const void *key);
147
148/* Creating and initializing new list structures */
149EAPI Ecore_List * ecore_list_new(void);
150EAPI int ecore_list_init(Ecore_List *list);
151
152/* Adding items to the list */
153EAPI int ecore_list_append(Ecore_List *list, void *_data);
154EAPI int ecore_list_prepend(Ecore_List *list, void *_data);
155EAPI int ecore_list_insert(Ecore_List *list, void *_data);
156EAPI int ecore_list_append_list(Ecore_List *list,
157 Ecore_List *append);
158EAPI int ecore_list_prepend_list(Ecore_List *list,
159 Ecore_List *prepend);
160
161/* Removing items from the list */
162EAPI int ecore_list_remove_destroy(Ecore_List *list);
163EAPI void * ecore_list_remove(Ecore_List *list);
164EAPI void * ecore_list_first_remove(Ecore_List *list);
165EAPI void * ecore_list_last_remove(Ecore_List *list);
166
167/* Retrieve the current position in the list */
168EAPI void * ecore_list_current(Ecore_List *list);
169EAPI void * ecore_list_first(Ecore_List *list);
170EAPI void * ecore_list_last(Ecore_List *list);
171EAPI int ecore_list_index(Ecore_List *list);
172EAPI int ecore_list_count(Ecore_List *list);
173
174/* Traversing the list */
175EAPI int ecore_list_for_each(Ecore_List *list,
176 Ecore_For_Each function,
177 void *user_data);
178EAPI void * ecore_list_first_goto(Ecore_List *list);
179EAPI void * ecore_list_last_goto(Ecore_List *list);
180EAPI void * ecore_list_index_goto(Ecore_List *list, int index);
181EAPI void * ecore_list_goto(Ecore_List *list, const void *_data);
182
183/* Traversing the list and returning data */
184EAPI void * ecore_list_next(Ecore_List *list);
185EAPI void * ecore_list_find(Ecore_List *list,
186 Ecore_Compare_Cb function,
187 const void *user_data);
188
189/* Sorting the list */
190EAPI int ecore_list_sort(Ecore_List *list,
191 Ecore_Compare_Cb compare,
192 char order);
193EAPI int ecore_list_mergesort(Ecore_List *list,
194 Ecore_Compare_Cb compare,
195 char order);
196EAPI int ecore_list_heapsort(Ecore_List *list,
197 Ecore_Compare_Cb compare,
198 char order);
199EAPI void ecore_list_merge(Ecore_List *list, Ecore_List *l2,
200 Ecore_Compare_Cb, char order);
201
202/* Check to see if there is any data in the list */
203EAPI int ecore_list_empty_is(Ecore_List *list);
204
205/* Remove every node in the list without freeing the list itself */
206EAPI int ecore_list_clear(Ecore_List *list);
207/* Free the list and it's contents */
208EAPI void ecore_list_destroy(Ecore_List *list);
209
210/* Creating and initializing list nodes */
211EAPI Ecore_List_Node *ecore_list_node_new(void);
212EAPI int ecore_list_node_init(Ecore_List_Node *newNode);
213
214/* Destroying nodes */
215EAPI int ecore_list_node_destroy(Ecore_List_Node *_e_node,
216 Ecore_Free_Cb free_func);
217
218EAPI int ecore_list_free_cb_set(Ecore_List *list,
219 Ecore_Free_Cb free_func);
220
221typedef Ecore_List Ecore_DList;
222# define ECORE_DLIST(dlist) ((Ecore_DList *)dlist)
223
224typedef struct _ecore_dlist_node Ecore_DList_Node;
225# define ECORE_DLIST_NODE(dlist) ((Ecore_DList_Node *)dlist)
226
227struct _ecore_dlist_node
228{
229 Ecore_List_Node single;
230 Ecore_DList_Node *previous;
231};
232
233/* Creating and initializing new list structures */
234EAPI Ecore_DList *ecore_dlist_new(void);
235EAPI int ecore_dlist_init(Ecore_DList *list);
236EAPI void ecore_dlist_destroy(Ecore_DList *list);
237
238/* Adding items to the list */
239EAPI int ecore_dlist_append(Ecore_DList *_e_dlist, void *_data);
240EAPI int ecore_dlist_prepend(Ecore_DList *_e_dlist, void *_data);
241EAPI int ecore_dlist_insert(Ecore_DList *_e_dlist, void *_data);
242EAPI int ecore_dlist_append_list(Ecore_DList *_e_dlist,
243 Ecore_DList *append);
244EAPI int ecore_dlist_prepend_list(Ecore_DList *_e_dlist,
245 Ecore_DList *prepend);
246
247/* Info about list's state */
248# define ecore_dlist_first(list) ecore_list_first(list)
249# define ecore_dlist_last(list) ecore_list_last(list)
250EAPI void * ecore_dlist_current(Ecore_DList *list);
251EAPI int ecore_dlist_index(Ecore_DList *list);
252# define ecore_dlist_count(list) ecore_list_count(list)
253
254/* Removing items from the list */
255EAPI void * ecore_dlist_remove(Ecore_DList *_e_dlist);
256EAPI void * ecore_dlist_first_remove(Ecore_DList *_e_dlist);
257EAPI int ecore_dlist_remove_destroy(Ecore_DList *list);
258EAPI void * ecore_dlist_last_remove(Ecore_DList *_e_dlist);
259
260/* Traversing the list */
261# define ecore_dlist_for_each(list, function, user_data) \
262 ecore_list_for_each(list, function, user_data)
263EAPI void * ecore_dlist_first_goto(Ecore_DList *_e_dlist);
264EAPI void * ecore_dlist_last_goto(Ecore_DList *_e_dlist);
265EAPI void * ecore_dlist_index_goto(Ecore_DList *_e_dlist, int index);
266EAPI void * ecore_dlist_goto(Ecore_DList *_e_dlist, void *_data);
267
268/* Traversing the list and returning data */
269EAPI void * ecore_dlist_next(Ecore_DList *list);
270EAPI void * ecore_dlist_previous(Ecore_DList *list);
271
272/* Sorting the list */
273EAPI int ecore_dlist_sort(Ecore_DList *list,
274 Ecore_Compare_Cb compare,
275 char order);
276EAPI int ecore_dlist_mergesort(Ecore_DList *list,
277 Ecore_Compare_Cb compare,
278 char order);
279# define ecore_dlist_heapsort(list, compare, order) \
280 ecore_list_heapsort(list, compare, order)
281EAPI void ecore_dlist_merge(Ecore_DList *list, Ecore_DList *l2,
282 Ecore_Compare_Cb, char order);
283
284/* Check to see if there is any data in the list */
285EAPI int ecore_dlist_empty_is(Ecore_DList *_e_dlist);
286
287/* Remove every node in the list without free'ing it */
288EAPI int ecore_dlist_clear(Ecore_DList *_e_dlist);
289
290/* Creating and initializing list nodes */
291EAPI int ecore_dlist_node_init(Ecore_DList_Node *node);
292EAPI Ecore_DList_Node *ecore_dlist_node_new(void);
293
294/* Destroying nodes */
295EAPI int ecore_dlist_node_destroy(Ecore_DList_Node *node,
296 Ecore_Free_Cb free_func);
297
298EAPI int ecore_dlist_free_cb_set(Ecore_DList *dlist,
299 Ecore_Free_Cb free_func);
300
301
302
303/*
304 * Hash Table Implementation:
305 *
306 * Traditional hash table implementation. I had tried a list of tables
307 * approach to save on the realloc's but it ended up being much slower than
308 * the traditional approach.
309 */
310
311typedef struct _ecore_hash_node Ecore_Hash_Node;
312# define ECORE_HASH_NODE(hash) ((Ecore_Hash_Node *)hash)
313
314struct _ecore_hash_node
315{
316 Ecore_Hash_Node *next; /* Pointer to the next node in the bucket list */
317 void *key; /* The key for the data node */
318 void *value; /* The value associated with this node */
319};
320
321typedef struct _ecore_hash Ecore_Hash;
322# define ECORE_HASH(hash) ((Ecore_Hash *)hash)
323
324struct _ecore_hash
325{
326 Ecore_Hash_Node **buckets;
327 int size; /* An index into the table of primes to
328 determine size */
329 int nodes; /* The number of nodes currently in the hash */
330
331 int index; /* The current index into the bucket table */
332
333 Ecore_Compare_Cb compare; /* The function used to compare node values */
334 Ecore_Hash_Cb hash_func; /* The callback function to determine hash */
335
336 Ecore_Free_Cb free_key; /* The callback function to free key */
337 Ecore_Free_Cb free_value; /* The callback function to free value */
338};
339
340/* Create and initialize a hash */
341EAPI Ecore_Hash *ecore_hash_new(Ecore_Hash_Cb hash_func,
342 Ecore_Compare_Cb compare);
343EAPI int ecore_hash_init(Ecore_Hash *hash,
344 Ecore_Hash_Cb hash_func,
345 Ecore_Compare_Cb compare);
346
347/* Functions related to freeing the data in the hash table */
348EAPI int ecore_hash_free_key_cb_set(Ecore_Hash *hash,
349 Ecore_Free_Cb function);
350EAPI int ecore_hash_free_value_cb_set(Ecore_Hash *hash,
351 Ecore_Free_Cb function);
352EAPI void ecore_hash_destroy(Ecore_Hash *hash);
353
354EAPI int ecore_hash_count(Ecore_Hash *hash);
355EAPI int ecore_hash_for_each_node(Ecore_Hash *hash,
356 Ecore_For_Each for_each_func,
357 void *user_data);
358EAPI Ecore_List *ecore_hash_keys(Ecore_Hash *hash);
359
360/* Retrieve and store data into the hash */
361EAPI void * ecore_hash_get(Ecore_Hash *hash, const void *key);
362EAPI int ecore_hash_set(Ecore_Hash *hash, void *key, void *value);
363EAPI int ecore_hash_hash_set(Ecore_Hash *hash, Ecore_Hash *set);
364EAPI void * ecore_hash_remove(Ecore_Hash *hash, const void *key);
365EAPI void * ecore_hash_find(Ecore_Hash *hash,
366 Ecore_Compare_Cb compare,
367 const void *value);
368EAPI void ecore_hash_dump_graph(Ecore_Hash *hash);
369EAPI void ecore_hash_dump_stats(Ecore_Hash *hash);
370
371
372typedef struct _ecore_heap Ecore_Sheap;
373# define ECORE_HEAP(heap) ((Ecore_Sheap *)heap)
374
375struct _ecore_heap
376{
377 void **data;
378 int size;
379 int space;
380
381 char order, sorted;
382
383 /* Callback for comparing node values, default is direct comparison */
384 Ecore_Compare_Cb compare;
385
386 /* Callback for freeing node data, default is NULL */
387 Ecore_Free_Cb free_func;
388};
389
390EAPI Ecore_Sheap *ecore_sheap_new(Ecore_Compare_Cb compare, int size);
391EAPI void ecore_sheap_destroy(Ecore_Sheap *heap);
392EAPI int ecore_sheap_init(Ecore_Sheap *heap,
393 Ecore_Compare_Cb compare,
394 int size);
395EAPI int ecore_sheap_free_cb_set(Ecore_Sheap *heap,
396 Ecore_Free_Cb free_func);
397EAPI int ecore_sheap_insert(Ecore_Sheap *heap, void *data);
398EAPI void * ecore_sheap_extract(Ecore_Sheap *heap);
399EAPI void * ecore_sheap_extreme(Ecore_Sheap *heap);
400EAPI int ecore_sheap_change(Ecore_Sheap *heap,
401 void *item,
402 void *newval);
403EAPI int ecore_sheap_compare_set(Ecore_Sheap *heap,
404 Ecore_Compare_Cb compare);
405EAPI void ecore_sheap_order_set(Ecore_Sheap *heap, char order);
406EAPI void ecore_sheap_sort(Ecore_Sheap *heap);
407
408EAPI void * ecore_sheap_item(Ecore_Sheap *heap, int i);
409
410
411typedef struct _ecore_string Ecore_String;
412struct _ecore_string
413{
414 char *string;
415 int references;
416};
417
418EAPI int ecore_string_init();
419EAPI void ecore_string_shutdown();
420EAPI const char *ecore_string_instance(const char *string);
421EAPI void ecore_string_release(const char *string);
422
423typedef struct _Ecore_Tree_Node Ecore_Tree_Node;
424# define ECORE_TREE_NODE(object) ((Ecore_Tree_Node *)object)
425struct _Ecore_Tree_Node
426{
427
428 /* The actual data for each node */
429 void *key;
430 void *value;
431
432 /* Pointers to surrounding nodes */
433 Ecore_Tree_Node *parent;
434 Ecore_Tree_Node *left_child;
435 Ecore_Tree_Node *right_child;
436
437 /* Book keeping information for quicker balancing of the tree */
438 int max_right;
439 int max_left;
440};
441
442typedef struct _Ecore_Tree Ecore_Tree;
443# define ECORE_TREE(object) ((Ecore_Tree *)object)
444struct _Ecore_Tree
445{
446 /* Nodes of the tree */
447 Ecore_Tree_Node *tree;
448
449 /* Callback for comparing node values, default is direct comparison */
450 Ecore_Compare_Cb compare_func;
451
452 /* Callback for freeing node data, default is NULL */
453 Ecore_Free_Cb free_value;
454 /* Callback for freeing node key, default is NULL */
455 Ecore_Free_Cb free_key;
456};
457
458/* Some basic tree functions */
459/* Allocate and initialize a new tree */
460EAPI Ecore_Tree * ecore_tree_new(Ecore_Compare_Cb compare_func);
461/* Initialize a new tree */
462EAPI int ecore_tree_init(Ecore_Tree *tree,
463 Ecore_Compare_Cb compare_func);
464
465/* Free the tree */
466EAPI int ecore_tree_destroy(Ecore_Tree *tree);
467/* Check to see if the tree has any nodes in it */
468EAPI int ecore_tree_empty_is(Ecore_Tree *tree);
469
470/* Retrieve the value associated with key */
471EAPI void * ecore_tree_get(Ecore_Tree *tree, const void *key);
472EAPI Ecore_Tree_Node *ecore_tree_get_node(Ecore_Tree *tree, const void *key);
473/* Retrieve the value of node with key greater than or equal to key */
474EAPI void * ecore_tree_closest_larger_get(Ecore_Tree *tree,
475 const void *key);
476/* Retrieve the value of node with key less than or equal to key */
477EAPI void * ecore_tree_closest_smaller_get(Ecore_Tree *tree,
478 const void *key);
479
480/* Set the value associated with key to value */
481EAPI int ecore_tree_set(Ecore_Tree *tree, void *key, void *value);
482/* Remove the key from the tree */
483EAPI int ecore_tree_remove(Ecore_Tree *tree, const void *key);
484
485/* Add a node to the tree */
486EAPI int ecore_tree_node_add(Ecore_Tree *tree,
487 Ecore_Tree_Node *node);
488/* Remove a node from the tree */
489EAPI int ecore_tree_node_remove(Ecore_Tree *tree,
490 Ecore_Tree_Node *node);
491
492/* For each node in the tree perform the for_each_func function */
493/* For this one pass in the node */
494EAPI int ecore_tree_for_each_node(Ecore_Tree *tree,
495 Ecore_For_Each for_each_func,
496 void *user_data);
497/* And here pass in the node's value */
498EAPI int ecore_tree_for_each_node_value(
499 Ecore_Tree *tree,
500 Ecore_For_Each
501 for_each_func,
502 void *user_data);
503
504/* Some basic node functions */
505/* Initialize a node */
506EAPI int ecore_tree_node_init(Ecore_Tree_Node *new_node);
507/* Allocate and initialize a new node */
508EAPI Ecore_Tree_Node *ecore_tree_node_new(void);
509/* Free the desired node */
510EAPI int ecore_tree_node_destroy(Ecore_Tree_Node *node,
511 Ecore_Free_Cb free_value,
512 Ecore_Free_Cb free_key);
513
514/* Set the node's key to key */
515EAPI int ecore_tree_node_key_set(Ecore_Tree_Node *node, void *key);
516/* Retrieve the key in node */
517EAPI void * ecore_tree_node_key_get(Ecore_Tree_Node *node);
518
519/* Set the node's value to value */
520EAPI int ecore_tree_node_value_set(Ecore_Tree_Node *node,
521 void *value);
522/* Retrieve the value in node */
523EAPI void * ecore_tree_node_value_get(Ecore_Tree_Node *node);
524
525/* Add a function to free the data stored in nodes */
526EAPI int ecore_tree_free_value_cb_set(Ecore_Tree *tree,
527 Ecore_Free_Cb free_value);
528/* Add a function to free the keys stored in nodes */
529EAPI int ecore_tree_free_key_cb_set(Ecore_Tree *tree,
530 Ecore_Free_Cb free_key);
531
532
533EAPI Ecore_Strbuf * ecore_strbuf_new(void);
534EAPI void ecore_strbuf_free(Ecore_Strbuf *buf);
535EAPI void ecore_strbuf_append(Ecore_Strbuf *buf, const char *str);
536EAPI void ecore_strbuf_append_char(Ecore_Strbuf *buf, char c);
537EAPI void ecore_strbuf_insert(Ecore_Strbuf *buf, const char *str,
538 size_t pos);
539# define ecore_strbuf_prepend(buf, str) ecore_strbuf_insert(buf, str, 0)
540EAPI const char * ecore_strbuf_string_get(Ecore_Strbuf *buf);
541EAPI size_t ecore_strbuf_length_get(Ecore_Strbuf *buf);
542EAPI int ecore_strbuf_replace(Ecore_Strbuf *buf, const char *str,
543 const char *with, unsigned int n);
544# define ecore_strbuf_replace_first(buf, str, with) \
545 ecore_strbuf_replace(buf, str, with, 1)
546EAPI int ecore_strbuf_replace_all(Ecore_Strbuf *buf,
547 const char *str,
548 const char *with);
549
550extern int ecore_str_compare(const void *key1, const void *key2);
551extern int ecore_direct_compare(const void *key1, const void *key2);
552extern unsigned int ecore_str_hash(const void *key);
553
554#ifdef __cplusplus
555}
556#endif
557#endif /* _ECORE_DATA_H */
diff --git a/src/tests/Evas_Data.h b/src/tests/Evas_Data.h
new file mode 100644
index 0000000..9784892
--- /dev/null
+++ b/src/tests/Evas_Data.h
@@ -0,0 +1,195 @@
1#ifndef _EVAS_DATA_H
2#define _EVAS_DATA_H
3
4#ifdef EAPI
5# undef EAPI
6#endif
7
8#ifdef _WIN32
9# ifdef EFL_EVAS_BUILD
10# ifdef DLL_EXPORT
11# define EAPI __declspec(dllexport)
12# else
13# define EAPI
14# endif /* ! DLL_EXPORT */
15# else
16# define EAPI __declspec(dllimport)
17# endif /* ! EFL_EVAS_BUILD */
18#else
19# ifdef __GNUC__
20# if __GNUC__ >= 4
21# define EAPI __attribute__ ((visibility("default")))
22# else
23# define EAPI
24# endif
25# else
26# define EAPI
27# endif
28#endif /* ! _WIN32 */
29
30/**
31 * @file
32 * @brief These routines are used for Evas data types.
33 */
34
35typedef unsigned char Evas_Bool;
36
37typedef struct _Evas_Array_Hash Evas_Array_Hash;
38typedef struct _Evas_Hash Evas_Hash; /**< A Hash table handle */
39typedef struct _Evas_List Evas_List; /**< A generic linked list node handle */
40typedef struct _Evas_Object_List Evas_Object_List;
41
42struct _Evas_Hash
43{
44 int population;
45 Evas_Object_List *buckets[256];
46};
47
48struct _Evas_List /** A linked list node */
49{
50 void *data; /**< Pointer to list element payload */
51 Evas_List *next; /**< Next member in the list */
52 Evas_List *prev; /**< Previous member in the list */
53 struct _Evas_List_Accounting *accounting; /**< Private list accounting info - don't touch */
54};
55
56struct _Evas_Object_List
57{
58 Evas_Object_List *next, *prev;
59 Evas_Object_List *last;
60};
61
62
63#ifdef __cplusplus
64extern "C" {
65#endif
66
67/*
68 * Evas Array Hash functions
69 */
70
71EAPI Evas_Array_Hash *evas_array_hash_new (void);
72EAPI void evas_array_hash_free (Evas_Array_Hash *hash);
73EAPI void evas_array_hash_add (Evas_Array_Hash *hash,
74 int key,
75 int data);
76EAPI int evas_array_hash_search (Evas_Array_Hash *hash,
77 int key);
78
79
80/*
81 * Evas Hash functions
82 */
83
84/* FIXME: add:
85 * api to add find, del members by data, size not just string and also
86 * provide hash generation functions settable by the app
87 *
88 * do we really need this? hmmm - let me think... there may be a better way
89 */
90EAPI Evas_Hash *evas_hash_add (Evas_Hash *hash,
91 const char *key,
92 const void *data);
93EAPI Evas_Hash *evas_hash_direct_add (Evas_Hash *hash,
94 const char *key,
95 const void *data);
96EAPI Evas_Hash *evas_hash_del (Evas_Hash *hash,
97 const char *key,
98 const void *data);
99EAPI void * evas_hash_find (const Evas_Hash *hash,
100 const char *key);
101EAPI void * evas_hash_modify (Evas_Hash *hash,
102 const char *key,
103 const void *data);
104EAPI int evas_hash_size (const Evas_Hash *hash);
105EAPI void evas_hash_free (Evas_Hash *hash);
106EAPI void evas_hash_foreach (const Evas_Hash *hash,
107 Evas_Bool (*func)(
108 const Evas_Hash *hash,
109 const char *
110 key,
111 void *data,
112 void *fdata),
113 const void *fdata);
114EAPI int evas_hash_alloc_error (void);
115
116
117/*
118 * Evas List functions
119 */
120
121EAPI Evas_List *evas_list_append (Evas_List *list,
122 const void *data);
123EAPI Evas_List *evas_list_prepend (Evas_List *list,
124 const void *data);
125EAPI Evas_List *evas_list_append_relative (Evas_List *list,
126 const void *data,
127 const void *relative);
128EAPI Evas_List *evas_list_append_relative_list (Evas_List *list,
129 const void *data,
130 Evas_List *relative);
131EAPI Evas_List *evas_list_prepend_relative (Evas_List *list,
132 const void *data,
133 const void *relative);
134EAPI Evas_List *evas_list_prepend_relative_list (Evas_List *list,
135 const void *data,
136 Evas_List *relative);
137EAPI Evas_List *evas_list_remove (Evas_List *list,
138 const void *data);
139EAPI Evas_List *evas_list_remove_list (Evas_List *list,
140 Evas_List *remove_list);
141EAPI Evas_List *evas_list_promote_list (Evas_List *list,
142 Evas_List *move_list);
143EAPI void * evas_list_find (const Evas_List *list,
144 const void *data);
145EAPI Evas_List *evas_list_find_list (const Evas_List *list,
146 const void *data);
147EAPI Evas_List *evas_list_free (Evas_List *list);
148EAPI Evas_List *evas_list_last (const Evas_List *list);
149EAPI Evas_List *evas_list_next (const Evas_List *list);
150EAPI Evas_List *evas_list_prev (const Evas_List *list);
151EAPI void * evas_list_data (const Evas_List *list);
152EAPI int evas_list_count (const Evas_List *list);
153EAPI void * evas_list_nth (const Evas_List *list, int n);
154EAPI Evas_List *evas_list_nth_list (const Evas_List *list, int n);
155EAPI Evas_List *evas_list_reverse (Evas_List *list);
156EAPI Evas_List *evas_list_sort (Evas_List *list,
157 int size,
158 int (*func)(void *,void *));
159EAPI int evas_list_alloc_error (void);
160
161
162/*
163 * Evas Object List functions
164 */
165
166EAPI void * evas_object_list_append (void *in_list,
167 void *in_item);
168EAPI void * evas_object_list_prepend (void *in_list,
169 void *in_item);
170EAPI void * evas_object_list_append_relative (void *in_list,
171 void *in_item,
172 void *in_relative);
173EAPI void * evas_object_list_prepend_relative (void *in_list,
174 void *in_item,
175 void *in_relative);
176EAPI void * evas_object_list_remove (void *in_list,
177 void *in_item);
178EAPI void * evas_object_list_find (void *in_list,
179 void *in_item);
180
181
182/*
183 * Evas Stringshare functions
184 */
185
186EAPI void evas_stringshare_init (void); /* not implemented */
187EAPI void evas_stringshare_shutdown (void); /* not implemented */
188EAPI const char *evas_stringshare_add (const char *str);
189EAPI void evas_stringshare_del (const char *str);
190
191#ifdef __cplusplus
192}
193#endif
194
195#endif /* _EVAS_DATA_H */
diff --git a/src/tests/Makefile.am b/src/tests/Makefile.am
new file mode 100644
index 0000000..622afbf
--- /dev/null
+++ b/src/tests/Makefile.am
@@ -0,0 +1,120 @@
1MAINTAINERCLEANFILES = Makefile.in
2
3benchdir = $(bindir)
4
5AM_CPPFLAGS = \
6-I$(top_srcdir)/src/lib \
7-I$(top_srcdir)/src/include \
8-I$(top_builddir)/src/include \
9-I$(top_builddir)/src/lib \
10-DPACKAGE_BIN_DIR=\"$(bindir)\" \
11-DPACKAGE_LIB_DIR=\"$(libdir)\" \
12-DPACKAGE_DATA_DIR=\"$(datadir)/$(PACKAGE)\" \
13-DPACKAGE_BUILD_DIR=\"`pwd`/$(top_builddir)\" \
14@CHECK_CFLAGS@ \
15@GLIB_CFLAGS@
16
17if EINA_HAVE_GLIB
18
19AM_CPPFLAGS += -DEINA_BENCH_HAVE_GLIB
20
21endif
22
23if EINA_ENABLE_BENCHMARK_E17
24
25AM_CPPFLAGS += -DEINA_ENABLE_BENCH_E17
26
27endif
28
29if EFL_ENABLE_TESTS
30
31check_PROGRAMS = eina_suite
32
33eina_suite_SOURCES = \
34eina_suite.c \
35eina_test_fp.c \
36eina_test_stringshare.c \
37eina_test_ustringshare.c\
38eina_test_ustr.c \
39eina_test_binshare.c \
40eina_test_array.c \
41eina_test_error.c \
42eina_test_sched.c \
43eina_test_log.c \
44eina_test_magic.c \
45eina_test_inlist.c \
46eina_test_main.c \
47eina_test_counter.c \
48eina_test_lalloc.c \
49eina_test_hash.c \
50eina_test_iterator.c \
51eina_test_accessor.c \
52eina_test_module.c \
53eina_test_convert.c \
54eina_test_rbtree.c \
55eina_test_file.c \
56eina_test_benchmark.c \
57eina_test_mempool.c \
58eina_test_rectangle.c \
59eina_test_list.c \
60eina_test_matrixsparse.c \
61eina_test_tiler.c \
62eina_test_strbuf.c \
63eina_test_str.c \
64eina_test_quadtree.c
65
66eina_suite_LDADD = @CHECK_LIBS@ $(top_builddir)/src/lib/libeina.la -lm
67
68module_dummydir = $(libdir)/eina/test
69module_dummy_LTLIBRARIES = module_dummy.la
70
71module_dummy_la_SOURCES = \
72eina_test_module_dummy.c
73
74module_dummy_la_CPPFLAGS = \
75-I$(top_srcdir)/src/lib \
76-I$(top_srcdir)/src/include \
77-I$(top_builddir)/src/include \
78-I$(top_builddir)/src/lib \
79@EFL_EINA_BUILD@
80module_dummy_la_LIBADD = $(top_builddir)/src/lib/libeina.la @EINA_LIBS@
81module_dummy_la_LDFLAGS = -no-undefined @lt_enable_auto_import@ -module -avoid-version
82module_dummy_la_LIBTOOLFLAGS = --tag=disable-static
83
84endif
85
86if EFL_ENABLE_BENCHMARK
87
88bench_PROGRAMS = eina_bench
89
90eina_bench_SOURCES = \
91eina_bench.c \
92eina_bench_sort.c \
93eina_bench_hash.c \
94eina_bench_stringshare.c \
95eina_bench_convert.c \
96eina_bench_mempool.c \
97eina_bench_stringshare_e17.c \
98eina_bench_array.c \
99eina_bench_rectangle_pool.c \
100ecore_list.c \
101ecore_strings.c \
102ecore_hash.c \
103ecore_sheap.c \
104evas_hash.c \
105evas_list.c \
106evas_mempool.c \
107evas_object_list.c \
108evas_stringshare.c \
109eina_bench_quad.c
110
111eina_bench_LDADD = @GLIB_LIBS@ $(top_builddir)/src/lib/libeina.la
112
113endif
114
115EXTRA_DIST = eina_bench.h \
116 eina_suite.h \
117 Ecore_Data.h \
118 Evas_Data.h \
119 evas_mempool.h \
120 strlog
diff --git a/src/tests/ecore_hash.c b/src/tests/ecore_hash.c
new file mode 100644
index 0000000..f957d52
--- /dev/null
+++ b/src/tests/ecore_hash.c
@@ -0,0 +1,949 @@
1#ifdef HAVE_CONFIG_H
2# include <config.h>
3#endif
4
5#include <stdlib.h>
6#include <stdio.h>
7#include <string.h>
8
9#include "Ecore_Data.h"
10
11#define PRIME_TABLE_MAX 21
12#define PRIME_MIN 17
13#define PRIME_MAX 16777213
14
15#define ECORE_HASH_CHAIN_MAX 3
16
17#define ECORE_COMPUTE_HASH(hash, key) hash->hash_func(key) % \
18 ecore_prime_table[hash->size];
19
20#define ECORE_HASH_INCREASE(hash) ((hash && ecore_prime_table[hash->size] < \
21 PRIME_MAX) ? \
22 (hash->nodes / \
23 ecore_prime_table[hash->size]) > \
24 ECORE_HASH_CHAIN_MAX : FALSE)
25#define ECORE_HASH_REDUCE(hash) ((hash && ecore_prime_table[hash->size] > \
26 PRIME_MIN) ? \
27 (double)hash->nodes / \
28 (double)ecore_prime_table[hash->size - 1] \
29 < ((double)ECORE_HASH_CHAIN_MAX * \
30 0.375) : FALSE)
31
32
33static const unsigned int ecore_prime_table[] =
34{
35 17, 31, 61, 127, 257, 509, 1021,
36 2053, 4093, 8191, 16381, 32771, 65537, 131071, 262147, 524287, 1048573,
37 2097143, 4194301, 8388617, 16777213
38};
39
40
41/* Private hash manipulation functions */
42static int _ecore_hash_node_add(Ecore_Hash *hash,
43 Ecore_Hash_Node *node);
44static Ecore_Hash_Node * _ecore_hash_node_get(Ecore_Hash *hash,
45 const void *key);
46static int _ecore_hash_increase(Ecore_Hash *hash);
47static int _ecore_hash_decrease(Ecore_Hash *hash);
48static inline int _ecore_hash_rehash(Ecore_Hash *hash,
49 Ecore_Hash_Node **old_table,
50 int old_size);
51static int _ecore_hash_bucket_destroy(Ecore_Hash_Node *list,
52 Ecore_Free_Cb keyd,
53 Ecore_Free_Cb valued);
54static inline Ecore_Hash_Node *_ecore_hash_bucket_get(Ecore_Hash *hash,
55 Ecore_Hash_Node *bucket,
56 const void *key);
57
58static Ecore_Hash_Node * _ecore_hash_node_new(void *key, void *value);
59static int _ecore_hash_node_init(Ecore_Hash_Node *node,
60 void *key,
61 void *value);
62static int _ecore_hash_node_destroy(Ecore_Hash_Node *node,
63 Ecore_Free_Cb keyd,
64 Ecore_Free_Cb valued);
65
66/**
67 * @defgroup Ecore_Data_Hash_ADT_Creation_Group Hash Creation Functions
68 *
69 * Functions that create hash tables.
70 */
71
72/**
73 * Creates and initializes a new hash
74 * @param hash_func The function for determining hash position.
75 * @param compare The function for comparing node keys.
76 * @return @c NULL on error, a new hash on success.
77 * @ingroup Ecore_Data_Hash_ADT_Creation_Group
78 */
79EAPI Ecore_Hash *
80ecore_hash_new(Ecore_Hash_Cb hash_func, Ecore_Compare_Cb compare)
81{
82 Ecore_Hash *new_hash = (Ecore_Hash *)malloc(sizeof(Ecore_Hash));
83 if (!new_hash)
84 return NULL;
85
86 if (!ecore_hash_init(new_hash, hash_func, compare))
87 {
88 FREE(new_hash);
89 return NULL;
90 }
91
92 return new_hash;
93}
94
95/**
96 * Initializes the given hash.
97 * @param hash The given hash.
98 * @param hash_func The function used for hashing node keys.
99 * @param compare The function used for comparing node keys.
100 * @return @c TRUE on success, @c FALSE on an error.
101 * @ingroup Ecore_Data_Hash_ADT_Creation_Group
102 */
103EAPI int
104ecore_hash_init(Ecore_Hash *hash,
105 Ecore_Hash_Cb hash_func,
106 Ecore_Compare_Cb compare)
107{
108 CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
109
110 memset(hash, 0, sizeof(Ecore_Hash));
111
112 hash->hash_func = hash_func;
113 hash->compare = compare;
114
115 hash->buckets = (Ecore_Hash_Node **)calloc(ecore_prime_table[0],
116 sizeof(Ecore_Hash_Node *));
117
118 return TRUE;
119}
120
121/**
122 * @defgroup Ecore_Data_Hash_ADT_Destruction_Group Hash Destruction Functions
123 *
124 * Functions that destroy hash tables and their contents.
125 */
126
127/**
128 * Sets the function to destroy the keys of the given hash.
129 * @param hash The given hash.
130 * @param function The function used to free the node keys. NULL is a
131 * valid value and means that no function will be called.
132 * @return @c TRUE on success, @c FALSE on error.
133 * @ingroup Ecore_Data_Hash_ADT_Destruction_Group
134 */
135EAPI int
136ecore_hash_free_key_cb_set(Ecore_Hash *hash, Ecore_Free_Cb function)
137{
138 CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
139
140 hash->free_key = function;
141
142 return TRUE;
143}
144
145/**
146 * Sets the function to destroy the values in the given hash.
147 * @param hash The given hash.
148 * @param function The function that will free the node values. NULL is a
149 * valid value and means that no function will be called.
150 * @return @c TRUE on success, @c FALSE on error
151 * @ingroup Ecore_Data_Hash_ADT_Destruction_Group
152 */
153EAPI int
154ecore_hash_free_value_cb_set(Ecore_Hash *hash, Ecore_Free_Cb function)
155{
156 CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
157
158 hash->free_value = function;
159
160 return TRUE;
161}
162
163/**
164 * @defgroup Ecore_Data_Hash_ADT_Data_Group Hash Data Functions
165 *
166 * Functions that set, access and delete values from the hash tables.
167 */
168
169/**
170 * Sets a key-value pair in the given hash table.
171 * @param hash The given hash table.
172 * @param key The key.
173 * @param value The value.
174 * @return @c TRUE if successful, @c FALSE if not.
175 * @ingroup Ecore_Data_Hash_ADT_Data_Group
176 */
177EAPI int
178ecore_hash_set(Ecore_Hash *hash, void *key, void *value)
179{
180 int ret = FALSE;
181 Ecore_Hash_Node *node;
182
183 CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
184
185 node = _ecore_hash_node_get(hash, key);
186 if (node)
187 {
188 if (hash->free_key)
189 hash->free_key(key);
190
191 if (node->value && hash->free_value)
192 hash->free_value(node->value);
193
194 node->value = value;
195 ret = TRUE;
196 }
197 else
198 {
199 node = _ecore_hash_node_new(key, value);
200 if (node)
201 ret = _ecore_hash_node_add(hash, node);
202 }
203
204 return ret;
205}
206
207/**
208 * Sets all key-value pairs from set in the given hash table.
209 * @param hash The given hash table.
210 * @param set The hash table to import.
211 * @return @c TRUE if successful, @c FALSE if not.
212 * @ingroup Ecore_Data_Hash_ADT_Data_Group
213 */
214EAPI int
215ecore_hash_hash_set(Ecore_Hash *hash, Ecore_Hash *set)
216{
217 unsigned int i;
218 Ecore_Hash_Node *node, *old;
219
220 CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
221 CHECK_PARAM_POINTER_RETURN("set", set, FALSE);
222
223 for (i = 0; i < ecore_prime_table[set->size]; i++)
224 {
225 /* Hash into a new list to avoid loops of rehashing the same nodes */
226 while ((old = set->buckets[i]))
227 {
228 set->buckets[i] = old->next;
229 old->next = NULL;
230 node = _ecore_hash_node_get(hash, old->key);
231 if (node)
232 {
233 /* This key already exists. Delete the old and add the new
234 * value */
235 if (hash->free_key)
236 hash->free_key(node->key);
237
238 if (hash->free_value)
239 hash->free_key(node->value);
240
241 node->key = old->key;
242 node->value = old->value;
243 free(old);
244 }
245 else
246 _ecore_hash_node_add(hash, old);
247 }
248 }
249 FREE(set->buckets);
250 ecore_hash_init(set, set->hash_func, set->compare);
251 return TRUE;
252}
253
254/**
255 * Frees the hash table and the data contained inside it.
256 * @param hash The hash table to destroy.
257 * @return @c TRUE on success, @c FALSE on error.
258 * @ingroup Ecore_Data_Hash_ADT_Destruction_Group
259 */
260EAPI void
261ecore_hash_destroy(Ecore_Hash *hash)
262{
263 unsigned int i = 0;
264
265 CHECK_PARAM_POINTER("hash", hash);
266
267 if (hash->buckets)
268 {
269 while (i < ecore_prime_table[hash->size])
270 {
271 if (hash->buckets[i])
272 {
273 Ecore_Hash_Node *bucket;
274
275 /*
276 * Remove the bucket list to avoid possible recursion
277 * on the free callbacks.
278 */
279 bucket = hash->buckets[i];
280 hash->buckets[i] = NULL;
281 _ecore_hash_bucket_destroy(bucket,
282 hash->free_key,
283 hash->free_value);
284 }
285
286 i++;
287 }
288
289 FREE(hash->buckets);
290 }
291
292 FREE(hash);
293
294 return;
295}
296
297/**
298 * @defgroup Ecore_Data_Hash_ADT_Traverse_Group Hash Traverse Functions
299 *
300 * Functions that iterate through hash tables.
301 */
302
303/**
304 * Counts the number of nodes in a hash table.
305 * @param hash The hash table to count current nodes.
306 * @return The number of nodes in the hash.
307 * @ingroup Ecore_Data_Hash_ADT_Destruction_Group
308 */
309EAPI int
310ecore_hash_count(Ecore_Hash *hash)
311{
312 CHECK_PARAM_POINTER_RETURN("hash", hash, 0);
313
314 return hash->nodes;
315}
316
317/**
318 * Runs the @p for_each_func function on each entry in the given hash.
319 * @param hash The given hash.
320 * @param for_each_func The function that each entry is passed to.
321 * @param user_data a pointer passed to calls of for_each_func
322 * @return TRUE on success, FALSE otherwise.
323 * @ingroup Ecore_Data_Hash_ADT_Traverse_Group
324 */
325EAPI int
326ecore_hash_for_each_node(Ecore_Hash *hash,
327 Ecore_For_Each for_each_func,
328 void *user_data)
329{
330 unsigned int i = 0;
331
332 CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
333 CHECK_PARAM_POINTER_RETURN("for_each_func", for_each_func, FALSE);
334
335 while (i < ecore_prime_table[hash->size])
336 {
337 if (hash->buckets[i])
338 {
339 Ecore_Hash_Node *node;
340
341 for (node = hash->buckets[i]; node; node = node->next)
342 {
343 for_each_func(node, user_data);
344 }
345 }
346
347 i++;
348 }
349
350 return TRUE;
351}
352
353/**
354 * Retrieves an ecore_list of all keys in the given hash.
355 * @param hash The given hash.
356 * @return new ecore_list on success, NULL otherwise
357 * @ingroup Ecore_Data_Hash_ADT_Traverse_Group
358 */
359EAPI Ecore_List *
360ecore_hash_keys(Ecore_Hash *hash)
361{
362 unsigned int i = 0;
363 Ecore_List *keys;
364
365 CHECK_PARAM_POINTER_RETURN("hash", hash, NULL);
366
367 keys = ecore_list_new();
368 while (i < ecore_prime_table[hash->size])
369 {
370 if (hash->buckets[i])
371 {
372 Ecore_Hash_Node *node;
373
374 for (node = hash->buckets[i]; node; node = node->next)
375 {
376 ecore_list_append(keys, node->key);
377 }
378 }
379
380 i++;
381 }
382 ecore_list_first_goto(keys);
383
384 return keys;
385}
386
387/**
388 * Prints the distribution of the given hash table for graphing.
389 * @param hash The given hash table.
390 */
391EAPI void
392ecore_hash_dump_graph(Ecore_Hash *hash)
393{
394 unsigned int i;
395
396 for (i = 0; i < ecore_prime_table[hash->size]; i++)
397 if (hash->buckets[i])
398 {
399 int n = 0;
400 Ecore_Hash_Node *node;
401 for (node = hash->buckets[i]; node; node = node->next)
402 n++;
403 printf("%d\t%u", i, n);
404 }
405 else
406 printf("%d\t0", i);
407
408}
409
410/**
411 * Prints the distribution of the given hash table for graphing.
412 * @param hash The given hash table.
413 */
414EAPI void
415ecore_hash_dump_stats(Ecore_Hash *hash)
416{
417 unsigned int i;
418 double variance, sum_n_2 = 0, sum_n = 0;
419
420 for (i = 0; i < ecore_prime_table[hash->size]; i++)
421 {
422 if (hash->buckets[i])
423 {
424 int n = 0;
425 Ecore_Hash_Node *node;
426 for (node = hash->buckets[i]; node; node = node->next)
427 n++;
428 sum_n_2 += ((double)n * (double)n);
429 sum_n += (double)n;
430 }
431 }
432 variance = (sum_n_2 - ((sum_n * sum_n) / (double)i)) / (double)i;
433 printf("Average length: %f\n\tvariance^2: %f", (sum_n / (double)i),
434 variance);
435}
436
437static int
438_ecore_hash_bucket_destroy(Ecore_Hash_Node *list,
439 Ecore_Free_Cb keyd,
440 Ecore_Free_Cb valued)
441{
442 Ecore_Hash_Node *node;
443
444 CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
445
446 for (node = list; node; node = list)
447 {
448 list = list->next;
449 _ecore_hash_node_destroy(node, keyd, valued);
450 }
451
452 return TRUE;
453}
454
455/*
456 * @brief Add the node to the hash table
457 * @param hash: the hash table to add the key
458 * @param node: the node to add to the hash table
459 * @return Returns FALSE on error, TRUE on success
460 */
461static int
462_ecore_hash_node_add(Ecore_Hash *hash, Ecore_Hash_Node *node)
463{
464 unsigned long hash_val;
465
466 CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
467 CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
468
469 /* Check to see if the hash needs to be resized */
470 if (ECORE_HASH_INCREASE(hash))
471 _ecore_hash_increase(hash);
472
473 /* Compute the position in the table */
474 if (!hash->hash_func)
475 hash_val = (unsigned long)node->key % ecore_prime_table[hash->size];
476 else
477 hash_val = ECORE_COMPUTE_HASH(hash, node->key);
478
479 /* Prepend the node to the list at the index position */
480 node->next = hash->buckets[hash_val];
481 hash->buckets[hash_val] = node;
482 hash->nodes++;
483
484 return TRUE;
485}
486
487/**
488 * Retrieves the value associated with the given key from the given hash
489 * table.
490 * @param hash The given hash table.
491 * @param key The key to search for.
492 * @return The value corresponding to key on success, @c NULL otherwise.
493 * @ingroup Ecore_Data_Hash_ADT_Data_Group
494 */
495EAPI void *
496ecore_hash_get(Ecore_Hash *hash, const void *key)
497{
498 void *data;
499 Ecore_Hash_Node *node;
500
501 CHECK_PARAM_POINTER_RETURN("hash", hash, NULL);
502
503 node = _ecore_hash_node_get(hash, key);
504 if (!node)
505 return NULL;
506
507 data = node->value;
508
509 return data;
510}
511
512/**
513 * Removes the value associated with the given key in the given hash
514 * table.
515 * @param hash The given hash table.
516 * @param key The key to search for.
517 * @return The value corresponding to the key on success. @c NULL is
518 * returned if there is an error.
519 * @ingroup Ecore_Data_Hash_ADT_Data_Group
520 */
521EAPI void *
522ecore_hash_remove(Ecore_Hash *hash, const void *key)
523{
524 Ecore_Hash_Node *node = NULL;
525 Ecore_Hash_Node *list;
526 unsigned long hash_val;
527 void *ret = NULL;
528
529 CHECK_PARAM_POINTER_RETURN("hash", hash, NULL);
530
531 /* Compute the position in the table */
532 if (!hash->hash_func)
533 hash_val = (unsigned long )key % ecore_prime_table[hash->size];
534 else
535 hash_val = ECORE_COMPUTE_HASH(hash, key);
536
537 /*
538 * If their is a list that could possibly hold the key/value pair
539 * traverse it and remove the hash node.
540 */
541 if (hash->buckets[hash_val])
542 {
543 list = hash->buckets[hash_val];
544
545 /*
546 * Traverse the list to find the specified key
547 */
548 node = list;
549 if (hash->compare)
550 while ((node) && (hash->compare(node->key, key) != 0))
551 {
552 list = node;
553 node = node->next;
554 }
555 else
556 while ((node) && (node->key != key))
557 {
558 list = node;
559 node = node->next;
560 }
561
562 /*
563 * Remove the node with the matching key and free it's memory
564 */
565 if (node)
566 {
567 if (list == node)
568 hash->buckets[hash_val] = node->next;
569 else
570 list->next = node->next;
571
572 ret = node->value;
573 node->value = NULL;
574 _ecore_hash_node_destroy(node, hash->free_key, NULL);
575 hash->nodes--;
576 }
577 }
578
579 if (ECORE_HASH_REDUCE(hash))
580 _ecore_hash_decrease(hash);
581
582 return ret;
583}
584
585/**
586 * Retrieves the first value that matches
587 * table.
588 * @param hash The given hash table.
589 * @param key The key to search for.
590 * @return The value corresponding to key on success, @c NULL otherwise.
591 * @ingroup Ecore_Data_Hash_ADT_Data_Group
592 */
593EAPI void *
594ecore_hash_find(Ecore_Hash *hash, Ecore_Compare_Cb compare, const void *value)
595{
596 unsigned int i = 0;
597
598 CHECK_PARAM_POINTER_RETURN("hash", hash, NULL);
599 CHECK_PARAM_POINTER_RETURN("compare", compare, NULL);
600 CHECK_PARAM_POINTER_RETURN("value", value, NULL);
601
602 while (i < ecore_prime_table[hash->size])
603 {
604 if (hash->buckets[i])
605 {
606 Ecore_Hash_Node *node;
607
608 for (node = hash->buckets[i]; node; node = node->next)
609 {
610 if (!compare(node->value, value))
611 return node->value;
612 }
613 }
614
615 i++;
616 }
617
618 return NULL;
619}
620
621/*
622 * @brief Retrieve the node associated with key
623 * @param hash: the hash table to search for the key
624 * @param key: the key to search for in the hash table
625 * @return Returns NULL on error, node corresponding to key on success
626 */
627static Ecore_Hash_Node *
628_ecore_hash_node_get(Ecore_Hash *hash, const void *key)
629{
630 unsigned long hash_val;
631 Ecore_Hash_Node *node = NULL;
632
633 CHECK_PARAM_POINTER_RETURN("hash", hash, NULL);
634
635 if (!hash->buckets)
636 return NULL;
637
638 /* Compute the position in the table */
639 if (!hash->hash_func)
640 hash_val = (unsigned long)key % ecore_prime_table[hash->size];
641 else
642 hash_val = ECORE_COMPUTE_HASH(hash, key);
643
644 /* Grab the bucket at the specified position */
645 if (hash->buckets[hash_val])
646 {
647 node = _ecore_hash_bucket_get(hash, hash->buckets[hash_val], key);
648 /*
649 * Move matched node to the front of the list as it's likely
650 * to be searched for again soon.
651 */
652 if (node && node != hash->buckets[hash_val])
653 {
654 node->next = hash->buckets[hash_val];
655 hash->buckets[hash_val] = node;
656 }
657 }
658
659 return node;
660}
661
662/*
663 * @brief Search the hash bucket for a specified key
664 * @param hash: the hash table to retrieve the comparison function
665 * @param bucket: the list to search for the key
666 * @param key: the key to search for in the list
667 * @return Returns NULL on error or not found, the found node on success
668 */
669static inline Ecore_Hash_Node *
670_ecore_hash_bucket_get(Ecore_Hash *hash,
671 Ecore_Hash_Node *bucket,
672 const void *key)
673{
674 Ecore_Hash_Node *prev = NULL;
675 Ecore_Hash_Node *node = NULL;
676
677 /*
678 * Traverse the list to find the desired node, if the node is in the
679 * list, then return the node.
680 */
681 if (hash->compare)
682 for (node = bucket; node; node = node->next)
683 {
684 if (hash->compare(node->key, key) == 0)
685 break;
686
687 prev = node;
688 }
689 else
690 for (node = bucket; node; node = node->next)
691 {
692 if (node->key == key)
693 break;
694
695 prev = node;
696 }
697
698 /*
699 * Remove node from the list to replace it at the beginning.
700 */
701 if (node && prev)
702 {
703 prev->next = node->next;
704 node->next = NULL;
705 }
706
707 return node;
708}
709
710/*
711 * @brief Increase the size of the hash table by approx. 2 * current size
712 * @param hash: the hash table to increase the size of
713 * @return Returns TRUE on success, FALSE on error
714 */
715static int
716_ecore_hash_increase(Ecore_Hash *hash)
717{
718 void *old;
719
720 CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
721
722 /* Max size reached so return FALSE */
723 if ((ecore_prime_table[hash->size] == PRIME_MAX) ||
724 (hash->size == PRIME_TABLE_MAX))
725 return FALSE;
726
727 /*
728 * Increase the size of the hash and save a pointer to the old data
729 */
730 hash->size++;
731 old = hash->buckets;
732
733 /*
734 * Allocate a new bucket area, of the new larger size
735 */
736 hash->buckets =
737 calloc(ecore_prime_table[hash->size], sizeof(Ecore_Hash_Node *));
738
739 /*
740 * Make sure the allocation succeeded, if not replace the old data and
741 * return a failure.
742 */
743 if (!hash->buckets)
744 {
745 hash->buckets = old;
746 hash->size--;
747 return FALSE;
748 }
749
750 hash->nodes = 0;
751
752 /*
753 * Now move all of the old data into the new bucket area
754 */
755 if (_ecore_hash_rehash(hash, old, hash->size - 1))
756 {
757 FREE(old);
758 return TRUE;
759 }
760
761 /*
762 * Free the old buckets regardless of success.
763 */
764 FREE(old);
765
766 return FALSE;
767}
768
769/*
770 * @brief Decrease the size of the hash table by < 1/2 * current size
771 * @param hash: the hash table to decrease the size of
772 * @return Returns TRUE on success, FALSE on error
773 */
774static int
775_ecore_hash_decrease(Ecore_Hash *hash)
776{
777 Ecore_Hash_Node **old;
778
779 CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
780
781 if (ecore_prime_table[hash->size] == PRIME_MIN)
782 return FALSE;
783
784 /*
785 * Decrease the hash size and store a pointer to the old data
786 */
787 hash->size--;
788 old = hash->buckets;
789
790 /*
791 * Allocate a new area to store the data
792 */
793 hash->buckets = (Ecore_Hash_Node **)calloc(ecore_prime_table[hash->size],
794 sizeof(Ecore_Hash_Node *));
795
796 /*
797 * Make sure allocation succeeded otherwise rreturn to the previous
798 * state
799 */
800 if (!hash->buckets)
801 {
802 hash->buckets = old;
803 hash->size++;
804 return FALSE;
805 }
806
807 hash->nodes = 0;
808
809 if (_ecore_hash_rehash(hash, old, hash->size + 1))
810 {
811 FREE(old);
812 return TRUE;
813 }
814
815 return FALSE;
816}
817
818/*
819 * @brief Rehash the nodes of a table into the hash table
820 * @param hash: the hash to place the nodes of the table
821 * @param table: the table to remove the nodes from and place in hash
822 * @return Returns TRUE on success, FALSE on error
823 */
824static inline int
825_ecore_hash_rehash(Ecore_Hash *hash, Ecore_Hash_Node **old_table, int old_size)
826{
827 unsigned int i;
828 Ecore_Hash_Node *old;
829
830 CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
831 CHECK_PARAM_POINTER_RETURN("old_table", old_table, FALSE);
832
833 for (i = 0; i < ecore_prime_table[old_size]; i++)
834 {
835 /* Hash into a new list to avoid loops of rehashing the same nodes */
836 while ((old = old_table[i]))
837 {
838 old_table[i] = old->next;
839 old->next = NULL;
840 _ecore_hash_node_add(hash, old);
841 }
842 }
843
844 return TRUE;
845}
846
847/*
848 * @brief Create a new hash node for key and value storage
849 * @param key: the key for this node
850 * @param value: the value that the key references
851 * @return Returns NULL on error, a new hash node on success
852 */
853static Ecore_Hash_Node *
854_ecore_hash_node_new(void *key, void *value)
855{
856 Ecore_Hash_Node *node;
857
858 node = (Ecore_Hash_Node *)malloc(sizeof(Ecore_Hash_Node));
859 if (!node)
860 return NULL;
861
862 if (!_ecore_hash_node_init(node, key, value))
863 {
864 FREE(node);
865 return NULL;
866 }
867
868 return node;
869}
870
871/*
872 * @brief Initialize a hash node to some sane default values
873 * @param node: the node to set the values
874 * @param key: the key to reference this node
875 * @param value: the value that key refers to
876 * @return Returns TRUE on success, FALSE on error
877 */
878static int
879_ecore_hash_node_init(Ecore_Hash_Node *node, void *key, void *value)
880{
881 CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
882
883 node->key = key;
884 node->value = value;
885
886 return TRUE;
887}
888
889/*
890 * @brief Destroy a node and call the specified callbacks to free data
891 * @param node: the node to be destroyed
892 * @param keyd: the function to free the key
893 * @param valued: the function to free the value
894 * @return Returns TRUE on success, FALSE on error
895 */
896static int
897_ecore_hash_node_destroy(Ecore_Hash_Node *node,
898 Ecore_Free_Cb keyd,
899 Ecore_Free_Cb valued)
900{
901 CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
902
903 if (keyd)
904 keyd(node->key);
905
906 if (valued)
907 valued(node->value);
908
909 FREE(node);
910
911 return TRUE;
912}
913
914int
915ecore_str_compare(const void *key1, const void *key2)
916{
917 const char *k1, *k2;
918
919 if (!key1 || !key2)
920 return ecore_direct_compare(key1, key2);
921 else if (key1 == key2)
922 return 0;
923
924 k1 = key1;
925 k2 = key2;
926
927 return strcmp(k1, k2);
928}
929
930unsigned int
931ecore_str_hash(const void *key)
932{
933 int i;
934 unsigned int mask;
935 unsigned int value = 0;
936 const char *k = key;
937
938 if (!k)
939 return 0;
940
941 mask = (sizeof(unsigned int) * 8) - 1;
942
943 for (i = 0; k[i] != '\0'; i++)
944 {
945 value ^= ((unsigned int)k[i] << ((i * 5) & mask));
946 }
947
948 return value;
949}
diff --git a/src/tests/ecore_list.c b/src/tests/ecore_list.c
new file mode 100644
index 0000000..7da4417
--- /dev/null
+++ b/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 */
16static void * _ecore_list_current(Ecore_List *list);
17
18/* Adding functions */
19static int _ecore_list_insert(Ecore_List *list,
20 Ecore_List_Node *node);
21static int _ecore_list_append_0(Ecore_List *list,
22 Ecore_List_Node *node);
23static int _ecore_list_prepend_0(Ecore_List *list,
24 Ecore_List_Node *node);
25
26/* Remove functions */
27static void * _ecore_list_remove_0(Ecore_List *list);
28static void * _ecore_list_first_remove(Ecore_List *list);
29static void * _ecore_list_last_remove(Ecore_List *list);
30
31/* Basic traversal functions */
32static void * _ecore_list_next(Ecore_List *list);
33static void * _ecore_list_last_goto(Ecore_List *list);
34static void * _ecore_list_first_goto(Ecore_List *list);
35static void * _ecore_list_goto(Ecore_List *list, const void *data);
36static void * _ecore_list_index_goto(Ecore_List *list, int idx);
37
38/* Iterative functions */
39static int _ecore_list_for_each(Ecore_List *list,
40 Ecore_For_Each function,
41 void *user_data);
42static void * _ecore_list_find(Ecore_List *list,
43 Ecore_Compare_Cb function,
44 const void *user_data);
45
46/* Sorting functions */
47static Ecore_List_Node *_ecore_list_node_mergesort(Ecore_List_Node *first,
48 int n,
49 Ecore_Compare_Cb compare,
50 int order);
51static Ecore_List_Node *_ecore_list_node_merge(Ecore_List_Node *first,
52 Ecore_List_Node *second,
53 Ecore_Compare_Cb compare,
54 int order);
55static Ecore_List_Node *_ecore_dlist_node_mergesort(Ecore_List_Node *first,
56 int n,
57 Ecore_Compare_Cb compare,
58 int order);
59static 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 */
65static void *_ecore_dlist_previous(Ecore_DList *list);
66static void *_ecore_dlist_first_remove(Ecore_DList *list);
67static 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 */
80EAPI Ecore_List *
81ecore_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 */
104EAPI int
105ecore_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 */
119EAPI void
120ecore_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 */
143EAPI int
144ecore_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 */
158EAPI int
159ecore_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 */
176EAPI int
177ecore_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 */
193EAPI int
194ecore_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 */
218EAPI inline int
219ecore_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 */
235static 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 */
265EAPI inline int
266ecore_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 */
282static 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 */
307EAPI inline int
308ecore_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 */
324static 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
366EAPI int
367ecore_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 */
400EAPI int
401ecore_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 */
440EAPI inline void *
441ecore_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 */
453static 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 */
497EAPI int
498ecore_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 */
518EAPI inline void *
519ecore_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 */
531static 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 */
570EAPI inline void *
571ecore_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 */
583static 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 */
630EAPI inline void *
631ecore_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 */
644static 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 */
683EAPI inline void *
684ecore_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 */
696static 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 */
737EAPI inline void *
738ecore_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 */
750static 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 */
768EAPI inline void *
769ecore_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 */
781static 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 */
798EAPI inline void *
799ecore_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 */
813EAPI inline void *
814ecore_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 */
831EAPI inline void *
832ecore_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 */
845static 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 */
864EAPI inline void *
865ecore_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 */
877static 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 */
905EAPI int
906ecore_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 */
923EAPI int
924ecore_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 */
936static 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 */
958EAPI void *
959ecore_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 */
969static 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 */
1002EAPI int
1003ecore_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 */
1029EAPI int
1030ecore_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 */
1065EAPI void
1066ecore_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 */
1098static 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 */
1141static 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 */
1198EAPI int
1199ecore_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 */
1237EAPI int
1238ecore_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 */
1260EAPI Ecore_List_Node *
1261ecore_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 */
1283EAPI int
1284ecore_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 */
1308EAPI Ecore_DList *
1309ecore_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 */
1332EAPI int
1333ecore_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 */
1347EAPI void
1348ecore_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 */
1371EAPI int
1372ecore_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 */
1384EAPI int
1385ecore_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 */
1397EAPI inline int
1398ecore_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 */
1418EAPI int
1419ecore_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 */
1445EAPI int
1446ecore_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 */
1472EAPI int
1473ecore_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 */
1516EAPI int
1517ecore_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 */
1551EAPI int
1552ecore_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 */
1593EAPI void *
1594ecore_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 */
1620EAPI void *
1621ecore_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 */
1639EAPI int
1640ecore_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
1656static 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 */
1677EAPI void *
1678ecore_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 */
1715EAPI void *
1716ecore_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 */
1729static 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 */
1769EAPI void *
1770ecore_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 */
1787EAPI void *
1788ecore_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 */
1804EAPI void *
1805ecore_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 */
1821EAPI void *
1822ecore_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 */
1836EAPI void *
1837ecore_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 */
1851EAPI void *
1852ecore_dlist_previous(Ecore_DList *list)
1853{
1854 void *data;
1855
1856 data = _ecore_dlist_previous(list);
1857
1858 return data;
1859}
1860
1861static 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 */
1892EAPI int
1893ecore_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 */
1914EAPI int
1915ecore_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 */
1941EAPI int
1942ecore_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 */
1977EAPI void
1978ecore_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 */