Always preserve insertion order of object items

9 files changed, 68 insertions, 111 deletions

diff --git a/doc/apiref.rst b/doc/apiref.rst
index ae0feed..5f08c16 100644
--- a/doc/apiref.rst
+++ b/doc/apiref.rst
@@ -659,7 +659,8 @@ allowed in object keys.
            /* block of code that uses key and value */
        }
 
-   The items are not returned in any particular order.
+   The items are returned in the order they were inserted to the
+   object.
 
    **Note:** It's not safe to call ``json_object_del(object, key)``
    during iteration. If you need to, use
@@ -685,9 +686,8 @@ allowed in object keys.
 
 
 The following functions can be used to iterate through all key-value
-pairs in an object. The items are not returned in any particular order,
-as this would require sorting due to the internal hashtable
-implementation.
+pairs in an object. The items are returned in the order they were
+inserted to to obhect.
 
 .. function:: void *json_object_iter(json_t *object)
 
@@ -885,10 +885,13 @@ can be ORed together to obtain *flags*.
    compared.
 
 ``JSON_PRESERVE_ORDER``
-   If this flag is used, object keys in the output are sorted into the
-   same order in which they were first inserted to the object. For
-   example, decoding a JSON text and then encoding with this flag
-   preserves the order of object keys.
+   **Deprecated since version 2.8:** Order of object keys
+   is always preserved.
+
+   Prior to version 2.8: If this flag is used, object keys in the
+   output are sorted into the same order in which they were first
+   inserted to the object. For example, decoding a JSON text and then
+   encoding with this flag preserves the order of object keys.
 
 ``JSON_ENCODE_ANY``
    Specifying this flag makes it possible to encode any JSON value on
@@ -1508,9 +1511,7 @@ the same child values in the copied value. Deep copying makes a fresh
 copy of the child values, too. Moreover, all the child values are deep
 copied in a recursive fashion.
 
-Copying objects doesn't preserve the insertion order of keys. Deep
-copying also loses the key insertion order of any objects deeper in
-the hierarchy.
+Copying objects preserves the insertion order of keys.
 
 .. function:: json_t *json_copy(json_t *value)
 
diff --git a/src/dump.c b/src/dump.c
index 912f955..1918619 100644
--- a/src/dump.c
+++ b/src/dump.c
@@ -25,11 +25,6 @@
 #define FLAGS_TO_INDENT(f)      ((f) & 0x1F)
 #define FLAGS_TO_PRECISION(f)   (((f) >> 11) & 0x1F)
 
