1 #include "wimlib_internal.h"
4 #include "lookup_table.h"
8 struct link_group *next;
9 struct list_head dentry_list;
12 struct link_group_table {
13 struct link_group **array;
20 struct link_group_table *new_link_group_table(u64 capacity)
22 return (struct link_group_table*)new_lookup_table(capacity);
25 /* Insert a dentry into the hard link group table based on its hard link group
28 * If there is already a dentry in the table having the same hard link group ID,
29 * we link the dentries together in a circular list.
31 * If the hard link group ID is 0, this is a no-op and the dentry is not
34 int link_group_table_insert(struct dentry *dentry, struct link_group_table *table)
37 struct link_group *group;
39 if (dentry->hard_link == 0) {
40 INIT_LIST_HEAD(&dentry->link_group_list);
44 /* Try adding to existing hard link group */
45 pos = dentry->hard_link % table->capacity;
46 group = table->array[pos];
48 if (group->link_group_id == dentry->hard_link) {
49 list_add(&dentry->link_group_list, &group->dentry_list);
55 /* Add new hard link group to the table */
57 group = MALLOC(sizeof(struct link_group));
59 return WIMLIB_ERR_NOMEM;
60 group->link_group_id = dentry->hard_link;
61 group->next = table->array[pos];
62 INIT_LIST_HEAD(&group->dentry_list);
63 list_add(&dentry->link_group_list, &group->dentry_list);
64 table->array[pos] = group;
66 /* XXX Make the table grow when too many entries have been inserted. */
71 /* Frees a link group table. */
72 void free_link_group_table(struct link_group_table *table)
77 for (u64 i = 0; i < table->capacity; i++) {
78 struct link_group *group = table->array[i];
79 struct link_group *next;
91 /* Assign the link group IDs to dentries in a link group table, and return the
92 * next available link group ID. */
93 u64 assign_link_groups(struct link_group_table *table)
95 struct link_group *remaining_groups = NULL;
97 for (u64 i = 0; i < table->capacity; i++) {
98 struct link_group *group = table->array[i];
99 struct link_group *next_group;
100 struct dentry *dentry;
102 next_group = group->next;
103 if (list_is_singular(&group->dentry_list)) {
104 /* Hard link group of size 1. Change the hard
105 * link ID to 0 and discard the link_group */
106 dentry = container_of(group->dentry_list.next,
109 dentry->hard_link = 0;
112 /* Hard link group of size > 1. Assign the
113 * dentries in the group the next available hard
114 * link IDs and queue the group to be
115 * re-inserted into the table. */
116 list_for_each_entry(dentry, &group->dentry_list,
118 dentry->hard_link = id;
119 group->next = remaining_groups;
120 remaining_groups = group;
126 memset(table->array, 0, table->capacity * sizeof(table->array[0]));
127 table->num_entries = 0;
128 while (remaining_groups) {
129 struct link_group *group = remaining_groups;
130 size_t pos = group->link_group_id % table->capacity;
132 table->num_entries++;
133 group->next = table->array[pos];
134 table->array[pos] = group;
135 remaining_groups = remaining_groups->next;
141 /* Load a dentry tree into the link group table */
142 int load_link_groups(struct link_group_table *table, struct dentry *root)
144 int ret = for_dentry_in_tree(dentry, link_group_table_insert, table);
146 assign_link_groups(table);