10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Do you want advice about style coding? You use some bad practice in C (I don't speak for everyone, it's just my opinion). \$\endgroup\$ – Stargateur Feb 22 '17 at 13:16
  • \$\begingroup\$ @Star Sure. I don't see why not. \$\endgroup\$ – Nic Hartley Feb 22 '17 at 13:19
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ calloc and memset are used so that the memory stored is always a valid, null-terminated C string. Also, I think you meant malloc(sizeof(*ret)), because otherwise it's not valid (AFAIK at least). Aside from that, nice answer! I've already gotten told off for typedefing the pointer and fixed that, but I forgot to update the code here; thanks for also providing a reference for why. WRT "zero sized string" -- what happens when you try to append to it? Allowing a capacity of zero doesn't make sense, and I was using NULL to indicate errors. I like your suggestion of default values, though. \$\endgroup\$ – Nic Hartley Feb 22 '17 at 14:59
  • \$\begingroup\$ "calloc and memset are used so that the memory stored is always a valid", this is clearly not performing you should use an other method like append the nil terminate when you give the buffer to the user because affect all the string to zero is not effective. Plus, that mean you have a undefined behavior if the user fill the exact size of the string you will give an invalid c-string with no nil terminate byte. \$\endgroup\$ – Stargateur Feb 22 '17 at 15:04
  • \$\begingroup\$ I agree about zero size string, that don't make sense, this is why the user is not suppose to send it. Trust the user, you have two option: 1. Tell to the user that use 0 size buffer is undefined behavior. 2. Use a default value. \$\endgroup\$ – Stargateur Feb 22 '17 at 15:09
  • \$\begingroup\$ Actually, calloc and memset have been performing just fine. The user has no way to add an entire string, and adding each character until you got right up to the capacity would... increase the capacity, fill the rest with zeroes, and it'd still be a valid, null-terminated C string. I've tested this. It works as it is. I'm looking for ways to make it better, not fix nonexistent bugs. I did just code a version that manually sets the one after the final character to \0, and (with slightly modified bounds checking) it is cleaner, so I'm using that. \$\endgroup\$ – Nic Hartley Feb 22 '17 at 15:46
  • \$\begingroup\$ Alright, I just implemented most of this (Except for the "rename to String" and the ones that "stop using PIMPL" made obsolete). Expect v3: There Was No Breakin' 3 soon. \$\endgroup\$ – Nic Hartley Feb 22 '17 at 17:53
5
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ WRT the fact that it only works if LOAD_FACTOR == 2 -- yep, that was addressed in the other answer. I actually realized while refactoring to produce the new version that's going up once I'm done with classes for the day that I never use sb_as_string except in debug-related functions that can now just access the memory directly. For the second point, though, my logic for that was non-existent, and I feel dumb for forgetting that realloc exists when I used it in that same thing. \$\endgroup\$ – Nic Hartley Feb 22 '17 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.