Member Avatar for xcr

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.

Recommended Answers

All 3 Replies

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;
        
    }

Should be

else{     /*else search for correct location*/
    unsigned long front = 0;
    unsigned long back = pDict->count - 1; //HERE is the change
    /*input it there*/
    pDict->wordList[binarysearch (pDict, word, front, back)] = word;
        
    }
Member Avatar for xcr

Thank you for the prompt reply,
I implemented the change you suggested, however, when I run it I still Seg Fault. Wnhen I backtrack it through gdb I get

(gdb) bt
#0  0xb7ee942a in strcmp () from /lib/libc.so.6
#1  0x08048643 in binarysearch (pDict=0x804b008, key=0x8048951 "Sorry", first=0, last=4294967295) at dictionary.c:51
#2  0x08048762 in addWordDict (pDict=0x804b008, word=0x8048951 "Sorry") at dictionary.c:78
#3  0x0804882e in main () at lab5.c:15

last=MAX_UNSIGNED_INT?
Sounds like you subtracted 1 from 0, as there are not that many words in a dictionary.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.