array: Add array_sort function

diff --git a/configure.ac b/configure.ac
index 10f1e19..649f181 100644 (file)
--- a/configure.ac
+++ b/configure.ac
@@ -494,6 +494,43 @@ AC_CHECK_FUNC(
        )]
 )
 
+AC_CHECK_FUNC(
+       [qsort_r],
+       [
+               AC_DEFINE([HAVE_QSORT_R], [], [have qsort_r()])
+               # set -Werror so that we get an error for "argument ... has
+               # incompatible pointer type" warnings
+               save_CFLAGS="$CFLAGS"
+               CFLAGS="$CFLAGS -Werror"
+               AC_MSG_CHECKING([for GNU-style qsort_r])
+               AC_COMPILE_IFELSE(
+                       [AC_LANG_PROGRAM(
+                               [[#define _GNU_SOURCE
+                                 #include <stdlib.h>
+                                 int cmp (const void *a, const void *b, void *x) { return 0; }]],
+                               [[int arr[] = { 0, 1 };
+                                 qsort_r(arr, 2, sizeof(int), cmp, arr);]])],
+               [AC_MSG_RESULT([yes]);
+                AC_DEFINE([HAVE_QSORT_R_GNU], [], [have GNU-style qsort_r()])],
+               [
+                       AC_MSG_RESULT([no]);
+                       AC_MSG_CHECKING([for BSD-style qsort_r])
+                       AC_COMPILE_IFELSE(
+                               [AC_LANG_PROGRAM(
+                                       [[#include <stdlib.h>
+                                         int cmp (void *x, const void *a, const void *b) { return 0; }]],
+                                       [[int arr[] = { 0, 1 };
+                                         qsort_r(arr, 2, sizeof(int), arr, cmp);]])],
+                       [AC_MSG_RESULT([yes]);
+                        AC_DEFINE([HAVE_QSORT_R_BSD], [], [have BSD-style qsort_r()])],
+                       [AC_MSG_RESULT([no]);
+                        AC_MSG_FAILURE([qsort_r has unknown semantics])])
+               ])
+               CFLAGS="$save_CFLAGS"
+       ],
+       [AC_MSG_FAILURE([qsort_r not found])]
+)
+
 AC_CHECK_FUNCS(prctl mallinfo getpass closefrom getpwnam_r getgrnam_r getpwuid_r)
 AC_CHECK_FUNCS(fmemopen funopen mmap)
 

diff --git a/src/libstrongswan/collections/array.c b/src/libstrongswan/collections/array.c
index d0df23a..f6f9cf4 100644 (file)
--- a/src/libstrongswan/collections/array.c
+++ b/src/libstrongswan/collections/array.c
@@ -1,4 +1,7 @@
 /*
+ * Copyright (C) 2014 Tobias Brunner
+ * Hochschule fuer Technik Rapperswil
+ *
  * Copyright (C) 2013 Martin Willi
  * Copyright (C) 2013 revosec AG
  *
@@ -13,6 +16,9 @@
  * for more details.
  */
 
