I want to start by saying that I'm absolutely not an expert with C programming and I haven't done it in a while.

But I was tasked with writing code in C for a problem regarding combinatorics.

The basic task is, given any word, to construct a square table containing all possible right shifts of a word. There's also a lot of stuff after this first step, but this is the most important one and the one that's giving me trouble.

Pratical example: If the word is "ababa", the "2D array" should contain:

1. ababa
2. aabab
3. baaba
4. abaab
5. babaa

Since this 2D array is always length * length in size (so if the word has length 5, the table will be 5x5) I thought the thing to do was:

1. Calling a function passing the length as a parameter
2. Create a char** with malloc so it is the correct size
3. return said char**
4. Calling another function to fill it with the strings

I came up with the following code, but while it is actually perfectly working in GDB online, it returns an error in Code::Blocks. The error is: Process terminated with status -1073741819

What baffles me is that, when I try to debug it, inside Code::Blocks the code actually works. This is the function that allocates the array:

char** returnTable(int length){
char** rotationTable = malloc(length*sizeof(char));
char* values = calloc((length 1)*(length 1), sizeof(char));

for(int i=0; i<length; i  ){
        rotationTable[i] = values   i*(length 1);
        rotationTable[i][0] = '\0';
}
return rotationTable;}

And this is the function that fills the struct with the right words:

void orderedConjugacyClass(char** table, char* word, int length){
    //first word copied in the rotationTable
    table[0] = strdup(word);
    //let's start from the second row
    int j = 1;
    //p on the last char of the word
    char* p = &table[j-1][length-1];
    //q on the first 
    char* q = &table[j-1][0];
    //buffer string,  1 for terminating character
    char buffer[length 1];
    buffer[0] = '\0';

    while(j < length){
        strncat(buffer, p, 1);
        strncat(buffer, q, length-1);
        buffer[length] = '\0';
        table[j] = strdup(buffer);
        p = &table[j][length-1];
        q = &table[j][0];
        //to cancel and reuse the buffer for next iteration
        buffer[0]='\0';
        j  ;
    }
}

In the main I simply call both functions. And If I just limit myself to that, the code doesn't (apparently) have problems. But whenever I try to access the contents of the table and display it with a printf, that's when the problem occurs and the output "diverges" between GDB online and CodeBlocks:

 int length = strlen(argv[1]);
        char** rotationTable = returnTable(length);
        orderedConjugacyClass(rotationTable, argv[1], length);
        
        for(int j=0; j<length; j  )
                printf("%s\n", rotationTable[j]);
        
        for(int i=0; i<length; i  )
            free(rotationTable[i]);
        free(rotationTable);
        return 0;

Additional Details: I'm on Windows, MinGW compiler.

Thank you for your help and understanding.

CodePudding user response：

Don't do this:

SomeType something = malloc(length*sizeof(SomeType));

Do this:

SomeType something = malloc(length*sizeof(*something));

The first one is only correct if the two uses of SomeType are identical, and it's a very easy mistake to make them different, particularly if you change SomeType at some point in your program development.

In this case, you wrote

char** rotationTable = malloc(length*sizeof(char));

Here, the element type is char* but you used char in the sizeof, which lead to you allocating too little space.

If you'd written

char** rotationTable = malloc(length*sizeof(*rotationTable));

you wouldn't have had that problem.

Also note that you're preallocating the elements of rotationTable and then replacing the preallocated arrays with other arrays. The originally allocated pointers are lost, so you never free them, so you have a memory leak. I don't see the point of returnTable. Just have orderedConjugacyClass create and return the array.

Finally, this is silly.

        strncat(buffer, p, 1);
        strncat(buffer, q, length-1);
        buffer[length] = '\0';

strncat has to scan the destination to find its end. But you know where the end is. So the cycles spent scanning the string are completely pointless.

buffer[0] = p[0];
memcpy(buffer 1, q, length-1);
buffer[length] = '\0';

On the other hand, p and q are kind of pointless as well, since you could just copy from the original word. Indeed, you could get rid of buffer as well:

/* Production code should check if malloc succeeded */
char** conjTable(const char* word) {
    size_t len = strlen(word);
    char** table = malloc(len * sizeof(*table));
    for (size_t i = 0; i < len;   i) {
        table[i] = malloc(len   1);
        memcpy(table[i], word   len - i, i);
        memcpy(table[i]   i, word, len - i);
        table[i][len] = '\0';
    }
    return table;
}