Making a StringBuffer in C, and questioning my sanity

Making a StringBuffer in C, and questioning my sanity(briandouglas.ie)

46 points by coneonthefloor 307 days ago | 55 comments

o11c 303 days ago |

Hm, this implementation seems allergic to passing types by value, which eliminates half of the allocations. It also makes the mistake of being mutable-first, and provides some fundamentally-inefficient operations.

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.

zahlman 303 days ago | |

> It also makes the mistake of being mutable-first

Is mutability not part of the point of having a string buffer? Wouldn't the corresponding immutable type just be a string?

o11c 303 days ago | | |

"Buffer" just means it is used between input and output. It does not imply mutability, and many buffers indeed only take their state at construction time and are not mutable.

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

Immutable methods:

  print
  index_of
  match_all
  split

Mutable methods:

  append
  prepend (inefficient!)
  remove
  replace

I've already mentioned `append`, and I suppose I can grant `prepend` for symmetry (though note that immutable strings do provide some sort of `concatenate`, though beware efficiency concerns). Immutable strings ubiquitously provide `replace` (and `remove` is just `replace` with an empty string), which are much safer/easier to use.

There are also a lot of common operations not provided here. And the ones that are provided fail to work with `StringBuffer` input.

remexre 303 days ago | |

How would you recommend doing that sort of "subtyping"? _Generic and macros?

o11c 303 days ago | | |

Yup. It's a lot saner in C++, but people who refuse to use C++ for political reasons can do it the ugly way using C11 or GNU C.

amelius 303 days ago | |

I wonder how an LLM would rate this code.

lelanthran 303 days ago | | |

> I wonder how an LLM would rate this code.

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.

WalterBright 303 days ago |

    new_capacity *= 2;

A better value is to increase size by 1.5:

https://stackoverflow.com/questions/1100311/what-is-the-idea...

kazinator 302 days ago |

There is a way for this not to terminate:

  while (new_capacity < required) {
    new_capacity *= 2;
  }

1. All variables are unsigned (due to being size_t). So we don't worry about overflow UB.

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.

burnt-resistor 303 days ago |

It can be refactored into creating a buffer primitive of void* buf, size_t capacity, size_t refcount. Then, the string can implement using CoW logic on a buffer and size_t length. Read-only references to substrings become cheap and copying is done whenever there's a modification or realloc can't grow the underlying buffer.

ranger_danger 303 days ago |

You might be interested in https://github.com/antirez/sds

fsckboy 303 days ago | |

neat, i like it, has some of the same ideas i've used in my string packages

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!

ranger_danger 303 days ago | | |

> The null terminator is a wasted field

I think that would break its "Compatible with normal C string functions" feature.

gblargg 303 days ago |

It's odd how it has error reporting in some areas (alloc, split can return NULL if allocation fails), but not others (append, prepend have a void return type but might require allocation internally).

teo_zero 302 days ago |

What I don't like is that some functions take as arguments a mix of StringBuffer's and regular C strings. This is confusing. For example why this:

  void StringBuffer_replace(StringBuffer *buf,
    const char *original,
    const char *update,
    size_t from);

instead of this:

  void StringBuffer_replace(StringBuffer *buf,
    const StringBuffer *original,
    const StringBuffer *update,
    size_t from);

p0w3n3d 303 days ago |

By the way, I have no power here, but you people are ubiquitous, at least one of you is in C committee.

Hereby I propose an addition to C:

  namespace something { }

Which is preprocessing to something_ before every function

  class someclass { }

Which is preprocessing all the functions inside to

  someclass_fn1(someclass\* asfirstparameter, ...)

And of course the final syntax sugar

  cl\* c;
  c->fn1(a,b)

I mean this would make C much easier, as we already code object oriented in it, but the amount of preprocessing, unreadability that needs to be done in headers is simply brain exhausting

improgrammer007 303 days ago |

I would rather focus on solving the main problem than reinvent the wheel. Just use C++ if perf is critical which gives you all these things for free. In this day and age the reasons for using C as your main language should be almost zero.

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)

// 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();