StringBuilder in C v2: Not a charged dance

Question

A follow-up on this. To quote by copy/paste:

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

It's the same as last time.

#ifndef CONCATEN_STRINGBUILDER_H
#define CONCATEN_STRINGBUILDER_H
#include <stddef.h>
#include <stdbool.h>

struct StringBuilder;
typedef struct StringBuilder *StringBuilder;
StringBuilder sb_new(size_t);
bool sb_append(StringBuilder, char);
char *sb_as_string(StringBuilder);
char *sb_free_copy(StringBuilder);
size_t sb_size(StringBuilder);
void sb_free(StringBuilder);

#endif //CONCATEN_STRINGBUILDER_H

stringbuilder.c

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

struct StringBuilder {
    char *mem;
    size_t count;
    size_t cap;
};
StringBuilder sb_new(size_t init_cap) {
    if (init_cap == 0) {
        return NULL;
    }
    StringBuilder ret = malloc(sizeof(struct StringBuilder));
    if (!ret) return NULL;
    ret->mem = calloc(init_cap, sizeof(char));
    if (!ret->mem) {
        free(ret);
        return NULL;
    }
    ret->cap = init_cap;
    ret->count = 0;
    return ret;
}
#define LOAD_FACTOR 2
bool sb_append(StringBuilder to, char c) {
    if (to->count + 1 == 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;
    }
    ++to->count;
    to->mem[to->count - 1] = c;
    return true;
}
char *sb_as_string(StringBuilder sb) {
    return sb->mem;
}
char *sb_free_copy(StringBuilder sb) {
    char *ret = malloc((sb->count + 1) * sizeof(char));
    if (!ret) {
        return NULL;
    }
    strcpy(ret, sb->mem);
    ret[sb->count] = 0;
    sb_free(sb);
    return ret;
}
size_t sb_size(StringBuilder sb) {
    return sb->count;
}
void sb_free(StringBuilder sb) {
    if (sb) {
        if (sb->mem) free(sb->mem);
        free(sb);
    }
}

This time around, I'm concerned most about... exactly the same things:

• 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.

Also,

• Portability. Will this code be compileable on any (C11-conforming and/or major) compiler? I want the code that uses this to be as simple to deploy on as many platforms as possible.

Note that I specifically am not asking for advice on functions that would be nice to have. I'm only spending the time to implementing things I'm going to use; this isn't part of a general-purpose utility library, so I really don't care about supporting all the features when I use a tiny fraction of them.

Answer 1

The main reason why C don't have a system like that is because that produce some overhead. But I suppose you know this and want the less overhead possible and this system.

The two following lines are not C idiomatic:

struct StringBuilder;
typedef struct StringBuilder *StringBuilder;

Of course, they are two side about this, I will give you my vision. You should not hide the implementation of structure in C. Why? Because C is design to trust the user, if your user want to "play" with his data, you can't prevent it. C allow user to hack easily and this could improve the use of your library. For example, if your library don't have a code functionality the user could code it.

The second problem is that you hide the pointer in the typedef. You should not hide pointer, this made the code hard to read. And the user could think that this is not a pointer and try to write StringBuilder *foo;. A answer about this is available on stackoverflow.

For the following, I will assume that the user know that you hide the pointer and I will use explicit struct StringBuilder in the code.

Next I will talk about your function sb_new(), first I think you should not allocate the structure StringBuilder, this made a lot of overhead. You should separate your function into two sb_new() and sb_init(), one if the user want allocate the structure and one if the user take care of it.

Plus, you use calloc(), this add a lot of useless overhead. You should use malloc(). If the user want to affect the string by zero you should implement an other function for it, like sb_unused_zero().

And, if the user want a zero size string you send NULL, I don't see the point. Maybe you should use this value for tell to the function to use a default value like 42.

A detail about your call of malloc(), you could write struct StringBuilder *ret = malloc(sizeof *ret);, this is more readable and you can read this answer about it. You don't need to use sizeof char because by definition the is equal to 1.

Example:

