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;
16 struct link_group *singles;
21 struct link_group_table *new_link_group_table(u64 capacity)
23 struct link_group_table *table;
24 struct link_group **array;
26 table = MALLOC(sizeof(struct link_group_table));
29 array = CALLOC(capacity, sizeof(array[0]));
34 table->num_entries = 0;
35 table->capacity = capacity;
37 table->singles = NULL;
40 ERROR("Failed to allocate memory for link group table with capacity %zu",
45 /* Insert a dentry into the hard link group table based on its hard link group
48 * If there is already a dentry in the table having the same hard link group ID,
49 * we link the dentries together in a circular list.
51 * If the hard link group ID is 0, this is a no-op and the dentry is not
54 int link_group_table_insert(struct dentry *dentry, struct link_group_table *table)
57 struct link_group *group;
59 if (dentry->hard_link == 0) {
60 /* Single group--- Add to the singles list (we can't put it in
61 * the table itself because all the singles have a link group ID
63 group = MALLOC(sizeof(struct link_group));
65 return WIMLIB_ERR_NOMEM;
66 group->link_group_id = 0;
67 group->next = table->singles;
68 table->singles = group;
69 INIT_LIST_HEAD(&dentry->link_group_list);
70 group->dentry_list = &dentry->link_group_list;
74 /* Try adding to existing hard link group */
75 pos = dentry->hard_link % table->capacity;
76 group = table->array[pos];
78 if (group->link_group_id == dentry->hard_link) {
79 list_add(&dentry->link_group_list, group->dentry_list);
85 /* Add new hard link group to the table */
87 group = MALLOC(sizeof(struct link_group));
89 return WIMLIB_ERR_NOMEM;
90 group->link_group_id = dentry->hard_link;
91 group->next = table->array[pos];
92 INIT_LIST_HEAD(&dentry->link_group_list);
93 group->dentry_list = &dentry->link_group_list;
94 table->array[pos] = group;
96 /* XXX Make the table grow when too many entries have been inserted. */
101 /* Frees a link group table. */
102 void free_link_group_table(struct link_group_table *table)
107 for (u64 i = 0; i < table->capacity; i++) {
108 struct link_group *group = table->array[i];
109 struct link_group *next;
121 /* Assign the link group IDs to dentries in a link group table, and return the
122 * next available link group ID. */
123 u64 assign_link_groups(struct link_group_table *table)
125 DEBUG("Assigning link groups");
127 for (u64 i = 0; i < table->capacity; i++) {
128 struct link_group *group = table->array[i];
129 struct link_group *next_group;
130 struct dentry *dentry;
131 struct list_head *cur;
133 cur = group->dentry_list;
135 dentry = container_of(cur,
138 dentry->hard_link = id;
140 } while (cur != group->dentry_list);
146 struct link_group *single = table->singles;
148 struct dentry *dentry;
149 struct link_group *next_single;
152 next_single = single->next;
154 dentry = container_of(single->dentry_list, struct dentry,
156 dentry->hard_link = id;
158 pos = id % table->capacity;
159 single->next = table->array[pos];
160 table->array[pos] = single;
162 single = next_single;
165 table->singles = NULL;
169 static int link_group_free_duplicate_data(struct link_group *group,
170 struct link_group **bad_links)
172 struct list_head *head;
173 struct list_head *next;
174 struct dentry *master;
176 head = group->dentry_list;
177 master = container_of(head, struct dentry, link_group_list);
179 master->link_group_master_status = GROUP_MASTER;
180 while (head != group->dentry_list) {
182 struct dentry *slave;
185 slave = container_of(head, struct dentry, link_group_list);
186 ret = share_dentry_ads(master, slave);
188 /* I would it to be an error if two dentries are the same hard
189 * link group but have irreconcilable differences such as
190 * different file permissions, but unfortunately some of M$'s
191 * WIMs contain many instances of this error. This problem is
192 * worked around here by splitting each offending dentry off
193 * into its own hard link group. */
195 struct link_group *single;
196 single = MALLOC(sizeof(struct link_group));
198 return WIMLIB_ERR_NOMEM;
199 single->link_group_id = 0;
200 single->next = *bad_links;
202 INIT_LIST_HEAD(&slave->link_group_list);
203 single->dentry_list = &slave->link_group_list;
204 slave->link_group_master_status = GROUP_INDEPENDENT;
211 int link_groups_free_duplicate_data(struct link_group_table *table)
213 for (u64 i = 0; i < table->capacity; i++) {
214 struct link_group *group = table->array[i];
217 ret = link_group_free_duplicate_data(group,