diff options
Diffstat (limited to '')
| -rw-r--r-- | src/doveadm/dsync/dsync-mailbox-tree.c | 554 |
1 files changed, 554 insertions, 0 deletions
diff --git a/src/doveadm/dsync/dsync-mailbox-tree.c b/src/doveadm/dsync/dsync-mailbox-tree.c new file mode 100644 index 0000000..e34f335 --- /dev/null +++ b/src/doveadm/dsync/dsync-mailbox-tree.c @@ -0,0 +1,554 @@ +/* Copyright (c) 2013-2018 Dovecot authors, see the included COPYING file */ + +#include "lib.h" +#include "array.h" +#include "hash.h" +#include "str.h" +#include "sort.h" +#include "mailbox-list-private.h" +#include "dsync-mailbox-tree-private.h" + + +struct dsync_mailbox_tree_iter { + struct dsync_mailbox_tree *tree; + + struct dsync_mailbox_node *cur; + string_t *name; +}; + +struct dsync_mailbox_tree * +dsync_mailbox_tree_init(char sep, char escape_char, char alt_char) +{ + struct dsync_mailbox_tree *tree; + pool_t pool; + + i_assert(sep != '\0'); + i_assert(alt_char != '\0'); + + pool = pool_alloconly_create(MEMPOOL_GROWING"dsync mailbox tree", 4096); + tree = p_new(pool, struct dsync_mailbox_tree, 1); + tree->pool = pool; + tree->sep = tree->sep_str[0] = sep; + tree->escape_char = escape_char; + tree->alt_char = alt_char; + tree->root.name = ""; + i_array_init(&tree->deletes, 32); + return tree; +} + +void dsync_mailbox_tree_deinit(struct dsync_mailbox_tree **_tree) +{ + struct dsync_mailbox_tree *tree = *_tree; + + *_tree = NULL; + hash_table_destroy(&tree->name128_hash); + hash_table_destroy(&tree->guid_hash); + array_free(&tree->deletes); + pool_unref(&tree->pool); +} + +static struct dsync_mailbox_node * +dsync_mailbox_node_find(struct dsync_mailbox_node *nodes, const char *name) +{ + for (; nodes != NULL; nodes = nodes->next) { + if (strcmp(name, nodes->name) == 0) + return nodes; + } + return NULL; +} + +struct dsync_mailbox_node * +dsync_mailbox_tree_lookup(struct dsync_mailbox_tree *tree, + const char *full_name) +{ + struct dsync_mailbox_node *node = &tree->root; + + T_BEGIN { + const char *const *path; + + path = t_strsplit(full_name, tree->sep_str); + for (; *path != NULL && node != NULL; path++) + node = dsync_mailbox_node_find(node->first_child, *path); + } T_END; + return node; +} + +void dsync_mailbox_tree_node_attach(struct dsync_mailbox_node *node, + struct dsync_mailbox_node *parent) +{ + node->parent = parent; + node->next = parent->first_child; + parent->first_child = node; +} + +void dsync_mailbox_tree_node_detach(struct dsync_mailbox_node *node) +{ + struct dsync_mailbox_node **p; + + for (p = &node->parent->first_child;; p = &(*p)->next) { + if (*p == node) { + *p = node->next; + break; + } + } + node->parent = NULL; +} + +struct dsync_mailbox_node * +dsync_mailbox_tree_get(struct dsync_mailbox_tree *tree, const char *full_name) +{ + struct dsync_mailbox_node *parent = NULL, *node = &tree->root; + + i_assert(tree->iter_count == 0); + + T_BEGIN { + const char *const *path; + + /* find the existing part */ + path = t_strsplit(full_name, tree->sep_str); + for (; *path != NULL; path++) { + parent = node; + node = dsync_mailbox_node_find(node->first_child, *path); + if (node == NULL) + break; + } + /* create the rest */ + for (; *path != NULL; path++) { + node = p_new(tree->pool, struct dsync_mailbox_node, 1); + node->name = p_strdup(tree->pool, *path); + node->ns = parent->ns; + dsync_mailbox_tree_node_attach(node, parent); + parent = node; + } + } T_END; + return node; +} + +static void +node_get_full_name_recurse(const struct dsync_mailbox_tree *tree, + const struct dsync_mailbox_node *node, string_t *str) +{ + if (node->parent != &tree->root) + node_get_full_name_recurse(tree, node->parent, str); + + str_append(str, node->name); + str_append_c(str, tree->sep); +} + +const char *dsync_mailbox_node_get_full_name(const struct dsync_mailbox_tree *tree, + const struct dsync_mailbox_node *node) +{ + string_t *str = t_str_new(128); + dsync_mailbox_node_append_full_name(str, tree, node); + return str_c(str); +} + +void dsync_mailbox_node_append_full_name(string_t *str, + const struct dsync_mailbox_tree *tree, + const struct dsync_mailbox_node *node) +{ + i_assert(node->parent != NULL); + + node_get_full_name_recurse(tree, node, str); + /* remove the trailing separator */ + str_truncate(str, str_len(str)-1); +} + +void dsync_mailbox_node_copy_data(struct dsync_mailbox_node *dest, + const struct dsync_mailbox_node *src) +{ + memcpy(dest->mailbox_guid, src->mailbox_guid, + sizeof(dest->mailbox_guid)); + dest->uid_validity = src->uid_validity; + dest->uid_next = src->uid_next; + dest->existence = src->existence; + dest->last_renamed_or_created = src->last_renamed_or_created; + dest->subscribed = src->subscribed; + dest->last_subscription_change = src->last_subscription_change; +} + +struct dsync_mailbox_tree_iter * +dsync_mailbox_tree_iter_init(struct dsync_mailbox_tree *tree) +{ + struct dsync_mailbox_tree_iter *iter; + + iter = i_new(struct dsync_mailbox_tree_iter, 1); + iter->tree = tree; + iter->name = str_new(default_pool, 128); + iter->cur = &tree->root; + + tree->iter_count++; + return iter; +} + +static size_t node_get_full_name_length(struct dsync_mailbox_node *node) +{ + if (node->parent->parent == NULL) + return strlen(node->name); + else { + return strlen(node->name) + 1 + + node_get_full_name_length(node->parent); + } +} + +bool dsync_mailbox_tree_iter_next(struct dsync_mailbox_tree_iter *iter, + const char **full_name_r, + struct dsync_mailbox_node **node_r) +{ + size_t len; + + if (iter->cur->first_child != NULL) + iter->cur = iter->cur->first_child; + else { + while (iter->cur->next == NULL) { + if (iter->cur == &iter->tree->root) + return FALSE; + iter->cur = iter->cur->parent; + } + iter->cur = iter->cur->next; + len = iter->cur->parent == &iter->tree->root ? 0 : + node_get_full_name_length(iter->cur->parent); + str_truncate(iter->name, len); + } + if (str_len(iter->name) > 0) + str_append_c(iter->name, iter->tree->sep); + str_append(iter->name, iter->cur->name); + *full_name_r = str_c(iter->name); + *node_r = iter->cur; + return TRUE; +} + +void dsync_mailbox_tree_iter_deinit(struct dsync_mailbox_tree_iter **_iter) +{ + struct dsync_mailbox_tree_iter *iter = *_iter; + + *_iter = NULL; + + i_assert(iter->tree->iter_count > 0); + iter->tree->iter_count--; + + str_free(&iter->name); + i_free(iter); +} + +void dsync_mailbox_tree_build_name128_hash(struct dsync_mailbox_tree *tree) +{ + struct dsync_mailbox_tree_iter *iter; + struct dsync_mailbox_node *node; + const char *name; + guid_128_t *sha128; + uint8_t *guid_p; + + i_assert(!hash_table_is_created(tree->name128_hash)); + + hash_table_create(&tree->name128_hash, + tree->pool, 0, guid_128_hash, guid_128_cmp); + iter = dsync_mailbox_tree_iter_init(tree); + while (dsync_mailbox_tree_iter_next(iter, &name, &node)) { + sha128 = p_new(tree->pool, guid_128_t, 1); + mailbox_name_get_sha128(name, *sha128); + guid_p = *sha128; + hash_table_insert(tree->name128_hash, guid_p, node); + } + dsync_mailbox_tree_iter_deinit(&iter); +} + +static const char * +convert_name_to_remote_sep(struct dsync_mailbox_tree *tree, const char *name) +{ + string_t *str = t_str_new(128); + + char remote_escape_chars[3] = { + tree->remote_escape_char, + tree->remote_sep, + '\0' + }; + + for (;;) { + const char *end = strchr(name, tree->sep); + const char *name_part = end == NULL ? name : + t_strdup_until(name, end++); + + if (tree->escape_char != '\0') + mailbox_list_name_unescape(&name_part, tree->escape_char); + if (remote_escape_chars[0] != '\0') { + /* The local name can be fully escaped to remote + name and back. */ + mailbox_list_name_escape(name_part, remote_escape_chars, + str); + } else { + /* There is no remote escape char, so for conflicting + separator use the alt_char. */ + for (; *name_part != '\0'; name_part++) { + if (*name_part == tree->remote_sep) + str_append_c(str, tree->alt_char); + else + str_append_c(str, *name_part); + } + } + if (end == NULL) + break; + str_append_c(str, tree->remote_sep); + } + return str_c(str); +} + +static void +dsync_mailbox_tree_build_name128_remotesep_hash(struct dsync_mailbox_tree *tree) +{ + struct dsync_mailbox_tree_iter *iter; + struct dsync_mailbox_node *node; + const char *name; + guid_128_t *sha128; + uint8_t *guid_p; + + i_assert(tree->sep != tree->remote_sep); + i_assert(!hash_table_is_created(tree->name128_remotesep_hash)); + + hash_table_create(&tree->name128_remotesep_hash, tree->pool, 0, + guid_128_hash, guid_128_cmp); + iter = dsync_mailbox_tree_iter_init(tree); + while (dsync_mailbox_tree_iter_next(iter, &name, &node)) { + sha128 = p_new(tree->pool, guid_128_t, 1); + T_BEGIN { + const char *remote_name = + convert_name_to_remote_sep(tree, name); + mailbox_name_get_sha128(remote_name, *sha128); + } T_END; + guid_p = *sha128; + hash_table_insert(tree->name128_remotesep_hash, guid_p, node); + } + dsync_mailbox_tree_iter_deinit(&iter); +} + +int dsync_mailbox_tree_guid_hash_add(struct dsync_mailbox_tree *tree, + struct dsync_mailbox_node *node, + struct dsync_mailbox_node **old_node_r) +{ + struct dsync_mailbox_node *old_node; + uint8_t *guid = node->mailbox_guid; + + if (guid_128_is_empty(node->mailbox_guid)) + return 0; + + *old_node_r = old_node = hash_table_lookup(tree->guid_hash, guid); + if (old_node == NULL) + hash_table_insert(tree->guid_hash, guid, node); + else if (old_node != node) + return -1; + return 0; +} + +int dsync_mailbox_tree_build_guid_hash(struct dsync_mailbox_tree *tree, + struct dsync_mailbox_node **dup_node1_r, + struct dsync_mailbox_node **dup_node2_r) +{ + struct dsync_mailbox_tree_iter *iter; + struct dsync_mailbox_node *node, *old_node; + const char *name; + int ret = 0; + + if (!hash_table_is_created(tree->guid_hash)) { + hash_table_create(&tree->guid_hash, tree->pool, 0, + guid_128_hash, guid_128_cmp); + } + iter = dsync_mailbox_tree_iter_init(tree); + while (dsync_mailbox_tree_iter_next(iter, &name, &node)) { + if (dsync_mailbox_tree_guid_hash_add(tree, node, &old_node) < 0) { + *dup_node1_r = node; + *dup_node2_r = old_node; + ret = -1; + } + } + dsync_mailbox_tree_iter_deinit(&iter); + return ret; +} + +struct dsync_mailbox_node * +dsync_mailbox_tree_lookup_guid(struct dsync_mailbox_tree *tree, + const guid_128_t guid) +{ + const uint8_t *guid_p = guid; + + return hash_table_lookup(tree->guid_hash, guid_p); +} + +const struct dsync_mailbox_delete * +dsync_mailbox_tree_get_deletes(struct dsync_mailbox_tree *tree, + unsigned int *count_r) +{ + return array_get(&tree->deletes, count_r); +} + +struct dsync_mailbox_node * +dsync_mailbox_tree_find_delete(struct dsync_mailbox_tree *tree, + const struct dsync_mailbox_delete *del) +{ + const uint8_t *guid_p = del->guid; + + i_assert(hash_table_is_created(tree->guid_hash)); + i_assert(tree->remote_sep != '\0'); + + if (del->type == DSYNC_MAILBOX_DELETE_TYPE_MAILBOX) { + /* find node by GUID */ + return hash_table_lookup(tree->guid_hash, guid_p); + } + + /* find node by name. this is a bit tricky, since the hierarchy + separator may differ from ours. */ + if (tree->sep == tree->remote_sep) { + if (!hash_table_is_created(tree->name128_hash)) + dsync_mailbox_tree_build_name128_hash(tree); + return hash_table_lookup(tree->name128_hash, guid_p); + } else { + if (!hash_table_is_created(tree->name128_remotesep_hash)) + dsync_mailbox_tree_build_name128_remotesep_hash(tree); + return hash_table_lookup(tree->name128_remotesep_hash, guid_p); + } +} + +void dsync_mailbox_tree_set_remote_chars(struct dsync_mailbox_tree *tree, + char remote_sep, char escape_char) +{ + i_assert(tree->remote_sep == '\0'); + i_assert(tree->remote_escape_char == '\0'); + + tree->remote_sep = remote_sep; + tree->remote_escape_char = escape_char; +} + +static void +dsync_mailbox_tree_dup_nodes(struct dsync_mailbox_tree *dest_tree, + const struct dsync_mailbox_node *src, + string_t *path) +{ + size_t prefix_len = str_len(path); + struct dsync_mailbox_node *node; + + if (prefix_len > 0) { + str_append_c(path, dest_tree->sep); + prefix_len++; + } + for (; src != NULL; src = src->next) { + str_truncate(path, prefix_len); + str_append(path, src->name); + node = dsync_mailbox_tree_get(dest_tree, str_c(path)); + + node->ns = src->ns; + memcpy(node->mailbox_guid, src->mailbox_guid, + sizeof(node->mailbox_guid)); + node->uid_validity = src->uid_validity; + node->uid_next = src->uid_next; + node->existence = src->existence; + node->last_renamed_or_created = src->last_renamed_or_created; + node->subscribed = src->subscribed; + node->last_subscription_change = src->last_subscription_change; + + if (src->first_child != NULL) { + dsync_mailbox_tree_dup_nodes(dest_tree, + src->first_child, path); + } + } +} + +struct dsync_mailbox_tree * +dsync_mailbox_tree_dup(const struct dsync_mailbox_tree *src) +{ + struct dsync_mailbox_tree *dest; + string_t *str = t_str_new(128); + + dest = dsync_mailbox_tree_init(src->sep, src->escape_char, + src->alt_char); + dsync_mailbox_tree_dup_nodes(dest, &src->root, str); + return dest; +} + +int dsync_mailbox_node_name_cmp(struct dsync_mailbox_node *const *n1, + struct dsync_mailbox_node *const *n2) +{ + return strcmp((*n1)->name, (*n2)->name); +} + +static bool +dsync_mailbox_nodes_equal(const struct dsync_mailbox_node *node1, + const struct dsync_mailbox_node *node2) +{ + return strcmp(node1->name, node2->name) == 0 && + node1->ns == node2->ns && + memcmp(node1->mailbox_guid, node2->mailbox_guid, + sizeof(node1->mailbox_guid)) == 0 && + node1->uid_validity == node2->uid_validity && + node1->existence == node2->existence && + node1->subscribed == node2->subscribed; +} + +static bool +dsync_mailbox_branches_equal(struct dsync_mailbox_node *node1, + struct dsync_mailbox_node *node2) +{ + /* this function is used only for unit tests, so performance doesn't + really matter */ + struct dsync_mailbox_node *n, **snodes1, **snodes2; + unsigned int i, count; + + for (n = node1, count = 0; n != NULL; n = n->next) count++; + for (n = node2, i = 0; n != NULL; n = n->next) i++; + if (i != count) + return FALSE; + if (count == 0) + return TRUE; + + /* sort the trees by name */ + snodes1 = t_new(struct dsync_mailbox_node *, count); + snodes2 = t_new(struct dsync_mailbox_node *, count); + for (n = node1, i = 0; n != NULL; n = n->next, i++) + snodes1[i] = n; + for (n = node2, i = 0; n != NULL; n = n->next, i++) + snodes2[i] = n; + i_qsort(snodes1, count, sizeof(*snodes1), dsync_mailbox_node_name_cmp); + i_qsort(snodes2, count, sizeof(*snodes2), dsync_mailbox_node_name_cmp); + + for (i = 0; i < count; i++) { + if (!dsync_mailbox_nodes_equal(snodes1[i], snodes2[i])) + return FALSE; + if (!dsync_mailbox_branches_equal(snodes1[i]->first_child, + snodes2[i]->first_child)) + return FALSE; + } + return TRUE; +} + +bool dsync_mailbox_trees_equal(struct dsync_mailbox_tree *tree1, + struct dsync_mailbox_tree *tree2) +{ + bool ret; + + T_BEGIN { + ret = dsync_mailbox_branches_equal(&tree1->root, &tree2->root); + } T_END; + return ret; +} + +const char *dsync_mailbox_node_to_string(const struct dsync_mailbox_node *node) +{ + return t_strdup_printf("guid=%s uid_validity=%u uid_next=%u subs=%s last_change=%ld last_subs=%ld", + guid_128_to_string(node->mailbox_guid), + node->uid_validity, node->uid_next, + node->subscribed ? "yes" : "no", + (long)node->last_renamed_or_created, + (long)node->last_subscription_change); +} + +const char * +dsync_mailbox_delete_type_to_string(enum dsync_mailbox_delete_type type) +{ + switch (type) { + case DSYNC_MAILBOX_DELETE_TYPE_MAILBOX: + return "mailbox"; + case DSYNC_MAILBOX_DELETE_TYPE_DIR: + return "dir"; + case DSYNC_MAILBOX_DELETE_TYPE_UNSUBSCRIBE: + return "unsubscribe"; + } + i_unreached(); +} |