FW: rTree insert optimization.

Dear all,

rTree using for allocation glyph image on GL texture.
This patch made more accurately allocation space for GL texture.

Please review this patch.

----------------------------------------------------------------------------------------------------------------------
commit 51951ba37d67960b7f7df43ceee6fe9d68555308
Author: Valery Volgutov <[email protected]>
Date:   Mon Feb 27 16:42:58 2012 +0400

    gl: RTree insert optimization

diff --git a/src/cairo-rtree.c b/src/cairo-rtree.c
index dbc0409..66f5c96 100644
--- a/src/cairo-rtree.c
+++ b/src/cairo-rtree.c
@@ -199,13 +199,30 @@ _cairo_rtree_insert (cairo_rtree_t             *rtree,
                     cairo_rtree_node_t     **out)
 {
     cairo_rtree_node_t *node;
+    cairo_rtree_node_t *found = NULL;
+    int min_d = 0x7fffffff;
+    int dw;
+    int dh;
+    int d;

     cairo_list_foreach_entry (node, cairo_rtree_node_t,
                              &rtree->available, link)
     {
-       if (node->width >= width && node->height >= height)
-           return _cairo_rtree_node_insert (rtree, node, width, height, out);
+        dw = node->width - width;
+        dh = node->height - height;
+        d = dw > dh ? dh: dw;
+
+        if (dw >= 0 && dh >= 0 && min_d > d)
+        {
+            min_d = d;
+            if (min_d == 0)
+                return _cairo_rtree_node_insert (rtree, node, width, height, out);
+
+            found = node;
+        }
     }
+    if (found)
+        return _cairo_rtree_node_insert (rtree, found, width, height, out);

     return CAIRO_INT_STATUS_UNSUPPORTED;
 }
----------------------------------------------------------------------------------------------------------------------

Best regards,
Valery Volgutov

--
cairo mailing list
[email protected]
http://lists.cairographics.org/mailman/listinfo/cairo

commit 51951ba37d67960b7f7df43ceee6fe9d68555308
Author: Valery Volgutov <[email protected]>
Date:   Mon Feb 27 16:42:58 2012 +0400

    gl: RTree insert optimization

diff --git a/src/cairo-rtree.c b/src/cairo-rtree.c
index dbc0409..66f5c96 100644
--- a/src/cairo-rtree.c
+++ b/src/cairo-rtree.c
@@ -199,13 +199,30 @@ _cairo_rtree_insert (cairo_rtree_t	     *rtree,
 	             cairo_rtree_node_t	    **out)
 {
     cairo_rtree_node_t *node;
+    cairo_rtree_node_t *found = NULL;
+    int min_d = 0x7fffffff;
+    int dw;
+    int dh;
+    int d;
 
     cairo_list_foreach_entry (node, cairo_rtree_node_t,
 			      &rtree->available, link)
     {
-	if (node->width >= width && node->height >= height)
-	    return _cairo_rtree_node_insert (rtree, node, width, height, out);
+        dw = node->width - width;
+        dh = node->height - height;
+        d = dw > dh ? dh: dw;
+
+        if (dw >= 0 && dh >= 0 && min_d > d)
+        {
+            min_d = d;
+            if (min_d == 0)
+                return _cairo_rtree_node_insert (rtree, node, width, height, out);
+
+            found = node;
+        }
     }
+    if (found)
+        return _cairo_rtree_node_insert (rtree, found, width, height, out);
 
     return CAIRO_INT_STATUS_UNSUPPORTED;
 }