Implement JSON_PRESERVE_ORDER encoding flag

With this encoding flag, the object key-value pairs in output are in
the same order in which they were first inserted into the object.

To make this possible, a key of an object is now a serial number plus
a string. An object keeps an increasing counter which is used to
assign serial number to the keys. Hashing, comparison and public API
functions were changed to act only on the string part, i.e. the serial
number is ignored everywhere else but in the encoder, where it's used
to order object keys if JSON_PRESERVE_ORDER flag is used.

diff --git a/doc/apiref.rst b/doc/apiref.rst
index 0a96999..ebe00ea 100644 (file)
--- a/doc/apiref.rst
+++ b/doc/apiref.rst
@@ -595,6 +595,14 @@ can be ORed together to obtain *flags*.
 
    .. versionadded:: 1.2
 
+``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.
+
+   .. versionadded:: 1.3
+
 The following functions perform the actual JSON encoding. The result
 is in UTF-8.
 

diff --git a/src/dump.c b/src/dump.c
index e8ae440..a08c2e1 100644 (file)
--- a/src/dump.c
+++ b/src/dump.c
@@ -154,9 +154,16 @@ static int dump_string(const char *str, int ascii, dump_func dump, void *data)
     return dump("\"", 1, data);
 }
 
-static int object_key_cmp(const void *key1, const void *key2)
+static int object_key_compare_keys(const void *key1, const void *key2)
 {
-    return strcmp(*(const char **)key1, *(const char **)key2);
+    return strcmp((*(const object_key_t **)key1)->key,
+                  (*(const object_key_t **)key2)->key);
+}
+
+static int object_key_compare_serials(const void *key1, const void *key2)
+{
+    return (*(const object_key_t **)key1)->serial -
+           (*(const object_key_t **)key2)->serial;
 }
 
 static int do_dump(const json_t *json, unsigned long flags, int depth,
@@ -290,36 +297,40 @@ static int do_dump(const json_t *json, unsigned long flags, int depth,
             if(dump_indent(flags, depth + 1, 0, dump, data))
                 return -1;
 
-            if(flags & JSON_SORT_KEYS)
+            if(flags & JSON_SORT_KEYS || flags & JSON_PRESERVE_ORDER)
             {
-                /* Sort keys */
-
-                const char **keys;
+                const object_key_t **keys;
                 unsigned int size;
                 unsigned int i;
+                int (*cmp_func)(const void *, const void *);
 
                 size = json_object_size(json);
-                keys = malloc(size * sizeof(const char *));
+                keys = malloc(size * sizeof(object_key_t *));
                 if(!keys)
                     return -1;
 
                 i = 0;
                 while(iter)
                 {
-                    keys[i] = json_object_iter_key(iter);
+                    keys[i] = jsonp_object_iter_fullkey(iter);
                     iter = json_object_iter_next((json_t *)json, iter);
                     i++;
                 }
                 assert(i == size);
 
-                qsort(keys, size, sizeof(const char *), object_key_cmp);
+                if(flags & JSON_SORT_KEYS)
+                    cmp_func = object_key_compare_keys;
+                else
+                    cmp_func = object_key_compare_serials;
+
+                qsort(keys, size, sizeof(object_key_t *), cmp_func);
 
                 for(i = 0; i < size; i++)
                 {
                     const char *key;
                     json_t *value;
 
-                    key = keys[i];
+                    key = keys[i]->key;
                     value = json_object_get(json, key);
                     assert(value);
 

diff --git a/src/jansson.h b/src/jansson.h
index 55dce0f..24b4949 100644 (file)
--- a/src/jansson.h
+++ b/src/jansson.h
@@ -173,6 +173,7 @@ json_t *json_load_file(const char *path, json_error_t *error);
 #define JSON_COMPACT        0x100
 #define JSON_ENSURE_ASCII   0x200
 #define JSON_SORT_KEYS      0x400
+#define JSON_PRESERVE_ORDER 0x800
 
 char *json_dumps(const json_t *json, unsigned long flags);
 int json_dumpf(const json_t *json, FILE *output, unsigned long flags);

diff --git a/src/jansson_private.h b/src/jansson_private.h
index 3045956..4490702 100644 (file)
--- a/src/jansson_private.h
+++ b/src/jansson_private.h
@@ -17,6 +17,7 @@
 typedef struct {
     json_t json;
     hashtable_t hashtable;
+    unsigned long serial;
     int visited;
 } json_object_t;
 
@@ -49,4 +50,11 @@ typedef struct {
 #define json_to_real(json_)   container_of(json_, json_real_t, json)
 #define json_to_integer(json_) container_of(json_, json_integer_t, json)
 
+typedef struct {
+    unsigned long serial;
+    char key[];
+} object_key_t;
+
+const object_key_t *jsonp_object_iter_fullkey(void *iter);
+
 #endif

diff --git a/src/value.c b/src/value.c
index 35166f4..f74c684 100644 (file)
--- a/src/value.c
+++ b/src/value.c
@@ -25,9 +25,16 @@ static inline void json_init(json_t *json, json_type type)
 
 /*** object ***/
 
-static unsigned int hash_string(const void *key)
+/* This macro just returns a pointer that's a few bytes backwards from
+   string. This makes it possible to pass a pointer to object_key_t
+   when only the string inside it is used, without actually creating
+   an object_key_t instance. */
+#define string_to_key(string)  container_of(string, object_key_t, key)
+
+static unsigned int hash_key(const void *ptr)
 {
-    const char *str = (const char *)key;
+    const char *str = ((const object_key_t *)ptr)->key;
+
     unsigned int hash = 5381;
     unsigned int c;
 
@@ -40,9 +47,10 @@ static unsigned int hash_string(const void *key)
     return hash;
 }
 
-static int string_equal(const void *key1, const void *key2)
+static int key_equal(const void *ptr1, const void *ptr2)
 {
-    return strcmp((const char *)key1, (const char *)key2) == 0;
+    return strcmp(((const object_key_t *)ptr1)->key,
+                  ((const object_key_t *)ptr2)->key) == 0;
 }
 
 static void value_decref(void *value)
@@ -57,13 +65,14 @@ json_t *json_object(void)
         return NULL;
     json_init(&object->json, JSON_OBJECT);
 
-    if(hashtable_init(&object->hashtable, hash_string, string_equal,
+    if(hashtable_init(&object->hashtable, hash_key, key_equal,
                       free, value_decref))
     {
         free(object);
         return NULL;
     }
 
+    object->serial = 0;
     object->visited = 0;
 
     return &object->json;
@@ -94,12 +103,13 @@ json_t *json_object_get(const json_t *json, const char *key)
         return NULL;
 
     object = json_to_object(json);
-    return hashtable_get(&object->hashtable, key);
+    return hashtable_get(&object->hashtable, string_to_key(key));
 }
 
 int json_object_set_new_nocheck(json_t *json, const char *key, json_t *value)
 {
     json_object_t *object;
+    object_key_t *k;
 
     if(!key || !value)
         return -1;
@@ -111,7 +121,14 @@ 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, strdup(key), value))
+    k = malloc(sizeof(object_key_t) + strlen(key) + 1);
+    if(!k)
+        return -1;
+
+    k->serial = object->serial++;
+    strcpy(k->key, key);
+
+    if(hashtable_set(&object->hashtable, k, value))
     {
         json_decref(value);
         return -1;
@@ -139,7 +156,7 @@ int json_object_del(json_t *json, const char *key)
         return -1;
 
     object = json_to_object(json);
-    return hashtable_del(&object->hashtable, key);
+    return hashtable_del(&object->hashtable, string_to_key(key));
 }
 
 int json_object_clear(json_t *json)
@@ -198,7 +215,7 @@ void *json_object_iter_at(json_t *json, const char *key)
         return NULL;
 
     object = json_to_object(json);
-    return hashtable_iter_at(&object->hashtable, key);
+    return hashtable_iter_at(&object->hashtable, string_to_key(key));
 }
 
 void *json_object_iter_next(json_t *json, void *iter)
@@ -212,12 +229,20 @@ void *json_object_iter_next(json_t *json, void *iter)
     return hashtable_iter_next(&object->hashtable, iter);
 }
 
+const object_key_t *jsonp_object_iter_fullkey(void *iter)
+{
+    if(!iter)
+        return NULL;
+
+    return hashtable_iter_key(iter);
+}
+
 const char *json_object_iter_key(void *iter)
 {
     if(!iter)
         return NULL;
 
-    return (const char *)hashtable_iter_key(iter);
+    return jsonp_object_iter_fullkey(iter)->key;
 }
 
 json_t *json_object_iter_value(void *iter)

diff --git a/test/bin/json_process.c b/test/bin/json_process.c
index 809c4d4..77407e5 100644 (file)
--- a/test/bin/json_process.c
+++ b/test/bin/json_process.c
@@ -53,6 +53,9 @@ int main(int argc, char *argv[])
     if(getenv_int("JSON_ENSURE_ASCII"))
         flags |= JSON_ENSURE_ASCII;
 
+    if(getenv_int("JSON_PRESERVE_ORDER"))
+        flags |= JSON_PRESERVE_ORDER;
+
     if(getenv_int("JSON_SORT_KEYS"))
         flags |= JSON_SORT_KEYS;
 

diff --git a/test/suites/api/test_object.c b/test/suites/api/test_object.c
index 4e730bb..90370e5 100644 (file)
--- a/test/suites/api/test_object.c
+++ b/test/suites/api/test_object.c
@@ -402,6 +402,41 @@ static void test_misc()
     json_decref(object);
 }
 
+static void test_preserve_order()
+{
+    json_t *object;
+    char *result;
+
+    const char *expected = "{\"foobar\": 1, \"bazquux\": 6, \"lorem ipsum\": 3, \"sit amet\": 5, \"helicopter\": 7}";
+
+    object = json_object();
+
+    json_object_set_new(object, "foobar", json_integer(1));
+    json_object_set_new(object, "bazquux", json_integer(2));
+    json_object_set_new(object, "lorem ipsum", json_integer(3));
+    json_object_set_new(object, "dolor", json_integer(4));
+    json_object_set_new(object, "sit amet", json_integer(5));
+
+    /* changing a value should preserve the order */
+    json_object_set_new(object, "bazquux", json_integer(6));
+
+    /* deletion shouldn't change the order of others */
+    json_object_del(object, "dolor");
+
+    /* add a new item just to make sure */
+    json_object_set_new(object, "helicopter", json_integer(7));
+
+    result = json_dumps(object, JSON_PRESERVE_ORDER);
+
+    if(strcmp(expected, result) != 0) {
+        fprintf(stderr, "%s != %s", expected, result);
+        fail("JSON_PRESERVE_ORDER doesn't work");
+    }
+
+    free(result);
+    json_decref(object);
+}
+
 int main()
 {
     test_misc();
@@ -410,6 +445,7 @@ int main()
     test_circular();
     test_set_nocheck();
     test_iterators();
+    test_preserve_order();
 
     return 0;
 }

diff --git a/test/suites/encoding-flags/preserve-order/env b/test/suites/encoding-flags/preserve-order/env
new file mode 100644 (file)
index 0000000..ce3582d
--- /dev/null
+++ b/test/suites/encoding-flags/preserve-order/env
@@ -0,0 +1 @@
+export JSON_PRESERVE_ORDER=1

diff --git a/test/suites/encoding-flags/preserve-order/input b/test/suites/encoding-flags/preserve-order/input
new file mode 100644 (file)
index 0000000..27bcf18
--- /dev/null
+++ b/test/suites/encoding-flags/preserve-order/input
@@ -0,0 +1 @@
+{"foo": 1, "bar": 2, "asdf": 3, "deadbeef": 4, "badc0ffee": 5, "qwerty": 6}

diff --git a/test/suites/encoding-flags/preserve-order/output b/test/suites/encoding-flags/preserve-order/output
new file mode 100644 (file)
index 0000000..7a443f6
--- /dev/null
+++ b/test/suites/encoding-flags/preserve-order/output
@@ -0,0 +1 @@
+{"foo": 1, "bar": 2, "asdf": 3, "deadbeef": 4, "badc0ffee": 5, "qwerty": 6}
\ No newline at end of file