summaryrefslogtreecommitdiff
path: root/source/fitz
diff options
context:
space:
mode:
authorTor Andersson <tor.andersson@artifex.com>2014-05-22 14:03:24 +0200
committerTor Andersson <tor.andersson@artifex.com>2014-05-22 14:03:24 +0200
commit3c4bd6130b6e2ff423e38654e0dcc8502f22274a (patch)
treee2d03bc59468953b6503fe5da1400346fda8c70d /source/fitz
parent2191d24236c6e2283521a4013dbca2b4feb6c6e7 (diff)
downloadmupdf-3c4bd6130b6e2ff423e38654e0dcc8502f22274a.tar.xz
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.
Diffstat (limited to 'source/fitz')
-rw-r--r--source/fitz/draw-edge.c20
1 files changed, 17 insertions, 3 deletions
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;
}
}