Jeremy Tung Jeremy Tung - 1 year ago 66
C Question

Writing a word puzzle solver and getting segmentation fault. Seems to be to do with freeing heap memory. Can someone take a look?

I am having some trouble with heap memory. I am writing some code in C to solve word puzzles - (from a game called Countdown here in the UK). The game is that you are given 9 letters and the goal is to make the longest word you can.

My code works (although I haven't fully tested it) if I comment out all the calls to free() but when I put the free calls in I get a segmentation fault. I have run valgrind and get error messages like "Address 0x9cbe627 is 7 bytes inside a block of size 9 free'd" and "invalid read of size 1." I have tried looking online to find out about this and I still don't understand.

Can anyone take a look and explain what is going on? (Code given below) I would be very appreciative!

/**
* Program to solve word puzzles from the TV show Countdown. Asks for 9
* letters for input and then prints out the
* maximum score and an example word of that score
*/

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

/*
uses recursion to iterate over combinations of size "length" from
data[] of size "lengthData." Stores combinations generated in
combination[] and permutations in permutation[]. For each combination
calls checkPermutations to iterate over all permutations
of the combination checking against a dcitionary for word matches
returning true if a match is found
*/
bool checkForWords(char data[], int lengthData, int length, char
combination[], int lengthCombination, char permutation[]);

/**
* takes in an array - (in practice combination[] from main()) and
* iterates through all the permutations of the array storing
* generated permutations in permutation[] by using recursion. For
* each checks against a dictionary for word match. Returns true
* when match is found
*/
bool checkPermutations(char data[], int lengthData, char permutation[],
int lengthPermutation);

/**
* takes an array of some length and an index and then retruns a
* pointer to an array on the heap that is the same but with the
* elements at the index and to the left removed and then remaining
* elements "shifted down"
*/
char* removeLeftOfIndex(char data[], int lengthData, int index);

/**
* takes an array of some length and index position and returns a
* pointer to an array on the heap that has the element removed
* and remaining elements "shifted down"
*/
char* removeElementAtIndex(char data[], int lengthData, int index);

int main(void)
{
char letters[9];

// getting letters
for (int i = 0; i < 9; i++)
{
printf("Please enter letter %i: ", i + 1);
letters[i] = GetChar();
}

// formatting
printf("\n");


// iterating over the length of word to look for starting at 9 and
decrementing
for (int i = 9; i > 0; i--)
{
char* data = malloc(9 * sizeof(char));
char* permutation = malloc(10 * sizeof(char));
char* combination = malloc(9 * sizeof(char));

for (int j = 0; j < 9; j++)
data[j] = letters[j];

// checks to see if there is a word of length i
if (checkForWords(data, 9, i, combination, i, permutation) == true)
{
printf("Max score: %i\nExample word: %s\n", i, permutation);
free(permutation);
return 0;
}

free(permutation);
}

// no words found
printf("Max score: 0\nNo words can be made\n");
return 0;
}

bool checkForWords(char data[], int lengthData, int length, char
combination[], int lengthCombination, char permutation[])
{
// base recursive case
if (length == 0)
{
free(data);

// checks for permutations for the fixed combination
return checkPermutations(combination, lengthCombination, permutation, lengthCombination);
}

else
{
// generating combination by fixing one element and the recursively generating and checking
for (int j = 0; j <= lengthData - length; ++j)
{
// fixes one element
combination[lengthCombination - length] = data[j];

// recursive part
if (checkForWords(removeLeftOfIndex(data, lengthData, j), lengthData - j - 1, length - 1, combination,
lengthCombination, permutation) == true)
{
free(data);
return true;
}
}

free(data);
return false;
}
}

bool checkPermutations(char data[], int lengthData, char permutation[], int lengthPermutation)
{

// base recursive case
if (lengthData == 0)
{
// null character for printing string later
permutation[lengthPermutation] = '\0';


// checking against dictionary - make this much faster with binary search!!!!
FILE* dictionary= fopen("/usr/share/dict/words", "r");
char word[15];
while (fgets(word, sizeof(word), dictionary) != NULL)
{
// checks to see if match
if (strncmp(permutation, word, lengthPermutation) == 0)
{
fclose(dictionary);
free(data);
return true;
}

}

// not in dictionary
fclose(dictionary);


free(data);
return false;

}

else
{
// generating permutations and checking for words by fixing one element and then using recursion.
for (int j = 0; j < lengthData; j++)
{
// fixing element
permutation[lengthPermutation - lengthData] = data[j];

// recursive part
if (checkPermutations(removeElementAtIndex(data, lengthData, j), lengthData - 1, permutation, lengthPermutation) == true)
{
free(data);
return true;
}

}
free(data);
return false;
}
}

char* removeLeftOfIndex(char data[], int lengthData, int index)
{
// allocating heap memory
char* newData = malloc((lengthData - index - 1) * sizeof(char));

// loop to copy relevant parts
for (int j = 0; j < lengthData - index - 1; j++)
newData[j] = data[j + index + 1];

return newData;
}

char* removeElementAtIndex(char data[], int lengthData, int index)
{
// allocating heap memory
char* newData = malloc((lengthData - 1) * sizeof(char));

// loops to copy relevant parts
for (int i = 0; i < index; i++)
newData[i] = data[i];
for(int i = index; i < lengthData - 1; i++)
newData[i] = data[i + 1];

return newData;

}


It might also be worth mentioning that when I tried debugging that the segmentation fault appeared to be happening on a call to malloc() in the implementation of the last function in the code:

// allocating heap memory
char* newData = malloc((lengthData - 1) * sizeof(char));


Thanks in advance for any help. I am relatively new to programming so heap memory is fairly new to me and hopefully someone can explain and anyone with similar question can learn too!

Answer Source

Your code is quite a spider's web of memory allocation and freeing. I've reworked it so the memory allocation make a little more sense (to me, anyway.) Having a subroutine free memory of its caller is odd -- the opposite is OK, having a caller free the return result of a subroutine.

Although the basic case (exact match for word in dictionary) seems to work, I can't say I was able to test the other possibilities so this code may need more debugging. But it's not complaining about memory errors:

/**
 * Program to solve word puzzles from the TV show Countdown. 
 * Asks for 9 letters for input and then prints out the
 * maximum score and an example word of that score
 */

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

/**
 uses recursion to iterate over combinations of size "length" from 
 data[] of size "lengthData." Stores combinations generated in
 combination[] and permutations in permutation[]. For each combination
 calls checkPermutations to iterate over all permutations
 of the combination checking against a dictionary for word matches 
 returning true if a match is found
 */
bool checkForWords(char data[], int lengthData, int length, char combination[], int lengthCombination, char permutation[]);

/**
 * takes in an array - (in practice combination[] from main()) and
 * iterates through all the permutations of the array storing
 * generated permutations in permutation[] by using recursion. For 
 * each checks against a dictionary for word match. Returns true
 * when match is found
 */
bool checkPermutations(char data[], int lengthData, char permutation[], int lengthPermutation);

/**
 * takes an array of some length and an index and then returns a
 * pointer to an array on the heap that is the same but with the
 * elements at the index and to the left removed and then remaining 
 * elements "shifted down"
 */
char *removeLeftOfIndex(char data[], int lengthData, int index);

/**
 * takes an array of some length and index position and returns a
 * pointer to an array on the heap that has the element removed
 * and remaining elements "shifted down"
 */
char *removeElementAtIndex(char data[], int lengthData, int index);

#define LETTER_COUNT (9)

int main(void)
{
    char letters[LETTER_COUNT];

    // getting letters
    for (int i = 0; i < LETTER_COUNT; i++)
    {
        printf("Please enter letter %i: ", i + 1);
        letters[i] = GetChar();
    }

    // formatting
    printf("\n");

    bool success = false;

    char *data = malloc(LETTER_COUNT);
    char *permutation = malloc(LETTER_COUNT + 1);
    char *combination = malloc(LETTER_COUNT);

    // iterating over the length of word to look for starting at 9 and decrementing
    for (int i = LETTER_COUNT; i > 0; i--)
    {
        (void) strncpy(data, letters, LETTER_COUNT);

        // checks to see if there is a word of length i
        if (checkForWords(data, LETTER_COUNT, i, combination, i, permutation))
        {
            printf("Max score: %i\nExample word: %s\n", i, permutation);
            success = true;
            break;
        }
    }

    if (!success)
    {
        printf("Max score: 0\nNo words can be made\n");
    }

    free(data);
    free(permutation);
    free(combination);

    return EXIT_SUCCESS;
}

bool checkForWords(char data[], int lengthData, int length, char combination[], int lengthCombination, char permutation[])
{
    // base recursive case
    if (length == 0)
    { 
        // checks for permutations for the fixed combination
        return checkPermutations(combination, lengthCombination, permutation, lengthCombination);
    }

    // generating combination by fixing one element and the recursively generating and checking
    for (int j = 0; j <= lengthData - length; ++j)
    { 
        // fixes one element
        combination[lengthCombination - length] = data[j];

        // recursive part
        char *reduced = removeLeftOfIndex(data, lengthData, j);
        if (checkForWords(reduced, lengthData - j - 1, length - 1, combination, lengthCombination, permutation))
        {
            free(reduced);
            return true;
        }
        free(reduced);
    }

    return false;
}

bool checkPermutations(char data[], int lengthData, char permutation[], int lengthPermutation)
{
    // base recursive case
    if (lengthData == 0)
    { 
        // null character for printing string later
        permutation[lengthPermutation] = '\0';

        // checking against dictionary - make this much faster with binary search!!!!
        FILE* dictionary= fopen("/usr/share/dict/words", "r");
        char word[64];

        while (fgets(word, sizeof(word), dictionary) != NULL)
        { 
            // checks to see if match
            if (strncmp(permutation, word, lengthPermutation) == 0)
            { 
                fclose(dictionary);
                return true;
            }
        }

        // not in dictionary
        fclose(dictionary);
        return false;
    }

    // generating permutations and checking for words by fixing one element and then using recursion.
    for (int j = 0; j < lengthData; j++)
    { 
        // fixing element
        permutation[lengthPermutation - lengthData] = data[j];

        // recursive part
        char *reduced = removeElementAtIndex(data, lengthData, j);
        if (checkPermutations(reduced, lengthData - 1, permutation, lengthPermutation))
        {
            free(reduced);
            return true;
        }
        free(reduced);
    }

    return false;
}

char *removeLeftOfIndex(char data[], int lengthData, int index)
{ 
    // allocating heap memory
    char *newData = malloc(lengthData - index - 1);

    // loop to copy relevant parts
    for (int j = 0; j < lengthData - index - 1; j++)
    {
        newData[j] = data[j + index + 1];
    }

    return newData;
}

char *removeElementAtIndex(char data[], int lengthData, int index)
{ 
    // allocating heap memory
    char *newData = malloc(lengthData - 1);

    // loops to copy relevant parts
    for (int i = 0; i < index; i++)
    {
        newData[i] = data[i];
    }

    for (int i = index; i < lengthData - 1; i++)
    {
        newData[i] = data[i + 1];
    }

    return newData;
}

Good luck and I hope this helps!