array: Add array_bsearch function

diff --git a/src/libstrongswan/collections/array.c b/src/libstrongswan/collections/array.c
index f6f9cf4..ed0d12e 100644 (file)
--- a/src/libstrongswan/collections/array.c
+++ b/src/libstrongswan/collections/array.c
@@ -419,6 +419,56 @@ void array_sort(array_t *array, int (*cmp)(const void*,const void*,void*),
        }
 }
 
        }
 }
 

+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)
 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 c9c5285..c6b6fcc 100644 (file)
--- a/src/libstrongswan/collections/array.h
+++ b/src/libstrongswan/collections/array.h
@@ -186,6 +186,31 @@ void array_sort(array_t *array, int (*cmp)(const void*,const void*,void*),
                                void *user);
 
 /**
                                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
  * 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 4295f0e..ba2aff4 100644 (file)
--- a/src/libstrongswan/tests/suites/test_array.c
+++ b/src/libstrongswan/tests/suites/test_array.c
@@ -359,6 +359,67 @@ START_TEST(test_sort_ptr)
 }
 END_TEST
 
 }
 END_TEST
 

+static int comp_search_obj(const void *a, const void *b)
+{
+       return *(int*)a - *(int*)b;
+}
+
+START_TEST(test_bsearch_obj)
+{
+       array_t *array;
+       int x[] = { 3, 2, 1 };
+       int k, v;
+
+       array = array_create(sizeof(x[0]), 0);
+       array_insert(array, ARRAY_TAIL, &x[0]);
+       array_insert(array, ARRAY_TAIL, &x[1]);
+       array_insert(array, ARRAY_TAIL, &x[2]);
+
+       array_sort(array, (void*)comp_search_obj, NULL);
+
+       k = 0;
+       ck_assert_int_eq(array_bsearch(array, &k, comp_search_obj, &v), -1);
+       for (k = 1; k < 4; k++)
+       {
+               ck_assert_int_eq(array_bsearch(array, &k, comp_search_obj, &v), k-1);
+               ck_assert_int_eq(v, k);
+       }
+       k = 4;
+       ck_assert_int_eq(array_bsearch(array, &k, comp_search_obj, &v), -1);
+       array_destroy(array);
+}
+END_TEST
+
+static int comp_search_ptr(const void *a, const void *b)
+{
+       return strcmp(a, b);
+}
+
+START_TEST(test_bsearch_ptr)
+{
+       array_t *array;
+       char *x[] = {"c", "b", "a"};
+       char *v;
+
+       array = array_create(0, 0);
+       array_insert(array, ARRAY_TAIL, x[0]);
+       array_insert(array, ARRAY_TAIL, x[1]);
+       array_insert(array, ARRAY_TAIL, x[2]);
+
+       array_sort(array, (void*)comp_search_ptr, NULL);
+
+       ck_assert_int_eq(array_bsearch(array, "abc", comp_search_ptr, &v), -1);
+       ck_assert_int_eq(array_bsearch(array, "a", comp_search_ptr, &v), 0);
+       ck_assert_str_eq(v, "a");
+       ck_assert_int_eq(array_bsearch(array, "b", comp_search_ptr, &v), 1);
+       ck_assert_str_eq(v, "b");
+       ck_assert_int_eq(array_bsearch(array, "c", comp_search_ptr, &v), 2);
+       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;
 static void invoke(void *data, int idx, void *user)
 {
        int *y = user, *x = data;


@@ -454,6 +515,11 @@ Suite *array_suite_create()
        tcase_add_test(tc, test_sort_ptr);
        suite_add_tcase(s, tc);
 
        tcase_add_test(tc, test_sort_ptr);
        suite_add_tcase(s, tc);
 

+       tc = tcase_create("bsearch");
+       tcase_add_test(tc, test_bsearch_obj);
+       tcase_add_test(tc, test_bsearch_ptr);
+       suite_add_tcase(s, tc);
+

        tc = tcase_create("invoke");
        tcase_add_test(tc, test_invoke);
        suite_add_tcase(s, tc);
        tc = tcase_create("invoke");
        tcase_add_test(tc, test_invoke);
        suite_add_tcase(s, tc);