commit 66cf3ede04bfc4d4e87b6b6ead619bb7549138be
parent 1896ad99d6120ad8e3e954b1cfa2a17676c76ad3
Author: Sebastian <sebastian@sebsite.pw>
Date: Sat, 2 Apr 2022 00:05:22 -0400
sort: add types.ha
This adds the cmpfunc type, as well as private helper functions scmp and
icmp.
Signed-off-by: Sebastian <sebastian@sebsite.pw>
Diffstat:
6 files changed, 33 insertions(+), 24 deletions(-)
diff --git a/scripts/gen-stdlib b/scripts/gen-stdlib
@@ -1068,6 +1068,7 @@ gensrcs_sort() {
gen_srcs sort \
search.ha \
sort.ha \
+ types.ha \
$*
}
@@ -1079,7 +1080,7 @@ sort() {
gensrcs_sort \
+test.ha
fi
- gen_ssa sort
+ gen_ssa sort strings
}
strconv() {
diff --git a/sort/+test.ha b/sort/+test.ha
@@ -2,20 +2,15 @@
// (c) 2021 Drew DeVault <sir@cmpwn.com>
// (c) 2021 Eyal Sawady <ecs@d2evs.net>
-fn ncmp(a: const *void, b: const *void) int = {
- let a = a: const *int, b = b: const *int;
- return *a - *b;
-};
-
@test fn search() void = {
const nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
for (let i = 0z; i < len(nums); i += 1) {
const key = nums[i];
- const p = search(nums, size(int), &key, &ncmp) as *const int;
+ const p = search(nums, size(int), &key, &icmp) as *const int;
assert(p == &nums[i] && *p == nums[i]);
};
const key = 1337;
- assert(search(nums[..], size(int), &key, &ncmp) == null);
+ assert(search(nums, size(int), &key, &icmp) is null);
};
@test fn sort() void = {
@@ -26,7 +21,7 @@ fn ncmp(a: const *void, b: const *void) int = {
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);
+ sort(nums, size(int), &icmp);
for (let i = 1z; i < len(nums); i += 1) {
assert(nums[i] >= nums[i - 1]);
};
diff --git a/sort/search.ha b/sort/search.ha
@@ -10,7 +10,7 @@ export fn search(
in: []const void,
sz: size,
key: const *void,
- cmp: *fn(a: const *void, b: const *void) int,
+ cmp: *cmpfunc,
) nullable *const void = {
let ba = in: *[*]u8;
for (let nmemb = len(in); nmemb > 0) {
diff --git a/sort/sort.ha b/sort/sort.ha
@@ -10,11 +10,7 @@
// argument.
//
// This implementation provides a stable sort.
-export fn sort(
- items: []void,
- itemsz: size,
- cmp: *fn(a: const *void, b: const *void) int,
-) void = {
+export fn sort(items: []void, itemsz: size, cmp: *cmpfunc) void = {
if (len(items) < 256) {
insort(items, itemsz, cmp);
return;
@@ -39,7 +35,7 @@ fn search_rightmost(
in: []void,
sz: size,
key: const *void,
- cmp: *fn(a: const *void, b: const *void) int,
+ cmp: *cmpfunc,
) size = {
let l = 0z;
let r = len(in);
@@ -55,11 +51,7 @@ fn search_rightmost(
return r - 1;
};
-fn insort(
- items: []void,
- itemsz: size,
- cmp: *fn(a: const *void, b: const *void) int,
-) void = {
+fn insort(items: []void, itemsz: size, cmp: *cmpfunc) void = {
let ba = items: *[*]u8;
for (let i = 0z; i < len(items); i += 1) {
let bound = search_rightmost(items[0..i], itemsz,
diff --git a/sort/types.ha b/sort/types.ha
@@ -0,0 +1,19 @@
+// License: MPL-2.0
+// (c) 2022 Sebastian <sebastian@sebsite.pw>
+use strings;
+
+// This function type is used when sorting and searching. Given two pointers to
+// values, a function of this type should 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.
+export type cmpfunc = fn(a: const *void, b: const *void) int;
+
+fn scmp(a: const *void, b: const *void) int = {
+ const a = a: const *str, b = b: const *str;
+ return strings::strcmp(*a, *b);
+};
+
+fn icmp(a: const *void, b: const *void) int = {
+ const a = a: const *int, b = b: const *int;
+ return *a - *b;
+};
diff --git a/stdlib.mk b/stdlib.mk
@@ -1637,9 +1637,10 @@ $(HARECACHE)/slices/slices-any.ssa: $(stdlib_slices_any_srcs) $(stdlib_rt) $(std
# sort (+any)
stdlib_sort_any_srcs= \
$(STDLIB)/sort/search.ha \
- $(STDLIB)/sort/sort.ha
+ $(STDLIB)/sort/sort.ha \
+ $(STDLIB)/sort/types.ha
-$(HARECACHE)/sort/sort-any.ssa: $(stdlib_sort_any_srcs) $(stdlib_rt)
+$(HARECACHE)/sort/sort-any.ssa: $(stdlib_sort_any_srcs) $(stdlib_rt) $(stdlib_strings_$(PLATFORM))
@printf 'HAREC \t$@\n'
@mkdir -p $(HARECACHE)/sort
@HARECACHE=$(HARECACHE) $(HAREC) $(HAREFLAGS) -o $@ -Nsort \
@@ -3558,9 +3559,10 @@ $(TESTCACHE)/slices/slices-any.ssa: $(testlib_slices_any_srcs) $(testlib_rt) $(t
testlib_sort_any_srcs= \
$(STDLIB)/sort/search.ha \
$(STDLIB)/sort/sort.ha \
+ $(STDLIB)/sort/types.ha \
$(STDLIB)/sort/+test.ha
-$(TESTCACHE)/sort/sort-any.ssa: $(testlib_sort_any_srcs) $(testlib_rt)
+$(TESTCACHE)/sort/sort-any.ssa: $(testlib_sort_any_srcs) $(testlib_rt) $(testlib_strings_$(PLATFORM))
@printf 'HAREC \t$@\n'
@mkdir -p $(TESTCACHE)/sort
@HARECACHE=$(TESTCACHE) $(HAREC) $(TESTHAREFLAGS) -o $@ -Nsort \
