diff options
| -rw-r--r-- | include/util/rect_union.h | 76 | ||||
| -rw-r--r-- | util/meson.build | 1 | ||||
| -rw-r--r-- | util/rect_union.c | 91 |
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(®, ru->unsorted.data, nrects); + if (!ok) { + handle_alloc_failure(ru); + goto bounding_box; + } + ok = pixman_region32_union(®, ®, &ru->region); + if (!ok) { + pixman_region32_fini(®); + 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; +} + |