Skip to content

Instantly share code, notes, and snippets.

@mitrnsplt
Last active August 29, 2015 13:57
Show Gist options
  • Save mitrnsplt/9574979 to your computer and use it in GitHub Desktop.
Save mitrnsplt/9574979 to your computer and use it in GitHub Desktop.
load function in dictionary.c with huge memory leak related to line 121
/****************************************************************************
* dictionary.c
*
* Computer Science 50
* Problem Set 6
*
* Implements a dictionary's functionality
* Uses a hash function based on djb2 found at www.cse.yorku.ca/~oz/hash.html
***************************************************************************/
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dictionary.h"
unsigned int hash(const char* word);
char word[LENGTH + 1];
unsigned int word_num = 0;
#define SIZE 6569
typedef struct node
{
char* word;
struct node* next;
}
node;
//create hashtable
node* hashtable[SIZE] = {NULL};
/**
* Returns true if word is in dictionary else false.
*/
bool check(const char* word)
{
//malloc space for pointer for the word
char* text_word = (char*)malloc(sizeof(strlen(word) + 1));
// check to see if allocation was successful
if (text_word == NULL)
{
printf("Could not malloc text_word");
return false;
}
// copy word
strcpy(text_word, word);
//convert letters to lower case
for (int i = 0, n = strlen(word); i < n; i++)
{
text_word[i] = tolower(text_word[i]);
}
//hash word
unsigned int hashindex = hash(text_word);
//create a node to keep track of current position
//assign the hashindex to a node
node * current = hashtable[hashindex];
//survey bucket list to find word
while (current != NULL)
{
if (strcmp(current->word, text_word) == 0)
{
return true;
}
else
{
current = current->next;
}
}
free(current);
free(text_word);
return false;
}
/**
* Loads dictionary into memory. Returns true if successful else false.
*/
bool load(const char* dictionary)
{
//initialize a file pointer (fp) to the dictionary file in order to load the dictionary
FILE* fp = fopen(dictionary, "r");
if (fp == NULL)
{
printf("Error loading dictionary\n");
return 1;
}
// initialize variables
unsigned int hashindex = 0;
for (int i = 0; i < SIZE; i++)
{
hashtable[i] = NULL;
}
// while not end of file, get a word from the dictionary
while(fscanf(fp, "%s\n", word) != EOF)
{
//create a node to hold the word
node* tnode = malloc(sizeof(node));
// check to see if allocation was successful
if (tnode == NULL)
{
return 1;
}
//put the word in the node
tnode->word = malloc(strlen(word) + 1);
strcpy(tnode->word, word);
//hash the word and get the index
hashindex = hash(word);
//insert the word at the indexed point of the hashtable if it is empty
if (hashtable[hashindex] == NULL)
{
hashtable[hashindex] = tnode;
tnode->next = NULL;
}
// if the indexed point is occuppied, insert the word at the head of the list
else
{
tnode->next = hashtable[hashindex];
hashtable[hashindex] = tnode;
}
//count words in the dictionary as you scan
word_num++;
}
fclose(fp);
return true;
}
/**
* Returns number of words in dictionary if loaded else 0 if not yet loaded.
*/
unsigned int size(void)
{
// reports number of words counted in load
return word_num;
}
/**
* Unloads dictionary from memory. Returns true if successful else false.
*/
bool unload(void)
{
// unload hashtable
node *nextnode, *tnode;
for (int i = 0; i < SIZE; i++)
{
tnode = hashtable[i];
while (tnode != NULL)
{
free(tnode->word);
nextnode = tnode->next;
free(tnode);
tnode = nextnode;
}
}
return true;
}
unsigned int hash(const char* word)
{
int hash = 3;
for (int i = 0; i < strlen(word); i++)
{
hash += hash * 33 ^ word[i];
}
hash = abs(hash) % SIZE;
return hash;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment