rsys

commit 8f8381373ee976fc07c8dadf167392ac9bc70b4a
parent 5739a78ea8262d314c11807aa277c6e93b544e22
Author: vaplv <vaplv@free.fr>
Date:   Mon, 30 Jul 2018 15:40:39 +0200

Fix the search_lower_bound algorithm

Diffstat:
M
src/algorithm.h
 | 
2
+-
M
src/test_algorithm.c
 | 
70
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------

2 files changed, 58 insertions(+), 14 deletions(-)
diff --git a/src/algorithm.h b/src/algorithm.h
@@ -37,7 +37,7 @@ search_lower_bound
 {
 #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) {
+  while(lo < hi) {
     size_t mid = (lo + hi) / 2;
     if(compar(key, AT(base, mid)) > 0) {
       lo = mid + 1;
diff --git a/src/test_algorithm.c b/src/test_algorithm.c
@@ -15,6 +15,11 @@
 
 #include "algorithm.h"
 
+struct data {
+  char dummy[16];
+  double dbl;
+};
+
 static int
 cmp_int(const void* a, const void* b)
 {
@@ -32,6 +37,14 @@ cmp_dbl(const void* a, const void* b)
     ? -1 : (*(const double*)a > *(const double*)b ? 1 : 0);
 }
 
+static int
+cmp_key_data(const void* key, const void* data)
+{
+  const double h = *((const double*)key);
+  const struct data* d = (const struct data*)data;
+  return h < d->dbl ? -1 : (h > d->dbl ? 1 : 0);
+}
+
 int
 main(int argc, char** argv)
 {
@@ -41,42 +54,73 @@ main(int argc, char** argv)
     -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);
+  const struct data data[] = {
+    {{0},-1.123},
+    {{0},2.3},
+    {{0},2.3},
+    {{0},2.3},
+    {{0},4.0},
+    {{0},5.0},
+    {{0},5.2},
+    {{0},6.0},
+    {{0},9.1},
+    {{0},19.123}
+  };
+  const size_t ndata = sizeof(data)/sizeof(struct data);
+
   int* pi;
   int i;
   double* pd;
+  struct data* pdata;
   double d;
   (void)argc, (void)argv;
 
-  i = 3, pi = search_lower_bound(&i, array_int, nints, sizeof(int), cmp_int);
+  #define SEARCH search_lower_bound
+
+  i = 3, pi = SEARCH(&i, array_int, nints, sizeof(int), cmp_int);
   CHK(*pi == 4);
   CHK(pi[3] == 6);
-  i = 4, pi = search_lower_bound(&i, array_int, nints, sizeof(int), cmp_int);
+  i = 4, pi = SEARCH(&i, array_int, nints, sizeof(int), cmp_int);
   CHK(*pi == 4);
   CHK(pi[3] == 6);
-  i = 5, pi = search_lower_bound(&i, array_int, nints, sizeof(int), cmp_int);
+  i = 5, pi = SEARCH(&i, array_int, nints, sizeof(int), cmp_int);
   CHK(*pi == 6);
-  i = 13, pi = search_lower_bound(&i, array_int, nints, sizeof(int), cmp_int);
+  i = 13, pi = SEARCH(&i, array_int, nints, sizeof(int), cmp_int);
   CHK(*pi == 13);
-  i = -1, pi = search_lower_bound(&i, array_int, nints, sizeof(int), cmp_int);
+  i = -1, pi = SEARCH(&i, array_int, nints, sizeof(int), cmp_int);
   CHK(*pi == 0);
-  i = 19, pi = search_lower_bound(&i, array_int, nints, sizeof(int), cmp_int);
+  i = 19, pi = SEARCH(&i, array_int, nints, sizeof(int), cmp_int);
   CHK(pi == NULL);
 
-  d = 2.1, pd = search_lower_bound(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
+  d = 2.1, pd = SEARCH(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
   CHK(*pd == 2.3);
-  d = 2.3, pd = search_lower_bound(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
+  d = 2.3, pd = SEARCH(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
   CHK(*pd == 2.3);
   CHK(pd[3] == 4);
-  d = -1.0, pd = search_lower_bound(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
+  d = -1.0, pd = SEARCH(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
   CHK(*pd == 2.3);
-  d = 6.001, pd = search_lower_bound(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
+  d = 6.001, pd = SEARCH(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
   CHK(*pd == 9.1);
-  d = 19.0, pd = search_lower_bound(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
+  d = 19.0, pd = SEARCH(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
   CHK(*pd == 19.123);
-  d = 20.0, pd = search_lower_bound(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
+  d = 20.0, pd = SEARCH(&d, array_dbl, ndbls, sizeof(double), cmp_dbl);
   CHK(pd == NULL);
 
-  i = -1, pi = search_lower_bound(&i, array_int, 1, sizeof(int), cmp_int);
+  d = 2.1, pdata = SEARCH(&d, data, ndata, sizeof(struct data), cmp_key_data);
+  CHK(pdata->dbl == 2.3);
+  d = 2.3, pdata = SEARCH(&d, data, ndata, sizeof(struct data), cmp_key_data);
+  CHK(pdata->dbl == 2.3);
+  CHK(pdata[3].dbl == 4);
+  d = -1.0, pdata = SEARCH(&d, data, ndata, sizeof(struct data), cmp_key_data);
+  CHK(pdata->dbl == 2.3);
+  d = 6.001, pdata = SEARCH(&d, data, ndata, sizeof(struct data), cmp_key_data);
+  CHK(pdata->dbl == 9.1);
+  d = 19.0, pdata = SEARCH(&d, data, ndata, sizeof(struct data), cmp_key_data);
+  CHK(pdata->dbl == 19.123);
+  d = 20.0, pdata = SEARCH(&d, data, ndata, sizeof(struct data), cmp_key_data);
+  CHK(pdata == NULL);
+
+  i = -1, pi = SEARCH(&i, array_int, 1, sizeof(int), cmp_int);
   CHK(*pi ==  0);
 
   return 0;