Linkie listies.

common.h

#ifndef __COMMON_H
#define __COMMON_H

#include <string.h>

#define TRUE 1
#define FALSE  0

typedef int Boolean;

#endif /* __COMMON_H */

HashObject.c

/*
 * HashObject.c
 *
 *  Created on: Apr 11, 2012
 *      Author: johnotander
 */


#include "HashObject.h"


//The HashObject that is pointed to by the Node in the chain. Holds key and value.
HashObjectPtr newHashObject(char *key, char *value)
{
  if(!key) return NULL;

	HashObjectPtr obj;
	if((obj = malloc(sizeof(HashObject))) == NULL)
		printf("Couldn't Allocate Memory.");
	if((obj->key = malloc(sizeof(char)*strlen(key)+1)) == NULL)
		printf("Couldn't Allocate Memory.");
	strcpy(obj->key, key);

	if(value)
	{
		obj->value = malloc(sizeof(char)*strlen(value)+1);
		strcpy(obj->value, value);
	}
	else
	{
		obj->value = NULL;
	}

	return obj;
}


void freeHashObject(HashObjectPtr obj)
{
	if(!obj) return;

	if(obj->value)
		free(obj->value);

	free(obj->key);
	free(obj);
}

HashObject.h

/*
 * HashObject.h
 *
 *  Created on: Apr 11, 2012
 *      Author: johnotander
 */


#ifndef HASHOBJECT_H_
#define HASHOBJECT_H_


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Node.h"


typedef struct hashobject HashObject;
typedef struct hashobject *HashObjectPtr;


struct hashobject{
  char *key;
	void *value;
	
	void (*f)(HashObjectPtr obj);
};


HashObjectPtr newHashObject(char *key, char *value);


void freeHashObject(HashObjectPtr obj);

#endif /* HASHOBJECT_H_ */

HashTable.c

/*
 * HashTable.c
 *
 *  Created on: Apr 11, 2012
 *      Author: johnotander
 */


#include"HashTable.h"


HashTablePtr createTable(int size) {
  HashTablePtr table;
	if((table = malloc(sizeof(HashTable))) == NULL)
		printf("Couldn't Allocate Memory.");
	if((table->buckets = malloc(sizeof(ListPtr)*size)) == NULL)
		printf("Couldn't Allocate Memory.");

	int i;
	for (i = 0; i < size; i++) {
		table->buckets[i] = createList();
	}

	table->size = size;
	table->h = hashFunction;
	table->p = printTable;

	return table;
}

//Insert a HashObject to the table.
HashTablePtr insert(HashTablePtr table, HashObjectPtr obj) {
	if (!table)
		return NULL;
	if (!obj)
		return NULL;

	int mapping;
	mapping = table->h(table, obj->key);
	if(mapping < 0 || mapping > table->size) return NULL;

	table->buckets[mapping] = addAtFront((ListPtr)(table->buckets[mapping]), createNode(obj)); //Adds HashObjectPtr to the Node which is inserted.

	return table;
}


//Bernstein Hash
unsigned int hashFunction(HashTablePtr table, char *key) {
	if (!table)
		return -1;
	if (!key)
		return -1;

	unsigned int hash = 0;

	int c;
	while((c = *key++))
		hash = ((hash << 5) + hash) ^ c;

	return(hash % table->size);
}


NodePtr searchTable(HashTablePtr table, char *key) {
	if (!table)
		return NULL;
	if (!key)
		return NULL;

	int index;
	index = (table->h)(table, key);

	if (!table->buckets[index] || isEmpty((ListPtr)(table->buckets[index])))
		return 0; //No list in bucket.
	
	NodePtr found;
	if((found = search(table->buckets[index], key)))
	{
		return found;
	}
	else
	{
		return 0;
	}
}


int printTable(HashTablePtr table)
{
	if(!table) return 0;

	int i;
	for(i = 0; i < table->size-1; i++)
	{
		if(!isEmpty(table->buckets[i]))
		{
			printf("Bucket at index %d: ", i);
			printList(table->buckets[i]);
			printf("\n");
		}
	}

	return 1;
}


