From 3c4bd6130b6e2ff423e38654e0dcc8502f22274a Mon Sep 17 00:00:00 2001 From: Tor Andersson Date: Thu, 22 May 2014 14:03:24 +0200 Subject: Fix 695247: Use exponential realloc pattern and qsort for huge paths. Grow the edge list using an exponential realloc pattern. Use qsort for huge paths and only fall back to the simple shell sort for small paths. --- source/fitz/draw-edge.c | 20 +++++++++++++++++--- 1 file changed, 17 insertions(+), 3 deletions(-) (limited to 'source') diff --git a/source/fitz/draw-edge.c b/source/fitz/draw-edge.c index 769116ac..c8d94155 100644 --- a/source/fitz/draw-edge.c +++ b/source/fitz/draw-edge.c @@ -326,7 +326,7 @@ fz_insert_gel_raw(fz_gel *gel, int x0, int y0, int x1, int y1) if (y1 > gel->bbox.y1) gel->bbox.y1 = y1; if (gel->len + 1 == gel->cap) { - int new_cap = gel->cap + 512; + int new_cap = gel->cap * 2; gel->edges = fz_resize_array(gel->ctx, gel->edges, new_cap, sizeof(fz_edge)); gel->cap = new_cap; } @@ -427,15 +427,30 @@ fz_insert_gel(fz_gel *gel, float fx0, float fy0, float fx1, float fy1) fz_insert_gel_raw(gel, x0, y0, x1, y1); } +static int cmpedge(const void *va, const void *vb) +{ + const fz_edge *a = va; + const fz_edge *b = vb; + return a->y - b->y; +} + void fz_sort_gel(fz_gel *gel) { fz_edge *a = gel->edges; int n = gel->len; - int h, i, k; fz_edge t; + + /* quick sort for long lists */ + if (n > 10000) + { + qsort(a, n, sizeof *a, cmpedge); + return; + } + + /* shell sort for short lists */ h = 1; if (n < 14) { h = 1; @@ -459,7 +474,6 @@ fz_sort_gel(fz_gel *gel) } a[k + h] = t; } - h /= 3; } } -- cgit v1.2.3