Last active
August 29, 2015 13:57
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/**************************************************************************** | |
* 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