Dynamic Strings in C

Question

I wrote this code for dynamic strings and would like to know what mistakes I've made.

It's just a struct that gets filled on the first call to ds_allocate and freed on the first call to ds_free. It uses memcpy for concatenation and supports a few basic operations.

Here's the header

#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

//Size and expansion
#define MULTIPLIER 1.00 //add 100% every time
#define FIXED_STEP 0 //overrides multiplier
#define STARTING_SIZE 24

//Can set other memory functions
#define allocate malloc
#define deallocate free
#define reallocate realloc

//Main structure
typedef struct {
    char *content;
    char *position;
    char *end; //1 past the end
} Dynamic_String;

And the code so far:

static inline size_t max(size_t x, size_t y)
{
    return (x > y) ? x : y;
}
static inline size_t min(size_t x, size_t y)
{
    return (x < y) ? x : y;
}

//Allocate initial space and set the structure members, return pointer to
//newly allocated memory. Available for use is custom_size - 1. It doesn't
//allocate space for the structure itself
char *ds_allocate(Dynamic_String *ds, size_t custom_size)
{
    //What's the point in having only the '\0' character?
    assert(custom_size != 1);

    size_t size = (custom_size > 0) ? custom_size : STARTING_SIZE;

    char *start = allocate(size);
    if(start == NULL){
        return NULL;
    }

    ds->content = ds->position = start;
    ds->end = start + size;
    *start = '\0';

    return start;
}

void ds_free(Dynamic_String *ds)
{
    deallocate(ds->content);
}

//Keep memory allocated, clear contents
void ds_clear(Dynamic_String *ds)
{
    ds->position = ds->content;
    *ds->position = '\0';
}

//If the content is manipulated without using these functions, but the memory
//allocated is the same and there's a '\0', it corrects the string position.
//Otherwise it writes a new '\0' at the end and returns NULL. The string
//should be usable after calling this function.
char *ds_fix(Dynamic_String *broken)
{
    assert(broken->content != NULL);

    broken->position = memchr(broken->content, '\0', ds_capacity(broken));

    if(broken->position == NULL){
        broken->position = broken->end - 1;
        *broken->position = '\0';
        return NULL;
    }
    return broken->position;
}

//Equivalent of strlen
size_t ds_length(const Dynamic_String *ds)
{
    return ds->position - ds->content;
}

//Total memory allocated
size_t ds_capacity(const Dynamic_String *ds)
{
    return ds->end - ds->content;
}

//Space available, accounts for '\0'
size_t ds_space(const Dynamic_String *ds)
{
    return ds->end - ds->position - 1;
}

bool ds_is_empty(const Dynamic_String *ds)
{
    return ds->position == ds->content;
}

bool ds_is_full(const Dynamic_String *ds)
{
    return ds_space(ds) == 0;
}

//Resize memory and update the structure
char *ds_resize(Dynamic_String *ds, size_t new_size)
{
    //Can't free the string through this function and what's the point of
    //having only space for the '\0' terminator
    assert(new_size > 0 && new_size != 1);

    //Location might change
    size_t position_offset = ds_length(ds);

    char *temp = reallocate(ds->content, new_size);
    if(temp == NULL){
        return NULL;
    }

    ds->content = temp;
    ds->end = temp + new_size;

    //Position still in range?
    if(position_offset < new_size){
        ds->position = temp + position_offset;
    }
    else {
        ds->position = temp + new_size - 1;
        *ds->position = '\0';   
    }

    return temp;
}

//Allocate more bytes
char *ds_reserve(Dynamic_String *ds, size_t amount)
{
    assert(amount > 0); 
    return ds_resize(ds, ds_capacity(ds) + amount);
}

//Deallocate part of memory
char *ds_shrink(Dynamic_String *ds, size_t amount)
{
    assert(amount < ds_capacity(ds));
    return ds_resize(ds, ds_capacity(ds) - amount); 
}

//Reduce allocated storage so it's just enough for the current content
char *ds_shrink_to_fit(Dynamic_String *ds)
{
    //Shouldn't be used to free the string
    assert(ds_length(ds) > 0);
    return ds_shrink(ds, ds_space(ds)); 
}

//Expand according to multiplier or fixed step
static char *expand(Dynamic_String *ds)
{
    assert(FIXED_STEP > 0 || MULTIPLIER > 0);   
    if(FIXED_STEP > 0){
        return ds_reserve(ds, FIXED_STEP);
    }   

    return ds_reserve(ds, ds_capacity(ds) * MULTIPLIER);
}

//Expand by at least a minimum value
static char *expand_by_at_least(Dynamic_String *ds, size_t minimum)
{
    assert(minimum > 0);
    assert(FIXED_STEP > 0 || MULTIPLIER > 0);

    size_t regular_size;
    if(FIXED_STEP > 0){
         regular_size = FIXED_STEP;
    }
    else {
        regular_size = ds_capacity(ds) * MULTIPLIER;
    }

    return ds_reserve(ds, max(regular_size, minimum));
}

