mlibc: Tinycc support: qsort.

* lib/libc+tcc.c (qswap, qpart): New function
  (qsort): Implement.
* scaffold/tests/81-qsort.c: Test it.
* make.scm ("81-qsort"): Build it.

diff --git a/lib/libc+tcc.c b/lib/libc+tcc.c
index db9eff9ad2d2051455355fe80e4385e9ef538571..4773fafd50904db5caac67e68b891c1cdd345978 100644 (file)
--- a/lib/libc+tcc.c
+++ b/lib/libc+tcc.c
@@ -170,9 +170,41 @@ mprotect (void *addr, size_t len, int prot)
 }
 
 void
-qsort (void *base, size_t nmemb, size_t size, int (*compar)(void const *, void const *))
+qswap (void *a, void *b, size_t size)
 {
-  eputs ("qsort stub\n");
+  char *buf[8];
+  memcpy (buf, a, size);
+  memcpy (a, b, size);
+  memcpy (b, buf, size);
+}
+
+size_t
+qpart (void *base, size_t count, size_t size, int (*compare)(void const *, void const *))
+{
+  void* p = base + count*size;
+  size_t i = 0;
+  for (size_t j = 0; j < count; j++)
+    {
+      if (compare (base+j*size, p) < 0)
+        {
+          qswap (base+i*size, base+j*size, size);
+          i++;
+        }
+    }
+  if (compare (base+count*size, base+i*size) < 0)
+    qswap (base+i*size, base+count*size, size);
+  return i;
+}
+
+void
+qsort (void *base, size_t count, size_t size, int (*compare)(void const *, void const *))
+{
+  if (count > 1)
+    {
+      int p = qpart (base, count-1, size, compare);
+      qsort (base, p, size, compare);
+      qsort (base+p*size, count-p, size, compare);
+    }
 }
 
 int

diff --git a/make.scm b/make.scm
index 070f784527686cbd3210124ea00c69c0e37a9fc2..4dc4c2e308d490b53801361799ee317eb026baa8 100755 (executable)
--- a/make.scm
+++ b/make.scm
@@ -259,7 +259,8 @@ exec ${GUILE-guile} --no-auto-compile -L . -L guile -C . -C guile -s "$0" ${1+"$
 ;; tests/80: and beyond tinycc; building GNU GCC and dependencies
 (for-each
  (cut add-scaffold-test <> #:libc libc+tcc-mes.hex2 #:libc-gcc libc+tcc-gcc.mlibc-o)
- '("80-setjmp"))
+ '("80-setjmp"
+   "81-qsort"))
 
 (add-target (group "check-scaffold-tests/8" #:dependencies (filter (target-prefix? "check-scaffold/tests/8") %targets)))
 

diff --git a/scaffold/tests/81-qsort.c b/scaffold/tests/81-qsort.c
new file mode 100644 (file)
index 0000000..15e7a27
--- /dev/null
+++ b/scaffold/tests/81-qsort.c
@@ -0,0 +1,45 @@
+/* -*-comment-start: "//";comment-end:""-*-
+ * Mes --- Maxwell Equations of Software
+ * Copyright © 2017 Jan Nieuwenhuizen <janneke@gnu.org>
+ *
+ * This file is part of Mes.
+ *
+ * Mes is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or (at
+ * your option) any later version.
+ *
+ * Mes is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Mes.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "30-test.i"
+#include <string.h>
+
+
+int
+compare_int (void *a, void *b)
+{
+  eputs ("compare: "); eputs (itoa (*(int*)a)); eputs (" <? "); eputs (itoa (*(int*)b));
+  eputs (" => "); eputs (itoa (*(int*)a - *(int*)b)); eputs ("\n");
+  return *(int*)a - *(int*)b;
+}
+
+int
+test ()
+{
+  int lst[6] = {0, 5, 4, 3, 2, -1};
+  qsort (lst, 6, sizeof (int), compare_int);
+  for (int i = 0; i < 6; i++)
+    {
+      eputs (itoa (i)); eputs (":"); eputs (itoa (lst[i])); eputs ("\n");
+    }
+  if (lst[0] != -1) return 1;
+  if (lst[5] != 5) return 2;
+  return 0;
+}