Add ordered iterator for JsonObject

The current iterator API does not guarantee the iteration order, as it's
based off of the hash table iterator. JsonObject, though, can guarantee
the iteration order—we do that for json_object_foreach_member().

Instead of changing the behaviour of json_object_iter_next(), we can add
API to initialize and iterate a JsonObjectIter in insertion order.

5 files changed, 185 insertions, 10 deletions

diff --git a/doc/json-glib-sections.txt b/doc/json-glib-sections.txt
index ced06d0..556bed3 100644
--- a/doc/json-glib-sections.txt
+++ b/doc/json-glib-sections.txt
@@ -27,6 +27,8 @@ json_object_foreach_member
 JsonObjectIter
 json_object_iter_init
 json_object_iter_next
+json_object_iter_init_ordered
+json_object_iter_next_ordered
 
 <SUBSECTION>
 json_object_set_array_member
diff --git a/json-glib/json-object.c b/json-glib/json-object.c
index 8e6b293..c67b687 100644
--- a/json-glib/json-object.c
+++ b/json-glib/json-object.c
@@ -62,7 +62,8 @@ json_object_new (void)
   JsonObject *object;
 
   object = g_slice_new0 (JsonObject);
-  
+
+  object->age = 0;
   object->ref_count = 1;
   object->members = g_hash_table_new_full (g_str_hash, g_str_equal,
                                            g_free,
@@ -176,7 +177,10 @@ object_set_member_internal (JsonObject  *object,
   gchar *name = g_strdup (member_name);
 
   if (g_hash_table_lookup (object->members, name) == NULL)
-    g_queue_push_tail (&object->members_ordered, name);
+    {
+      g_queue_push_tail (&object->members_ordered, name);
+      object->age += 1;
+    }
   else
     {
       GList *l;
@@ -1120,6 +1124,12 @@ json_object_iter_init (JsonObjectIter  *iter,
  * The order in which members are returned by the iterator is undefined. The
  * iterator is invalidated if its #JsonObject is modified during iteration.
  *
+ * You must use this function with a #JsonObjectIter initialized with
+ * json_object_iter_init(); using this function with an iterator initialized
+ * with json_object_iter_init_ordered() yields undefined behavior.
+ *
+ * See also: json_object_iter_next_ordered()
+ *
  * Returns: %TRUE if @member_name and @member_node are valid; %FALSE if the end
  *    of the object has been reached
  *
@@ -1140,3 +1150,102 @@ json_object_iter_next (JsonObjectIter  *iter,
                                  (gpointer *) member_name,
                                  (gpointer *) member_node);
 }
+
+/**
+ * json_object_iter_init_ordered:
+ * @iter: an uninitialised #JsonObjectIter
+ * @object: the #JsonObject to iterate over
+ *
+ * Initialise the @iter and associate it with @object.
+ *
+ * |[<!-- language="C" -->
+ * JsonObjectIter iter;
+ * const gchar *member_name;
+ * JsonNode *member_node;
+ *
+ * json_object_iter_init_ordered (&iter, some_object);
+ * while (json_object_iter_next_ordered (&iter, &member_name, &member_node))
+ *   {
+ *     // Do something with @member_name and @member_node.
+ *   }
+ * ]|
+ *
+ * See also: json_object_iter_init()
+ *
+ * Since: 1.6
+ */
+void
+json_object_iter_init_ordered (JsonObjectIter  *iter,
+                               JsonObject      *object)
+{
+  JsonObjectOrderedIterReal *iter_real = (JsonObjectOrderedIterReal *) iter;
+
+  g_return_if_fail (iter != NULL);
+  g_return_if_fail (object != NULL);
+  g_return_if_fail (object->ref_count > 0);
+
+  iter_real->object = object;
+  iter_real->cur_member = NULL;
+  iter_real->next_member = NULL;
+  iter_real->age = iter_real->object->age;
+}
+
+/**
+ * json_object_iter_next_ordered:
+ * @iter: a #JsonObjectIter
+ * @member_name: (out callee-allocates) (transfer none) (optional): return
+ *    location for the member name, or %NULL to ignore
+ * @member_node: (out callee-allocates) (transfer none) (optional): return
+ *    location for the member value, or %NULL to ignore
+ *
+ * Advance @iter and retrieve the next member in the object. If the end of the
+ * object is reached, %FALSE is returned and @member_name and @member_node are
+ * set to invalid values. After that point, the @iter is invalid.
+ *
+ * The order in which members are returned by the iterator is the same order in
+ * which the members were added to the #JsonObject. The iterator is invalidated
+ * if its #JsonObject is modified during iteration.
+ *
+ * You must use this function with a #JsonObjectIter initialized with
+ * json_object_iter_init_ordered(); using this function with an iterator initialized
+ * with json_object_iter_init() yields undefined behavior.
+ *
+ * See also: json_object_iter_next()
+ *
+ * Returns: %TRUE if @member_name and @member_node are valid; %FALSE if the end
+ *    of the object has been reached
+ *
+ * Since: 1.6
+ */
+gboolean
+json_object_iter_next_ordered (JsonObjectIter  *iter,
+                               const gchar    **member_name,
+                               JsonNode       **member_node)
+{
+  JsonObjectOrderedIterReal *iter_real = (JsonObjectOrderedIterReal *) iter;
+  const char *name = NULL;
+
+  g_return_val_if_fail (iter != NULL, FALSE);
+  g_return_val_if_fail (iter_real->object != NULL, FALSE);
+  g_return_val_if_fail (iter_real->object->ref_count > 0, FALSE);
+  g_return_val_if_fail (iter_real->age == iter_real->object->age, FALSE);
+
+  if (iter_real->cur_member == NULL)
+    iter_real->cur_member = iter_real->object->members_ordered.head;
+  else
+    iter_real->cur_member = iter_real->cur_member->next;
+
+  name = iter_real->cur_member != NULL ? iter_real->cur_member->data : NULL;
+
+  if (member_name != NULL)
+    *member_name = name;
+  if (member_node != NULL)
+    {
+      if (name != NULL)
+        *member_node = g_hash_table_lookup (iter_real->object->members, name);
+      else
+        *member_name = NULL;
+    }
+
+  return iter_real->cur_member != NULL;
+}
diff --git a/json-glib/json-types-private.h b/json-glib/json-types-private.h
index bc29e80..264b32b 100644
--- a/json-glib/json-types-private.h
+++ b/json-glib/json-types-private.h
@@ -104,6 +104,7 @@ struct _JsonObject
 
   GQueue members_ordered;
 
+  int age;
   guint immutable_hash;  /* valid iff immutable */
   volatile gint ref_count;
   gboolean immutable : 1;
@@ -118,6 +119,19 @@ typedef struct
 
 G_STATIC_ASSERT (sizeof (JsonObjectIterReal) == sizeof (JsonObjectIter));
 
+typedef struct
+{
+  JsonObject *object; /* unowned */
+  GList *cur_member;
+  GList *next_member;
+  gpointer priv_pointer[3];
+  int age;
+  int priv_int[1];
+  gboolean priv_boolean;
+} JsonObjectOrderedIterReal;
+
+G_STATIC_ASSERT (sizeof (JsonObjectOrderedIterReal) == sizeof (JsonObjectIter));
+
 G_GNUC_INTERNAL
 const gchar *   json_node_type_get_name         (JsonNodeType     node_type);
 G_GNUC_INTERNAL
diff --git a/json-glib/json-types.h b/json-glib/json-types.h
index 99d1fb9..5e16d4d 100644
--- a/json-glib/json-types.h
+++ b/json-glib/json-types.h
@@ -448,6 +448,14 @@ gboolean              json_object_iter_next          (JsonObjectIter  *iter,
                                                       const gchar    **member_name,
                                                       JsonNode       **member_node);
 
+JSON_AVAILABLE_IN_1_6
+void                  json_object_iter_init_ordered  (JsonObjectIter  *iter,
+                                                      JsonObject      *object);
+JSON_AVAILABLE_IN_1_6
+gboolean              json_object_iter_next_ordered  (JsonObjectIter  *iter,
+                                                      const char     **member_name,
+                                                      JsonNode       **member_node);
+
 JSON_AVAILABLE_IN_1_0
 GType                 json_array_get_type            (void) G_GNUC_CONST;
 JSON_AVAILABLE_IN_1_0
diff --git a/json-glib/tests/object.c b/json-glib/tests/object.c
index 772265a..fa2efd2 100644
--- a/json-glib/tests/object.c
+++ b/json-glib/tests/object.c
@@ -106,6 +106,7 @@ test_remove_member (void)
 typedef struct _TestForeachFixture
 {
   gint n_members;
+  gboolean ordered;
 } TestForeachFixture;
 
 static const struct {
@@ -128,15 +129,27 @@ verify_foreach (JsonObject  *object,
                 gpointer     user_data)
 {
   TestForeachFixture *fixture = user_data;
-  gint i;
 
-  for (i = 0; i < G_N_ELEMENTS (type_verify); i++)
+  if (fixture->ordered)
     {
-      if (strcmp (member_name, type_verify[i].member_name) == 0)
+      int idx = fixture->n_members;
+
+      g_assert_cmpstr (member_name, ==, type_verify[idx].member_name);
+      g_assert_true (json_node_get_node_type (member_node) == type_verify[idx].member_type);
+      g_assert_true (json_node_get_value_type (member_node) == type_verify[idx].member_gtype);
+    }
+  else
+    {
+      int i;
+
+      for (i = 0; i < G_N_ELEMENTS (type_verify); i++)
         {
-          g_assert (json_node_get_node_type (member_node) == type_verify[i].member_type);
-          g_assert (json_node_get_value_type (member_node) == type_verify[i].member_gtype);
-          break;
+          if (strcmp (member_name, type_verify[i].member_name) == 0)
+            {
+              g_assert_true (json_node_get_node_type (member_node) == type_verify[i].member_type);
+              g_assert_true (json_node_get_value_type (member_node) == type_verify[i].member_gtype);
+              break;
+            }
         }
     }
 
@@ -147,7 +160,7 @@ static void
 test_foreach_member (void)
 {
   JsonObject *object = json_object_new ();
-  TestForeachFixture fixture = { 0, };
+  TestForeachFixture fixture = { 0, TRUE, };
 
   json_object_set_int_member (object, "integer", 42);
   json_object_set_boolean_member (object, "boolean", TRUE);
@@ -167,7 +180,7 @@ static void
 test_iter (void)
 {
   JsonObject *object = NULL;
-  TestForeachFixture fixture = { 0, };
+  TestForeachFixture fixture = { 0, FALSE, };
   JsonObjectIter iter;
   const gchar *member_name;
   JsonNode *member_node;
@@ -192,6 +205,34 @@ test_iter (void)
 }
 
 static void
+test_ordered_iter (void)
+{
+  JsonObject *object = NULL;
+  TestForeachFixture fixture = { 0, TRUE, };
+  JsonObjectIter iter;
+  const gchar *member_name;
+  JsonNode *member_node;
+
+  object = json_object_new ();
+
+  json_object_set_int_member (object, "integer", 42);
+  json_object_set_boolean_member (object, "boolean", TRUE);
+  json_object_set_string_member (object, "string", "hello");
+  json_object_set_double_member (object, "double", 3.14159);
+  json_object_set_null_member (object, "null");
+  json_object_set_int_member (object, "", 0);
+
+  json_object_iter_init_ordered (&iter, object);
+
+  while (json_object_iter_next_ordered (&iter, &member_name, &member_node))
+    verify_foreach (object, member_name, member_node, &fixture);
+
+  g_assert_cmpint (fixture.n_members, ==, json_object_get_size (object));
+
+  json_object_unref (object);
+}
+
+static void
 test_empty_member (void)
 {
   JsonObject *object = json_object_new ();
@@ -227,6 +268,7 @@ main (int   argc,
   g_test_add_func ("/object/remove-member", test_remove_member);
   g_test_add_func ("/object/foreach-member", test_foreach_member);
   g_test_add_func ("/object/iter", test_iter);
+  g_test_add_func ("/object/ordered-iter", test_ordered_iter);
   g_test_add_func ("/object/empty-member", test_empty_member);
 
   return g_test_run ();