Use the BSEARCH() macro in overlap placement

Currently the code rolls its own binary search, but now that we have
a well-tested binary search implementation in obt/ we can make use
of that.

1 files changed, 22 insertions, 24 deletions

diff --git a/openbox/place_overlap.c b/openbox/place_overlap.c
index ac7255bf..ed7ff6c0 100644
--- a/openbox/place_overlap.c
+++ b/openbox/place_overlap.c
@@ -19,7 +19,9 @@
 #include "config.h"
 #include "geom.h"
 #include "place_overlap.h"
+#include "obt/bsearch.h"
 
+#include <glib.h>
 #include <stdlib.h>
 
 static void make_grid(const Rect* client_rects,
@@ -170,29 +172,23 @@ static int total_overlap(const Rect* client_rects,
     return overlap;
 }
 
-/* Unfortunately, the libc bsearch() function cannot be used to find the
-   position of a value that is not in the array, and glib doesn't
-   provide a binary search function at all.  So, tricky as it is, if we
-   want to avoid linear scan of the edge array, we have to roll our
-   own. */
-static int grid_position(int value,
-                         const int* edges,
-                         int max_edges)
+static int find_first_grid_position_greater_or_equal(int search_value,
+                                                     const int* edges,
+                                                     int max_edges)
 {
-    int low = 0;
-    int high = max_edges - 1;
-    int mid = low + (high - low) / 2;
-    while (low != mid) {
-        if (value < edges[mid])
-            high = mid;
-        else if (value > edges[mid])
-            low = mid;
-        else                    /* value == edges[mid] */
-            return mid;
-        mid = low + (high - low) / 2;
-    }
-    /* we get here when low == mid.  can have low == high or low == high - 1 */
-    return (value <= edges[low] ? low : high);
+    g_assert(max_edges >= 2);
+    g_assert(search_value >= edges[0]);
+    g_assert(search_value <= edges[max_edges - 1]);
+
+    BSEARCH_SETUP();
+    BSEARCH(int, edges, 0, max_edges, search_value);
+
+    if (BSEARCH_FOUND())
+        return BSEARCH_AT();
+
+    g_assert(BSEARCH_FOUND_NEAREST_SMALLER());
+    /* Get the nearest larger instead. */
+    return BSEARCH_AT() + 1;
 }                         
 
 static void expand_width(Rect* r, int by)
@@ -263,9 +259,11 @@ static void center_in_field(Point* top_left,
 {
     /* Find minimal rectangle. */
     int orig_right_edge_index =
-        grid_position(top_left->x + req_size->width, x_edges, max_edges);
+        find_first_grid_position_greater_or_equal(
+            top_left->x + req_size->width, x_edges, max_edges);
     int orig_bottom_edge_index =
-        grid_position(top_left->y + req_size->height, y_edges, max_edges);
+        find_first_grid_position_greater_or_equal(
+            top_left->y + req_size->height, y_edges, max_edges);
     ExpandInfo i = {
         .top_left = top_left,
         .orig_width = x_edges[orig_right_edge_index] - top_left->x,