Do not preload named destinations, instead do lookup when necessary.

6 files changed, 91 insertions, 91 deletions

diff --git a/apps/common/pdfapp.c b/apps/common/pdfapp.c
index 273f536f..b24cec3d 100644
--- a/apps/common/pdfapp.c
+++ b/apps/common/pdfapp.c
@@ -131,10 +131,6 @@ void pdfapp_open(pdfapp_t *app, char *filename)
 	if (app->xref->info)
 		fz_keepobj(app->xref->info);
 
-	error = pdf_loadnametrees(app->xref);
-	if (error)
-		pdfapp_error(app, error);
-
 	error = pdf_loadoutline(&app->outline, app->xref);
 	if (error)
 		pdfapp_error(app, error);
diff --git a/apps/mozilla/moz_main.c b/apps/mozilla/moz_main.c
index 52deb38f..569d48a4 100644
--- a/apps/mozilla/moz_main.c
+++ b/apps/mozilla/moz_main.c
@@ -163,11 +163,6 @@ void pdfmoz_open(pdfmoz_t *moz, char *filename)
     if (moz->xref->info)
 	fz_keepobj(moz->xref->info);
 
-
-    error = pdf_loadnametrees(moz->xref);
-    if (error)
-	pdfmoz_error(moz, error);
-
     moz->doctitle = filename;
     if (strrchr(moz->doctitle, '\\'))
 	moz->doctitle = strrchr(moz->doctitle, '\\') + 1;
diff --git a/mupdf/mupdf.h b/mupdf/mupdf.h
index 82e83a3f..26ca8d32 100644
--- a/mupdf/mupdf.h
+++ b/mupdf/mupdf.h
@@ -113,7 +113,6 @@ struct pdf_xref_s
 	fz_obj *trailer;		/* TODO split this into root/info/encrypt/id */
 	fz_obj *root;			/* resolved catalog dict */
 	fz_obj *info;			/* resolved info dict */
-	fz_obj *dests;			/* flattened dests nametree */
 
 	int len;
 	int cap;
@@ -533,7 +532,7 @@ struct pdf_outline_s
 };
 
 fz_error pdf_loadnametree(fz_obj **dictp, pdf_xref *xref, fz_obj *root);
-fz_error pdf_loadnametrees(pdf_xref *xref);
+fz_obj *pdf_lookupdest(pdf_xref *xref, fz_obj *nameddest);
 
 fz_error pdf_newlink(pdf_link**, fz_rect rect, fz_obj *dest);
 fz_error pdf_loadlink(pdf_link **linkp, pdf_xref *xref, fz_obj *dict);
