From d180f4d9b3fab72ff1bad881c91b004c905299c3 Mon Sep 17 00:00:00 2001
From: Manuel Stoeckl <code@mstoeckl.com>
Date: Sun, 1 Oct 2023 16:25:39 -0400
Subject: util: add struct to track union of rectangles
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

The new struct rect_union is designed to make it easier to
efficiently accumulate a list of rectangles, and then operate
on an exact cover of their union.

Using rect_union, the times needed to added t rectangles, and then
compute their exact cover will be O(t), and something between Ω(t) and
O(t^2), depending on the rectangle arrangement. If one tries to do
the same by storing a pixman_region32_t and updating it with
pixman_region32_union_rect(), then total time needed would be between
Ω(t^2) and O(t^3), depending on the input. Without changing the public
API (data structure + rectangle ordering rules) for pixman_region32_t,
it is impossible to improve its worst case time.
---
 include/util/rect_union.h | 76 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 76 insertions(+)
 create mode 100644 include/util/rect_union.h

(limited to 'include/util')

diff --git a/include/util/rect_union.h b/include/util/rect_union.h
new file mode 100644
index 00000000..2d74f94d
--- /dev/null
+++ b/include/util/rect_union.h
@@ -0,0 +1,76 @@
+#ifndef UTIL_RECT_UNION_H
+#define UTIL_RECT_UNION_H
+
+#include <stdlib.h>
+#include <stdbool.h>
+#include <pixman.h>
+#include <wayland-util.h>
+
+/**
+ * `struct rect_union` is a data structure to efficiently accumulate a number
+ * of rectangles and then, when needed, compute a disjoint cover of their union.
+ * (That is: produce a list of disjoint rectangles which covers every point
+ * that was contained in one of the added rectangles.)
+ *
+ * Add rectangles to the union with `rect_union_add()`; to compute the disjoint
+ * union, run `rect_union_evaluate()`, which will place the result in `.region`.
+ * If there were any allocation failures, `.region` will instead contain the
+ * bounding box for the entire list of rectangles.
+ *
+ * Example usage:
+ *
+ *     struct rect_union r;
+ *     rect_union_init(&r);
+ *     for (j in ...) {
+ *         rect_union_add(&r, box[j]);
+ *     }
+ *     const pixman_region32_t *reg = rect_union_evaluate(&r);
+ *     int nboxes;
+ *     pixman_box32_t *boxes = pixman_region32_rectangles(reg, nboxes);
+ *     for (int i = 0; i < nboxes; i++) {
+ *         do_stuff(boxes[i]);
+ *     }
+ *     rect_union_destroy(&r);
+ *
+ */
+struct rect_union {
+	pixman_box32_t bounding_box; // Always up-to-date bounding box
+	pixman_region32_t region; // Updated only on _evaluate()
+
+	struct wl_array unsorted; // pixman_box32_t
+	bool alloc_failure; // If this is true, fall back to computing a bounding box
+};
+
+/**
+ * Initialize *r, disregarding any previous contents.
+ */
+void rect_union_init(struct rect_union *r);
+
+/**
+ * Free heap data associated with *r; should only be called after rect_union_init.
+ * Leaves *r in an invalid state.
+ */
+void rect_union_finish(struct rect_union *r);
+
+/**
+ * Add a rectangle to the union. If `box` is empty or invalid (x2 > x1 || y2 > y1),
+ * do nothing.
+ *
+ * Amortized time: O(1)
+ */
+void rect_union_add(struct rect_union *r, pixman_box32_t box);
+
+/**
+ * Compute an exact cover of the rectangles added so far, and return
+ * a pointer to a pixman_region32_t giving that cover. The pointer will
+ * remain valid until the next time *r is modified. If there was an allocation
+ * failure, this function may return a single-rectangle bounding box instead.
+ *
+ * This may be called multiple times and interleaved with rect_union_add().
+ *
+ * Worst case time: O(t^2), where t is the number of rectangles in the list.
+ * Best case time: O(t), if rectangles are disjoint and have y-x band structure
+ */
+const pixman_region32_t *rect_union_evaluate(struct rect_union *r);
+
+#endif
-- 
cgit v1.2.3