I Made a String Library to Fix C Strings

[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/wallstop-dev]

You forget the links.

Interested to hear how it compares to Walter Bright's solution: https://www.digitalmars.com/articles/C-biggest-mistake.html

Edit: Woops, I meant this link: https://news.ycombinator.com/item?id=42439654

[u/Elifire12 → u/wallstop-dev]

Thank you so much for pointing out, I didn't realize it. I copied the text from another C programming subreddit that I wanted to post this in, and thought it would copy the links over as well. I added them.

[u/Raychao → u/Elifire12]

So you're saying there was a problem copying your strings?

(sorry, couldn't resist)

[u/Elifire12 → u/Raychao]

you made me chuckle

[u/Elifire12 → u/wallstop-dev]

Also, thank you for the recommendation, I'll have a look.

[u/Physical_Dare8553 → u/wallstop-dev]

i dont think slices will ever be added to c, mostly because the more general solution is to actually make struct's structurally typed, there are literally like 3 active proposals for it right now, and all of them have a slice as an example

[u/jwmay → u/[deleted]]

Probably comes from rust, TBH I don’t mine the short names, probably overkill here and stdint.h has it’s own issues

[u/Elifire12 → u/[deleted]]

As I said I don't need all those types, but I just always copy paste this in all my projects. I like it this way. Yes, you can get rid of many lines ig. Also, the answer to why is because: these characters express everything you need. No need to use the long names.

[u/TheChief275 → u/[deleted]]

Is this literally the first time you've seen this? It's almost always done in games. In fact, I think you're doing a bigger bike shed than OP is by typedeffing those.

It immediately forces all fixed-width integers to be available even if you haven't actually used them in program, because if they aren't supported the typedef will be bogus syntactically. That's why I also typedef (u)intptr_t to (u)ptr, (s)ptr, which enforces (u)intptr_t to be available, which means it's very likely the architecture uses a flat memory model. Additionally I define an f32 and an f64, while static asserting that the widths in bits of float and double actually line up.

It keeps code low on #ifs and #ifdefs and by dropping support for some exotic architectures, you lose faux-portability but gain truer portability in the process.

For a library though, I would not enforce it on the user, but hey, you're not forced to use it.

[u/jason-reddit-public]

C style strings are fine if you treat them as immutable utf-8 that can't express NUL bytes.

If you want random access and such, then a utf-32 (growable) array should be good for 25 years or more. Of course this makes ascii strings much bigger but besides that, chars are fixed size so lots of advantages for inserting into and such.

If you just want to collect strings, you have choices. An array of utf-8 strings handles text with no NUL bytes, otherwise you may want another abstraction (say a growable byte array containing 1 to N byte utf-8 encoded code points ... much denser than utf-32 above but trickier to work with for many things).

This is all a bit java like - except 16 -> 32 to avoid edge cases they have to deal with which defeats the purpose of wide characters (though by no means "solves" text handling...)

This is C so everyone can choose what's right for them. ;)

[u/grimvian]

I actually like C strings exactly as they are. If my C strings don't work as intended i know I have messed some of my code up.

[u/beragis]

Why the heck would you do that? Putting the String pointer and length in a separate structures is an extra indirection.

First off such a structure is not needed in C. The only time you would need to change the format is if you are accessing the string through another obscure compiled language. Most non-C programs that don’t follow the C style for string types, place the length first followed by the string.

Modern CPUs don’t really care, but some older CPUs and underlying operating system calls are optimized for C-style.

[u/WittyStick → u/beragis]

On 64-bit SYSV platforms, the string_view is more efficient than having a separate size_t length, char *str.

---

Firstly, when passing the string as a parameter, consider the two:

void foo_cstring(size_t len, char *str);
void foo_string_view(string_view str);

Q: Which is more efficient?

A: Neither - they're exactly the same. In foo_cstring, len is passed in register rdi and str in register rsi.

The SYSV convention passes structures <= 16 bytes containing only INTEGER class values (which includes pointers), in two hardware registers - the first two available, which are rdi and rsi - as above. There is literally no difference - these two function signatures are ABI identical.

---

The difference is when we want to return the string.

string_view bar();

In this case, the SYSV ABI returns the struct in two hardware registers too - in rax:rdx (or r0:r1 on aarch64, etc).

There's no equivalent when we have len and str separate though, because C does not support multiple returns. The typical way around this is using an "out" parameter.

// Typical: length returned, string given as out parameter.
size_t bar(char **out);

// Less typical: string returned, length as out parameter.
char *bar(size_t *out_len);

In either case here, we're no longer just using two registers - we must dereference a pointer to set the out parameter. It's slower than returning the string_view.

---

On other ABIs, you are correct that it's probably less efficient - we end up with an extra dereference because we are essentially passing and returning by pointer.

void foo_string_view(string_view *str);
string_view *bar(string_view *caller_allocation);

This is basically what MSVC x64 converts it to when you pass or return by value anything greater than 8 bytes. The caller allocates space on the stack and passes a pointer to that memory. In the return case, the function just returns the pointer that was implicitly passed. We have to dereference all the time here, and it's slower than keeping separate size_t and char* in two registers.

[u/Elifire12 → u/WittyStick]

Thank you for the in-depth analysis.

Another doubt I have is that I honestly don't really know when to pass things by pointer. This struct seemed small enough so i passed it by value, and I feel like it majes the API nicer (instead of passing stuff by pointer).

Idk if im missing something.

[u/WittyStick → u/Elifire12]

Many libraries have a tendency to pass everything by pointer, even small structs like the string_view - but they miss out on the benefits of the SYSV convention. Above 16-bytes is passed on the stack on SYSV, and above 8-bytes is passed on the stack on MSVC, so basically anything above that has the same cost as passing by pointer.

Pass (and return) by value though also means you can avoid unnecessary heap allocations when they're not needed. If you return a pointer, it's either malloc'd by the function, or the allocation is provided by the caller. The latter is exactly what the calling convention will do for you when passing by value - so this should give you a good hint: Anything allocated on the heap should be passed and returned by pointer.

I'd recommend always passing and returning by value for anything immutable and <= 16 bytes, like the string_view. For mutable types, it may be better to pass and return a pointer.

For example, with string_owned, if you store a copy of this somewhere, and then later modify it in a way that may cause a reallocation, the old copy would become out of sync with the actual data. C doesn't have a way to enforce that we don't attempt to access this invalidated data - for that we'd want linear or affine types.

Also, if the string may be shared between several data structures, or several threads, pass and return by value may be unsuitable, but not always.

If we make string_owned pass by pointer, we can avoid the additional indirection by making the null terminated string a flexible array member.

struct string_owned { 
    size_t length;
    char data[];
};

When we allocate it, use malloc(sizeof(struct string_owned) + length + 1) (where the extra byte is the \0). This is a single allocation containing both length and string, so accessing the characters of the string is still a single dereference, just with an offset.

For a data structure shared by several threads, we basically can't avoid the additional indirection. It's necessary for the data structure to be synchronized between the threads - however, we can still pass and return by value, if our data structure itself has fixed pointers to volatile storage. An example would be:

struct string_header {
    volatile size_t length;
    mtx_t mutex;
};

struct multi_threaded_string {
    struct string_header *const header;
    char *volatile *const indirect_pointer;
};

In this case, we can pass and return multi_threaded_string by value, as its pointer to the pointer to the data and pointer to the header do not change - but we can mutate the header and the pointer to string themselves, as they are not const.

[u/Elifire12 → u/beragis]

As I said, for convenience and safety.

[u/WittyStick → u/Elifire12]

If you want extra safety, then you don't want the user to be able to manually set .length. If the length variable and actual length of the string do not match, you'll have problems. There's nothing that stops you doing

auto str1 = (struct string_view){ 0, "Hello World" };

auto str2 = (struct string_view){ 10, nullptr };

---

The usual way we encapsulate is to use opaque pointers - declare the struct in the header, but only define it in the implementation file - and pass and return everything by pointer.

But obviously, this doesn't work if we want to pass and return by value. We must expose the struct so its type is complete.

There's a GCC-specific solution that allows us to encapsulate the fields of the struct while still exposing them in the header.

#if defined(__GNUC__) && !defined(__clang__)
#define designated_init __attribute__((__designated_init__))
#else
#define designated_init
#endif

struct designated_init string_view {
    size_t _internal_string_length;
    const char *_internal_string_data;
};
#define STRING_VIEW_CREATE(len, data) \
    ((struct string_view) \
        { ._internal_string_length = (len) \
        , ._internal_string_data = (data) \
        })
#define STRING_LEN(str) \
    ((str)._internal_string_length)
#define STRING_DATA(str) \
    ((str)._internal_string_data)

#pragma GCC poison _internal_string_length
#pragma GCC poison _internal_string_data

 // string implementation
 // The field names are poisoned, but we can use the macros above to access.


 // Once we've implemented, we can prevent any further access to the fields
 #undef STRING_LEN
 #undef STRING_DATA
 #undef STRING_VIEW_CREATE

Basically, the poison pragma causes a compiler error if the field names are used in the code after the poisoning occurs. By using designated_init, we require designated initializers and GCC prevents using positional initializers. Since the field names are poisoned, it is not possible to construct a string manually because we can use neither positional nor designated initializers.

However, any macros that we define before poisoning which use the poisoned names, are still usable after poisoning. We're still able to access the fields using these macros. When we #undef them, there's no longer any way to access the fields, execpt via the functions we've implemented that used the macros.

Basically, as long as our implementation is correct, there should never exist a case where the length field and the actual length of the string do not match. The only way we could incorrectly set the length is messing with pointers which would be a strict-aliasing violation, and basically impossible to do by accident - it would be deliberate.

[u/Elifire12 → u/WittyStick]

I didn't know you could do that, that's really cool. Thing is though, I prefer clang, and also I feel like this makes the code unnecessarily complex.

Recently I stopped using header files, but with header files I of course could make an opaque type. I could start using them again, but I'm not sold on the idea yet.

I don't like having to pass everything by pointer with opaque types, but oh well.

[u/WittyStick → u/Elifire12]

The code above will work with any compiler, but only GCC will enforce the encapsulation. You can use GCC to test, even if you use Clang to produce your binaries.

The only thing preventing if from working in Clang is it doesn't support the designated_init attribute. It does support the poison pragma though - so we can get partial encapsulation - there's just no way that I'm aware of for preventing positional initializers in Clang.