)]
)
+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)
/*
+ * Copyright (C) 2014 Tobias Brunner
+ * Hochschule fuer Technik Rapperswil
+ *
* Copyright (C) 2013 Martin Willi
* Copyright (C) 2013 revosec AG
*
* for more details.
*/
+#define _GNU_SOURCE /* for qsort_r() */
+#include <stdlib.h>
+
#include "array.h"
/**
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)
/*
+ * Copyright (C) 2014 Tobias Brunner
+ * Hochschule fuer Technik Rapperswil
+ *
* Copyright (C) 2013 Martin Willi
* Copyright (C) 2013 revosec AG
*
* 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
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
/*
+ * Copyright (C) 2014 Tobias Brunner
+ * Hochschule fuer Technik Rapperswil
+ *
* Copyright (C) 2013 Martin Willi
* Copyright (C) 2013 revosec AG
*
}
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;
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);