The main mistake that this makes in common with most string implementations make is to only provide a single type, rather than a series of mostly-compatible types that can be used generically in common contexts, but which differ in ways that sometimes matter. Ownership, lifetime, representation, etc.
Is mutability not part of the point of having a string buffer? Wouldn't the corresponding immutable type just be a string?
In my experience, the only functions a mutable string buffer needs to provide are "append string (or to-string-able)" and "undo that append" (which mostly comes up in list-like contexts, e.g. to remove a final comma); for everything else you can convert to an immutable string first.
(theoretically there might be a "split and clobber" function like `strtok`, but in my experience it isn't that useful once your APIs actually take a buffer class).
Considering the functions from this implementation, they can be divided as follows:
Lifetime methods:
init
free
clear
print
index_of
match_all
split
append
prepend (inefficient!)
remove
replace
There are also a lot of common operations not provided here. And the ones that are provided fail to work with `StringBuffer` input.
I dunno how it rates it now, but if this link: https://www.reddit.com/r/programming/comments/1m3dg0l/making... gets used for future training, future LLMs might make good suggestions for cleaning it up.
new_capacity *= 2;
https://stackoverflow.com/questions/1100311/what-is-the-idea...
At the small end, on the real machine tiny allocations are inefficient, so rather than 1, 2, 3, 5, 8, 12, 27, 41 turns out we should probably start with 16 or even 64 bytes.
Then at the large end the "clever" reuse is a nonsense because of virtual memory, so that 1598, 2397, 3596 doesn't work out as cleanly as 1024, 2048, 4096
Folly has a growable array type which talks a big game on this 1.5 factor, but as I indicated above they quietly disable this "optimisation" for both small and large sizes in the code itself.
Of course YMMV, it is entirely possible that some particular application gets a noticeable speedup from a hand rolled 1.8x growth factor, or from starting at size 18 or whatever.
Clearly we don't just want a blanket constant, but the growth factor should be a function of the current length - decreasing as the size of the array grows.
For space optimization an ideal growth factor is 1+1/√(length). In the above example, where we have 2 Gi array, we would grow it only by 64ki elements. Obviously this results in many more allocations, and would only use this technique where we're optimizing for space rather than time.
We don't want to be messing around with square roots, and ideally, we want arrays to always be a multiple of some power of 2, so the trick is to approximate the square root:
inline int64_t approx_sqrt(int64_t length) {
return 1 << (64 - __builtin_clzll(length)) / 2;
// if C23, use stdc_first_leading_one_ull() from <stdbit.h>
}
inline int64_t new_length(int64_t length) {
if (length == 0) return 1;
return length + approx_sqrt(length);
}
old length: 2^16 -> new length: 0x00010100 (growth: 2^8)
old length: 2^17 -> new length: 0x00020200 (growth: 2^9)
old length: 2^18 -> new length: 0x00040200 (growth: 2^9)
old length: 2^19 -> new length: 0x00080400 (growth: 2^10)
old length: 2^20 -> new length: 0x00100400 (growth: 2^10)
old length: 2^21 -> new length: 0x00200800 (growth: 2^11)
old length: 2^22 -> new length: 0x00400800 (growth: 2^11)
old length: 2^23 -> new length: 0x00801000 (growth: 2^12)
old length: 2^24 -> new length: 0x01001000 (growth: 2^12)
old length: 2^25 -> new length: 0x02002000 (growth: 2^13)
old length: 2^26 -> new length: 0x04002000 (growth: 2^13)
old length: 2^27 -> new length: 0x08004000 (growth: 2^14)
old length: 2^28 -> new length: 0x10004000 (growth: 2^14)
old length: 2^29 -> new length: 0x20008000 (growth: 2^15)
old length: 2^30 -> new length: 0x40008000 (growth: 2^15)
old length: 2^31 -> new length: 0x80010000 (growth: 2^16)
[1]:https://cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf
while (new_capacity < required) {
new_capacity *= 2;
}
2. new_capacity * 2 always produces an even number, whether truncating or not.
3. Supppose required is SIZE_MAX, the highest value of size_t; note that this is an odd number.
4. Therefore new_capacity * 2 is always < required; loop does not terminate.
but i did see a place to shave a byte in the sds data struct. The null terminator is a wasted field, that byte (or int) should be used to store the amount of free space left in the buffer (as a proxy for strlen). When there is no space left in the buffer, the free space value will be.... a very convenient 0 heheh
hey, OP said he wants to be a better C programmer!
I think that would break its "Compatible with normal C string functions" feature.
void StringBuffer_replace(StringBuffer *buf,
const char *original,
const char *update,
size_t from);
void StringBuffer_replace(StringBuffer *buf,
const StringBuffer *original,
const StringBuffer *update,
size_t from);Hereby I propose an addition to C:
namespace something { }
class someclass { }
someclass_fn1(someclass\* asfirstparameter, ...)
cl\* c;
c->fn1(a,b)
Unfortunately, you will need to cover more ground with this proposal than what you have presented. It sounds simple but what you are suggesting is very complicated. Of course, to the OOP minds out there, they think their suggestion is a be-all-to-end-all, when in reality there are many ways to solve a problem.
I understand what you are trying to do. I am not suggesting it is wrong but C is not an OOP language. I dont see why we should PRETEND that it has OOP-class features when its all you advocating is smoke and mirrors.
Sure, C can do "OOP" but I must remind all that these techniques have been in C for years, before the OOP name was popularised and evolved into the form it is now. You are just forcing C programmers to program in such a way OOPLOVERS like when it is not required - and that is the modern OOP than has been forced on everything since the early-to-mid 90's.
You are just HIDING whats really going on
This proposal you are suggesting -- I am going to call this Typescript-C.
The problem is that this namespace/class overlay makes much ASSUMPTIONS what the programmer wants. Lets dig into this further. Here is how (I believe) you see it implemented :-
// In my TypeScript-C.
namespace Foo {
class Bar {
int baz;
void init() {
this->baz = 10;
}
void free() {
// whatever
}
int process(int withval) {
return withval + this->baz;
}
}
}
// calling example :-
Foo.Bar sample;
sample->init();
printf("%d\n", sample->process(100));
sample->free();
// Translated C...
typedef struct Foo_Bar {
int baz;
}
void Foo_Bar_init(Foo_Bar *self) {
self->baz = 10;
}
void Foo_Bar_free(Foo_Bar *self) {
// whatever
}
int Foo_bar_process(Foo_Bar \*self, int withval) {
return withval + self->baz;
}
// calling example :-
Foo_Bar sample;
Foo_Bar_init(&sample);
printf("%d\n", Foo_Bar_process(&sample, 100));
Foo_Bar_free();
If anyone is THAT bad they cannot write proper C code, then I suggest they move to C++, Java, C#, Dlang.. or whatever.
Its just adding extra fluff -- and C guys like to SEE what is going on. (Thats why it takes ages to truly grasp C++ internals)
However while we're looking at any library, GTK for example, those structs are made like that. But you're right - this only looks simple, as there are many pitfalls we could hit when implementing it.