bcb4e51a409d94ae670de96afb8483a4f7855294Stephan Bosch/* Copyright (c) 2006-2018 Dovecot authors, see the included COPYING file */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
211c638d81d382517d196ad47565e0d85012c927klemens/* The idea is that we use 32bit integers for string sort IDs which specify
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen the sort order for primary sort condition. The whole 32bit integer space is
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen used and whenever adding a string, the available space is halved and the new
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ID is added in the middle. For example if we add one mail the first time, it
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen gets ID 2^31. If we then add two mails which are sorted before the first
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen one, they get IDs 2^31/3 and 2^31/3*2. Once we run out of the available
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen space between IDs, more space is made by renumbering some IDs.
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen*/
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen#include "lib.h"
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen#include "array.h"
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen#include "str.h"
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen#include "index-storage.h"
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen#include "index-sort-private.h"
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenstruct mail_sort_node {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen uint32_t seq:29;
c1277b66e1aaadaae8cb3344b97b60b0fe57ca26Timo Sirainen bool wanted:1;
c1277b66e1aaadaae8cb3344b97b60b0fe57ca26Timo Sirainen bool no_update:1;
c1277b66e1aaadaae8cb3344b97b60b0fe57ca26Timo Sirainen bool sort_id_changed:1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen uint32_t sort_id;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen};
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo SirainenARRAY_DEFINE_TYPE(mail_sort_node, struct mail_sort_node);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenstruct sort_string_context {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen struct mail_search_sort_program *program;
08f7dfe63ae5afae1b1f68d4de108d18cdd737b0Timo Sirainen const char *primary_sort_name;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ARRAY_TYPE(mail_sort_node) zero_nodes, nonzero_nodes, sorted_nodes;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen const char **sort_strings;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen pool_t sort_string_pool;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen unsigned int first_missing_sort_id_idx;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen uint32_t ext_id, last_seq, highest_reset_id, prev_seq;
f6a1fbad55980c9b257ffc1881a55dc7fafe9a83Timo Sirainen uint32_t lowest_nonexpunged_zero;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
0dffa25d211be541ee3c953b23566a1a990789dfTimo Sirainen bool regetting:1;
0dffa25d211be541ee3c953b23566a1a990789dfTimo Sirainen bool have_all_wanted:1;
0dffa25d211be541ee3c953b23566a1a990789dfTimo Sirainen bool no_writing:1;
0dffa25d211be541ee3c953b23566a1a990789dfTimo Sirainen bool reverse:1;
0dffa25d211be541ee3c953b23566a1a990789dfTimo Sirainen bool seqs_nonsorted:1;
0dffa25d211be541ee3c953b23566a1a990789dfTimo Sirainen bool broken:1;
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen bool failed:1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen};
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenstatic struct sort_string_context *static_zero_cmp_context;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainenstatic void index_sort_list_reset_broken(struct sort_string_context *ctx,
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen const char *reason);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenstatic void index_sort_node_add(struct sort_string_context *ctx,
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen struct mail_sort_node *node);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenvoid index_sort_list_init_string(struct mail_search_sort_program *program)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen struct sort_string_context *ctx;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen const char *name;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen switch (program->sort_program[0] & MAIL_SORT_MASK) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen case MAIL_SORT_CC:
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen name = "sort-c";
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen break;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen case MAIL_SORT_FROM:
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen name = "sort-f";
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen break;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen case MAIL_SORT_SUBJECT:
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen name = "sort-s";
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen break;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen case MAIL_SORT_TO:
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen name = "sort-t";
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen break;
00d43d5087b555c5c9c5667942ddf41d1b4ecb0fTimo Sirainen case MAIL_SORT_DISPLAYFROM:
00d43d5087b555c5c9c5667942ddf41d1b4ecb0fTimo Sirainen name = "sort-df";
00d43d5087b555c5c9c5667942ddf41d1b4ecb0fTimo Sirainen break;
00d43d5087b555c5c9c5667942ddf41d1b4ecb0fTimo Sirainen case MAIL_SORT_DISPLAYTO:
00d43d5087b555c5c9c5667942ddf41d1b4ecb0fTimo Sirainen name = "sort-dt";
00d43d5087b555c5c9c5667942ddf41d1b4ecb0fTimo Sirainen break;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen default:
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_unreached();
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen program->context = ctx = i_new(struct sort_string_context, 1);
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen ctx->reverse = (program->sort_program[0] & MAIL_SORT_FLAG_REVERSE) != 0;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ctx->program = program;
08f7dfe63ae5afae1b1f68d4de108d18cdd737b0Timo Sirainen ctx->primary_sort_name = name;
ca98d6a1bbe73499da758a36bfab2963375c8d06Timo Sirainen ctx->ext_id = mail_index_ext_register(program->t->box->index, name, 0,
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen sizeof(uint32_t),
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen sizeof(uint32_t));
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_array_init(&ctx->zero_nodes, 128);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_array_init(&ctx->nonzero_nodes, 128);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainenstatic int sort_node_seq_cmp(const struct mail_sort_node *n1,
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen const struct mail_sort_node *n2)
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen{
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen if (n1->seq < n2->seq)
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen return -1;
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen if (n1->seq > n2->seq)
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen return 1;
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen return 0;
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen}
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenstatic void index_sort_generate_seqs(struct sort_string_context *ctx)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen struct mail_sort_node *nodes, *nodes2;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen unsigned int i, j, count, count2;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen uint32_t seq;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nodes = array_get_modifiable(&ctx->nonzero_nodes, &count);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nodes2 = array_get_modifiable(&ctx->zero_nodes, &count2);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (!array_is_created(&ctx->program->seqs))
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_array_init(&ctx->program->seqs, count + count2);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen else
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_clear(&ctx->program->seqs);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (i = j = 0;;) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (i < count && j < count2) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (nodes[i].seq < nodes2[j].seq)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen seq = nodes[i++].seq;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen else
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen seq = nodes2[j++].seq;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen } else if (i < count) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen seq = nodes[i++].seq;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen } else if (j < count2) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen seq = nodes2[j++].seq;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen } else {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen break;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_append(&ctx->program->seqs, &seq, 1);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenstatic void index_sort_reget_sort_ids(struct sort_string_context *ctx)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen struct mail_sort_node node;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen const uint32_t *seqs;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen unsigned int i, count;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_assert(!ctx->regetting);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ctx->regetting = TRUE;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen index_sort_generate_seqs(ctx);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_clear(&ctx->zero_nodes);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_clear(&ctx->nonzero_nodes);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
efe78d3ba24fc866af1c79b9223dc0809ba26cadStephan Bosch i_zero(&node);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen node.wanted = TRUE;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen seqs = array_get(&ctx->program->seqs, &count);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (i = 0; i < count; i++) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen node.seq = seqs[i];
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen index_sort_node_add(ctx, &node);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ctx->regetting = FALSE;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenstatic void index_sort_node_add(struct sort_string_context *ctx,
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen struct mail_sort_node *node)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen struct mail_index_map *map;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen const void *data;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen uint32_t reset_id;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen bool expunged;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
cd83124e5d070a016c590bb0b1096d7828c7b6adTimo Sirainen mail_index_lookup_ext_full(ctx->program->t->view, node->seq,
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ctx->ext_id, &map, &data, &expunged);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (expunged) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* we don't want to update expunged messages' sort IDs */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen node->no_update = TRUE;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* we can't trust expunged messages' sort IDs. they might be
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen valid, but it's also possible that sort IDs were updated
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen and the expunged messages' sort IDs became invalid. we could
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen use sort ID if we could know the extension's reset_id at the
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen time of the expunge so we could compare it to
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen highest_reset_id, but this isn't currently possible. */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen node->sort_id = 0;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen } else {
08f7dfe63ae5afae1b1f68d4de108d18cdd737b0Timo Sirainen node->sort_id = ctx->broken || data == NULL ? 0 :
08f7dfe63ae5afae1b1f68d4de108d18cdd737b0Timo Sirainen *(const uint32_t *)data;
f6a1fbad55980c9b257ffc1881a55dc7fafe9a83Timo Sirainen if (node->sort_id == 0) {
f6a1fbad55980c9b257ffc1881a55dc7fafe9a83Timo Sirainen if (ctx->lowest_nonexpunged_zero > node->seq ||
f6a1fbad55980c9b257ffc1881a55dc7fafe9a83Timo Sirainen ctx->lowest_nonexpunged_zero == 0)
f6a1fbad55980c9b257ffc1881a55dc7fafe9a83Timo Sirainen ctx->lowest_nonexpunged_zero = node->seq;
08f7dfe63ae5afae1b1f68d4de108d18cdd737b0Timo Sirainen } else if (ctx->lowest_nonexpunged_zero != 0 &&
08f7dfe63ae5afae1b1f68d4de108d18cdd737b0Timo Sirainen ctx->lowest_nonexpunged_zero <= node->seq) {
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen uint32_t nonzero_uid, zero_uid;
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen mail_index_lookup_uid(ctx->program->t->view,
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen node->seq, &nonzero_uid);
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen mail_index_lookup_uid(ctx->program->t->view,
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen ctx->lowest_nonexpunged_zero, &zero_uid);
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen index_sort_list_reset_broken(ctx, t_strdup_printf(
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen "sort_id=0 found in the middle "
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen "(uid=%u has sort_id, uid=%u doesn't)",
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen nonzero_uid, zero_uid));
08f7dfe63ae5afae1b1f68d4de108d18cdd737b0Timo Sirainen ctx->broken = TRUE;
08f7dfe63ae5afae1b1f68d4de108d18cdd737b0Timo Sirainen node->sort_id = 0;
f6a1fbad55980c9b257ffc1881a55dc7fafe9a83Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (node->sort_id != 0) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* if reset ID increases, lookup all existing messages' sort
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen IDs again. if it decreases, ignore the sort ID. */
cd83124e5d070a016c590bb0b1096d7828c7b6adTimo Sirainen if (!mail_index_ext_get_reset_id(ctx->program->t->view, map,
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ctx->ext_id, &reset_id))
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen reset_id = 0;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (reset_id != ctx->highest_reset_id) {
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen if (reset_id < ctx->highest_reset_id) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_assert(expunged);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen node->sort_id = 0;
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen } else if (ctx->have_all_wanted) {
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen /* a bit late to start changing the reset_id.
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen the node lists aren't ordered by sequence
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen anymore. */
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen node->sort_id = 0;
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen ctx->no_writing = TRUE;
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen } else {
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen ctx->highest_reset_id = reset_id;
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen index_sort_reget_sort_ids(ctx);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (node->sort_id == 0)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_append(&ctx->zero_nodes, node, 1);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen else
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_append(&ctx->nonzero_nodes, node, 1);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (ctx->last_seq < node->seq)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ctx->last_seq = node->seq;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenvoid index_sort_list_add_string(struct mail_search_sort_program *program,
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen struct mail *mail)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen struct sort_string_context *ctx = program->context;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen struct mail_sort_node node;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
efe78d3ba24fc866af1c79b9223dc0809ba26cadStephan Bosch i_zero(&node);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen node.seq = mail->seq;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen node.wanted = TRUE;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen if (mail->seq < ctx->prev_seq)
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen ctx->seqs_nonsorted = TRUE;
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen ctx->prev_seq = mail->seq;
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen index_sort_node_add(ctx, &node);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
c9dea5c23355dea35c6fa423de69f6507852efe4Timo Sirainenstatic int sort_node_zero_string_cmp(const struct mail_sort_node *n1,
c9dea5c23355dea35c6fa423de69f6507852efe4Timo Sirainen const struct mail_sort_node *n2)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
3e937db1db323cc690bbadb552c17e8492589b8bTimo Sirainen struct sort_string_context *ctx = static_zero_cmp_context;
3e937db1db323cc690bbadb552c17e8492589b8bTimo Sirainen int ret;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
3e937db1db323cc690bbadb552c17e8492589b8bTimo Sirainen ret = strcmp(ctx->sort_strings[n1->seq], ctx->sort_strings[n2->seq]);
3e937db1db323cc690bbadb552c17e8492589b8bTimo Sirainen if (ret != 0)
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen return !ctx->reverse ? ret : -ret;
3e937db1db323cc690bbadb552c17e8492589b8bTimo Sirainen
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen return index_sort_node_cmp_type(ctx->program,
3e937db1db323cc690bbadb552c17e8492589b8bTimo Sirainen ctx->program->sort_program + 1,
3e937db1db323cc690bbadb552c17e8492589b8bTimo Sirainen n1->seq, n2->seq);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenstatic void index_sort_zeroes(struct sort_string_context *ctx)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen enum mail_sort_type sort_type = ctx->program->sort_program[0];
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen string_t *str;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen pool_t pool;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen struct mail_sort_node *nodes;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen unsigned int i, count;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* first get all the messages' sort strings. although this takes more
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen memory, it makes error handling easier and probably also helps
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen CPU caching. */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ctx->sort_strings = i_new(const char *, ctx->last_seq + 1);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ctx->sort_string_pool = pool =
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen pool_alloconly_create("sort strings", 1024*64);
a203000ed248009c1808cf8b45f84b2c3d5b89e9Timo Sirainen str = str_new(default_pool, 512);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nodes = array_get_modifiable(&ctx->zero_nodes, &count);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (i = 0; i < count; i++) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_assert(nodes[i].seq <= ctx->last_seq);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
a203000ed248009c1808cf8b45f84b2c3d5b89e9Timo Sirainen T_BEGIN {
a85cf0bdd86ba36e6f1243e9b6848a335625185bTimo Sirainen if (index_sort_header_get(ctx->program, nodes[i].seq,
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen sort_type, str) < 0) {
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen nodes[i].no_update = TRUE;
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen ctx->failed = TRUE;
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen }
a203000ed248009c1808cf8b45f84b2c3d5b89e9Timo Sirainen ctx->sort_strings[nodes[i].seq] =
a203000ed248009c1808cf8b45f84b2c3d5b89e9Timo Sirainen str_len(str) == 0 ? "" :
a203000ed248009c1808cf8b45f84b2c3d5b89e9Timo Sirainen p_strdup(pool, str_c(str));
a203000ed248009c1808cf8b45f84b2c3d5b89e9Timo Sirainen } T_END;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
a203000ed248009c1808cf8b45f84b2c3d5b89e9Timo Sirainen str_free(&str);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* we have all strings, sort nodes based on them */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen static_zero_cmp_context = ctx;
c9dea5c23355dea35c6fa423de69f6507852efe4Timo Sirainen array_sort(&ctx->zero_nodes, sort_node_zero_string_cmp);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
6cf18519f0804755385871d84384834465b2d68eTimo Sirainenstatic bool
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenindex_sort_get_expunged_string(struct sort_string_context *ctx, uint32_t idx,
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen string_t *str, const char **result_r)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen enum mail_sort_type sort_type = ctx->program->sort_program[0];
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen const struct mail_sort_node *nodes;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen const char *result = NULL;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen unsigned int i, count;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen uint32_t sort_id;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* Look forwards and backwards to see if there are
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen identical sort_ids. If we do find them, try to get
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen their sort string and use it to update the rest. */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nodes = array_get(&ctx->nonzero_nodes, &count);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen sort_id = nodes[idx].sort_id;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* If previous sort ID is identical and its sort string is set, we can
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen trust it. If it's expunged, we already verified that there are no
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen non-expunged messages. */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (idx > 0 && nodes[idx-1].sort_id == sort_id &&
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen ctx->sort_strings[nodes[idx].seq] != NULL) {
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen *result_r = ctx->sort_strings[nodes[idx].seq];
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen return TRUE;
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* Go forwards as long as there are identical sort IDs. If we find one
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen that's not expunged, update string table for all messages with
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen identical sort IDs. */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (i = idx + 1; i < count; i++) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (nodes[i].sort_id != sort_id)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen break;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (ctx->sort_strings[nodes[i].seq] != NULL) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* usually we fill all identical sort_ids and this
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen shouldn't happen, but we can get here if we skipped
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen over messages when binary searching */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen result = ctx->sort_strings[nodes[i].seq];
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen break;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
a85cf0bdd86ba36e6f1243e9b6848a335625185bTimo Sirainen if (index_sort_header_get(ctx->program, nodes[i].seq,
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen sort_type, str) > 0) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen result = str_len(str) == 0 ? "" :
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen p_strdup(ctx->sort_string_pool, str_c(str));
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen break;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (result == NULL) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* unknown */
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen return FALSE;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* fill all identical sort_ids with the same value */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (i = idx; i > 0 && nodes[i-1].sort_id == sort_id; i--) ;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (i = idx; i < count && nodes[i].sort_id == sort_id; i++)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ctx->sort_strings[nodes[i].seq] = result;
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen *result_r = result;
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen return TRUE;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
91ede77590440f8613c477bac1b7336ca8928e87Timo Sirainenstatic bool
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenindex_sort_get_string(struct sort_string_context *ctx,
1a229e3e15ed387208c13e7dfe56984becf90288Timo Sirainen uint32_t idx, struct mail_sort_node *node,
1a229e3e15ed387208c13e7dfe56984becf90288Timo Sirainen const char **str_r)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
1a229e3e15ed387208c13e7dfe56984becf90288Timo Sirainen uint32_t seq = node->seq;
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen int ret = 1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
0a6a527f0c42b5478d80ac53ab357885676fd516Timo Sirainen if (node->no_update) {
0a6a527f0c42b5478d80ac53ab357885676fd516Timo Sirainen /* we've already determined that we can't do this lookup */
f976c38f07e6da867000c4c0e74afe235bc763d5Timo Sirainen *str_r = ctx->sort_strings[seq];
0a6a527f0c42b5478d80ac53ab357885676fd516Timo Sirainen return FALSE;
0a6a527f0c42b5478d80ac53ab357885676fd516Timo Sirainen }
0a6a527f0c42b5478d80ac53ab357885676fd516Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (ctx->sort_strings[seq] == NULL) T_BEGIN {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen string_t *str;
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen const char *result;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen str = t_str_new(256);
a85cf0bdd86ba36e6f1243e9b6848a335625185bTimo Sirainen ret = index_sort_header_get(ctx->program, seq,
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ctx->program->sort_program[0], str);
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen if (ret < 0)
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen ctx->failed = TRUE;
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen else if (ret == 0) {
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen if (!index_sort_get_expunged_string(ctx, idx, str, &result))
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen ctx->sort_strings[seq] = "";
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen else {
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen /* found the expunged string - return success */
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen ctx->sort_strings[seq] = result;
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen ret = 1;
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen } else {
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen ctx->sort_strings[seq] = str_len(str) == 0 ? "" :
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen p_strdup(ctx->sort_string_pool, str_c(str));
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen } T_END;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
1a229e3e15ed387208c13e7dfe56984becf90288Timo Sirainen if (ret <= 0)
1a229e3e15ed387208c13e7dfe56984becf90288Timo Sirainen node->no_update = TRUE;
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen *str_r = ctx->sort_strings[seq];
91ede77590440f8613c477bac1b7336ca8928e87Timo Sirainen return ret > 0;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenstatic void
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenindex_sort_bsearch(struct sort_string_context *ctx, const char *key,
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen unsigned int start_idx, unsigned int *idx_r,
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen const char **prev_str_r)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen struct mail_sort_node *nodes;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen const char *str, *str2;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen unsigned int idx, left_idx, right_idx, prev;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen int ret;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nodes = array_get_modifiable(&ctx->nonzero_nodes, &right_idx);
25480af2e21cf136e461ec802177f52b43154485Timo Sirainen i_assert(right_idx < INT_MAX);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen idx = left_idx = start_idx;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen while (left_idx < right_idx) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen idx = (left_idx + right_idx) / 2;
91ede77590440f8613c477bac1b7336ca8928e87Timo Sirainen if (index_sort_get_string(ctx, idx, &nodes[idx], &str))
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ret = strcmp(key, str);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen else {
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen /* put expunged (and otherwise failed) messages first */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ret = 1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (prev = idx; prev > 0; ) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen prev--;
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen if (index_sort_get_string(ctx, prev,
1a229e3e15ed387208c13e7dfe56984becf90288Timo Sirainen &nodes[prev],
91ede77590440f8613c477bac1b7336ca8928e87Timo Sirainen &str2)) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ret = strcmp(key, str2);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (ret <= 0) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen idx = prev;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen str = str2;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen break;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (ret > 0)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen left_idx = idx+1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen else if (ret < 0)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen right_idx = idx;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen else {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen *idx_r = idx + 1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen *prev_str_r = str;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen return;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (left_idx > idx)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen idx++;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen *idx_r = idx;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (idx > start_idx) {
91ede77590440f8613c477bac1b7336ca8928e87Timo Sirainen bool success;
91ede77590440f8613c477bac1b7336ca8928e87Timo Sirainen
a9ce43c494ce7434277f6b30e591f4b832e2d49dTimo Sirainen prev = idx;
a9ce43c494ce7434277f6b30e591f4b832e2d49dTimo Sirainen do {
a9ce43c494ce7434277f6b30e591f4b832e2d49dTimo Sirainen prev--;
91ede77590440f8613c477bac1b7336ca8928e87Timo Sirainen success = index_sort_get_string(ctx, prev,
91ede77590440f8613c477bac1b7336ca8928e87Timo Sirainen &nodes[prev], &str2);
91ede77590440f8613c477bac1b7336ca8928e87Timo Sirainen } while (!success && prev > 0 &&
a9ce43c494ce7434277f6b30e591f4b832e2d49dTimo Sirainen nodes[prev-1].sort_id == nodes[prev].sort_id);
a9ce43c494ce7434277f6b30e591f4b832e2d49dTimo Sirainen *prev_str_r = str2;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenstatic void index_sort_merge(struct sort_string_context *ctx)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen struct mail_sort_node *znodes, *nznodes;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen const char *zstr, *nzstr, *prev_str;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen unsigned int zpos, nzpos, nz_next_pos, zcount, nzcount;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen int ret;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* both zero_nodes and nonzero_nodes are sorted. we'll now just have
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen to merge them together. use sorted_nodes as the result array. */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_array_init(&ctx->sorted_nodes, array_count(&ctx->nonzero_nodes) +
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_count(&ctx->zero_nodes));
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen znodes = array_get_modifiable(&ctx->zero_nodes, &zcount);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nznodes = array_get_modifiable(&ctx->nonzero_nodes, &nzcount);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen prev_str = NULL;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (zpos = nzpos = 0; zpos < zcount && nzpos < nzcount; ) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen zstr = ctx->sort_strings[znodes[zpos].seq];
91ede77590440f8613c477bac1b7336ca8928e87Timo Sirainen if (index_sort_get_string(ctx, nzpos, &nznodes[nzpos], &nzstr))
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ret = strcmp(zstr, nzstr);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen else if (prev_str != NULL && strcmp(zstr, prev_str) == 0) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* identical to previous message, must keep them
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen together */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ret = -1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen } else {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* we can't be yet sure about the order, but future
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nznodes may reveal that the znode must be added
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen later. if future nznodes don't reveal that, we have
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen no idea about these nodes' order. so just always
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen put the expunged message first. */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ret = 1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
06ff86fc92a789e9239dccbb4300f7994ee8842eTimo Sirainen if (ret == 0) {
06ff86fc92a789e9239dccbb4300f7994ee8842eTimo Sirainen ret = index_sort_node_cmp_type(ctx->program,
06ff86fc92a789e9239dccbb4300f7994ee8842eTimo Sirainen ctx->program->sort_program + 1,
06ff86fc92a789e9239dccbb4300f7994ee8842eTimo Sirainen znodes[zpos].seq, nznodes[nzpos].seq);
06ff86fc92a789e9239dccbb4300f7994ee8842eTimo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (ret <= 0) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_append(&ctx->sorted_nodes, &znodes[zpos], 1);
a9ce43c494ce7434277f6b30e591f4b832e2d49dTimo Sirainen prev_str = zstr;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen zpos++;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen } else {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_append(&ctx->sorted_nodes, &nznodes[nzpos], 1);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen prev_str = nzstr;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nzpos++;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* avoid looking up all existing messages' strings by
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen binary searching the next zero-node position. don't
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen bother if it looks like more work than linear
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen scanning. */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (zcount - zpos < (nzcount - nzpos)/2) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen index_sort_bsearch(ctx, zstr, nzpos,
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen &nz_next_pos, &prev_str);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_append(&ctx->sorted_nodes,
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen &nznodes[nzpos],
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nz_next_pos - nzpos);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nzpos = nz_next_pos;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* only one of zero_nodes and nonzero_nodes can be non-empty now */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (; zpos < zcount; zpos++)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_append(&ctx->sorted_nodes, &znodes[zpos], 1);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (; nzpos < nzcount; nzpos++)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_append(&ctx->sorted_nodes, &nznodes[nzpos], 1);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* future index_sort_get_string() calls use ctx->nonzero_nodes, but we
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen use only ctx->sorted_nodes. make them identical. */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_free(&ctx->nonzero_nodes);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen ctx->nonzero_nodes = ctx->sorted_nodes;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainenstatic int
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenindex_sort_add_ids_range(struct sort_string_context *ctx,
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen unsigned int left_idx, unsigned int right_idx,
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen const char **reason_r)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen struct mail_sort_node *nodes;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen unsigned int i, count, rightmost_idx, skip;
d50f5a6963f56c587b1d47119c3af4da2fde45edTimo Sirainen const char *left_str = NULL, *right_str = NULL, *str = NULL;
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen uint32_t left_sort_id, right_sort_id, diff, left_str_idx = 0;
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen bool no_left_str = FALSE, no_right_str = FALSE;
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen int ret;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nodes = array_get_modifiable(&ctx->sorted_nodes, &count);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen rightmost_idx = count - 1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* get the sort IDs from left and right */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen left_sort_id = nodes[left_idx].sort_id;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen right_sort_id = nodes[right_idx].sort_id;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* check if all of them should have the same sort IDs. we don't want
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen to hit the renumbering code in that situation. */
782e7c6d33ade2d3b8a2126801c06956358abf66Timo Sirainen if (left_sort_id == right_sort_id && left_sort_id != 0) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* they should all have the same sort ID */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (i = left_idx + 1; i < right_idx; i++) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nodes[i].sort_id = left_sort_id;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nodes[i].sort_id_changed = TRUE;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen return 0;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (left_sort_id == 0) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_assert(left_idx == 0);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen left_sort_id = 1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (right_sort_id == 0) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_assert(right_idx == rightmost_idx);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen right_sort_id = (uint32_t)-1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_assert(left_sort_id <= right_sort_id);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen diff = right_sort_id - left_sort_id;
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen while (diff / (right_idx-left_idx + 2) == 0) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* we most likely don't have enough space. we have to
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen renumber some of the existing sort IDs. do this by
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen widening the area we're giving sort IDs. */
b0aaaad8427cacdb9486b4406198c3301569422cTimo Sirainen while (left_idx > 0) {
b0aaaad8427cacdb9486b4406198c3301569422cTimo Sirainen if (nodes[--left_idx].sort_id != left_sort_id) {
b0aaaad8427cacdb9486b4406198c3301569422cTimo Sirainen left_sort_id = nodes[left_idx].sort_id;
b0aaaad8427cacdb9486b4406198c3301569422cTimo Sirainen if (left_sort_id == 0) {
b0aaaad8427cacdb9486b4406198c3301569422cTimo Sirainen i_assert(left_idx == 0);
b0aaaad8427cacdb9486b4406198c3301569422cTimo Sirainen left_sort_id = 1;
b0aaaad8427cacdb9486b4406198c3301569422cTimo Sirainen }
b0aaaad8427cacdb9486b4406198c3301569422cTimo Sirainen break;
258464263315a814d8c3f1440058044c62540025Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen while (right_idx < rightmost_idx) {
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen right_idx++;
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen if (nodes[right_idx].sort_id > right_sort_id)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen break;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
258464263315a814d8c3f1440058044c62540025Timo Sirainen right_sort_id = nodes[right_idx].sort_id;
258464263315a814d8c3f1440058044c62540025Timo Sirainen if (right_sort_id == 0) {
258464263315a814d8c3f1440058044c62540025Timo Sirainen i_assert(right_idx == rightmost_idx);
258464263315a814d8c3f1440058044c62540025Timo Sirainen right_sort_id = (uint32_t)-1;
258464263315a814d8c3f1440058044c62540025Timo Sirainen }
a25113c19ed6ed75ea19ed99976c9fbc762a29c7Timo Sirainen i_assert(left_sort_id <= right_sort_id);
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen if (diff == right_sort_id - left_sort_id) {
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen /* we did nothing, but there's still not enough space.
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen have to renumber the leftmost/rightmost node(s) */
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen i_assert(left_idx == 0 && right_idx == rightmost_idx);
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen if (left_sort_id > 1) {
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen left_sort_id = 1;
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen no_left_str = TRUE;
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen } else {
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen i_assert(right_sort_id != (uint32_t)-1);
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen right_sort_id = (uint32_t)-1;
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen no_right_str = TRUE;
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen }
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen }
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen diff = right_sort_id - left_sort_id;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen if (nodes[left_idx].sort_id != 0 && !no_left_str) {
91ede77590440f8613c477bac1b7336ca8928e87Timo Sirainen if (!index_sort_get_string(ctx, left_idx,
91ede77590440f8613c477bac1b7336ca8928e87Timo Sirainen &nodes[left_idx], &left_str)) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* not equivalent with any message */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen left_str = NULL;
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen } else {
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen left_str_idx = left_idx;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen left_idx++;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
00e3803ee6a7e56f1b58bcf0452ccbfde6a22fcaTimo Sirainen if (nodes[right_idx].sort_id != 0 && !no_right_str) {
91ede77590440f8613c477bac1b7336ca8928e87Timo Sirainen if (!index_sort_get_string(ctx, right_idx,
91ede77590440f8613c477bac1b7336ca8928e87Timo Sirainen &nodes[right_idx], &right_str)) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* not equivalent with any message */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen right_str = NULL;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen right_idx--;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_assert(left_idx <= right_idx);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* give (new) sort IDs to all nodes in left_idx..right_idx range.
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen divide the available space so that each message gets an equal sized
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen share. some messages' sort strings may be equivalent, so give them
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen the same sort IDs. */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (i = left_idx; i <= right_idx; i++) {
91ede77590440f8613c477bac1b7336ca8928e87Timo Sirainen if (!index_sort_get_string(ctx, i, &nodes[i], &str)) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* it doesn't really matter what we give to this
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen message, since it's only temporary and we don't
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen know its correct position anyway. so let's assume
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen it's equivalent to previous message. */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nodes[i].sort_id = left_sort_id;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen continue;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen ret = left_str == NULL ? 1 : strcmp(str, left_str);
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen if (ret <= 0) {
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen if (ret < 0) {
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen /* broken sort_ids */
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen uint32_t str_uid, left_str_uid;
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen mail_index_lookup_uid(ctx->program->t->view,
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen nodes[i].seq, &str_uid);
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen mail_index_lookup_uid(ctx->program->t->view,
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen nodes[left_str_idx].seq, &left_str_uid);
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen *reason_r = t_strdup_printf(
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen "(idx=%u, seq=%u, uid=%u) '%s' < left string (idx=%u, seq=%u, uid=%u) '%s'",
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen i, nodes[i].seq, str_uid, str,
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen left_str_idx, nodes[left_str_idx].seq, left_str_uid, left_str);
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen return -1;
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nodes[i].sort_id = left_sort_id;
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen } else if (right_str != NULL && strcmp(str, right_str) == 0) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* the rest of the sort IDs should be the same */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nodes[i].sort_id = right_sort_id;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen left_sort_id = right_sort_id;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen } else {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* divide the available space equally. leave the same
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen sized space also between the first and the last
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen messages */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen skip = (right_sort_id - left_sort_id) /
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen (right_idx - i + 2);
1aba6c7fba4ee28d3e90e0885424abe6a4b08e91Timo Sirainen if (skip == 0) {
1aba6c7fba4ee28d3e90e0885424abe6a4b08e91Timo Sirainen /* broken sort IDs (we previously assigned
1aba6c7fba4ee28d3e90e0885424abe6a4b08e91Timo Sirainen left_sort_id=right_sort_id) */
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen uint32_t uid;
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen mail_index_lookup_uid(ctx->program->t->view,
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen nodes[i].seq, &uid);
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen *reason_r = t_strdup_printf(
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen "no sort_id space for uid=%u", uid);
1aba6c7fba4ee28d3e90e0885424abe6a4b08e91Timo Sirainen return -1;
1aba6c7fba4ee28d3e90e0885424abe6a4b08e91Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen left_sort_id += skip;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_assert(left_sort_id < right_sort_id);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nodes[i].sort_id = left_sort_id;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen left_str = str;
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen left_str_idx = i;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nodes[i].sort_id_changed = TRUE;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
e376e08040b5f21ff79a15ae728d2532a34207f6Timo Sirainen i_assert(str != NULL);
e376e08040b5f21ff79a15ae728d2532a34207f6Timo Sirainen
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen if (right_str == NULL || strcmp(str, right_str) < 0 ||
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen (strcmp(str, right_str) == 0 &&
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen nodes[i-1].sort_id == right_sort_id))
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen return 0;
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen *reason_r = t_strdup_printf("Invalid sort_id order ('%s' > '%s')",
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen str, right_str);
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen return -1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainenstatic int
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainenindex_sort_add_sort_ids(struct sort_string_context *ctx, const char **reason_r)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen const struct mail_sort_node *nodes;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen unsigned int i, left_idx, right_idx, count;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nodes = array_get(&ctx->sorted_nodes, &count);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (i = 0; i < count; i++) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (nodes[i].sort_id != 0)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen continue;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* get the range for all sort_id=0 nodes. include the nodes
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen left and right of the range as well */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (right_idx = i + 1; right_idx < count; right_idx++) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (nodes[right_idx].sort_id != 0)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen break;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (right_idx == count)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen right_idx--;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen left_idx = i == 0 ? 0 : i - 1;
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen if (index_sort_add_ids_range(ctx, left_idx, right_idx, reason_r) < 0)
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen return -1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen return 0;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenstatic void index_sort_write_changed_sort_ids(struct sort_string_context *ctx)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
cd83124e5d070a016c590bb0b1096d7828c7b6adTimo Sirainen struct mail_index_transaction *itrans = ctx->program->t->itrans;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen uint32_t ext_id = ctx->ext_id;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen const struct mail_sort_node *nodes;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen unsigned int i, count;
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen uint32_t lowest_failed_seq;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen if (ctx->no_writing) {
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen /* our reset_id is already stale - don't even bother
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen trying to write */
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen return;
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen }
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen
cd83124e5d070a016c590bb0b1096d7828c7b6adTimo Sirainen mail_index_ext_reset_inc(itrans, ext_id,
cd83124e5d070a016c590bb0b1096d7828c7b6adTimo Sirainen ctx->highest_reset_id, FALSE);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen /* We require that there aren't sort_id=0 gaps in the middle of the
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen mails. At this point they could exist though, because some of the
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen mail lookups may have failed. Failures due to expunges don't matter,
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen because on the next lookup those mails will be lost anyway.
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen Otherwise, make sure we don't write those gaps out
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen First find the lowest non-expunged mail that has no_update set. */
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen nodes = array_get_modifiable(&ctx->sorted_nodes, &count);
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen lowest_failed_seq = (uint32_t)-1;
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen for (i = 0; i < count; i++) {
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen uint32_t seq = nodes[i].seq;
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen if (nodes[i].no_update && lowest_failed_seq > seq &&
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen !mail_index_is_expunged(ctx->program->t->view, seq))
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen lowest_failed_seq = seq;
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen }
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen /* add the missing sort IDs to index, but only for those sequences
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen that are below lowest_failed_seq */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen nodes = array_get_modifiable(&ctx->sorted_nodes, &count);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (i = 0; i < count; i++) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_assert(nodes[i].sort_id != 0);
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen if (!nodes[i].sort_id_changed || nodes[i].no_update ||
6ffa4fc008d510a503acb6f06ef847ecf84b7f93Timo Sirainen nodes[i].seq >= lowest_failed_seq)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen continue;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
cd83124e5d070a016c590bb0b1096d7828c7b6adTimo Sirainen mail_index_update_ext(itrans, nodes[i].seq, ext_id,
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen &nodes[i].sort_id, NULL);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
c9dea5c23355dea35c6fa423de69f6507852efe4Timo Sirainenstatic int sort_node_cmp(const struct mail_sort_node *n1,
c9dea5c23355dea35c6fa423de69f6507852efe4Timo Sirainen const struct mail_sort_node *n2)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen struct sort_string_context *ctx = static_zero_cmp_context;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (n1->sort_id < n2->sort_id)
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen return !ctx->reverse ? -1 : 1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (n1->sort_id > n2->sort_id)
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen return !ctx->reverse ? 1 : -1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen return index_sort_node_cmp_type(ctx->program,
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen ctx->program->sort_program + 1,
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen n1->seq, n2->seq);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenstatic void index_sort_add_missing(struct sort_string_context *ctx)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen struct mail_sort_node node;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen const uint32_t *seqs;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen unsigned int i, count;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen uint32_t seq, next_seq;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
2511b0c8fac94fbd3bc58f515aab22855ddf49d9Timo Sirainen ctx->have_all_wanted = TRUE;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen seqs = array_get(&ctx->program->seqs, &count);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (i = 0, next_seq = 1; i < count; i++) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (seqs[i] == next_seq)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen next_seq++;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen else {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_assert(next_seq < seqs[i]);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (seq = next_seq; seq < seqs[i]; seq++) {
efe78d3ba24fc866af1c79b9223dc0809ba26cadStephan Bosch i_zero(&node);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen node.seq = seq;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen index_sort_node_add(ctx, &node);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen next_seq = seqs[i] + 1;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
f6a1fbad55980c9b257ffc1881a55dc7fafe9a83Timo Sirainen
f6a1fbad55980c9b257ffc1881a55dc7fafe9a83Timo Sirainen if (ctx->lowest_nonexpunged_zero == 0) {
f6a1fbad55980c9b257ffc1881a55dc7fafe9a83Timo Sirainen /* we're handling only expunged zeros. if it causes us to
f6a1fbad55980c9b257ffc1881a55dc7fafe9a83Timo Sirainen renumber some existing sort IDs, don't save them. */
f6a1fbad55980c9b257ffc1881a55dc7fafe9a83Timo Sirainen ctx->no_writing = TRUE;
f6a1fbad55980c9b257ffc1881a55dc7fafe9a83Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainenstatic void index_sort_list_reset_broken(struct sort_string_context *ctx,
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen const char *reason)
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen{
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen struct mailbox *box = ctx->program->t->box;
e20e638805c4bd54e039891a3e92760b1dfa189aTimo Sirainen struct mail_sort_node *node;
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen
d4002fe1f64d25a792f76fb102ef7dc519cd4e24Martti Rannanjärvi mailbox_set_critical(box, "Broken %s indexes, resetting: %s",
d4002fe1f64d25a792f76fb102ef7dc519cd4e24Martti Rannanjärvi ctx->primary_sort_name, reason);
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen array_clear(&ctx->zero_nodes);
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen array_append_array(&ctx->zero_nodes,
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen &ctx->nonzero_nodes);
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen array_clear(&ctx->nonzero_nodes);
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen
e20e638805c4bd54e039891a3e92760b1dfa189aTimo Sirainen array_foreach_modifiable(&ctx->zero_nodes, node)
e20e638805c4bd54e039891a3e92760b1dfa189aTimo Sirainen node->sort_id = 0;
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen}
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainenvoid index_sort_list_finish_string(struct mail_search_sort_program *program)
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen{
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen struct sort_string_context *ctx = program->context;
c9dea5c23355dea35c6fa423de69f6507852efe4Timo Sirainen const struct mail_sort_node *nodes;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen unsigned int i, count;
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen const char *reason;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen uint32_t seq;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen static_zero_cmp_context = ctx;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (array_count(&ctx->zero_nodes) == 0) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* fast path: we have all sort IDs */
c9dea5c23355dea35c6fa423de69f6507852efe4Timo Sirainen array_sort(&ctx->nonzero_nodes, sort_node_cmp);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
9c3eebe94a39f13bda04926b168f54056fca05a4Timo Sirainen nodes = array_get(&ctx->nonzero_nodes, &count);
041c33f5c10902266496af22347c6efc1018e556Timo Sirainen if (!array_is_created(&program->seqs))
041c33f5c10902266496af22347c6efc1018e556Timo Sirainen i_array_init(&program->seqs, count);
041c33f5c10902266496af22347c6efc1018e556Timo Sirainen else
041c33f5c10902266496af22347c6efc1018e556Timo Sirainen array_clear(&program->seqs);
c9dea5c23355dea35c6fa423de69f6507852efe4Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (i = 0; i < count; i++) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen seq = nodes[i].seq;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_append(&program->seqs, &seq, 1);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_free(&ctx->nonzero_nodes);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen } else {
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen if (ctx->seqs_nonsorted) {
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen /* the nodes need to be sorted by sequence initially */
c9dea5c23355dea35c6fa423de69f6507852efe4Timo Sirainen array_sort(&ctx->zero_nodes, sort_node_seq_cmp);
c9dea5c23355dea35c6fa423de69f6507852efe4Timo Sirainen array_sort(&ctx->nonzero_nodes, sort_node_seq_cmp);
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen }
5a3aadf1f09af57cc8581c19234db45b00ef77fbTimo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* we have to add some sort IDs. we'll do this for all
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen messages, so first remember what messages we wanted
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen to know about. */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen index_sort_generate_seqs(ctx);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* add messages not in seqs list */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen index_sort_add_missing(ctx);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* sort all messages with sort IDs */
c9dea5c23355dea35c6fa423de69f6507852efe4Timo Sirainen array_sort(&ctx->nonzero_nodes, sort_node_cmp);
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen for (;;) {
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen /* sort all messages without sort IDs */
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen index_sort_zeroes(ctx);
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen if (ctx->reverse) {
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen /* sort lists are descending currently, but
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen merging and sort ID assigning works only
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen with ascending lists. reverse the lists
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen temporarily. we can't do this while earlier
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen because secondary sort conditions must not
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen be reversed in results (but while assigning
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen sort IDs it doesn't matter). */
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen array_reverse(&ctx->nonzero_nodes);
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen array_reverse(&ctx->zero_nodes);
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen }
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen /* merge zero and non-zero arrays into sorted_nodes */
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen index_sort_merge(ctx);
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen /* give sort IDs to messages missing them */
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen if (index_sort_add_sort_ids(ctx, &reason) == 0)
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen break;
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen /* broken, try again with sort IDs reset */
96c7d2a59593b4ad2b4d5ec65ba5c1394e0d1171Timo Sirainen index_sort_list_reset_broken(ctx, reason);
c655b40d5eaeb8c1e3af0c006b29b1aed40ebb0dTimo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen index_sort_write_changed_sort_ids(ctx);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen if (ctx->reverse) {
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen /* restore the correct sort order */
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen array_reverse(&ctx->sorted_nodes);
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen }
0ec26d0ba45ecb400e35d672d2a97a160527bd79Timo Sirainen
c9dea5c23355dea35c6fa423de69f6507852efe4Timo Sirainen nodes = array_get(&ctx->sorted_nodes, &count);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_clear(&program->seqs);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen for (i = 0; i < count; i++) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen if (nodes[i].wanted) {
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen seq = nodes[i].seq;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_append(&program->seqs, &seq, 1);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen pool_unref(&ctx->sort_string_pool);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen i_free(ctx->sort_strings);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_free(&ctx->sorted_nodes);
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen /* NOTE: we already freed nonzero_nodes and made it point to
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen sorted_nodes. */
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen }
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen if (ctx->failed)
6cf18519f0804755385871d84384834465b2d68eTimo Sirainen program->failed = TRUE;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen array_free(&ctx->zero_nodes);
041c33f5c10902266496af22347c6efc1018e556Timo Sirainen i_free(ctx);
041c33f5c10902266496af22347c6efc1018e556Timo Sirainen program->context = NULL;
ed336ce8060d7dc1e452ecb0bbe923ece25c3aa8Timo Sirainen}