I've implemented the following code for queues as a linked list. Now I'm trying to get an hashtable as an array of queues as a linked list. It works fine until I do insertion after deletion.
What is being done is a queue is implemented as linked list. So when I want to remove, I delete the head element and for insert I use tail.
To do an hashtable I maintain another linked list of keys in the order in which they were inserted. Deletion starts with first removing this key and going to that individual linked list and removing the head and updating the head.
#include<stdio.h>
#include<stdlib.h>
struct Node{
int value;
struct Node *next;
struct Node* head;
struct Node* tail;
};
struct Node* lruhashtable[10];
struct Node* trackHead;
struct Node* trackTail;
void insert(int page)
{
if(trackHead==NULL)
{
trackHead=malloc(sizeof(struct Node));
trackHead->value=(page-1)%10;
trackHead->next=NULL;
trackTail=trackHead;
}
else
{
struct Node* temp=malloc(sizeof(struct Node));
temp->value=(page-1)%10;
temp->next=NULL;
trackTail->next=temp;
trackTail=temp;
}
}
void hashEntry(int page)
{
struct Node** iter;
iter=&lruhashtable[(page-1)%10];
for(;*iter;iter=&(*iter)->next);
*iter = malloc(sizeof **iter );
(*iter)->value = page;
(*iter)->next = NULL;
if((*iter)->head==NULL)
{
(*iter)->head=*iter;
(*iter)->tail= (*iter)->head;
}
else
{
(*iter)->tail->next=*iter;
(*iter)->tail=*iter;
}
insert(page);
}
void deleteInHashEntry()
{
int pageToDelete=delete();
struct Node** iter;
iter=&lruhashtable[pageToDelete];
if((*iter)->head!=NULL)
{
struct Node* curr=(*iter)->head;
(*iter)=curr->next;
if((*iter)!=NULL)
(*iter)->head=*iter;
free(curr);
}
else
{
(*iter)->tail=NULL;
}
}
void print()
{
int i;
struct Node **iter;
for(i=0;i<10;i++)
{
iter=&lruhashtable[i];
for(;*iter;iter=&(*iter)->next)
{
printf("%d%s%d\n",(*iter)->value,"--",i);
}
}
}
int delete()
{
int page=-1;
if(trackHead!=NULL)
{
struct Node*current=trackHead;
page=current->value;
trackHead=current->next;
free(current);
}
else
{
trackTail=NULL;
}
return page;
}
void printTrack()
{
struct Node* temp=trackHead;
while(temp!=NULL)
{
printf("%d",temp->value);
printf("\n");
temp=temp->next;
}
}
int main()
{
hashEntry(1);
hashEntry(11);
hashEntry(2);
hashEntry(3);
hashEntry(22);
hashEntry(4);
hashEntry(33);
print();
printTrack();
deleteInHashEntry();
print();
printTrack();
deleteInHashEntry();
print();
printTrack();
deleteInHashEntry();
print();
printTrack();
hashEntry(1);
hashEntry(11);
hashEntry(22);
deleteInHashEntry();
deleteInHashEntry();
deleteInHashEntry();
deleteInHashEntry();
deleteInHashEntry();
deleteInHashEntry();
deleteInHashEntry();
return 0;
}