commit aa929853fe0a7d7d790b171576a73e33c8d8a6c9
parent 969d54db90a136b30d9fd7cfd4ff38f7f09efe35
Author: Drew DeVault <sir@cmpwn.com>
Date: Wed, 31 Mar 2021 14:52:04 -0400
sort::sort: basic implementation
This is just an insertion sort.
Diffstat:
4 files changed, 69 insertions(+), 1 deletion(-)
diff --git a/scripts/gen-stdlib b/scripts/gen-stdlib
@@ -461,6 +461,7 @@ slice() {
gensrcs_sort() {
gen_srcs sort \
search.ha \
+ sort.ha \
$*
}
diff --git a/sort/+test.ha b/sort/+test.ha
@@ -15,3 +15,20 @@ fn ncmp(a: const *void, b: const *void) int = {
const key = 1337;
assert(search(nums[..], size(int), &key, &ncmp) == null);
};
+
+fn io::errorln(items: str...) void;
+fn strconv::itos(in: int) str;
+
+@test fn sort() void = {
+ let nums = [
+ 1, 6, 10, 7, 8, 10, 10, 3, 7, 5, 5, 8, 1, 1, 1, 9, 2, 3, 1, 4,
+ 2, 1, 5, 3, 2, 5, 10, 1, 7, 6, 8, 10, 6, 5, 7, 4, 3, 9, 9, 4, 7,
+ 10, 3, 4, 4, 8, 5, 6, 2, 1, 6, 2, 2, 2, 10, 8, 3, 4, 5, 6, 6, 2,
+ 5, 2, 3, 7, 10, 7, 7, 5, 5, 2, 3, 4, 5, 3, 6, 2, 3, 6, 8, 8, 9,
+ 7, 10, 4, 10, 3, 2, 7, 10, 8, 8, 2, 2, 5, 3, 7, 4, 1,
+ ];
+ sort(nums[..], size(int), &ncmp);
+ for (let i = 1z; i < len(nums); i += 1) {
+ assert(nums[i] >= nums[i - 1]);
+ };
+};
diff --git a/sort/sort.ha b/sort/sort.ha
@@ -0,0 +1,48 @@
+// Sorts a slice of items in place. Provide a slice of 'items', the size of each
+// member, and a function to compare one member to another. The 'cmp' function
+// will be called with two pointers to values within the items slice, and shall
+// return an integer less than, equal to, or greater than zero if the first
+// argument is, respectively, less than, equal to, or greater than the second
+// argument.
+//
+// This implementation provides a stable sort.
+export fn sort(
+ items: []void,
+ itemsz: size,
+ cmp: *fn(a: const *void, b: const *void) int,
+) void = {
+ if (len(items) < 256) {
+ insort(items, itemsz, cmp);
+ return;
+ };
+
+ // TODO: Timsort
+ insort(items, itemsz, cmp);
+};
+
+fn swap(a: *void, b: *void, sz: size) void = {
+ let a = a: *[*]u8, b = b: *[*]u8;
+ for (let i = 0z; i < sz; i += 1) {
+ let c = a[i];
+ a[i] = b[i];
+ b[i] = c;
+ };
+};
+
+fn insort(
+ items: []void,
+ itemsz: size,
+ cmp: *fn(a: const *void, b: const *void) int,
+) void = {
+ let ba = items: *[*]u8;
+ for (let i = 0z; i < len(items); i += 1) {
+ for (let j = i; j > 0; j -= 1) {
+ let a = &ba[(j - 1) * itemsz];
+ let b = &ba[j * itemsz];
+ if (cmp(a, b) <= 0) {
+ break;
+ };
+ swap(a, b, itemsz);
+ };
+ };
+};
diff --git a/stdlib.mk b/stdlib.mk
@@ -611,7 +611,8 @@ $(HARECACHE)/slice/slice.ssa: $(stdlib_slice_srcs) $(stdlib_rt)
# sort
stdlib_sort_srcs= \
- $(STDLIB)/sort/search.ha
+ $(STDLIB)/sort/search.ha \
+ $(STDLIB)/sort/sort.ha
$(HARECACHE)/sort/sort.ssa: $(stdlib_sort_srcs) $(stdlib_rt)
@printf 'HAREC \t$@\n'
@@ -1354,6 +1355,7 @@ $(TESTCACHE)/slice/slice.ssa: $(testlib_slice_srcs) $(testlib_rt)
# sort
testlib_sort_srcs= \
$(STDLIB)/sort/search.ha \
+ $(STDLIB)/sort/sort.ha \
$(STDLIB)/sort/+test.ha
$(TESTCACHE)/sort/sort.ssa: $(testlib_sort_srcs) $(testlib_rt)
