Insert function hash table C

Question

I am having trouble implementing my insert function for my hash table.

So I implement some test calls where I just call the function separately. For actual use, I call the function inside a while loop. For testing purpose, I only run the loop 4 times.

I post some outputs below. The reason the table looks weird is because of my hash function. It hashes the words such that A = 1, B = 2, C = 3, and so on. The position of the letter in the word is irrelevant, since I will consider permutations of the word. Moreover, the case of the letter will be irrelevant in this problem as well, so the value of a = the value of A = 1.

And for strings, abc = 1 + 2 + 3 = 6, bc = 2 + 3 = 5, etc.

Overall, the hash function is fine. The problem is the insert function.

The first 4 words of my local dictionary are A, A's, AA's, AB's.

My expected output should be (I got the same output when I run the test calls):

0: 
1: [W: A, Len:1] 
2: 
3: 
...
18: 
19: 
20: [W: A's, Len:3] 
21: [W: AA's, Len:4] 
22: [W: AB's, Len:4]

But when I call the function inside a loop, whatever is last on the list will overwrite other entries. If I run the loop 100 times, then the last entry still replaces the previous ones (Notice how the lengths of the words are unchanged, but only the words are replaced):

0: 
1: [W: AB's, L:1] 
2: 
3: 
...
18: 
19: 
20: [W: AB's, Len:3] 
21: [W: AB's, Len:4] 
22: [W: AB's, Len:4] 

Below is my code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int hash(char *word)
{
   int h = 0;

   while(*word != '\0')
   {
      if(*word >='A' && *word < 'A'+26) {
         h=h+(*word -'A' + 1);
      }
      else if(*word >='a' && *word < 'a'+26) {
         h=h+(*word -'a' + 1);
      }
      //else { // special characters
      // return -1;  
      //}

      word++;
   }

   return h;
}

typedef struct Entry {
   char *word;
   int len;
   struct Entry *next;
} Entry;

#define TABLE_SIZE 1000 // random numbers for testing

Entry *table[TABLE_SIZE] = { NULL }; // an array of elements

void init() {
   int i;

   for (i = 0; i < TABLE_SIZE; i++) {
      // initialize values
      struct Entry *en = (struct Entry *)malloc(sizeof(struct Entry));

      en->word = "";
      en->len = 0;
      en->next = table[i];
      table[i] = en;
   }
}

//Insert element
void insertElement(char *word, int len) {
   int h = hash(word);
   int i;

   // because all words are different so there is no need to check for duplicates
   struct Entry *en = (struct Entry *)malloc(sizeof(struct Entry));

   en->word = word;
   en->len = len;
   en->next = table[h];
   table[h] = en;
}

void cleanTable()
{
   struct Entry *p, *q;
   int i;

   for( i=0; i<TABLE_SIZE; ++i )
   {
      for( p=table[i]; p!=NULL; p=q )
      {
         q = p->next;
         free( p );
      }
   }  // for each entry
}

int main() {
   init(); // create hash table

   // test calls produce correct output
   //insertElement("A", (int)strlen("A"));
   //insertElement("A's", (int)strlen("A's"));
   //insertElement("AA's", (int)strlen("AA's"));
   //insertElement("AB's", (int)strlen("AB's"));

   int i;
   i = 0;

   FILE* dict = fopen("/usr/share/dict/words", "r"); //open the dictionary for read-only access 
   if(dict == NULL) {   
      return;                    
   }

   // Read each line of the file, and insert the word in hash table
   char word[128];      
   while(i < 4 && fgets(word, sizeof(word), dict) != NULL) {
      size_t len = strlen(word); 
      if (len > 0 &&  word[len - 1] == '\n') {
         word[len - 1] = '\0'; // trim the \n
      }

      insertElement(word, (int)strlen(word));

      i++;
   }

   for ( i=0; i < 50; i++)
   {
      printf("%d: ", i);

      struct Entry *enTemp = table[i];

      while (enTemp->next != NULL)
      {
         printf("[W: %s, Len:%d] ", enTemp->word, enTemp->len);
         enTemp = enTemp->next;
      }

      printf("\n");
   }

   cleanTable();

   return 0;
}

Answer 1

notice that your insertElement get a pointer to a string, and assign that pointer to the current Entry, but its the main function, you pass the word argument(a pointer) that point the stack allocated string, and that string is changed after each read of a word. you must use malloc so that each word point to its own memory area

Answer 2

Try to reallocate the memory in each loop in this part of code:

char* word = malloc(sizeof(char)*128);      
while(i < 4 && fgets(word, sizeof(word), dict) != NULL) {
    size_t len = strlen(word); 
    if (len > 0 &&  word[len - 1] == '\n') {
        word[len - 1] = '\0'; // trim the \n
    }
    insertElement(word, (int)strlen(word));
    word = malloc(sizeof(char)*128);
    i++;
}

You forgot to reallocate memory to every string which causes all pointers points at same point

Note: Not tested