From 15fb7904f4431a6e7c305fd08732458f7f885e7e Mon Sep 17 00:00:00 2001 From: Yves-Alexis Perez Date: Tue, 11 Mar 2014 20:48:48 +0100 Subject: Imported Upstream version 5.1.2 --- src/libstrongswan/collections/array.c | 151 +++++++++++++++++++++++++++++++++- src/libstrongswan/collections/array.h | 73 +++++++++++++++- 2 files changed, 222 insertions(+), 2 deletions(-) (limited to 'src/libstrongswan/collections') 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 + #include "array.h" +#ifndef HAVE_QSORT_R +#include +#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 @@ -139,6 +142,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. * @@ -151,6 +166,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. * @@ -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_ @}*/ -- cgit v1.2.3