Not sure on hash table memory allocations

I'm trying to work on a program that inputs entries from a file and then builds a hash table. I'm a little new to programming so I know I do not have the best form. I only submitted the code that I think might be the problem...

This code compiles but then has runtime errors and every time I look to see if the current hash table index is NULL it has a large number like a memory address. If anyone could give me some advice on what I might be doing wrong with the add and search functions that would be so nice... :)

PHP Code:

---

[CODE]


struct  ht_entry {                             /* an entry (node) in hash table */
     char    ht_name[NAME_LENGTH + 1];         /* name in hash table */
     int     ref_count;                        /* number of references to the name */
     struct  ht_entry  *next;
};


struct  ht_entry  *hash_tbl[BKT_SIZE];         /* bucket directory (hash index) */


int search(char *name_ptr, int *ind_ptr)       /* name to be searched , hash index (index into the hash table) */
{
   struct ht_entry *tmp;                       /* declare tmp */
   tmp = malloc(sizeof(*tmp));                 /* allocate memory for tmp */
   tmp=hash_tbl[*ind_ptr];                     /* sets to the head of hash_tbl */
   
   printf("SEARCH ");
   
   while(tmp!=NULL)                            /* while tmp is not NULL */
   {  
      if((strcmp(tmp->ht_name, name_ptr))==0)  /* if hash_tbl name is equal to current name return true (FOUND) */
      {
          return TRUE;
      }

      tmp=tmp->next;    
   }   

   return FALSE;                               /* else return false (NOT FOUND) */

}/* end of search */


void add(char *name_ptr,int *ind_ptr)          /* (pointer to name, pointer to hash index)  THIS ADDS NODE TO HASH TABLE */
{
    struct ht_entry *head;                                 /* declare head */
    head = malloc(sizeof(*head));                          /* allocate memory for head */
    
    if(hash_tbl[*ind_ptr]==NULL)                           /* if hash_tbl[index] is NULL initialize a new node for index */
    {
       hash_tbl[*ind_ptr] = malloc(sizeof(*hash_tbl));     /* allocate memory for hash_tbl[hash_index] if it's NULL */ 
       strcpy(hash_tbl[*ind_ptr]->ht_name, name_ptr);
       hash_tbl[*ind_ptr]->ref_count=0;
       printf("It was NULL."  );
    }
    else                                                   /* else initialize head then link to hash_tbl[index] */
    {
       strcpy(head->ht_name, name_ptr);
       head->ref_count=0;
       head->next=hash_tbl[*ind_ptr];
       hash_tbl[*ind_ptr]=head;
       printf("It wasn't NULL.  ");
    }    

    printf("It's been added!\n");

}//end add

/*

Sample Input:
   DEF  GONE
   DEF  KMN127
   DEF  EGG
   DEF  VAN
   DEF  AKK
   DEF  EGG
   USE  VAN
   USE  AKK
   USE  JEEP
   USE  AKK
   DEF  FUN
   DEF  ALI
   USE  KMN127
   
Sample Output:
     Input Data
   Command   Name
   DEF       GONE
   DEF       KMN127
   DEF       EGG
   DEF       VAN
   DEF       AKK
   DEF       EGG          *** Duplicate Name ***
   USE       VAN
   USE       AKK
   USE       JEEP         *** Undefined Name ***
   USE       AKK
   DEF       FUN
   DEF       ALI
   USE       KMN127
   
*/

[/CODE] 


---

Quote:

---

Originally Posted by Thumper333

Code:

---

void add(char *name_ptr,int *ind_ptr)          /* (pointer to name, pointer to hash index)  THIS ADDS NODE TO HASH TABLE */
{
    struct ht_entry *head;                                /* declare head */
    head = malloc(sizeof(*head));                          /* allocate memory for head */
   
    if(hash_tbl[*ind_ptr]==NULL)                          /* if hash_tbl[index] is NULL initialize a new node for index */
    {
//ERROR HERE
      hash_tbl[*ind_ptr] = malloc(sizeof(*hash_tbl));    /* allocate memory for hash_tbl[hash_index] if it's NULL */
      strcpy(hash_tbl[*ind_ptr]->ht_name, name_ptr);
      hash_tbl[*ind_ptr]->ref_count=0;
      printf("It was NULL."  );
    }
    else                                                  /* else initialize head then link to hash_tbl[index] */
    {
/*....................*/
    }   

/*....................*/

}//end add

---

---

The problem is simple. When struct ht_entry *next is NULL you allocate memory to the pointer and initiate the variables. Then you must assign NULL the the next pointer in the allocated struct, or instead use calloc at stdlib to alocate memory initialized automaticly with zeros.
Plus shouldn't this be

Code:

---

hash_tbl[*ind_ptr] = malloc(sizeof(*ht_entry));

---

instead of

