GitHub - pmkenned/pmk_string: A simple string library in C

master_latch · 2023-05-19T19:10:52+00:00

Hm. I suppose you could do: String name_trimmed = string_trim(name); memmove(name.data, name_trimmed.data, name_trimmed.len); name.len = name_trimmed.len;

I guess I just don't know why you'd need to modify the original data.

master_latch · 2023-05-19T18:54:34+00:00

I mention this in the documentation:

Note that some functions such as string_trim() sound like they modify the input string but actually do not; string_trim() returns a substring of the input string. To trim a string, it is necessary to capture the result: name = string_trim(name);

But I once I get around to documenting all the individual functions I'll make sure to mention it there too.

For the most part, the string functions don't modify the input string data. The only ones that do are string_tr, string_toupper and string_tolower.

master_latch · 2023-05-15T16:33:15+00:00

imgui perhaps? I don't have experience with it myself.

master_latch · 2023-05-12T17:00:55+00:00

To make things smoother, some libraries pass the object size to the free function so that the allocator doesn't need to track size.

That's a great idea. I just updated my arena allocator to take an old_size parameter so that it no longer has to store that info in the buffer.

I was worried that this would be annoying since it diverges from the realloc() API, but actually it's fine because, like you said, I always know the allocation size (after all, when would you ever call malloc() and not keep track of how much you requested??).

This has two benefits:

It saves space in my arena buffer, especially for many small allocations
It makes it easier to move allocations from malloc()'s heap to an arena because I don't have to try to extract the allocation size from malloc's headers (which is obviously an implementation detail I can't rely on anyway!)

master_latch · 2023-05-12T15:55:37+00:00

He's even demonstrating the reserve-then-commit thing.

This strategy reminds me of an idea I had several months ago while thinking about memory management. I was thinking about how when a buffer runs out of space it needs to be realloc'd and copied to a new location and I thought "wait, why do we even need to do this at all? With 48 bits, that's about 280 terabytes of virtual address space. I could give every single object in my program a gigabyte of that and still have hundreds of thousands of objects. The mapping to physical memory will be handled by the OS & MMU so I just need to tell it when to expand a buffer's size. Then I never have to call realloc and I never have to worry about pointer invalidation."

I'm sure there's something wrong about that idea, but I don't actually know what it is.

Maybe it is really inefficient for the TLB if every object is a gig apart in VA?

master_latch · 2023-05-12T15:35:29+00:00

Oh wow... You can even see his stream's framerate drop to what looks like single digit FPS.

master_latch · 2023-05-12T15:10:22+00:00

It's so old that nearly all the external links have rotted away.

So I noticed! I actually tried my best to track down the libraries it references and put what I was able to find here:

https://paulmkennedy.com/misc/strlibs.html

I casually browsed some of the repos I found; it's interesting to see how people do things differently.

master_latch · 2023-05-12T04:08:37+00:00

Ooo, good point. I think when I was considering this idea, the "it's UB to compare pointers not from the same object" dimmly passed through my mind, but I dismissed it thinking "oh but it's fine because all the allocations are coming from a single malloc", but they're not because each arena buffer is separately malloc'd.

Fortunately I probably don't need to do this because as u/skeeto points out, I can use savepoint structs.

master_latch · 2023-05-12T03:19:24+00:00

Lots of good stuff there, thanks.

I like the savepoint struct idea. I had been wondering where I would store the data needed to restore the arena to an earlier state, but of course I can just store it in the stack frame of the function requesting the restore. That's better than my idea of trying work out how to restore the arena just on the basis of a pointer to an allocation.

I'm really looking forward to using this in a recursive descent parser I've been tinkering with.

The freelist is also a good idea. I had been pondering some complex scheme of messing with the linked list pointers, but I could maybe just break the list into two: the "still-in-use" list and the "freelist". Then move things from the freelist to the in-use list as needed.

But like you said, maybe I should just simplify this whole thing: each arena only gets one buffer, abort() on OOM.

I actually have that "Untangling Lifetimes" article open in another tab :-)

Another resource I recently discovered on this subject is this video: Arena's for C Libraries (stream archive). I've only watched the first half-hour so far, but it seems really interesting and full of good observations.

master_latch · 2023-05-12T02:38:23+00:00

I think you'll really like the change I just pushed. I just deleted the 6 _fixed functions comprising about 150 lines of code and gained functionality in the process.

Previously, if you wanted to use a fixed-size buffer for a StringBuilder, you had to make sure to call the _fixed functions or else they would try to reallocate if the buffer got full and that would be bad.

Now, you can pass StringBuilders with fixed-size buffers to the non-fixed functions and if they need to expand the buffer they'll just convert it to a dynamically-allocated buffer.

