From 0441d265f2bb9da249c7abf333f0f771fadb4ab5 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Mon, 15 Apr 2024 19:36:47 +0200 Subject: Adding upstream version 1:2.3.21+dfsg1. Signed-off-by: Daniel Baumann --- src/lib-storage/mailbox-tree.c | 345 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 345 insertions(+) create mode 100644 src/lib-storage/mailbox-tree.c (limited to 'src/lib-storage/mailbox-tree.c') diff --git a/src/lib-storage/mailbox-tree.c b/src/lib-storage/mailbox-tree.c new file mode 100644 index 0000000..9333fb6 --- /dev/null +++ b/src/lib-storage/mailbox-tree.c @@ -0,0 +1,345 @@ +/* Copyright (c) 2003-2018 Dovecot authors, see the included COPYING file */ + +#include "lib.h" +#include "array.h" +#include "str.h" +#include "mailbox-tree.h" + +struct mailbox_tree_context { + pool_t pool; + char separator; + bool parents_nonexistent; + bool sorted; + unsigned int node_size; + + struct mailbox_node *nodes; +}; + +struct mailbox_tree_iterate_context { + struct mailbox_node *root, *next_node; + unsigned int flags_mask; + + char separator; + + ARRAY(struct mailbox_node *) node_path; + string_t *path_str; + size_t parent_pos; + + bool first_child:1; +}; + +struct mailbox_tree_context *mailbox_tree_init(char separator) +{ + return mailbox_tree_init_size(separator, sizeof(struct mailbox_node)); +} + +struct mailbox_tree_context * +mailbox_tree_init_size(char separator, unsigned int mailbox_node_size) +{ + struct mailbox_tree_context *tree; + + i_assert(mailbox_node_size >= sizeof(struct mailbox_node)); + + tree = i_new(struct mailbox_tree_context, 1); + tree->pool = pool_alloconly_create(MEMPOOL_GROWING"mailbox_tree", 10240); + tree->separator = separator; + tree->node_size = mailbox_node_size; + return tree; +} + +void mailbox_tree_deinit(struct mailbox_tree_context **_tree) +{ + struct mailbox_tree_context *tree = *_tree; + + *_tree = NULL; + pool_unref(&tree->pool); + i_free(tree); +} + +void mailbox_tree_set_separator(struct mailbox_tree_context *tree, + char separator) +{ + tree->separator = separator; +} + +void mailbox_tree_set_parents_nonexistent(struct mailbox_tree_context *tree) +{ + tree->parents_nonexistent = TRUE; +} + +void mailbox_tree_clear(struct mailbox_tree_context *tree) +{ + p_clear(tree->pool); + tree->nodes = NULL; +} + +pool_t mailbox_tree_get_pool(struct mailbox_tree_context *tree) +{ + return tree->pool; +} + +static struct mailbox_node * ATTR_NULL(2) +mailbox_tree_traverse(struct mailbox_tree_context *tree, const char *path, + bool create, bool *created_r) +{ + struct mailbox_node **node, *parent; + const char *name; + string_t *str; + + *created_r = FALSE; + + if (path == NULL) + return tree->nodes; + + if (strncasecmp(path, "INBOX", 5) == 0 && + (path[5] == '\0' || path[5] == tree->separator)) + path = t_strdup_printf("INBOX%s", path+5); + + parent = NULL; + node = &tree->nodes; + + str = t_str_new(strlen(path)+1); + for (name = path;; path++) { + if (*path != tree->separator && *path != '\0') + continue; + + str_truncate(str, 0); + str_append_data(str, name, (size_t) (path - name)); + name = str_c(str); + + /* find the node */ + while (*node != NULL) { + if (strcmp((*node)->name, name) == 0) + break; + + node = &(*node)->next; + } + + if (*node == NULL) { + /* not found, create it */ + if (!create) + break; + + *node = p_malloc(tree->pool, tree->node_size); + (*node)->parent = parent; + (*node)->name = p_strdup(tree->pool, name); + if (tree->parents_nonexistent) + (*node)->flags = MAILBOX_NONEXISTENT; + tree->sorted = FALSE; + *created_r = TRUE; + } + + if (*path == '\0') + break; + + name = path+1; + + parent = *node; + node = &(*node)->children; + } + + return *node; +} + +struct mailbox_node * +mailbox_tree_get(struct mailbox_tree_context *tree, const char *path, + bool *created_r) +{ + struct mailbox_node *node; + bool created; + + T_BEGIN { + node = mailbox_tree_traverse(tree, path, TRUE, &created); + } T_END; + if (created && tree->parents_nonexistent) + node->flags = 0; + + *created_r = created; + return node; +} + +struct mailbox_node * +mailbox_tree_lookup(struct mailbox_tree_context *tree, const char *path) +{ + struct mailbox_node *node; + bool created; + + i_assert(tree != NULL); + + T_BEGIN { + node = mailbox_tree_traverse(tree, path, FALSE, &created); + } T_END; + return node; +} + +struct mailbox_tree_iterate_context * +mailbox_tree_iterate_init(struct mailbox_tree_context *tree, + struct mailbox_node *root, unsigned int flags_mask) +{ + struct mailbox_tree_iterate_context *ctx; + + ctx = i_new(struct mailbox_tree_iterate_context, 1); + ctx->separator = tree->separator; + ctx->root = root != NULL ? root : tree->nodes; + ctx->flags_mask = flags_mask; + ctx->path_str = str_new(default_pool, 256); + i_array_init(&ctx->node_path, 16); + + ctx->next_node = ctx->root; + return ctx; +} + +static void +mailbox_tree_iterate_set_next_node(struct mailbox_tree_iterate_context *ctx) +{ + struct mailbox_node *node = ctx->next_node; + struct mailbox_node *const *nodes; + unsigned int i, count; + + if (node->children != NULL) { + array_push_back(&ctx->node_path, &node); + ctx->parent_pos = str_len(ctx->path_str); + node = node->children; + ctx->first_child = TRUE; + } else if (node->next != NULL) { + node = node->next; + } else { + nodes = array_get(&ctx->node_path, &count); + node = NULL; + for (i = count; i != 0; i--) { + size_t len = strlen(nodes[i-1]->name) + 1; + + i_assert(len <= ctx->parent_pos); + ctx->parent_pos -= len; + if (nodes[i-1]->next != NULL) { + node = nodes[i-1]->next; + ctx->first_child = TRUE; + i--; + + if (ctx->parent_pos != 0) + ctx->parent_pos--; + break; + } + } + array_delete(&ctx->node_path, i, count - i); + } + + ctx->next_node = node; +} + +struct mailbox_node * +mailbox_tree_iterate_next(struct mailbox_tree_iterate_context *ctx, + const char **path_r) +{ + struct mailbox_node *node; + + do { + node = ctx->next_node; + if (node == NULL) + return NULL; + + str_truncate(ctx->path_str, ctx->parent_pos); + if (ctx->first_child) { + ctx->first_child = FALSE; + if (node->parent != NULL) { + str_append_c(ctx->path_str, ctx->separator); + ctx->parent_pos++; + } + } + str_append(ctx->path_str, node->name); + + mailbox_tree_iterate_set_next_node(ctx); + } while ((node->flags & ctx->flags_mask) != ctx->flags_mask); + + *path_r = str_c(ctx->path_str); + return node; +} + +void mailbox_tree_iterate_deinit(struct mailbox_tree_iterate_context **_ctx) +{ + struct mailbox_tree_iterate_context *ctx = *_ctx; + + *_ctx = NULL; + str_free(&ctx->path_str); + array_free(&ctx->node_path); + i_free(ctx); +} + +static struct mailbox_node * ATTR_NULL(1, 2) +mailbox_tree_dup_branch(struct mailbox_tree_context *dest_tree, + struct mailbox_node *dest_parent, + const struct mailbox_node *src) +{ + struct mailbox_node *node, *dest_nodes = NULL, **dest = &dest_nodes; + + for (; src != NULL; src = src->next) { + *dest = node = p_malloc(dest_tree->pool, dest_tree->node_size); + node->name = p_strdup(dest_tree->pool, src->name); + node->flags = src->flags; + + node->parent = dest_parent; + node->children = mailbox_tree_dup_branch(dest_tree, node, + src->children); + dest = &node->next; + } + return dest_nodes; +} + +struct mailbox_tree_context *mailbox_tree_dup(struct mailbox_tree_context *src) +{ + struct mailbox_tree_context *dest; + + /* for now we don't need to support extra data */ + i_assert(src->node_size == sizeof(struct mailbox_node)); + + dest = mailbox_tree_init_size(src->separator, src->node_size); + dest->nodes = mailbox_tree_dup_branch(dest, NULL, src->nodes); + return dest; +} + +static int mailbox_node_name_cmp(struct mailbox_node *const *node1, + struct mailbox_node *const *node2) +{ + return strcmp((*node1)->name, (*node2)->name); +} + +static void mailbox_tree_sort_branch(struct mailbox_node **nodes, + ARRAY_TYPE(mailbox_node) *tmparr) +{ + struct mailbox_node *node, **dest; + + if (*nodes == NULL) + return; + + /* first put the nodes into an array and sort it */ + array_clear(tmparr); + for (node = *nodes; node != NULL; node = node->next) + array_push_back(tmparr, &node); + array_sort(tmparr, mailbox_node_name_cmp); + + /* update the node pointers */ + dest = nodes; + array_foreach_elem(tmparr, node) { + *dest = node; + dest = &(*dest)->next; + } + *dest = NULL; + + /* sort the children */ + for (node = *nodes; node != NULL; node = node->next) + mailbox_tree_sort_branch(&node->children, tmparr); +} + +void mailbox_tree_sort(struct mailbox_tree_context *tree) +{ + if (tree->sorted) + return; + tree->sorted = TRUE; + + T_BEGIN { + ARRAY_TYPE(mailbox_node) tmparr; + + t_array_init(&tmparr, 32); + mailbox_tree_sort_branch(&tree->nodes, &tmparr); + } T_END; +} -- cgit v1.2.3