index-thread.c revision 3b681900f0032ffe31e77f97f06ec3b65ef1b203
/* Copyright (c) 2002-2010 Dovecot authors, see the included COPYING file */
/* doc/thread-refs.txt describes the incremental algorithm we use here. */
#include "lib.h"
#include "array.h"
#include "bsearch-insert-pos.h"
#include "hash2.h"
#include "message-id.h"
#include "mail-index-private.h"
#include "mail-index-sync-private.h"
#include "mail-search.h"
#include "mail-search-build.h"
#include "mailbox-search-result-private.h"
#include "index-storage.h"
#include "index-thread-private.h"
#include <stdlib.h>
#define MAIL_THREAD_CONTEXT(obj) \
struct mail_thread_context {
struct mailbox_transaction_context *t;
struct mail_index_strmap_view_sync *strmap_sync;
struct mail_search_args *search_args;
unsigned int failed:1;
};
struct mail_thread_mailbox {
union mailbox_module_context module_ctx;
unsigned int next_msgid_idx;
struct mail_thread_cache *cache;
struct mail_index_strmap *strmap;
struct mail_index_strmap_view *strmap_view;
/* sorted by UID, ref_index */
const struct hash2_table *msgid_hash;
/* set only temporarily while needed */
struct mail_thread_context *ctx;
};
static int
const struct mail_index_strmap_rec *rec,
const char **msgid_r)
{
unsigned int n = 0;
int ret;
return 0;
/* Message-ID: header */
break;
/* In-Reply-To: header */
break;
default:
/* References: header */
break;
}
if (ret < 0) {
/* treat it as if it didn't exist. trying to add it
again will result in failure. */
return 0;
}
return -1;
}
/* get the nth message-id */
for (; n > 0 && *msgids != '\0'; n--)
}
/* shouldn't have happened */
"Threading lost Message ID");
return -1;
}
return 1;
}
static bool
mail_thread_hash_key_cmp(const char *key,
const struct mail_index_strmap_rec *rec,
void *context)
{
const char *msgid;
bool cmp_ret;
int ret;
/* either a match or a collision, need to look closer */
T_BEGIN {
if (ret <= 0) {
if (ret < 0)
} else {
}
} T_END;
return cmp_ret;
}
static int
const struct mail_index_strmap_rec *rec2,
void *context)
{
int ret;
T_BEGIN {
if (ret > 0) {
&msgid2);
}
} T_END;
return ret;
}
unsigned int old_count,
{
const struct mail_thread_node *old_nodes;
struct mail_thread_node *node;
return;
if (new_count == 0) {
/* strmap was reset, we'll need to rebuild thread */
return;
}
/* optimization: allocate all nodes initially */
/* renumber existing valid nodes. all existing records in old_nodes
should also exist in idx_map since we've removed expunged messages
from the cache before committing the sync. */
for (i = 0; i < max; i++) {
if (idx_map[i] == 0) {
/* expunged record. */
} else {
if (node->parent_idx != 0) {
}
}
}
/* copy invalid nodes, if any. no other messages point to them,
so this is safe. we still need to update their parent_idx
pointers though. */
for (i = 0; i < invalid_count; i++) {
if (node->parent_idx != 0) {
}
}
/* replace the old nodes with the renumbered ones */
}
const char **value_r)
{
return -1;
/* Message is expunged. Instead of failing the entire THREAD
command, just treat the header as non-existing. */
}
return 0;
}
static int
{
return -1;
/* add Message-ID: */
msgid);
} else {
}
/* add References: if there are any valid ones */
do {
ref_index++;
} else {
/* no References:, use In-Reply-To: */
&in_reply_to) < 0)
return -1;
msgid);
}
}
/* message-id lookup failed in hash compare */
return -1;
}
return 0;
}
{
static const char *wanted_headers[] = {
};
struct mailbox_header_lookup_ctx *headers_ctx;
struct mail_search_args *search_args;
struct mail_search_context *search_ctx;
int ret = 0;
/* first time we're threading this mailbox */
tbox->strmap_view =
&tbox->msgid_hash);
}
/* add all missing UIDs */
&last_uid);
if (seq1 == 0) {
/* nothing is missing */
return 0;
}
ret = -1;
break;
}
}
if (mailbox_search_deinit(&search_ctx) < 0)
ret = -1;
if (ret < 0)
else
return ret;
}
{
}
{
const struct mail_index_strmap_rec *msgid_map;
/* first check that we're not inserting any messages in the middle */
return FALSE;
/* next remove messages so we'll see early if we have to rebuild.
we expect to find all removed UIDs from msgid_map that are <= max
UID in msgid_map */
for (i = j = 0; i < uid_count; i++) {
/* find and remove from the map */
j += idx;
if (j == map_count) {
/* all removals after this are about messages we never
even added to the cache */
break;
}
j--;
/* remove the messages from cache */
if (j == map_count) {
break;
}
return FALSE;
}
}
return TRUE;
}
{
const struct mail_index_strmap_rec *msgid_map;
/* everything removed successfully, add the new messages. all of them
should already be in msgid_map. */
if (uid_count == 0)
return;
msgid_map_cmp, &j);
j--;
for (i = 0; i < uid_count; i++) {
j++;
}
}
}
static void
{
if (count == 0) {
/* there are no invalid indexes yet, we can update the first
invalid index position to delay conflicts. */
/* conflict - move the invalid indexes forward */
}
}
struct mail_thread_context *ctx)
{
return;
/* successfully updated the cache */
return;
}
}
/* failed to use the cache, rebuild */
}
struct mail_thread_context *ctx,
struct mail_search_context *search_ctx)
{
const struct mail_index_strmap_rec *msgid_map;
unsigned int i, count;
/* we already checked at sync_remove that we can use this
search result. */
return;
}
/* we're relying on the array being zero-terminated (outside used
count - kind of kludgy) */
i = 0;
i++;
}
}
struct mail_thread_context **ctx_r)
{
struct mail_thread_context *ctx;
struct mail_search_context *search_ctx;
int ret;
else {
}
/* perform search first, so we don't break if there are INTHREAD keys */
if (ret == 0)
if (mailbox_search_deinit(&search_ctx) < 0)
ret = -1;
if (ret < 0) {
return -1;
} else {
return 0;
}
}
{
(void)mailbox_transaction_commit(&ctx->t);
}
{
}
struct mail_thread_iterate_context *
{
}
{
}
{
}
{
/* mailbox was already opened+closed once. */
return;
}
}