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);
}