Tiny programs (C, C++, C#, ...)

/*
 * Soubor: htable.c - modul hashovaci tabulky
 * Kamil Dudka, FIT, DU2, priklad 2, 17.4.2005
 */
 
 
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "htable.h"
 
/*
 * Rekurzivni funkce list_free rekurzivne uvolni cely seznam (od zadane polozky dal)
 */
void list_free (struct htable_listitem *);
 
/*
 * Funkce list_newitemt alokuje a inicializuje novou
 * polozku seznamu a skopiruje do ni zadany retezec
 */
struct htable_listitem *list_newitemt (const char *);
 
 
/*
 * Hashovaci funkce opsana ze zadani DU
 */
unsigned int hash_function(const char *, unsigned);
 
 
htable_t *htable_init (unsigned size) {
	// Alokace struktury popisujici hashovaci tabulku
	htable_t *pHash;
	if (NULL==( pHash=malloc(sizeof(htable_t))))
		return NULL;
 
	// Ulozeni velikosti hashovaci tabulky
	pHash->size = size;
 
	// Alokace a inicializace hashovaci tabulky
	pHash->data = calloc(size, sizeof(struct htable_listitem *));
	if (NULL== pHash->data) {
		free (pHash);
		return NULL;
	} else
		return pHash;
}
 
struct htable_listitem *list_newitemt (const char *str) {
	// Alokace pameti pro polozky struktury
	struct htable_listitem *p;
	if (NULL==( p=malloc (sizeof(struct htable_listitem)) ))
		// Nedostatek pameti
		return NULL;
 
	// Inicializace slozek struktury
	p->next = NULL;
	p->n = 0;
 
	// Alokace pameti pro ulozeni retezce
	if (NULL==( p->uk = malloc ((strlen(str)+1)*sizeof(char)) ))
		// Nedostatek pameti
		return NULL;
 
	// Kopie retezce
	strcpy (p->uk, str);
	return p;
}
 
void htable_clear (htable_t *pHash) {
	for (unsigned i=0; i< pHash->size; i++)
		list_free ((pHash->data)[i]);		
}
 
/*
 * Rekurzivni funkce list_free rekurzivne uvolni cely seznam (od *pNow dal)
 */
void list_free (struct htable_listitem *pNow) {
	if (NULL==pNow)
		// Konec seznamu
		return;
 
	// Rekurzivni volani
	list_free (pNow->next);
 
	// Uvolneni alokovane pameti pro ulozeni retezce
	free (pNow->uk);
 
	// Uvolneni struktury prvku
	free (pNow);
}
 
void htable_print (htable_t *pHash) {
	// Hlavni cyklus prochazi polozky hashovaci tabulky
	for (unsigned i=0; i< pHash->size; i++) {
		struct htable_listitem *now = (pHash->data)[i];
		// Vnoreny cyklus prochazi seznam
		while (NULL!=now) {
			printf ("%s\t%i\n", now->uk, now->n);
			now = now->next;
		}
	}
}
 
void htable_free (htable_t *pHash) {
 
	// Zruseni vsech polozek hashovaci tabulky
	htable_clear (pHash);
 
	// Zruseni hashovaci tabulky
	free (pHash->data);
 
	// Zruseni struktury popisujici hashovaci tabulku
	free (pHash);
}
 
struct htable_listitem *htable_lookup (htable_t *pHash, const char *str) {
 
	// Vypocet pozice v hashovaci tabulce
	const unsigned hashPos = hash_function (str, pHash->size);
	struct htable_listitem *pNow = (pHash->data) [hashPos];
 
	if (NULL==pNow)
		// Na dane pozici mapovaci tabulky nic neni
		return ((pHash->data)[hashPos] = list_newitemt (str));
 
		// Vyhlednani prvku na pocatecni pozici
	if (0==strcmp (pNow->uk, str))
		return pNow;
 
		// Vyhledani prvku ve zbytku seznamu
	while (NULL!= pNow->next) {
		pNow = pNow->next;
		if (0==strcmp (pNow->uk, str))
			return pNow;
	}
 
	// Vlozeni prvku na konec seznamu
	pNow->next = list_newitemt (str);
	if (NULL== pNow->next)
		return NULL;
	else
		return pNow->next;
}
 
/*
 * Hashovaci funkce opsana ze zadani DU
 */
unsigned int hash_function(const char *str, unsigned htable_size) { 
	unsigned int h=0;
	unsigned char *p;
	for(p=(unsigned char*)str; *p!='\0'; p++) 
	h = 31*h + *p;
	return h % htable_size;
}