diff options
| -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 |