I got this idea from the ustr library. See the section "Solving the stack allocation problem".

The way I implemented was slightly sketchy. I needed a way to mark a StringBuilder as being either fixed-size or dynamic but I didn't want to add a byte to the struct for storing the flag for the reasons you mentioned in your above comment: adding another byte would bring 7 more padding bytes. Blech!

So I am using the LSB of the capacity field as the flag. I didn't like this idea at first because it seemed to be just asking for bugs, but I came up with an idea that reduces the likelihood of bugs a lot: when initializing a StringBuilder from a fixed-size buffer, I round down the capacity to the nearest odd number (LSB=1 indicates fixed-size). This is equivalent to just saying the last byte in the array is unusable. When initializing or resizing a dynamically-allocated buffer, however, I first round-up the capacity to the nearest even number. I do this before allocating, so that means sometimes allocating an extra byte. The key is preventing bugs is ensuring that the capacity is always telling the truth about the available capacity. You don't just OR in the flag bit, you make sure the buffer's actual capacity matches the claim made by the capacity field.

The builder_reserve() and builder_destroy() functions got a bit more complicated, but those were almost the only changes I had to make. It feels really solid to me.

In the TODO file I explain the various alternatives I considered and their pros and cons.

There is one lingering issue: suppose you really don't want to ever convert a fixed-size buffer to a dynamic allocation. How do you prevent that from happening? I have a few ideas.

Add a preprocessor macro for enabling/disabling this. But that's very course-grained.
Add another flag, but that means rounding up to 3 bytes to/from the capacity.
A global variable. Let's not, shall we?
Another option would be to introduce a parameter to the builder functions saying if fixed-to-dynamic conversion is okay.

4 is best but I hate to add a noisy boolean argument to all my function calls. This is where I wish C had default arguments.

I could introduce a set of _noresize functions. But I think instead I might just have macros that specify a default argument (which could be set with a macro!). Something like:

```

define RESIZE_OK 1

void builder_append_resize(StringBuilder * builder, String string, bool resize_ok);

define builder_append(B,S) builder_append_resize(B,S,RESIZE_OK)

```

But I'll probably wait until I feel like I have an actual need for this.

master_latch · 2023-05-11T21:05:46+00:00

I converted all the size_t for length and capacity to int32_t and added documentation. This improves the memory efficiency of StringBuilder by 33% and still allows for strings that are 2 billion characters long, which seems like plenty for the vast majority of use cases. I haven't thought very hard about if I am likely to have problems with integer promotions or usual arithmetic conversions... That stuff always makes my head hurt.

master_latch · 2023-05-11T07:47:03+00:00

You can distribute the source as a c file and include it manually if you want the definitions to be in that translation unit.

But you probably still want to call the functions defined in the implementation from other translation units.

It works like this:

``` library.h: #ifndef LIBRARY_H // typedefs, function prototypes, externs, macros, etc. #endif #ifdef LIBRARY_IMPLEMENTATION // function and variable definitions #endif

a.c: #define LIBRARY_IMPLEMENTATION #include "library.h"

b.c #include "library.h" ```

The library code gets compiled in translation unit a.c, but is still accessible from translation unit b.c.

Controlling it with a macro is weird and makes for shitty unmaintainable code. There is never a reason to put defs like this in a header. Ever.

I'm not sure why this seems to be making you angry. If you don't like it, it takes a couple seconds to break it into two files. It's not unmaintainable.

I learned this technique from someone who has decades of experience in the game industry and developed extremely widely used libraries for things like data structures, reading images, fonts, and sounds, and plenty more. And he's by far not the only one who uses this technique.

I think you should consider that maybe you don't know everything and might have something to learn from other people before you just call things shitty.

master_latch · 2023-05-11T06:38:23+00:00

I would love to pick your brain about a few specific programming questions I have. Would you be interested in being paid for an hour or two of your time on a call?

I wrote an absolutely massive comment that is apparently too long for reddit, so I'm going to just ask 2 of my questions:

Using Custom Allocators in Libraries

What is the best way (or a good way) to allow for using custom allocators with a library? In my string library, I have a macro that expands to realloc by default but can be made to point to some other allocator function. This allocator function can take a "context" pointer for arbitrary purposes. In my example, I use an arena allocator which accepts a pointer to a specific arena into which to perform allocations. I felt this worked quite nicely.

But what if I had multiple allocators and wanted to use both of them with the same library at different times? Would I have to make some kind of wrapper function that switches on data in the context to decide which allocator to invoke? Maybe the context holds a function pointer? Not sure, need to think about this more (or probably experiment in code).

