[cairo-commit] 2 commits - src/cairo-bentley-ottmann.c src/cairo-combsort-private.h src/Makefile.sources
Chris Wilson
ickle at kemper.freedesktop.org
Thu Oct 30 12:08:35 PDT 2008
src/Makefile.sources | 1
src/cairo-bentley-ottmann.c | 71 +++++++++++++++++++++----------------------
src/cairo-combsort-private.h | 71 +++++++++++++++++++++++++++++++++++++++++++
3 files changed, 108 insertions(+), 35 deletions(-)
New commits:
commit 52c3fc58b52c77282998f9ad75657a6bec5956f8
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Wed Oct 8 13:04:37 2008 +0100
[tessellator] Simplify dequeuing by using a sentinel value.
Instead of maintaining an index and comparing it to the count, just mark
the last startstop event with NULL and stop dequeuing events upon seeing
that sentinel value. (Removes an unreadable line, and cachegrind hints
that it may be a tiny bit faster.)
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 1d019c8..1dd7b21 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -129,8 +129,6 @@ typedef struct _cairo_bo_event_queue {
cairo_bo_event_t *startstop_events;
cairo_bo_event_t **sorted_startstop_event_ptrs;
- unsigned next_startstop_event_index;
- unsigned num_startstop_events;
} cairo_bo_event_queue_t;
/* This structure extends #cairo_skip_list_t, which must come first. */
@@ -942,16 +940,17 @@ _cairo_bo_event_dequeue (cairo_bo_event_queue_t *event_queue)
cairo_bo_event_t *intersection = elt ? SKIP_ELT_TO_EVENT (elt) : NULL;
cairo_bo_event_t *startstop;
- if (event_queue->next_startstop_event_index == event_queue->num_startstop_events)
+ startstop = *event_queue->sorted_startstop_event_ptrs;
+ if (startstop == NULL)
return intersection;
- startstop = event_queue->sorted_startstop_event_ptrs[
- event_queue->next_startstop_event_index];
- if (!intersection || cairo_bo_event_compare (startstop, intersection) <= 0)
+ if (intersection == NULL ||
+ cairo_bo_event_compare (startstop, intersection) <= 0)
{
- event_queue->next_startstop_event_index++;
+ event_queue->sorted_startstop_event_ptrs++;
return startstop;
}
+
return intersection;
}
@@ -968,27 +967,24 @@ _cairo_bo_event_queue_init (cairo_bo_event_queue_t *event_queue,
cairo_bo_event_t *events, **sorted_event_ptrs;
unsigned num_events = 2*num_edges;
- memset (event_queue, 0, sizeof(*event_queue));
-
_cairo_skip_list_init (&event_queue->intersection_queue,
- cairo_bo_event_compare_abstract,
- sizeof (cairo_bo_event_t));
- if (0 == num_edges)
- return CAIRO_STATUS_SUCCESS;
+ cairo_bo_event_compare_abstract,
+ sizeof (cairo_bo_event_t));
/* The skip_elt_t field of a cairo_bo_event_t isn't used for start
* or stop events, so this allocation is safe. XXX: make the
* event type a union so it doesn't always contain the skip
* elt? */
- events = _cairo_malloc_ab (num_events, sizeof (cairo_bo_event_t) + sizeof(cairo_bo_event_t*));
+ events = _cairo_malloc_ab_plus_c (num_events,
+ sizeof (cairo_bo_event_t) +
+ sizeof (cairo_bo_event_t *),
+ sizeof (cairo_bo_event_t *));
if (events == NULL)
return _cairo_error (CAIRO_STATUS_NO_MEMORY);
sorted_event_ptrs = (cairo_bo_event_t **) (events + num_events);
event_queue->startstop_events = events;
event_queue->sorted_startstop_event_ptrs = sorted_event_ptrs;
- event_queue->num_startstop_events = num_events;
- event_queue->next_startstop_event_index = 0;
for (i = 0; i < num_edges; i++) {
sorted_event_ptrs[i] = &events[2*i];
@@ -1009,6 +1005,7 @@ _cairo_bo_event_queue_init (cairo_bo_event_queue_t *event_queue,
}
_cairo_bo_event_queue_sort (sorted_event_ptrs, num_events);
+ event_queue->sorted_startstop_event_ptrs[num_events] = NULL;
return CAIRO_STATUS_SUCCESS;
}
@@ -1494,6 +1491,9 @@ _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_edge_t *edges,
cairo_bo_edge_t *left, *right;
cairo_bo_edge_t *edge1, *edge2;
+ if (num_edges == 0)
+ return CAIRO_STATUS_SUCCESS;
+
status = _cairo_bo_event_queue_init (&event_queue, edges, num_edges);
if (status)
return status;
commit ef9e0a5d1d74ac92a1fcde5a657c866a8e6509e6
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Tue Oct 7 22:09:37 2008 +0100
[tessellator] Use a combsort for sorting the event queue.
In my experiments using cairo-perf, the inlined combsort is ~20% quicker
than the library qsort.
diff --git a/src/Makefile.sources b/src/Makefile.sources
index 7d6bfd6..082b6af 100644
--- a/src/Makefile.sources
+++ b/src/Makefile.sources
@@ -57,6 +57,7 @@ cairo_private = \
cairo-atomic-private.h \
cairo-cache-private.h \
cairo-clip-private.h \
+ cairo-combsort-private.h \
cairo-compiler-private.h \
cairo-fixed-private.h \
cairo-fixed-type-private.h \
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 2d8e324..1d019c8 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -38,6 +38,7 @@
#include "cairo-skiplist-private.h"
#include "cairo-freelist-private.h"
+#include "cairo-combsort-private.h"
#define DEBUG_VALIDATE 0
#define DEBUG_PRINT_STATE 0
@@ -630,21 +631,18 @@ cairo_bo_event_compare_abstract (void *list,
}
static int
-cairo_bo_event_compare_pointers (void const *voida,
- void const *voidb)
+cairo_bo_event_compare_pointers (const cairo_bo_event_t *a,
+ const cairo_bo_event_t *b)
{
- cairo_bo_event_t const * const *a = voida;
- cairo_bo_event_t const * const *b = voidb;
- if (*a != *b) {
- int cmp = cairo_bo_event_compare (*a, *b);
- if (cmp)
- return cmp;
- if (*a < *b)
- return -1;
- if (*a > *b)
- return +1;
- }
- return 0;
+ int cmp;
+
+ if (a == b)
+ return 0;
+ cmp = cairo_bo_event_compare (a, b);
+ if (cmp)
+ return cmp;
+
+ return a - b;
}
static inline cairo_int64_t
@@ -957,6 +955,10 @@ _cairo_bo_event_dequeue (cairo_bo_event_queue_t *event_queue)
return intersection;
}
+CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort,
+ cairo_bo_event_t *,
+ cairo_bo_event_compare_pointers)
+
static cairo_status_t
_cairo_bo_event_queue_init (cairo_bo_event_queue_t *event_queue,
cairo_bo_edge_t *edges,
@@ -989,8 +991,8 @@ _cairo_bo_event_queue_init (cairo_bo_event_queue_t *event_queue,
event_queue->next_startstop_event_index = 0;
for (i = 0; i < num_edges; i++) {
- sorted_event_ptrs[2*i] = &events[2*i];
- sorted_event_ptrs[2*i+1] = &events[2*i+1];
+ sorted_event_ptrs[i] = &events[2*i];
+ sorted_event_ptrs[i+num_edges] = &events[2*i+1];
/* Initialize "middle" to top */
edges[i].middle = edges[i].top;
@@ -1006,9 +1008,8 @@ _cairo_bo_event_queue_init (cairo_bo_event_queue_t *event_queue,
edges[i].bottom);
}
- qsort (sorted_event_ptrs, num_events,
- sizeof(cairo_bo_event_t *),
- cairo_bo_event_compare_pointers);
+ _cairo_bo_event_queue_sort (sorted_event_ptrs, num_events);
+
return CAIRO_STATUS_SUCCESS;
}
diff --git a/src/cairo-combsort-private.h b/src/cairo-combsort-private.h
new file mode 100644
index 0000000..d2fbb72
--- /dev/null
+++ b/src/cairo-combsort-private.h
@@ -0,0 +1,71 @@
+/*
+ * Copyright © 2008 Chris Wilson
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * The Initial Developer of the Original Code is Chris Wilson
+ *
+ * Contributor(s):
+ * Chris Wilson <chris at chris-wilson.co.uk>
+ */
+
+/* This fragment implements a comb sort (specifically combsort11) */
+#ifndef _HAVE_CAIRO_COMBSORT_NEWGAP
+#define _HAVE_CAIRO_COMBSORT_NEWGAP
+static inline unsigned int
+_cairo_combsort_newgap (unsigned int gap)
+{
+ gap = 10 * gap / 13;
+ if (gap == 9 || gap == 10)
+ gap = 11;
+ if (gap < 1)
+ gap = 1;
+ return gap;
+}
+#endif
+
+#define CAIRO_COMBSORT_DECLARE(NAME, TYPE, CMP) \
+static void \
+NAME (TYPE *base, unsigned int nmemb) \
+{ \
+ unsigned int gap = nmemb; \
+ unsigned int i, j; \
+ int swapped; \
+ do { \
+ gap = _cairo_combsort_newgap (gap); \
+ swapped = 0; \
+ for (i = 0; i < nmemb-gap ; i++) { \
+ j = i + gap; \
+ if (CMP (base[i], base[j]) > 0 ) { \
+ TYPE tmp; \
+ tmp = base[i]; \
+ base[i] = base[j]; \
+ base[j] = tmp; \
+ swapped = 1; \
+ } \
+ } \
+ } while (gap > 1 || swapped); \
+}
More information about the cairo-commit
mailing list