diff --git a/mupdf/pdf_annot.c b/mupdf/pdf_annot.c
index f98e0323..1749157c 100644
--- a/mupdf/pdf_annot.c
+++ b/mupdf/pdf_annot.c
@@ -37,15 +37,9 @@ pdf_droplink(pdf_link *link)
 static fz_obj *
 resolvedest(pdf_xref *xref, fz_obj *dest)
 {
-	if (fz_isname(dest))
+	if (fz_isname(dest) || fz_isstring(dest))
 	{
-		dest = fz_dictget(xref->dests, dest);
-		return resolvedest(xref, dest);
-	}
-
-	else if (fz_isstring(dest))
-	{
-		dest = fz_dictget(xref->dests, dest);
+		dest = pdf_lookupdest(xref, dest);
 		return resolvedest(xref, dest);
 	}
 
diff --git a/mupdf/pdf_nametree.c b/mupdf/pdf_nametree.c
index 8a3f7fed..add43980 100644
--- a/mupdf/pdf_nametree.c
+++ b/mupdf/pdf_nametree.c
@@ -1,100 +1,119 @@
 #include "fitz.h"
 #include "mupdf.h"
 
-static fz_error
-loadnametreenode(fz_obj *tree, pdf_xref *xref, fz_obj *node)
+static int
+destcmp(fz_obj *s1, fz_obj *s2)
 {
-	fz_error error;
-	fz_obj *names;
-	fz_obj *kids;
-	fz_obj *key;
-	fz_obj *val;
-	int i, len;
+	int l1 = fz_tostrlen(s1);
+	int l2 = fz_tostrlen(s2);
 
+	if (l1 < l2)
+		return -1;
+	if (l1 > l2)
+		return 1;
+
+	return memcmp(fz_tostrbuf(s1), fz_tostrbuf(s2), l1);
+}
+
+static int
+nametreelookup(fz_obj *node, fz_obj *nameddest, fz_obj **destp)
+{
+	fz_obj *kids, *names, *limits;
+
+	kids = fz_dictgets(node, "Kids");
 	names = fz_dictgets(node, "Names");
-	if (names)
-	{
-		len = fz_arraylen(names) / 2;
+	limits = fz_dictgets(node, "Limits");
 
-		for (i = 0; i < len; ++i)
-		{
-			key = fz_arrayget(names, i * 2 + 0);
-			val = fz_arrayget(names, i * 2 + 1);
+	*destp = nil;
 
-			error = fz_dictput(tree, key, val);
-			if (error)
-				return fz_rethrow(error, "cannot insert name tree entry");
+	if (limits && fz_isarray(limits))
+	{
+		fz_obj *first = fz_arrayget(limits, 0);
+		fz_obj *last = fz_arrayget(limits, 1);
 
-			fz_sortdict(tree);
-		}
+		if (destcmp(first, nameddest) > 0)
+			return 1;
+		if (destcmp(last, nameddest) < 0)
+			return -1;
 	}
 
-	kids = fz_dictgets(node, "Kids");
-	if (kids)
+	if (kids && fz_isarray(kids))
 	{
-		len = fz_arraylen(kids);
-		for (i = 0; i < len; ++i)
+		int l = 0;
+		int r = fz_arraylen(kids) - 1;
+
+		while (l <= r)
 		{
-			error = loadnametreenode(tree, xref, fz_arrayget(kids, i));
-			if (error)
-				return fz_rethrow(error, "cannot load name tree node");
+			int m = (l + r) >> 1;
+			int c;
+			fz_obj *kid = fz_arrayget(kids, m);
+
+			c = -nametreelookup(kid, nameddest, destp);
+			if (c < 0)
+				r = m - 1;
+			else if (c > 0)
+				l = m + 1;
+			else
+				return 0;
 		}
 	}
 
-	return fz_okay;
-}
-
-fz_error
-pdf_loadnametree(fz_obj **dictp, pdf_xref *xref, fz_obj *root)
-{
-	fz_error error;
-	fz_obj *tree;
-
-	error = fz_newdict(&tree, 128);
-	if (error)
-		return fz_rethrow(error, "cannot create name tree dictionary");
-
-	error = loadnametreenode(tree, xref, root);
-	if (error)
+	if (names && fz_isarray(names))
 	{
-		fz_dropobj(tree);
-		return fz_rethrow(error, "cannot load name tree");
-	}
+		int l = 0;
+		int r = (fz_arraylen(names) / 2) - 1;
 
-	fz_sortdict(tree);
+		while (l <= r)
+		{
+			int m = (l + r) >> 1;
+			int c;
+			fz_obj *key = fz_arrayget(names, m * 2);
+			fz_obj *val = fz_arrayget(names, m * 2 + 1);
+
+			c = -destcmp(key, nameddest);
+			if (c < 0)
+				r = m - 1;
+			else if (c > 0)
+				l = m + 1;
+			else
+			{
+				*destp = val;
+				return 0;
+			}
+		}
+	}
 
-	*dictp = tree;
-	return fz_okay;
+	return -1;
 }
 
-fz_error
-pdf_loadnametrees(pdf_xref *xref)
+fz_obj *
+pdf_lookupdest(pdf_xref *xref, fz_obj *nameddest)
 {
-	fz_error error;
-	fz_obj *names;
-	fz_obj *dests;
+	fz_obj *dests = fz_dictgets(xref->root, "Dests");
+	fz_obj *names = fz_dictgets(xref->root, "Names");
+	fz_obj *dest = nil;
 
-	/* PDF 1.1 */
-	dests = fz_dictgets(xref->root, "Dests");
+	/* PDF 1.1 has destinations in a dictionary */
 	if (dests)
 	{
-		xref->dests = fz_keepobj(dests);
-		return fz_okay;
+		if (fz_isname(nameddest))
+			dest = fz_dictget(dests, nameddest);
+		else
+			dest = fz_dictgets(dests, fz_tostrbuf(nameddest));
 	}
 
-	/* PDF 1.2 */
-	names = fz_dictgets(xref->root, "Names");
-	if (names)
+	/* PDF 1.2 has destinations in a name tree */
+	if (names && !dest)
 	{
-		dests = fz_dictgets(names, "Dests");
-		if (dests)
-		{
-			error = pdf_loadnametree(&xref->dests, xref, dests);
-			if (error)
-				return fz_rethrow(error, "cannot load name tree");
-		}
+		fz_obj *desttree = fz_dictgets(names, "Dests");
+		if (desttree)
+			nametreelookup(desttree, nameddest, &dest);
 	}
 
-	return fz_okay;
-}
+	if (fz_isdict(dest))
+		return dest;
+	else if (fz_isarray(dest))
+		return dest;
 
+	return nil;
+}
diff --git a/mupdf/pdf_xref.c b/mupdf/pdf_xref.c
index 510f1354..2966bb61 100644
--- a/mupdf/pdf_xref.c
+++ b/mupdf/pdf_xref.c
@@ -27,7 +27,6 @@ pdf_newxref(pdf_xref **xrefp)
 	xref->trailer = nil;
 	xref->root = nil;
 	xref->info = nil;
-	xref->dests = nil;
 	xref->store = nil;
 
 	xref->cap = 0;
@@ -64,8 +63,6 @@ pdf_closexref(pdf_xref *xref)
 		fz_dropobj(xref->root);
 	if (xref->info)
 		fz_dropobj(xref->info);
-	if (xref->dests)
-		fz_dropobj(xref->dests);
 	if (xref->crypt)
 		pdf_freecrypt(xref->crypt);