8
\$\begingroup\$

So I've written up what the title says.

Obviously, I'm looking for speed, safety and ease of use. To achieve the perfect ratio I've made some functions straight away crash if the input is wrong (in debug mode only, otherwise UD). The design is inspired by the C++ counterpart.

Will be glad to hear other opinions. (It's a lot of code, so bear with me.)

dynstring.h

#ifndef DYNSTRING_H
#define DYNSTRING_H

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

typedef struct {
    char* data;
    size_t size;
} string;

extern bool string_create(string*);
extern bool string_create_n(string*, size_t);
extern bool string_create_from_raw(string*, const char*);

extern void string_destroy(string*);

extern bool string_copy(string*, string);
extern bool string_copy_from_raw(string*, const char*);

extern void string_set(string*, size_t, char);
extern char string_get(string, size_t);

extern char* string_front(string);
extern char* string_back(string);

extern char* string_to_raw(string);

extern size_t string_size(string);
extern bool   string_empty(string);

extern void string_erase(string*, size_t, size_t);

extern bool string_push_back(string*, char);
extern bool string_push_front(string*, char);

extern bool string_pop_back(string*);
extern bool string_pop_front(string*);

extern bool string_append(string*, string);
extern bool string_append_raw(string*, const char*);

extern bool string_substr(string, size_t, size_t, string*);

extern void string_swap(string*, string*);
extern int  string_compare(string, string);

extern size_t string_find(string, char);
extern size_t string_find_substr(string, const char*);

#endif

dynstring.c

#include "dynstring.h"

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

bool string_create(string* str)
{
    assert(str);
    // allocate 1 for '\0'
    str->data = malloc(sizeof(char));
    if (!str->data) {
        return false;
    }
    str->size = 0;
    str->data[0] = '\0';
    return true;
}

bool string_create_n(string* str, size_t size)
{
    assert(str);
    if (size == 0) {
        return string_create(str);
    }
    // one extra for '\0'
    str->data = malloc(sizeof(char) * size + 1);
    if (!str->data) {
        return false;
    }
    str->size = size;
    str->data[str->size] = '\0';
    return true;
}

bool string_create_from_raw(string* str, const char* from)
{
    assert(str && from);
    if (!string_create_n(str, strlen(from))) {
        return false;
    }
    memcpy(str->data, from, sizeof(char) * str->size);
    return true;
}

void string_destroy(string* str)
{
    assert(str);
    free(str->data);
}

bool string_copy(string* dest, string src)
{
    assert(dest);
    if (dest->size >= src.size) {
        memcpy(dest->data, src.data, sizeof(char) * src.size + 1);
    }
    else
    {
        char* temp = malloc(sizeof(char) * src.size + 1);
        if (!temp) {
            return false;
        }
        memcpy(temp, src.data, sizeof(char) * src.size + 1);
        free(dest->data);
        dest->data = temp;
    }
    dest->size = src.size;
    return true;
}

bool string_copy_from_raw(string* dest, const char* src)
{
    assert(dest && src);
    string str;
    if (!string_create_from_raw(&str, src)) {
        return false;
    }
    string_swap(&str, dest);
    string_destroy(&str);
    return true;
}

void string_set(string* str, size_t i, char c)
{
    assert(str && str->size > i);
    str->data[i] = c;
}

char string_get(string str, size_t i)
{
    assert(str.size > i);
    return str.data[i];
}

char* string_front(string str) {
    return str.data;
}

char* string_back(string str) {
    return str.data + str.size - 1;
}

// same as string_front
// exists only because it looks better
// to say puts(string_to_raw(str));
char* string_to_raw(string str) {
    return str.data;
}

size_t string_size(string str) {
    return str.size;
}

bool string_empty(string str) {
    return str.size;
}

// erases characters in range [i, i+n] including
void string_erase(string* str, size_t i, size_t n)
{
    assert(str && str->size > i);
    if (i + n > str->size) {
        str->size = i;
    }
    else if (n != 0)
    {
        memcpy(str->data + i, 
               str->data + i + n, 
               sizeof(char) * str->size - i + n);
        str->size -= n;
    }
    str->data[str->size] = 0;
}

bool string_push_back(string* str, char ch)
{
    assert(str);
    string temp;
    if (!string_create_n(&temp, str->size + 1)) {
        return false;
    }
    memcpy(temp.data, str->data, sizeof(char) * str->size);
    temp.data[temp.size - 1] = ch;
    string_swap(&temp, str);
    string_destroy(&temp);
    return true;
}

bool string_push_front(string* str, char ch)
{
    assert(str);
    string temp;
    if (!string_create_n(&temp, str->size + 1)) {
        return false;
    }
    memcpy(temp.data + 1, str->data, sizeof(char) * str->size);
    temp.data[0] = ch;
    string_swap(&temp, str);
    string_destroy(&temp);
    return true;
}

bool string_pop_back(string* str)
{
    assert(str && str->size != 0);
    --str->size;
    str->data[str->size] = 0;
    return true;
}

bool string_pop_front(string* str)
{
    assert(str && str->size != 0);
    string temp;
    if (!string_create_from_raw(&temp, str->data + 1)) {
        return false;
    }
    string_destroy(str);
    string_swap(&temp, str);
    return true;
}

bool string_append(string* str, string toapp)
{
    assert(str);
    string temp;
    if (!string_create_n(&temp, str->size + toapp.size)) {
        return false;
    }
    memcpy(temp.data, str->data, str->size);
    memcpy(temp.data + str->size, toapp.data, toapp.size);
    string_swap(&temp, str);
    string_destroy(&temp);
    return true;
}

bool string_append_raw(string* str, const char* toapp)
{
    assert(str && toapp);
    size_t len = strlen(toapp);
    string temp;
    if (!string_create_n(&temp, str->size + len)) {
        return false;
    }
    memcpy(temp.data, str->data, str->size);
    memcpy(temp.data + str->size, toapp, len);
    string_swap(&temp, str);
    string_destroy(&temp);
    return true;
}

// puts the substring from index i to index j into 'to'
bool string_substr(string from, size_t i, size_t j, string* to)
{
    assert(i < j && j < from.size && to);
    string temp;
    if (!string_create_n(&temp, j - i + 1)) {
        return false;
    }
    memcpy(temp.data, from.data + i, j - i + 1);
    string_swap(&temp, to);
    string_destroy(&temp);
    return true;
}

void string_swap(string* lhs, string* rhs)
{
    assert(lhs && rhs);

    char* data = lhs->data;
    lhs->data = rhs->data;
    rhs->data = data;

    size_t size = lhs->size;
    lhs->size = rhs->size;
    rhs->size = size;
}

int string_compare(string lhs, string rhs) {
    return strcmp(lhs.data, rhs.data);
}

size_t string_find(string str, char c)
{
    char* find = strchr(str.data, c);
    if (!find) {
        return (size_t)-1;
    }
    return (size_t)(find - str.data);
}

size_t string_find_substr(string str, const char* tofind)
{
    assert(tofind);
    char* find = strstr(str.data, tofind);
    if (!find) {
        return (size_t)-1;
    }
    return (size_t)(find - str.data);
}
\$\endgroup\$
8
  • 3
    \$\begingroup\$ Real C++ string will exponentially increase in size. You'll need to keep a capacity for that, or you could check for null terminator. If you want extreme optimizations, there are two paths to choose from: prepend the metadata right before the string on the heap, or use small object optimization (create a union that will be either {char* data, size_t size, size_t capacity} or char[24]). The latter also has some more optimizations, but they are much harder to implement. \$\endgroup\$ Mar 27, 2017 at 14:35
  • 1
    \$\begingroup\$ @Incomputable Yes, thanks for the comment. I had considered both optimizations, but thought it wouldn't be too fun to upload 500 lines up here... People wouldn't bother I guess. \$\endgroup\$
    – DeiDei
    Mar 27, 2017 at 14:38
  • 3
    \$\begingroup\$ One immediately obvious problem is that your identifiers all begin with str. All identifiers beginning with str are reserved for future Standard Library extension. \$\endgroup\$ Mar 27, 2017 at 15:17
  • 1
    \$\begingroup\$ @Toby Do you have a reference at hand? \$\endgroup\$ Mar 27, 2017 at 15:35
  • 2
    \$\begingroup\$ §7.31.12 of the C11 standard if anyone wants to look. This also means "is" followed by a lowercase is reserved, which is absurd... \$\endgroup\$
    – DeiDei
    Mar 27, 2017 at 16:03

2 Answers 2

2
\$\begingroup\$

Improvements

Initializing functions (string_create*)

I think it's a common practice that initializing functions return whole structure element. For example, your implementation

extern bool string_create_n(string* str, size_t size);

should look like this

extern string * string_create_n(size_t size);

It's also applicable to free/destroy function - this function should destroy whole object (not just data).

Try realloc before malloc

Let's say you calling string_push_back function, so it basically means that you would like to add one more character to the data. Instead of using malloc in a first place I would suggest to try to extend current array by one sizeof(char) using realloc. I also introduced one more variable to the structure - size_t alloc_size keeps actual size of allocated memory. It allows to avoid frequent reallocations events (there is invariant that alloc_size >= size + 1).

Be careful with Memory leaks

Your code contains a lot of problems with memory management. For example

bool string_create(string* str)
{
    assert(str);
    // allocate 1 for '\0'
    str->data = malloc(sizeof(char));
    if (!str->data) {
        return false;
    }
    str->size = 0;
    str->data[0] = '\0';
    return true;
}

Imagine that there is an allocated array in str->data. By making malloc before freeing, you losing link to the first array.


Suggestions

  1. I prefer to use const modifier as much as possible. There are numerous benefits to follow this advice.
  2. Thanks to @toby-speight' comment I get to know that identifier should not start from reserved word like str.

TODO List

  1. You should remove assert and write meaningful error messages. Instead of returning bool value, use int values which should be macro-defined.
  2. dyn_string_push_front and dyn_string_pop_front are implemented not-optimally.
  3. Structure dyn_string contains size of the data, so you can skip '\0' ending. It's good idea because, first, you will save memory and, second, you will avoid actions related to '\0' maintenance.

My version

dynstring.c

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

dyn_string* dyn_string_alloc(const size_t n)
{
    dyn_string *p;
    assert(n);
    p = (dyn_string *) malloc (sizeof (dyn_string));
    assert(p);
    p->data = (char *) malloc (n * sizeof (char));
    assert(p->data);
    p->size = 0;
    p->data[0] = '\0';
    p->alloc_size = n;
    return p;
}

void dyn_string_realloc(dyn_string * p, const size_t n)
{
    char *c;
    assert(p);
    if (n > p->alloc_size) {
        c = (char *) realloc(p->data, sizeof(char) * n);
        if(c == 0) {
            c = (char *) malloc(sizeof(char) * n);
            assert(c);
            memcpy(c, p->data, sizeof(char) * (p->size + 1));
            free(p->data);
            p->data = c;
        } 
        p->alloc_size = n;
    }
}

dyn_string* dyn_string_alloc_raw(const char* src)
{
    size_t n = strlen(src) + 1;
    dyn_string *p = dyn_string_alloc(n);
    assert(p);
    memcpy(p->data, src, sizeof(char) * n);
    p->size = n - 1;
    return p;
}

dyn_string* dyn_string_alloc_cpy(const dyn_string * src)
{
    assert(src);
    size_t n = src->size + 1;
    dyn_string *p = dyn_string_alloc(n);
    memcpy(p->data, src->data, sizeof(char) * n);
    p->size = src->size;
    p->alloc_size = n;
    return p;
}

void dyn_string_free(dyn_string * p)
{
    assert(p);
    free(p->data);
    free(p);
}

void dyn_string_cpy(dyn_string * dst, const dyn_string * src)
{
    assert(dst && src);
    size_t n = src->size + 1;
    if (dst->alloc_size < n) {
        dyn_string_realloc(dst, n);
    }
    memcpy(dst->data, src->data, sizeof(char) * n);
    dst->size = src->size;
}

void dyn_string_cpy_raw(dyn_string* dst, const char* src)
{
    assert(dst && src);
    size_t n = strlen(src) + 1;
    if (dst->alloc_size < n) {
        dyn_string_realloc(dst, n);
    }
    memcpy(dst->data, src, sizeof(char) * n);
    dst->size = n - 1;
}

void dyn_string_set(dyn_string* p, const size_t i, const char c)
{
    assert(p && p->size > i);
    p->data[i] = c;
}

char dyn_string_get(const dyn_string* p, const size_t i)
{
    assert(p->size > i);
    return p->data[i];
}

char* dyn_string_front(const dyn_string * p) {
    return p->data;
}

char* dyn_string_back(const dyn_string * p) {
    return p->data + p->size;
}

size_t dyn_string_size(const dyn_string * p) {
    return p->size;
}

// erases characters iddn range [i, i+n] including
void dyn_string_erase(dyn_string* p, const size_t i, const size_t n)
{
    assert(p && p->size > i);
    if (i + n + 1 >= p->size) {
        p->size = i;
    } else {
        p->size -= (n + 1);
        memcpy(p->data + i,
               p->data + i + n + 1,
               sizeof(char) * (p->size - i));
    } 
    p->data[p->size] = '\0';
}

void dyn_string_push_back(dyn_string* p, const char c)
{
    assert(p);
    if (p->size + 1 <= p->alloc_size) {
        dyn_string_realloc(p, p->alloc_size<<1);
    }
    p->data[p->size++] = c;
    p->data[p->size] = '\0';
}

void dyn_string_push_front(dyn_string* p, const char c)
{
    assert(p);
    if (p->size + 1 <= p->alloc_size) {
        dyn_string_realloc(p, p->alloc_size<<1);
    }
    p->size++;
    memcpy(p->data + 1, p->data, sizeof(char) * p->size); //Not optimal
    p->data[0] = c;
}

char dyn_string_pop_back(dyn_string* p)
{
    assert(p && p->size != 0); 
    p->size--;
    char c = p->data[p->size];
    p->data[p->size] = '\0';
    return c;
}

char dyn_string_pop_front(dyn_string* p)
{
    assert(p && p->size != 0);
    char c = p->data[0];
    memcpy(p->data, p->data + 1, sizeof(char) * p->size--); //Not optimal
    return c;
}

void dyn_string_append(dyn_string* dst, const dyn_string* src)
{
    assert(src && dst);
    size_t n = dst->size + src->size + 1;
    if (dst->alloc_size < n) {
        dyn_string_realloc(dst, n);
    }
    memcpy(dst->data + dst->size, src->data, sizeof(char) * (src->size + 1));
    dst->size = n - 1;
}

void dyn_string_append_raw(dyn_string* dst, const char* src)
{
    assert(src && dst);
    size_t l = strlen(src) + 1;
    size_t n = l + dst->size;
    if (dst->alloc_size < n) {
        dyn_string_realloc(dst, n);           
    }   
    memcpy(dst->data + dst->size, src, sizeof(char) * l);
    dst->size = n - 1;
}

// copy substr iddn range [i, i+n] including
void dyn_string_substr(dyn_string * dst, const dyn_string * src, const size_t i, const size_t n)
{
    assert(dst && src && i + n < src->size);
    size_t n0 = n + 1;
    if (dst->alloc_size < n0) {
        dyn_string_realloc(dst, n0);
    }
    memcpy(dst->data, src->data + i, sizeof(char) * n0);
    dst->size = n;
}

void dyn_string_swap(dyn_string* p0, dyn_string* p1)
{
    assert(p0 && p1);
    dyn_string * p = p0;
    p0 = p1;
    p1 = p;
}

int dyn_string_compare(const dyn_string* p0, const dyn_string* p1) 
{
    assert(p0 && p1);
    return (p0->size != p1->size) ? (p0->size - p1->size) : strcmp(p0->data, p1->data);
}

size_t dyn_string_find(const dyn_string* src, const char c)
{
    assert(src);
    char *p;
    return (p = strchr(src->data, c)) ? (p - src->data) : (size_t)-1;
}

size_t dyn_string_find_substr(const dyn_string* big, const char* small)
{
    assert(big && small);
    char *p;
    return (p = strstr(big->data, small)) ? (p-big->data) : (size_t)-1;
}

dynstring.h

#ifndef DYNSTRING_H
#define DYNSTRING_H

#include <stddef.h>

typedef struct {
    char* data;
    size_t size;
    size_t alloc_size;
} dyn_string;

extern dyn_string* dyn_string_alloc(const size_t);
extern void dyn_string_realloc(dyn_string*, const size_t);
extern dyn_string* dyn_string_alloc_raw(const char*);
extern dyn_string* dyn_string_alloc_cpy(const dyn_string*);

extern void dyn_string_free(dyn_string*);

extern void dyn_string_cpy(dyn_string*, const dyn_string*);
extern void dyn_string_cpy_raw(dyn_string*, const char*);

extern void dyn_string_set(dyn_string*, const size_t, const char);
extern char dyn_string_get(const dyn_string*, const size_t);

extern char* dyn_string_front(const dyn_string*);
extern char* dyn_string_back(const dyn_string*);

extern size_t dyn_string_size(const dyn_string*);
extern void dyn_string_erase(dyn_string*, const size_t, const size_t);

extern void dyn_string_push_back(dyn_string*, const char);
extern void dyn_string_push_front(dyn_string*, const char);

extern char dyn_string_pop_back(dyn_string*);
extern char dyn_string_pop_front(dyn_string*);

extern void dyn_string_append(dyn_string*, const dyn_string*);
extern void dyn_string_append_raw(dyn_string*, const char*);

extern void dyn_string_substr(dyn_string*, const dyn_string *, const size_t, const size_t);

extern void dyn_string_swap(dyn_string*, dyn_string*);
extern int  dyn_string_compare(const dyn_string*, const dyn_string*);

extern size_t dyn_string_find(const dyn_string*, const char);
extern size_t dyn_string_find_substr(const dyn_string*, const char*);

#endif
\$\endgroup\$
8
  • 1
    \$\begingroup\$ assert.h doesn't belong into dynstring.h. \$\endgroup\$ Apr 18, 2017 at 6:18
  • \$\begingroup\$ @RolandIllig Yes, I agree. I changed files \$\endgroup\$
    – pgs
    Apr 18, 2017 at 8:14
  • 1
    \$\begingroup\$ If you omit the '\0', how will you use the string? Pretty much all string-related functions like printf etc. need the '\0'. Also note that you should use memmove for overlapping data, which does exactly the same thing as OP's implementation – it uses a temporary buffer. \$\endgroup\$
    – kyrill
    Apr 18, 2017 at 9:34
  • 1
    \$\begingroup\$ OK, what if I wanted to use puts instead? Or what if I wanted to use this dynamic string as the formatting string for printf? \$\endgroup\$
    – kyrill
    Apr 18, 2017 at 9:44
  • 1
    \$\begingroup\$ size can be useful if you need it often, especially when the strings are long since it's \$O(n)\$ time to calculate the length. \$\endgroup\$
    – kyrill
    Apr 18, 2017 at 10:07
1
\$\begingroup\$

This module is intended to be written once, never changed again, right? Also, you strive for efficiency? Then put everything in the header. As currently used extern does nothing. Replace it with inline and put the definitions there. You can still move the declarations tothe top of the file, for client convenience.

Secondly, one more vote for small object optimization. The heap is insanely expensive (could reach 1000 cycles for a single allocation). If portability is not important, usa alloca().

Drop the bool returns. In my experience, no one checks error codes. And most errors you report can almost never happen. malloc fails? There is something very wrong with the system. Blow an assert or exit(1). What is a caller supposed to do with a failed malloc? Try to malloc again?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ "Blow an assert or exit(1)". Yeah why not system('poweroff')... \$\endgroup\$
    – kyrill
    Apr 18, 2017 at 19:29
  • \$\begingroup\$ if your system has 0% physical memory, a power off could be a sensible approach. \$\endgroup\$
    – Vorac
    Apr 19, 2017 at 6:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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