StringBuilder in C

Question

Lots of languages have something that lets you build up a dynamically-sized string with minimal overhead. C doesn't, and I found myself using code that did that manually in a couple of places, so I packaged it into a class. Note that I've only implemented functionality I'm using.

stringbuilder.h:

#ifndef CONCATEN_STRINGBUILDER_H
#define CONCATEN_STRINGBUILDER_H

#include <stddef.h>
#include <stdbool.h>

struct stringbuilder_s;
typedef struct stringbuilder_s *stringbuilder_t;
stringbuilder_t sb_new(size_t);
bool sb_append(stringbuilder_t, char);
char *sb_as_string(stringbuilder_t);
void sb_free(stringbuilder_t);

#endif //CONCATEN_STRINGBUILDER_H

stringbuilder.c:

#include <stdlib.h>
#include <string.h>
#include "stringbuilder.h"

struct stringbuilder_s {
    char *mem;
    size_t count;
    size_t cap;
};
typedef struct stringbuilder_s *stringbuilder_t;
stringbuilder_t sb_new(size_t init_cap) {
    stringbuilder_t ret = malloc(sizeof(struct stringbuilder_s));
    if (!ret) return NULL;
    ret->mem = calloc(init_cap, sizeof(char));
    if (!ret->mem) return NULL;
    ret->cap = init_cap;
    ret->count = 0;
    return ret;
}
#define LOAD_FACTOR 2
bool sb_append(stringbuilder_t to, char c) {
    to->mem[to->count] = c;
    ++to->count;
    if (to->count == to->cap) {
        char *new_mem = realloc(to->mem, to->cap * LOAD_FACTOR);
        if (!new_mem) {
            return false;
        }
        memset(new_mem + to->cap, 0, to->cap);
        to->mem = new_mem;
        to->cap *= LOAD_FACTOR;
    }
    return true;
}
char *sb_as_string(stringbuilder_t sb) {
    return sb->mem;
}
void sb_free(stringbuilder_t sb) {
    free(sb->mem);
    free(sb);
}

I'm interested specifically in:

• Performance. This code gets called a lot. I want it to be as fast as possible.
• Memory safety. While I'm fairly sure that this doesn't leak memory (assuming it's used properly), I'm not confident, and I'm not sure how to check.
• Edge cases. It works, as far as I can tell, but that doesn't mean that it's bug-free.

Tested here.

Answer 1

Bug: Initial allocation not cleared to zero

Your initial allocation of sb->mem uses malloc instead of calloc, so its contents are uninitialized. If you then append a few characters and call sb_as_string(), you will get back a string that is not properly terminated. You should use calloc instead.

Minor bug

If your call to realloc fails, your buffer will be incorrect because it will no longer be null terminated (you just appended a character to the last spot). You should either rewrite a '\0' to the end of the buffer if realloc fails, or do the realloc before you append the character.

Argument check

When creating a string buffer, you should handle the case where init_cap is passed in as 0. You can set it to some default value in that case. Right now, an initial capacity of 0 will cause a crash down the line because your append function will append to a zero length buffer without ever reallocating.

Usability

I would much prefer an append function that took a string argument instead of a character argument. I'm not sure that I would ever need to append one character at a time.

Also, it might be nice to have a to_string type function that returns the string but also frees the stringbuilder. The way you currently have it, you can retrieve the string, but if you subsequently free the stringbuilder it will also free the string you just retrieved. That makes it difficult to use the string because its lifetime is tied to the lifetime of the stringbuilder.

Answer 2

To be more comprehensive, the line in sb_append():

memset(new_mem + to->cap, 0, to->cap);

should become:

memset(new_mem + to->cap, 0, (to->cap) * (LOAD_FACTOR - 1));

That matters when LOAD_FACTOR is set to something greater than 2.

thanks for sharing this code.

Answer 3

I don't think it's necessary to insist that the string builder itself be in dynamic storage. It's a fixed size, and would really like to be in automatic storage. Ideally, it would be re-usable, too.

That can be enabled, by adding functions like these:

typedef struct stringbuilder_s stringbuilder_s;

bool sb_init(stringbuilder_s *b, const char *s)
{
    b->count = strlen(s);
    b->cap = LOAD_FACTOR * (b->count + 1);
    b->mem = malloc(b->cap);
    if (!b->mem) {
        b->count = 0;
        b->cap = 0;
        return false;
    }
    strcpy(b->mem, s);
    return true;
}

void sb_close(stringbuilder_s *b)
{
    free(b->mem);
    b->cap = 0;
    b->count = 0;
}

We can then use like this:

#include <stdio.h>

int main(void)
{
    stringbuilder_s builder;
    if (!sb_init(&builder, "foo")) { goto fail; }
    if (!sb_append_char(&builder, '1')) { goto fail; }
    printf("Created %s\n", sb_as_string(&builder));
    sb_close(&builder);
    return 0;

 fail:
    sb_close(&builder);
    fprintf(stderr, "String creation failed");
    return 1;
}

---

Bug:

• If sb_new() fails to allocate mem, we really need to free ret before returning null.

---

Minor points:

• sizeof (char) is 1 by definition, and sizeof *ret is clearer than sizeof (struct stringbuilder_s) when allocating to assign to ret.
• It's wasteful to zero out the whole capacity, when we only need a single terminator for a string. We could defer the null termination until we sb_as_string() is called, but I think it's better to keep mem nul-terminated as we go. (The overhead shrinks once we support sb_append_string(), of course).