a5d8b9fae05fae57f56dae0fab55262bcb9456ef
[wimlib] / src / hardlink.c
1 #include "wimlib_internal.h"
2 #include "dentry.h"
3 #include "list.h"
4 #include "lookup_table.h"
5
6 struct link_group {
7         u64 link_group_id;
8         struct link_group *next;
9         struct list_head dentry_list;
10 };
11
12 struct link_group_table {
13         struct link_group **array;
14         u64 num_entries;
15         u64 capacity;
16 };
17
18 #include <sys/mman.h>
19
20 struct link_group_table *new_link_group_table(u64 capacity)
21 {
22         return (struct link_group_table*)new_lookup_table(capacity);
23 }
24
25 /* Insert a dentry into the hard link group table based on its hard link group
26  * ID.
27  *
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.
30  *
31  * If the hard link group ID is 0, this is a no-op and the dentry is not
32  * inserted.
33  */
34 int link_group_table_insert(struct dentry *dentry, struct link_group_table *table)
35 {
36         size_t pos;
37         struct link_group *group;
38
39         if (dentry->hard_link == 0) {
40                 INIT_LIST_HEAD(&dentry->link_group_list);
41                 return 0;
42         }
43
44         /* Try adding to existing hard link group */
45         pos = dentry->hard_link % table->capacity;
46         group = table->array[pos];
47         while (group) {
48                 if (group->link_group_id == dentry->hard_link) {
49                         list_add(&dentry->link_group_list, &group->dentry_list);
50                         return 0;
51                 }
52                 group = group->next;
53         }
54
55         /* Add new hard link group to the table */
56
57         group = MALLOC(sizeof(struct link_group));
58         if (!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;
65
66         /* XXX Make the table grow when too many entries have been inserted. */
67         table->num_entries++;
68         return 0;
69 }
70
71 /* Frees a link group table. */
72 void free_link_group_table(struct link_group_table *table)
73 {
74         if (!table)
75                 return;
76         if (table->array) {
77                 for (u64 i = 0; i < table->capacity; i++) {
78                         struct link_group *group = table->array[i];
79                         struct link_group *next;
80                         while (group) {
81                                 next = group->next;
82                                 FREE(group);
83                                 group = next;
84                         }
85                 }
86                 FREE(table->array);
87         }
88         FREE(table);
89 }
90
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)
94 {
95         struct link_group *remaining_groups = NULL;
96         u64 id = 1;
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;
101                 while (group) {
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,
107                                                       struct dentry,
108                                                       link_group_list);
109                                 dentry->hard_link = 0;
110                                 FREE(group);
111                         } else {
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,
117                                                     link_group_list)
118                                         dentry->hard_link = id;
119                                 group->next = remaining_groups;
120                                 remaining_groups = group;
121                                 id++;
122                         }
123                         group = next_group;
124                 }
125         }
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;
131
132                 table->num_entries++;
133                 group->next = table->array[pos];
134                 table->array[pos] = group;
135                 remaining_groups = remaining_groups->next;
136         }
137         return id;
138 }
139
140 #if 0
141 /* Load a dentry tree into the link group table */
142 int load_link_groups(struct link_group_table *table, struct dentry *root)
143 {
144         int ret = for_dentry_in_tree(dentry, link_group_table_insert, table);
145         if (ret == 0)
146                 assign_link_groups(table);
147         return ret;
148 }
149 #endif