lib/string_map: simulate stable sorting

qsort(3) does not promise stability, and recent versions of glibc have
been showing more unstable behaviour [2]. Michael Gruber observed [1] test
breakage due to changing output order for message properties.

We provide a sorting order of (key,value) pairs that _looks_ stable by
breaking ties based on value if keys are equal. Internally there may
be some instability in the case of duplicate (key,value) pairs, but it
should not be observable via the iterator API.

[1]: id:CAA19uiSHjVFmwH0pMC7WwDYCOSzu3yqNbuYhu3ZMeNNRh313eA@mail.gmail.com
[2]: id:87msv3i44u.fsf@oldenburg.str.redhat.com

diff --git a/lib/string-map.c b/lib/string-map.c
index e3a81b4fe1457a030154fb3cb05cfc59cd3bb059..99bc2ea2450fe7a188f527106d5f45fb711f8f10 100644 (file)
--- a/lib/string-map.c
+++ b/lib/string-map.c
@@ -86,10 +86,14 @@ _notmuch_string_map_append (notmuch_string_map_t *map,
 static int
 cmppair (const void *pa, const void *pb)
 {
+    int cmp = 0;
     notmuch_string_pair_t *a = (notmuch_string_pair_t *) pa;
     notmuch_string_pair_t *b = (notmuch_string_pair_t *) pb;
 
-    return strcmp (a->key, b->key);
+    cmp = strcmp (a->key, b->key);
+    if (cmp == 0)
+       cmp = strcmp (a->value, b->value);
+    return cmp;
 }
 
 static void