//-----------------------------------------------------------------------------
// Struttura dati:
// 1) grafo (composto da un numero di nodi pari nel caso peggiore a
//    20 domini piu' 100 host) per memorizzare la topologia della rete.
//    Si utilizza una matrice di adiacenza per memorizzare il grafo.
// 2) tabella di hash per memorizzare l'associazione del nome di un host/dominio
//    con il suo numero di nodo nel grafo.
// Algoritmo utilizzato:
// Visita in profondita' a partire dal nodo corrispondente al <nodo sorgente>.
// La visita puo' terminare in due casi:
// 1) non esistono piu' nodi visitabili e non si e' mai raggiunto il 
//    <nodo destinazione>. In questo caso si stampa un messaggio di errore.
// 2) si arriva al <nodo destinazione>. In questo caso si stampa l'elenco
//    dei nodi visitati e per cui e' pari ad 1 il campo is_domain nella
//    tabella di hash. Ovvero stampa solo e soltanto i domini visitati.
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define     N_DOMAIN      20
#define	    N_HOST	100
#define     TAB_SIZE    7919

//-----------------------------------------------------------------------------
// Definizione della struttura dati per la memorizzazione del grafo mediante
// matrice di adiacenze.
//
int     mtx[N_DOMAIN+N_HOST][N_DOMAIN+N_HOST];
int	n_mtx;

typedef struct TAG_HASH {
	char    *key;		// La chiave della tabella e' il nome
	char	*IP_adx;	// Indirizzo IP del nomde/dominio
	char	is_domain;	// Flag che indica se l'elemento e' un dominio
	int     num;		// Numero del nodo nel grafo
} HASH;

//-----------------------------------------------------------------------------
// Definizione della tabella di hash usata per memorizzare l'associazione
// nome del nodo, nodo del grafo
//
HASH    tab[TAB_SIZE];

//-----------------------------------------------------------------------------
// Definizione della struttura dati con la soluzione
//
int	route[N_DOMAIN+2];
int	n_route;
char	found;

//-----------------------------------------------------------------------------
// Prototipi delle funzioni
//
int     hash( char *k );		// Funzione di hash
int     hash_init( void );		// Inizializza la tabella
void    hash_add( char *k, char *ip, int n, char d );	// Aggiunge un dato
void	hash_update( char *k, char *ip ); 	// Aggiorna chiave
int     hash_lookup( char *k );		// Cerca una chiave nella tabella
char    *hash_getkey( int n );		// Cerca la chiave associata al dato
int	hash_getpos( int n );		// Ritona la posizione in tabella
void    hash_dispose( void );		// Canella il contenuto della tabella

void    read_file( char *s );		// Legge il file
void	display_mtx( void );		// Visualizza la matrice di adiacenza
void	traceroute( char *s, char *d ); // Implemente la traceroute
void	dfs( int src, int dst );	// Visita in profondita'
void	display_route( void );		// Stampa la soluzione

//-----------------------------------------------------------------------------
// Implementazione delle funzioni
//
int	hash( char *k )
{
	char    *p;
	int     h;
    
	h = 0;
	for( p = k; *p; p++ )
	    h += (char)*p;
	    
	h = h % TAB_SIZE;
	
	return( h );
}

int    hash_init( void )
{
	int     i;
	
	for( i = 0; i < TAB_SIZE; i++ )
	{
	    tab[i].key = NULL;     
	    tab[i].IP_adx = NULL;     
	    tab[i].is_domain = 0;
	    tab[i].num = -1;
	}
	return 1;
}


void    hash_add( char *k, char *ip, int n, char d)
{
	int     h;
    
	h = hash( k );
    
	// Gestisce le collisioni con open addressing e linear probing
	while( tab[h].key != NULL )
		h = (h+1) % TAB_SIZE;
        
	tab[h].key = (char *)strdup( k );
	tab[h].IP_adx = (char *)strdup( ip );
	tab[h].is_domain = d;
	tab[h].num = n;
}

int    hash_lookup( char *k )
{
	int     h;    
	h = hash( k );
      
	while( tab[h].key != NULL && strcmp( tab[h].key, k ) != 0 )
	{    
		h = (h+1) % TAB_SIZE;
	}
    
	if( tab[h].key == NULL )
		return( -1 );	// La chiave non esiste
	return( h );		// La chiave esiste
}

void    hash_update( char *k, char *ip )
{
	int     h;
    
	h = hash_lookup( k );
	strcpy( tab[h].IP_adx, ip );
}

int	hash_getpos( int n )
{
	int	i;

	for( i = 0; i < TAB_SIZE; i++ )
		if( tab[i].num == n )
			return( i );
}