//Push character to the end of string, return pointer to it
char *ds_push_back(Dynamic_String *ds, int c)
{
    if(ds_is_full(ds) && expand(ds) == NULL){
        return NULL;
    }

    *ds->position++ = c;
    *ds->position = '\0';

    return ds->position - 1;        
}

//Append one dynamic string to another, return content position
char *ds_append(Dynamic_String *destination, const Dynamic_String *source)
{
    size_t destination_space = ds_space(destination);
    size_t source_length = ds_length(source);

    if(source_length > destination_space 
        && expand_by_at_least(destination, source_length - destination_space)
                    == NULL){
        return NULL;
    }

    char *insertion_point = destination->position;
    destination->position += source_length;
    *destination->position = '\0';

    return memcpy(insertion_point, source->content, source_length);
}

//Append at most n characters from source to destination
char *ds_append_n(Dynamic_String *destination, const Dynamic_String *source, size_t max)
{
    //Append whole string?
    if(max > ds_length(source)){
        return ds_append(destination, source);
    }

    size_t space = ds_space(destination);
    if(max > space && expand_by_at_least(destination, max - space) == NULL){
        return NULL;
    }

    char *insertion_point = destination->position;
    destination->position += max;
    *destination->position = '\0';

    return memcpy(insertion_point, source->content, max);
}

//Compare two dynamic strings and return  0 if equal, positive if first
//differing character is greater on str1 or negative if smaller
int ds_compare(const Dynamic_String *str1, const Dynamic_String *str2)
{
    size_t length = min(ds_length(str1), ds_length(str2));
    return memcmp(str1->content, str2->content, length + 1);
}

//Compare up to n characters
int ds_compare_n(   const Dynamic_String *str1, 
                    const Dynamic_String *str2, 
                    size_t max                  )

{
    assert(max > 0);

    size_t length = min(ds_length(str1), ds_length(str2));
    return memcmp(str1->content, str2->content, min(length + 1, max));
}


///////////////////////
////// Functions to work with dynamic and regular strings

//Takes an already allocated regular string and put it into a container. Making
//it a normal dynamic string. Container must not hold an allocated string or
//there will be memory leaks. 
void ds_from_cstring(Dynamic_String *ds, char *c_string)
{
    ds->content = c_string;
    ds->position = strchr(c_string, '\0');
    ds->end = ds->position + 1;
}

//Return an allocated copy of Dynamic_String content
char *ds_content_copy(const Dynamic_String *ds)
{
    assert(ds_length(ds) > 0);

    size_t length = ds_length(ds);

    char *temp = malloc(length + 1);
    if(temp == NULL){
        return NULL;
    }

    return memcpy(temp, ds->content, length + 1);
}

//Append regular C string to Dynamic_String
char *ds_append_cstring(Dynamic_String *destination, const char *c_string)
{
    //It could trigger expansion without any need
    assert(*c_string != '\0');

    char *insertion_point = destination->position;

    for(;;){
        //Avoid checking the available space all the time
        //Benchmark
        //16 cases:  28,700,681
        //8  cases:  29,747,016
        //4  cases:  37,400,868
        switch(ds_space(destination)){
            case 0:
                if(expand(destination) == NULL){
                    goto handle_error;
                }
                break;

            default:

            case 8:
                if(*c_string == '\0'){
                    goto done;
                }
                *destination->position++ = *c_string++;

            case 7:
                if(*c_string == '\0'){
                    goto done;
                }
                *destination->position++ = *c_string++;

            case 6:
                if(*c_string == '\0'){
                    goto done;
                }
                *destination->position++ = *c_string++;

            case 5:
                if(*c_string == '\0'){
                    goto done;
                }
                *destination->position++ = *c_string++;

            case 4:
                if(*c_string == '\0'){
                    goto done;
                }
                *destination->position++ = *c_string++;

            case 3:
                if(*c_string == '\0'){
                    goto done;
                }
                *destination->position++ = *c_string++;

            case 2:
                if(*c_string == '\0'){
                    goto done;
                }
                *destination->position++ = *c_string++;

            case 1:
                if(*c_string == '\0'){
                    goto done;
                }
                *destination->position++ = *c_string++;
        }
    }

    done:
    *destination->position = '\0';
    return insertion_point;

    //Cancel changes if there's an error
    handle_error:
    destination->position = insertion_point;
    *destination->position = '\0';
    return NULL;
}

//Appending a C string of known size is a lot faster
char *ds_append_cstring_by_length(  Dynamic_String *destination,
                                    char *c_string,
                                    size_t length                   )
{
    assert(length > 0);
    assert(c_string[length - 1] != '\0');

    size_t destination_space = ds_space(destination);
    if(destination_space < length
        && expand_by_at_least(destination, length - destination_space) 
            == NULL){
        return NULL;
    }   

    char *insertion_point = destination->position;
    destination->position += length;
    *destination->position = '\0';

    return memcpy(insertion_point, c_string, length);   
}

