/*! 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)
/*! 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 */ \
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
--- /dev/null
+#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();
+}
exit 1
}
+build_and_test() {
+ style=$1
+ make >/dev/null 2>/dev/null || error "make failed ($style)"
+ ./obt/obt_unittests > /dev/null || error "unittest failed ($style)"
+ make distclean >/dev/null || error "make distclean failed"
+}
+
REV="$1"
test -z "$REV" && help
VERSION="$2"
BAD_PO="$(grep Project-Id-Version po/en*.po|grep -v "openbox $VERSION\\\\n")"
test -z "$BAD_PO" || error "wrong version in po files" "$BAD_PO"
-#### TEST COMPILATION ####
+#### RESET THE REPO TO A CLEAN STATE ####
+
+git clean -f -x -d -q
+
+#### TEST ALL OPTIONAL COMPILATION FLAGS ####
# check that it builds
-./bootstrap >/dev/null || "bootstrap failed"
-#CFLAGS="-Werror -isystem /usr/lib/glib-2.0" \
+echo Bootstrapping
+./bootstrap >/dev/null 2>/dev/null || "bootstrap failed"
+
+echo Check compile with debug and all options enabled
+CFLAGS="-Werror -isystem /usr/lib/glib-2.0" \
./configure -C --enable-debug >/dev/null || \
error "configure (with debug) failed"
-make || error "make (with debug and Werror) failed"
-git clean -f -x -d -q
+build_and_test "with debug and Werror"
# check that it builds with each optional featureset
-./bootstrap >/dev/null || "bootstrap failed"
-
echo Check compile with all options enabled
./configure -C >/dev/null || \
error "configure failed"
-make >/dev/null 2>/dev/null || \
- error "make failed"
grep "XKB 1" config.log >/dev/null || error "missing xkb extension"
grep "XRANDR 1" config.log >/dev/null || error "missing xrandr extension"
grep "XINERAMA 1" config.log >/dev/null || error "missing xinerama extension"
grep "SYNC 1" config.log >/dev/null || error "missing sync extension"
-make clean >/dev/null || error "make clean failed"
+grep "USE_XCURSOR 1" config.log >/dev/null || error "missing xcursor extension"
+grep "USE_IMLIB2 1" config.log >/dev/null || error "missing imlib2 library"
+grep "USE_LIBRSVG 1" config.log >/dev/null || error "missing librsvg library"
+grep "USE_SM 1" config.log >/dev/null || error "missing session management extension"
+build_and_test
echo Check compile with startup notification disabled
./configure -C --disable-startup-notification >/dev/null || \
error "configure failed"
-make >/dev/null 2>/dev/null || \
- error "make (with --disable-startup-notification) failed"
-make clean >/dev/null || error "make clean failed"
+build_and_test "with --disable-startup-notification"
echo Check compile with xcursor disabled
./configure -C --disable-xcursor >/dev/null || \
error "configure failed"
-make >/dev/null 2>/dev/null || \
- error "make (with --disable-xcursor) failed"
-make clean >/dev/null || error "make clean failed"
+build_and_test "with --disable-xcursor"
echo Check compile with imlib2 disabled
./configure -C --disable-imlib2 >/dev/null || \
error "configure failed"
-make >/dev/null 2>/dev/null || \
- error "make (with --disable-imlib2) failed"
-make clean >/dev/null || error "make clean failed"
+build_and_test "with --disable-imlib2"
echo Check compile with librsvg disabled
-./configure -C --disable-imlib2 >/dev/null || \
+./configure -C --disable-librsvg >/dev/null || \
error "configure failed"
-make >/dev/null 2>/dev/null || \
- error "make (with --disable-librsvg) failed"
-make clean >/dev/null || error "make clean failed"
+build_and_test "with --disable-librsvg"
echo Check compile with session management disabled
./configure -C --disable-session-management >/dev/null || \
error "configure failed"
-make >/dev/null 2>/dev/null || \
- error "make (with --disable-session-management) failed"
-make clean >/dev/null || error "make clean failed"
+build_and_test "with --disable-session-management"
echo Check compile with xkb disabled
./configure -C --disable-xkb >/dev/null || error "configure failed"
-make >/dev/null 2>/dev/null || error "make (with --disable-xkb) failed"
-make clean >/dev/null || error "make clean failed"
+build_and_test "with --disable-xkb"
echo Check compile with xrandr disabled
./configure -C --disable-xrandr >/dev/null || error "configure failed"
-make >/dev/null 2>/dev/null || error "make (with --disable-xrandr) failed"
-make clean >/dev/null || error "make clean failed"
+build_and_test "with --disable-xrandr"
echo Check compile with xinerama disabled
./configure -C --disable-xinerama >/dev/null || error "configure failed"
-make >/dev/null 2>/dev/null || error "make (with --disable-xinerama) failed"
-make clean >/dev/null || error "make clean failed"
+build_and_test("with --disable-xinerama")
echo Check compile with xsync disabled
./configure -C --disable-xsync >/dev/null || error "configure failed"
-make >/dev/null 2>/dev/null || error "make (with --disable-xsync) failed"
-make clean >/dev/null || error "make clean failed"
+build_and_test("with --disable-xsync")
# check that it installs sanely
echo Check installation correctness
projects / mikachu / openbox.git / commitdiff