void freeTable(HashTablePtr table)
{
	int i;
	for(i = 0; i < table->size; i++)
	{
		freeList((ListPtr)table->buckets[i]);
	}

	free(table->buckets);
	free(table);
}

HashTable.h

/*
 * HashTable.h
 *
 *  Created on: Apr 11, 2012
 *      Author: johnotander
 */

#ifndef HASHTABLE_H_
#define HASHTABLE_H_


#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "List.h"
#include "HashObject.h"
#include "common.h"
#include <math.h>


typedef struct hashtable HashTable;
typedef struct hashtable *HashTablePtr;


struct hashtable{
  void **buckets;

	int size;
	unsigned int (*h)(HashTablePtr table, char *key);
	int (*p)(HashTablePtr table);
	NodePtr (*s)(HashTablePtr table, char *key, void *value);
};


HashTablePtr createTable(int size);
void freeTable(HashTablePtr table);
int printTable(HashTablePtr table);

HashTablePtr insert(HashTablePtr table, HashObjectPtr obj);
unsigned int hashFunction(HashTablePtr table, char *key);
NodePtr searchTable(HashTablePtr table, char *key);


#endif /* HASHTABLE_H_ */

List.c

#include <stdio.h>
#include <stdlib.h>
#include "List.h"

/*

  list.c 
		Contains functions to manipulate a doubly-linked list.
 
*/


/* private methods */

static NodePtr reverse(NodePtr L);
static void print(NodePtr node);



ListPtr createList()
{
	ListPtr list = malloc(sizeof(List));
	list->size = 0;
	list->head = NULL;
	list->tail = NULL;

	return list;
}

void freeList(ListPtr L)
{
	NodePtr node = L->head;

	while(node)
	{
		NodePtr next = node->next;
		freeNode(node);
		node = next;
	}

	free(L);
}

int getSize(ListPtr L)
{
	return L->size;
}

Boolean isEmpty(ListPtr L)
{
	if (L->size == 0)
		return TRUE;
	else
		return FALSE;
}

ListPtr addAtFront(ListPtr list, NodePtr node)
{
	if (list == NULL) return NULL;
	if (node == NULL) return NULL;

	list->size++;
	node->prev = NULL;

	if (list->head == NULL)
	{
		list->head = node;
		list->tail = node;
	} else {
		node->next = list->head;
		list->head->prev = node;
		list->head = node;
	}

	return list;
}

//Adds a node to the rear of the list.
void addAtRear(ListPtr list, NodePtr node)
{
	if (list == NULL) return;
	if (node == NULL) return;

	//Increment the size since we're adding a node.
	list->size++;

	//In case there aren't any nodes in the list yet.
	if (list->head == NULL)
	{
		list->head = node;
		list->tail = node;
	}
	else
	{
		node->prev = list->tail;    //Set up the previous pointer.
		list->tail->next = node;    //Set up next pointer for previous node.
		list->tail = node;          //Set up tail pointer.
		list->tail->next = NULL;    //Set up the next pointer for node to be NULL.
	}
}

//Remove the node at the front of the list.
NodePtr removeFront(ListPtr list)
{
	if (list == NULL) return NULL;
	if (list->head == NULL) return NULL;

	//In case there is only one node in the list.
	if (list->size == 1)
	{
		list->size--;
		NodePtr temp = list->head;
		list->head = NULL;
		list->tail = NULL;

		return (temp);
	}
	else if(list->size == 0)
	{
		return NULL;
	}
	else
	{
		NodePtr tmp = list->head;       //Make a temp node that points to head.
		list->head = list->head->next;  //Reset the head pointer to the next node.
		list->head->prev = NULL;        //Set the previous pointer for new head to NULL.
		list->size--;                   //Decrement size since we removed a node.

		return(tmp);
	}
}

NodePtr removeRear(ListPtr list)
{
	if (list == NULL) return NULL;
	if (list->head == NULL) return NULL;

	//In case there is only one node in the list.
	if (list->size == 1)
	{
		list->size--;
		NodePtr temp = list->head;
		list->head = NULL;
		list->tail = NULL;

		return (temp);
	}
	else if (list->size == 0)
	{
		return NULL;
	}
	else
	{
		NodePtr tmp = list->tail;          //Make a temp node that points to the tail.
		list->tail = list->tail->prev;     //Make the tail pointer go to the previous node.
		list->tail->next = NULL;           //Make the next pointer for new tail NULL.
		list->size--;                      //Decrement the size since we removed a node.

		return(tmp);
	}
}

