hare

commit c6f71bf417f1ae0387178201c217cf3118585319
parent a52cf502c0e526128acf4ea6e37648ceed2ea9d3
Author: Drew DeVault <sir@cmpwn.com>
Date:   Fri, 19 Feb 2021 13:31:17 -0500

sort: new module

Diffstat:
M
hare/lex/lex.ha
 | 
10
++++------
M
hare/lex/token.ha
 | 
1
+
A
sort/+test.ha
 | 
17
+++++++++++++++++
A
sort/search.ha
 | 
26
++++++++++++++++++++++++++

4 files changed, 48 insertions(+), 6 deletions(-)
diff --git a/hare/lex/lex.ha b/hare/lex/lex.ha
@@ -57,7 +57,7 @@ export fn lex(lex: *lexer) ((token, location) | io::EOF | error) = {
 
 	if (is_name(r, false)) {
 		unget(lex, r);
-		return lex_name(lex);
+		return lex_name(lex, loc);
 	};
 	if (ascii::isdigit(r)) {
 		unget(lex, r);
@@ -87,7 +87,7 @@ export fn lex(lex: *lexer) ((token, location) | io::EOF | error) = {
 fn is_name(r: rune, num: bool) bool =
 	ascii::isalpha(r) || r == '_' || r == '@' || (num && ascii::isdigit(r));
 
-fn lex_name(lex: *lexer) ((token, location) | io::EOF | error) = {
+fn lex_name(lex: *lexer, loc: location) ((token, location) | io::EOF | error) = {
 	let chars: []u8 = [];
 	match (next(lex)) {
 		r: rune => {
@@ -109,10 +109,8 @@ fn lex_name(lex: *lexer) ((token, location) | io::EOF | error) = {
 		},
 	};
 
-	let name = strings::from_utf8(chars);
-	io::println(name);
-
-	abort();
+	let n = strings::from_utf8(chars);
+	return (n: name: token, loc);
 };
 
 fn lex2(
diff --git a/hare/lex/token.ha b/hare/lex/token.ha
@@ -61,6 +61,7 @@ export type btoken = enum {
 	UNION,
 	USE,
 	VOID,
+	NAMED_LAST = VOID,
 
 	// Operators
 	ANDEQ,
diff --git a/sort/+test.ha b/sort/+test.ha
@@ -0,0 +1,17 @@
+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];
+		match (search(nums[..], size(int), &key, &ncmp): nullable *int) {
+			null => abort(),
+			p: *int => assert(p == &nums[i] && *p == nums[i]),
+		};
+	};
+	const key = 1337;
+	assert(search(nums[..], size(int), &key, &ncmp) == null);
+};
diff --git a/sort/search.ha b/sort/search.ha
@@ -0,0 +1,26 @@
+// Performs a binary search over a sorted slice. 'in' shall be the sorted slice,
+// and 'sz' shall be the size of each array member. The 'cmp' function will be
+// called with the key value and an array member, and shall return a integer
+// less than, equal to, or greater than zero if the key is, respectively, less
+// than, equal to, or greater than the array member.
+export fn search(
+	in: []void,
+	sz: size,
+	key: const *void,
+	cmp: *fn(a: const *void, b: const *void) int,
+) nullable *void = {
+	let ba = in: *[*]u8;
+	for (let nmemb = len(in); nmemb > 0) {
+		let v = &ba[nmemb / 2 * sz];
+		let r = cmp(key, v);
+		if (r < 0) {
+			nmemb /= 2;
+		} else if (r > 0) {
+			ba = (v: uintptr + sz: uintptr): *[*]u8;
+			nmemb -= nmemb / 2 + 1;
+		} else {
+			return v;
+		};
+	};
+	return null;
+};