pdf_dict_find optimisation.

When doing pdf_dict_put, we first call pdf_dict_find to hunt for an
existing entry we can just update.

Recently we introduced a 'location' return from pdf_dict_find that
would (in the non-found case) return the location of where such an
entry should be inserted.

It's just dawned on me that we don't need a separate variable for
this. We continue to return negative numbers for 'not found', but
these negative numbers can contain the insertion point.

1 files changed, 25 insertions, 36 deletions

diff --git a/source/pdf/pdf-object.c b/source/pdf/pdf-object.c
index 0ebff26d..72d79c8b 100644
--- a/source/pdf/pdf-object.c
+++ b/source/pdf/pdf-object.c
@@ -1016,19 +1016,20 @@ pdf_dict_put_val_drop(fz_context *ctx, pdf_obj *obj, int i, pdf_obj *new_obj)
 	DICT(obj)->items[i].v = new_obj;
 }
 
+/* Returns 0 <= i < len for key found. Returns -1-len < i <= -1 for key
+ * not found, but with insertion point -1-i. */
 static int
-pdf_dict_finds(fz_context *ctx, pdf_obj *obj, const char *key, int *location)
+pdf_dict_finds(fz_context *ctx, pdf_obj *obj, const char *key)
 {
-	if ((obj->flags & PDF_FLAGS_SORTED) && DICT(obj)->len > 0)
+	int len = DICT(obj)->len;
+	if ((obj->flags & PDF_FLAGS_SORTED) && len > 0)
 	{
 		int l = 0;
-		int r = DICT(obj)->len - 1;
+		int r = len - 1;
 
 		if (strcmp(pdf_to_name(ctx, DICT(obj)->items[r].k), key) < 0)
 		{
-			if (location)
-				*location = r + 1;
-			return -1;
+			return -1 - (r+1);
 		}
 
 		while (l <= r)
@@ -1041,40 +1042,34 @@ pdf_dict_finds(fz_context *ctx, pdf_obj *obj, const char *key, int *location)
 				l = m + 1;
 			else
 				return m;
-
-			if (location)
-				*location = l;
 		}
+		return -1 - l;
 	}
 
 	else
 	{
 		int i;
-		for (i = 0; i < DICT(obj)->len; i++)
+		for (i = 0; i < len; i++)
 			if (strcmp(pdf_to_name(ctx, DICT(obj)->items[i].k), key) == 0)
 				return i;
 
-		if (location)
-			*location = DICT(obj)->len;
+		return -1 - len;
 	}
-
-	return -1;
 }
 
 static int
-pdf_dict_find(fz_context *ctx, pdf_obj *obj, pdf_obj *key, int *location)
+pdf_dict_find(fz_context *ctx, pdf_obj *obj, pdf_obj *key)
 {
-	if ((obj->flags & PDF_FLAGS_SORTED) && DICT(obj)->len > 0)
+	int len = DICT(obj)->len;
+	if ((obj->flags & PDF_FLAGS_SORTED) && len > 0)
 	{
 		int l = 0;
-		int r = DICT(obj)->len - 1;
+		int r = len - 1;
 		pdf_obj *k = DICT(obj)->items[r].k;
 
 		if (k == key || (k >= PDF_OBJ__LIMIT && strcmp(NAME(k)->n, PDF_NAMES[(intptr_t)key]) < 0))
 		{
-			if (location)
-				*location = r + 1;
-			return -1;
+			return -1 - (r+1);
 		}
 
 		while (l <= r)
@@ -1090,15 +1085,13 @@ pdf_dict_find(fz_context *ctx, pdf_obj *obj, pdf_obj *key, int *location)
 				l = m + 1;
 			else
 				return m;
-
-			if (location)
-				*location = l;
 		}
+		return -1 - l;
 	}
 	else
 	{
 		int i;
-		for (i = 0; i < DICT(obj)->len; i++)
+		for (i = 0; i < len; i++)
 		{
 			pdf_obj *k = DICT(obj)->items[i].k;
 			if (k < PDF_OBJ__LIMIT)
@@ -1113,11 +1106,8 @@ pdf_dict_find(fz_context *ctx, pdf_obj *obj, pdf_obj *key, int *location)
 			}
 		}
 
-		if (location)
-			*location = DICT(obj)->len;
+		return -1 - len;
 	}
-
-	return -1;
 }
 
 pdf_obj *
@@ -1129,7 +1119,7 @@ pdf_dict_gets(fz_context *ctx, pdf_obj *obj, const char *key)
 	if (obj < PDF_OBJ__LIMIT || obj->kind != PDF_DICT)
 		return NULL;
 
-	i = pdf_dict_finds(ctx, obj, key, NULL);
+	i = pdf_dict_finds(ctx, obj, key);
 	if (i >= 0)
 		return DICT(obj)->items[i].v;
 
@@ -1198,9 +1188,9 @@ pdf_dict_get(fz_context *ctx, pdf_obj *obj, pdf_obj *key)
 		return NULL;
 
 	if (key < PDF_OBJ__LIMIT)
-		i = pdf_dict_find(ctx, obj, key, NULL);
+		i = pdf_dict_find(ctx, obj, key);
 	else
-		i = pdf_dict_finds(ctx, obj, pdf_to_name(ctx, key), NULL);
+		i = pdf_dict_finds(ctx, obj, pdf_to_name(ctx, key));
 	if (i >= 0)
 		return DICT(obj)->items[i].v;
 	return NULL;
@@ -1232,7 +1222,6 @@ pdf_dict_put(fz_context *ctx, pdf_obj *obj, pdf_obj *key, pdf_obj *val)
 	RESOLVE(obj);
 	if (obj >= PDF_OBJ__LIMIT)
 	{
-		int location;
 		int i;
 
 		if (obj->kind != PDF_DICT)
@@ -1258,9 +1247,9 @@ pdf_dict_put(fz_context *ctx, pdf_obj *obj, pdf_obj *key, pdf_obj *val)
 			pdf_sort_dict(ctx, obj);
 
 		if (key < PDF_OBJ__LIMIT)
-			i = pdf_dict_find(ctx, obj, key, &location);
+			i = pdf_dict_find(ctx, obj, key);
 		else
-			i = pdf_dict_finds(ctx, obj, pdf_to_name(ctx, key), &location);
+			i = pdf_dict_finds(ctx, obj, pdf_to_name(ctx, key));
 		if (i >= 0 && i < DICT(obj)->len)
 		{
 			if (DICT(obj)->items[i].v != val)
@@ -1275,7 +1264,7 @@ pdf_dict_put(fz_context *ctx, pdf_obj *obj, pdf_obj *key, pdf_obj *val)
 			if (DICT(obj)->len + 1 > DICT(obj)->cap)
 				pdf_dict_grow(ctx, obj);
 
-			i = location;
+			i = -1-i;
 			if ((obj->flags & PDF_FLAGS_SORTED) && DICT(obj)->len > 0)
 				memmove(&DICT(obj)->items[i + 1],
 						&DICT(obj)->items[i],
@@ -1509,7 +1498,7 @@ pdf_dict_dels(fz_context *ctx, pdf_obj *obj, const char *key)
 			fz_warn(ctx, "assert: not a dict (%s)", pdf_objkindstr(obj));
 		else
 		{
-			int i = pdf_dict_finds(ctx, obj, key, NULL);
+			int i = pdf_dict_finds(ctx, obj, key);
 			if (i >= 0)
 			{
 				pdf_drop_obj(ctx, DICT(obj)->items[i].k);