Code:
/*This hash table resizes the table once the size exceeds # of buckets */
#include <stdio.h>
#define INITNUMBUCKETS 5
#define LINKBLOCKSIZE 16
#define RESIZERATIO 1
#define NOMATCH -1
#define DEBUG 1
typedef struct Link {
int Key;
int Value;
struct Link *Next;
} Link;
typedef struct {
Link **Buckets;
int NumBuckets;
Link *FreeLinks;
int Size;
} HashTable;
int main(int argc, char *argv[]) {
HashTable HT;
FILE *FP;
int NumVals, Key, Value;
void Initialize_Hash_Table(HashTable *HT);
void Insert(HashTable *HT, int Key, int Value);
int Lookup(HashTable *HT, int Key);
void Remove(HashTable *HT, int Key);
void Print_Hash_Table(HashTable *HT);
if (argc != 2) {
printf("usage: %s valuefile\n", argv[0]);
exit(1);
}
FP = fopen(argv[1], "r");
if (FP == NULL) {
printf("%s could not be opened; check the filename\n", argv[1]);
exit(1);
} else {
Initialize_Hash_Table(&HT);
do {
NumVals = fscanf(FP, "%d %d\n", &Key, &Value);
if (NumVals == 2) {
if (Key < 0) {
printf("Remove(%d)\n", -Key);
Remove(&HT, -Key);
} else if (Value == -1) {
Value = Lookup(&HT, Key);
printf("%d = Lookup(%d)\n", Value, Key);
} else {
printf("Insert(%d, %d)\n", Key, Value);
Insert(&HT, Key, Value);
}
if (DEBUG)
Print_Hash_Table(&HT);
}
} while (NumVals == 2);
Print_Hash_Table(&HT);
fclose(FP);
exit(0);
}
}
/* Hash: This routine transforms the key into a bucket number. */
int Hash(HashTable *HT, int Key) {
return Key % HT->NumBuckets;
}
/* Initialize Hash Table: This routine initializes a new hash table
object. Buckets are allocated and cleared; the Freelist is
initialized, and the size is zeroed. */
void Initialize_Hash_Table(HashTable *HT) {
int Index;
void *malloc(unsigned int);
HT->NumBuckets = INITNUMBUCKETS;
HT->Buckets = (Link **) malloc(HT->NumBuckets * sizeof(Link *));
if (HT->Buckets == NULL) {
printf("Out of heap memory\n");
exit(1);
}
for (Index = 0; Index < HT->NumBuckets; Index++)
HT->Buckets[Index] = NULL;
HT->FreeLinks = NULL;
HT->Size = 0;
}
/* Make New Links: This routine allocates, initializes, and returns a
new block of link objects. */
Link *Make_New_Links() {
Link *NewLinks;
int Index;
void *malloc(unsigned int);
void Print_Next_Link(Link *Next);
if (DEBUG)
printf(" making more links\n");
NewLinks = (Link *) malloc(LINKBLOCKSIZE * sizeof(Link));
if (NewLinks == NULL) {
printf("Out of heap memory\n");
exit(1);
}
for (Index = 0; Index < LINKBLOCKSIZE; Index++) {
NewLinks[Index].Key = -1;
NewLinks[Index].Value = -1;
if (Index == LINKBLOCKSIZE - 1)
NewLinks[Index].Next = NULL;
else
NewLinks[Index].Next = &(NewLinks[Index + 1]);
}
if (DEBUG) {
printf(" free list\n");
Print_Next_Link(NewLinks);
}
return NewLinks;
}
/* Print Hash Table: This routine prints the size and contents of a
hash table object. */
void Print_Hash_Table(HashTable *HT) {
int Index;
void Print_Next_Link(Link *Next);
if (DEBUG)
printf(" [HashTable %u, size = %d]\n", HT, HT->Size);
else
printf(" [HashTable size = %d]\n", HT->Size);
for (Index = 0; Index < HT->NumBuckets; Index++) {
if (DEBUG)
printf(" bucket %d\n", Index);
Print_Next_Link(HT->Buckets[Index]);
}
}
/* Print Next Link: This recursive routine prints the next non-NULL
link entry including its key and value. */
void Print_Next_Link(Link *NextLink) {
if (NextLink != NULL) {
if (DEBUG)
printf(" <%u: %5d, %3d, %u>\n", NextLink, NextLink->Key, NextLink->Value, NextLink->Next);
else
printf(" <%5d:%5d>\n", NextLink->Key, NextLink->Value);
Print_Next_Link(NextLink->Next);
}
}
/* Insert: This routine inserts a key value pair in the hash table.
If the key already exists, the value is updated. Otherwise a new link
is allocated, initlized, and added to the appropriate bucket list. */
void Insert(HashTable *HT, int Key, int Value) {
Link *FoundLink;
Link *Find_Key(HashTable *HT, int Key);
Link *Make_New_Links();
int Hash(HashTable *HT, int Key);
void Resize_Hash_Table(HashTable *HT);
FoundLink = Find_Key(HT, Key);
if (FoundLink == NULL) {
if (HT->FreeLinks == NULL)
HT->FreeLinks = Make_New_Links();
FoundLink = HT->FreeLinks;
HT->FreeLinks = HT->FreeLinks->Next;
FoundLink->Key = Key;
FoundLink->Value = Value;
FoundLink->Next = HT->Buckets[Hash(HT, Key)];
HT->Buckets[Hash(HT, Key)] = FoundLink;
HT->Size += 1;
if (HT->Size > HT->NumBuckets * RESIZERATIO)
Resize_Hash_Table(HT);
} else
FoundLink->Value = Value;
}
/* Lookup: This routine attempts to locate a key in the hash table. If
the key is located, the value is returned, otherwise NOMATCH is
returned. A interal function performs the search returning the
matching link if the key si found or NULL if it is not found. */
int Lookup(HashTable *HT, int Key) {
Link *FoundLink;
Link *Find_Key(HashTable *HT, int Key);
FoundLink = Find_Key(HT, Key);
if (FoundLink == NULL)
return -1;
else
return FoundLink->Value;
}
/* Remove: This routine removes a key value pair from the hash table.
It pushes the removed link back on the FreeLinks list for later reuse. */
void Remove(HashTable *HT, int Key) {
int Index;
Link *ThisLink;
Link **TrailingPointer;
int Hash(HashTable *HT, int Key);
void Print_Next_Link(Link *Next);
Index = Hash(HT, Key);
ThisLink = HT->Buckets[Index];
TrailingPointer = &(HT->Buckets[Index]);
while(ThisLink != NULL && ThisLink->Key != Key) {
TrailingPointer = &(ThisLink->Next);
ThisLink = ThisLink->Next;
}
if (ThisLink != NULL) {
*TrailingPointer = ThisLink->Next;
ThisLink->Next = HT->FreeLinks;
HT->FreeLinks = ThisLink;
HT->Size -= 1;
if (DEBUG) {
printf(" free list\n");
Print_Next_Link(HT->FreeLinks);
}
}
}
/* Find_Key: This internal routine performs a hash table lookup,
returning the located link is the key exists in the hash table, or
NULL if it does not. */
Link *Find_Key(HashTable *HT, int Key) {
Link *ThisLink;
int Index;
int Hash(HashTable *HT, int Key);
Index = Hash(HT, Key);
ThisLink = HT->Buckets[Index];
while(ThisLink != NULL && ThisLink->Key != Key)
ThisLink = ThisLink->Next;
return ThisLink;
}
void Resize_Hash_Table(HashTable *HT){
//Initialize new HT
//printf("DOING THE RESIZE HASH TABLE \n"); /////////////////////REMOVE
int Index;
void *malloc(unsigned int);
HashTable HT2;
int ind, num;
Link *current=NULL, *temp=NULL;
void insertCustom(HashTable *HT, int Key, int Value);
void Custom_Print_Hash_Table(HashTable *HT);
HT2.NumBuckets = 2*(HT->NumBuckets)+1;
HT2.Buckets = (Link **) malloc(HT->NumBuckets * sizeof(Link *));
if (HT2.Buckets == NULL) {
printf("Out of heap memory\n");
exit(1);
}
for (Index = 0; Index < HT2.NumBuckets; Index++)
HT2.Buckets[Index] = NULL;
HT2.FreeLinks = NULL;
HT2.Size = 0;
//end Initialize new HT
//Begin copy old contents to new contents
ind=1;
num=0;
while(num<HT->NumBuckets){
current=HT->Buckets[num];
if(current==NULL){
num++; //If the rest of the bucket is empty, goto next bucket
}
else{
while(current!=NULL){//Else, iterate through the bucket and insert
insertCustom(&HT2, current->Key, current->Value);
temp=current->Next;
free(current);
current=temp; //Next item in the bucket
}
num++;
}
ind++;
}
*HT=HT2;
}
void insertCustom(HashTable *HT, int Key, int Value) {
HT->Size =HT->Size + 1;
if(HT->FreeLinks==0){ //If no free links
Link *Make_New_Links();
Link *freed=Make_New_Links();
HT->FreeLinks=freed->Next;
freed->Key=Key;
freed->Value=Value;
freed->Next=HT->Buckets[Hash(HT, Key)];
HT->Buckets[Hash(HT, Key)]=freed;
}
else{ //If free links exist
Link *current=HT->FreeLinks;
current->Key=Key;
current->Value=Value;
HT->FreeLinks=current->Next;
current->Next=HT->Buckets[Hash(HT, Key)];
HT->Buckets[Hash(HT, Key)]=current;
}
}
void Custom_Print_Hash_Table(HashTable *HT) { /////////////////////REMOVE
int Index;
void Print_Next_Link(Link *Next);
printf(" [HashTable %u, size = %d]\n", HT, HT->Size);
for (Index = 0; Index < HT->NumBuckets; Index++) {
printf(" bucket %d\n", Index);
Print_Next_Link(HT->Buckets[Index]);
}
}