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