Show HN: A nice C string API
github.com
A convenient C string API, friendly alongside classic C strings.
github.com
https://github.com/antirez/sds
The trick is the size is hidden before the adress of the buffer.("Learn this one simple trick that will change your life for ever").
From the Readme:
```
Advantage #1: you can pass SDS strings to functions designed for C functions without accessing a struct member or calling a function
Advantage #2: accessing individual chars is straightforward.
Advantage #3: single allocation has better cache locality. Usually when you access a string created by a string library using a structure, you have two different allocations for the structure representing the string, and the actual buffer holding the string. Over the time the buffer is reallocated, and it is likely that it ends in a totally different part of memory compared to the structure itself. Since modern programs performances are often dominated by cache misses, SDS may perform better in many workloads.
```
This library takes string slices without having to allocate or copy memory; it seems to be for use cases involving breaking down strings in complex ways, where good ergonomics and efficiency of obtaining a null-terminated C string are secondary.
Another way to do it is to use:
typedef struct{ size_t allocated; size_t used; char buffer[]; }String;
This lets the header and the string be the same allocation. Thats a huge saving. Its also useful to store the allocation and use size separatly so that you can reuse / modify buffers. The used field lets you use memcpy without looking for string termination.
You can make it even more complex by adding flags if the string is on the stack or on the heap. That way you can do things like:
String buffer = MACRO_TO_CREATE_STRING_BUFFER_ON_STACK(256), *b; b = &buffer;
b = do_processing_with_buffer(&b); // allocates on heap a larger buffer if needed
string_free(b); // frees buffer if its on heap.
The best way to be efficient is often to make assumptions about the data. Most strings don't need any dynamic allocation after having been "built". So it makes a ton of sense to make a string builder API that returns a final string when it's finished. In this way, you save at least the "allocated" member.
The advantage of the simpler string representation is that it works for any string (or substring) that is contiguous in memory, and is completely decoupled from allocation concerns. E.g. I can easily
#define STRING(string_literal) \
((String) { string_literal "", sizeof string_literal - 1 })
String my_string = STRING("Foo bar");
In practice, I find string handling so easy that I rarely even define this struct String. I just pass around strings to functions as two arguments - pointer + size. It feels so light and data flows so easily between APIs, I love it.
A big downside is that you you can't easily take ownership of an existing buffer and treat it as this string type.
string s;
char some_buf[];
string_take(&s, some_buf, some_capacity);
Also you would of course never dynamically allocate string structs, just the data member if needed.
That is how strings use to be stored before C made the choice of using null-terminator. Pascal stored the string size before the string data. The advantage of relying on a terminator symbol is that the string size can be any length where as storing the size at the start forces the string to not exceed certain size.
That, plus you'd be a fool to store a huge string in this way anywhere (in or out of memory) in any case.
Not necessarily. A 64-bit system could give processes an address space that’s significantly larger than half the full 64-bit address space and have an allocator that allows you to allocate a block of more than SIZE_MAX bytes (malloc takes a size_t, but you can use calloc)
The calloc() [1] function mentioned above takes two values of type size_t, and allocates their product bytes.
I'm on mobile without (!) the C99 draft spec but at least the man page gives no such restriction.
However, the standard says (https://en.cppreference.com/w/c/types/size_t):
“size_t can store the maximum size of a theoretically possible object of any type (including array).”
and (https://en.cppreference.com/w/c/language/pointer):
“Pointer is a type of an object that refers to a function or an object of another type, possibly adding qualifiers. Pointer may also refer to nothing, which is indicated by the special null pointer value.”
⇒ pointers must either be null or point to an object, and objects aren’t larger than SIZE_MAX, so I think having a pointer pointing to a block larger than SIZE_MAX violates the standard.
it's simply not possible, by definition.
calloc returns NULL when can't satisfy the request. The idea of taking two arguments is not to allow the user to specify a larger requested size, but to protect against overflows as it can happen with e.g. malloc() where the user has to compute the size of arrays by multiplying NUM_ELEMS * SIZE_PER_ELEM. And the user will normally do so less carefully than a library function.
On a quick test on my 64-bit system, a C program doing `printf("%zu\n", SIZE_MAX);` outputs 18446744073709551615, which looks like (2^64)-1 to me.
Or is there a thing in the standard that says this isn't always the case?
> The type ssize_t shall be capable of storing values at least in the range [-1, {SSIZE_MAX}].
[1] https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sy...
Note that neither is ptrdiff_t guaranteed to be that signed version, or to hold any possible value in the domain of size_t or (strictly speaking) any possible object size. Both GCC and Clang assume the latter, though, and can miscompile[3] code that relies on (e.g.) malloc() succeeding for sizes > 2^31 on a 32-bit system.
[1] https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sy...
[2] https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/li...
[3] https://trust-in-soft.com/blog/2016/05/20/objects-larger-tha...
In the same way that since we identify unicode code points with a 16-bit value, it's impossible to include U+1D460 in a string?
In the same way that since Matroska files encode the length of their segments, there's a hard upper limit on the length of a segment?
Of course none of those things is actually true. Storing the string size has no implications for how long the string can be. It requires an amount of space, to store the string size, that is logarithmic in the length of the string, and completely insignificant.
What do you gain in handling short strings from an inability to handle long ones?
Flexible width encoding is more complicated compared to simple member access to get at the first character. And how do you handle construction of a string whose size you don't know yet? You might have to move the string away to make space for a bigger string length field. I don't like it.
I don't think this is true either. It's almost true. But what happens if the string length is 0?
If you make the assumption that you can access the first character of a zero-length string by just grabbing whatever is in memory after the string header, you're going to make the exact mistake the length field is there to stop you from making, a memory access violation. You have to process the length field in order to do any access at all; many strings don't have a first character.
> And how do you handle construction of a string whose size you don't know yet? You might have to move the string away to make space for a bigger string length field.
That's true; you'll either need to be willing to store the character data and the length metadata in separate locations, or you'll need to be willing to occasionally move the data around.
1. Read the first chunk of the string length.
2. Is it more than 0?
1. Read the first chunk of the string length.
2. Did we get the whole thing?
3. Is the length more than 0?
---
Also, it occurs to me that this whole discussion is talking about how to serialize or deserialize a string, when the original discussion is over how the string should be represented in memory.
Not a single 16-bit value. Some codepoints are two 16-bit values.
c0 (0b0000) -> length is 0xc = 12
1341 (0b0001) -> length is 0x134 = 69,940
239a42 (0b0010) -> length is 0x239a42 = 145,828
deadbeaf239a47 (0b0111) -> length is 0xdeadbeaf239a4 = 3917404957718948.
Maybe reserve 0x1111 for future use.
Maybe the other endian makes more sense here, and maybe 0 should mean zero-length.
It's probably not very performant compared to other solutions, but you can just shift 4 bits, and you're done
I'm curious how many strings are allocated at a particular point in time (across everything, kernel, os, apps, etc)
Other popular approaches to allocate strings dynamically would generally group strings of similar lifetime or by size, amortizing possible overheads over many strings.
If your favorite memory allocator requires a size field to support efficient deallocation, then by all means put that in the allocation record. But this is totally orthogonal to the format of a simple string representation.
In fact, in standard Pascal, string handling is extremely rudimentary; there was no way to express "this variable / parameter / pointer refers to a string with a length not known at compile-time".
https://www.iso.org/standard/18237.html
Additionally, Modula-2 was already available in 1978, sorting out all the issues of original Pascal, with all the features needed for a safe systems programming language in the late 70's.
Do you seriously expect in two years left of 70's for Modula-2 to be available everywhere?
But we digress. The topic at hand was "How does Pascal store strings?" I stand by the pedantic statement that ISO Standard Pascal does not require string lengths to be stored with the string (nor anywhere else); there's no way for the programmer to obtain the length of a string at compile-time, never mind run-time, without resorting to some sort of compiler-specific language extension (most (all?) of which did indeed put the string length in front). Conversely, the Extended Pascal standard pretty much requires strings to instead be implemented as "fat pointers," consisting of a length and a pointer to the actual characters. I say this because substring operations return references to pieces of the original string, thus you can't stuff a length in front of the actual characters of the substring, as this would over-write characters in the original string.
This has drawbacks:
1. you can't convert an existing buffer to an sds buffer
2. you can't slice into a buffer, because the metadata is part of the string's buffer (even if it's before the pointer)
Counterpoint #1: You can't pass SDS strings to functions that accept `char **` (which is a common way to return a string of unknown length, and often can act as an in-out parameter as well).
Counterpoint #2: You rarely access individual "characters" (whatever this means). It is a conscious decision to whether you should iterate over bytes or Unicode scalar values or code points or grapheme clusters, and for this reason it is better to make the decision explicit even though it's C `char` in the surface level.
I have no evidence for nor against advantage #3 though.
Malloc does this.
One obvious advantage of such scheme of course is that you can pass them as-is to C APIs
It is still single allocation, so the allocation is just as fast.
The pointer is in the same cache line as the string bytes in all strings except for slices (and any other fancy indirect string types). Even though the code fetches indirectly via that pointer, the CPU will be able to fetch the initial string byte efficiently as soon as it has the pointer.
The length-prefix string has a major problem - it cannot be sliced to produce another length-prefix string. It has to be copied. Instead, using a phat pointer (size_t length, char* ptr) works very, very well. We've been using it in D for 20 years.
I've proposed it for C, too:
Come again? Of course it can. It can't be done in place, mind you, but that's a pretty bad way to do any string slicing, regardless of implementation, in a manual memory management environment. Do most programmers expect their slices to result in undefined behavior if they release the larger string they were made from? I doubt it.
Oh come on.. I'm pretty sure Walter meant taking a view kind of slice. Obviously one can always copy part of a string, but that's not what slice implies I think.
> It can't be done in place, mind you, but that's a pretty bad way to do any string slicing, regardless of implementation, in a manual memory management environment.
It's not bad. It's the best, most efficient way. O(1)-ish.
> Do most programmers expect their slices to result in undefined behavior if they release the larger string they were made from? I doubt it.
That's what copy-on-write is for : release of the parent is blocked until no views are left on it.
I made a C String lib using CoW. It works well:
1. don't have to make a copy
2. don't have to scan to find the length
3. don't have to load the string into the cache to find its length
As a bonus, they're memory safe.
int x[10];
Sould mean "put 10 ints in memory, and make x the pointer to it.". The thing that messes this up is sizeof. sizeof(x) doesnt give the size of the pointer like it should, it gives you the size of the array. If that was fixed (obviusly it can without breaking everything) then things would be much better and consistent.
But "arrays" definitely are pointers. I put "arrays" in quote because C has nothing I would personally call an array. It’s just contiguous memory allocation. It’s to the point that 10[a] and a[10] are desugared to the same thing.
I guess the SDS authors might ship a linter to spot all the times you mistakenly use free() instead of sdsfree()? That could make the cleverness more tolerable?
It's pretty weird to see it anywhere other than malloc though especially masquerading as a basic type. It's incompatible with other common patterns like returning via (char *) and you can't identify which deallocator you're supposed to give the result to from the type alone.
But that seems like a valid case: e.g. these are comma-delimited lists of numbers:
"" // empty
"1" // one number
"20,30" // two numbers
I don't see coverage for this in the tests. There is a test which uses "123/456/789", which extracts the first two splits, and then just verifies that "789" remains. What the programmer wants is to be able to write a loop which will extract "123", "456" and "789" and then* hit the terminating case where the invalid str_t is returned.
How many items are in "1,2,3," viewed as comma-separated: three or four?
It would also be a code improvement to replace umpteen repetitions of "(str_t){.data = NULL, .size = 0}" throughout the code with a macro.
I want some struct that is a pointer to the char array `s’ with size_t `n’.
To meaningfully do this, it means you need auxiliary functions that you execute after calling string.h functions, or you write wrappers that do this for you after calling the relevant string.h functions.
I’m OK with that.
SDS doesn’t do this. Most other C string libraries like this one basically do what I’m asking for, but not quite.
I don’t want separate structs for reading and writing strings. I just want authors to keep it as simple as possible without diverging too hard from how C strings already work today.
This allows for nicer string handling while always allowing interop with anything expecting a char *. Libraries with their own string implementation always exact a penalty to get a cstr out.
https://pubs.opengroup.org/onlinepubs/9699919799/xrat/V4_xsh...
And it's quite easy to create an highlighting rule for it in vim if you still did not convert to treesitter. Just put in ~/.vim/after/c.vim :
```
syn match cType /\<\(t\|s\|e\|u\)_\w\+\>/
```
Boom, custom type highlighting for C ! Pick the the letters you will use.
Just
* have sane naming in your program.
* respect namespaces like _[A-Z] and __
* solve clashes that actually happen
Historically, revisions of POSIX have introduced identifiers that were not in any previously announced namespace. There is no way you can name an identifier that is guaranteed not to clash with POSIX, or any other vendor. For instance the name "openat" was fine to use in a POSIX program once upon a time.
Consider that all strings have the empty string as a suffix. The string "abc" has four suffixes: "abc", "bc", "c" and "".
So, every current and future POSIX identifier has "" as a suffix. This is not just a threat; it is guaranteed! Since every identifier in your program also has a "" suffix, it clashes with that namespace.
What's wrong with the argument is that identifiers don't just have a suffix; they have to be identical in order to actually clash. (Or have identical prefixes, due to truncation of external names in a linker: decades ago, the limits were ridiculously small.)
I doubt that even one person in POSIX standardization would be dumb enough to approve str_t being added as a typedef name in some existing or new header, and multiple approvals are required.
Nobody should be losing any sleep over using _t typedef names in their C code.
Why do you believe POSIX would never approve a str_t type? Nobody likes raw char arrays, perhaps a future revision of POSIX may decide to make the lives of C programmers easier and implement their own sane string type.
If you think it's necessary, it's very easy to make an argument that you'd have to have a generic type for slices of any type. (Actually, more so than strings, since C is just not a language for domains with a focus on strings).
Now, whether you think a language must have a generic slice type or not, C is simply not the language where you can fit that in.
Now extending the suffix to "_t" doesn't make it much less absurd. Not qualitatively, just a bit quantitatively less absurd.
Why I suspect POSIX isn't about to add a str_t is that str_t is likely to occur in countless numbers of unknown existing code bases.
And that might be a good reason for avoiding it in a library API, not the _t namespace being reserved.
We can have this variant of the argument: most identifiers end in a lower-case letter, so they land into any one of 26 namespaces: the *a namespace, the *b namespace, ... future POSIX identifiers have to be in one of these 26, except those that end in digits or underscores. POSIX does not say "future versions of this standard shall not claim new function or other identifiers ending in e". That doesn't mean you stay away from identifiers ending in "e", right?
I wouldn't avoid str_t in the internals of a program though. In the worst case, a clash happens somewhere and we do some renaming; life goes on.
POSIX's reservation doesn't really mean much; all they are saying is "we have some type names ending in _t, and will likely have more, so watch out". Yes, POSIX will likely have such names, and so will every C programmer and his dog. Whoppee dee. POSIX will likely have new names ending in 'e' also, and so on.
Only ISO C can officially reserve names, everyone else just has their personal code/naming style that you can chooseto follow or not.
Usually if there's nothing else meaningful that one can say about someone else's project, they will comment on the _t naming... and as anyone with a yota of real-world experience would know it's a complete non-issue outside of a handful top-tier open source projects.
Don't be that guy. Save this comment for when it may actually be relevant.
If you don't want to be banned, you're welcome to email hn@ycombinator.com and give us reason to believe that you'll follow the rules in the future. They're here: https://news.ycombinator.com/newsguidelines.html.
Naming things is one of the hardest problems in CS.
If rust string were str and strvec or strbuf no one would care.
What is important there is that the invalid string value is completely compatible with most C functions - despite actual data pointer is NULL, the length of data is zero so memcmp, memmove/memcpy and most other functions will not segfault.
This is really thought out approach.
Thank you!
printf("The string is %"PRIstr"\n", PRIstrarg(mystring));
But that's tedious to write. So create a small macro
#define ls(x) (x).size,(x).data
printf("the string is : %.*s", ls(mystr));
> #define ls(x) (x).size,(x).data
Doesn't that double-evaluate `x`?
Often, you have to both null-delimit your string and store its length somewhere. That’s the dangerous part. Messing either of those up, or passing your string to an API that messes that up, is not safe.
C strings are pointers to memory, either the stack or the heap, and follow exactly the same rules as everything else in that chaotic space: Not many.
I've done it for decades; it isn't really as bad as hype-attracting headlines would have you believe.
Munitions control, aircraft management systems, industrial automation systems, and many more life-critical systems were programmed in C for decades with comparatively little danger from the language intrinsics leading to death.
It's easy to look at the stats and say "there's a few dozen CVEs annually due to C footguns", but that's a few dozen out of hundreds of millions of deployed systems that are written in C.
In practice, very few lines of C code bypass the type system, so you get much fewer bugs than an equivalent system in the more usual dynamic programming languages (Python, Javascript, etc).
Yes, it is better to have memory safe languages. But it encourages sloppiness as "nothing can happen". Then those folks aren't fit to write anything else. Which closes the feedback loop on inefficient but safe languages.
Which becomes the same thing in airplanes. Pilots don't really know how to fly without instruments anymore.
Well that's just a blatantly wrong generalisation you made there, curious as to where you got that from. Consider looking up how pilot training is done before making such assumptions. Even though modern airplanes make heavy use of technology, there are emergency scenarios where lots of instruments may not work, and pilots receive more than enough training to fly an airplane in that scenario just to give one example among tons of others.
edit: grammar
https://www.businessinsider.com/too-many-pilots-cant-handle-...
Now, I'm not an expert into pilots statistics, so my example might be off, but I do see a worrisome pattern in my daily work (software engineering). Blind reliance on those "frameworks".
Which isn't bad in itself, but no-one really knows how they work anymore. They just assume. And that leads to lots of cargo cults. Which ranges from inefficient to outright dangerous.
One of the most complex representations is probably the string rope datastructure - a balanced tree of string chunks, supporting efficient insertion and removal anywhere in the string.
Specific to C, as well as lots of low-level APIs, is only that strings are often expected to be contiguously laid out in memory and terminated with a NUL (0) byte. So you need to make sure that you always terminate with a NUL after writing to string storage.
Other than that, strings aren't any harder than other aspects of programming with manually managed memory.
Maybe motivated from higher-level dynamic or managed languages, is the popular idea that strings should always be allocated dynamically (like std::string for example), and support operations like string-append with automatic reallocation if the currently allocated memory isn't enough to store the new string.
In practice, that's not true at all - unless you are in a domain where lots of small intermediate strings are generated. This is pretty inefficient anyway and there is likely no point to use C in this case.
By far most strings in most domains are either completely static (use string literals), or are created once in a sequence of append operations and then never changed again. I get by, doing many different things from GUI apps to networking to parsers and interpreters, without any sophisticated string type. All I do is define some printf-like APIs to do logging, for example. Those typically just use a fixed size buffer for the formatting, and then flush that buffer to e.g. stderr. or flush it to a dynamically allocated memory buffer, but there almost never is a need to reallocate that string later.
https://kttnr.net/blog/null-terminated-strings-are-incorrect...
How do you get the null byte into the string? Is it through casting blob to string? The way I have encountered this is when using the C API in which string arguments for prepared statements are passed as char pointers. If those contain the null byte then the string is cut off.
Allowing null characters and then mishandling them is worse than not allowing them.
So, you can’t ask it to create a string that contains the result of appending a string to another one. If you want to append two ‘strings’, you have to create a buffer large enough to hold the result, and then copy in the two sequences of bytes. And even for doing that, the library functions aren’t optimal. The basic “append this string’s data to that string, assuming there’s enough space to do so” function is strcat. It walks the first string to find the zero byte, but to “create a buffer large enough to hold the result” you already must do that.
See for example https://stackoverflow.com/questions/21880730/c-what-is-the-b...
len = snprintf(buffer, buffersize, "%s%s%d", string_1, string_2, int_1);
if (len + 1 /*NUL*/ > buffersize)
{
// not enough space
}
len = snprintf(NULL, 0, ....);
buffersize = len + 1; /* NUL */
buffer = allocate(buffersize);
snprintf(buffer, buffersize, ... /*same args as before*/);It won't be as fast, but it's almost always not a problem, and the nice thing about C and C++ is that the char-by-char route is still available when it is.
I like to use asprintf, when available: https://man7.org/linux/man-pages/man3/asprintf.3.html - and when not available, I add it, along the lines of the snippet you present.
Here's something I've found a useful upgrade to asprintf, as it frees the passed-in buffer after expanding the format string. You can just pass the same char ** repeatedly and it'll update the char * appropriately each time.
int xasprintf(char**p,const char *fmt,..) {
int n=0;
char *p2=nullptr;
if(fmt) {
va_list v;
va_start(v);
n=asprintf(&p2,fmt,v);
va_end(v);
}
if(n>=0) {
free(*p);
*p=p2;
}
return n;
}Back in the 90s, I was very experienced with C strings and managing them. Then I chanced to look at BASIC again, and realized that strings in BASIC were so simple and intuitive. Why couldn't C be like that? When I started on the design of D, I decided that it had to make strings as easy to do as BASIC did.
And D does.
The trouble with C strings is the 0 termination of them. This means:
1. to get the length of the string, you have to scan it. This is expensive.
2. when manipulating strings, a common error is to get off by one in the storage because of the 0 termination
3. you cannot get a subset of the string without making a copy. Not only is a copy expensive, but then you have to keep track of the memory for it
4. there's no way to check for buffer overflows
D's design, which uses a phat pointer (length, ptr) for strings, solves these problems.
It is a bit shame that BASIC has such a bad reputation, there are many BASIC dialects that does the job well still today.
https://www.purebasic.com/documentation/reference/ug_string....
typedef struct str_t {
const char* data;
size_t size;
} str_t;
Kudos for having a go at it.
For the C++ case, it's not that easy due to C code that cannot handle exceptions thrown in C++ code.
For the Rust bit, I'm not sure - creating the library in Rust and letting it be called from C makes the whole rust library unsafe because the data returned from the Rust API would lose ownership information, and is no more safe than simply writing it in C.
2. It has terrible overhead.
So effectively a str_t works like an std::string_view from C++, and strbuf_t works like an inline std::string.
To produce a null-terminated string from a section of a longer string requires an allocation, unless you can temporarily modify the original string to replace one of its characters with a terminator.
That is just plain reading of "null terminator at the end of the buffer", as 'buffer' is just place in memory, regardless of what is stored in it. 'End of the buffer' is commonly used for end of such reserved memory, not end of valid data in that memory.
But maintaining the null-terminated string in the buffer is much more useful behavior than just maintaining null terminator at the end of the buffer, so it is likely just sloppiness in the documentation.