/*
 * Copyright (C) 2009 Andre Noll <maan@tuebingen.mpg.de>
 *
 * Licensed under the GPL v2. For licencing details see COPYING.
 */

/*
 * A simple program that traverses a directory and prints groups of file names
 * which are hard-linked to each other.
 */

#include <inttypes.h>
#include <osl.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <sys/types.h>
#include <dirent.h>
#include <errno.h>
#include <sys/mman.h>
#include <fcntl.h>

/**
 * We are lazy here and use an osl table with only a single column of type
 * OSL_NO_STORAGE.  This is possible because we need only one red black tree
 * for hlt.  So we pack everything into one structure and use a fixed-size
 * column for the data of each (device, inode) pair.
 *
 * This approach keeps things simple but is a bit dangerous: As the compare
 * function for the red black tree, hld_compare, uses only the dev_id and the
 * inode fields of struct hard_link_data it's OK to modify the other fields of
 * the struct in-place.
 */
enum hlt_columns {
	COL_HLD,
	NUM_HLT_COLUMNS
};

/**
 * The data of one "row" of the table.
 */
struct hard_link_data {
	/** The st_dev field from struct stat. */
	dev_t dev_id;
	/** The st_ino field from struct stat. */
	ino_t inode;
	/** The st_nlink field from struct stat. */
	nlink_t num_links;
	/** The array of pathnames. */
	char **paths;
	/** The size of \a paths. */
	unsigned array_size;
	/** The number of hard links found so far. */
	unsigned num_paths;
};

/**
 * Compare two hard_link_data structs.
 *
 * \param obj1 Pointer to the first object.
 * \param obj2 Pointer to the second object.
 *
 * \return It returns an integer less than, equal to, or greater than zero if
 * \a obj1 is found, respectively, to be less than, to match, or be greater than
 * obj2.
 *
 * \sa strcmp(3), strncmp(3), osl_compare_func.
 */
static int hld_compare(const struct osl_object *obj1, const struct osl_object *obj2)
{
	const struct hard_link_data *hld1 = obj1->data;
	const struct hard_link_data *hld2 = obj2->data;

	if (hld1->inode < hld2->inode)
		return -1;
	if (hld1->inode > hld2->inode)
		return 1;
	if (hld1->dev_id < hld2->dev_id)
		return -1;
	if (hld1->dev_id > hld2->dev_id)
		return 1;
	return 0;
}

static struct osl_column_description hlt_table_cols[] = {
	[COL_HLD] = {
		.storage_type = OSL_NO_STORAGE,
		.storage_flags = OSL_RBTREE | OSL_UNIQUE | OSL_FIXED_SIZE,
		.data_size = sizeof(struct hard_link_data),
		.name = "hard link data",
		.compare_function = hld_compare,
	},
};

static struct osl_table *table;

static struct osl_table_description hlt_table_desc = {
	/* dir not needed because all cols have storage type NO_STORAGE */
	.dir = NULL,
	.name = "hlt",
	.num_columns = NUM_HLT_COLUMNS,
	.flags = 0,
	.column_descriptions = hlt_table_cols,
};

static void print_usage_and_die(void)
{
	fprintf(stderr, "usage:\n\thlt <dirname>\n");
	exit(EXIT_FAILURE);
}

/* either succeeds or exits */
static void create_table_or_die(int argc, char **argv)
{
	struct stat statbuf;
	int ret;

	/* some sanity checks */
	if (argc != 2)
		print_usage_and_die();
	if (lstat(argv[1], &statbuf) == -1) {
		fprintf(stderr, "no such dir: %s\n", argv[1]);
		exit(EXIT_FAILURE);
	}
	if (!S_ISDIR(statbuf.st_mode)) {
		fprintf(stderr, "not a dir: %s\n", argv[1]);
		exit(EXIT_FAILURE);
	}

	//fprintf(stderr, "col_desc: %p\n", hlt_table_desc.column_descriptions);
	/* create the osl table... */
	ret = osl_create_table(&hlt_table_desc);
	if (ret < 0) {
		fprintf(stderr, "%s\n", osl_strerror(-ret));
		exit(EXIT_FAILURE);
	}
	/* ...and open it. */
	ret = osl_open_table(&hlt_table_desc, &table);
	if (ret < 0) {
		fprintf(stderr, "osl_open_table: %s\n", osl_strerror(-ret));
		exit(EXIT_FAILURE);
	}
}

static void *malloc_or_die(size_t size)
{
	void *ret = malloc(size);

	if (ret)
		return ret;
	fprintf(stderr, "out of memory\n");
	exit(EXIT_FAILURE);
}

static char *make_name(const char *dirname, const char *subdirname)
{
	size_t len = strlen(dirname) + strlen(subdirname) + 2;
	char *name = malloc_or_die(len);

	sprintf(name, "%s/%s", dirname, subdirname);
	return name;
}

static int add_hard_link(char *path, struct stat *s)
{
	int ret;
	struct osl_row *row;
	struct hard_link_data *entry;

	/*
	 * We need to find out whether a row containing the (dev_t, inode) pair
	 * given by \a s already exists in the osl table. Therefore we init a
	 * hard_link_data structure with only these two fields initialized...
	 */
	struct hard_link_data hld = {
		.dev_id = s->st_dev,
		.inode = s->st_ino
	};

	/* ... and make an osl object out of it. */
	struct osl_object obj = {
		.data = &hld,
		.size = sizeof(hld)
	};

	/*
	 * check whether there is a row with the same dev_id and inode values.
	 */
	ret = osl_get_row(table, COL_HLD, &obj, &row);

	/* Abort on real errors. */
	if (ret < 0 && ret != -E_OSL_RB_KEY_NOT_FOUND)
		return ret;

	if (ret < 0) { /* key not found, add a new row to the table. */
		struct osl_object objs[NUM_HLT_COLUMNS];

		entry = malloc_or_die(sizeof(*entry));
		memset(entry, 0, sizeof(*entry));

		/* copy relevant data from struct stat */
		entry->dev_id = s->st_dev;
		entry->inode = s->st_ino;
		entry->num_links = s->st_nlink;

		entry->array_size = s->st_nlink; /* that's usually enough */
		entry->paths = malloc_or_die(entry->array_size * sizeof(char *));

		/* Add the new row */
		objs[COL_HLD].data = entry;
		objs[COL_HLD].size = sizeof(*entry);
		ret = osl_add_row(table, objs);
		if (ret < 0) {
			free(entry);
			return ret;
		}
	} else { /* OK, we have a row, retrieve the hld struct */
		ret = osl_get_object(table, row, COL_HLD, &obj);
		if (ret < 0)
			return ret;
		entry = obj.data;
	}

	/*
	 * Now 'entry' points to a struct hard_link_data and we may modify
	 * everything in-place except dev_id and inode (these two fields must
	 * not be changed directly because that would mess up the rbtree).
	 *
	 * So increase the counter and add the new path to the entry->paths
	 * array.
	 */

	if (entry->num_paths >= entry->array_size) {
		/*
		 * New hard links have been created by someone and the
		 * entry->paths array is too small. Double its size.
		 */
		entry->array_size *= 2;
		entry->paths = realloc(entry->paths,
			entry->array_size * sizeof(char *));
		if (!entry->paths) {
			fprintf(stderr, "realloc error. array size: %u\n",
				entry->array_size);
			exit(EXIT_FAILURE);
		}
	}

	entry->paths[entry->num_paths] = path;
	entry->num_paths++;
	return 1;
}

/**
 * Traverse the given directory recursively. Each regular file
 * with hard link count > 1 is going to be added to the table.
 */
static int populate_table(char *dirname)
{
	struct dirent *entry;
	int ret;
	DIR *dir = opendir(dirname);

	if (!dir) {
		fprintf(stderr, "failed to open dir %s\n", dirname);
		/* Ignore this error by returning success. */
		return 1;
	}
	while ((entry = readdir(dir))) {
		mode_t m;
		struct stat s;
		char *new_name;

		if (!strcmp(entry->d_name, "."))
			continue;
		if (!strcmp(entry->d_name, ".."))
			continue;
		new_name = make_name(dirname, entry->d_name);
		if (lstat(new_name, &s) == -1) {
			fprintf(stderr, "lstat error for %s (%s)\n",
				new_name, strerror(errno));
			free(new_name);
			continue;
		}
		m = s.st_mode;
		if (S_ISDIR(m)) {
			/* recurse and pass the name of the subdir */
			ret = populate_table(new_name);
			free(new_name);
			if (ret < 0) /* fatal error */
				goto out;
			continue;
		}
		if (!S_ISREG(m) || s.st_nlink < 2) {
			free(new_name);
			continue;
		}
		/* regular file with hard links, add it to the table */
		add_hard_link(new_name, &s);
	}
	ret = 1; /* success */
out:
	closedir(dir);
	return ret;
}

static int print_row(struct osl_row *row, void *data)
{
	struct hard_link_data *hld;
	struct osl_object obj;
	int i, ret = osl_get_object(table, row, COL_HLD, &obj);

	if (ret < 0)
		return ret;
	hld = obj.data;
	printf("%d/%d: Found %u/%u hard links:\n", (int)hld->dev_id,
		(int)hld->inode, hld->num_paths, hld->num_links);
	for (i = 0; i < hld->num_paths; i++) {
		printf("\t%s\n", hld->paths[i]);
		free(hld->paths[i]);
	}
	free(hld->paths);
	return 1;
}

int main(int argc, char **argv)
{
	int ret;

	create_table_or_die(argc, argv);
	ret = populate_table(argv[1]);
	if (ret < 0)
		goto out;
	/*
	 * Print results by iterating over all rows and calling print_row() for
	 * each row.
	 */
	ret = osl_rbtree_loop(table, COL_HLD, NULL, print_row);
out:
	/* This frees the memory pointed to by the osl objects. */
	osl_close_table(table, OSL_FREE_VOLATILE);
	return ret < 0? EXIT_FAILURE : EXIT_SUCCESS;
}