1 #include "wimlib_internal.h"
4 #include "lookup_table.h"
8 struct link_group *next;
9 struct list_head *link_group_head;
12 struct link_group_table {
13 struct link_group **array;
19 struct link_group_table *new_link_group_table(u64 capacity)
21 return (struct link_group_table*)new_lookup_table(capacity);
24 /* Insert a dentry into the hard link group table based on its hard link group
27 * If there is already a dentry in the table having the same hard link group ID,
28 * we link the dentries together in a circular list.
30 * If the hard link group ID is 0, this is a no-op and the dentry is not
33 int link_group_table_insert(struct dentry *dentry, struct link_group_table *table)
36 struct link_group *group;
38 if (dentry->hard_link == 0)
41 /* Try adding to existing hard link group */
42 pos = dentry->hard_link % table->capacity;
43 group = table->array[pos];
45 if (group->link_group_id == dentry->hard_link) {
46 list_add(&dentry->link_group_list, group->link_group_head);
52 /* Add new hard link group to the table */
54 group = MALLOC(sizeof(struct link_group));
56 return WIMLIB_ERR_NOMEM;
57 INIT_LIST_HEAD(&dentry->link_group_list);
58 group->link_group_id = dentry->hard_link;
59 group->next = table->array[pos];
60 group->link_group_head = &dentry->link_group_list;
61 table->array[pos] = group;
63 /* XXX Make the table grow when too many entries have been inserted. */
68 /* Frees a link group table. */
69 void free_link_group_table(struct link_group_table *table)
74 for (u64 i = 0; i < table->capacity; i++) {
75 struct link_group *group = table->array[i];
76 struct link_group *next;
88 /* Assign the link group IDs to dentries in a link group table, and return the
89 * next available link group ID. */
90 u64 assign_link_groups(struct link_group_table *table)
92 struct link_group *remaining_groups = NULL;
94 for (u64 i = 0; i < table->capacity; i++) {
95 struct link_group *group = table->array[i];
96 struct link_group *next_group;
97 struct dentry *dentry;
99 next_group = group->next;
100 if (list_empty(group->link_group_head)) {
101 /* Hard link group of size 1. Change the hard
102 * link ID to 0 and discard the link_group */
103 dentry = container_of(group->link_group_head,
106 dentry->hard_link = 0;
109 /* Hard link group of size > 1. Assign the
110 * dentries in the group the next available hard
111 * link IDs and queue the group to be
112 * re-inserted into the table. */
113 list_for_each_entry(dentry, group->link_group_head,
115 dentry->hard_link = id;
116 group->next = remaining_groups;
117 remaining_groups = group;
123 memset(table->array, 0, table->capacity * sizeof(table->array[0]));
124 table->num_entries = 0;
125 while (remaining_groups) {
126 struct link_group *group = remaining_groups;
127 size_t pos = group->link_group_id % table->capacity;
129 table->num_entries++;
130 group->next = table->array[pos];
131 table->array[pos] = group;
132 remaining_groups = remaining_groups->next;
138 /* Load a dentry tree into the link group table */
139 int load_link_groups(struct link_group_table *table, struct dentry *root)
141 int ret = for_dentry_in_tree(dentry, link_group_table_insert, table);
143 assign_link_groups(table);