(text: string, byte: u8, start := 0) -> int
(text: string, needle: string, start := 0) -> int
The first byte at or after start, or -1.
#import "Extensions/Byte_Search";
Fast searches for bytes and substrings, with vector instructions.
Byte_Search :: #import "Extensions/Byte_Search";
text := "id,name;note\nneedle in a/haystack";
at := Byte_Search.find(text, #char "\n"); // the first newline, or -1
at = Byte_Search.find_any(text, #char ",", #char ";");
at = Byte_Search.find(text, "needle"); // the first "needle", or -1
at = Byte_Search.find_last(text, #char "/");
// A needle searched for many times: its analysis is done once.
finder := Byte_Search.make_finder("needle");
at = Byte_Search.find(*finder, text, start = at + 1);Every search takes start and returns a position in the whole text, or -1. Every search is
linear in the text, including substring search with a needle built to defeat it.
Procedures#
(text: string, a: u8, b: u8, start := 0) -> int
(text: string, a: u8, b: u8, c: u8, start := 0) -> int
The first of either byte at or after start, or -1.
(text: string, byte: u8, end := -1) -> int
(text: string, needle: string, end := -1) -> int
The last byte before end (-1: the end of the text), or -1.
(text: string, a: u8, b: u8, end := -1) -> int
(text: string, a: u8, b: u8, c: u8, end := -1) -> int
The last of either byte before end, or -1.
Byte_Search :: #import "Extensions/Byte_Search";
assert(Byte_Search.find_last_any("dir\\file/name", #char "/", #char "\\") == 8);(text: string, byte: u8) -> int
How many times byte occurs in the text.
(bytes: [] u8) -> Byte_Set
Builds the Byte_Set holding bytes. Reuse it across searches.
Byte_Search :: #import "Extensions/Byte_Search";
delimiters := Byte_Search.make_byte_set(.[#char " ", #char "\t", #char ",", #char ";"]);
assert(Byte_Search.find(*delimiters, "one;two three") == 3);Whether byte is in the set.
Byte_Search :: #import "Extensions/Byte_Search";
vowels := Byte_Search.make_byte_set(.[#char "a", #char "e", #char "i", #char "o", #char "u"]);
assert(Byte_Search.contains(*vowels, #char "e"));
assert(!Byte_Search.contains(*vowels, #char "z"));The first i at or after start where text[i] is in first and text[i + gap] is in second,
or -1. Two rare-ish bytes at a fixed distance pick out far fewer places than either alone.
(first: *Byte_Set, second: *Byte_Set, third: *Byte_Set, gap_2: int, gap_3: int, text: string, start := 0) -> int
The same with three sets: text[i] in first, text[i + gap_2] in second, text[i + gap_3] in
third, with gap_3 the largest gap.
(needle: string) -> Finder
Analyses needle once so that find and find_last on the Finder skip that work.
Byte_Search :: #import "Extensions/Byte_Search";
finder := Byte_Search.make_finder("ab");
at := Byte_Search.find(*finder, "xxabxxab");
assert(at == 2);
assert(Byte_Search.find(*finder, "xxabxxab", at + 1) == 6);Types#
:: struct
A set of bytes to search for, any number of them. Make it once with make_byte_set.
- low: [2] u8x16
- per low nibble: the buckets holding a byte with that low nibble
- high: [2] u8x16
- per high nibble: its bucket bit
- wide: bool
- the bytes have more than 8 high nibbles, so both table pairs are used
- single: s16
- the set's only byte, or -1: then a plain compare finds it
- bits: [32] u8
- membership, one bit per byte
:: struct
A needle prepared for repeated searches. It points into the needle, which must outlive it.
- needle: string
- first_offset: int
- The two bytes the vector loop looks for, at these positions in the needle: the rarest two in typical text, so that few candidates need checking.
- second_offset: int
- The two bytes the vector loop looks for, at these positions in the needle: the rarest two in typical text, so that few candidates need checking.
- first_byte: u8
- second_byte: u8
- critical: int
- Two-Way's factorization, for the linear-time path.
- period: int
- periodic: bool
- reverse_critical: int
- The same for the needle read backwards, for find_last.
- reverse_period: int
- reverse_periodic: bool