aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorManuel Stoeckl <code@mstoeckl.com>2023-10-01 16:25:39 -0400
committerSimon Ser <contact@emersion.fr>2023-10-05 11:45:32 +0000
commitd180f4d9b3fab72ff1bad881c91b004c905299c3 (patch)
tree0db65ca8def31d644852826ea4b9000eb6697264
parentd817ebb80f8b0f1a27152104525d4b5a8c38e56d (diff)
util: add struct to track union of rectangles
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.
-rw-r--r--include/util/rect_union.h76
-rw-r--r--util/meson.build1
-rw-r--r--util/rect_union.c91
3 files changed, 168 insertions, 0 deletions
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
diff --git a/util/meson.build b/util/meson.build
index 1cd7f65c..1c3dcd5a 100644
--- a/util/meson.build
+++ b/util/meson.build
@@ -5,6 +5,7 @@ wlr_files += files(
'env.c',
'global.c',
'log.c',
+ 'rect_union.c',
'region.c',
'set.c',
'shm.c',
diff --git a/util/rect_union.c b/util/rect_union.c
new file mode 100644
index 00000000..8cd26d76
--- /dev/null
+++ b/util/rect_union.c
@@ -0,0 +1,91 @@
+#include <limits.h>
+#include "util/rect_union.h"
+
+static void box_union(pixman_box32_t *dst, pixman_box32_t box) {
+ dst->x1 = dst->x1 < box.x1 ? dst->x1 : box.x1;
+ dst->y1 = dst->y1 < box.y1 ? dst->y1 : box.y1;
+ dst->x2 = dst->x2 > box.x2 ? dst->x2 : box.x2;
+ dst->y2 = dst->y2 > box.y2 ? dst->y2 : box.y2;
+}
+
+static bool box_empty_or_invalid(pixman_box32_t box) {
+ return box.x1 >= box.x2 || box.y1 >= box.y2;
+}
+
+void rect_union_init(struct rect_union *ru) {
+ *ru = (struct rect_union) {
+ .alloc_failure = false,
+ .bounding_box = (pixman_box32_t) {
+ .x1 = INT_MAX,
+ .x2 = INT_MIN,
+ .y1 = INT_MAX,
+ .y2 = INT_MIN,
+ }
+ };
+ pixman_region32_init(&ru->region);
+ wl_array_init(&ru->unsorted);
+};
+
+void rect_union_finish(struct rect_union *ru) {
+ pixman_region32_fini(&ru->region);
+ wl_array_release(&ru->unsorted);
+}
+
+static void handle_alloc_failure(struct rect_union *ru) {
+ ru->alloc_failure = true;
+ wl_array_release(&ru->unsorted);
+ wl_array_init(&ru->unsorted);
+}
+
+void rect_union_add(struct rect_union *ru, pixman_box32_t box) {
+ if (box_empty_or_invalid(box)) {
+ return;
+ }
+
+ box_union(&ru->bounding_box, box);
+
+ if (!ru->alloc_failure) {
+ pixman_box32_t *entry = wl_array_add(&ru->unsorted, sizeof(*entry));
+ if (entry) {
+ *entry = box;
+ } else {
+ handle_alloc_failure(ru);
+ }
+ }
+}
+
+const pixman_region32_t *rect_union_evaluate(struct rect_union *ru) {
+ if (ru->alloc_failure) {
+ goto bounding_box;
+ }
+
+ int nrects = (int)(ru->unsorted.size / sizeof(pixman_box32_t));
+ pixman_region32_t reg;
+ bool ok = pixman_region32_init_rects(&reg, ru->unsorted.data, nrects);
+ if (!ok) {
+ handle_alloc_failure(ru);
+ goto bounding_box;
+ }
+ ok = pixman_region32_union(&reg, &reg, &ru->region);
+ if (!ok) {
+ pixman_region32_fini(&reg);
+ handle_alloc_failure(ru);
+ goto bounding_box;
+ }
+ pixman_region32_fini(&ru->region);
+ // pixman_region32_t is safe to move
+ ru->region = reg;
+ wl_array_release(&ru->unsorted);
+ wl_array_init(&ru->unsorted);
+
+ return &ru->region;
+bounding_box:
+ pixman_region32_fini(&ru->region);
+ if (box_empty_or_invalid(ru->bounding_box)) {
+ pixman_region32_init(&ru->region);
+ } else {
+ pixman_region32_init_with_extents(&ru->region, &ru->bounding_box);
+ }
+ return &ru->region;
+}
+