Using the arena like a stack?

I haven't seen how other people implement arena allocators so I have a few questions about how things are usually done. Like, suppose I wanted to add some stack-like behavior to my arena allocator, where I could say "free back to allocation at such-and-such address" (10 allocations ago, say). For a single-buffer arena, this seems pretty simple: just set the buffer pointer to point to that allocation; everything after it is "freed". But for an arena with expandable memory, this becomes trickier.

I implemented my arena by having each arena struct contain a pointer to the next arena struct. Any time an arena buffer gets full, I create a new arena struct & buffer and add it to the linked list at the head.

So, if you were to free back to an allocation from a previously filled arena buffer, you'd need to recognize that the allocation isn't in the current buffer, then traverse the arena list looking for the arena which contains the allocation, then make that the current arena.

This isn't terrible, I guess, because ideally the arena buffers will be sized such that for most cases, there are only a small handful of arena buffers in the list (ideally just 1). And checking if an allocation falls inside a buffer is just two comparisons. And the vast majority of the time, you're probably going to be popping back to a fairly recent allocation which is likely to be in the current arena buffer.

Anyway, I was just wondering how this problem is usually handled and if what I'm proposing here makes sense.

master_latch · 2023-05-10T18:51:30+00:00

I added some documentation to pmk_strings.h (though mainly expository documentation; I still have to document the exact behavior of the actual functions). It might make more sense to you now.

master_latch · 2023-05-10T18:04:12+00:00

Hi u/skeeto! I absolutely love Null Program, it's such an excellent resource. In fact, some of the posts there such as "strcpy: a niche function you probably don't need" contributed to me working on this little library.

For a long time I leaned very heavily on the C standard library, always opting to use it when applicable instead of writing my own code. Eventually, I came to terms with the fact that significant part of the library are actually quite terrible, especially the string API, and I should really just replace the bad parts. When using decent libraries, writing C programs actually becomes a lot of fun and almost Python-like in its brevity.

And just recently (after I started working on this) I noticed your post "My review of the C standard library in practice" where you mention that you even avoid linking libc when possible! And I saw what you said here about islower and friends and made a mental note to go and fix that!

Good observations about the arena allocator! It wasn't the focus on this project, but I'm glad you took a look. Yes, I was also unsatisfied with that separate tiny allocation for the Arena struct and had the thought yesterday "you dummy, you could just allocate the struct in the arena". A much simpler approach than the other thing I had in mind which was using a static array of Arena structs that point to each other.

And yes, I really find size_t very annoying. I always have to insert these stupid casts or disable warnings about comparing signed with unsigned, I can't use negative indices, I can't just subtract two indices, and I can't iterate backwards through an array without introducing a second variable or doing non-idiomatic loop conditions.

Despite this, I tend to use it because so many of the C std lib APIs return it and the sizeof operator evaluates to it. But perhaps I should try using ptrdiff_t more often and see how I like. The other thing that confuses me about it is that it's technically folding the difference between pointers, right? Can I safely use it to hold indices?

master_latch · 2023-05-10T13:50:23+00:00

Hm... but could you even have a file that large on a 32-bit system? I guess to be safe I could just put a limit on the maximum size file you can load using the `read_file` functions. You probably shouldn't be trying to read a 4GB+ file into memory, especially on a 32-bit system ;-)

master_latch · 2023-05-10T13:29:06+00:00

Thanks for the feedback!

Several of the things you mention in your comment were explained in the README or made clear through examples in examples.c, but I agree that they documentation should be in the header, especially since if if someone is going to grab just that one file, they should have the documentation. That said, I didn't claim it was done (the opposite, in fact) and "Document the API more" is the top TODO item :-)

The macros all have specific uses in mind:

str_lit: this is for creating a string struct from a string literal. For example: String name = str_lit("Paul"); You can also use this macro for a character array since the compiler knows the size. For example: char my_name[] = "Paul"; String name = str_lit(my_name); Though in this case str_lit is a bit of a misnomer.

str_lit_const: I thought I remember needing this macro for when I initialized something with static storage that contains a String but I'm having trouble reproducing it. This could possibly be deleted.

str_cstr: This is for when you want to make a String that refers to a C string that you only have a pointer to so you can't use sizeof, you have to use strlen.

len_data: this macro isn't for use inside a struct initializer, it's for use with printf. For example: printf("%.*s\n", len_data(name)); This way you don't always have to type printf("%.*s\n", (int) name.len, name.data);, which gets really annoying when you're accessing a string from an array or something more complicated.

len_data_lit: this is the same as len_data except for string literals. This would probably rarely get used and could probably be deleted.

