epub: Speed up css application by sorting the matched property list.

3 files changed, 51 insertions, 9 deletions

diff --git a/include/mupdf/html.h b/include/mupdf/html.h
index 8f4e5073..7a9a192d 100644
--- a/include/mupdf/html.h
+++ b/include/mupdf/html.h
@@ -8,6 +8,7 @@ typedef struct fz_html_s fz_html;
 typedef struct fz_html_flow_s fz_html_flow;
 
 typedef struct fz_css_rule_s fz_css_rule;
+typedef struct fz_css_match_prop_s fz_css_match_prop;
 typedef struct fz_css_match_s fz_css_match;
 typedef struct fz_css_style_s fz_css_style;
 
@@ -78,15 +79,18 @@ struct fz_css_value_s
 	fz_css_value *next;
 };
 
+struct fz_css_match_prop_s
+{
+	const char *name; /* not owned */
+	fz_css_value *value; /* not owned */
+	int spec;
+};
+
 struct fz_css_match_s
 {
 	fz_css_match *up;
 	int count;
-	struct {
-		const char *name; /* not owned */
-		fz_css_value *value; /* not owned */
-		int spec;
-	} prop[64];
+	fz_css_match_prop prop[64];
 };
 
 enum { DIS_NONE, DIS_BLOCK, DIS_INLINE, DIS_LIST_ITEM, DIS_INLINE_BLOCK };
diff --git a/source/html/css-apply.c b/source/html/css-apply.c
index 345a307f..f7884504 100644
--- a/source/html/css-apply.c
+++ b/source/html/css-apply.c
@@ -579,6 +579,27 @@ add_property(fz_css_match *match, const char *name, fz_css_value *value, int spe
 	++match->count;
 }
 
+static void
+sort_properties(fz_css_match *match)
+{
+	int count = match->count;
+	fz_css_match_prop *prop = match->prop;
+	int i, k;
+
+	/* Insertion sort. */
+	for (i = 1; i < count; ++i)
+	{
+		k = i;
+		while (k > 0 && strcmp(prop[k-1].name, prop[k].name) > 0)
+		{
+			fz_css_match_prop save = prop[k-1];
+			prop[k-1] = prop[k];
+			prop[k] = save;
+			--k;
+		}
+	}
+}
+
 void
 fz_match_css(fz_context *ctx, fz_css_match *match, fz_css_rule *css, fz_xml *node)
 {
@@ -623,6 +644,8 @@ fz_match_css(fz_context *ctx, fz_css_match *match, fz_css_rule *css, fz_xml *nod
 			fz_warn(ctx, "ignoring style attribute");
 		}
 	}
+
+	sort_properties(match); /* speed up subsequent value_from_raw_property lookups */
 }
 
 void
@@ -646,15 +669,27 @@ fz_match_css_at_page(fz_context *ctx, fz_css_match *match, fz_css_rule *css)
 			sel = sel->next;
 		}
 	}
+
+	sort_properties(match); /* speed up subsequent value_from_raw_property lookups */
 }
 
 static fz_css_value *
 value_from_raw_property(fz_css_match *match, const char *name)
 {
-	int i;
-	for (i = 0; i < match->count; ++i)
-		if (!strcmp(match->prop[i].name, name))
-			return match->prop[i].value;
+	fz_css_match_prop *prop = match->prop;
+	int l = 0;
+	int r = match->count - 1;
+	while (l <= r)
+	{
+		int m = (l + r) >> 1;
+		int c = strcmp(name, prop[m].name);
+		if (c < 0)
+			r = m - 1;
+		else if (c > 0)
+			l = m + 1;
+		else
+			return prop[m].value;
+	}
 	return NULL;
 }
 
diff --git a/source/html/html-layout.c b/source/html/html-layout.c
index b7e2b779..d3f80cef 100644
--- a/source/html/html-layout.c
+++ b/source/html/html-layout.c
@@ -59,6 +59,9 @@ static int iswhite(int c)
 	return c == ' ' || c == '\t' || c == '\r' || c == '\n';
 }
 
+/* TODO: pool allocator for flow nodes */
+/* TODO: store text by pointing to a giant buffer */
+
 static void fz_drop_html_flow(fz_context *ctx, fz_html_flow *flow)
 {
 	while (flow)