diff options
| author | M Joonas Pihlaja <jpihlaja@cc.helsinki.fi> | 2010-05-13 06:52:00 +0300 |
|---|---|---|
| committer | M Joonas Pihlaja <jpihlaja@cc.helsinki.fi> | 2010-05-15 08:18:18 +0300 |
| commit | 2445d5a5d4f210ce4c57c48dfb989b2a7f8e8ed7 (patch) | |
| tree | d1f3337c6b982d7a2e26674005e41bbbcfa81903 | |
| parent | 35307fc66f649cc042ec07b7b79277d7ee5987f3 (diff) | |
ordered interesectionswip/master-tor-ordered-x
| -rw-r--r-- | src/cairo-tor-scan-converter.c | 15 |
1 files changed, 10 insertions, 5 deletions
diff --git a/src/cairo-tor-scan-converter.c b/src/cairo-tor-scan-converter.c index 1f8160ec..0fa89f9d 100644 --- a/src/cairo-tor-scan-converter.c +++ b/src/cairo-tor-scan-converter.c @@ -1184,7 +1184,8 @@ active_list_init(struct active_list *active) /* Merge the edges in an unsorted list of edges into a sorted * list. The sort order is edges ascending by edge->x.quo. Returns - * the new head of the sorted list. */ + * the new head of the sorted list. This depends on the unsorted + * list being approximately in order to avoid quadratic blowup. */ static struct edge * merge_unsorted_edges(struct edge *sorted_head, struct edge *unsorted_head) { @@ -1204,8 +1205,9 @@ merge_unsorted_edges(struct edge *sorted_head, struct edge *unsorted_head) struct edge *prev = *cursor; x = unsorted_head->x.quo; - if (x < prev->x.quo) + if (x < prev->x.quo) { cursor = &sorted_head; + } while (1) { UNROLL3({ @@ -1316,6 +1318,7 @@ active_list_substep_edges( struct edge **cursor = &active->head; grid_scaled_x_t prev_x = INT_MIN; struct edge *unsorted = NULL; + struct edge **unsorted_tail = &unsorted; while (1) { struct edge *edge; @@ -1335,8 +1338,8 @@ active_list_substep_edges( if (edge->x.quo < prev_x) { *cursor = edge->next; - edge->next = unsorted; - unsorted = edge; + *unsorted_tail = edge; + unsorted_tail = &edge->next; } else { prev_x = edge->x.quo; cursor = &edge->next; @@ -1348,8 +1351,10 @@ active_list_substep_edges( }); } - if (unsorted) + if (unsorted) { + *unsorted_tail = NULL; active->head = merge_unsorted_edges(active->head, unsorted); + } } inline static glitter_status_t |