record: Use a bbtree to reduce is-visible checking overheads

By using a bounding-box rtree, we are able to reject invisible branches
of the tree and so find the visible leafs with fewer intersection
checks. Overhead reduction is strongly dependent upon the ability to
spatially partition the geometry and so performance correlates with
small tiles and small operations.

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>

1 files changed, 23 insertions, 0 deletions

diff --git a/src/cairo-combsort-private.h b/src/cairo-combsort-private.h
index bb7abb47..d359faeb 100644
--- a/src/cairo-combsort-private.h
+++ b/src/cairo-combsort-private.h
@@ -69,3 +69,26 @@ NAME (TYPE *base, unsigned int nmemb) \
       } \
   } while (swapped); \
 }
+
+#define CAIRO_COMBSORT_DECLARE_WITH_DATA(NAME, TYPE, CMP) \
+static void \
+NAME (TYPE *base, unsigned int nmemb, void *data) \
+{ \
+  unsigned int gap = nmemb; \
+  unsigned int i, j; \
+  int swapped; \
+  do { \
+      gap = _cairo_combsort_newgap (gap); \
+      swapped = gap > 1; \
+      for (i = 0; i < nmemb-gap ; i++) { \
+	  j = i + gap; \
+	  if (CMP (base[i], base[j], data) > 0 ) { \
+	      TYPE tmp; \
+	      tmp = base[i]; \
+	      base[i] = base[j]; \
+	      base[j] = tmp; \
+	      swapped = 1; \
+	  } \
+      } \
+  } while (swapped); \
+}