author Dana Jansens Sun, 1 Sep 2013 19:17:11 +0000 (15:17 -0400) committer Dana Jansens Mon, 2 Sep 2013 18:10:37 +0000 (14:10 -0400)
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.

index ac7255b..ed7ff6c 100644 (file)
@@ -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);
+    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,