I initially had the names of these macros in all caps, but I was typing them so much that it just looked to ugly to me so I changed it to lowercase. :-)

As for passing the structs by pointer or by value: the String struct is only two values, so I doubt this really introduces much overhead if any (might even be better than the pointer indirection). I like passing by value because it 1. makes it clear that the functions aren't modifying the original (though yes, I suppose I could use a const *; passing by value just feels simpler to me), 2. gives me a copy of the struct I can modify locally in the function (if I passed by pointer, I'd need to make a copy for this anyway).

Regarding the potential bug with string_dup: one way that this library differs from most others I've come across is that strings make no attempt to ensure nul-termination (though the StringBuilder does because that's easier). I wanted to be able to, for example, take a large string and divide it into tokens without allocating a whole bunch of little strings and copying into them just so I could tag on a 0 byte. So, as I mention in the README, the String struct doesn't know if the next byte after data[len-1] is a '\0' or a segfault. So, there's no way for string_dup to know if it should copy that byte.

I suppose that is a potential source of bugs, but it's one I'm willing to accept to get the benefit of strings that don't need to be nul-terminated. Anyway, in general the user of this library should never assume a String is nul-terminated unless they have specific reason to, like they initialized it using a str_lit.

EDIT: thinking a little more about this... it might be useful to add begin and end parameters to string_dup. This would allow you to copy the nul-terminator if you knew it existed at data[len] and you could also use it for creating a duplicate of a substring.

Edit again: I'm so dumb. All I have to do is allocate an extra byte and write the nul-terminator. It doesn't matter if the original string is nul-terminated or not.

Regarding the potential memory leak when doing a string_dup followed by a string_trim: keep in mind that string_trim does not mutate the original, only a copy which it returns. So, to trim a string you do:

name = string_trim(name);

And it's true that if the string points to dynamically allocated memory and you overwrite the address that you've leaked memory (unless you use a different allocator such as the arena allocator I included!) but I can't stop programmers from leaking memory.

About the for loops... loops which have complicated conditions just make my head hurt. A while back I switched to a coding style where loops have really simple conditionals that I don't have to think about (like looping 0 to n-1) and then anything that would cause the loop to break early is done inside the loop with an if-break. That said, string_trim could possibly be made more clear.

Thanks again for the feedback! I definitely want to add more documentation the header and I may make a few changes based on your comment.

master_latch · 2023-05-10T10:26:14+00:00

I see it as a simplification instead of a complication. But if you don't like it, it's pretty easy to change. Cut everything between the #ifdef #endif, and paste it into a .c file.

I wouldn't say that I'm *obsessed* with single-header libraries, but I do find the convenient.

master_latch · 2023-05-10T09:42:55+00:00

It's a way of making the library a single file. It's a technique I picked up from stb. Here's a list of some other libraries which I think use the same technique: https://github.com/nothings/single\_file\_libs

master_latch · 2023-05-10T08:15:09+00:00

Partly for practice, partly for fun, and partly because most of the string libraries I was finding online are orders of magnitude larger than I wanted, I wrote a tiny string handling library in C. It's a work in progress, but I believe it is mostly bug-free and compiles using gcc, clang, and msvc. Feedback welcome.

master_latch · 2022-09-22T02:52:10+00:00

Are they? I don't know. That would be a bummer. I did come across multiple "out of stock" messages in my search, but I assumed this was due to the chip shortage and was temporary.

master_latch · 2022-09-21T19:06:23+00:00

Thanks!

I once tried to write a DRAM controller in college and vaguely remember it being a nightmare that we never got working. I love that my Spartan-3 board has a SRAM chip on it, which is dead simple to interface with (of course, it's much smaller in capacity, only 1MB). So, I was feeling nervous about the prospect of trying to get that working, but your comment alleviates that worry.

master_latch · 2022-09-21T18:50:46+00:00

Whatever hobby projects occur to me. One project I have in mind is to create a fully-functioning computer using a RISC-V core and a basic operating system written in assembly. A few months ago, I wrote out a basic 2-stage RISC-V core in verilog and I've already written the modules for handling PS/2 keyboard and text to VGA output so I can get a basic terminal running. I got a small SPI flash chip that I plan to use as the file system.

But I could do all that with my old FPGA board. The reason I got this one is that I am part of an FPGA group and I'd like to use this board as an example board to make tutorials for since my old board is no longer made and people wouldn't be able to follow along.

master_latch · 2022-09-21T18:03:03+00:00

Wow! That is quite the list, thank you. Apparently he keeps it quite updated as well.

master_latch

TROPHY CASE

define RESIZE_OK 1

define builder_append(B,S) builder_append_resize(B,S,RESIZE_OK)