NodePtr removeNode(ListPtr list, NodePtr node)
{
	if (list == NULL) return NULL;
	if (node == NULL) return NULL;


	if (list->size == 0)
	{
		return NULL;
	}
	else if ( (list->head) == node)   //In case the node to be removed is the head.
	{
		return removeRear(list);
	}
	else if ( (list->tail) == node)    //In case the node to be removed is the tail.
	{
		return removeFront(list);
	}
	else
	{
		node->prev->next = node->next; //Reroute the next pointer around removed node.
		node->next->prev = node->prev; //Reroute the prev pointer around removed node.
		list->size--;
		return node;
	}
}

NodePtr search(ListPtr list, char* key)
{
	if (list == NULL) return NULL;

	NodePtr tmp = list->head;           //Make a temp node to start search at head.

	while(tmp)
	{
		if( ((HashObjectPtr) (tmp->data))->key == key)     //See if there is a match, casted as HashObjectPtr.
		{
			return tmp;                 //Match.
		}
		else
		{
			if (tmp->next)               //Make sure the next node exists.
				tmp = tmp->next;         //Move on to the next node for search.
			else
				return NULL;
		}
	}

	return NULL;                         //No match.
}

void reverseList(ListPtr L)
{
	if (L == NULL) return;
	L->tail = L->head;
	L->head  = reverse (L->head);
}

static NodePtr reverse(NodePtr L)
{
	NodePtr list = NULL;
	while (L != NULL) {
		NodePtr tmp = L;
		L = L->next;
		if (L != NULL) L->prev = tmp;
		tmp->next = list;
		tmp->prev = L;
		list = tmp;
	}
	return list;
}

void printList(ListPtr L)
{
	if (L) print(L->head);
}

static void print(NodePtr node)
{
	int count = 0;
	char *output;

	while (node) {
		output = ((HashObjectPtr)(node->data))->key;
		printf(" %s ||", output);

		if((output = ((HashObjectPtr)(node->data))->value))
			printf(" %s -->", output);

		node = node->next;
		count++;
		if ((count % 6) == 0)
			printf("\n");
	}
    printf(" NULL \n");
}

List.h

/*
  List.h: Defines the interface for a doubly-linked list.
*/

#ifndef __LIST_H
#define __LIST_H

#include <stdio.h>
#include <stdlib.h>
#include "common.h"
#include "Node.h"
#include "HashTable.h"

typedef struct list List;
typedef struct list * ListPtr;

struct list {
	int size;
	NodePtr head;
	NodePtr tail;
};

/* prototypes of public methods */

ListPtr createList(); /* constructor */
void freeList(ListPtr L); /* destructor */

int getSize(ListPtr L);

Boolean isEmpty(ListPtr L);

ListPtr addAtFront(ListPtr list, NodePtr node);
void addAtRear(ListPtr list, NodePtr node);

NodePtr removeFront(ListPtr list);
NodePtr removeRear(ListPtr list);
NodePtr removeNode(ListPtr list, NodePtr node);

NodePtr search(ListPtr list, char *key);

void reverseList(ListPtr  L);

void printList(ListPtr L);


#endif /* __LIST_H */ 

Node.c

#include "Node.h"


NodePtr createNode(void *data)
{
  NodePtr newNode = malloc(sizeof(Node));
	newNode->next = NULL;
	newNode->prev = NULL;
	newNode->data = data;
	return newNode;
}


void freeNode (NodePtr node)
{
	if (node == NULL) return;
	freeHashObject(node->data);

	free(node);
}

Node.h

#ifndef __NODE_H
#define __NODE_H

#include <stdio.h>
#include <stdlib.h>
#include "common.h"
#include "HashObject.h"

typedef struct node Node;
typedef struct node * NodePtr;

struct node {
  void *data;
	NodePtr next;
	NodePtr prev;
};

NodePtr createNode (void *data);
void freeNode(NodePtr node);


#endif /* __NODE_H */