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

[Tomi Ollila <tomi.ollila@iki.fi>]

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