]> git.cworth.org Git - notmuch/commit
lib/string_map: simulate stable sorting
authorDavid Bremner <david@tethera.net>
Sat, 25 Nov 2023 12:33:52 +0000 (08:33 -0400)
committerDavid Bremner <david@tethera.net>
Tue, 28 Nov 2023 13:19:21 +0000 (09:19 -0400)
commit4f82acce17ca51b03bea2abe3eefb7c3026138fe
treec9d48ed813af0dc0c3e85b98e2d37a1e55ab11db
parent356ad392716d2a775e58d766c1fec9047cc84163
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
lib/string-map.c