[json-glib] core: Add JSON node, object, array hashes

[Emmanuele Bassi <ebassi src gnome org>]

commit 6ddbc94c9888e5ddcd1cbb15845d2f1b5524b3ed
Author: Philip Withnall <philip withnall collabora co uk>
Date:   Tue Mar 1 15:01:07 2016 +0000

    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>

 doc/reference/json-glib-sections.txt |   11 ++
 json-glib/json-array.c               |  104 +++++++++++++-
 json-glib/json-node.c                |  245 ++++++++++++++++++++++++++++++++++
 json-glib/json-object.c              |   99 ++++++++++++++-
 json-glib/json-parser.c              |    8 +-
 json-glib/json-types-private.h       |    5 +
 json-glib/json-types.h               |   27 ++++
 json-glib/json-value.c               |   45 ++++++
 8 files changed, 530 insertions(+), 14 deletions(-)
---
diff --git a/doc/reference/json-glib-sections.txt b/doc/reference/json-glib-sections.txt
index 21e1f0d..4f1e471 100644
--- a/doc/reference/json-glib-sections.txt
+++ b/doc/reference/json-glib-sections.txt
@@ -7,6 +7,8 @@ json_object_ref
 json_object_unref
 json_object_seal
 json_object_is_immutable
+json_object_hash
+json_object_equal
 
 <SUBSECTION>
 json_object_add_member
@@ -55,6 +57,8 @@ json_array_ref
 json_array_unref
 json_array_seal
 json_array_is_immutable
+json_array_hash
+json_array_equal
 
 <SUBSECTION>
 json_array_add_element
@@ -114,6 +118,8 @@ json_node_ref
 json_node_unref
 json_node_is_immutable
 json_node_seal
+json_node_hash
+json_node_equal
 
 <SUBSECTION>
 json_node_set_array
@@ -148,6 +154,11 @@ json_node_get_value_type
 json_node_get_node_type
 json_node_is_null
 
+<SUBSECTION>
+json_string_hash
+json_string_equal
+json_string_compare
+
 <SUBSECTION Private>
 JSON_DEPRECATED
 JSON_DEPRECATED_FOR
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;
+}
diff --git a/json-glib/json-node.c b/json-glib/json-node.c
index 35a7918..44cbdd2 100644
--- a/json-glib/json-node.c
+++ b/json-glib/json-node.c
@@ -27,6 +27,7 @@
 
 #include <glib.h>
 
