commit 911ecbd8f2e4f577b5bc542460e8fcd291ceeade
parent e6cab9bc88bdc902fc43a3526bd8bc8d2e39e442
Author: Sebastian <sebastian@sebsite.pw>
Date: Sat, 2 Apr 2022 00:05:26 -0400
sort: add strings and sortstrings
Signed-off-by: Sebastian <sebastian@sebsite.pw>
Diffstat:
4 files changed, 24 insertions(+), 21 deletions(-)
diff --git a/hare/lex/lex.ha b/hare/lex/lex.ha
@@ -149,11 +149,6 @@ export fn lex(lex: *lexer) (token | error) = {
fn is_name(r: rune, num: bool) bool =
ascii::isalpha(r) || r == '_' || r == '@' || (num && ascii::isdigit(r));
-fn ncmp(a: const *void, b: const *void) int = {
- let a = a: const *str, b = b: const *str;
- return strings::strcmp(*a, *b);
-};
-
fn lex_unicode(lex: *lexer, loc: location, n: size) (rune | error) = {
assert(n < 9);
let buf: [8]u8 = [0...];
@@ -312,15 +307,12 @@ fn lex_name(lex: *lexer, loc: location, label: bool) (token | error) = {
return (ltok::LABEL, n, loc);
};
- match (sort::search(bmap[..ltok::LAST_KEYWORD+1],
- size(str), &n, &ncmp)) {
- case null =>
+ match (sort::searchstrings(bmap[..ltok::LAST_KEYWORD+1], n)) {
+ case void =>
return (ltok::NAME, n, loc);
- case let v: *void =>
- defer free(n);
- let tok = v: uintptr - &bmap[0]: uintptr;
- tok /= size(str): uintptr;
- return (tok: ltok, void, loc);
+ case let i: size =>
+ free(n);
+ return (i: ltok, void, loc);
};
};
diff --git a/hare/module/scan.ha b/hare/module/scan.ha
@@ -120,12 +120,6 @@ export fn parse_name(name: str) (str, str, []tag) = {
return (base, ext, tags);
};
-fn strcmp(a: const *void, b: const *void) int = {
- const a = *(a: const *str);
- const b = *(b: const *str);
- return ascii::strcmp(a, b) as int;
-};
-
fn scan_directory(
ctx: *context,
ver: *version,
@@ -180,8 +174,8 @@ fn scan_directory(
};
// Sorted to keep the hash consistent
- sort::sort(dirs, size(str), &strcmp);
- sort::sort(files, size(str), &strcmp);
+ sort::strings(dirs);
+ sort::strings(files);
// Tuple of is_directory, basename, tags, and path to a candidate input.
let inputs: [](bool, str, []tag, str) = [];
diff --git a/sort/search.ha b/sort/search.ha
@@ -24,3 +24,16 @@ export fn search(
};
return null;
};
+
+// Performs a binary search over a sorted slice of strings. Sorting is done with
+// respect to Unicode codepoints; see [[strings::strcmp]]. The index of the
+// matching item in the slice is returned if found, otherwise void is returned.
+export fn searchstrings(in: []const str, key: str) (size | void) = {
+ match (search(in, size(str), &key, &scmp)) {
+ case null =>
+ return void;
+ case let v: *const void =>
+ const offs = (v: uintptr - in: *[*]const str: uintptr);
+ return (offs / size(str): uintptr): size;
+ };
+};
diff --git a/sort/sort.ha b/sort/sort.ha
@@ -16,6 +16,10 @@ export fn sort(items: []void, itemsz: size, cmp: *cmpfunc) void = {
insort(items, itemsz, cmp);
};
+// Sorts a slice of strings in place. Sorting is done with respect to Unicode
+// codepoints; see [[strings::strcmp]].
+export fn strings(items: []str) void = sort(items, size(str), &scmp);
+
fn swap(a: *void, b: *void, sz: size) void = {
let a = a: *[*]u8, b = b: *[*]u8;
for (let i = 0z; i < sz; i += 1) {
