#include <stdio.h>
#include <dir.h>
#include <stdlib.h>
#include <string.h>
#include <dos.h>

#define BUFFER    10000       /* Velikost bufferu pro porovnavane soubory */
#define TABULKA   1000        /* Velikost hash tabulky */
#define NALEZENO  100         /* Velikost tabulky nalezenych souboru */

/* Struktura popisujici udaj jednoho souboru v hash tabulce */
struct soubor {
	int index;               /* index v tabulce shodnych souboru */
	struct soubor *stejny;   /* dalsi shodny soubor */
	struct soubor *dalsi;    /* dalsi soubor v prohledavacim retezci hash_tabulky */
	long int delka;          /* delka souboru */
	char nazev[1];           /* nazev souboru - alokuje se vzdy potrebna pamet */
};

struct soubor *tabulka[TABULKA];  /* hash tabulka, fce delka % TABULKA */
struct soubor **nalezeno;         /* tabulka shodnych souboru */
int volny, velikost;              /* prvni volny a velikost tabulky
									 shodnych souboru */
char buf1[BUFFER], buf2[BUFFER];  /* buffery pro porovnavani souboru */

void init(void)
{
	register int i;
	for ( i=0; i<TABULKA; i++ )
		tabulka[i] = NULL;

	volny = 1;
	velikost = NALEZENO;
	if ( (nalezeno = (struct soubor **) malloc(
		velikost*sizeof(struct soubor *))) == NULL ) {
			fprintf(stderr,"Dosla pamet !!\n");
			exit(-1);
		}
	for ( i=0; i<NALEZENO; i++ )
		nalezeno[i] = NULL;
}

/*
 * Zvetsi pole pro ukladani shodnych souboru pokud je to treba
 */
void zvetsi_volny(void)
{
	volny++;
	if (volny==velikost) {
		velikost *= 2;
		if ( (nalezeno = (struct soubor **) realloc( nalezeno,
			velikost*sizeof(struct soubor *))) == NULL ) {
			fprintf(stderr,"Dosla pamet !!\n");
			exit(-1);
		}
	}
}

/*
 * Porovnani obsahu dvou souboru
 */
int stejny(char *nazev1, char *nazev2)
{
	FILE *fr1, *fr2;
	int pocet;

	if ( (fr1 = fopen(nazev1,"rb")) == NULL ) {
		fprintf(stderr,"Nelze precist soubor: %s\n", nazev1);
		perror("Duvod");
		return 0;
	}
	if ( (fr2 = fopen(nazev2,"rb")) == NULL ) {
		fprintf(stderr,"Nelze precist soubor: %s\n", nazev2);
		perror("Duvod");
		fclose(fr1);
		return 0;
	}
	while ( pocet=fread(buf1,1,BUFFER,fr1) ) {
		fread(buf2,1,BUFFER,fr2);
		if ( memcmp( buf1, buf2, pocet ) ) {
			fclose(fr1);
			fclose(fr2);
			return 0;
		}
	}
	fclose(fr1);
	fclose(fr2);
	return 1;
}

/*
 * Prida soubor do hash tabulky, pokud tam uz shodny soubor je,
 * zaradi jej do seznamu stejnych souboru
 */
void pridej_soubor(long int delka, char *nazev)
{
	struct soubor *pom, *novy;
	long int index;

	if ( (novy = (struct soubor *) malloc( sizeof(struct soubor)
		+ strlen(nazev)) ) == NULL ) {
		fprintf(stderr,"Dosla pamet !!\n");
		exit(-1);
	}
	novy -> stejny = NULL;
	strcpy( novy->nazev, nazev );
	novy -> delka = delka;
	novy -> index = 0;

	pom = tabulka[index = delka % TABULKA];
	while ( pom != NULL ) {
		if ( delka == pom->delka && stejny(nazev, pom->nazev )) {
			if ( pom->index == 0 ) {
				pom->index = volny;
				zvetsi_volny();
			}
			novy -> stejny = nalezeno[pom->index] ? nalezeno[pom->index] : pom;
			nalezeno[pom->index] = novy;
			novy = NULL;
			break;
		}
		pom = pom->dalsi;
	}
	if ( novy ) {
		novy -> dalsi = tabulka[index];
		tabulka[index] = novy;
	}
}

/*
 * Prohleda podadresar
 */

void pridej_adresar( char * nazev )
{
	static char cely_nazev[1000];
	struct ffblk ffblk;
	int konec;
	char *jmeno;

	strcpy(cely_nazev, nazev);
	strcat(cely_nazev,"\\*.*");
	konec = findfirst(cely_nazev, &ffblk, FA_DIREC);
	while (!konec) {
		jmeno = malloc(strlen(nazev)+15);
		strcpy( jmeno, nazev );
		strcat( jmeno, "\\" );
		strcat( jmeno, ffblk.ff_name );
		if ( ffblk.ff_attrib & FA_DIREC ) {
			if ( strcmp(ffblk.ff_name,".") && strcmp(ffblk.ff_name,".."))
				pridej_adresar( jmeno );
		} else {
			pridej_soubor( ffblk.ff_fsize, jmeno );
		}
		free( jmeno );
		konec = findnext( &ffblk );
	}
}

int main(int argc, char *argv[])
{
	FILE *vystup;
	int i;
	struct soubor *pom;

	if (argc < 2 || argc > 3) {
		fprintf(stderr,"Spatny pocet parametru !!!\n");
		fprintf(stderr,"\nPouziti:\n");
		fprintf(stderr,"\n\t%s [d:\\]adresar [vystup]\n", argv[0]);
		return -1;
	}
	if ( argc==3 ) {
		if ( (vystup = fopen(argv[2], "w")) == NULL ) {
			perror("Nelze otevrit vystupni soubor");
			return -1;
		}
	} else {
		vystup = stdout;
	}
	init();
	pridej_adresar( argv[1] );

	fprintf(vystup, "Shodne soubory stromu %s\n\n", argv[1] );
	for ( i = 1 ; pom = nalezeno[i] ; i++ ) {
		fprintf(vystup, "Shoda %d:\n",i);
		while ( pom ) {
			fprintf( vystup, "%8ld - %s\n", pom->delka, pom->nazev );
			pom = pom->stejny;
		}
		fprintf( vystup, "\n" );
	}
	fclose(vystup);
	return 0;
}