#include "wimlib_internal.h"
#include "dentry.h"
#include "list.h"
#include "lookup_table.h"

struct link_group {
	u64 link_group_id;
	struct link_group *next;
	struct list_head *link_group_head;
};

struct link_group_table {
	struct link_group **array;
	u64 num_entries;
	u64 capacity;
};


struct link_group_table *new_link_group_table(u64 capacity)
{
	return (struct link_group_table*)new_lookup_table(capacity);
}

/* Insert a dentry into the hard link group table based on its hard link group
 * ID.
 *
 * If there is already a dentry in the table having the same hard link group ID,
 * we link the dentries together in a circular list.
 *
 * If the hard link group ID is 0, this is a no-op and the dentry is not
 * inserted.
 */
int link_group_table_insert(struct dentry *dentry, struct link_group_table *table)
{
	size_t pos;
	struct link_group *group;

	if (dentry->hard_link == 0)
		return 0;

	/* Try adding to existing hard link group */
	pos = dentry->hard_link % table->capacity;
	group = table->array[pos];
	while (group) {
		if (group->link_group_id == dentry->hard_link) {
			list_add(&dentry->link_group_list, group->link_group_head);
			return 0;
		}
		group = group->next;
	}

	/* Add new hard link group to the table */

	group = MALLOC(sizeof(struct link_group));
	if (!group)
		return WIMLIB_ERR_NOMEM;
	INIT_LIST_HEAD(&dentry->link_group_list);
	group->link_group_id = dentry->hard_link;
	group->next = table->array[pos];
	group->link_group_head = &dentry->link_group_list;
	table->array[pos] = group;

	/* XXX Make the table grow when too many entries have been inserted. */
	table->num_entries++;
	return 0;
}

/* Frees a link group table. */
void free_link_group_table(struct link_group_table *table)
{
	if (!table)
		return;
	if (table->array) {
		for (u64 i = 0; i < table->capacity; i++) {
			struct link_group *group = table->array[i];
			struct link_group *next;
			while (group) {
				next = group->next;
				FREE(group);
				group = next;
			}
		}
		FREE(table->array);
	}
	FREE(table);
}

/* Assign the link group IDs to dentries in a link group table, and return the
 * next available link group ID. */
u64 assign_link_groups(struct link_group_table *table)
{
	struct link_group *remaining_groups = NULL;
	u64 id = 1;
	for (u64 i = 0; i < table->capacity; i++) {
		struct link_group *group = table->array[i];
		struct link_group *next_group;
		struct dentry *dentry;
		while (group) {
			next_group = group->next;
			if (list_empty(group->link_group_head)) {
				/* Hard link group of size 1.  Change the hard
				 * link ID to 0 and discard the link_group */
				dentry = container_of(group->link_group_head,
						      struct dentry,
						      link_group_list);
				dentry->hard_link = 0;
				FREE(group);
			} else {
				/* Hard link group of size > 1.  Assign the
				 * dentries in the group the next available hard
				 * link IDs and queue the group to be
				 * re-inserted into the table. */
				list_for_each_entry(dentry, group->link_group_head,
						    link_group_list)
					dentry->hard_link = id;
				group->next = remaining_groups;
				remaining_groups = group;
				id++;
			}
			group = next_group;
		}
	}
	memset(table->array, 0, table->capacity * sizeof(table->array[0]));
	table->num_entries = 0;
	while (remaining_groups) {
		struct link_group *group = remaining_groups;
		size_t pos = group->link_group_id % table->capacity;

		table->num_entries++;
		group->next = table->array[pos];
		table->array[pos] = group;
		remaining_groups = remaining_groups->next;
	}
	return id;
}

#if 0
/* Load a dentry tree into the link group table */
int load_link_groups(struct link_group_table *table, struct dentry *root)
{
	int ret = for_dentry_in_tree(dentry, link_group_table_insert, table);
	if (ret == 0)
		assign_link_groups(table);
	return ret;
}
#endif