Imported Upstream version 5.1.2

2 files changed, 222 insertions, 2 deletions

diff --git a/src/libstrongswan/collections/array.c b/src/libstrongswan/collections/array.c
index 387e2a57d..314e8e916 100644
--- 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,8 +16,15 @@
  * for more details.
  */
 
+#define _GNU_SOURCE /* for qsort_r() */
+#include <stdlib.h>
+
 #include "array.h"
 
+#ifndef HAVE_QSORT_R
+#include <threading/thread_value.h>
+#endif
+
 /**
  * Data is an allocated block, with potentially unused head and tail:
  *
@@ -43,6 +53,11 @@ struct array_t {
 	void *data;
 };
 
+#ifndef HAVE_QSORT_R
+	/* store data to replicate qsort_r in thread local storage */
+	static thread_value_t *sort_data;
+#endif
+
 /** maximum number of unused head/tail elements before cleanup */
 #define ARRAY_MAX_UNUSED 32
 
@@ -314,7 +329,7 @@ void array_insert(array_t *array, int idx, void *data)
 	}
 }
 
-bool array_remove(array_t *array, int idx, void *data)
+bool array_get(array_t *array, int idx, void *data)
 {
 	if (!array)
 	{
@@ -337,12 +352,25 @@ bool array_remove(array_t *array, int idx, void *data)
 		memcpy(data, array->data + get_size(array, array->head + idx),
 			   get_size(array, 1));
 	}
+	return TRUE;
+}
+
+bool array_remove(array_t *array, int idx, void *data)
+{
+	if (!array_get(array, idx, data))
+	{
+		return FALSE;
+	}
 	if (idx > array_count(array) / 2)
 	{
 		remove_tail(array, idx);
 	}
 	else
 	{
+		if (idx < 0)
+		{
+			idx = array_count(array) - 1;
+		}
 		remove_head(array, idx);
 	}
 	if (array->head + array->tail > ARRAY_MAX_UNUSED)
@@ -352,6 +380,113 @@ 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)
+#elif defined(HAVE_QSORT_R_BSD)
+static int compare_elements(void *arg, const void *a, const void *b)
+#else /* !HAVE_QSORT_R */
+static int compare_elements(const void *a, const void *b)
+#endif
+{
+#ifdef HAVE_QSORT_R
+	sort_data_t *data = (sort_data_t*)arg;
+#else
+	sort_data_t *data = sort_data->get(sort_data);
+#endif
+
+	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);
+#elif defined(HAVE_QSORT_R_BSD)
+		qsort_r(start, array->count, get_size(array, 1), &data,
+				compare_elements);
+#else /* !HAVE_QSORT_R */
+		sort_data->set(sort_data, &data);
+		qsort(start, array->count, get_size(array, 1), compare_elements);
+#endif
+	}
+}
+
+typedef struct {
+	/** the array */
+	array_t *array;
+	/** the key */
+	const void *key;
+	/** comparison function */
+	int (*cmp)(const void*,const void*);
+} bsearch_data_t;
+
+static int search_elements(const void *a, const void *b)
+{
+	bsearch_data_t *data = (bsearch_data_t*)a;
+
+	if (data->array->esize)
+	{
+		return data->cmp(data->key, b);
+	}
+	return data->cmp(data->key, *(void**)b);
+}
+
+int array_bsearch(array_t *array, const void *key,
+				  int (*cmp)(const void*,const void*), void *out)
+{
+	int idx = -1;
+
+	if (array)
+	{
+		bsearch_data_t data = {
+			.array = array,
+			.key = key,
+			.cmp = cmp,
+		};
+		void *start, *item;
+
+		start = array->data + get_size(array, array->head);
+
+		item = bsearch(&data, start, array->count, get_size(array, 1),
+					   search_elements);
+		if (item)
+		{
+			if (out)
+			{
+				memcpy(out, item, get_size(array, 1));
+			}
+			idx = (item - start) / get_size(array, 1);
+		}
+	}
+	return idx;
+}
+
 void array_invoke(array_t *array, array_callback_t cb, void *user)
 {
 	if (array)
@@ -414,3 +549,17 @@ void array_destroy_offset(array_t *array, size_t offset)
 	array_invoke_offset(array, offset);
 	array_destroy(array);
 }
+
+void arrays_init()
+{
+#ifndef HAVE_QSORT_R
+	sort_data =  thread_value_create(NULL);
+#endif
+}
+
+void arrays_deinit()
+{
+#ifndef HAVE_QSORT_R
+	sort_data->destroy(sort_data);
+#endif
+}
diff --git a/src/libstrongswan/collections/array.h b/src/libstrongswan/collections/array.h
index 0dc7b2250..ce702ebfa 100644
--- 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
@@ -140,6 +143,18 @@ void array_insert_create(array_t **array, int idx, void *ptr);
 void array_insert_enumerator(array_t *array, int idx, enumerator_t *enumerator);
 
 /**
+ * Get an element from the array.
+ *
+ * If data is given, the element is copied to that position.
+ *
+ * @param array			array to get element from, or NULL
+ * @param idx			index of the item to get
+ * @param data			data to copy element to, or NULL
+ * @return				TRUE if idx valid and item returned
+ */
+bool array_get(array_t *array, int idx, void *data);
+
+/**
  * Remove an element from the array.
  *
  * If data is given, the element is copied to that position.
@@ -152,6 +167,50 @@ void array_insert_enumerator(array_t *array, int idx, enumerator_t *enumerator);
 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);
+
+/**
+ * Binary search of a sorted array.
+ *
+ * The array should be sorted in ascending order according to the given
+ * comparison function.
+ *
+ * The comparison function must return an integer less than, equal to, or
+ * greater than zero if the first argument (the key) is considered to be
+ * respectively less than, equal to, or greater than the second.
+ *
+ * If there are multiple elements that match the key it is not specified which
+ * element is returned.
+ *
+ * The comparison function receives the key object and a pointer to an array
+ * element (esize != 0) or an actual pointer (esize = 0).
+ *
+ * @param array			array to search, or NULL
+ * @param key			key to search for
+ * @param cmp			comparison function
+ * @param data			data to copy element to, or NULL
+ * @return				index of the element if found, -1 if not
+ */
+int array_bsearch(array_t *array, const void *key,
+				  int (*cmp)(const void*,const void*), void *data);
+
+/**
  * Invoke a callback for all array members.
  *
  * @param array			array to traverse, or NULL
@@ -192,4 +251,16 @@ void array_destroy_function(array_t *array, array_callback_t cb, void *user);
  */
 void array_destroy_offset(array_t *array, size_t offset);
 
+
+/**
+ * Required on some platforms to initialize thread local value to implement
+ * array_sort().
+ */
+void arrays_init();
+
+/**
+ * Destroys the thread local value if required.
+ */
+void arrays_deinit();
+
 #endif /** ARRAY_H_ @}*/