-struct object_key {
-    size_t serial;
-    const char *key;
-};
-
 static int dump_to_strbuffer(const char *buffer, size_t size, void *data)
 {
     return strbuffer_append_bytes((strbuffer_t *)data, buffer, size);
@@ -165,18 +160,9 @@ static int dump_string(const char *str, size_t len, json_dump_callback_t dump, v
     return dump("\"", 1, data);
 }
 
-static int object_key_compare_keys(const void *key1, const void *key2)
+static int compare_keys(const void *key1, const void *key2)
 {
-    return strcmp(((const struct object_key *)key1)->key,
-                  ((const struct object_key *)key2)->key);
-}
-
-static int object_key_compare_serials(const void *key1, const void *key2)
-{
-    size_t a = ((const struct object_key *)key1)->serial;
-    size_t b = ((const struct object_key *)key2)->serial;
-
-    return a < b ? -1 : a == b ? 0 : 1;
+    return strcmp(*(const char **)key1, *(const char **)key2);
 }
 
 static int do_dump(const json_t *json, size_t flags, int depth,
@@ -309,40 +295,33 @@ static int do_dump(const json_t *json, size_t flags, int depth,
             if(dump_indent(flags, depth + 1, 0, dump, data))
                 goto object_error;
 
-            if(flags & JSON_SORT_KEYS || flags & JSON_PRESERVE_ORDER)
+            if(flags & JSON_SORT_KEYS)
             {
-                struct object_key *keys;
+                const char **keys;
                 size_t size, i;
-                int (*cmp_func)(const void *, const void *);
 
                 size = json_object_size(json);
-                keys = jsonp_malloc(size * sizeof(struct object_key));
+                keys = jsonp_malloc(size * sizeof(const char *));
                 if(!keys)
                     goto object_error;
 
                 i = 0;
                 while(iter)
                 {
-                    keys[i].serial = hashtable_iter_serial(iter);
-                    keys[i].key = json_object_iter_key(iter);
+                    keys[i] = json_object_iter_key(iter);
                     iter = json_object_iter_next((json_t *)json, iter);
                     i++;
                 }
                 assert(i == size);
 
-                if(flags & JSON_SORT_KEYS)
-                    cmp_func = object_key_compare_keys;
-                else
-                    cmp_func = object_key_compare_serials;
-
-                qsort(keys, size, sizeof(struct object_key), cmp_func);
+                qsort(keys, size, sizeof(const char *), compare_keys);
 
                 for(i = 0; i < size; i++)
                 {
                     const char *key;
                     json_t *value;
 
-                    key = keys[i].key;
+                    key = keys[i];
                     value = json_object_get(json, key);
                     assert(value);
 
diff --git a/src/hashtable.c b/src/hashtable.c
index a453b00..90ec2d8 100644
--- a/src/hashtable.c
+++ b/src/hashtable.c
@@ -34,6 +34,7 @@ extern volatile uint32_t hashtable_seed;
 #include "lookup3.h"
 
 #define list_to_pair(list_)  container_of(list_, pair_t, list)
+#define ordered_list_to_pair(list_)  container_of(list_, pair_t, ordered_list)
 #define hash_str(key)        ((size_t)hashlittle((key), strlen(key), hashtable_seed))
 
 static JSON_INLINE void list_init(list_t *list)
@@ -126,6 +127,7 @@ static int hashtable_do_del(hashtable_t *hashtable,
         bucket->last = pair->list.prev;
 
     list_remove(&pair->list);
+    list_remove(&pair->ordered_list);
     json_decref(pair->value);
 
     jsonp_free(pair);
@@ -194,6 +196,7 @@ int hashtable_init(hashtable_t *hashtable)
         return -1;
 
     list_init(&hashtable->list);
+    list_init(&hashtable->ordered_list);
 
     for(i = 0; i < hashsize(hashtable->order); i++)
     {
@@ -210,9 +213,7 @@ void hashtable_close(hashtable_t *hashtable)
     jsonp_free(hashtable->buckets);
 }
 
-int hashtable_set(hashtable_t *hashtable,
-                  const char *key, size_t serial,
-                  json_t *value)
+int hashtable_set(hashtable_t *hashtable, const char *key, json_t *value)
 {
     pair_t *pair;
     bucket_t *bucket;
@@ -250,12 +251,13 @@ int hashtable_set(hashtable_t *hashtable,
             return -1;
 
         pair->hash = hash;
-        pair->serial = serial;
         strncpy(pair->key, key, len + 1);
         pair->value = value;
         list_init(&pair->list);
+        list_init(&pair->ordered_list);
 
         insert_to_bucket(hashtable, bucket, &pair->list);
+        list_insert(&hashtable->ordered_list, &pair->ordered_list);
 
         hashtable->size++;
     }
@@ -297,12 +299,13 @@ void hashtable_clear(hashtable_t *hashtable)
     }
 
     list_init(&hashtable->list);
+    list_init(&hashtable->ordered_list);
     hashtable->size = 0;
 }
 
 void *hashtable_iter(hashtable_t *hashtable)
 {
-    return hashtable_iter_next(hashtable, &hashtable->list);
+    return hashtable_iter_next(hashtable, &hashtable->ordered_list);
 }
 
 void *hashtable_iter_at(hashtable_t *hashtable, const char *key)
@@ -318,38 +321,32 @@ void *hashtable_iter_at(hashtable_t *hashtable, const char *key)
     if(!pair)
         return NULL;
 
-    return &pair->list;
+    return &pair->ordered_list;
 }
 
 void *hashtable_iter_next(hashtable_t *hashtable, void *iter)
 {
     list_t *list = (list_t *)iter;
-    if(list->next == &hashtable->list)
+    if(list->next == &hashtable->ordered_list)
         return NULL;
     return list->next;
 }
 
 void *hashtable_iter_key(void *iter)
 {
-    pair_t *pair = list_to_pair((list_t *)iter);
+    pair_t *pair = ordered_list_to_pair((list_t *)iter);
     return pair->key;
 }
 
-size_t hashtable_iter_serial(void *iter)
-{
-    pair_t *pair = list_to_pair((list_t *)iter);
-    return pair->serial;
-}
-
 void *hashtable_iter_value(void *iter)
 {
-    pair_t *pair = list_to_pair((list_t *)iter);
+    pair_t *pair = ordered_list_to_pair((list_t *)iter);
     return pair->value;
 }
 
 void hashtable_iter_set(void *iter, json_t *value)
 {
-    pair_t *pair = list_to_pair((list_t *)iter);
+    pair_t *pair = ordered_list_to_pair((list_t *)iter);
 
     json_decref(pair->value);
     pair->value = value;
diff --git a/src/hashtable.h b/src/hashtable.h
index fab6443..d2c27d2 100644
--- a/src/hashtable.h
+++ b/src/hashtable.h
@@ -21,9 +21,9 @@ struct hashtable_list {
    too */
 struct hashtable_pair {
     struct hashtable_list list;
+    struct hashtable_list ordered_list;
     size_t hash;
     json_t *value;
-    size_t serial;
     char key[1];
 };
 
@@ -37,11 +37,12 @@ typedef struct hashtable {
     struct hashtable_bucket *buckets;
     size_t order;  /* hashtable has pow(2, order) buckets */
     struct hashtable_list list;
+    struct hashtable_list ordered_list;
 } hashtable_t;
 
 
 #define hashtable_key_to_iter(key_) \
-    (&(container_of(key_, struct hashtable_pair, key)->list))
+    (&(container_of(key_, struct hashtable_pair, key)->ordered_list))
 
 
 /**
@@ -80,9 +81,7 @@ void hashtable_close(hashtable_t *hashtable);
  *
  * Returns 0 on success, -1 on failure (out of memory).
  */
-int hashtable_set(hashtable_t *hashtable,
-                  const char *key, size_t serial,
-                  json_t *value);
+int hashtable_set(hashtable_t *hashtable, const char *key, json_t *value);
 
 /**
  * hashtable_get - Get a value associated with a key
@@ -160,13 +159,6 @@ void *hashtable_iter_next(hashtable_t *hashtable, void *iter);
 void *hashtable_iter_key(void *iter);
 
 /**
- * hashtable_iter_serial - Retrieve the serial number pointed to by an iterator
- *
- * @iter: The iterator
- */
-size_t hashtable_iter_serial(void *iter);
-
-/**
  * hashtable_iter_value - Retrieve the value pointed by an iterator
  *
  * @iter: The iterator
diff --git a/src/jansson_private.h b/src/jansson_private.h
index ccb3a57..dc83055 100644
--- a/src/jansson_private.h
+++ b/src/jansson_private.h
@@ -34,7 +34,6 @@
 typedef struct {
     json_t json;
     hashtable_t hashtable;
-    size_t serial;
     int visited;
 } json_object_t;
 
diff --git a/src/pack_unpack.c b/src/pack_unpack.c
index f6c700c..54a3979 100644
--- a/src/pack_unpack.c
+++ b/src/pack_unpack.c
@@ -464,7 +464,7 @@ static int unpack_object(scanner_t *s, json_t *root, va_list *ap)
         if(unpack(s, value, ap))
             goto out;
 
-        hashtable_set(&key_set, key, 0, json_null());
+        hashtable_set(&key_set, key, json_null());
         next_token(s);
     }
 
diff --git a/src/value.c b/src/value.c
index 2010605..a7df559 100644
--- a/src/value.c
+++ b/src/value.c
@@ -67,7 +67,6 @@ json_t *json_object(void)
         return NULL;
     }
 
-    object->serial = 0;
     object->visited = 0;
 
     return &object->json;
@@ -115,7 +114,7 @@ int json_object_set_new_nocheck(json_t *json, const char *key, json_t *value)
     }
     object = json_to_object(json);
 
-    if(hashtable_set(&object->hashtable, key, object->serial++, value))
+    if(hashtable_set(&object->hashtable, key, value))
     {
         json_decref(value);
         return -1;
@@ -154,9 +153,7 @@ int json_object_clear(json_t *json)
         return -1;
 
     object = json_to_object(json);
-
     hashtable_clear(&object->hashtable);
-    object->serial = 0;
 
     return 0;
 }
diff --git a/test/suites/api/test_copy.c b/test/suites/api/test_copy.c
index cf1f25a..aeb7e72 100644
--- a/test/suites/api/test_copy.c
+++ b/test/suites/api/test_copy.c
@@ -232,6 +232,9 @@ static void test_copy_object(void)
     const char *json_object_text =
         "{\"foo\": \"bar\", \"a\": 1, \"b\": 3.141592, \"c\": [1,2,3,4]}";
 
+    const char *keys[] = {"foo", "a", "b", "c"};
+    int i;
+
     json_t *object, *copy;
     void *iter;
 
@@ -247,6 +250,7 @@ static void test_copy_object(void)
     if(!json_equal(copy, object))
         fail("copying an object produces an inequal copy");
 
+    i = 0;
     iter = json_object_iter(object);
     while(iter)
     {
@@ -258,9 +262,13 @@ static void test_copy_object(void)
         value2 = json_object_get(copy, key);
 
         if(value1 != value2)
-            fail("deep copying an object modifies its items");
+            fail("copying an object modifies its items");
+
+        if (strcmp(key, keys[i]) != 0)
+            fail("copying an object doesn't preserve key order");
 
         iter = json_object_iter_next(object, iter);
+        i++;
     }
 
     json_decref(object);
@@ -272,6 +280,9 @@ static void test_deep_copy_object(void)
     const char *json_object_text =
         "{\"foo\": \"bar\", \"a\": 1, \"b\": 3.141592, \"c\": [1,2,3,4]}";
 
+    const char *keys[] = {"foo", "a", "b", "c"};
+    int i;
+
     json_t *object, *copy;
     void *iter;
 
@@ -287,6 +298,7 @@ static void test_deep_copy_object(void)
     if(!json_equal(copy, object))
         fail("deep copying an object produces an inequal copy");
 
+    i = 0;
     iter = json_object_iter(object);
     while(iter)
     {
@@ -300,7 +312,11 @@ static void test_deep_copy_object(void)
         if(value1 == value2)
             fail("deep copying an object doesn't copy its items");
 
+        if (strcmp(key, keys[i]) != 0)
+            fail("deep copying an object doesn't preserve key order");
+
         iter = json_object_iter_next(object, iter);
+        i++;
     }
 
     json_decref(object);
diff --git a/test/suites/api/test_object.c b/test/suites/api/test_object.c
index 01cc8fd..c5b97e3 100644
--- a/test/suites/api/test_object.c
+++ b/test/suites/api/test_object.c
@@ -275,11 +275,7 @@ static void test_set_nocheck()
 
 static void test_iterators()
 {
-    int i;
     json_t *object, *foo, *bar, *baz;
-    const char *iter_keys[3];
-    int have_key[3] = { 0, 0, 0 };
-    json_t *iter_values[3];
     void *iter;
 
     if(json_object_iter(NULL))
@@ -306,50 +302,30 @@ static void test_iterators()
     iter = json_object_iter(object);
     if(!iter)
         fail("unable to get iterator");
-    iter_keys[0] = json_object_iter_key(iter);
-    iter_values[0] = json_object_iter_value(iter);
+    if (strcmp(json_object_iter_key(iter), "a") != 0)
+        fail("iterating doesn't yield keys in order");
+    if (json_object_iter_value(iter) != foo)
+        fail("iterating doesn't yield values in order");
 
     iter = json_object_iter_next(object, iter);
     if(!iter)
         fail("unable to increment iterator");
-    iter_keys[1] = json_object_iter_key(iter);
-    iter_values[1] = json_object_iter_value(iter);
+    if (strcmp(json_object_iter_key(iter), "b") != 0)
+        fail("iterating doesn't yield keys in order");
+    if (json_object_iter_value(iter) != bar)
+        fail("iterating doesn't yield values in order");
 
     iter = json_object_iter_next(object, iter);
     if(!iter)
         fail("unable to increment iterator");
-    iter_keys[2] = json_object_iter_key(iter);
-    iter_values[2] = json_object_iter_value(iter);
+    if (strcmp(json_object_iter_key(iter), "c") != 0)
+        fail("iterating doesn't yield keys in order");
+    if (json_object_iter_value(iter) != baz)
+        fail("iterating doesn't yield values in order");
 
     if(json_object_iter_next(object, iter) != NULL)
         fail("able to iterate over the end");
 
-    /* Check that keys have correct values */
-    for (i = 0; i < 3; i++) {
-        if (strcmp(iter_keys[i], "a") == 0) {
-            if (iter_values[i] != foo)
-                fail("wrong value for iter key a");
-            else
-                have_key[0] = 1;
-        } else if (strcmp(iter_keys[i], "b") == 0) {
-            if (iter_values[i] != bar)
-                fail("wrong value for iter key b");
-            else
-                have_key[1] = 1;
-        } else if (strcmp(iter_keys[i], "c") == 0) {
-            if (iter_values[i] != baz)
-                fail("wrong value for iter key c");
-            else
-                have_key[2] = 1;
-        }
-    }
-
-    /* Check that we got all keys */
-    for(i = 0; i < 3; i++) {
-        if(!have_key[i])
-            fail("a key wasn't iterated over");
-    }
-
     if(json_object_iter_at(object, "foo"))
         fail("json_object_iter_at() succeeds for non-existent key");