array: Add an insert/create function for value based arrays

[people/ms/strongswan.git] / src / libstrongswan / collections / array.c

diff --git a/src/libstrongswan/collections/array.c b/src/libstrongswan/collections/array.c
index d92eaacfe48fa51a6799ac8cf23e2fe0041bbe51..a45a68aafeb3a35659e070bbd69dd5cee3b498ab 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,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,13 +53,18 @@ 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
 
 /**
  * Get the actual size of a number of elements
  */
-static size_t get_size(array_t *array, int num)
+static size_t get_size(array_t *array, u_int32_t num)
 {
        if (array->esize)
        {
@@ -126,7 +141,7 @@ static void remove_tail(array_t *array, int idx)
        /* move all items after idx one down */
        memmove(array->data + get_size(array, idx + array->head),
                        array->data + get_size(array, idx + array->head + 1),
-                       get_size(array, array->count - idx));
+                       get_size(array, array->count - 1 - idx));
        array->count--;
        array->tail++;
 }
@@ -153,7 +168,7 @@ array_t *array_create(u_int esize, u_int8_t reserve)
        );
        if (array->tail)
        {
-               array->data = malloc(array->tail * array->esize);
+               array->data = malloc(get_size(array, array->tail));
        }
        return array;
 }
@@ -262,6 +277,16 @@ void array_insert_create(array_t **array, int idx, void *ptr)
        array_insert(*array, idx, ptr);
 }
 
+void array_insert_create_value(array_t **array, u_int esize,
+                                                          int idx, void *val)
+{
+       if (*array == NULL)
+       {
+               *array = array_create(esize, 0);
+       }
+       array_insert(*array, idx, val);
+}
+
 void array_insert_enumerator(array_t *array, int idx, enumerator_t *enumerator)
 {
        void *ptr;
@@ -314,7 +339,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,6 +362,19 @@ 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 < 0)
+       {
+               idx = array_count(array) - 1;
+       }
        if (idx > array_count(array) / 2)
        {
                remove_tail(array, idx);
@@ -352,6 +390,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 +559,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
+}