free causing different results from malloc

Question

Below is a C program I have written to print different combination of characters in a string.

This is not an efficient way as this algorithm creates a lot of extra strings. However my question is NOT about how to solve this problem more efficiently.

The program works(inefficiently though) and prints the different combination of the characters of string(correctly). But when I try to free the extra strings that is getting created I run into issue. The free that is causing issue is at the end of the recur_printc function (it is commented).

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

#define N 3

void recur_printc(char *, int, char *);
int main()
{
    char str[] = "abc";
    char *print_arr = malloc(N * sizeof(char));
    //Call recur_print
    recur_printc(print_arr, 0, str);
    free(print_arr);
    return 0;
}

void recur_printc( char *print_arr, int index, char *remaining)
{
    int i, j, rem_len, index_4_next;
    //base case, only last character remaining
    if(strlen(remaining) == 1)
    {
        print_arr[index] = remaining[0];
        //Print the print_arr
        for(i=0; i<N; i++)
        {
            printf("%c",print_arr[i]);
        }
        printf("\n");
        return;
    }
    //If more than one character remaining
    else
    {
        rem_len = strlen(remaining);
        for(i=0; i<rem_len; i++)
        {
            //Add one character to print_arr
            print_arr[index] = remaining[i];
            //now create the string with remaining characters 
            char *remaining_for_next = malloc((rem_len-1) * sizeof(char));
            index_4_next = 0;
            for(j=0; j<rem_len; j++)
            {
                if(j != i)
                {
                    remaining_for_next[index_4_next] = remaining[j];
                    index_4_next++;
                }
            }
            //call recur_print 
            recur_printc(print_arr, index+1, remaining_for_next);
            //Free the remainin_for_next
            /*------This is causing issues----*/
            //free(remaining_for_next);
            remaining_for_next = NULL;
        }
    }
}

When I ran this program in gdb I noticed that when i=1 for the first instance of recur_print, a strange thing happens with the malloc.

When this line is executed :

char *remaining_for_next = malloc((rem_len-1) * sizeof(char));

Although rem_len-1 equals to 2, malloc allocates 3 bytes, and then the whole algorithm fails because the somewhere in the code strlen of this string is used (which will be 3 instead of 2). Not sure what is happening.(This does not happen when I comment out the free() line.)

Below is gdb output :

42              char *remaining_for_next = malloc((rem_len-1) * sizeof(char));
(gdb) print remaining_for_next
$3 = 0x0
(gdb) n
43              index_4_next = 0;
(gdb) print remaining_for_next
$4 = 0x602030 "@ `"
(gdb) print rem_len-1
$5 = 2
(gdb) q

Sorry for the long post. Once again, my question is NOT about how to print the combination in a different(and better) way. My question is why the above code fails when I try to free the remaining_for_next string (maybe why malloc is getting affected).

Answer 1

Every time you are creating your string, you are not appending a null terminator, which causes the error.

So change this:

for(j=0; j<rem_len; j++) {
  if(j != i) {
    remaining_for_next[index_4_next] = remaining[j];
    index_4_next++;
  }
}

to this:

for(j=0; j<rem_len; j++) {
  if(j != i) {
    remaining_for_next[index_4_next] = remaining[j];
    index_4_next++;
  }
}
remaining_for_next[index_4_next] = '\0';

Output:

gsamaras@gsamaras:~/Desktop/px$ gcc -Wall main.c
gsamaras@gsamaras:~/Desktop/px$ ./a.out 
abc
acb
bac
bca
cab
cba

Tip: It's almost always a must to null terminate your strings, do not forget it!

---

Important edit:

As alk noticed, you need to change this:

char *remaining_for_next = malloc((rem_len - 1) * sizeof(char));

to this:

char *remaining_for_next = malloc((rem_len) * sizeof(char));

in order to make space for the null terminator.

---

_{Nice question, +1.}

Answer 2

I haven't gone through everything with a fine-toothed comb but I believe the remaining_for_next string will have no null character termination. You're using strlen() which doesn't include the null character in the string length and then copying the string as if it were an array of characters. It might be a place to begin searching. I'd imagine the first time that recur_printc is called from itself, the behaviour won't be what you want. Try manually appending a null character to remaining_for_next and see if that fixes the problem.