core: Add JSON node, object, array hashes

Now that these objects can be marked as immutable, it is possible to
calculate and cache hash values for each of them. This allows efficient
hash-based deduplication of large numbers of JSON nodes, as needed by
Walbottle for JSON test vector generation.

To complement the new hash functions, each of JsonNode, JsonValue,
JsonObject and JsonArray also now have an equal() comparison method.
This compares them structurally and recursively, using the definition of
equality from the JSON Schema specification, which seems as good as any
other.

http://json-schema.org/latest/json-schema-core.html#anchor9

https://bugzilla.gnome.org/show_bug.cgi?id=756121

Signed-off-by: Emmanuele Bassi <ebassi@gnome.org>

1 files changed, 97 insertions, 7 deletions

diff --git a/json-glib/json-array.c b/json-glib/json-array.c
index cc9c979..c861b8e 100644
--- a/json-glib/json-array.c
+++ b/json-glib/json-array.c
@@ -159,6 +159,7 @@ json_array_seal (JsonArray *array)
   for (i = 0; i < array->elements->len; i++)
     json_node_seal (g_ptr_array_index (array->elements, i));
 
+  array->immutable_hash = json_array_hash (array);
   array->immutable = TRUE;
 }
 
@@ -535,7 +536,7 @@ json_array_add_int_element (JsonArray *array,
 {
   g_return_if_fail (array != NULL);
 
-  g_ptr_array_add (array->elements, json_node_init_int (json_node_alloc (), value));
+  json_array_add_element (array, json_node_init_int (json_node_alloc (), value));
 }
 
 /**
@@ -555,7 +556,7 @@ json_array_add_double_element (JsonArray *array,
 {
   g_return_if_fail (array != NULL);
 
-  g_ptr_array_add (array->elements, json_node_init_double (json_node_alloc (), value));
+  json_array_add_element (array, json_node_init_double (json_node_alloc (), value));
 }
 
 /**
@@ -575,7 +576,7 @@ json_array_add_boolean_element (JsonArray *array,
 {
   g_return_if_fail (array != NULL);
 
-  g_ptr_array_add (array->elements, json_node_init_boolean (json_node_alloc (), value));
+  json_array_add_element (array, json_node_init_boolean (json_node_alloc (), value));
 }
 
 /**
@@ -604,7 +605,7 @@ json_array_add_string_element (JsonArray   *array,
   else
     json_node_init_null (node);
 
-  g_ptr_array_add (array->elements, node);
+  json_array_add_element (array, node);
 }
 
 /**
@@ -622,7 +623,7 @@ json_array_add_null_element (JsonArray *array)
 {
   g_return_if_fail (array != NULL);
 
-  g_ptr_array_add (array->elements, json_node_init_null (json_node_alloc ()));
+  json_array_add_element (array, json_node_init_null (json_node_alloc ()));
 }
 
 /**
@@ -655,7 +656,7 @@ json_array_add_array_element (JsonArray *array,
   else
     json_node_init_null (node);
 
-  g_ptr_array_add (array->elements, node);
+  json_array_add_element (array, node);
 }
 
 /**
@@ -688,7 +689,7 @@ json_array_add_object_element (JsonArray  *array,
   else
     json_node_init_null (node);
 
-  g_ptr_array_add (array->elements, node);
+  json_array_add_element (array, node);
 }
 
 /**
@@ -743,3 +744,92 @@ json_array_foreach_element (JsonArray        *array,
       (* func) (array, i, element_node, data);
     }
 }
+
+/**
+ * json_array_hash:
+ * @key: (type JsonArray): a JSON array to hash
+ *
+ * Calculate a hash value for the given @key (a #JsonArray).
+ *
+ * The hash is calculated over the array and all its elements, recursively. If
+ * the array is immutable, this is a fast operation; otherwise, it scales
+ * proportionally with the length of the array.
+ *
+ * Returns: hash value for @key
+ * Since: UNRELEASED
+ */
+guint
+json_array_hash (gconstpointer key)
+{
+  JsonArray *array;  /* unowned */
+  guint hash = 0;
+  guint i;
+
+  g_return_val_if_fail (key != NULL, 0);
+
+  array = (JsonArray *) key;
+
+  /* If the array is immutable, we can use the calculated hash. */
+  if (array->immutable)
+    return array->immutable_hash;
+
+  /* Otherwise, calculate the hash. */
+  for (i = 0; i < array->elements->len; i++)
+    {
+      JsonNode *node = g_ptr_array_index (array->elements, i);
+      hash ^= (i ^ json_node_hash (node));
+    }
+
+  return hash;
+}
+
+/**
+ * json_array_equal:
+ * @a: (type JsonArray): a JSON array
+ * @b: (type JsonArray): another JSON array
+ *
+ * Check whether @a and @b are equal #JsonArrays, meaning they have the same
+ * number of elements, and the values of elements in corresponding positions
+ * are equal.
+ *
+ * Returns: %TRUE if @a and @b are equal; %FALSE otherwise
+ * Since: UNRELEASED
+ */
+gboolean
+json_array_equal (gconstpointer a,
+                  gconstpointer b)
+{
+  JsonArray *array_a, *array_b;  /* unowned */
+  guint length_a, length_b, i;
+
+  g_return_val_if_fail (a != NULL, FALSE);
+  g_return_val_if_fail (b != NULL, FALSE);
+
+  array_a = (JsonArray *) a;
+  array_b = (JsonArray *) b;
+
+  /* Identity comparison. */
+  if (array_a == array_b)
+    return TRUE;
+
+  /* Check lengths. */
+  length_a = json_array_get_length (array_a);
+  length_b = json_array_get_length (array_b);
+
+  if (length_a != length_b)
+    return FALSE;
+
+  /* Check elements. */
+  for (i = 0; i < length_a; i++)
+    {
+      JsonNode *child_a, *child_b;  /* unowned */
+
+      child_a = json_array_get_element (array_a, i);
+      child_b = json_array_get_element (array_b, i);
+
+      if (!json_node_equal (child_a, child_b))
+        return FALSE;
+    }
+
+  return TRUE;
+}