Code:
#include <stdlib.h>
#include <stdio.h>
#include <sys/stat.h>
#include "hashtable.h"
typedef struct H* HashTable;
HashTable createHashTable(unsigned int capacity);
void addItem(HashTable table, int item, int value);
int containsItem(HashTable table, int item);
void destroyHashTable(HashTable table);
struct Node;
typedef struct Node* Link;
struct Node {
int item;
int value;
Link next;
};
struct H {
Link* data;
unsigned int capacity;
unsigned int bytes;
};
/*
* Allocates a new node to hold the given initial values, and
* returns a pointer to that node. Returns NULL if the node
* could not be allocated.
*/
Link newNode(int item, int value, Link next, HashTable table) {
printf("New node Address of table %d, bytes %d\n", table, table->bytes);
table = realloc(table, table->bytes + sizeof(struct Node));
int address = table;
Link result = address + table->bytes; //calloc(1, sizeof(struct Node));
int rel_address = table->bytes;
printf("New node Address of link %d, bytes %d\n", result, table->bytes);
printf("Relative adddress %d of item %d should make an address of %d\n", rel_address, item, address + rel_address);
table->bytes = table->bytes + sizeof(struct Node);
if (result == NULL) {
printf("Realloc failed\n");
return NULL;
}
result->item = item;
result->value = value;
printf("Address of next %d\n", next);
result->next = next;
return rel_address;
}
/*
* Creates a hashtable with the given capacity and hash function.
* Returns a pointer to the newly created table, or NULL if the
* table could not be created.
*/
HashTable createHashTable(unsigned int capacity) {
HashTable table = (HashTable)calloc(1, sizeof(struct H));
table->bytes = sizeof(struct H);
printf("Address of table %d, bytes %d\n", table, table->bytes);
if (table == NULL) return NULL;
table = (Link*)realloc(table, table->bytes + (sizeof(void *) * capacity));
printf("Address of table after realloc %d, bytes %d\n", table, table->bytes);
int address = table;
printf("Predicted Address of table->data %d\n", address + table->bytes);
table->data = address + table->bytes;
printf("Address of table->data %d\n", table->data);
table->bytes = table->bytes + (sizeof(void *) * capacity);
if (table->data == NULL) return NULL;
table->capacity = capacity;
return table;
}
/*
* Adds the given item to the table, unless the item is already in
* the table, in which case it does nothing.
*/
void addItem(HashTable table, int item, int value) {
printf("Ok\n");
/* Which bucket does the item hash to? */
int index = item % table->capacity;
/* Search the linked list - if already there, bail! */
int rel_address = table->data[index];
int address = table;
printf("Table Address %d, Rel Address %d\n", address, rel_address);
Link p = address + rel_address;
int pnexta = rel_address;
printf("Address of p->next %d\n", pnexta + address);
while (pnexta != NULL) {
printf("Testing Rel address %d\n", pnexta);
p = pnexta + address;
printf("%d == %d\n", p->item, item);
if (p->item == item) {
printf("Already in index\n");
return;
}
pnexta = p->next;
}
/* Didn't find it in the list - add it! */
printf("Inserting %d into index\n", index);
table->data[index] = newNode(item, value, table->data[index], table);
}
/*
* Returns 1 (true) if item is in table, otherwise returns 0 (false).
*/
int containsItem(HashTable table, int item) {
/* Which bucket does the item hash to? */
int index = item % table->capacity;
int rel_address = table->data[index];
printf("Relative address of lookup = %d\n", rel_address);
int address = table;
Link p = address + rel_address;
printf("Real address of lookup = %d\n", p);
/* Search the linked list */
int pnexta = rel_address;
printf("Address of p->next %d\n", pnexta + address);
while (pnexta != NULL) {
printf("Testing Rel address %d\n", pnexta);
p = pnexta + address;
printf("%d == %d\n", p->item, item);
if (p->item == item) {
printf("Returning value %d\n", p->value);
return p->value;
}
pnexta = p->next;
}
/* Didn't find it in the list */
return 0;
}
/*
* Cleans up any memory allocated when we created the hashtable.
*/
void destroyHashTable(HashTable table) {
free(table);
}
int main () {
HashTable table = createHashTable(100);
addItem(table, 560, 34);
addItem(table, 660, 12);
// addItem(table, 570);
// addItem(table, 550023);
int bytes_to_read = table->bytes; //Cheat, should read table first to get the number of
// bytes then read the rest, but i can't be bothered at the moment
FILE * stream = NULL;
if ((stream = fopen("./test", "wb+")) == NULL) {
printf("Could not open file for writing\n");
exit(1);
} else {
fwrite(table, table->bytes, 1, stream);
fclose(stream);
}
destroyHashTable(table);
/* Test reading it back */
stream = NULL;
if ((stream = fopen("./test", "rb+")) == NULL) {
printf("Could not open file for reading\n");
exit(1);
} else {
HashTable new_table = malloc(bytes_to_read);
fread(new_table, bytes_to_read, 1, stream);
/*test search */
int value = 0;
if ((value = containsItem(new_table, 560)) != NULL) {
printf("%d found\n", value);
} else {
printf("not found\n");
}
fclose(stream);
}
}
Originally Posted by zootreeves
