+ if (node) {
+ free_sd_tree(node->rb_left);
+ free_sd_tree(node->rb_right);
+ FREE(container_of(node, struct sd_node, rb_node));
+ }
+}
+
+/* Frees a security descriptor index set. */
+void
+destroy_sd_set(struct wim_sd_set *sd_set, bool rollback)
+{
+ if (rollback) {
+ struct wim_security_data *sd = sd_set->sd;
+ u8 **descriptors = sd->descriptors + sd_set->orig_num_entries;
+ u32 num_entries = sd->num_entries - sd_set->orig_num_entries;
+ while (num_entries--)
+ FREE(*descriptors++);
+ sd->num_entries = sd_set->orig_num_entries;
+ }
+ free_sd_tree(sd_set->rb_root.rb_node);
+}
+
+/* Inserts a a new node into the security descriptor index tree. */
+static bool
+insert_sd_node(struct wim_sd_set *set, struct sd_node *new)
+{
+ struct rb_root *root = &set->rb_root;
+ struct rb_node **p = &(root->rb_node);
+ struct rb_node *rb_parent = NULL;
+
+ while (*p) {
+ struct sd_node *this = container_of(*p, struct sd_node, rb_node);
+ int cmp = hashes_cmp(new->hash, this->hash);
+
+ rb_parent = *p;
+ if (cmp < 0)
+ p = &((*p)->rb_left);
+ else if (cmp > 0)
+ p = &((*p)->rb_right);
+ else
+ return false; /* Duplicate security descriptor */
+ }
+ rb_link_node(&new->rb_node, rb_parent, p);
+ rb_insert_color(&new->rb_node, root);
+ return true;
+}
+
+/* Returns the index of the security descriptor having a SHA1 message digest of
+ * @hash. If not found, return -1. */
+int
+lookup_sd(struct wim_sd_set *set, const u8 hash[SHA1_HASH_SIZE])
+{
+ struct rb_node *node = set->rb_root.rb_node;
+
+ while (node) {
+ struct sd_node *sd_node = container_of(node, struct sd_node, rb_node);
+ int cmp = hashes_cmp(hash, sd_node->hash);
+ if (cmp < 0)
+ node = node->rb_left;
+ else if (cmp > 0)
+ node = node->rb_right;
+ else
+ return sd_node->security_id;
+ }
+ return -1;
+}
+
+/*
+ * Adds a security descriptor to the indexed security descriptor set as well as
+ * the corresponding `struct wim_security_data', and returns the new security
+ * ID; or, if there is an existing security descriptor that is the same, return
+ * the security ID for it. If a new security descriptor cannot be allocated,
+ * return -1.
+ */
+int
+sd_set_add_sd(struct wim_sd_set *sd_set, const char *descriptor, size_t size)
+{
+ u8 hash[SHA1_HASH_SIZE];
+ int security_id;
+ struct sd_node *new;
+ u8 **descriptors;
+ u64 *sizes;
+ u8 *descr_copy;
+ struct wim_security_data *sd;
+ bool bret;
+
+ sha1_buffer(descriptor, size, hash);
+
+ security_id = lookup_sd(sd_set, hash);
+ if (security_id >= 0) /* Identical descriptor already exists */
+ goto out;
+
+ /* Need to add a new security descriptor */
+ security_id = -1;
+
+ new = MALLOC(sizeof(*new));
+ if (!new)
+ goto out;
+
+ descr_copy = memdup(descriptor, size);
+ if (!descr_copy)
+ goto out_free_node;
+
+ sd = sd_set->sd;
+ new->security_id = sd->num_entries;
+ copy_hash(new->hash, hash);
+
+ /* There typically are only a few dozen security descriptors in a
+ * directory tree, so expanding the array of security descriptors by
+ * only 1 extra space each time should not be a problem. */
+ descriptors = REALLOC(sd->descriptors,
+ (sd->num_entries + 1) * sizeof(sd->descriptors[0]));
+ if (!descriptors)
+ goto out_free_descr;
+ sd->descriptors = descriptors;
+ sizes = REALLOC(sd->sizes,
+ (sd->num_entries + 1) * sizeof(sd->sizes[0]));
+ if (!sizes)
+ goto out_free_descr;
+ sd->sizes = sizes;
+ sd->descriptors[sd->num_entries] = descr_copy;
+ sd->sizes[sd->num_entries] = size;
+ sd->num_entries++;
+ DEBUG("There are now %u security descriptors", sd->num_entries);
+ bret = insert_sd_node(sd_set, new);
+ wimlib_assert(bret);
+ security_id = new->security_id;
+ goto out;
+out_free_descr:
+ FREE(descr_copy);
+out_free_node:
+ FREE(new);
+out:
+ return security_id;