Hello all,
I hope that someone can help me with this,
I am trying to add an element to a dictionary, and in order to do such, I am using a binary search mechanism to find the correct place in the dictionary. My code compiles fine, but when I run it, it will hang. When I use a debugger, I get that the code gets stuck at the line "if ( strcmp(key, pDict->wordList[mid]) > 0){" (line 56 in the code here) when my third word is going through.
Can anyone help me out on this? my code is below:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INITIAL_DICT_SIZE 10
typedef struct {
char **wordList;
unsigned long wordListSize;
unsigned long count;
} dictionary;
int initDict(dictionary ** pDict) {
*pDict = (dictionary*) malloc(sizeof(dictionary));
if (NULL != pDict) { /* if malloc doesn't fail*/
(*pDict)->count = 0;
(*pDict)->wordListSize = INITIAL_DICT_SIZE;
(*pDict)->wordList = malloc(sizeof(char*)*INITIAL_DICT_SIZE);
if (NULL == (*pDict)->wordList) { /* free it if it does*/
free(pDict);
return -1;
}
}
return 0;
}
void destroyDict(dictionary* pDict) {
free(pDict->wordList);
free(pDict);
}
int printDict(dictionary* pDict) {
char** index;
for (index = pDict->wordList; index != &pDict->wordList[pDict->count]; ++index) {
printf("%s \n", *index); /*maybe not the most effective way*/
}
return 0;
}
static int growDict(dictionary* pDict, unsigned long newS, void ** newWs){
* newWs = realloc(pDict->wordList, sizeof(char*)*newS); /*change old to old + new*/
if (NULL == newWs) { /*if that fails */
return 1;
} else { /*update variables */
pDict->wordListSize = newS;
pDict->wordList = (char**)newWs;
}
return 0;
}
unsigned long binarysearch(dictionary* pDict, char* key, unsigned long first, unsigned long last){
while (first <= last){
unsigned long mid = (last-first) / 2; /*find midpt*/
if ( strcmp(key, pDict->wordList[mid]) > 0){ /*above midpoint*/
first = mid + 1;
}else if (strcmp (key, pDict->wordList[mid]) < 0){ /*below midpoint*/
last = mid - 1;
} else if (strcmp (key, pDict->wordList[mid]) == 0){/*we've got it*/
return mid;
}
}
return -(first + 1); /*fail*/
}
int addWordDict(dictionary* pDict, char* word) {
unsigned long count = pDict->count;
if (count >= pDict->wordListSize) {
unsigned long newSize = pDict->wordListSize + sizeof(pDict->wordList);
void * newWords;
growDict(pDict, newSize, &newWords); /* grow the dictionary for me*/
}
/*sort method:*/
/*handle the case where word should be the first element*/
if (pDict->wordList[0] == NULL || strcmp(word, pDict->wordList[0]) > 0){
pDict->wordList[0] = word;
}else{ /*else search for correct location*/
unsigned long front = 0;
unsigned long back = pDict->count;
/*input it there*/
pDict->wordList[binarysearch (pDict, word, front, back)] = word;
}
/*back to regularly scheduled code*/
++pDict->count; /*keep count up to date*/
return 0;
}
int verifyDict(dictionary * pDict, char* match){
unsigned long index;
for (index = 0; index < pDict->count; index++) {
if (!strcmp(pDict->wordList[index], match)){ /* strcmp returns 0 on success*/
return 0;
}
}
return 1;
}
int main (/*int argc, char* argv[]*/) {
dictionary dict;
dictionary* pdict = &dict;
initDict(&pdict);
addWordDict(pdict, "Hello");
addWordDict(pdict, "World");
addWordDict(pdict, "Sorry");
addWordDict(pdict, "Excuses");
printDict(pdict);
verifyDict(pdict, "Hello");
destroyDict(pdict);
return 0;
}sorry for the long post, but I could really use another set of eyes on this.