/* Copyright (c) 2006-2018 Dovecot authors, see the included COPYING file */
/* The idea is that we use 32bit integers for string sort IDs which specify
the sort order for primary sort condition. The whole 32bit integer space is
used and whenever adding a string, the available space is halved and the new
ID is added in the middle. For example if we add one mail the first time, it
gets ID 2^31. If we then add two mails which are sorted before the first
one, they get IDs 2^31/3 and 2^31/3*2. Once we run out of the available
space between IDs, more space is made by renumbering some IDs.
*/
#include "lib.h"
#include "array.h"
#include "str.h"
#include "index-storage.h"
#include "index-sort-private.h"
struct mail_sort_node {
};
struct sort_string_context {
const char *primary_sort_name;
const char **sort_strings;
unsigned int first_missing_sort_id_idx;
};
const char *reason);
struct mail_sort_node *node);
{
const char *name;
case MAIL_SORT_CC:
name = "sort-c";
break;
case MAIL_SORT_FROM:
name = "sort-f";
break;
case MAIL_SORT_SUBJECT:
name = "sort-s";
break;
case MAIL_SORT_TO:
name = "sort-t";
break;
case MAIL_SORT_DISPLAYFROM:
name = "sort-df";
break;
case MAIL_SORT_DISPLAYTO:
name = "sort-dt";
break;
default:
i_unreached();
}
sizeof(uint32_t),
sizeof(uint32_t));
}
const struct mail_sort_node *n2)
{
return -1;
return 1;
return 0;
}
{
else
for (i = j = 0;;) {
else
} else if (i < count) {
} else if (j < count2) {
} else {
break;
}
}
}
{
unsigned int i, count;
for (i = 0; i < count; i++) {
}
}
struct mail_sort_node *node)
{
const void *data;
bool expunged;
if (expunged) {
/* we don't want to update expunged messages' sort IDs */
/* we can't trust expunged messages' sort IDs. they might be
valid, but it's also possible that sort IDs were updated
and the expunged messages' sort IDs became invalid. we could
use sort ID if we could know the extension's reset_id at the
time of the expunge so we could compare it to
highest_reset_id, but this isn't currently possible. */
} else {
ctx->lowest_nonexpunged_zero == 0)
} else if (ctx->lowest_nonexpunged_zero != 0 &&
"sort_id=0 found in the middle "
"(uid=%u has sort_id, uid=%u doesn't)",
nonzero_uid, zero_uid));
}
}
/* if reset ID increases, lookup all existing messages' sort
IDs again. if it decreases, ignore the sort ID. */
reset_id = 0;
} else if (ctx->have_all_wanted) {
/* a bit late to start changing the reset_id.
the node lists aren't ordered by sequence
anymore. */
} else {
}
}
}
else
}
{
}
const struct mail_sort_node *n2)
{
int ret;
if (ret != 0)
}
{
unsigned int i, count;
/* first get all the messages' sort strings. although this takes more
memory, it makes error handling easier and probably also helps
CPU caching. */
for (i = 0; i < count; i++) {
T_BEGIN {
}
} T_END;
}
/* we have all strings, sort nodes based on them */
}
static bool
{
unsigned int i, count;
/* Look forwards and backwards to see if there are
identical sort_ids. If we do find them, try to get
their sort string and use it to update the rest. */
/* If previous sort ID is identical and its sort string is set, we can
trust it. If it's expunged, we already verified that there are no
non-expunged messages. */
return TRUE;
}
/* Go forwards as long as there are identical sort IDs. If we find one
that's not expunged, update string table for all messages with
identical sort IDs. */
break;
/* usually we fill all identical sort_ids and this
shouldn't happen, but we can get here if we skipped
over messages when binary searching */
break;
}
break;
}
}
/* unknown */
return FALSE;
}
/* fill all identical sort_ids with the same value */
return TRUE;
}
static bool
const char **str_r)
{
/* we've already determined that we can't do this lookup */
return FALSE;
}
const char *result;
if (ret < 0)
else if (ret == 0) {
else {
/* found the expunged string - return success */
ret = 1;
}
} else {
}
} T_END;
if (ret <= 0)
return ret > 0;
}
static void
const char **prev_str_r)
{
int ret;
else {
/* put expunged (and otherwise failed) messages first */
ret = 1;
prev--;
&str2)) {
if (ret <= 0) {
}
break;
}
}
}
if (ret > 0)
else if (ret < 0)
else {
*prev_str_r = str;
return;
}
}
idx++;
bool success;
do {
prev--;
*prev_str_r = str2;
}
}
{
int ret;
/* both zero_nodes and nonzero_nodes are sorted. we'll now just have
to merge them together. use sorted_nodes as the result array. */
/* identical to previous message, must keep them
together */
ret = -1;
} else {
/* we can't be yet sure about the order, but future
nznodes may reveal that the znode must be added
later. if future nznodes don't reveal that, we have
no idea about these nodes' order. so just always
put the expunged message first. */
ret = 1;
}
if (ret == 0) {
}
if (ret <= 0) {
zpos++;
} else {
nzpos++;
/* avoid looking up all existing messages' strings by
binary searching the next zero-node position. don't
bother if it looks like more work than linear
scanning. */
&nz_next_pos, &prev_str);
nz_next_pos - nzpos);
nzpos = nz_next_pos;
}
}
}
/* only one of zero_nodes and nonzero_nodes can be non-empty now */
/* future index_sort_get_string() calls use ctx->nonzero_nodes, but we
use only ctx->sorted_nodes. make them identical. */
}
static int
const char **reason_r)
{
int ret;
/* get the sort IDs from left and right */
/* check if all of them should have the same sort IDs. we don't want
to hit the renumbering code in that situation. */
/* they should all have the same sort ID */
}
return 0;
}
if (left_sort_id == 0) {
left_sort_id = 1;
}
if (right_sort_id == 0) {
}
/* we most likely don't have enough space. we have to
renumber some of the existing sort IDs. do this by
widening the area we're giving sort IDs. */
while (left_idx > 0) {
if (left_sort_id == 0) {
left_sort_id = 1;
}
break;
}
}
while (right_idx < rightmost_idx) {
right_idx++;
break;
}
if (right_sort_id == 0) {
}
/* we did nothing, but there's still not enough space.
if (left_sort_id > 1) {
left_sort_id = 1;
no_left_str = TRUE;
} else {
no_right_str = TRUE;
}
}
}
/* not equivalent with any message */
} else {
}
left_idx++;
}
/* not equivalent with any message */
}
right_idx--;
}
/* give (new) sort IDs to all nodes in left_idx..right_idx range.
divide the available space so that each message gets an equal sized
share. some messages' sort strings may be equivalent, so give them
the same sort IDs. */
/* it doesn't really matter what we give to this
message, since it's only temporary and we don't
know its correct position anyway. so let's assume
it's equivalent to previous message. */
continue;
}
if (ret <= 0) {
if (ret < 0) {
/* broken sort_ids */
"(idx=%u, seq=%u, uid=%u) '%s' < left string (idx=%u, seq=%u, uid=%u) '%s'",
return -1;
}
/* the rest of the sort IDs should be the same */
} else {
/* divide the available space equally. leave the same
sized space also between the first and the last
messages */
(right_idx - i + 2);
if (skip == 0) {
/* broken sort IDs (we previously assigned
left_sort_id=right_sort_id) */
"no sort_id space for uid=%u", uid);
return -1;
}
left_sort_id += skip;
left_str_idx = i;
}
}
return 0;
return -1;
}
static int
{
for (i = 0; i < count; i++) {
continue;
/* get the range for all sort_id=0 nodes. include the nodes
left and right of the range as well */
break;
}
right_idx--;
left_idx = i == 0 ? 0 : i - 1;
return -1;
}
return 0;
}
{
unsigned int i, count;
if (ctx->no_writing) {
/* our reset_id is already stale - don't even bother
trying to write */
return;
}
/* We require that there aren't sort_id=0 gaps in the middle of the
mails. At this point they could exist though, because some of the
mail lookups may have failed. Failures due to expunges don't matter,
because on the next lookup those mails will be lost anyway.
Otherwise, make sure we don't write those gaps out
First find the lowest non-expunged mail that has no_update set. */
for (i = 0; i < count; i++) {
}
/* add the missing sort IDs to index, but only for those sequences
that are below lowest_failed_seq */
for (i = 0; i < count; i++) {
continue;
}
}
const struct mail_sort_node *n2)
{
}
{
unsigned int i, count;
next_seq++;
else {
}
}
}
if (ctx->lowest_nonexpunged_zero == 0) {
/* we're handling only expunged zeros. if it causes us to
renumber some existing sort IDs, don't save them. */
}
}
const char *reason)
{
&ctx->nonzero_nodes);
}
{
unsigned int i, count;
const char *reason;
/* fast path: we have all sort IDs */
else
for (i = 0; i < count; i++) {
}
} else {
if (ctx->seqs_nonsorted) {
/* the nodes need to be sorted by sequence initially */
}
/* we have to add some sort IDs. we'll do this for all
messages, so first remember what messages we wanted
to know about. */
/* add messages not in seqs list */
/* sort all messages with sort IDs */
for (;;) {
/* sort all messages without sort IDs */
/* sort lists are descending currently, but
merging and sort ID assigning works only
with ascending lists. reverse the lists
temporarily. we can't do this while earlier
because secondary sort conditions must not
be reversed in results (but while assigning
sort IDs it doesn't matter). */
}
/* merge zero and non-zero arrays into sorted_nodes */
/* give sort IDs to messages missing them */
break;
/* broken, try again with sort IDs reset */
}
/* restore the correct sort order */
}
for (i = 0; i < count; i++) {
}
}
/* NOTE: we already freed nonzero_nodes and made it point to
sorted_nodes. */
}
}