WebSVN – Kolibri OS – Diff – /programs/develop/libraries/cairo/src/cairo-bentley-ottmann-rectangular.c

 /* Provide definitions for standalone compilation */
 #include "cairoint.h"
 #include "cairo-boxes-private.h"
 #include "cairo-error-private.h"
-#include "cairo-combsort-private.h"
+#include "cairo-combsort-inline.h"
+#include "cairo-list-private.h"
-#include "cairo-list-private.h"
+#include "cairo-traps-private.h"
 #include
 #define PQ_FIRST_ENTRY 1
 /* left and right children are index * 2 and (index * 2) +1 respectively */
-#define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
-typedef struct _pqueue {
-    int size, max_size;
-    rectangle_t **elements;
-    rectangle_t *elements_embedded[1024];
-} pqueue_t;
+#define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
-typedef struct _sweep_line {
-    rectangle_t **rectangles;
+typedef struct _sweep_line {
-    pqueue_t pq;
+    rectangle_t **rectangles;
-    edge_t head, tail;
+    rectangle_t **stop;
-    edge_t *insert_left, *insert_right;
+    edge_t head, tail, *insert, *cursor;
+    int32_t current_y;
+    int32_t last_y;
-    int32_t current_y;
+    int stop_size;
+    int32_t insert_x;
+    cairo_fill_rule_t fill_rule;
     int32_t last_y;
     cairo_bool_t do_traps;
-    cairo_fill_rule_t fill_rule;
+    void *container;
+{
     return a->bottom - b->bottom;
+}
-static inline void
-pqueue_init (pqueue_t *pq)
-{
-    pq->max_size = ARRAY_LENGTH (pq->elements_embedded);
-    pq->size = 0;
-    pq->elements = pq->elements_embedded;
-    pq->elements[PQ_FIRST_ENTRY] = NULL;
-}
-static inline void
-pqueue_fini (pqueue_t *pq)
-{
-    if (pq->elements != pq->elements_embedded)
-	free (pq->elements);
-}
-static cairo_bool_t
-pqueue_grow (pqueue_t *pq)
-{
-    rectangle_t **new_elements;
-    pq->max_size *= 2;
-    if (pq->elements == pq->elements_embedded) {
-	new_elements = _cairo_malloc_ab (pq->max_size,
-					 sizeof (rectangle_t *));
-	if (unlikely (new_elements == NULL))
-	    return FALSE;
-	memcpy (new_elements, pq->elements_embedded,
-		sizeof (pq->elements_embedded));
-    } else {
-	new_elements = _cairo_realloc_ab (pq->elements,
-					  pq->max_size,
-					  sizeof (rectangle_t *));
-	if (unlikely (new_elements == NULL))
-	    return FALSE;
-    }
-    pq->elements = new_elements;
-    return TRUE;
-}
 static inline void
 pqueue_push (sweep_line_t *sweep, rectangle_t *rectangle)
+{
     rectangle_t **elements;
-    int i, parent;
-    if (unlikely (sweep->pq.size + 1 == sweep->pq.max_size)) {
-	if (unlikely (! pqueue_grow (&sweep->pq))) {
-	    longjmp (sweep->unwind,
-		     _cairo_error (CAIRO_STATUS_NO_MEMORY));
-	}
-    }
+    int i, parent;
-    elements = sweep->pq.elements;
+    elements = sweep->stop;
-    for (i = ++sweep->pq.size;
+    for (i = ++sweep->stop_size;
 	 i != PQ_FIRST_ENTRY &&
 	 rectangle_compare_stop (rectangle,
 				 elements[parent = PQ_PARENT_INDEX (i)]) < 0;
     elements[i] = rectangle;
+}
 static inline void
-pqueue_pop (pqueue_t *pq)
+rectangle_pop_stop (sweep_line_t *sweep)
+{
-    rectangle_t **elements = pq->elements;
+    rectangle_t **elements = sweep->stop;
     rectangle_t *tail;
     int child, i;
-    tail = elements[pq->size--];
+    tail = elements[sweep->stop_size--];
-    if (pq->size == 0) {
+    if (sweep->stop_size == 0) {
 	elements[PQ_FIRST_ENTRY] = NULL;
 	return;
+    }
     for (i = PQ_FIRST_ENTRY;
-	 (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size;
+	 (child = PQ_LEFT_CHILD_INDEX (i)) <= sweep->stop_size;
 	 i = child)
+    {
-	if (child != pq->size &&
+	if (child != sweep->stop_size &&
 	    rectangle_compare_stop (elements[child+1],
+}
 static inline rectangle_t *
 rectangle_peek_stop (sweep_line_t *sweep_line)
 {
-    return sweep_line->pq.elements[PQ_FIRST_ENTRY];
+    return sweep_line->stop[PQ_FIRST_ENTRY];
+}
 CAIRO_COMBSORT_DECLARE (_rectangle_sort,
 			rectangle_t *,
 			rectangle_compare_start)
 static void
 sweep_line_init (sweep_line_t	 *sweep_line,
+		 rectangle_t	**rectangles,
+		 int		  num_rectangles,
-		 rectangle_t	**rectangles,
+		 cairo_fill_rule_t fill_rule,
+		 cairo_bool_t	 do_traps,
-		 int		  num_rectangles,
+		 void		*container)
 		 cairo_fill_rule_t fill_rule)
     rectangles[-2] = NULL;
+    rectangles[-1] = NULL;
+    rectangles[num_rectangles] = NULL;
+    sweep_line->rectangles = rectangles;
+    sweep_line->stop = rectangles - 2;
+    sweep_line->stop_size = 0;
+    sweep_line->insert = NULL;
-    _rectangle_sort (rectangles, num_rectangles);
+    sweep_line->insert_x = INT_MAX;
-    rectangles[num_rectangles] = NULL;
+    sweep_line->cursor = &sweep_line->tail;
-    sweep_line->rectangles = rectangles;
     sweep_line->head.dir = 0;
+    sweep_line->head.x = INT32_MIN;
-    sweep_line->head.x = INT32_MIN;
+    sweep_line->head.right = NULL;
-    sweep_line->head.right = NULL;
+    sweep_line->head.prev = NULL;
+    sweep_line->head.next = &sweep_line->tail;
-    sweep_line->head.dir = 0;
+    sweep_line->tail.prev = &sweep_line->head;
-    sweep_line->head.next = &sweep_line->tail;
-    sweep_line->tail.x = INT32_MAX;
-    sweep_line->tail.right = NULL;
-    sweep_line->tail.dir = 0;
-    sweep_line->tail.prev = &sweep_line->head;
+    sweep_line->tail.next = NULL;
     sweep_line->tail.right = NULL;
-    sweep_line->insert_left = &sweep_line->tail;
+    sweep_line->tail.x = INT32_MAX;
-    sweep_line->insert_right = &sweep_line->tail;
+    sweep_line->tail.dir = 0;
     sweep_line->current_y = INT32_MIN;
     sweep_line->last_y = INT32_MIN;
-    sweep_line->fill_rule = fill_rule;
-    pqueue_init (&sweep_line->pq);
-}
-static void
-sweep_line_fini (sweep_line_t *sweep_line)
-{
-    pqueue_fini (&sweep_line->pq);
-}
     sweep_line->fill_rule = fill_rule;
-static void
+    sweep_line->container = container;
-edge_end_box (sweep_line_t *sweep_line,
+    sweep_line->do_traps = do_traps;
 	      edge_t	*left,
-	      int32_t		 bot,
-	      cairo_bool_t	 do_traps,
+static void
-	      void	        *container)
+edge_end_box (sweep_line_t *sweep_line, edge_t *left, int32_t bot)
+{
     cairo_status_t status = CAIRO_STATUS_SUCCESS;
     /* Only emit (trivial) non-degenerate trapezoids with positive height. */
     if (likely (left->top < bot)) {
-	if (do_traps) {
+	if (sweep_line->do_traps) {
 	    cairo_line_t _left = {
 		{ left->x, left->top },
 		{ left->x, bot },
 	    }, _right = {
 		{ left->right->x, left->top },
 		{ left->right->x, bot },
 	    };
-	    _cairo_traps_add_trap (container, left->top, bot, &_left, &_right);
+	    _cairo_traps_add_trap (sweep_line->container, left->top, bot, &_left, &_right);
+	    status = _cairo_traps_status ((cairo_traps_t *) sweep_line->container);
+	} else {
-	    status = _cairo_traps_status ((cairo_traps_t *) container);
+	    cairo_box_t box;
 	} else {
-	    cairo_box_t box;
+	    box.p1.x = left->x;
 	    box.p1.y = left->top;
  * trapezoid would be a continuation of the existing one. */
 static inline void
 edge_start_or_continue_box (sweep_line_t *sweep_line,
 			    edge_t	*left,
 			    edge_t	*right,
-			    int		 top,
+			    int		 top)
-			    cairo_bool_t	 do_traps,
-			    void		*container)
+{
     if (left->right == right)
 	return;
     if (left->right != NULL) {
-	if (right != NULL && left->right->x == right->x) {
+	if (left->right->x == right->x) {
 	    /* continuation on right, so just swap edges */
 	    left->right = right;
 	    return;
 	}
 	edge_end_box (sweep_line,
-		      left, top, do_traps, container);
+	edge_end_box (sweep_line, left, top);
+    }
-    if (right != NULL && left->x != right->x) {
+    if (left->x != right->x) {
 	left->top = top;
+	left->right = right;
+    }
+}
+/*
+ * Merge two sorted edge lists.
+ * Input:
+ *  - head_a: The head of the first list.
+ *  - head_b: The head of the second list; head_b cannot be NULL.
+ * Output:
+ * Returns the head of the merged list.
+ *
+ * Implementation notes:
+ * To make it fast (in particular, to reduce to an insertion sort whenever
+ * one of the two input lists only has a single element) we iterate through
+ * a list until its head becomes greater than the head of the other list,
+ * then we switch their roles. As soon as one of the two lists is empty, we
+ * just attach the other one to the current list and exit.
+ * Writes to memory are only needed to "switch" lists (as it also requires
+ * attaching to the output list the list which we will be iterating next) and
+ * to attach the last non-empty list.
+ */
+static edge_t *
+merge_sorted_edges (edge_t *head_a, edge_t *head_b)
+{
+    edge_t *head, *prev;
+    int32_t x;
+    prev = head_a->prev;
+    if (head_a->x <= head_b->x) {
+	head = head_a;
+    } else {
+	head_b->prev = prev;
+	head = head_b;
+	goto start_with_b;
+    }
+    do {
+	x = head_b->x;
+	while (head_a != NULL && head_a->x <= x) {
+	    prev = head_a;
+	    head_a = head_a->next;
+	}
+	head_b->prev = prev;
+	prev->next = head_b;
+	if (head_a == NULL)
+	    return head;
+start_with_b:
+	x = head_a->x;
+	while (head_b != NULL && head_b->x <= x) {
+	    prev = head_b;
+	    head_b = head_b->next;
+	}
+	head_a->prev = prev;
+	prev->next = head_a;
+	if (head_b == NULL)
+	    return head;
+    } while (1);
+}
+/*
+ * Sort (part of) a list.
+ * Input:
+ *  - list: The list to be sorted; list cannot be NULL.
+ *  - limit: Recursion limit.
+ * Output:
+ *  - head_out: The head of the sorted list containing the first 2^(level+1) elements of the
+ *              input list; if the input list has fewer elements, head_out be a sorted list
+ *              containing all the elements of the input list.
+ * Returns the head of the list of unprocessed elements (NULL if the sorted list contains
+ * all the elements of the input list).
+ *
+ * Implementation notes:
+ * Special case single element list, unroll/inline the sorting of the first two elements.
+ * Some tail recursion is used since we iterate on the bottom-up solution of the problem
+ * (we start with a small sorted list and keep merging other lists of the same size to it).
+ */
+static edge_t *
+sort_edges (edge_t  *list,
+	    unsigned int  level,
+	    edge_t **head_out)
+{
+    edge_t *head_other, *remaining;
+    unsigned int i;
+    head_other = list->next;
+    if (head_other == NULL) {
+	*head_out = list;
+	return NULL;
+    }
+    remaining = head_other->next;
+    if (list->x <= head_other->x) {
+	*head_out = list;
+	head_other->next = NULL;
+    } else {
+	*head_out = head_other;
+	head_other->prev = list->prev;
+	head_other->next = list;
+	list->prev = head_other;
+	list->next = NULL;
+    }
+    for (i = 0; i < level && remaining; i++) {
+	remaining = sort_edges (remaining, i, &head_other);
+	*head_out = merge_sorted_edges (*head_out, head_other);
+    }
+    return remaining;
+}
+static edge_t *
+merge_unsorted_edges (edge_t *head, edge_t *unsorted)
+{
+    sort_edges (unsorted, UINT_MAX, &unsorted);
+    return merge_sorted_edges (head, unsorted);
+}
+static void
+active_edges_insert (sweep_line_t *sweep)
+{
+    edge_t *prev;
+    int x;
+    x = sweep->insert_x;
+    prev = sweep->cursor;
+    if (prev->x > x) {
+	do {
+	    prev = prev->prev;
+	} while (prev->x > x);
+    } else {
+	while (prev->next->x < x)
+	    prev = prev->next;
+    }
+    prev->next = merge_unsorted_edges (prev->next, sweep->insert);
+    sweep->cursor = sweep->insert;
-	left->right = right;
+    sweep->insert = NULL;
-    }
+    sweep->insert_x = INT_MAX;
-}
 static inline void
 active_edges_to_traps (sweep_line_t	*sweep,
-		       cairo_bool_t	 do_traps,
+static inline void
-		       void		*container)
+active_edges_to_traps (sweep_line_t *sweep)
+{
+    int top = sweep->current_y;
+    edge_t *pos;
-    int top = sweep->current_y;
+    if (sweep->last_y == sweep->current_y)
-    edge_t *pos;
+	return;
-    if (sweep->last_y == sweep->current_y)
+    if (sweep->insert)
 	    winding = left->dir;
 	    right = left->next;
-	    /* Check if there is a co-linear edge with an existing trap */
-	    if (left->right == NULL) {
-		while (unlikely (right->x == left->x)) {
+	    /* Check if there is a co-linear edge with an existing trap */
+	    while (right->x == left->x) {
-		    winding += right->dir;
+		if (right->right != NULL) {
-		    if (right->right != NULL) {
+		    assert (left->right == NULL);
-			/* continuation on left */
+		    /* continuation on left */
-			left->top = right->top;
+		    left->top = right->top;
-			left->right = right->right;
-			right->right = NULL;
-			winding -= right->dir;
+		    left->right = right->right;
-			break;
+		    right->right = NULL;
+		}
 		winding += right->dir;
-		    right = right->next;
+		right = right->next;
+	    }
 	    if (winding == 0) {
 		if (left->right != NULL)
-		if (winding == 0) {
+		    edge_end_box (sweep, left, top);
-		    pos = right;
-		    continue;
-		}
-	    }
-	    /* Greedily search for the closing edge, so that we generate the
+		pos = right;
-	     * maximal span width with the minimal number of trapezoids.
+		continue;
-	     */
+	    }
-	    do {
-		/* End all subsumed traps */
+	    do {
+		/* End all subsumed traps */
+		if (unlikely (right->right != NULL))
+		    edge_end_box (sweep, right, top);
 		if (unlikely (right->right != NULL)) {
-		    edge_end_box (sweep,
-				  right, top, do_traps, container);
-		}
+		/* Greedily search for the closing edge, so that we generate
 		 * the * maximal span width with the minimal number of
-		winding += right->dir;
-		if (winding == 0) {
+		 * boxes.
-		    /* skip co-linear edges */
+		 */
-		    if (likely (right->x != right->next->x))
+		winding += right->dir;
-			break;
-		}
 		if (winding == 0 && right->x != right->next->x)
-		right = right->next;
+		    break;
 	    } while (TRUE);
 		right = right->next;
-	    edge_start_or_continue_box (sweep,
+	    } while (TRUE);
 					left, right, top,
-					do_traps, container);
+	    edge_start_or_continue_box (sweep, left, right, top);
 	    pos = right->next;
 	} while (pos != &sweep->tail);
-    } else {
-	do {
-	    edge_t *right = pos->next;
-	    int count = 0;
+    } else {
+	do {
-	    do {
+	    edge_t *right = pos->next;
-		/* End all subsumed traps */
-		if (unlikely (right->right != NULL)) {
+	    int count = 0;
 		    edge_end_box (sweep,
-				  right, top, do_traps, container);
+	    do {
-		}
-		if (++count & 1) {
+		/* End all subsumed traps */
-		    /* skip co-linear edges */
+		if (unlikely (right->right != NULL))
-		    if (likely (right->x != right->next->x))
+		    edge_end_box (sweep, right, top);
 			break;
 		    /* skip co-linear edges */
 		if (++count & 1 && right->x != right->next->x)
-		right = right->next;
+		    break;
-	    } while (TRUE);
-	    edge_start_or_continue_box (sweep,
 					pos, right, top,
-					do_traps, container);
+		right = right->next;
 	    } while (TRUE);
 	    pos = right->next;
-	} while (pos != &sweep->tail);
+	    edge_start_or_continue_box (sweep, pos, right, top);
+	    pos = right->next;
-    sweep->last_y = sweep->current_y;
+	} while (pos != &sweep->tail);
-}
-static inline void
-sweep_line_delete_edge (sweep_line_t *sweep_line,
 			edge_t *edge,
-			cairo_bool_t do_traps,
-			void *container)
-{
-    if (edge->right != NULL) {
+    sweep->last_y = sweep->current_y;
 	edge_t *next = edge->next;
 	if (next->x == edge->x) {
-	    next->top = edge->top;
+static inline void
-	    next->right = edge->right;
+sweep_line_delete_edge (sweep_line_t *sweep, edge_t *edge)
-	} else {
+{
-	    edge_end_box (sweep_line,
-			  edge,
-			  sweep_line->current_y,
-			  do_traps, container);
+    if (edge->right != NULL) {
 	edge_t *next = edge->next;
 	if (next->x == edge->x) {
 	    next->top = edge->top;
-    if (sweep_line->insert_left == edge)
+	    next->right = edge->right;
-	sweep_line->insert_left = edge->next;
+	} else
-    if (sweep_line->insert_right == edge)
+	    edge_end_box (sweep, edge, sweep->current_y);
 	sweep_line->insert_right = edge->next;
-    edge->prev->next = edge->next;
+    if (sweep->cursor == edge)
-    edge->next->prev = edge->prev;
-}
-static inline cairo_bool_t
-sweep_line_delete (sweep_line_t	*sweep,
-		   rectangle_t	*rectangle,
+	sweep->cursor = edge->prev;
 		   cairo_bool_t		 do_traps,
-		   void			*container)
+    edge->prev->next = edge->next;
     edge->next->prev = edge->prev;
-    cairo_bool_t update;
+}
-    update = TRUE;
+static inline cairo_bool_t
-    if (sweep->fill_rule == CAIRO_FILL_RULE_WINDING &&
-	rectangle->left.prev->dir == rectangle->left.dir)
-    {
-	update = rectangle->left.next != &rectangle->right;
+sweep_line_delete (sweep_line_t	*sweep, rectangle_t *rectangle)
-    }
-    sweep_line_delete_edge (sweep,
-			    &rectangle->left,
-			    do_traps, container);
-    sweep_line_delete_edge (sweep,
-			    &rectangle->right,
-			    do_traps, container);
-    pqueue_pop (&sweep->pq);
-    return update;
-}
-static inline void
-insert_edge (edge_t *edge, edge_t *pos)
+{
-{
+    cairo_bool_t update;
-    if (pos->x != edge->x) {
-	if (pos->x > edge->x) {
-	    do {
-		UNROLL3({
-		    if (pos->prev->x <= edge->x)
-			break;
-		    pos = pos->prev;
+    update = TRUE;
-		})
-	    } while (TRUE);
-	} else {
-	    do {
-		UNROLL3({
-		    pos = pos->next;
-		    if (pos->x >= edge->x)
+    if (sweep->fill_rule == CAIRO_FILL_RULE_WINDING &&
-			break;
-		})
-	    } while (TRUE);
-	}
+	rectangle->left.prev->dir == rectangle->left.dir)
-    }
-    pos->prev->next = edge;
+    {
-    edge->prev = pos->prev;
+	update = rectangle->left.next != &rectangle->right;
-    edge->next = pos;
-    pos->prev = edge;
-}
-static inline cairo_bool_t
-sweep_line_insert (sweep_line_t	*sweep,
-		   rectangle_t	*rectangle)
-{
     edge_t *pos;
-    /* right edge */
+    sweep_line_delete_edge (sweep, &rectangle->left);
-    pos = sweep->insert_right;
+    sweep_line_delete_edge (sweep, &rectangle->right);
     sweep_line_t sweep_line;
     rectangle_t *rectangle;
     cairo_status_t status;
     cairo_bool_t update = FALSE;
+    sweep_line_init (&sweep_line,
+		     rectangles, num_rectangles,
+		     fill_rule,
-    sweep_line_init (&sweep_line, rectangles, num_rectangles, fill_rule);
+		     do_traps, container);
     if ((status = setjmp (sweep_line.unwind)))
-	goto unwind;
+	return status;
     rectangle = rectangle_pop_start (&sweep_line);
     do {
 	if (rectangle->top != sweep_line.current_y) {
 	    rectangle_t *stop;
 	    stop = rectangle_peek_stop (&sweep_line);
 	    while (stop != NULL && stop->bottom < rectangle->top) {
-		if (stop->bottom != sweep_line.current_y) {
-		    if (update) {
+		if (stop->bottom != sweep_line.current_y) {
-			active_edges_to_traps (&sweep_line,
+		    if (update) {
-					       do_traps, container);
+			active_edges_to_traps (&sweep_line);
 			update = FALSE;
 		    }
 		    sweep_line.current_y = stop->bottom;
 		    sweep_line.current_y = stop->bottom;
+		}
-		update |= sweep_line_delete (&sweep_line, stop, do_traps, container);
 		update |= sweep_line_delete (&sweep_line, stop);
 		stop = rectangle_peek_stop (&sweep_line);
+	    }
+	    if (update) {
-	    if (update) {
+		active_edges_to_traps (&sweep_line);
-		active_edges_to_traps (&sweep_line, do_traps, container);
+		update = FALSE;
+	    }
+	    sweep_line.current_y = rectangle->top;
 		update = FALSE;
 	do {
-	    sweep_line.current_y = rectangle->top;
+	    sweep_line_insert (&sweep_line, rectangle);
 	} while ((rectangle = rectangle_pop_start (&sweep_line)) != NULL &&
 		 sweep_line.current_y == rectangle->top);
-	update |= sweep_line_insert (&sweep_line, rectangle);
-    } while ((rectangle = rectangle_pop_start (&sweep_line)) != NULL);
+	update = TRUE;
     } while (rectangle);
-    while ((rectangle = rectangle_peek_stop (&sweep_line)) != NULL) {
-	if (rectangle->bottom != sweep_line.current_y) {
+    while ((rectangle = rectangle_peek_stop (&sweep_line)) != NULL) {
-	    if (update) {
-		active_edges_to_traps (&sweep_line, do_traps, container);
-		update = FALSE;
+	if (rectangle->bottom != sweep_line.current_y) {
 	    if (update) {
 		active_edges_to_traps (&sweep_line);
-	    sweep_line.current_y = rectangle->bottom;
+		update = FALSE;
+	    }
 	    sweep_line.current_y = rectangle->bottom;
 	update |= sweep_line_delete (&sweep_line, rectangle, do_traps, container);
-    }
-unwind:
+	update |= sweep_line_delete (&sweep_line, rectangle);
     sweep_line_fini (&sweep_line);
     return status;
     return CAIRO_STATUS_SUCCESS;
+}
     rectangles_ptrs = stack_rectangles_ptrs;
     if (traps->num_traps > ARRAY_LENGTH (stack_rectangles)) {
 	rectangles = _cairo_malloc_ab_plus_c (traps->num_traps,
-					  sizeof (rectangle_t) +
+					      sizeof (rectangle_t) +
-					  sizeof (rectangle_t *),
+					      sizeof (rectangle_t *),
-					  sizeof (rectangle_t *));
+*sizeof (rectangle_t *));
 	if (unlikely (rectangles == NULL))
 	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 	rectangles_ptrs = (rectangle_t **) (rectangles + traps->num_traps);
 	rectangles[i].right.right = NULL;
 	rectangles[i].top = traps->traps[i].top;
 	rectangles[i].bottom = traps->traps[i].bottom;
+	rectangles_ptrs[i+2] = &rectangles[i];
+    }
-	rectangles_ptrs[i] = &rectangles[i];
+    /* XXX incremental sort */
-    }
+    _rectangle_sort (rectangles_ptrs+2, i);
     _cairo_traps_clear (traps);
-    status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs, i,
+    status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs+2, i,
 							    fill_rule,
 _cairo_bentley_ottmann_tessellate_boxes (const cairo_boxes_t *in,
 					 cairo_fill_rule_t fill_rule,
 					 cairo_boxes_t *out)
+{
     rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)];
+    rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 3];
-    rectangle_t *rectangles;
+    rectangle_t *rectangles, **rectangles_ptrs;
-    rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 1];
+    rectangle_t *stack_rectangles_chain[CAIRO_STACK_ARRAY_LENGTH (rectangle_t *) ];
-    rectangle_t **rectangles_ptrs;
+    rectangle_t **rectangles_chain = NULL;
     const struct _cairo_boxes_chunk *chunk;
     cairo_status_t status;
-    int i, j;
+    int i, j, y_min, y_max;
+    if (unlikely (in->num_boxes == 0)) {
+	_cairo_boxes_clear (out);
+	return CAIRO_STATUS_SUCCESS;
+    }
+    if (in->num_boxes == 1) {
+	if (in == out) {
+	    cairo_box_t *box = &in->chunks.base[0];
+	    if (box->p1.x > box->p2.x) {
+		cairo_fixed_t tmp = box->p1.x;
+		box->p1.x = box->p2.x;
+		box->p2.x = tmp;
+	    }
+	} else {
+	    cairo_box_t box = in->chunks.base[0];
+	    if (box.p1.x > box.p2.x) {
+		cairo_fixed_t tmp = box.p1.x;
+		box.p1.x = box.p2.x;
+		box.p2.x = tmp;
+	    }
+	    _cairo_boxes_clear (out);
+	    status = _cairo_boxes_add (out, CAIRO_ANTIALIAS_DEFAULT, &box);
+	    assert (status == CAIRO_STATUS_SUCCESS);
     if (unlikely (in->num_boxes <= 1))
+	return CAIRO_STATUS_SUCCESS;
+    }
+    y_min = INT_MAX; y_max = INT_MIN;
+    for (chunk = &in->chunks; chunk != NULL; chunk = chunk->next) {
+	const cairo_box_t *box = chunk->base;
+	for (i = 0; i < chunk->count; i++) {
+	    if (box[i].p1.y < y_min)
+		y_min = box[i].p1.y;
+	    if (box[i].p1.y > y_max)
+		y_max = box[i].p1.y;
+	}
+    }
+    y_min = _cairo_fixed_integer_floor (y_min);
+    y_max = _cairo_fixed_integer_floor (y_max) + 1;
+    y_max -= y_min;
+    if (y_max < in->num_boxes) {
+	rectangles_chain = stack_rectangles_chain;
+	if (y_max > ARRAY_LENGTH (stack_rectangles_chain)) {
+	    rectangles_chain = _cairo_malloc_ab (y_max, sizeof (rectangle_t *));
+	    if (unlikely (rectangles_chain == NULL))
+		return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+	}
+	memset (rectangles_chain, 0, y_max * sizeof (rectangle_t*));
 	return CAIRO_STATUS_SUCCESS;
     rectangles = stack_rectangles;
     rectangles_ptrs = stack_rectangles_ptrs;
     if (in->num_boxes > ARRAY_LENGTH (stack_rectangles)) {
 	rectangles = _cairo_malloc_ab_plus_c (in->num_boxes,
-					  sizeof (rectangle_t) +
+					      sizeof (rectangle_t) +
-					  sizeof (rectangle_t *),
+					      sizeof (rectangle_t *),
+*sizeof (rectangle_t *));
+	if (unlikely (rectangles == NULL)) {
-					  sizeof (rectangle_t *));
+	    if (rectangles_chain != stack_rectangles_chain)
+		free (rectangles_chain);
-	if (unlikely (rectangles == NULL))
+	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 	rectangles_ptrs = (rectangle_t **) (rectangles + in->num_boxes);
+    }
+    j = 0;
+    for (chunk = &in->chunks; chunk != NULL; chunk = chunk->next) {
-    j = 0;
+	const cairo_box_t *box = chunk->base;
-    for (chunk = &in->chunks; chunk != NULL; chunk = chunk->next) {
+	for (i = 0; i < chunk->count; i++) {
-	const cairo_box_t *box = chunk->base;
+	    int h;
 	for (i = 0; i < chunk->count; i++) {
 	    rectangles[j].right.right = NULL;
 	    rectangles[j].top = box[i].p1.y;
+	    rectangles[j].bottom = box[i].p2.y;
+	    if (rectangles_chain) {
+		h = _cairo_fixed_integer_floor (box[i].p1.y) - y_min;
+		rectangles[j].left.next = (edge_t *)rectangles_chain[h];
-	    rectangles[j].bottom = box[i].p2.y;
+		rectangles_chain[h] = &rectangles[j];
+	    } else {
 		rectangles_ptrs[j+2] = &rectangles[j];
 	    rectangles_ptrs[j] = &rectangles[j];
 	    j++;
+	}
+    }
+    if (rectangles_chain) {
+	j = 2;
+	for (y_min = 0; y_min < y_max; y_min++) {
+	    rectangle_t *r;
+	    int start = j;
+	    for (r = rectangles_chain[y_min]; r; r = (rectangle_t *)r->left.next)
+		rectangles_ptrs[j++] = r;
+	    if (j > start + 1)
+		_rectangle_sort (rectangles_ptrs + start, j - start);
+	}
+	if (rectangles_chain != stack_rectangles_chain)
+	    free (rectangles_chain);
+	j -= 2;
+    } else {
 	_rectangle_sort (rectangles_ptrs + 2, j);
     }
     _cairo_boxes_clear (out);
-    status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs, j,
+    status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs+2, j,
 							    fill_rule,

Subversion Repositories Kolibri OS

(root)/programs/develop/libraries/cairo/src/cairo-bentley-ottmann-rectangular.c – Rev 1892 → 3959