0

This problem set is becoming my bane. I have spent hours on it and I am still getting the same issues with valgrind (definitely losing 7 million bytes). I think my issues lie with load and check and not unload or the word count. I have tried starting over and writing everything out on paper, and while that proved to tidy-up and fix some of my code, the whole of it remains broken. Help would be much appreciated :)

Global stuff and headers:

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

#include "dictionary.h"

// define a node
typedef struct node
{
// array to store word
char new[LENGTH + 1];

//create a pointer to the next node
struct node* next;
}node;

// hash function
int hash_fxn (char* key)
{
// hash on 1st letter (apostrophe hashes to 'a')
    int hash = toupper(key[0]) - 'A';
    return hash % 26;
}

// create the base array of the alphabet
node* alphabet[26];

// word counter
int wordcount = 0;

Check function:

   /**
   * Returns true if word is in dictionary else false.
   */
   bool check(const char* word)

{ // TODO

// get space for lowercase shifted word
char lowercase[strlen(word)];

// create space for new node cursor
node* cursor = NULL;

// break down word to all lower-case
for (int i = 0; i < strlen(word); i++)
    lowercase[i] = tolower(word[i]);
lowercase[strlen(word)] = '\0'; // end of string marker

// go to corresponding bin for hash function and search
cursor = alphabet[hash_fxn(lowercase)];

while (cursor != NULL)
{
    // compare strings with strcmp
    if (strcmp(cursor->new, lowercase) == 0)
        return true;  
    cursor = cursor->next;
}

free(cursor);
return false;
}

Load function:

/**
* Loads dictionary into memory.  Returns true if successful else false.
*/
bool load(const char* dictionary)
{
// TODO
// allocate space for the array of linked lists
for (int i = 0; i < 26; i++)
{
    alphabet[i] = NULL;
}

// open dictionary
FILE* dict = fopen(dictionary, "r");

if (dict == NULL)
{
    printf("Dictionary could not be loaded\n");
    return false;
}

// create temporary placeholder node
node* temp = NULL;

// execute while the dictionary is not finished
while (!feof(dict))
{
    // create space for new_node
    node* new_word = malloc(sizeof(node));

    // read word from dictionary and place it in new node
    fscanf(dict, "%s", new_word->new);

    // generate hash value
    int hash_value = hash_fxn(new_word->new);

    // if there is nothing already in the hash bin
    if (alphabet[hash_value] == NULL)
        alphabet[hash_value] = new_word; // set the bin equal to the new node

    // if something is in bin insert at the head of the bin
    else if (alphabet[hash_value] != NULL)
    {
        // insert new_word at head of linked list utilizing temporary storage
        temp = alphabet[hash_value];
        new_word->next = temp;
        alphabet[hash_value] = new_word;        
    }

    // add to wordcount
    wordcount++;
}   

// if all goes according to plan, return true
return true;
}

Unload function:

/**
* Unloads dictionary from memory.  Returns true if successful else false.
*/
bool unload(void)
{
// TODO

for (int i = 0; i < 26; i++)
{
    node* cursor = alphabet[i];
    while (cursor != NULL)
    {
        node* temp = cursor;
        cursor = cursor->next;
        free(temp);
    }
    free(alphabet[i]);
}
return true;
}
1

I haven't tested the code, but I have several observations. First, do you actually have the code fully working? If not, you really should focus on that first. Correcting memory leaks before getting it working often just complicates the debugging.

Here's a red flag:

// create the base array of the alphabet
node* alphabet[25];

There are 26 letters in the alphabet, not 25.

In check():

  • you're not inserting an end of string marker into lowercase.
  • the pointer cursor is declared with a malloc and later reassigned to something else. The memory that was malloc'd is lost, a memory leak of 45 bytes for every word checked. Assign the pointer to null instead.

Look at the following code:

  while (cursor != NULL)
  {
      // compare strings with strcmp
      if (strcmp(cursor->new, lowercase) == 0)
          free(lowercase);
          free(cursor);
          return true;  
      cursor = cursor->next;
  }

It looks like you wanted to execute multiple statements when the IF statement is true, but only the first free() will execute based on the IF statement because there are no curly braces. The second free and the return will ALWAYS execute. Next, return statements always immediately terminate the current function and return to the calling code.The assignment of cursor is never executed and is dead code. My guess is that you wanted to enclose the two free() statements and the return statement in curly braces.

You could have declared both cursor and lowercase as regular vars instead of pointers and eliminated the need for mallocs and frees for both.

In LOAD():

This code is a big memory leak:

alphabet[i] = malloc(sizeof(node));
alphabet[i] = NULL;

The first line allocates memory, the second line sets the pointer to null, leaving the previously allocated memory lost but still allocated.

Similarly, temp is declared with a malloc and then reassigned, losing the allocated memory. In a related problem that is probably causing more significant issues, you later free(temp);. Earlier, you temp = alphabet[hash_value]; so the last alphabet[hash_value] that was assigned to temp will be freed and lost from the dictionary.

In the unload() function, cursor will always be null when you hit the free(cursor). There's nothing to free there.

In summary, the biggest problem I see is that you declare a pointer, malloc memory to it, and then reassign the pointer elsewhere, thus losing track of the allocated memory. Instead, you could declare them and assign null to the pointers.

There are probably other issues, but this will get you started again.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

3
  • So I have updated the code above with all of your hints. You were right, one of my biggest flaws was that I wasn't aware that setting something to NULL after allocating memory to it would throw that memory away. That being said, I am only ever reading a handful of words spelled correctly. So, I am either not correctly forming my hash-table, or my check function isn't identifying the correct words (I think it is my check function).
    – peachykeen
    Dec 6 '15 at 23:55
  • Sounds like time to spend some quality time with gdb and inserting some strategic printf statements. You might also try testing with a small dictionary of about 3 or 4 words and using the dictionary file as both the dictionary and the file to be tested. If your program says that there's a misspelled word or doesn't give the right counts, then you know you still have a problem. Of course, a small dictionary may not reveal some unique issues, but it will get you a long way toward success.
    – Cliff B
    Dec 7 '15 at 3:35
  • After some extensive use of GDB and Valgrind, I got it. Thank you for all your help :).
    – peachykeen
    Dec 7 '15 at 20:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .