duskos

commit f24da679a95f4813a44050af9996acca6e11bb3a
parent 723ebf403e6a193321b35a26a468c46e5cd951ac
Author: Virgil Dupras <hsoft@hardcoded.net>
Date:   Sun, 13 Nov 2022 15:16:59 -0500

cc/lib: add qsort()

For now, it operates on direct 4b numbers only, no structure support yet.

Diffstat:
M
fs/cc/lib.fs
 | 
29
+++++++++++++++++++++++++++++
M
fs/cc/vm/i386.fs
 | 
2
+-
M
fs/tests/cc/lib.fs
 | 
7
+++++++

3 files changed, 37 insertions(+), 1 deletion(-)
diff --git a/fs/cc/lib.fs b/fs/cc/lib.fs
@@ -107,3 +107,32 @@ $100 MemFile :new const _sfile
     void *_seek;
 };
 
+\ Quick sort implementation using Hoare's partitioning
+
+:c static unsigned int* _partition(unsigned int *lo, unsigned int *hi) {
+    unsigned int pivot = *(lo+((hi-lo)/2));
+    unsigned int n;
+    lo--; hi++;
+    while (1) {
+        // TODO: allow while to be followed by ";"
+        while (*(++lo) < pivot) { }
+        while (*(--hi) > pivot) { }
+        if (lo >= hi) return hi;
+        n = *lo;
+        *lo = *hi;
+        *hi = n;
+    }
+}
+
+:c static void _qsort(unsigned int *lo, unsigned int *hi) {
+    unsigned int *middle;
+    if (hi > lo) {
+        middle = _partition(lo, hi);
+        _qsort(lo, middle);
+        _qsort(middle+1, hi);
+    }
+}
+
+:c void qsort(unsigned int *a, unsigned int count) {
+    _qsort(a, a+count-1);
+}
diff --git a/fs/cc/vm/i386.fs b/fs/cc/vm/i386.fs
@@ -260,7 +260,7 @@ LOGOPCNT wordtbl _tblunsigned
 \ we take current op and test whether it's zero, setting Z. If the op is a
 \ simple register, the "test eax, eax" form is more compact. Otherwise, use
 \ test ..., -1.
-: vmtest, vmop :dest# vmop :compiletest vmop :init ;
+: vmtest, vmop :>reg vmop :compiletest vmop :init ;
 : vmjz, ( a -- ) vmtest, abs>rel jz, ;
 : vmjz[, ( -- a ) vmtest, forward jz, ;
 : vmjnz, ( a -- ) vmtest, abs>rel jnz, ;
diff --git a/fs/tests/cc/lib.fs b/fs/tests/cc/lib.fs
@@ -51,4 +51,11 @@ S" ( ----- %d )" S" ( ----- 000 )" sscanf # 0 #eq
   return 1;
 }
 foo #
+
+create myarray 3 , 7 , 8 , 5 , 2 , 1 , 9 , 5 , 4 ,
+myarray dump
+myarray 9 qsort
+create expected 1 , 2 , 3 , 4 , 5 , 5 , 7 , 8 , 9 ,
+myarray expected 9 CELLSZ * []= #
+
 testend