summaryrefslogtreecommitdiffstats
path: root/src/doveadm/dsync/dsync-mailbox-tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/doveadm/dsync/dsync-mailbox-tree.c')
-rw-r--r--src/doveadm/dsync/dsync-mailbox-tree.c571
1 files changed, 571 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..e2a86a3
--- /dev/null
+++ b/src/doveadm/dsync/dsync-mailbox-tree.c
@@ -0,0 +1,571 @@
+/* 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->name128_remotesep_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++);
+ 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();
+}
+
+const char *const *
+dsync_mailbox_name_to_parts(const char *name, char hierarchy_sep,
+ char escape_char)
+{
+ const char sep[] = { hierarchy_sep, '\0' };
+ char **parts = p_strsplit(unsafe_data_stack_pool, name, sep);
+ if (escape_char != '\0') {
+ for (unsigned int i = 0; parts[i] != NULL; i++) {
+ mailbox_list_name_unescape((const char **)&parts[i],
+ escape_char);
+ }
+ }
+ return (const char *const *)parts;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-10 02:12:14 +0000