aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJérémy Zurcher <jeremy@asynk.ch>2013-03-20 11:45:57 +0100
committerChris Michael <cp.michael@samsung.com>2013-03-26 08:53:33 +0000
commit12491248113599ed6643454ec7f8b920fb04f86e (patch)
tree3a534013d93f25ddb03eb75314018e5531cccc6a
parentoh so minor buglet - interpolate border scale by a sa float (in fixed (diff)
downloadefl-12491248113599ed6643454ec7f8b920fb04f86e.tar.gz
TES
Conflicts: src/lib/eina/eina_list.c src/lib/eina/eina_types.h
-rw-r--r--src/lib/eina/eina_list.c79
-rw-r--r--src/lib/eina/eina_types.h15
-rw-r--r--src/tests/eina/eina_test_list.c57
3 files changed, 151 insertions, 0 deletions
diff --git a/src/lib/eina/eina_list.c b/src/lib/eina/eina_list.c
index 01871b20f8..4e217dd9a6 100644
--- a/src/lib/eina/eina_list.c
+++ b/src/lib/eina/eina_list.c
@@ -1095,6 +1095,85 @@ eina_list_sort(Eina_List *list, unsigned int limit, Eina_Compare_Cb func)
}
EAPI Eina_List *
+eina_list_shuffle(Eina_List *list, Eina_Random_Cb func)
+{
+ unsigned int n, i, j;
+ Eina_List_Accounting *accounting;
+ Eina_List *shuffled_list, *shuffled_last, *li;
+
+ if (!list)
+ return NULL;
+
+ EINA_MAGIC_CHECK_LIST(list, NULL);
+
+ accounting = list->accounting;
+ n = accounting->count;
+ shuffled_list = shuffled_last = NULL;
+
+ if (n == 1)
+ return list;
+
+ while (n > 1)
+ {
+ if (func)
+ i = func(0, (n - 1));
+ else
+ i = (int) ((float)n*rand()/(RAND_MAX+1.0));
+
+ if(i == 0)
+ {
+ li = list;
+ list = list->next;
+ }
+ else if (i == (n - 1) || i == n)
+ {
+ li = accounting->last;
+ accounting->last = li->prev;
+ }
+ else
+ {
+ if (i > (n / 2))
+ for (j = n - 1,
+ li = accounting->last;
+ j!=i;
+ li = li->prev, j--);
+ else
+ for (j = 0,
+ li = list;
+ j!=i;
+ li = li->next, j++);
+
+ li->prev->next = li->next;
+ li->next->prev = li->prev;
+ }
+
+ n--;
+
+ if (shuffled_list == NULL)
+ {
+ li->prev = NULL;
+ shuffled_list = li;
+ shuffled_last = li;
+ }
+ else
+ {
+ shuffled_last->next = li;
+ li->prev = shuffled_last;
+ shuffled_last = li;
+ }
+ }
+
+ list->next = NULL;
+ list->prev = shuffled_last;
+ shuffled_last->next = list;
+
+ accounting->last = list;
+ shuffled_list->accounting = accounting;
+
+ return shuffled_list;
+}
+
+EAPI Eina_List *
eina_list_merge(Eina_List *left, Eina_List *right)
{
unsigned int n_left, n_right;
diff --git a/src/lib/eina/eina_types.h b/src/lib/eina/eina_types.h
index d74d200a32..d37b20f71f 100644
--- a/src/lib/eina/eina_types.h
+++ b/src/lib/eina/eina_types.h
@@ -334,6 +334,21 @@ typedef int (*Eina_Compare_Cb)(const void *data1, const void *data2);
#define EINA_COMPARE_CB(function) ((Eina_Compare_Cb)function)
/**
+ * @typedef Eina_Random_Cb
+ * Function used in shuffling functions. An integer betwen min and max
+ * inclusive must be returned.
+ *
+ * @since 1.8
+ */
+typedef int (*Eina_Random_Cb)(const int min, const int max);
+
+/**
+ * @def EINA_RANDOM_CB
+ * Macro to cast to Eina_Random_Cb.
+ */
+#define EINA_RANDOM_CB(function) ((Eina_Random_Cb)function)
+
+/**
* @typedef Eina_Each_Cb
* A callback type used when iterating over a container.
*/
diff --git a/src/tests/eina/eina_test_list.c b/src/tests/eina/eina_test_list.c
index 0f48688a53..fd11f8996e 100644
--- a/src/tests/eina/eina_test_list.c
+++ b/src/tests/eina/eina_test_list.c
@@ -375,6 +375,62 @@ START_TEST(eina_test_list_split)
}
END_TEST
+static int uicmp(const void *d1, const void *d2)
+{
+ const unsigned int *a = d1;
+ const unsigned int *b = d2;
+
+ if(*a == *b) return 0;
+ if(*a > *b) return 1;
+
+ return -1;
+}
+
+#define SHUFFLE_SZ 100
+#define SHUFFLE_N 100000
+START_TEST(eina_test_shuffle)
+{
+ double d;
+ unsigned int *p;
+ unsigned int i, j;
+ unsigned int n[SHUFFLE_SZ];
+ unsigned int rand_count[SHUFFLE_SZ];
+ Eina_List *list = NULL;
+ Eina_List *item = NULL;
+
+ eina_init();
+
+ for(i = 0; i < SHUFFLE_SZ; i++)
+ {
+ n[i] = i;
+ rand_count[i] = 0;
+ list = eina_list_append(list, &n[i]);
+ }
+
+ for(i = 0; i < SHUFFLE_N; i++)
+ {
+ list = eina_list_shuffle(list, NULL);
+ p = eina_list_nth(list, SHUFFLE_SZ/2);
+ rand_count[*p]++;
+
+ j = 0;
+ list = eina_list_sort(list, 0, (Eina_Compare_Cb)&uicmp);
+ EINA_LIST_FOREACH(list, item, p)
+ fail_if(*p != j++);
+ fail_if(j != SHUFFLE_SZ);
+ }
+
+ d = SHUFFLE_SZ/(float)(SHUFFLE_N);
+ for(i = 0; i < SHUFFLE_SZ; i++)
+ {
+ fail_if(rand_count[i]*d > 1.20f);
+ fail_if(rand_count[i]*d < 0.80f);
+ }
+
+ eina_shutdown();
+}
+END_TEST
+
void
eina_test_list(TCase *tc)
{
@@ -382,4 +438,5 @@ eina_test_list(TCase *tc)
tcase_add_test(tc, eina_test_merge);
tcase_add_test(tc, eina_test_sorted_insert);
tcase_add_test(tc, eina_test_list_split);
+ tcase_add_test(tc, eina_test_shuffle);
}