wimlib.net Git - wimlib/blob - 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 *link_group_head;
  10 };
  11
  12 struct link_group_table {
  13         struct link_group **array;
  14         u64 num_entries;
  15         u64 capacity;
  16 };
  17
  18
  19 struct link_group_table *new_link_group_table(u64 capacity)
  20 {
  21         return (struct link_group_table*)new_lookup_table(capacity);
  22 }
  23
  24 /* Insert a dentry into the hard link group table based on its hard link group
  25  * ID.
  26  *
  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.
  29  *
  30  * If the hard link group ID is 0, this is a no-op and the dentry is not
  31  * inserted.
  32  */
  33 int link_group_table_insert(struct dentry *dentry, struct link_group_table *table)
  34 {
  35         size_t pos;
  36         struct link_group *group;
  37
  38         if (dentry->hard_link == 0)
  39                 return 0;
  40
  41         /* Try adding to existing hard link group */
  42         pos = dentry->hard_link % table->capacity;
  43         group = table->array[pos];
  44         while (group) {
  45                 if (group->link_group_id == dentry->hard_link) {
  46                         list_add(&dentry->link_group_list, group->link_group_head);
  47                         return 0;
  48                 }
  49                 group = group->next;
  50         }
  51
  52         /* Add new hard link group to the table */
  53
  54         group = MALLOC(sizeof(struct link_group));
  55         if (!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;
  62
  63         /* XXX Make the table grow when too many entries have been inserted. */
  64         table->num_entries++;
  65         return 0;
  66 }
  67
  68 /* Frees a link group table. */
  69 void free_link_group_table(struct link_group_table *table)
  70 {
  71         if (!table)
  72                 return;
  73         if (table->array) {
  74                 for (u64 i = 0; i < table->capacity; i++) {
  75                         struct link_group *group = table->array[i];
  76                         struct link_group *next;
  77                         while (group) {
  78                                 next = group->next;
  79                                 FREE(group);
  80                                 group = next;
  81                         }
  82                 }
  83                 FREE(table->array);
  84         }
  85         FREE(table);
  86 }
  87
  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)
  91 {
  92         struct link_group *remaining_groups = NULL;
  93         u64 id = 1;
  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;
  98                 while (group) {
  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,
 104                                                       struct dentry,
 105                                                       link_group_list);
 106                                 dentry->hard_link = 0;
 107                                 FREE(group);
 108                         } else {
 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,
 114                                                     link_group_list)
 115                                         dentry->hard_link = id;
 116                                 group->next = remaining_groups;
 117                                 remaining_groups = group;
 118                                 id++;
 119                         }
 120                         group = next_group;
 121                 }
 122         }
 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;
 128
 129                 table->num_entries++;
 130                 group->next = table->array[pos];
 131                 table->array[pos] = group;
 132                 remaining_groups = remaining_groups->next;
 133         }
 134         return id;
 135 }
 136
 137 #if 0
 138 /* Load a dentry tree into the link group table */
 139 int load_link_groups(struct link_group_table *table, struct dentry *root)
 140 {
 141         int ret = for_dentry_in_tree(dentry, link_group_table_insert, table);
 142         if (ret == 0)
 143                 assign_link_groups(table);
 144         return ret;
 145 }
 146 #endif