mescc: Mes C Library: Fix qsort to support duplicate entries.
[mes.git] / lib / stdlib / qsort.c
1 /* -*-comment-start: "//";comment-end:""-*-
2  * GNU Mes --- Maxwell Equations of Software
3  * Copyright © 2017,2018 Jan (janneke) Nieuwenhuizen <janneke@gnu.org>
4  *
5  * This file is part of GNU Mes.
6  *
7  * GNU Mes is free software; you can redistribute it and/or modify it
8  * under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 3 of the License, or (at
10  * your option) any later version.
11  *
12  * GNU Mes is distributed in the hope that it will be useful, but
13  * WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with GNU Mes.  If not, see <http://www.gnu.org/licenses/>.
19  */
20
21 #include <stdlib.h>
22 #include <string.h>
23
24 void
25 qswap (void *a, void *b, size_t size)
26 {
27   char *buf[8];
28   memcpy (buf, a, size);
29   memcpy (a, b, size);
30   memcpy (b, buf, size);
31 }
32
33 size_t
34 qpart (void *base, size_t count, size_t size, int (*compare)(void const *, void const *))
35 {
36   void* p = base + count*size;
37   size_t i = 0;
38   for (size_t j = 0; j < count; j++)
39     {
40       int c = compare (base+j*size, p);
41       if (c < 0)
42         {
43           qswap (base+i*size, base+j*size, size);
44           i++;
45         }
46       else if (c == 0)
47         i++;
48     }
49   if (compare (base+count*size, base+i*size) < 0)
50     qswap (base+i*size, base+count*size, size);
51   return i;
52 }
53
54 void
55 qsort (void *base, size_t count, size_t size, int (*compare)(void const *, void const *))
56 {
57   if (count > 1)
58     {
59       int p = qpart (base, count-1, size, compare);
60       qsort (base, p, size, compare);
61       qsort (base+p*size, count-p, size, compare);
62     }
63 }