commit 258bb8745389844e4a46a0dc3a473bb8a0e0807e
parent 9b9b09b5c0d4685dfd6cb0523849e24dbd0cb6c6
Author: vaplv <vaplv@free.fr>
Date: Tue, 17 Nov 2015 16:00:40 +0100
Add and test the search_lower_bound algorithm
Find for the first element in a array in ascending order, that is *not*
less than a submitted value.
Diffstat:
3 files changed, 136 insertions(+), 0 deletions(-)
diff --git a/cmake/CMakeLists.txt b/cmake/CMakeLists.txt
@@ -63,6 +63,7 @@ endif(CMAKE_USE_PTHREADS_INIT)
set(RSYS_FILES_INC
io_c99.h)
set(RSYS_FILES_INC_API
+ algorithm.h
binary_heap.h
clock_time.h
condition.h
@@ -148,6 +149,7 @@ if(NOT NO_TEST)
set(MATH_LIB m)
endif(CMAKE_COMPILER_IS_GNUCC)
+ new_test(test_algorithm)
new_test(test_atomic)
new_test(test_binary_heap rsys)
new_test(test_cstr rsys)
diff --git a/src/algorithm.h b/src/algorithm.h
@@ -0,0 +1,53 @@
+/* Copyright (C) 2013-2015 Vincent Forest (vaplv@free.fr)
+ *
+ * The RSys library is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published
+ * by the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * The RSys library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */
+
+#ifndef ALGORITHM_H
+#define ALGORITHM_H
+
+#include "rsys.h"
+
+/* Search the first element in an array of `nmemb' objects pointed by `base',
+ * the first member that is *not* less than `key'. The size of each member of
+ * the array is specified by `size'. The array should be in ascending order
+ * according to the `compar' functor. This function is expected to have two
+ * arguments which point to the `key' object and an array member, in that
+ * order, and should return an integer less than, equal to, or greater than
+ * zero if the key object is found, respectively, to be less than, to match, or
+ * be greater than the array member. Return NULL if all array members compare
+ * less than `key'. */
+static INLINE void*
+search_lower_bound
+ (const void* key,
+ const void* base,
+ size_t nmemb,
+ size_t size,
+ int (*compar)(const void*, const void*))
+{
+#define AT(Base, Id) (void*)((const char*)(Base) + (Id)*size)
+ size_t lo = 0, hi = nmemb - 1;
+ while(compar(AT(base, lo), AT(base, hi)) < 0) {
+ size_t mid = (lo + hi) / 2;
+ if(compar(key, AT(base, mid)) > 0) {
+ lo = mid + 1;
+ } else {
+ hi = mid;
+ }
+ }
+ return compar(key, AT(base, lo)) > 0 ? NULL : AT(base, lo);
+#undef AT
+}
+
+#endif /* ALGORITHM_H */
+
diff --git a/src/test_algorithm.c b/src/test_algorithm.c
@@ -0,0 +1,81 @@
+/* Copyright (C) 2013-2015 Vincent Forest (vaplv@free.fr)
+ *
+ * The RSys library is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published
+ * by the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * The RSys library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */
+
+#include "algorithm.h"
+
+static int
+cmp_int(const void* a, const void* b)
+{
+ NCHECK(a, NULL);
+ NCHECK(b, NULL);
+ return *(const int*)a - *(const int*)b;
+}
+
+static int
+cmp_dbl(const void* a, const void* b)
+{
+ NCHECK(a, NULL);
+ NCHECK(b, NULL);
+ return *(const double*)a < *(const double*) b
+ ? -1 : (*(const double*)a > *(const double*)b ? 1 : 0);
+}
+
+int
+main(int argc, char** argv)
+{
+ const int array_int[] = { 0, 2, 4, 4, 4, 6, 10, 11, 13, 15, 17 };
+ const size_t nints = sizeof(array_int)/sizeof(int);
+ const double array_dbl[] = {
+ -1.123, 2.3, 2.3, 2.3, 4, 5.0, 5.2, 6, 9.1, 19.123
+ };
+ const size_t ndbls = sizeof(array_dbl)/sizeof(double);
+ int* pi;
+ int i;
+ double* pd;
+ double d;
+ (void)argc, (void)argv;
+
+ i = 3, pi = search_lower_bound(&i, array_int, nints, sizeof(int), cmp_int);
+ CHECK(*pi, 4);
+ CHECK(pi[3], 6);
+ i = 4, pi = search_lower_bound(&i, array_int, nints, sizeof(int), cmp_int);
+ CHECK(*pi, 4);
+ CHECK(pi[3], 6);
+ i = 5, pi = search_lower_bound(&i, array_int, nints, sizeof(int), cmp_int);
+ CHECK(*pi, 6);
+ i = 13, pi = search_lower_bound(&i, array_int, nints, sizeof(int), cmp_int);
+ CHECK(*pi, 13);
+ i = -1, pi = search_lower_bound(&i, array_int, nints, sizeof(int), cmp_int);
+ CHECK(*pi, 0);
+ i = 19, pi = search_lower_bound(&i, array_int, nints, sizeof(int), cmp_int);
+ CHECK(pi, NULL);
+
+ d = 2.1, pd = search_lower_bound(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
+ CHECK(*pd, 2.3);
+ d = 2.3, pd = search_lower_bound(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
+ CHECK(*pd, 2.3);
+ CHECK(pd[3], 4);
+ d = -1.0, pd = search_lower_bound(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
+ CHECK(*pd, 2.3);
+ d = 6.001, pd = search_lower_bound(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
+ CHECK(*pd, 9.1);
+ d = 19.0, pd = search_lower_bound(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
+ CHECK(*pd, 19.123);
+ d = 20.0, pd = search_lower_bound(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
+ CHECK(pd, NULL);
+
+ return 0;
+}
+
