Add caching of rendered tiles.

This requires a slight change to the device interface.

Callers that use fz_begin_tile will see no change (and no caching
will be done). We add a new fz_begin_tile_id function that takes an
extra 'id' parameter, and returns 0 or 1. If the id is 0 then the
function behaves exactly as fz_being_tile does, and always returns 0.

The PDF and XPS code continues to call the old (uncached) version.
The display list code however generates a unique id for every
BEGIN_TILE node, and passes this in.

If the id is non zero, then it is taken to be a unique identifier
for this tile; the implementer of the fz_begin_tile_id entry point
can choose to use this to implement caching. If it chooses to ignore
the id (and do no caching), it returns 0.

If the device implements caching, then it can check on entry for a
previously rendered tile with the appropriate matrix and a matching id.
If it finds one, then it returns 1. It is the callers responsibility
to then skip over all the device calls that would usually happen to
render the tiles (i.e. to skip forward to the matching 'END_TILE'
operation).

7 files changed, 132 insertions, 9 deletions

diff --git a/fitz/base_context.c b/fitz/base_context.c
index ea67e0be..8189efb2 100644
--- a/fitz/base_context.c
+++ b/fitz/base_context.c
@@ -1,5 +1,47 @@
 #include "fitz-internal.h"
 
+struct fz_id_context_s
+{
+	int refs;
+	int id;
+};
+
+static void
+fz_drop_id_context(fz_context *ctx)
+{
+	int refs;
+	fz_id_context *id = ctx->id;
+
+	if (id == NULL)
+		return;
+	fz_lock(ctx, FZ_LOCK_ALLOC);
+	refs = --id->refs;
+	fz_unlock(ctx, FZ_LOCK_ALLOC);
+	if (refs == 0)
+		fz_free(ctx, id);
+}
+
+static void
+fz_new_id_context(fz_context *ctx)
+{
+	ctx->id = fz_malloc_struct(ctx, fz_id_context);
+	ctx->id->refs = 1;
+	ctx->id->id = 0;
+}
+
+static fz_id_context *
+fz_keep_id_context(fz_context *ctx)
+{
+	fz_id_context *id = ctx->id;
+
+	if (id == NULL)
+		return NULL;
+	fz_lock(ctx, FZ_LOCK_ALLOC);
+	++id->refs;
+	fz_unlock(ctx, FZ_LOCK_ALLOC);
+	return id;
+}
+
 void
 fz_free_context(fz_context *ctx)
 {
@@ -11,6 +53,7 @@ fz_free_context(fz_context *ctx)
 	fz_drop_store_context(ctx);
 	fz_free_aa_context(ctx);
 	fz_drop_font_context(ctx);
+	fz_drop_id_context(ctx);
 
 	if (ctx->warn)
 	{
@@ -96,6 +139,7 @@ fz_new_context(fz_alloc_context *alloc, fz_locks_context *locks, unsigned int ma
 		fz_new_store_context(ctx, max_store);
 		fz_new_glyph_cache_context(ctx);
 		fz_new_font_context(ctx);
+		fz_new_id_context(ctx);
 	}
 	fz_catch(ctx)
 	{
@@ -138,6 +182,24 @@ fz_clone_context_internal(fz_context *ctx)
 	new_ctx->glyph_cache = fz_keep_glyph_cache(new_ctx);
 	new_ctx->font = ctx->font;
 	new_ctx->font = fz_keep_font_context(new_ctx);
+	new_ctx->id = ctx->id;
+	new_ctx->id = fz_keep_id_context(new_ctx);
 
 	return new_ctx;
 }
+
+int
+fz_gen_id(fz_context *ctx)
+{
+	int id;
+	fz_lock(ctx, FZ_LOCK_ALLOC);
+	/* We'll never wrap around in normal use, but if we *do*, then avoid
+	 * 0. */
+	do
+	{
+		id = ++ctx->id->id;
+	}
+	while (id == 0);
+	fz_unlock(ctx, FZ_LOCK_ALLOC);
+	return id;
+}
diff --git a/fitz/dev_list.c b/fitz/dev_list.c
index 69596e48..69542677 100644
--- a/fitz/dev_list.c
+++ b/fitz/dev_list.c
@@ -77,7 +77,7 @@ fz_new_display_node(fz_context *ctx, fz_display_command cmd, const fz_matrix *ct
 	node->rect = fz_empty_rect;
 	node->item.path = NULL;
 	node->stroke = NULL;
-	node->flag = 0;
+	node->flag = (cmd == FZ_CMD_BEGIN_TILE ? fz_gen_id(ctx) : 0);
 	node->ctm = *ctm;
 	if (colorspace)
 	{
@@ -504,9 +504,10 @@ fz_list_end_group(fz_device *dev)
 	fz_append_display_node(dev->user, node);
 }
 
-static void
-fz_list_begin_tile(fz_device *dev, const fz_rect *area, const fz_rect *view, float xstep, float ystep, const fz_matrix *ctm)
+static int
+fz_list_begin_tile(fz_device *dev, const fz_rect *area, const fz_rect *view, float xstep, float ystep, const fz_matrix *ctm, int id)
 {
+	/* We ignore id here, as we will pass on our own id */
 	fz_display_node *node;
 	node = fz_new_display_node(dev->ctx, FZ_CMD_BEGIN_TILE, ctm, NULL, NULL, 0);
 	node->rect = *area;
@@ -517,6 +518,7 @@ fz_list_begin_tile(fz_device *dev, const fz_rect *area, const fz_rect *view, flo
 	node->color[4] = view->x1;
 	node->color[5] = view->y1;
 	fz_append_display_node(dev->user, node);
+	return 0;
 }
 
 static void
@@ -590,6 +592,36 @@ fz_free_display_list(fz_context *ctx, fz_display_list *list)
 	fz_free(ctx, list);
 }
 
+static fz_display_node *
+skip_to_end_tile(fz_display_node *node, int *progress)
+{
+	fz_display_node *next;
+	int depth = 1;
+
+	/* Skip through until we find the matching end_tile. Note that
+	 * (somewhat nastily) we return the PREVIOUS node to this to help
+	 * the calling routine. */
+	do
+	{
+		next = node->next;
+		if (next == NULL)
+			break;
+		if (next->cmd == FZ_CMD_BEGIN_TILE)
+			depth++;
+		else if (next->cmd == FZ_CMD_END_TILE)
+		{
+			depth--;
+			if (depth == 0)
+				return node;
+		}
+		(*progress)++;
+		node = next;
+	}
+	while (1);
+
+	return NULL;
+}
+
 void
 fz_run_display_list(fz_display_list *list, fz_device *dev, const fz_matrix *top_ctm, const fz_rect *scissor, fz_cookie *cookie)
 {
@@ -755,13 +787,18 @@ visible:
 				break;
 			case FZ_CMD_BEGIN_TILE:
 			{
+				int cached;
 				fz_rect rect;
 				tiled++;
 				rect.x0 = node->color[2];
 				rect.y0 = node->color[3];
 				rect.x1 = node->color[4];
 				rect.y1 = node->color[5];
-				fz_begin_tile(dev, &node->rect, &rect, node->color[0], node->color[1], &ctm);
+				cached = fz_begin_tile_id(dev, &node->rect, &rect, node->color[0], node->color[1], &ctm, node->flag);
+				if (cached)
+				{
+					node = skip_to_end_tile(node, &progress);
+				}
 				break;
 			}
 			case FZ_CMD_END_TILE:
diff --git a/fitz/dev_null.c b/fitz/dev_null.c
index e7d31fdf..af9e2c64 100644
--- a/fitz/dev_null.c
+++ b/fitz/dev_null.c
@@ -313,18 +313,25 @@ fz_end_group(fz_device *dev)
 void
 fz_begin_tile(fz_device *dev, const fz_rect *area, const fz_rect *view, float xstep, float ystep, const fz_matrix *ctm)
 {
+	(void)fz_begin_tile_id(dev, area, view, xstep, ystep, ctm, 0);
+}
+
+int
+fz_begin_tile_id(fz_device *dev, const fz_rect *area, const fz_rect *view, float xstep, float ystep, const fz_matrix *ctm, int id)
+{
 	fz_context *ctx = dev->ctx;
+	int ret = 0;
 
 	if (dev->error_depth)
 	{
 		dev->error_depth++;
-		return;
+		return 0;
 	}
 
 	fz_try(ctx)
 	{
 		if (dev->begin_tile)
-			dev->begin_tile(dev, area, view, xstep, ystep, ctm);
+			ret = dev->begin_tile(dev, area, view, xstep, ystep, ctm, id);
 	}
 	fz_catch(ctx)
 	{
@@ -332,6 +339,7 @@ fz_begin_tile(fz_device *dev, const fz_rect *area, const fz_rect *view, float xs
 		strcpy(dev->errmess, fz_caught(ctx));
 		/* Error swallowed */
 	}
+	return ret;
 }
 
 void
diff --git a/fitz/dev_trace.c b/fitz/dev_trace.c
index c3c17021..88b445a2 100644
--- a/fitz/dev_trace.c
+++ b/fitz/dev_trace.c
@@ -267,8 +267,8 @@ fz_trace_end_group(fz_device *dev)
 	printf("</group>\n");
 }
 
-static void
-fz_trace_begin_tile(fz_device *dev, const fz_rect *area, const fz_rect *view, float xstep, float ystep, const fz_matrix *ctm)
+static int
+fz_trace_begin_tile(fz_device *dev, const fz_rect *area, const fz_rect *view, float xstep, float ystep, const fz_matrix *ctm, int id)
 {
 	printf("<tile");
 	printf(" area=\"%g %g %g %g\"", area->x0, area->y0, area->x1, area->y1);
@@ -276,6 +276,7 @@ fz_trace_begin_tile(fz_device *dev, const fz_rect *area, const fz_rect *view, fl
 	printf(" xstep=\"%g\" ystep=\"%g\"", xstep, ystep);
 	fz_trace_matrix(ctm);
 	printf(">\n");
+	return 0;
 }
 
 static void
diff --git a/fitz/fitz-internal.h b/fitz/fitz-internal.h
index 00c59cc5..b76510cf 100644
--- a/fitz/fitz-internal.h
+++ b/fitz/fitz-internal.h
@@ -473,6 +473,11 @@ struct fz_store_hash_s
 			void *ptr;
 			int i;
 		} pi;
+		struct
+		{
+			int id;
+			float m[4];
+		} im;
 	} u;
 };
 
@@ -1440,7 +1445,7 @@ struct fz_device_s
 	void (*begin_group)(fz_device *, const fz_rect *, int isolated, int knockout, int blendmode, float alpha);
 	void (*end_group)(fz_device *);
 
-	void (*begin_tile)(fz_device *, const fz_rect *area, const fz_rect *view, float xstep, float ystep, const fz_matrix *ctm);
+	int (*begin_tile)(fz_device *, const fz_rect *area, const fz_rect *view, float xstep, float ystep, const fz_matrix *ctm, int id);
 	void (*end_tile)(fz_device *);
 
 	int error_depth;
@@ -1466,6 +1471,7 @@ void fz_end_mask(fz_device *dev);
 void fz_begin_group(fz_device *dev, const fz_rect *area, int isolated, int knockout, int blendmode, float alpha);
 void fz_end_group(fz_device *dev);
 void fz_begin_tile(fz_device *dev, const fz_rect *area, const fz_rect *view, float xstep, float ystep, const fz_matrix *ctm);
+int fz_begin_tile_id(fz_device *dev, const fz_rect *area, const fz_rect *view, float xstep, float ystep, const fz_matrix *ctm, int id);
 void fz_end_tile(fz_device *dev);
 
 fz_device *fz_new_device(fz_context *ctx, void *user);
diff --git a/fitz/fitz.h b/fitz/fitz.h
index 294ab958..47f61f39 100644
--- a/fitz/fitz.h
+++ b/fitz/fitz.h
@@ -201,6 +201,7 @@ static inline void *fz_clampp(void *p, void *min, void *max)
 
 typedef struct fz_alloc_context_s fz_alloc_context;
 typedef struct fz_error_context_s fz_error_context;
+typedef struct fz_id_context_s fz_id_context;
 typedef struct fz_warn_context_s fz_warn_context;
 typedef struct fz_font_context_s fz_font_context;
 typedef struct fz_aa_context_s fz_aa_context;
@@ -294,6 +295,7 @@ struct fz_context_s
 {
 	fz_alloc_context *alloc;
 	fz_locks_context *locks;
+	fz_id_context *id;
 	fz_error_context *error;
 	fz_warn_context *warn;
 	fz_font_context *font;
@@ -664,6 +666,12 @@ int fz_runetochar(char *str, int rune);
 int fz_runelen(int rune);
 
 /*
+	fz_gen_id: Generate an id (guaranteed unique within this family of
+	contexts).
+*/
+int fz_gen_id(fz_context *ctx);
+
+/*
 	getopt: Simple functions/variables for use in tools.
 */
 extern int fz_getopt(int nargc, char * const *nargv, const char *ostr);
diff --git a/fitz/res_store.c b/fitz/res_store.c
index c8c1ed5f..a7d780b2 100644
--- a/fitz/res_store.c
+++ b/fitz/res_store.c
@@ -271,6 +271,7 @@ fz_store_item(fz_context *ctx, void *key, void *val_, unsigned int itemsize, fz_
 				existing->val->refs++;
 			fz_unlock(ctx, FZ_LOCK_ALLOC);
 			fz_free(ctx, item);
+			type->drop_key(ctx, key);
 			return existing->val;
 		}
 	}