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)
42 /* Try adding to existing hard link group */
43 pos = dentry->hard_link % table->capacity;
44 group = table->array[pos];
46 if (group->link_group_id == dentry->hard_link) {
47 list_add(&dentry->link_group_list, &group->dentry_list);
53 /* Add new hard link group to the table */
55 group = MALLOC(sizeof(struct link_group));
57 return WIMLIB_ERR_NOMEM;
58 group->link_group_id = dentry->hard_link;
59 group->next = table->array[pos];
60 INIT_LIST_HEAD(&group->dentry_list);
61 list_add(&dentry->link_group_list, &group->dentry_list);
62 table->array[pos] = group;
64 /* XXX Make the table grow when too many entries have been inserted. */
69 /* Frees a link group table. */
70 void free_link_group_table(struct link_group_table *table)
75 for (u64 i = 0; i < table->capacity; i++) {
76 struct link_group *group = table->array[i];
77 struct link_group *next;
89 /* Assign the link group IDs to dentries in a link group table, and return the
90 * next available link group ID. */
91 u64 assign_link_groups(struct link_group_table *table)
93 struct link_group *remaining_groups = NULL;
95 for (u64 i = 0; i < table->capacity; i++) {
96 struct link_group *group = table->array[i];
97 struct link_group *next_group;
98 struct dentry *dentry;
100 next_group = group->next;
101 if (list_is_singular(&group->dentry_list)) {
102 /* Hard link group of size 1. Change the hard
103 * link ID to 0 and discard the link_group */
104 dentry = container_of(group->dentry_list.next,
107 dentry->hard_link = 0;
110 /* Hard link group of size > 1. Assign the
111 * dentries in the group the next available hard
112 * link IDs and queue the group to be
113 * re-inserted into the table. */
114 list_for_each_entry(dentry, &group->dentry_list,
116 dentry->hard_link = id;
117 group->next = remaining_groups;
118 remaining_groups = group;
124 memset(table->array, 0, table->capacity * sizeof(table->array[0]));
125 table->num_entries = 0;
126 while (remaining_groups) {
127 struct link_group *group = remaining_groups;
128 size_t pos = group->link_group_id % table->capacity;
130 table->num_entries++;
131 group->next = table->array[pos];
132 table->array[pos] = group;
133 remaining_groups = remaining_groups->next;
139 /* Load a dentry tree into the link group table */
140 int load_link_groups(struct link_group_table *table, struct dentry *root)
142 int ret = for_dentry_in_tree(dentry, link_group_table_insert, table);
144 assign_link_groups(table);