summaryrefslogtreecommitdiff
path: root/obt
diff options
context:
space:
mode:
Diffstat (limited to 'obt')
-rw-r--r--obt/bsearch.h54
-rw-r--r--obt/bsearch_unittest.c316
-rw-r--r--obt/unittest_base.c55
-rw-r--r--obt/unittest_base.h65
4 files changed, 480 insertions, 10 deletions
diff --git a/obt/bsearch.h b/obt/bsearch.h
index 60da51d3..ceb53ff2 100644
--- a/obt/bsearch.h
+++ b/obt/bsearch.h
@@ -25,7 +25,8 @@ G_BEGIN_DECLS
/*! Setup to do a binary search on an array. */
#define BSEARCH_SETUP() \
- register guint l_BSEARCH, r_BSEARCH, out_BSEARCH;
+ register guint l_BSEARCH, r_BSEARCH, out_BSEARCH; \
+ register gboolean nearest_BSEARCH; (void)nearest_BSEARCH;
/*! Helper macro that just returns the input */
#define BSEARCH_IS_T(t) (t)
@@ -37,11 +38,21 @@ G_BEGIN_DECLS
/*! Search an array @ar, starting at index @start,
with @size elements, looking for value @val of type @t,
- using the macro @to_t to convert values in the arrau @ar to type @t.*/
+ using the macro @to_t to convert values in the arrau @ar to type @t.
+
+ If all elements in @ar are less than @val, then BSEARCH_AT() will be
+ the last element in @ar.
+ If all elements in @ar are greater than @val, then BSEARCH_AT() will be
+ the first element in @ar.
+ Otherwise, if the element @val is not found then BSEARCH_AT() will be set to
+ the position before the first element larger than @val.
+*/
#define BSEARCH_CMP(t, ar, start, size, val, to_t) \
-{ \
- l_BSEARCH = (start); \
- r_BSEARCH = (start)+(size)-1; \
+do { \
+ out_BSEARCH = (start); \
+ l_BSEARCH = (size) > 0 ? (start) : (start + 1); \
+ r_BSEARCH = (size) > 0 ? (start)+(size)-1 : (start); \
+ nearest_BSEARCH = FALSE; \
while (l_BSEARCH <= r_BSEARCH) { \
/* m is in the middle, but to the left if there's an even number \
of elements */ \
@@ -49,21 +60,44 @@ G_BEGIN_DECLS
if ((val) == to_t((ar)[out_BSEARCH])) { \
break; \
} \
- else if ((val) < to_t((ar)[out_BSEARCH]) && out_BSEARCH > 0) { \
- r_BSEARCH = out_BSEARCH-1; /* search to the left side */ \
+ else if ((val) < to_t((ar)[out_BSEARCH])) { \
+ if (out_BSEARCH > start) { \
+ r_BSEARCH = out_BSEARCH-1; /* search to the left side */ \
+ } else { \
+ /* reached the start of the array */ \
+ r_BSEARCH = out_BSEARCH; \
+ l_BSEARCH = out_BSEARCH + 1; \
+ } \
+ } \
+ else { \
+ l_BSEARCH = out_BSEARCH+1; /* search to the right side */ \
+ } \
+ } \
+ if ((size) > 0 && (val) != to_t((ar)[out_BSEARCH])) { \
+ if ((val) > to_t((ar)[out_BSEARCH])) { \
+ nearest_BSEARCH = TRUE; \
+ } \
+ else if (out_BSEARCH > start) { \
+ --out_BSEARCH; \
+ nearest_BSEARCH = (val) > to_t((ar)[out_BSEARCH]); \
} \
- else \
- l_BSEARCH = out_BSEARCH+1; /* search to the left side */ \
} \
-}
+} while (0)
/*! Returns true if the element last searched for was found in the array */
#define BSEARCH_FOUND() (l_BSEARCH <= r_BSEARCH)
+
/*! Returns the position in the array at which the element last searched for
was found. */
#define BSEARCH_AT() (out_BSEARCH)
+/*! Returns true if the element at BSEARCH_AT() in the array is the largest
+ value in the array smaller than the search key. Returns false if there was
+ nothing in the array smaller than the search key.
+ Should only be used when BSEARCH_FOUND() is false.
+*/
+#define BSEARCH_FOUND_NEAREST_SMALLER() (!BSEARCH_FOUND() && nearest_BSEARCH)
G_END_DECLS
diff --git a/obt/bsearch_unittest.c b/obt/bsearch_unittest.c
new file mode 100644
index 00000000..d5ff325d
--- /dev/null
+++ b/obt/bsearch_unittest.c
@@ -0,0 +1,316 @@
+#include "obt/unittest_base.h"
+
+#include "obt/bsearch.h"
+
+#include <glib.h>
+
+static void empty() {
+ TEST_START();
+
+ BSEARCH_SETUP();
+ int* array = NULL;
+ guint array_size = 0;
+
+ /* Search in an empty array. */
+ BSEARCH(int, array, 0, array_size, 10);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(0, BSEARCH_AT());
+
+ /* Search in an empty array with a non-zero starting position. */
+ BSEARCH(int, array, 10, array_size, -10);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(10, BSEARCH_AT());
+
+ TEST_END();
+}
+
+static void single_element() {
+ TEST_START();
+
+ BSEARCH_SETUP();
+ int array[1];
+ guint array_size = 1;
+
+ /* Search for something smaller than the only element. */
+ array[0] = 20;
+ BSEARCH(int, array, 0, array_size, -10);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(0, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ /* Search for something bigger than the only element. */
+ array[0] = 20;
+ BSEARCH(int, array, 0, array_size, 30);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(0, BSEARCH_AT());
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ /* Search for something smaller than the only element. */
+ array[0] = -20;
+ BSEARCH(int, array, 0, array_size, -30);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(0, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ /* Search for something bigger than the only element. */
+ array[0] = -20;
+ BSEARCH(int, array, 0, array_size, 10);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(0, BSEARCH_AT());
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ /* Search for the only element that exists. */
+ array[0] = -20;
+ BSEARCH(int, array, 0, array_size, -20);
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(0, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ TEST_END();
+}
+
+static void single_element_nonzero_start() {
+ TEST_START();
+
+ BSEARCH_SETUP();
+ int array[10];
+ guint array_start = 9;
+ guint array_size = 1;
+
+ /* Search for something smaller than the only element. */
+ array[array_start] = 20;
+ BSEARCH(int, array, array_start, array_size, -10);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(array_start, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ /* Search for something bigger than the only element. */
+ array[array_start] = 20;
+ BSEARCH(int, array, array_start, array_size, 30);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(array_start, BSEARCH_AT());
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ /* Search for something smaller than the only element. */
+ array[array_start] = -20;
+ BSEARCH(int, array, array_start, array_size, -30);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(array_start, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ /* Search for something bigger than the only element. */
+ array[array_start] = -20;
+ BSEARCH(int, array, array_start, array_size, 10);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(array_start, BSEARCH_AT());
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ /* Search for the only element that exists. */
+ array[array_start] = -20;
+ BSEARCH(int, array, array_start, array_size, -20);
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(array_start, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ TEST_END();
+}
+
+static void present() {
+ TEST_START();
+
+ BSEARCH_SETUP();
+ int array[5];
+ guint array_start = 0;
+ guint array_size = 5;
+
+ array[0] = 10;
+ array[1] = 12;
+ array[2] = 14;
+ array[3] = 16;
+ array[4] = 18;
+
+ /* Search for something that is in the array. */
+
+ BSEARCH(int, array, array_start, array_size, 10);
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(0, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 12);
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(1, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 14);
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(2, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 16);
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(3, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 18);
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(4, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ TEST_END();
+}
+
+static void present_nonzero_start() {
+ TEST_START();
+
+ BSEARCH_SETUP();
+ int array[5];
+ guint array_start = 2;
+ guint array_size = 3;
+
+ array[0] = 10;
+ array[1] = 12;
+ array[2] = 14;
+ array[3] = 16;
+ array[4] = 18;
+
+ /* Search for something that is in the array. */
+
+ BSEARCH(int, array, array_start, array_size, 10);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(array_start, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 12);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(array_start, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 14);
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(2, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 16);
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(3, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 18);
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(4, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ TEST_END();
+}
+
+static void missing() {
+ TEST_START();
+
+ BSEARCH_SETUP();
+ int array[5];
+ guint array_start = 0;
+ guint array_size = 5;
+
+ array[0] = 10;
+ array[1] = 12;
+ array[2] = 14;
+ array[3] = 16;
+ array[4] = 18;
+
+ /* Search for something that is _not_ in the array. */
+
+ BSEARCH(int, array, array_start, array_size, 9);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(0, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 11);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(0, BSEARCH_AT());
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 13);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(1, BSEARCH_AT());
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 15);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(2, BSEARCH_AT());
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 17);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(3, BSEARCH_AT());
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 19);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(4, BSEARCH_AT());
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ TEST_END();
+}
+
+static void missing_nonzero_start() {
+ TEST_START();
+
+ BSEARCH_SETUP();
+ int array[5];
+ guint array_start = 2;
+ guint array_size = 3;
+
+ array[0] = 10;
+ array[1] = 12;
+ array[2] = 14;
+ array[3] = 16;
+ array[4] = 18;
+
+ /* Search for something that is _not_ in the array. */
+
+ BSEARCH(int, array, array_start, array_size, 9);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(array_start, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 11);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(array_start, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 13);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(array_start, BSEARCH_AT());
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 15);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(2, BSEARCH_AT());
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 17);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(3, BSEARCH_AT());
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ BSEARCH(int, array, array_start, array_size, 19);
+ EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
+ EXPECT_UINT_EQ(4, BSEARCH_AT());
+ EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
+
+ TEST_END();
+}
+
+void run_bsearch_unittest() {
+ unittest_start_suite("bsearch");
+
+ empty();
+ single_element();
+ single_element_nonzero_start();
+ present();
+ present_nonzero_start();
+ missing();
+ missing_nonzero_start();
+
+ unittest_end_suite();
+}
diff --git a/obt/unittest_base.c b/obt/unittest_base.c
new file mode 100644
index 00000000..d6f91f4a
--- /dev/null
+++ b/obt/unittest_base.c
@@ -0,0 +1,55 @@
+#include <glib.h>
+
+#include "obt/unittest_base.h"
+
+guint g_test_failures = 0;
+guint g_test_failures_at_test_start = 0;
+const gchar* g_active_test_suite = NULL;
+const gchar* g_active_test_name = NULL;
+
+/* Add all test suites here. Keep them sorted. */
+extern void run_bsearch_unittest();
+
+gint main(gint argc, gchar **argv)
+{
+ /* Add all test suites here. Keep them sorted. */
+ run_bsearch_unittest();
+
+ return g_test_failures == 0 ? 0 : 1;
+}
+
+void unittest_start_suite(const char* suite_name)
+{
+ g_assert(g_active_test_suite == NULL);
+ g_active_test_suite = suite_name;
+ printf("[--------] %s\n", suite_name);
+}
+
+void unittest_end_suite()
+{
+ g_assert(g_active_test_suite);
+ printf("[--------] %s\n", g_active_test_suite);
+ printf("\n");
+ g_active_test_suite = NULL;
+}
+
+void unittest_start(const char* test_name)
+{
+ g_test_failures_at_test_start = g_test_failures;
+ g_assert(g_active_test_name == NULL);
+ g_active_test_name = test_name;
+ printf("[ RUN ] %s.%s\n", g_active_test_suite, g_active_test_name);
+}
+
+void unittest_end()
+{
+ g_assert(g_active_test_name);
+ if (g_test_failures_at_test_start == g_test_failures) {
+ printf("[ OK ] %s.%s\n",
+ g_active_test_suite, g_active_test_name);
+ } else {
+ printf("[ FAILED ] %s.%s\n",
+ g_active_test_suite, g_active_test_name);
+ }
+ g_active_test_name = NULL;
+}
diff --git a/obt/unittest_base.h b/obt/unittest_base.h
new file mode 100644
index 00000000..85106bb3
--- /dev/null
+++ b/obt/unittest_base.h
@@ -0,0 +1,65 @@
+#ifndef __obt_unittest_base_h
+#define __obt_unittest_base_h
+
+#include <glib.h>
+#include <stdio.h>
+
+G_BEGIN_DECLS
+
+extern guint g_test_failures;
+extern guint g_test_failures_at_test_start;
+extern const gchar* g_active_test_suite;
+extern const gchar* g_active_test_name;
+
+#define ADD_FAILURE() { ++g_test_failures; }
+
+#define FAILURE_AT() \
+ fprintf(stderr, "Failure at %s:%u\n", __FILE__, __LINE__); \
+ ADD_FAILURE();
+
+#define EXPECT_BOOL_EQ(expected, actual) \
+ if ((expected) != (actual)) { \
+ FAILURE_AT(); \
+ fprintf(stderr, "Expected: %s\nActual: %s\n", \
+ ((expected) ? "true" : "false"), \
+ ((actual) ? "true" : "false")); \
+ }
+
+#define EXPECT_CHAR_EQ(expected, actual) \
+ if ((expected) != (actual)) { \
+ FAILURE_AT(); \
+ fprintf(stderr, "Expected: %c\nActual: %c\n", (expected), (actual)); \
+ }
+
+#define EXPECT_INT_EQ(expected, actual) \
+ if ((expected) != (actual)) { \
+ FAILURE_AT(); \
+ fprintf(stderr, "Expected: %d\nActual: %d\n", (expected), (actual)); \
+ }
+
+#define EXPECT_UINT_EQ(expected, actual) \
+ if ((expected) != (actual)) { \
+ FAILURE_AT(); \
+ fprintf(stderr, "Expected: %u\nActual: %u\n", (expected), (actual)); \
+ }
+
+#define EXPECT_STRING_EQ(expected, actual) \
+ if ((expected) != (actual)) { \
+ FAILURE_AT(); \
+ fprintf(stderr, "Expected: %s\nActual: %s\n", \
+ ((expected) ? (expected) : "NULL"), \
+ ((actual) ? (actual) : NULL)); \
+ }
+
+void unittest_start_suite(const char* suite_name);
+void unittest_end_suite();
+
+void unittest_start(const char* test_name);
+void unittest_end();
+
+#define TEST_START() unittest_start(__func__);
+#define TEST_END() unittest_end();
+
+G_END_DECLS
+
+#endif
generated by cgit v1.2.3 (git 2.25.1) at 2026-02-17 05:23:38 +0000