0

No matter what text I test this with, I only ever get 3 or maybe 4 frees using Valgrind. Any ideas why?

/**
 * Implements a dictionary's functionality.
 */

#include <stdbool.h>
#include "dictionary.h"
#include <stdio.h>
#include <strings.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef struct node
{
    char word[LENGTH+1];
    struct node *next;
}
node;
node *hashtable[50];
int numofwords = 0;

/**
 * Returns true if word is in dictionary else false.
 */

bool check(char *searchword)
{

    // make the whole thing lowercase
    int len = strlen(searchword);
    char newword[len+1];


    for(int i = 0; i< len; i++){
        newword[i] = tolower(searchword[i]);
    }
    newword[len] = '\0';

    int x = hash(newword);
    node *current;
    current = hashtable[x];

    if (current == NULL){
        return false;
    }

    int cmpres = strcasecmp(current->word, newword);
    while(current != NULL){
        cmpres = strcasecmp(current->word, newword);
        if (cmpres == 0){
            return true;
        }
        current = current->next;
    }
    return false;
}

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary)
{

    FILE* dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("No valid dictionary to open.\n");
        return false;
    }

    char newstring [LENGTH+1];
    //make a new node for the word
    while (fscanf(dict, "%s", newstring) != EOF){
        node *newnode = malloc(sizeof(node));
        numofwords ++;
        int x = hash(newstring);
        //copy the newstring in to word
        strcpy(newnode->word, newstring);
        //replace head node with new node and link it to old head
        newnode->next = hashtable[x];
        hashtable[x] = newnode;
    }
    fclose(dict);
    return true;
}


/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{

    if (numofwords == 0){
        return 0;
    }
    else{
        return numofwords;
    }
}

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */
bool unload(void)
{
    // TODO
    int freed = 0;
    for(int i = 0; i < 50; i++){
        node *current = hashtable[i];
        while(current != NULL){
                node *temp=current;
                current=current->next;
                free(temp);
                freed++;
        }
        freed++;
    }
    if (freed!= 0){
        return true;
    }
    else{
        return false;
    }
}

/**
 * Hashes a word
 */

 int hash(char *newstring){
    char y = newstring[0];
    char z = newstring[1];
    int f = abs((y+z)/2);
    return f;
    }
0

Something tells me that your hash function does not output numbers between 0 and 49, so your nodes are mostly installed behind the elements you free later ("a" would end up at index 48, I cannot imagine another word in range), in memory that somewhat belongs to your programme (therefore no segmentation fault), but is not part of hashtable. Also, it's not a hash function I'd use at all.

At least use something like return f % 50; in the hash function, but you should consider using a completely different hash function. There are many out there, some with fancy bit shifting, but even something simple multiplication-based like

int hash(char *newstring)
{
    int hash = 42;
    for (int pos = 0, len = strlen(newstring); pos < len; pos++)
    {
        hash = (hash * 23 + newstring[pos]) % 50;
    }
    return hash;
}

would work. I hard-coded the hashtable length 50 in there, you could make that a constant in your code and try the performance for different values. The two magic numbers 42 and 23 could be anything, with a few constraints:

  • Initial value should be at least 1 and less than the hashtable size. Little relevance for text, as there cannot be zeroes in there.
  • Factor should be co-prime to the hashtable length, meaning they have no common dividers other than 1

You could also take some fancy bit-shifting algorithm, as long as you use something like %50 to ensure a result in range.

You must log in to answer this question.

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