How can I append to a string many times?

Question

So I have a loop that generates a sting every time and I want to append this string to an existing variable.

char fullString[] = "start: ";

while(x < 200){

    char someVar[] = "test "

    //append someVar to fullString

    x++;

}

So I would like to end up with a string like this:

start: test test test test test ...

I can do it easily on any other language, just not sure how to do it in c, any ideas?

Answer 1

The costs of strcat(), malloc() and realloc() are often overlooked.

I've played a bit with this case and got some numbers:

% ./catter "Start: " "test " 1000                                                                                                             
    realloc_catter:        379
   prealloc_catter:        154
  realloc_mycatter:        152
 prealloc_mycatter:          8
% ./catter "Start: " "test " 100000  
    realloc_catter:    1453494
   prealloc_catter:     741639
  realloc_mycatter:     733160
 prealloc_mycatter:        365
% ./catter "Start: " "test " 1000000
    realloc_catter:  265374117
   prealloc_catter:  128139699
  realloc_mycatter:  127484834
 prealloc_mycatter:       3397

Here we clearly see the O(n^2) costs. A properly optimized concatenation approach costs only O(n).

The test code was:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

void measure(char *name, void (*func)(char**,char *,char*,int), char **target, char *initial, char *repeat, int times)
{
    clock_t start, finish;
    start = clock();
    func(target, initial, repeat, times);
    free(*target);
    finish = clock();
    printf("%20s: %10lld\n", name, (long long)(finish - start));
}

void realloc_catter(char **target, char *initial, char *repeat, int times)
{
    *target = malloc(strlen(initial)+1);
    strcpy(*target, initial);
    for (int i = 0; i < times; i++) {
        *target = realloc(*target, strlen(*target) + strlen(repeat) + 1);
        strcat(*target, repeat);
    }
}

void prealloc_catter(char **target, char *initial, char *repeat, int times)
{
    *target = malloc(strlen(initial) + strlen(repeat) * times + 1);
    strcpy(*target, initial);
    for (int i = 0; i < times; i++) {
        strcat(*target, repeat);
    }
}

char *mystrcat(char *target, char *repeat)
{
    for(;;) {
        *target = *repeat;
        if (!*repeat) break;
        target++;
        repeat++;
    }
    return target;
}

void realloc_mycatter(char **target, char *initial, char *repeat, int times)
{
    char *catptr = *target = malloc(strlen(initial)+1);
    strcpy(*target, initial);
    for (int i = 0; i < times; i++) {
        *target = realloc(*target, strlen(*target) + strlen(repeat) + 1);
        catptr = mystrcat(catptr, repeat);
    }
}

void prealloc_mycatter(char **target, char *initial, char *repeat, int times)
{
    char *catptr = *target = malloc(strlen(initial) + strlen(repeat) * times + 1);
    strcpy(*target, initial);
    for (int i = 0; i < times; i++) {
        catptr = mystrcat(catptr, repeat);
    }
}

int main(int argc, char **argv)
{
    if (argc < 4) exit(1);
    char *initial = argv[1];
    char *repeat = argv[2];
    int times = atoi(argv[3]);

    char *target;

    measure("realloc_catter", realloc_catter, &target, initial, repeat, times);

    measure("prealloc_catter", prealloc_catter, &target, initial, repeat, times);

    measure("realloc_mycatter", realloc_mycatter, &target, initial, repeat, times);

    measure("prealloc_mycatter", prealloc_mycatter, &target, initial, repeat, times);

    return 0;
}

The mystrcat() function returns a pointer to the last string position saving the next call to have to walk the string again. This test code is also available as a gist.

Answer 2

I wrote this answer this morning but then had a power outage. Here it is anyway to guide the questioner in his/her understanding.

It is not easy in C because you have to manage the string space yourself (which other languages do for you).

In essence, every time you want to append to the existing string, you have to calculate its current length, the length of the string to append, allocate new space to hold both, copy the existing part to the new string memory, append the new string, and free the old string.

There are various ways to speed things up, such as using realloc, as others suggest, pre-allocating larger buffers, keeping track of the current length, etc; however, the method doesn't change if you have variable length strings to append.

Answer 3

with strcat() you run the risk of getting into the Schlemiel's algorithm.

Keep a current string length and sprintf() (or snprintf()) instead:

char *result;
size_t len = 0;
while (1) {
    /* make sure result points to a large enough area! */
    len += sprintf(result + len, "%s", "test ")
    if (stuff()) break;
}

Answer 4

Repeatedly appending strings results in O(n^2) run-time if you do it iteratively. Instead, one should allocate the full amount of memory up-front, and build the string incrementally.

Here's some code that does that.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// append_extra returns a string consisting of init
// with count copies of extra appended.
// Or NULL on failure.
char *append_extra(char *init, char *extra, int count) {
    size_t len_init = strlen(init);
    size_t len_extra = strlen(extra);
    char *result = malloc(len_init + len_extra * count + 1);
    if (!result) {
       return 0;
    }
    char *p = result;
    strcpy(p, init);
    p += len_init;
    for (int i = 0; i < count; i++) {
        strcpy(p, extra);
        p += len_extra;
    }
    return result;
}

int main(void) {
    char *result = append_extra("hello", " world", 10);
    if (!result) exit(1);
    printf("'%s'\n", result);
    return 0;
}

Answer 5

You can use like this,

char *full =malloc(10);// allocating the memory
 if ( full == NULL ){ 
         printf("allocation failed\n");
         return;
 }
strcpy(full,"Start: ");
char someVar[] ="test ";
char *temp;
while(x < 200 ) {
     temp=realloc(full,(strlen(full)+1)+(strlen(someVar)+1));//reallocating for store repeatedly
     if ( temp == NULL )
              printf("allocation failed\n");
         break;
     }
     full=temp;
     strcat(full,someVar);
     x++;
}

Answer 6

As proposed by DrKoch, multiple call of realloc might have an impact on you execution time, depending on the implementation of realloc.

If you already how many time you are going to append someVar you can allocate all the required dynamic memory at once:

char *full;
char someVar[] ="test ";
int  nb_append = 200;
int  x = 0;

if ((full = malloc(sizeof (*full) * 8) == NULL)// allocating the memory
   // Handle malloc error;
strcpy(full,"Start: ");
if (realloc(full,sizeof(*full) * 8 + sizeof(someVar) * nb_append) == NULL) //reallocating for store only once
   // Handle realloc error;
while (x < nb_append ) {
     strcat(full, someVar);
     x++;
}

Answer 7

You should have a buffer large enough to hold the whole concatenated string.

Use the string function strcat() as shown below

char fullString[2000] = "start: ";

while(x<200)
{
    char someVar[] = "test "; // What ever valid string you want to append to the existing string
    strcat(fullString,someVar);
    x++;
}