+#include "json-types.h"
 #include "json-types-private.h"
 
 /**
@@ -1216,3 +1217,247 @@ json_node_is_null (JsonNode *node)
 
   return node->type == JSON_NODE_NULL;
 }
+
+/**
+ * json_type_is_a:
+ * @sub: sub-type
+ * @super: super-type
+ *
+ * Check whether @sub is a sub-type of, or equal to, @super. The only sub-type
+ * relationship in the JSON Schema type system is that
+ * %WBL_PRIMITIVE_TYPE_INTEGER is a sub-type of %WBL_PRIMITIVE_TYPE_NUMBER.
+ *
+ * Formally, this function calculates: ` sub <: @super`.
+ *
+ * Reference: http://json-schema.org/latest/json-schema-core.html#rfc.section.3.5
+ *
+ * Returns: %TRUE if @sub is a sub-type of, or equal to, @super; %FALSE
+ *    otherwise
+ * Since: UNRELEASED
+ */
+static gboolean
+json_type_is_a (JsonNode  *sub,
+                JsonNode  *super)
+{
+  if (super->type == JSON_NODE_VALUE && sub->type == JSON_NODE_VALUE)
+    {
+      JsonValueType super_value_type, sub_value_type;
+
+      if (super->data.value == NULL || sub->data.value == NULL)
+        return FALSE;
+
+      super_value_type = super->data.value->type;
+      sub_value_type = sub->data.value->type;
+
+      return (super_value_type == sub_value_type ||
+              (super_value_type == JSON_VALUE_DOUBLE &&
+              sub_value_type == JSON_VALUE_INT));
+    }
+
+  return (super->type == sub->type);
+}
+
+/**
+ * json_string_hash:
+ * @key: (type utf8): a JSON string to hash
+ *
+ * Calculate a hash value for the given @key (a UTF-8 JSON string).
+ *
+ * Note: Member names are compared byte-wise, without applying any Unicode
+ * decomposition or normalisation. This is not explicitly mentioned in the JSON
+ * standard (ECMA-404), but is assumed.
+ *
+ * Returns: hash value for @key
+ * Since: UNRELEASED
+ */
+guint
+json_string_hash (gconstpointer key)
+{
+  return g_str_hash (key);
+}
+
+/**
+ * json_string_equal:
+ * @a: (type utf8): a JSON string
+ * @b: (type utf8): another JSON string
+ *
+ * Check whether @a and @b are equal UTF-8 JSON strings.
+ *
+ * Returns: %TRUE if @a and @b are equal; %FALSE otherwise
+ * Since: UNRELEASED
+ */
+gboolean
+json_string_equal (gconstpointer  a,
+                   gconstpointer  b)
+{
+  return g_str_equal (a, b);
+}
+
+/**
+ * json_string_compare:
+ * @a: (type utf8): a JSON string
+ * @b: (type utf8): another JSON string
+ *
+ * Check whether @a and @b are equal UTF-8 JSON strings and return an ordering
+ * over them in strcmp() style.
+ *
+ * Returns: an integer less than zero if @a < @b, equal to zero if @a == @b, and
+ *    greater than zero if @a > @b
+ * Since: UNRELEASED
+ */
+gint
+json_string_compare (gconstpointer  a,
+                     gconstpointer  b)
+{
+  return g_strcmp0 (a, b);
+}
+
+/**
+ * json_node_hash:
+ * @key: (type JsonNode): a JSON node to hash
+ *
+ * Calculate a hash value for the given @key (a #JsonNode).
+ *
+ * The hash is calculated over the node and its value, recursively. If the node
+ * is immutable, this is a fast operation; otherwise, it scales proportionally
+ * with the size of the node’s value (for example, with the number of members
+ * in the #JsonObject if this node contains an object).
+ *
+ * Returns: hash value for @key
+ * Since: UNRELEASED
+ */
+guint
+json_node_hash (gconstpointer key)
+{
+  JsonNode *node;  /* unowned */
+
+  /* These are all randomly generated and arbitrary. */
+  const guint value_hash = 0xc19e75ad;
+  const guint array_hash = 0x865acfc2;
+  const guint object_hash = 0x3c8f3135;
+
+  node = (JsonNode *) key;
+
+  /* XOR the hash values with a (constant) random number depending on the node’s
+   * type so that empty values, arrays and objects do not all collide at the
+   * hash value 0. */
+  switch (node->type)
+    {
+    case JSON_NODE_NULL:
+      return 0;
+    case JSON_NODE_VALUE:
+      return value_hash ^ json_value_hash (node->data.value);
+    case JSON_NODE_ARRAY:
+      return array_hash ^ json_array_hash (json_node_get_array (node));
+    case JSON_NODE_OBJECT:
+      return object_hash ^ json_object_hash (json_node_get_object (node));
+    default:
+      g_assert_not_reached ();
+    }
+}
+
+/**
+ * json_node_equal:
+ * @a: (type JsonNode): a JSON node
+ * @b: (type JsonNode): another JSON node
+ *
+ * Check whether @a and @b are equal #JsonNodes, meaning they have the same
+ * type and same values (checked recursively). Note that integer values are
+ * compared numerically, ignoring type, so a double value 4.0 is equal to the
+ * integer value 4.
+ *
+ * Returns: %TRUE if @a and @b are equal; %FALSE otherwise
+ * Since: UNRELEASED
+ */
+gboolean
+json_node_equal (gconstpointer  a,
+                 gconstpointer  b)
+{
+  JsonNode *node_a, *node_b;  /* unowned */
+
+  node_a = (JsonNode *) a;
+  node_b = (JsonNode *) b;
+
+  /* Identity comparison. */
+  if (node_a == node_b)
+    return TRUE;
+
+  /* Eliminate mismatched types rapidly. */
+  if (!json_type_is_a (node_a, node_b) &&
+      !json_type_is_a (node_b, node_a))
+    {
+      return FALSE;
+    }
+
+  switch (node_a->type)
+    {
+    case JSON_NODE_NULL:
+      /* Types match already. */
+      return TRUE;
+    case JSON_NODE_ARRAY:
+      return json_array_equal (json_node_get_array (node_a),
+                               json_node_get_array (node_b));
+    case JSON_NODE_OBJECT:
+      return json_object_equal (json_node_get_object (node_a),
+                                json_node_get_object (node_b));
+    case JSON_NODE_VALUE:
+      /* Handled below. */
+      break;
+    default:
+      g_assert_not_reached ();
+    }
+
+  /* Handle values. */
+  switch (node_a->data.value->type)
+    {
+    case JSON_VALUE_NULL:
+      /* Types already match. */
+      return TRUE;
+    case JSON_VALUE_BOOLEAN:
+      return (json_node_get_boolean (node_a) == json_node_get_boolean (node_b));
+    case JSON_VALUE_STRING:
+      return json_string_equal (json_node_get_string (node_a),
+                                json_node_get_string (node_b));
+    case JSON_VALUE_DOUBLE:
+    case JSON_VALUE_INT: {
+      gdouble val_a, val_b;
+      JsonValueType value_type_a, value_type_b;
+
+      value_type_a = node_a->data.value->type;
+      value_type_b = node_b->data.value->type;
+
+      /* Integer comparison doesn’t need to involve doubles… */
+      if (value_type_a == JSON_VALUE_INT &&
+          value_type_b == JSON_VALUE_INT)
+        {
+          return (json_node_get_int (node_a) ==
+                  json_node_get_int (node_b));
+        }
+
+      /* …but everything else does. We can use bitwise double equality here,
+       * since we’re not doing any calculations which could introduce floating
+       * point error. We expect that the doubles in the JSON nodes come directly
+       * from strtod() or similar, so should be bitwise equal for equal string
+       * representations.
+       *
+       * Interesting background reading:
+       * http://randomascii.wordpress.com/2012/06/26/\
+       *   doubles-are-not-floats-so-dont-compare-them/
+       */
+      if (value_type_a == JSON_VALUE_INT)
+        val_a = json_node_get_int (node_a);
+      else
+        val_a = json_node_get_double (node_a);
+
+      if (value_type_b == JSON_VALUE_INT)
+        val_b = json_node_get_int (node_b);
+      else
+        val_b = json_node_get_double (node_b);
+
+      return (val_a == val_b);
+    }
+    case JSON_VALUE_INVALID:
+    default:
+      g_assert_not_reached ();
+    }
+}
diff --git a/json-glib/json-object.c b/json-glib/json-object.c
index acb72f7..5b1ec9e 100644
--- a/json-glib/json-object.c
+++ b/json-glib/json-object.c
@@ -61,7 +61,7 @@ json_object_new (void)
 {
   JsonObject *object;
 
-  object = g_slice_new (JsonObject);
+  object = g_slice_new0 (JsonObject);
   
   object->ref_count = 1;
   object->members = g_hash_table_new_full (g_str_hash, g_str_equal,
@@ -146,6 +146,7 @@ json_object_seal (JsonObject *object)
   while (json_object_iter_next (&iter, NULL, &node))
     json_node_seal (node);
 
+  object->immutable_hash = json_object_hash (object);
   object->immutable = TRUE;
 }
 
@@ -904,6 +905,102 @@ json_object_foreach_member (JsonObject        *object,
 }
 
 /**
+ * json_object_hash:
+ * @key: (type JsonObject): a JSON object to hash
+ *
+ * Calculate a hash value for the given @key (a #JsonObject).
+ *
+ * The hash is calculated over the object and all its members, recursively. If
+ * the object is immutable, this is a fast operation; otherwise, it scales
+ * proportionally with the number of members in the object.
+ *
+ * Returns: hash value for @key
+ * Since: UNRELEASED
+ */
+guint
+json_object_hash (gconstpointer key)
+{
+  JsonObject *object = (JsonObject *) key;
+  guint hash = 0;
+  JsonObjectIter iter;
+  const gchar *member_name;
+  JsonNode *node;
+
+  g_return_val_if_fail (object != NULL, 0);
+
+  /* If the object is immutable, use the cached hash. */
+  if (object->immutable)
+    return object->immutable_hash;
+
+  /* Otherwise, calculate from scratch. */
+  json_object_iter_init (&iter, object);
+
+  while (json_object_iter_next (&iter, &member_name, &node))
+    hash ^= (json_string_hash (member_name) ^ json_node_hash (node));
+
+  return hash;
+}
+
+/**
+ * json_object_equal:
+ * @a: (type JsonObject): a JSON object
+ * @b: (type JsonObject): another JSON object
+ *
+ * Check whether @a and @b are equal #JsonObjects, meaning they have the same
+ * set of members, and the values of corresponding members are equal.
+ *
+ * Returns: %TRUE if @a and @b are equal; %FALSE otherwise
+ * Since: UNRELEASED
+ */
+gboolean
+json_object_equal (gconstpointer  a,
+                   gconstpointer  b)
+{
+  JsonObject *object_a, *object_b;
+  guint size_a, size_b;
+  JsonObjectIter iter_a;
+  JsonNode *child_a, *child_b;  /* unowned */
+  const gchar *member_name;
+
+  object_a = (JsonObject *) a;
+  object_b = (JsonObject *) b;
+
+  /* Identity comparison. */
+  if (object_a == object_b)
+    return TRUE;
+
+  /* Check sizes. */
+  size_a = json_object_get_size (object_a);
+  size_b = json_object_get_size (object_b);
+
+  if (size_a != size_b)
+    return FALSE;
+
+  /* Check member names and values. Check the member names first
+   * to avoid expensive recursive value comparisons which might
+   * be unnecessary. */
+  json_object_iter_init (&iter_a, object_a);
+
+  while (json_object_iter_next (&iter_a, &member_name, NULL))
+    {
+      if (!json_object_has_member (object_b, member_name))
+        return FALSE;
+    }
+
+  json_object_iter_init (&iter_a, object_a);
+
+  while (json_object_iter_next (&iter_a, &member_name, &child_a))
+    {
+      child_b = json_object_get_member (object_b, member_name);
+
+      if (!json_node_equal (child_a, child_b))
+        return FALSE;
+    }
+
+  return TRUE;
+}
+
+/**
  * json_object_iter_init:
  * @iter: an uninitialised #JsonObjectIter
  * @object: the #JsonObject to iterate over
diff --git a/json-glib/json-parser.c b/json-glib/json-parser.c
index a7b1c32..a48e9b2 100644
--- a/json-glib/json-parser.c
+++ b/json-glib/json-parser.c
@@ -610,9 +610,7 @@ json_parse_array (JsonParser   *parser,
 array_done:
   json_scanner_get_next_token (scanner);
 
-  /* We can guarantee that all the array elements are immutable, so we
-   * can skip the formal loop over them to seal them again. */
-  array->immutable = TRUE;
+  json_array_seal (array);
 
   json_node_take_array (priv->current_node, array);
   if (priv->immutable)
@@ -793,9 +791,7 @@ json_parse_object (JsonParser   *parser,
 
   json_scanner_get_next_token (scanner);
 
-  /* We can guarantee that all the object members are immutable, so we
-   * can skip the formal loop over them to seal them again. */
-  object->immutable = TRUE;
+  json_object_seal (object);
 
   json_node_take_object (priv->current_node, object);
   if (priv->immutable)
diff --git a/json-glib/json-types-private.h b/json-glib/json-types-private.h
index 8934e9a..db5dea6 100644
--- a/json-glib/json-types-private.h
+++ b/json-glib/json-types-private.h
@@ -93,6 +93,7 @@ struct _JsonArray
 {
   GPtrArray *elements;
 
+  guint immutable_hash;  /* valid iff immutable */
   volatile gint ref_count;
   gboolean immutable : 1;
 };
@@ -104,6 +105,7 @@ struct _JsonObject
   /* the members of the object, ordered in reverse */
   GList *members_ordered;
 
+  guint immutable_hash;  /* valid iff immutable */
   volatile gint ref_count;
   gboolean immutable : 1;
 };
@@ -162,6 +164,9 @@ const gchar *   json_value_get_string           (const JsonValue *value);
 G_GNUC_INTERNAL
 void            json_value_seal                 (JsonValue       *value);
 
+G_GNUC_INTERNAL
+guint           json_value_hash                 (gconstpointer    key);
+
 G_END_DECLS
 
 #endif /* __JSON_TYPES_PRIVATE_H__ */
diff --git a/json-glib/json-types.h b/json-glib/json-types.h
index 33180b4..ae5c4f7 100644
--- a/json-glib/json-types.h
+++ b/json-glib/json-types.h
@@ -285,6 +285,21 @@ JSON_AVAILABLE_IN_1_2
 void                  json_node_seal            (JsonNode     *node);
 gboolean              json_node_is_immutable    (JsonNode     *node);
 
+JSON_AVAILABLE_IN_1_2
+guint                 json_string_hash            (gconstpointer  key);
+JSON_AVAILABLE_IN_1_2
+gboolean              json_string_equal           (gconstpointer  a,
+                                                   gconstpointer  b);
+JSON_AVAILABLE_IN_1_2
+gint                  json_string_compare         (gconstpointer  a,
+                                                   gconstpointer  b);
+
+JSON_AVAILABLE_IN_1_2
+guint                 json_node_hash              (gconstpointer  key);
+JSON_AVAILABLE_IN_1_2
+gboolean              json_node_equal             (gconstpointer  a,
+                                                   gconstpointer  b);
+
 /*
  * JsonObject
  */
@@ -382,6 +397,12 @@ void                  json_object_seal               (JsonObject  *object);
 JSON_AVAILABLE_IN_1_2
 gboolean              json_object_is_immutable       (JsonObject  *object);
 
+JSON_AVAILABLE_IN_1_2
+guint                 json_object_hash               (gconstpointer key);
+JSON_AVAILABLE_IN_1_2
+gboolean              json_object_equal              (gconstpointer a,
+                                                      gconstpointer b);
+
 /**
  * JsonObjectIter:
  *
@@ -486,6 +507,12 @@ void                  json_array_seal                (JsonArray   *array);
 JSON_AVAILABLE_IN_1_2
 gboolean              json_array_is_immutable        (JsonArray   *array);
 
+JSON_AVAILABLE_IN_1_2
+guint                 json_array_hash                (gconstpointer key);
+JSON_AVAILABLE_IN_1_2
+gboolean              json_array_equal               (gconstpointer a,
+                                                      gconstpointer b);
+
 #ifdef G_DEFINE_AUTOPTR_CLEANUP_FUNC
 G_DEFINE_AUTOPTR_CLEANUP_FUNC (JsonArray, json_array_unref)
 G_DEFINE_AUTOPTR_CLEANUP_FUNC (JsonObject, json_object_unref)
diff --git a/json-glib/json-value.c b/json-glib/json-value.c
index 148cf8d..e636499 100644
--- a/json-glib/json-value.c
+++ b/json-glib/json-value.c
@@ -186,6 +186,51 @@ json_value_seal (JsonValue *value)
   value->immutable = TRUE;
 }
 
+guint
+json_value_hash (gconstpointer key)
+{
+  JsonValue *value;
+  guint value_hash;
+  guint type_hash;
+
+  value = (JsonValue *) key;
+
+  /* Hash the type and value separately.
+   * Use the top 3 bits to store the type. */
+  type_hash = value->type << (sizeof (guint) * 8 - 3);
+
+  switch (value->type)
+    {
+    case JSON_VALUE_NULL:
+      value_hash = 0;
+      break;
+    case JSON_VALUE_BOOLEAN:
+      value_hash = json_value_get_boolean (value) ? 1 : 0;
+      break;
+    case JSON_VALUE_STRING:
+      value_hash = json_string_hash (json_value_get_string (value));
+      break;
+    case JSON_VALUE_INT: {
+      gint64 v = json_value_get_int (value);
+      value_hash = g_int64_hash (&v);
+      break;
+    }
+    case JSON_VALUE_DOUBLE: {
+      gdouble v = json_value_get_double (value);
+      value_hash = g_double_hash (&v);
+      break;
+    }
+    case JSON_VALUE_INVALID:
+    default:
+      g_assert_not_reached ();
+    }
+
+  /* Mask out the top 3 bits of the @value_hash. */
+  value_hash &= ~(7 << (sizeof (guint) * 8 - 3));
+
+  return (type_hash | value_hash);
+}
+
 #define _JSON_VALUE_DEFINE_SET(Type,EType,CType,VField) \
 void \
 json_value_set_##Type (JsonValue *value, CType VField) \