#include <stdio.h>
#include <sys/types.h>
#include <dirent.h>
#include <sys/stat.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>


struct node {
	struct node *next;
	char *name;
	unsigned long size;
};

#define HASHSIZE 1024
struct node *hashtable[HASHSIZE];


unsigned int
hashfunc(unsigned long size)
{
	return size % HASHSIZE;
}

void
insert(char *name, unsigned long size)
{
	struct node *np;
	char *str;
	unsigned int h = hashfunc(size);

	if (!(np = malloc(sizeof(struct node)))) {
		fprintf(stderr, "Out of mem\n");
		exit(1);
	}
	if (!(str = strdup(name))) {
		fprintf(stderr, "Out of mem\n");
		exit(1);
	}
	np->name = str;
	np->size = size;
	np->next = hashtable[h];  /* push */
	hashtable[h] = np;
}

void
processdir(char *name)
{
	DIR *dp;
	struct dirent *dent;
	struct stat sbuf;
	char buf[BUFSIZ];

	if (!(dp = opendir(name))) {
		fprintf(stderr, "Unable to open: %s\n", name);
		return;
	}
	while ((dent = readdir(dp))) {
		if (strcmp(dent->d_name, ".")==0 ||
				strcmp(dent->d_name, "..")==0) {
			continue;
		}
		/* check for overflow */
		if (BUFSIZ < strlen(name)+strlen(dent->d_name)+2) {
			fprintf(stderr, "Path name too long, sorry.\n");
			exit(1);
		}
		snprintf(buf, BUFSIZ, "%s/%s", name, dent->d_name);
		if (lstat(buf, &sbuf) == -1) {
			fprintf(stderr, "unable to stat %s\n", buf);
			continue;
		}
		if (S_ISREG(sbuf.st_mode)) {
			insert(buf, (unsigned long)sbuf.st_size);
		} else if (S_ISDIR(sbuf.st_mode)) {
			processdir(buf);
		}
	}
	closedir(dp);
}

int
main(int argc, char *argv[])
{
	struct node *np;
	unsigned int i;

	memset(hashtable, 0, sizeof hashtable);  /* init hash table */

	if (argc == 1) {
		processdir(".");
	} else {
		for (argv++,argc--; *argv; argv++,argc--) {
			processdir(*argv);
		}
	}

	/* list the duplicates */
	for (i=0; i<HASHSIZE; i++) {
		if (!hashtable[i] || !hashtable[i]->next) {
			continue;  /* we only look for doubles, triples, ... */
		}
		for (np=hashtable[i]; np; np=np->next) {
			printf("%s\n", np->name);
		}
		putchar('\n');
	}

	return 0;
}