4 ms·
make str_t an opaque type. First char is always length. 1. If string is 0-15 chars long, str_t is a small string, aka char[16]. First byte is length, payload s
by crpatino 11y ago
make str_t an opaque type. First char is always length.
1. If string is 0-15 chars long, str_t is a small string, aka char[16]. First byte is length, payload starts in 2nd byte, tail is always zeroed. Empty string is all zeros always.
2. If string is 16-248, str_t is a half string. The whole payload exist in a single contiguous buffer. First bytes is length. A pointer to the rest of the payload exist within the remaining 15 bytes, starting at the first alligned address. This way you can cast half string as small string when passing as value without knowing the size at compile time (and stil recover the rest of the payload). Gap between the length and the pointer is reserved and always zeroed.
3. For lengths 249 and higher. Each value 249-255 is not the lenght, but an encoded way to represent one or more styles of bigger strings. Not need to hold the payload in a single contiguous buffer. Remaining 15 bytes will hold a pointer to the data structure in the same fashion as half string. Reserved bytes are used to represent length if possible. If not, length is required to exist at a fixed position in the first buffer accesible when dereferencing the pointer.
- christianmann 11y agoAre there any other types in C that allocate space on the heap? Is that even possible in C? Not C++; there we have std::string, which is much as you describe above.
- jandrese 11y agoWow, that sounds nightmarish. Three different ways to store the string, pointers to buffers everywhere, and because it is so complex your string library needs to account for all possibilities because there's no way anybody is going to want to manually twiddle with those strings. If you get it right and hide all of the complexity from the user then it's not quite as bad, although undoubtedly confusing the first few times someone inspects it in their debugger.
- blt 11y agoI used to work for a company that whose C++ string class worked like this, although not quite as intricate. Had a separate mode for statically compiled strings too. It was pretty nice, although I didn't agree with every style choice. Makes some branchy code though. In Visual Studio debugger you can write scripts to pretty-print string variables in the "watch" window, I would guess other good debuggers can do this too.
- crpatino 11y agoString operations are intrinsically complex by nature. At least they are now in this age that you cannot assume the encoding is always ASCII. The goodness of this approach is that if you just need to pass around the string, a shallow copy of the first 16 byte block is enough. It might or might not contain the whole of the array, but if you need to know, it means you need to go through all the corner cases, no strcat(small_buffer, unsanitized_user_input), thank you very much!
- crpatino 11y agoYEs, you are right... it is very complex. But it is consistent enought that the compiler can do it all in the background. If you think that it is a bad idea to do: str_t* string = (str_t*)malloc(string_length); then half of the goal is been achieved right there. The other half is to have this nailed down in the language definition in sufficient detail so that implementations do not differ widely and you can poke inside it with assembly when you have to.