0

Ok...I'm doing pset5 and I'v already done the load function though I think there's something wrong with it.When I run speller it gives a seg fault in check function.Something to do with strcmp according to gdb.

After a looot of debugging, I'v found out that it crashes in the strcmp function and for some reason my second node of the first bucket..Um..first linked list in the array is this 

"IN\000urgy\000\000ns\000\000m\000\000\000\000\000\000\000\000\000csilicovolcanoconiosis"

And here's my hash function, super simple I know, I'm gonna change it in the end.

int hashy(char* word){

 int num = (int)(toupper(word[0]) - 65);

 return num % 26;

}

And here's my load-

bool load(const char* dictionary)
{

FILE* dic = fopen(dictionary,"r");

//Make all the next pointers NULL
for(int j=0;j<26;j++){
 letters[j] = malloc(sizeof(node));
 letters[j]->next = NULL;
}

//Check if file could be opened
if(dic == NULL){

  printf("File not found, I repeat File not found");
  return false;

}

for(int i = 0;!feof(dic);i++){

  //new node
  node* new_node = malloc(sizeof(node));

  //get the word and store it in the node
  fscanf(dic,"%s",new_node->word);

  //first time
  if(letters[hashy(new_node->word)]->next == NULL){
    //letters[hashy(new_node->word)]->word = new_node->word;
    strcpy(letters[hashy(new_node->word)]->word,new_node->word);
    letters[hashy(new_node->word)]->next = new_node;
  }else{

    node* crawler = letters[hashy(new_node->word)]->next;

    while(!(crawler->next == NULL)){

     crawler = crawler->next;

    }

    crawler->next = new_node;

  }

  free(new_node);

}

fclose(dic);

return true;
}

And finally the check function-

bool check(const char* word)
{
char* worda = malloc(46);
strcpy(worda,word);

//find the wanted bucket
int buc = hashy(worda);

//loop through word
for(int i = 0,n = strlen(worda);i < n;i++){

if(isupper(worda[i])){
 tolower(worda[i]);
 }

}

node* crawler = letters[buc];

while(crawler != NULL){

  if(strcmp(crawler->word,worda) == 0){
  free(crawler);
  free(worda);
  return true;
      }

    crawler = crawler->next;

   }

    free(crawler);
    free(worda);
    return false;
}

Oh and the worda dosent get converted to lowercase letters in the function. I'v declared the letters array and struct node globally.Oh and here's what gdb shows in the end-

67      crawler = crawler->next;
(gdb) n
69     }
(gdb) 
59      while(crawler != NULL){
(gdb) 
61        if(strcmp(crawler->word,worda) == 0){
(gdb) 

Program received signal SIGSEGV, Segmentation fault.
__strcmp_sse4_2 () at ../sysdeps/i386/i686/multiarch/strcmp-sse4.S:217
217     movdqu  (%edx), %xmm2

Please do tell me what I'm doing wrong.

Improve this question
1

Does your load function even work? If not, that would explain the segfault (accessing illegal memory location) since there is no linked list to begin with.

Other points to consider:

  1. Your hash function looks fine. Since you know dictionary words are all in lower case, you could've just left them as is and subtracted 97. No need for %26 either.
  2. When you add new_node to your linked list in load, what does its next point to?
  3. Consider whether you really need a crawler node in load, which, by the way, you did not malloc. Looks like the reason you included it because you want to add each successive entry to the end, rather than the beginning, of the list. However, your check function doesn't use a search algorithm to take advantage of a sorted list. If you don't plan on sorting the list, you might as well add new entries to the head of the list and do away with crawler. Or use a search algorithm in check, but be sure to free crawler.
Improve this answer
  • Thanks a lot, but I was wondering about the search algorithm.Why do you need it? I thought they wouldnt work in a linked list right? Wasnt that the disadvantage of linked lists to arrays? We lose random access so what search algorithm do we use? – Jedi18 Oct 21 '15 at 6:31
  • Oh and could you please tell me why the letters are not converted to lowercase in the check function? When I print them in gdb they're still in upper case. – Jedi18 Oct 21 '15 at 6:33
  • 1. My understanding was that you used crawler in load to add new entries to the end of the list, rather than at the beginning, so as to keep your list alphabetized/sorted. This would make for faster checking. If that wasn't in fact your intent, then you don't need to crawler, just add new entries at the head of the list (i.e. letters[i] becomes new_node). Adding entries to the head of a list is more straightforward. 2. As for the question re not being converted to lowercase letters, take a look at the type of argument being passed to check, char*. – ronga Oct 21 '15 at 8:53
  • Oh ok thanks, but yeah I know it's a const char* but that's the reason why I created the worda variable, so shouldn't it be char* then? – Jedi18 Oct 21 '15 at 16:00
  • Notice the *, that means it's a pointer, so you're not directly accessing the variable. For that matter, you don't need to. You just need to have a char array within your check function to verify if the word is in the dictionary, you don't care if it's freed from stack after function executes, you just need check to tell you if it's in the dictionary (return true) or not. – ronga Oct 22 '15 at 1:11
0
bool load(const char* dictionary)
{

FILE* dic = fopen(dictionary,"r");

//Make all the next pointers NULL
for(int j=0;j<26;j++){
 letters[j]= NULL;
}

//Check if file could be opened
if(dic == NULL){

  printf("File not found, I repeat File not found");
  return false;

}

for(int i = 0;!feof(dic);i++){

  //new node
  node* new_node = malloc(sizeof(node));

  //get the word and store it in the node
  fscanf(dic,"%s",new_node->word);
  new_node->next = NULL; 

  //first time
  if(letters[hashy(new_node->word)]== NULL){

    letters[hashy(new_node->word)] = new_node;

  }else{

    node* crawler = malloc(sizeof(node));

    crawler = letters[hashy(new_node->word)];

    while(crawler->next != NULL){

     crawler = crawler->next;

    }

    crawler->next = new_node;
    free(crawler);

  }

}

    //TESTTTT

for(int i=0;i<26;i++){

node* ho = malloc(sizeof(node*));

ho = letters[i];

while(ho->next != NULL){

printf("ha_ha %s \n",ho->word);

ho= ho->next;

}

}

//TESTTTT


fclose(dic);

return true;

}

I'd added the test part to see if I'm loading it correctly but the while(ho->next != NULL)dosent get executed.

Improve this answer
  • check your load function, are you sure you have the final node for each linked list emanating from every letters[i] pointing to null? – ronga Oct 23 '15 at 3:35

You must log in to answer this question.

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