Change xref representation to cope better with sparse xrefs.

Currently each xref in the file results in an array from 0 to
num_objects. If we have a file that has been updated many times
this causes a huge waste of memory.

Instead we now hold each xref as a list of non-overlapping subsections
(exactly as the file holds them).

Lookup is therefore potentially slower, but only on files where the
xrefs are highly fragmented (i.e. where we would be saving in memory
terms).

Some parts of our code (notably the file writing code that does
garbage collection etc) assumes that lookups of object entry pointers
will not change previous object entry pointers that have been
looked up. To cope with this, and to cope with the case where we are
updating/creating new objects, we introduce the idea of a 'solid'
xref.

A solid xref is one where it has a single subsection record that spans
the entire range of valid object numbers for a file. Once we have
ensured that an xref is 'solid', we can safely work on the pointers
within it without fear of them moving.

We ensure that any 'incremental' xref is solid.

We also ensure that any non-incremental write makes the xref solid.

1 files changed, 12 insertions, 2 deletions

diff --git a/include/mupdf/pdf/xref.h b/include/mupdf/pdf/xref.h
index 27b656d7..70826314 100644
--- a/include/mupdf/pdf/xref.h
+++ b/include/mupdf/pdf/xref.h
@@ -48,10 +48,20 @@ enum
 	PDF_OBJ_FLAG_MARK = 1,
 };
 
-struct pdf_xref_s
+typedef struct pdf_xref_subsec_s pdf_xref_subsec;
+
+struct pdf_xref_subsec_s
 {
+	pdf_xref_subsec *next;
 	int len;
+	int start;
 	pdf_xref_entry *table;
+};
+
+struct pdf_xref_s
+{
+	int num_objects;
+	pdf_xref_subsec *subsec;
 	pdf_obj *trailer;
 	pdf_obj *pre_repair_trailer;
 };
@@ -89,7 +99,7 @@ int pdf_xref_is_incremental(pdf_document *doc, int num);
 void pdf_repair_xref(pdf_document *doc, pdf_lexbuf *buf);
 void pdf_repair_obj_stms(pdf_document *doc);
 pdf_obj *pdf_new_ref(pdf_document *doc, pdf_obj *obj);
-
+void pdf_ensure_solid_xref(pdf_document *doc, int num);
 void pdf_mark_xref(pdf_document *doc);
 void pdf_clear_xref(pdf_document *doc);
 void pdf_clear_xref_to_mark(pdf_document *doc);