Friday, December 4, 2009

A simple hash implementation in C

#include
#include

struct node{
int key;
char *value;
struct node* next;
};

struct node* hash[5];

char* m_strdup(char* tmp)
{
int len = strlen(tmp);
char* newmem = malloc(sizeof(char)*len);
if(!newmem)
{
fprintf(stderr,"problem in memory allocation");
exit(0);
}
strcpy(newmem,tmp);
return newmem;
}

void traverse(struct node* root)
{
printf("traversing\n");
while(root)
{
printf("%s",root->value);
root = root->next;
}
printf("\n");
}
void addnew(int value)
{
int key = value%5;
char tmp[10];
int counter = 0;
tmp[0] = 'a' + value;
tmp[1] = 0;
struct node* curr;
if(!hash[key])
{
hash[key] = malloc(sizeof(struct node));
hash[key]->value = m_strdup(tmp);
hash[key]->next = NULL;
printf("added at %d - %d\n",key,counter);
}
else
{
curr = hash[key];
while(hash[key]->next)
{
hash[key] = hash[key]->next;
counter++;
}
hash[key]->next = malloc(sizeof(struct node));
hash[key]->next->value = m_strdup(tmp);
hash[key]->next->next = NULL;
hash[key] = curr;
printf("added at %d - %d\n",key,counter);
}
}

void lookup(int value)
{
int key = value%5;
int counter = 0;
char tmp[10];
tmp[0] = 'a' + value;
tmp[1] = 0;
struct node* curr = hash[key];
while(curr)
{
if(strcmp(curr->value,tmp)==0)
{
printf("found at %d - %d\n",key,counter);
break;
}
curr = curr->next;
counter++;
}
//hash[key] = curr;
}

int main()
{
int i;
for (i=0;i<5;i++)
hash[i] = NULL;
addnew(1);
addnew(2);
addnew(22);
addnew(12);
addnew(3);
addnew(13);
traverse(hash[3]);
lookup(1);
lookup(2);
lookup(3);
lookup(22);
lookup(12);
lookup(13);
}

No comments:

Blog Archive