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(&dentry->link_group_list);
63 group->dentry_list = &dentry->link_group_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;
104 struct list_head *dentry_list = group->dentry_list;
105 if (dentry_list->next == dentry_list) {
106 /* Hard link group of size 1. Change the hard
107 * link ID to 0 and discard the link_group */
111 /* Hard link group of size > 1. Assign the
112 * dentries in the group the next available hard
113 * link IDs and queue the group to be
114 * re-inserted into the table. */
116 group->next = remaining_groups;
117 remaining_groups = group;
119 struct list_head *cur = dentry_list;
121 dentry = container_of(cur,
124 dentry->hard_link = cur_id;
126 } while (cur != dentry_list);
130 memset(table->array, 0, table->capacity * sizeof(table->array[0]));
131 table->num_entries = 0;
132 while (remaining_groups) {
133 struct link_group *group = remaining_groups;
134 size_t pos = group->link_group_id % table->capacity;
136 table->num_entries++;
137 group->next = table->array[pos];
138 table->array[pos] = group;
139 remaining_groups = remaining_groups->next;
145 /* Load a dentry tree into the link group table */
146 int load_link_groups(struct link_group_table *table, struct dentry *root)
148 int ret = for_dentry_in_tree(dentry, link_group_table_insert, table);
150 assign_link_groups(table);