+#define _GNU_SOURCE /* for qsort_r() */
+#include <stdlib.h>
+
 #include "array.h"
 
 /**
@@ -365,6 +371,54 @@ bool array_remove(array_t *array, int idx, void *data)
        return TRUE;
 }
 
+typedef struct {
+       /** the array */
+       array_t *array;
+       /** comparison function */
+       int (*cmp)(const void*,const void*,void*);
+       /** optional user arg */
+       void *arg;
+} sort_data_t;
+
+#ifdef HAVE_QSORT_R_GNU
+static int compare_elements(const void *a, const void *b, void *arg)
+#else /* HAVE_QSORT_R_BSD */
+static int compare_elements(void *arg, const void *a, const void *b)
+#endif
+{
+       sort_data_t *data = (sort_data_t*)arg;
+
+       if (data->array->esize)
+       {
+               return data->cmp(a, b, data->arg);
+       }
+       return data->cmp(*(void**)a, *(void**)b, data->arg);
+}
+
+void array_sort(array_t *array, int (*cmp)(const void*,const void*,void*),
+                               void *user)
+{
+       if (array)
+       {
+               sort_data_t data = {
+                       .array = array,
+                       .cmp = cmp,
+                       .arg = user,
+               };
+               void *start;
+
+               start = array->data + get_size(array, array->head);
+
+#ifdef HAVE_QSORT_R_GNU
+               qsort_r(start, array->count, get_size(array, 1), compare_elements,
+                               &data);
+#else /* HAVE_QSORT_R_BSD */
+               qsort_r(start, array->count, get_size(array, 1), &data,
+                               compare_elements);
+#endif
+       }
+}
+
 void array_invoke(array_t *array, array_callback_t cb, void *user)
 {
        if (array)

diff --git a/src/libstrongswan/collections/array.h b/src/libstrongswan/collections/array.h
index 6fa151b..c9c5285 100644 (file)
--- a/src/libstrongswan/collections/array.h
+++ b/src/libstrongswan/collections/array.h
@@ -1,4 +1,7 @@
 /*
+ * Copyright (C) 2014 Tobias Brunner
+ * Hochschule fuer Technik Rapperswil
+ *
  * Copyright (C) 2013 Martin Willi
  * Copyright (C) 2013 revosec AG
  *
@@ -87,7 +90,7 @@ void array_compress(array_t *array);
  * The enumerater enumerates directly over the array element (pass a pointer to
  * element types), unless the array is pointer based. If zero is passed as
  * element size during construction, the enumerator enumerates over the
- * deferenced pointer values.
+ * dereferenced pointer values.
  *
  * @param array                        array to create enumerator for, or NULL
  * @return                             enumerator, over elements or pointers
@@ -164,6 +167,25 @@ bool array_get(array_t *array, int idx, void *data);
 bool array_remove(array_t *array, int idx, void *data);
 
 /**
+ * Sort the array.
+ *
+ * The comparison function must return an integer less than, equal to, or
+ * greater than zero if the first argument is considered to be respectively less
+ * than, equal to, or greater than the second.  If two elements compare as
+ * equal, their order in the sorted array is undefined.
+ *
+ * The comparison function receives pointers to the array elements (esize != 0)
+ * or the actual pointers (esize = 0). The third argument is the user data
+ * supplied to this function.
+ *
+ * @param array                        array to sort, or NULL
+ * @param cmp                  comparison function
+ * @param user                 user data to pass to comparison function
+ */
+void array_sort(array_t *array, int (*cmp)(const void*,const void*,void*),
+                               void *user);
+
+/**
  * Invoke a callback for all array members.
  *
  * @param array                        array to traverse, or NULL

diff --git a/src/libstrongswan/tests/suites/test_array.c b/src/libstrongswan/tests/suites/test_array.c
index 198ee96..4295f0e 100644 (file)
--- a/src/libstrongswan/tests/suites/test_array.c
+++ b/src/libstrongswan/tests/suites/test_array.c
@@ -1,4 +1,7 @@
 /*
+ * Copyright (C) 2014 Tobias Brunner
+ * Hochschule fuer Technik Rapperswil
+ *
  * Copyright (C) 2013 Martin Willi
  * Copyright (C) 2013 revosec AG
  *
@@ -274,6 +277,88 @@ START_TEST(test_enumerate)
 }
 END_TEST
 
+static int comp_obj(const void *a, const void *b, void *arg)
+{
+       ck_assert_str_eq(arg, "arg");
+       return *(int*)a - *(int*)b;
+}
+
+START_TEST(test_sort_obj)
+{
+       array_t *array;
+       int x[][3] = {
+               {1, 2, 3},
+               {1, 3, 2},
+               {2, 1, 3},
+               {2, 3, 1},
+               {3, 1, 2},
+               {3, 2, 1},
+       };
+       char *arg = "arg";
+       int i, v;
+
+       for (i = 0; i < countof(x); i++)
+       {
+               array = array_create(sizeof(x[i][0]), 0);
+               array_insert(array, ARRAY_TAIL, &x[i][0]);
+               array_insert(array, ARRAY_TAIL, &x[i][1]);
+               array_insert(array, ARRAY_TAIL, &x[i][2]);
+
+               array_sort(array, comp_obj, arg);
+
+               ck_assert(array_get(array, 0, &v));
+               ck_assert_int_eq(v, 1);
+               ck_assert(array_get(array, 1, &v));
+               ck_assert_int_eq(v, 2);
+               ck_assert(array_get(array, 2, &v));
+               ck_assert_int_eq(v, 3);
+
+               array_destroy(array);
+       }
+}
+END_TEST
+
+static int comp_ptr(const void *a, const void *b, void *arg)
+{
+       ck_assert_str_eq(arg, "arg");
+       return strcmp(a, b);
+}
+
+START_TEST(test_sort_ptr)
+{
+       array_t *array;
+       char *x[][3] = {
+               {"a", "b", "c"},
+               {"a", "c", "b"},
+               {"b", "a", "c"},
+               {"b", "c", "a"},
+               {"c", "a", "b"},
+               {"c", "b", "a"},
+       };
+       char *v, *arg = "arg";
+       int i;
+
+       for (i = 0; i < countof(x); i++)
+       {
+               array = array_create(0, 0);
+               array_insert(array, ARRAY_TAIL, x[i][0]);
+               array_insert(array, ARRAY_TAIL, x[i][1]);
+               array_insert(array, ARRAY_TAIL, x[i][2]);
+
+               array_sort(array, comp_ptr, arg);
+
+               ck_assert(array_get(array, 0, &v));
+               ck_assert_str_eq(v, "a");
+               ck_assert(array_get(array, 1, &v));
+               ck_assert_str_eq(v, "b");
+               ck_assert(array_get(array, 2, &v));
+               ck_assert_str_eq(v, "c");
+
+               array_destroy(array);
+       }
+}
+END_TEST
+
 static void invoke(void *data, int idx, void *user)
 {
        int *y = user, *x = data;
@@ -364,6 +449,11 @@ Suite *array_suite_create()
        tcase_add_test(tc, test_enumerate);
        suite_add_tcase(s, tc);
 
+       tc = tcase_create("sort");
+       tcase_add_test(tc, test_sort_obj);
+       tcase_add_test(tc, test_sort_ptr);
+       suite_add_tcase(s, tc);
+
        tc = tcase_create("invoke");
        tcase_add_test(tc, test_invoke);
        suite_add_tcase(s, tc);