-#include "rbtree.h"
-
-/* Red-black tree that maps SHA1 message digests of security descriptors to
- * security IDs, which are themselves indices into the table of security
- * descriptors in the 'struct wim_security_data'. */
-struct sd_set {
- struct wim_security_data *sd;
- struct rb_root rb_root;
-};
-
-struct sd_node {
- int security_id;
- u8 hash[SHA1_HASH_SIZE];
- struct rb_node rb_node;
-};
-
-static void free_sd_tree(struct rb_node *node)
-{
- 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. */
-static void destroy_sd_set(struct sd_set *sd_set)
-{
- free_sd_tree(sd_set->rb_root.rb_node);
-}
-
-/* Inserts a a new node into the security descriptor index tree. */
-static void insert_sd_node(struct 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
- wimlib_assert(0); /* Duplicate SHA1 message digest */
- }
- rb_link_node(&new->rb_node, rb_parent, p);
- rb_insert_color(&new->rb_node, root);
-}
-
-/* Returns the index of the security descriptor having a SHA1 message digest of
- * @hash. If not found, return -1. */
-static int lookup_sd(struct 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;
-}