Code:

---

hash_tbl[*ind_ptr] = malloc(sizeof(*hash_tbl));

---

I think it should, Otherwize you're allocating a diferent amount of memory rather than the one needed. In this case BKT_SIZE*4 bytes.
So...

Code:

---

  if(hash_tbl[*ind_ptr]==NULL)                          /* if hash_tbl[index] is NULL initialize a new node for index */
    {
      hash_tbl[*ind_ptr] = malloc(sizeof(*ht_entry));//<-- HERE's the fix
      strcpy(hash_tbl[*ind_ptr]->ht_name, name_ptr);
      hash_tbl[*ind_ptr]->ref_count=0;
      hash_tbl[*ind_ptr]->next=NULL;//<-- HERE's the fix
      printf("It was NULL."  );
    }

---

Those big number you see are random values from the allocated memory, therefore invalid pointers.

Hope this helps. Cheers!

>struct ht_entry *tmp; /* declare tmp */
Wow, what a waste of a comment. Please don't comment code that is obvious to anyone remotely familiar with C, it clutters the code.

>tmp = malloc(sizeof(*tmp)); /* allocate memory for tmp */
Okay, and there's another redundant comment.

>tmp=hash_tbl[*ind_ptr];
Not okay, you just caused a memory leak because tmp was the only reference to the memory you just allocated.

>while(tmp!=NULL) /* while tmp is not NULL */
Good thing you had a comment there to tell me exactly what kind of loop you were using and what the condition is.

>void add(char *name_ptr,int *ind_ptr)
This is a sweeping comment for both search and add. Why is ind_ptr a pointer? It doesn't buy you anything except added complexity.

>hash_tbl[*ind_ptr] = malloc(sizeof(*hash_tbl));
Good idea, bad execution. You already have a entry allocated with head, why not just use that?

Try this instead:

Code:

---

struct  ht_entry {                          /* an entry (node) in hash table */
  char    ht_name[NAME_LENGTH + 1];        /* name in hash table */
  int    ref_count;                        /* number of references to the name */
  struct  ht_entry  *next;                  /* next entry with the same hash index */
};

struct  ht_entry  *hash_tbl[BKT_SIZE];      /* bucket directory (hash index) */

int search(char *name_ptr, int ind)
{
  struct ht_entry *tmp = hash_tbl[ind];

  printf("SEARCH ");

  while(tmp!=NULL)
  { 
    if((strcmp(tmp->ht_name, name_ptr))==0)
    {
      return TRUE;
    }

    tmp=tmp->next;   
  }   

  return FALSE;
}

void add(char *name_ptr,int ind)
{
  struct ht_entry *head = malloc(sizeof(*head));

  if(hash_tbl[ind]==NULL)
  {
    strcpy(head->ht_name, name_ptr);
    head->ref_count=0;
    head->next=hash_tbl[ind];
    hash_tbl[ind]=head;
    printf("It was NULL.");
  }
  else
  {
    strcpy(head->ht_name, name_ptr);
    head->ref_count=0;
    head->next=hash_tbl[ind];
    hash_tbl[ind]=head;
    printf("It wasn't NULL.  ");
  }   

  printf("It's been added!\n");
}

---

But, because you'll notice that both the null and not null casees in add are exactly the same, you can combine them:

Code:

---

void add(char *name_ptr,int ind)
{
  struct ht_entry *head = malloc(sizeof(*head));

  if(hash_tbl[ind]==NULL)
  {
    printf("It was NULL.");
  }
  else
  {
    printf("It wasn't NULL.  ");
  }

  strcpy(head->ht_name, name_ptr);
  head->ref_count=0;
  head->next=hash_tbl[ind];
  hash_tbl[ind]=head;

  printf("It's been added!\n");
}

---

Now we can test these functions with a simple driver:

Code:

---

int hash(char *s)
{
  int h;

  for(h=0; *s!='\0'; s++)
  {
    h=*s+31*h;
  }

  return h%BKT_SIZE;
}

int main(void)
{
  char buffer[20];
  struct ht_entry *p;
  int i;

  while(scanf("%19s", buffer)==1)
  {
    if(search(buffer, hash(buffer))==FALSE)
    {
      add(buffer, hash(buffer));
    }
    else
    {
      p=hash_tbl[hash(buffer)];

      while(strcmp(p->ht_name, buffer)!=0)
      {
        p=p->next;
      }

      p->ref_count++;
    }
  }

  for(i=0; i<BKT_SIZE; i++)
  {
    for(p=hash_tbl[i]; p!=NULL; p=p->next)
    {
      printf("%s(%d)->", p->ht_name, p->ref_count);
    }
    printf("\n");
  }

  return 0;
}

---

Thank you both! You two have solved my problems... well at least the current problems. I've also learned a good amount. Thanks a lot!