#include "hash.h"

//Hilfsfunktionen zur Berechnung von Primzahlen
unsigned int isPrime(unsigned int n) {
	int t;
	
	if (n < 2) {
		return 0;
	}
	if (n == 2) {
		return 1;
	}
	if (n % 2 == 0) {
		return 0;
	}

	t = 3;
	while (t * t <= n) {
		if (n % t == 0) {
			return 0;
		}
		t += 2;
	}

	return 1;
}

unsigned int getPrime(unsigned int n) {
	if (n % 2 == 0) {
		n++;
	}
	while ( ! isPrime(n) ) {
		n += 2;
	}
	return n;
}

// Die Hash-Funktion zur Berechnung des Hashwerts eines Strings 
unsigned int hash(char *key, unsigned int size) {
	unsigned int h = 0;
	while(*key != '\0') {
		h = 31 * h + *key;
		key++;
	}
	return (h % size);
}

//Einen neuen Hash erzeugen
void create_hash(Hash *h, unsigned int size ) {
	
	//Falls size keine Primzahl ist, wird die naechst groessere gesucht
	size = getPrime( size );
	
	//Speicher fuer die Hash-Struktur allozieren
	*h = (Hash) malloc( sizeof(struct _hash) );
	if(*h == NULL) {
		fprintf(stderr, "Could not allocate memory for map!\n");
		return;
	}

	//Speicher fuer den Vektor allozieren
	(*h)->entries = (Element *) calloc( size, sizeof(Element) );
	if( (*h)->entries == NULL ) {
		fprintf(stderr, "Could not allocate memory for hash entries!\n");
		return;
	}
	
	//Groesse setzen
	(*h)->size = size;

}


//Ein neues Listenelement erzeugen
void create_entry( Element *e, char *key, unsigned int value ) {
	//Speicher fuer die Element-Struktur allozieren
	*e = (Element) malloc( sizeof(struct _element) );
	if(*e == NULL) {
		fprintf(stderr, "Could not allocate mem for entry!\n");
		return;
	}

	//Speicher fuer den String allozieren
	(*e)->key = (char *) calloc( (strlen(key) + 1), sizeof(char) );
	if( (*e)->key == NULL ) {
		fprintf(stderr, "Could not allocate mem for entry!\n");
		return;
	}

	strcpy( (*e)->key, key );
	(*e)->value = value;
}

//Den Hash ausgeben
void print( Hash h ) {
	Element entry;

	unsigned int i;
	
	//Die Indizes des elements-Vektors durchlaufen
	for(i=0; i < h->size; i++) {
		entry = h->entries[i];
		//Die Liste durchlaufen
		while(entry != NULL) {
			printf( "key: %20s\tcount: %d\n", entry->key, entry->value );
			entry = entry->next;
		}			
	}	
}

/*
 * Falls der Schluessel key noch nicht im Hash vorhanden ist, wird er hinzugefuegt
 * return 1 wenn alles geklappt hat
 * return 0 wenn der key schon im Hash war, oder ein Fehler auftrat
*/
int put( Hash h, char *key, int value ) {

	Element entry;
	
	//Index im Hash-Vektor bestimmen
	unsigned int address = hash( key, h->size );

	entry = h->entries[address];
	
	//Die Liste durchlaufen
	while( entry != NULL ) {
		//String existiert bereits
		if( strcmp(key, entry->key) == 0 ) {
			return 0;
		}
		entry = entry->next;
	}

	//String ist noch nicht im Hash
	// => neuer Eintrag
	create_entry( &entry, key, value );
	if( entry == NULL ) {
		return 0;
	}
	//entry an den Kopf der Liste seten
	entry->next = h->entries[address];
	h->entries[address] = entry;

	return 1;
}

/*
 * Aendert den Wert des Schluessel key.
 * return 1 falls alles OK.
 * return 0 falls der Schluessel nicht gefunden wurde
 */
int change_value( Hash h, char *key, int value ) {
	Element entry;

	//Index im Hash-Vektor bestimmen
	unsigned int address = hash( key, h->size );
	
	entry = h->entries[address];
	
	//Die Liste durchlaufen
	while(entry != NULL) {
		//String gefunden => Wert aendern
		if( strcmp(key, entry->key) == 0 ) {
			entry->value = value;
			return 1;
		}
		entry = entry->next;
	}
	
	return 0;
}

/*
 * Speichert den Wert des Schluessel key.im Zeiger *value
 * return 1 falls alles OK.
 * return 0 falls der Schluessel nicht gefunden wurde
 */
int get( Hash h, char *key, int *value ) {
	Element entry;

	//Index im Hash-Vektor bestimmen
	unsigned int address = hash( key, h->size );
	
	entry = h->entries[address];

	//Die Liste durchlaufen
	while(entry != NULL) {
		//String gefunden => Wert zurueckgeben
		if( strcmp(key, entry->key) == 0 ) {
			*value = entry->value;
			return 1;
		}
		entry = entry->next;
	}
	
	return 0;
	
}