char    *hash_getkey( int n )
{
	int	i;

	for( i = 0; i < TAB_SIZE; i++ )
		if( tab[i].num == n )
			return( tab[i].key );
	return( NULL );
}

void    hash_dispose( void )
{
	int     i;
    
	for( i = 0; i < TAB_SIZE; i++ )
		if( tab[i].key != NULL )
			free( tab[i].key );
}

void    read_file(char *s )
{
	FILE    *fp;
	char	name[26];
	char	ip_adx[13];
	int	n_domain, n_host;
	int	domain, host;
	int	i, k, p;

	fp = fopen( s, "r" );
	if( fp == NULL )
	{    
		printf( "Impossibile aprire %s\n", s );
		return;
	}

	fscanf( fp, "%d\n", &n_domain );
	n_mtx = 0;
	for( i = 0; i < n_domain; i++ )
	{
		fscanf( fp, "%s\n", name );
		hash_add( name, "000000000000", i, 1 );
		n_mtx++;
	}

	p = n_domain;
	while( fscanf( fp, "%s %s %d\n", name, ip_adx, &n_host ) != EOF )
	{           
		// Aggiorno le informazioni sul dominio
		//
		k = hash_lookup( name );	
		if( domain == - 1 )
		{
			printf( "Impossibile trovare %s\n", name );
			exit( 1 );
		}
		else
		{
			hash_update( name, ip_adx );
		}
		domain = tab[k].num;

		// Aggiorno le informazioni sui nodi del domino
		//
		for( i = 0; i < n_host; i++ )
		{
			fscanf( fp, "%s %s\n", name, ip_adx );
			hash_add( name, ip_adx, p, 0 );
			host = p;
			p++;
			n_mtx++;

			mtx[host][domain] = 1;
			mtx[domain][host] = 1;
		}
		// Collego il dominio al dominio adiacente
		//
		fscanf( fp, "%s\n", name );
		k = hash_lookup( name );
		if( k == - 1 )
		{
			printf( "Impossibile trovare %s\n", name );
			exit( 1 );
		}
		else
		{
			k = tab[k].num;
			mtx[k][domain] = 1;
			mtx[domain][k] = 1;
		}
	}

	fclose( fp );
}

void	display_mtx( void )
{
	int   i, j;

	for( i = 0; i < n_mtx; i++ )
	{
		printf( "%s:\n", hash_getkey( i ) );
		for( j = 0; j < n_mtx; j++ )
			if( mtx[i][j] != 0 )
				printf( "\t%s\n", hash_getkey( j ) );
	}	
}

void	display_route( void )
{
	int	i, h;

	for( i = 0; i < n_route; i++ )
	{
		h = hash_getpos( route[i] );
		if( tab[h].is_domain == 1 )
			printf( "%s %s\n", tab[h].key, tab[h].IP_adx );
	}
}

void	dfs( int src, int dst )
{
	int	i;
	int	j;
	char	flag = 0;

	if( src == dst )
	{
		found = 1;
		display_route();
	}
	else
	{
		for( i = 0; i < n_mtx && !found; i++ )
		{
			if( mtx[src][i] != 0 )
			{
				flag = 0;
				for( j = 0; j < n_route; j++ )
					if( route[j] == i )
						flag = 1;
				if( !flag )
				{
					route[n_route++] = i;
					dfs( i, dst );
					n_route--;
				}
			}
		}
	}
}

void	traceroute( char *s, char *d )
{
	int	src, dst;

	src = hash_lookup( s );
	if( src == -1 )
	{
		printf( "Impossibile trovare %s\n", s );
		return;
	}
	src = tab[src].num;

	dst = hash_lookup( d );
	if( dst == -1 )
	{
		printf( "Impossibile trovare %s\n", d );
		return;
	}
	dst = tab[dst].num;

	route[0] = src;
	n_route = 1;
	found = 0;
	dfs( src, dst );

	if( found == 0 )
		printf( "Nessum cammino trovato\n" );
}

int	main(int argc, char *argv[])
{
	char	cmd[80];
	char	src[26], dst[26];

	hash_init();

	read_file( "dns.txt" );

	printf( "DNS> " );
	gets( cmd );
	while( strstr( cmd, "quit" ) == NULL )
	{
		if( strstr( cmd, "traceroute" ) )
		{
			sscanf( cmd, "%*s %s %s", src, dst );
			traceroute( src, dst );
		}
		if( strstr( cmd, "listdns" ) )
			display_mtx();
		printf( "DNS> " );
		gets( cmd );
	}


	hash_dispose();

	return 0;
}