1 /* Copyright (c) 2003-2018 Dovecot authors, see the included COPYING file */
2
3 #include "lib.h"
4 #include "array.h"
5 #include "str.h"
6 #include "mailbox-tree.h"
7
8 struct mailbox_tree_context {
9 pool_t pool;
10 char separator;
11 bool parents_nonexistent;
12 bool sorted;
13 unsigned int node_size;
14
15 struct mailbox_node *nodes;
16 };
17
18 struct mailbox_tree_iterate_context {
19 struct mailbox_node *root, *next_node;
20 unsigned int flags_mask;
21
22 char separator;
23
24 ARRAY(struct mailbox_node *) node_path;
25 string_t *path_str;
26 size_t parent_pos;
27
28 bool first_child:1;
29 };
30
mailbox_tree_init(char separator)31 struct mailbox_tree_context *mailbox_tree_init(char separator)
32 {
33 return mailbox_tree_init_size(separator, sizeof(struct mailbox_node));
34 }
35
36 struct mailbox_tree_context *
mailbox_tree_init_size(char separator,unsigned int mailbox_node_size)37 mailbox_tree_init_size(char separator, unsigned int mailbox_node_size)
38 {
39 struct mailbox_tree_context *tree;
40
41 i_assert(mailbox_node_size >= sizeof(struct mailbox_node));
42
43 tree = i_new(struct mailbox_tree_context, 1);
44 tree->pool = pool_alloconly_create(MEMPOOL_GROWING"mailbox_tree", 10240);
45 tree->separator = separator;
46 tree->node_size = mailbox_node_size;
47 return tree;
48 }
49
mailbox_tree_deinit(struct mailbox_tree_context ** _tree)50 void mailbox_tree_deinit(struct mailbox_tree_context **_tree)
51 {
52 struct mailbox_tree_context *tree = *_tree;
53
54 *_tree = NULL;
55 pool_unref(&tree->pool);
56 i_free(tree);
57 }
58
mailbox_tree_set_separator(struct mailbox_tree_context * tree,char separator)59 void mailbox_tree_set_separator(struct mailbox_tree_context *tree,
60 char separator)
61 {
62 tree->separator = separator;
63 }
64
mailbox_tree_set_parents_nonexistent(struct mailbox_tree_context * tree)65 void mailbox_tree_set_parents_nonexistent(struct mailbox_tree_context *tree)
66 {
67 tree->parents_nonexistent = TRUE;
68 }
69
mailbox_tree_clear(struct mailbox_tree_context * tree)70 void mailbox_tree_clear(struct mailbox_tree_context *tree)
71 {
72 p_clear(tree->pool);
73 tree->nodes = NULL;
74 }
75
mailbox_tree_get_pool(struct mailbox_tree_context * tree)76 pool_t mailbox_tree_get_pool(struct mailbox_tree_context *tree)
77 {
78 return tree->pool;
79 }
80
81 static struct mailbox_node * ATTR_NULL(2)
mailbox_tree_traverse(struct mailbox_tree_context * tree,const char * path,bool create,bool * created_r)82 mailbox_tree_traverse(struct mailbox_tree_context *tree, const char *path,
83 bool create, bool *created_r)
84 {
85 struct mailbox_node **node, *parent;
86 const char *name;
87 string_t *str;
88
89 *created_r = FALSE;
90
91 if (path == NULL)
92 return tree->nodes;
93
94 if (strncasecmp(path, "INBOX", 5) == 0 &&
95 (path[5] == '\0' || path[5] == tree->separator))
96 path = t_strdup_printf("INBOX%s", path+5);
97
98 parent = NULL;
99 node = &tree->nodes;
100
101 str = t_str_new(strlen(path)+1);
102 for (name = path;; path++) {
103 if (*path != tree->separator && *path != '\0')
104 continue;
105
106 str_truncate(str, 0);
107 str_append_data(str, name, (size_t) (path - name));
108 name = str_c(str);
109
110 /* find the node */
111 while (*node != NULL) {
112 if (strcmp((*node)->name, name) == 0)
113 break;
114
115 node = &(*node)->next;
116 }
117
118 if (*node == NULL) {
119 /* not found, create it */
120 if (!create)
121 break;
122
123 *node = p_malloc(tree->pool, tree->node_size);
124 (*node)->parent = parent;
125 (*node)->name = p_strdup(tree->pool, name);
126 if (tree->parents_nonexistent)
127 (*node)->flags = MAILBOX_NONEXISTENT;
128 tree->sorted = FALSE;
129 *created_r = TRUE;
130 }
131
132 if (*path == '\0')
133 break;
134
135 name = path+1;
136
137 parent = *node;
138 node = &(*node)->children;
139 }
140
141 return *node;
142 }
143
144 struct mailbox_node *
mailbox_tree_get(struct mailbox_tree_context * tree,const char * path,bool * created_r)145 mailbox_tree_get(struct mailbox_tree_context *tree, const char *path,
146 bool *created_r)
147 {
148 struct mailbox_node *node;
149 bool created;
150
151 T_BEGIN {
152 node = mailbox_tree_traverse(tree, path, TRUE, &created);
153 } T_END;
154 if (created && tree->parents_nonexistent)
155 node->flags = 0;
156
157 *created_r = created;
158 return node;
159 }
160
161 struct mailbox_node *
mailbox_tree_lookup(struct mailbox_tree_context * tree,const char * path)162 mailbox_tree_lookup(struct mailbox_tree_context *tree, const char *path)
163 {
164 struct mailbox_node *node;
165 bool created;
166
167 i_assert(tree != NULL);
168
169 T_BEGIN {
170 node = mailbox_tree_traverse(tree, path, FALSE, &created);
171 } T_END;
172 return node;
173 }
174
175 struct mailbox_tree_iterate_context *
mailbox_tree_iterate_init(struct mailbox_tree_context * tree,struct mailbox_node * root,unsigned int flags_mask)176 mailbox_tree_iterate_init(struct mailbox_tree_context *tree,
177 struct mailbox_node *root, unsigned int flags_mask)
178 {
179 struct mailbox_tree_iterate_context *ctx;
180
181 ctx = i_new(struct mailbox_tree_iterate_context, 1);
182 ctx->separator = tree->separator;
183 ctx->root = root != NULL ? root : tree->nodes;
184 ctx->flags_mask = flags_mask;
185 ctx->path_str = str_new(default_pool, 256);
186 i_array_init(&ctx->node_path, 16);
187
188 ctx->next_node = ctx->root;
189 return ctx;
190 }
191
192 static void
mailbox_tree_iterate_set_next_node(struct mailbox_tree_iterate_context * ctx)193 mailbox_tree_iterate_set_next_node(struct mailbox_tree_iterate_context *ctx)
194 {
195 struct mailbox_node *node = ctx->next_node;
196 struct mailbox_node *const *nodes;
197 unsigned int i, count;
198
199 if (node->children != NULL) {
200 array_push_back(&ctx->node_path, &node);
201 ctx->parent_pos = str_len(ctx->path_str);
202 node = node->children;
203 ctx->first_child = TRUE;
204 } else if (node->next != NULL) {
205 node = node->next;
206 } else {
207 nodes = array_get(&ctx->node_path, &count);
208 node = NULL;
209 for (i = count; i != 0; i--) {
210 size_t len = strlen(nodes[i-1]->name) + 1;
211
212 i_assert(len <= ctx->parent_pos);
213 ctx->parent_pos -= len;
214 if (nodes[i-1]->next != NULL) {
215 node = nodes[i-1]->next;
216 ctx->first_child = TRUE;
217 i--;
218
219 if (ctx->parent_pos != 0)
220 ctx->parent_pos--;
221 break;
222 }
223 }
224 array_delete(&ctx->node_path, i, count - i);
225 }
226
227 ctx->next_node = node;
228 }
229
230 struct mailbox_node *
mailbox_tree_iterate_next(struct mailbox_tree_iterate_context * ctx,const char ** path_r)231 mailbox_tree_iterate_next(struct mailbox_tree_iterate_context *ctx,
232 const char **path_r)
233 {
234 struct mailbox_node *node;
235
236 do {
237 node = ctx->next_node;
238 if (node == NULL)
239 return NULL;
240
241 str_truncate(ctx->path_str, ctx->parent_pos);
242 if (ctx->first_child) {
243 ctx->first_child = FALSE;
244 if (node->parent != NULL) {
245 str_append_c(ctx->path_str, ctx->separator);
246 ctx->parent_pos++;
247 }
248 }
249 str_append(ctx->path_str, node->name);
250
251 mailbox_tree_iterate_set_next_node(ctx);
252 } while ((node->flags & ctx->flags_mask) != ctx->flags_mask);
253
254 *path_r = str_c(ctx->path_str);
255 return node;
256 }
257
mailbox_tree_iterate_deinit(struct mailbox_tree_iterate_context ** _ctx)258 void mailbox_tree_iterate_deinit(struct mailbox_tree_iterate_context **_ctx)
259 {
260 struct mailbox_tree_iterate_context *ctx = *_ctx;
261
262 *_ctx = NULL;
263 str_free(&ctx->path_str);
264 array_free(&ctx->node_path);
265 i_free(ctx);
266 }
267
268 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)269 mailbox_tree_dup_branch(struct mailbox_tree_context *dest_tree,
270 struct mailbox_node *dest_parent,
271 const struct mailbox_node *src)
272 {
273 struct mailbox_node *node, *dest_nodes = NULL, **dest = &dest_nodes;
274
275 for (; src != NULL; src = src->next) {
276 *dest = node = p_malloc(dest_tree->pool, dest_tree->node_size);
277 node->name = p_strdup(dest_tree->pool, src->name);
278 node->flags = src->flags;
279
280 node->parent = dest_parent;
281 node->children = mailbox_tree_dup_branch(dest_tree, node,
282 src->children);
283 dest = &node->next;
284 }
285 return dest_nodes;
286 }
287
mailbox_tree_dup(struct mailbox_tree_context * src)288 struct mailbox_tree_context *mailbox_tree_dup(struct mailbox_tree_context *src)
289 {
290 struct mailbox_tree_context *dest;
291
292 /* for now we don't need to support extra data */
293 i_assert(src->node_size == sizeof(struct mailbox_node));
294
295 dest = mailbox_tree_init_size(src->separator, src->node_size);
296 dest->nodes = mailbox_tree_dup_branch(dest, NULL, src->nodes);
297 return dest;
298 }
299
mailbox_node_name_cmp(struct mailbox_node * const * node1,struct mailbox_node * const * node2)300 static int mailbox_node_name_cmp(struct mailbox_node *const *node1,
301 struct mailbox_node *const *node2)
302 {
303 return strcmp((*node1)->name, (*node2)->name);
304 }
305
mailbox_tree_sort_branch(struct mailbox_node ** nodes,ARRAY_TYPE (mailbox_node)* tmparr)306 static void mailbox_tree_sort_branch(struct mailbox_node **nodes,
307 ARRAY_TYPE(mailbox_node) *tmparr)
308 {
309 struct mailbox_node *node, **dest;
310
311 if (*nodes == NULL)
312 return;
313
314 /* first put the nodes into an array and sort it */
315 array_clear(tmparr);
316 for (node = *nodes; node != NULL; node = node->next)
317 array_push_back(tmparr, &node);
318 array_sort(tmparr, mailbox_node_name_cmp);
319
320 /* update the node pointers */
321 dest = nodes;
322 array_foreach_elem(tmparr, node) {
323 *dest = node;
324 dest = &(*dest)->next;
325 }
326 *dest = NULL;
327
328 /* sort the children */
329 for (node = *nodes; node != NULL; node = node->next)
330 mailbox_tree_sort_branch(&node->children, tmparr);
331 }
332
mailbox_tree_sort(struct mailbox_tree_context * tree)333 void mailbox_tree_sort(struct mailbox_tree_context *tree)
334 {
335 if (tree->sorted)
336 return;
337 tree->sorted = TRUE;
338
339 T_BEGIN {
340 ARRAY_TYPE(mailbox_node) tmparr;
341
342 t_array_init(&tmparr, 32);
343 mailbox_tree_sort_branch(&tree->nodes, &tmparr);
344 } T_END;
345 }
346