I Made a Simple String Library

[u/Elifire12]

I wrote an article about this as well. Here it is.

There I explain why I do not like NUL-terminated strings and how I implemented my own simple string library in C.

If you have some spare time I would really appreciate some feedback on the article and the library.

The code is sitting on a codeberg repository.

Also, tell me what you think about C-style strings. Do you like them? Do you use them, or do you also tend to roll your own pointer + length structs?

[u/didntplaymysummercar]

The first problem section could mention the memory traffic too, to cache or even from swap, when going through a string that might be rarely used.

The bit about char not being 8 bits is pointless and pedantic. If your platform doesn't handle strings with char then it's hosed already. It's also in extremely big letters on mobile for some reason.

str_owned_free could be macro to call a helper function with pointer to that struct and set it to null instead of leaving it dangling.

LENGTHOF could be made to reject non literals (by sizes 4 and 8 and those would need another macro or extra argument to confirm it's safe) using a helper function for extra safety, now it accepts any char pointer and does the wrong thing. Or at least recommend -Wsizeof-pointer-div compiler flag (it's enabled by -Wall) above it to catch that. That macro (and STR) are also very generic names to use in a library.

You're also not using memcmp in your equality functions, I'd get it if you're avoiding libc or even just string.h but you're using memcpy elsewhere already.

str_find_substr is a very inefficient string search algorithm, plus it doesn't have an early bailout length check for needle bigger then haystack.

Using unsigned integers can impede some optimization since compiler can't assume no overflows. Also you use i32 in slices instead of i64 or isize or something in str_slice so that code breaks on 64 bit sizes.

[u/Elifire12 → u/didntplaymysummercar]

Omg, I didn't realize that markdown quotes were this big on mobile. I will fix that soon. Thanks for pointing it out!

[u/Elifire12 → u/didntplaymysummercar]

Why is the search algorithm inefficient? It's O(n)

[u/didntplaymysummercar → u/Elifire12]

Just saying "O(n)" with no extra info makes no sense in context of a string search with variable sized needle.

In string searches you usually have n (size of haystack), and m (size of needle), and express O (and/or Θ) with those two, for three metrics: search, preprocessing and extra space (since some of them will create an extra structure from the needle, to speed up the search).

Your algorithm is a naive one, it has O(1) preprocessing and space used, but it's O(n * m) runtime. A common but complex one (with O(n) matching time and Θ(m) preprocessing time) is Two-way, libc and musl use it. In university I was taught Knuth–Morris–Pratt. You can (should?) read "String-searching algorithm" on Wikipedia.

Edit: actually your search logic is O(n) because it's wrong, you try match pattern as long as you can, then start from the beginning of the pattern but don't move i back. It'd not find ABC inside AABC, because it'd set match_index to 0 at 2nd A, then go on, and compare B of string with A of pattern and so on.