summaryrefslogtreecommitdiffstats
path: root/src/lib-storage/index/index-thread-links.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/lib-storage/index/index-thread-links.c242
1 files changed, 242 insertions, 0 deletions
diff --git a/src/lib-storage/index/index-thread-links.c b/src/lib-storage/index/index-thread-links.c
new file mode 100644
index 0000000..9affb83
--- /dev/null
+++ b/src/lib-storage/index/index-thread-links.c
@@ -0,0 +1,242 @@
+/* Copyright (c) 2002-2018 Dovecot authors, see the included COPYING file */
+
+#include "lib.h"
+#include "array.h"
+#include "message-id.h"
+#include "mail-storage.h"
+#include "index-thread-private.h"
+
+static uint32_t thread_msg_add(struct mail_thread_cache *cache,
+ uint32_t uid, uint32_t msgid_idx)
+{
+ struct mail_thread_node *node;
+
+ i_assert(msgid_idx != 0);
+ i_assert(msgid_idx < cache->first_invalid_msgid_str_idx);
+
+ node = array_idx_get_space(&cache->thread_nodes, msgid_idx);
+ if (node->uid == 0)
+ node->uid = uid;
+ else {
+ /* duplicate message-id, keep the original.
+ if the original ever gets expunged, rebuild. */
+ node->expunge_rebuilds = TRUE;
+
+ msgid_idx = cache->next_invalid_msgid_str_idx++;
+ node = array_idx_get_space(&cache->thread_nodes, msgid_idx);
+ node->uid = uid;
+ }
+ return msgid_idx;
+}
+
+static bool thread_node_has_ancestor(struct mail_thread_cache *cache,
+ const struct mail_thread_node *node,
+ const struct mail_thread_node *ancestor)
+{
+ while (node != ancestor) {
+ if (node->parent_idx == 0)
+ return FALSE;
+
+ node = array_idx(&cache->thread_nodes, node->parent_idx);
+ }
+ return TRUE;
+}
+
+static void thread_link_reference(struct mail_thread_cache *cache,
+ uint32_t parent_idx, uint32_t child_idx)
+{
+ struct mail_thread_node *node, *parent, *child;
+ uint32_t idx;
+
+ i_assert(parent_idx < cache->first_invalid_msgid_str_idx);
+
+ /* either child_idx or parent_idx may cause thread_nodes array to
+ grow. in such situation the other pointer may become invalid if
+ we don't get the pointers in correct order. */
+ if (child_idx < parent_idx) {
+ parent = array_idx_get_space(&cache->thread_nodes, parent_idx);
+ child = array_idx_modifiable(&cache->thread_nodes, child_idx);
+ } else {
+ child = array_idx_get_space(&cache->thread_nodes, child_idx);
+ parent = array_idx_modifiable(&cache->thread_nodes, parent_idx);
+ }
+
+ child->parent_link_refcount++;
+ if (thread_node_has_ancestor(cache, parent, child)) {
+ if (parent == child) {
+ /* loops to itself - ignore */
+ return;
+ }
+
+ /* child is an ancestor of parent. Adding child -> parent_node
+ would introduce a loop. If any messages referencing the path
+ between parent_node's parent and child_node get expunged, we
+ have to rebuild the tree because the loop might break.
+ For example:
+
+ #1: a -> b (a.ref=1, b.ref=1)
+ #2: b -> a (a.ref=2, b.ref=2)
+ #3: c -> a -> b (a.ref=3, b.ref=3, c.ref=1)
+
+ Expunging #3 wouldn't break the loop, but expunging #1
+ would. */
+ node = parent;
+ do {
+ idx = node->parent_idx;
+ i_assert(idx != 0);
+ node = array_idx_modifiable(&cache->thread_nodes, idx);
+ node->child_unref_rebuilds = TRUE;
+ } while (node != child);
+ return;
+ } else if (child->parent_idx == parent_idx) {
+ /* The same link already exists */
+ return;
+ }
+
+ /* Set parent_node as child_node's parent */
+ if (child->parent_idx == 0) {
+ child->parent_idx = parent_idx;
+ } else {
+ /* Conflicting parent already exists, keep the original */
+ if (MAIL_THREAD_NODE_EXISTS(child)) {
+ /* If this message gets expunged,
+ the parent is changed. */
+ child->expunge_rebuilds = TRUE;
+ } else {
+ /* Message doesn't exist, so it was one of the node's
+ children that created the original reference. If
+ that reference gets dropped, the parent is changed.
+ We could catch this in one of several ways:
+
+ a) Link to parent node gets unreferenced
+ b) Link to this node gets unreferenced
+ c) Any of the child nodes gets expunged
+
+ b) is probably the least likely to happen,
+ so use it */
+ child->child_unref_rebuilds = TRUE;
+ }
+ }
+}
+
+static uint32_t
+thread_link_references(struct mail_thread_cache *cache, uint32_t uid,
+ const struct mail_index_strmap_rec *msgid_map,
+ unsigned int *msgid_map_idx)
+{
+ uint32_t parent_idx;
+
+ if (msgid_map->uid != uid)
+ return 0;
+
+ parent_idx = msgid_map->str_idx;
+ msgid_map++;
+ *msgid_map_idx += 1;
+
+ for (; msgid_map->uid == uid; msgid_map++) {
+ thread_link_reference(cache, parent_idx, msgid_map->str_idx);
+ parent_idx = msgid_map->str_idx;
+ *msgid_map_idx += 1;
+ }
+ i_assert(parent_idx < cache->first_invalid_msgid_str_idx);
+ return parent_idx;
+}
+
+void mail_thread_add(struct mail_thread_cache *cache,
+ const struct mail_index_strmap_rec *msgid_map,
+ unsigned int *msgid_map_idx)
+{
+ struct mail_thread_node *node;
+ uint32_t idx, parent_idx;
+
+ i_assert(msgid_map->ref_index == MAIL_THREAD_NODE_REF_MSGID);
+ i_assert(cache->last_uid <= msgid_map->uid);
+
+ cache->last_uid = msgid_map->uid;
+
+ idx = thread_msg_add(cache, msgid_map->uid, msgid_map->str_idx);
+ parent_idx = thread_link_references(cache, msgid_map->uid,
+ msgid_map + 1, msgid_map_idx);
+
+ node = array_idx_modifiable(&cache->thread_nodes, idx);
+ if (node->parent_idx != parent_idx && node->parent_idx != 0) {
+ /* conflicting parent, remove it. */
+ node->parent_idx = 0;
+ /* If this message gets expunged, we have to revert back to
+ the original parent. */
+ node->expunge_rebuilds = TRUE;
+ }
+ if (parent_idx != 0)
+ thread_link_reference(cache, parent_idx, idx);
+ *msgid_map_idx += 1;
+}
+
+static bool
+mail_thread_unref_link(struct mail_thread_cache *cache,
+ uint32_t parent_idx, uint32_t child_idx)
+{
+ struct mail_thread_node *parent, *child;
+
+ parent = array_idx_modifiable(&cache->thread_nodes, parent_idx);
+ if (parent->child_unref_rebuilds)
+ return FALSE;
+
+ child = array_idx_modifiable(&cache->thread_nodes, child_idx);
+ i_assert(child->parent_link_refcount > 0);
+
+ child->parent_link_refcount--;
+ if (child->parent_link_refcount == 0) {
+ /* we don't have a root anymore */
+ child->parent_idx = 0;
+ }
+ return TRUE;
+}
+
+bool mail_thread_remove(struct mail_thread_cache *cache,
+ const struct mail_index_strmap_rec *msgid_map,
+ unsigned int *msgid_map_idx)
+{
+ struct mail_thread_node *node;
+ uint32_t idx, parent_idx;
+ unsigned int count = 1;
+
+ idx = msgid_map->str_idx;
+ i_assert(idx != 0);
+
+ if (msgid_map->uid > cache->last_uid) {
+ /* this message was never added to the cache, skip */
+ while (msgid_map[count].uid == msgid_map->uid)
+ count++;
+ *msgid_map_idx += count;
+ return TRUE;
+ }
+
+ node = array_idx_modifiable(&cache->thread_nodes, idx);
+ if (node->expunge_rebuilds) {
+ /* this catches the duplicate message-id case */
+ return FALSE;
+ }
+ i_assert(node->uid == msgid_map->uid);
+
+ /* update link refcounts */
+ if (msgid_map[count].uid == node->uid) {
+ parent_idx = msgid_map[count].str_idx;
+ count++;
+ while (msgid_map[count].uid == node->uid) {
+ if (!mail_thread_unref_link(cache, parent_idx,
+ msgid_map[count].str_idx))
+ return FALSE;
+ parent_idx = msgid_map[count].str_idx;
+ count++;
+ }
+ if (!mail_thread_unref_link(cache, parent_idx, idx))
+ return FALSE;
+ }
+ /* mark this message as expunged */
+ node->uid = 0;
+
+ /* we don't know (and don't want to waste time figuring out) if other
+ messages point to this removed message, so don't delete the node */
+ *msgid_map_idx += count;
+ return TRUE;
+}