Allocating memory for recursive strcat() function in C

Question

I'm trying to build a context-free grammar symulator, using the tip from other question but I have a problem allocating enough memory.

The basic code :

char * print_S ( )
{
    int los = zero_or_one();
    if ( los == 1 )
            return "1";
    else
            return strcat( print_A(), print_A() );
}

char * print_A ( )
{
    int los = zero_or_one();
    if ( los == 1 )
            return "0";
    else
            return strcat( print_S(), print_S() );
}

Returns segmentation fault when los = 0.
Then I tried something with alloccating memory for the string and then passing it to the functions, but still no luck:

char * out = (char *) malloc( 100 * sizeof(*out) );
printf("%s\n", print_S( out ) );

and

char * print_S ( char * out )
{
    int los = zero_or_one();

    if ( los == 1 ) {
        strcpy (out, "1");
        return out;
    } else {
        return strcat( print_A(out), print_A(out) );
    }
}

char * print_A ( char * out )
{
    int los = zero_or_one();

    if ( los == 1 ) {
        strcpy (out, "0");
        return out;
    } else {
        return strcat( print_S(out), print_S(out) );
    }
}

What's the right approach? Thanks

Answer 1

Given the context of the other question, I think you should arrange for the initial call to the functions to be given the start and end of an array of, say, 100 characters. As you work down recursively, you increment the start pointer that you pass to other functions appropriately.

This code works for me:

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

/* One of these is sufficient; symmetry requires both */
static char *print_S(char *dst, char *end);
static char *print_A(char *dst, char *end);

static int zero_or_one(void)
{
    int rv = rand() % 2;
    return rv;
}

static char *print_S(char *dst, char *end)
{
    assert(dst <= end);
    if (dst < end)
    {
        if (zero_or_one() == 0)
            *dst++ = '0';
        else
        {
            dst = print_A(dst, end);
            dst = print_A(dst, end);
        }
    }
    *dst = '\0';
    return dst;
}

static char *print_A(char *dst, char *end)
{
    assert(dst <= end);
    if (dst < end)
    {
        if (zero_or_one() == 1)
            *dst++ = '1';
        else
        {
            dst = print_S(dst, end);
            dst = print_S(dst, end);
        }
    }
    *dst = '\0';
    return dst;
}

int main(void)
{
    srand(time(0));
    for (int i = 0; i < 25; i++)
    {
        char buffer[100];
        (void)print_A(buffer, buffer + sizeof(buffer) - 1);
        printf("%s\n", buffer);
        (void)print_S(buffer, buffer + sizeof(buffer) - 1);
        printf("%s\n", buffer);
    }
    return 0;
}

Note that the sequences are often very short but can be quite long. One example run:

01011
0
1
0
1
0
00
11
1
0
1
0
1
1110
00
101110101000000011100001110000100111011011000110001000000111010001000110000100010000111111001100011
1
0
11000011111000110011001000011100
0
1
1000000100001000
011
0
110
0
1
0
1
001
1
0110110011000
11110011110101100101100000111101011010001000110110010100011001100
10111001100101
1
100
100010
0
00
0
011
11
0000100010110
0
1
11
00
0
1
0

Some example runs were truncated at 99 characters — as the long one in this example was. I tried with sizes 300 and 1000 too; in both cases, I got sample runs that were truncated.

If you want to do dynamic memory allocation, you have to be a little bit more devious:

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

/* One of these is sufficient; symmetry requires both */
static char *print_S(char **buffer, size_t *len, char *dst);
static char *print_A(char **buffer, size_t *len, char *dst);

static int zero_or_one(void)
{
    int rv = rand() % 2;
    return rv;
}

static void add_space(char **buffer, size_t *len, char **dst)
{
    assert(*dst < *buffer + *len);
    if (*dst == *buffer + *len - 1)
    {
        char *newbuf = realloc(*buffer, 2 * *len);
        if (newbuf == 0)
        {
            fprintf(stderr, "Out of memory (%zu)\n", 2 * *len);
            exit(1);
        }
        *len *= 2;
        *buffer = newbuf;
        *dst = *buffer + strlen(*buffer);
    }
}

static char *print_S(char **buffer, size_t *len, char *dst)
{
    add_space(buffer, len, &dst);

    if (zero_or_one() == 0)
        *dst++ = '0';
    else
    {
        dst = print_A(buffer, len, dst);
        dst = print_A(buffer, len, dst);
    }
    *dst = '\0';
    return dst;
}

static char *print_A(char **buffer, size_t *len, char *dst)
{
    add_space(buffer, len, &dst);
    if (zero_or_one() == 1)
        *dst++ = '1';
    else
    {
        dst = print_S(buffer, len, dst);
        dst = print_S(buffer, len, dst);
    }
    *dst = '\0';
    return dst;
}

int main(void)
{
    srand(time(0));
    size_t len = 100;
    char *buffer = malloc(len);
    for (int i = 0; i < 25; i++)
    {
        (void)print_A(&buffer, &len, buffer);
        printf("%zu: %s\n", strlen(buffer), buffer);
        (void)print_S(&buffer, &len, buffer);
        printf("%zu: %s\n", strlen(buffer), buffer);
    }
    free(buffer);
    return 0;
}

With this, I got one run where the output string was 14,473,874 bytes long. I won't bother to print it here; suffice to say there were 1's and 0's in it.