struct StringBuilder *sb_new(size_t init_cap) {
    struct StringBuilder *sb = malloc(sizeof *sb);
    if (!sb) return NULL;
    if (!sb_init(sb, init_cap)) {
        free(sb);
        return NULL;
    }
    return sb;
}

bool sb_init(struct StringBuilder *sb, size_t init_cap) {
    init_cap = init_cap == 0 ? 42 : init_cap;
    sb->mem = malloc(init_cap);
    if (!sb->mem) return false;
    sb->count = 0;
    sb->cap = init_cap;
    return true;
}

void sb_unused(struct StringBuilder *sb, char c) {
    memset(sb->mem + to->count, c, sb->cap - sb->count);
}

This allow the user to do the following:

struct foo {
    struct StringBuilder sb;
};

int main(void) {
    struct foo foo;
    sb_init(&foo.sb, 0);
}

Let talks about sb_append(), you don't check the potential overflow when you multiply by your LOAD_FACTOR, so you have an undefined behavior.

In this function, you affect new allocate byte to zero, this is again a big overhead that is useless in most of use cast. Again, the user should use the sb_unused() function that affect unused byte in your string. Plus, you suppose that your LOAD_FACTOR is equal to 2 in your use of memset().

bool sb_append(StringBuilder sb, char c) {
    if (sb->count + 1 == sb->cap) {
        if (SIZE_MAX / LOAD_FACTOR < sb->cap) return false; // this could be improve
        size_t new_cap = sb->cap * LOAD_FACTOR;
        char *new_mem = realloc(sb->mem, new_cap);
        if (!new_mem) return false;
        sb->mem = new_mem;
        sb->cap = new_cap;
    }
    sb->mem[to->count++] = c;
    return true;
}

Your next function sb_as_string() suppose that mem is already a valid c-string, maybe you should verify that your string contain a nil terminate byte.

I almost finish, the function sb_free_copy() has a strange name, maybe rename it to something like sb_into_string(). And your implementation is strange you add yourself the nil terminate byte contrary to the function sb_as_string(), more strcpy() already do it. Whatever, you should use memcpy() because you already know the good size to copy this would be faster.

Just a detail in sb_free() you verify that sb->mem is not NULL but free() handle this, so this is useless and add overhead.

Finally, maybe your structure should be rename String because I think the user could use it to keep dynamic string and not to transform it into standard c-string?

The last thing is about your use about bool, this limit the detail about the error. Maybe you could replace it by an enum of just an int that will give you more flexibility about error report.

Answer 2

Only works if LOAD_FACTOR is exactly 2

You have something called LOAD_FACTOR which is currently defined to 2 but presumably could change to something else in the future. However, this line is written to only handle a factor of 2 increase:

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

You should do something like this instead:

    size_t old_cap = to->cap;
    to->cap *= LOAD_FACTOR;
    memset(new_mem + old_cap, 0, to->cap - old_cap);

sb_free_copy() makes unnecessary copy

I'm not sure why sb_free_copy() makes a copy of the string and then frees the original. Why not just return the original?

char *sb_free_copy(StringBuilder sb) {
    char *ret = sb->mem;
    sb->mem = NULL;
    sb_free(sb);
    return ret;
}

If the reason is so that you want to use a perfect sized memory allocation for the return string instead of returning the current oversized allocation, then you could call realloc() before returning it:

char *sb_free_copy(StringBuilder sb) {
    char  *ret = realloc(sb->mem, sb->count + 1);
    if (ret == NULL)
        ret = sb->mem;
    sb->mem = NULL;
    sb_free(sb);
    return ret;
}

Still concerned about sb_as_string()

I'm not sure what your use case is for sb_as_string(). Suppose you call this function and get a string back. Is the idea that you can keep using the same stringbuffer to do more work? If so, you should know that as soon as you call sb_append() on that stringbuffer, it will invalidate the previously returned string because sb_append() could reallocate your buffer.

To me, the only safe way of getting the string out of the stringbuffer would be to use sb_free_copy() and not sb_as_string().

Minor stylistic change

This code:

++to->count;
to->mem[to->count - 1] = c;

could be rewritten as this:

to->mem[to->count++] = c;