Answer 1

The code is generally nice, so my comments are really just picking up crumbs.

I'm not comfortable with your use of asserts to catch errors that could legitimately occur at runtime. I consider asserts to be for asserting logical impossibilities, not for catching runtime errors.

Function expand is equivalent to expand_by_at_least(ds, 1)

Long parameter names destination and source could be abbreviated dst and src with no loss.

Is giving the user a read-write (ie. non-const) pointer to the private string a good idea (functions returning char*)? And is the position returned consistent (think not - sometimes the new end of string sometimes the old).

In ds_compare (ds_compare_n), why not just return the strcmp (strncmp) of the two strings?

I don't like the loop in ds_append_cstring. A simple loop copying and checking for destination full, expanding as necessary would be simpler.

Edit: Do you mind giving me an example of what assert errors could legitimately occur at runtime?

In the context of your code, I have no problem with asserting non-null pointers, but asserting for non-zero string length seems unsafe. There are many times when a string could have a zero length but the assert says that users of your code must guarantee that it is always a design fault in their code for a nul string to pass into your functions. Not only is this unreasonable, it is is unnecessary as you can easily handle such cases. BTW don't assume that mallocing 0 is equivalent to free (it isn't) - handle a zero request by allocating at least 1 byte.

As an example of testing a logical impossibilty consider some code that does:

expected length = calculate expected length of string
allocate memory
real length = create string in memory
assert(real length = expected length)

The assert tells you whether your algorithms are consistent/correct

Answer 2

Overall

Your header doesn't include any function declarations so I'm not sure what your "public interface" will be but only few of your functions are static so I have to assume you intend to make all others available in which case I have to say I don't like the interface into your structure.

From the looks of it your Dynamic_String should only be manipulated through the appropriate ds_ functions yet your return the pointer to the internal storage from various functions which has the potential for the programmer screwing it up easily.

So consider carefully defining the interface into your structure and how you intend it to be used. Most of you functions should either return Dynamic_String * or an int result indicating whether or not the operation was successfully executed. When dealing with memory allocation you should always check the result.

I'd probably even go as far as making Dynamic_String opaque. Suggested interface in your header file:

typedef struct Dynamic_String Dynamic_String;

Dynamic_String* ds_allocate(size_t initial_size);
int ds_resize(Dynamic_String* ds, size_t new_size);
int ds_reserve(Dynamic_String* ds, size_t amount);
int ds_shrink(Dynamic_String* ds, size_t amount);
void ds_free(Dynamic_String* ds);

int ds_compare(const Dynamic_String* first, const Dynamic_String* second);
int ds_compare_cstr(const Dynamic_String* first, const char* second);

int ds_copy(Dynamic_String* destination, const Dynamic_String* source);
int ds_copy_cstr(Dynamic_String* destination, const char *src);

Dynamic_String* ds_duplicate(const Dynamic_String* ds);
Dynamic_String* ds_from_cstr(const char *str);

int ds_append(Dynamic_String* destination, const Dynamic_String* source);
int ds_append_cstr(Dynamic_String* destination, const char* source);

... // etc. other useful manipulation functions 

const char* ds_getcontent(Dynamic_String* ds);
char* ds_getcontent_unsafe(Dynamic_String* ds); // all bets are of

... // query function like capacity, current size, is_empty/full etc.

Technical Details

1. ds_allocate does not check if there is already memory allocated and will simply leak if you pass in a structure which already has storage allocated. It think ds_allocate should simply allocate the structure and return it. Otherwise the programmer has to allocate the Dynamic_String structure and then call this init function which seems redundant. As user I'd prefer something along these lines:

   Dynamic_String* ds_allocate(size_t initial_size)
   {
       Dynamic_String *result = malloc(sizeof(Dynamic_string));
       if (result == NULL)
       {
           return NULL;
       }
       ...
   }
   

   Basically return NULL if any of the memory allocations fail or initial_size < 1. Provide a ds_allocate_default() if you want to give the programmer an option to just allocate an object with default size (I personally don't like these implicit "pass 0 or negative to obtain a default size allocation" implementations but YMMV).

2. Technically the result of a pointer subtraction is ptrdiff_t and not size_t. The former is signed while the latter is unsigned. You should probably store the result of the subtraction in a local variable of type ptrdiff_t and check that it's not negative before returning it as size_t. If it's negative you apparently have hit a bug in the implementation.

3. ds_append_cstring can be greatly simplified by using memcpy rather than copying each byte individually. It will also be much faster.

Answer 3

Others added many things, just some small 0 stuff follows.

1. assert(max > 0); in ds_compare_n() not needed.
   memcmp(,,0) is well defined: returns zero. C11dr §7.24.1 2.

2. In ds_append_cstring(), rather than assert(*c_string != '\0'), simply return destination; when *c_string == '\0'.

3. In ds_content_copy(), the same. The need to insure ds_length(ds) > 0) is not needed and it takes away from your fine code's range.