[PATCH] lib/string_map: simulate stable sorting

[PATCH] lib/string_map: simulate stable sorting

[David Bremner]

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
---
 lib/string-map.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/lib/string-map.c b/lib/string-map.c
index e3a81b4f..99bc2ea2 100644
--- 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
-- 
2.42.0

Re: [PATCH] lib/string_map: simulate stable sorting

[Tomi Ollila]

On Sat, Nov 25 2023, David Bremner wrote:

> 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.

I don't know (from the visible context here) why this is needed, but I
can image it is useful, so

LGTM.

Tomi

>
> [1]: id:CAA19uiSHjVFmwH0pMC7WwDYCOSzu3yqNbuYhu3ZMeNNRh313eA@mail.gmail.com
> [2]: id:87msv3i44u.fsf@oldenburg.str.redhat.com
> ---
>  lib/string-map.c | 6 +++++-
>  1 file changed, 5 insertions(+), 1 deletion(-)
>
> diff --git a/lib/string-map.c b/lib/string-map.c
> index e3a81b4f..99bc2ea2 100644
> --- 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
> -- 
> 2.42.0

Re: [PATCH] lib/string_map: simulate stable sorting

[David Bremner]

Tomi Ollila <tomi.ollila@iki.fi> writes:

> On Sat, Nov 25 2023, David Bremner wrote:
>
>> 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.
>
> I don't know (from the visible context here) why this is needed, but I
> can image it is useful, so
>
> LGTM.
>
> Tomi

Applied to release and master.

d