index-sort-string.c revision 2454dfa32c93c20a8522c6ed42fe057baaac9f9a
/* Copyright (c) 2006-2017 Dovecot authors, see the included COPYING file */
/* The idea is that we use 32bit integers for string sort IDs which specifiy
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 {
bool wanted:1;
bool no_update:1;
bool sort_id_changed:1;
};
struct sort_string_context {
struct mail_search_sort_program *program;
const char *primary_sort_name;
const char **sort_strings;
unsigned int first_missing_sort_id_idx;
bool regetting:1;
bool have_all_wanted:1;
bool no_writing:1;
bool reverse:1;
bool seqs_nonsorted:1;
bool broken:1;
};
static char expunged_msg;
static struct sort_string_context *static_zero_cmp_context;
struct mail_sort_node *node);
{
struct sort_string_context *ctx;
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;
}
}
}
{
struct mail_sort_node node;
unsigned int i, count;
for (i = 0; i < count; i++) {
}
}
struct mail_sort_node *node)
{
struct mail_index_map *map;
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 &&
}
}
/* 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
}
{
struct mail_sort_node node;
}
const struct mail_sort_node *n2)
{
int ret;
if (ret != 0)
}
{
struct mail_sort_node *nodes;
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 const char *
{
const struct mail_sort_node *nodes;
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. */
/* 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 &expunged_msg;
}
/* fill all identical sort_ids with the same value */
return result;
}
static const char *
{
int ret;
} else if (ret >= 0) {
} else {
}
} T_END;
}
static void
const char **prev_str_r)
{
const struct mail_sort_node *nodes;
int ret;
if (str != &expunged_msg)
else {
/* put expunged messages first */
ret = 1;
prev--;
if (str2 != &expunged_msg) {
if (ret <= 0) {
}
break;
}
}
}
if (ret > 0)
else if (ret < 0)
else {
*prev_str_r = str;
return;
}
}
idx++;
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. */
if (nzstr != &expunged_msg)
/* 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) {
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
{
struct mail_sort_node *nodes;
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;
}
}
}
if (left_str == &expunged_msg) {
/* not equivalent with any message */
}
left_idx++;
}
if (right_str == &expunged_msg) {
/* 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. */
if (str == &expunged_msg) {
/* 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 */
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) */
return -1;
}
left_sort_id += skip;
}
}
}
static int
{
const struct mail_sort_node *nodes;
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;
}
{
const struct mail_sort_node *nodes;
unsigned int i, count;
if (ctx->no_writing) {
/* our reset_id is already stale - don't even bother
trying to write */
return;
}
/* add the missing sort IDs to index */
for (i = 0; i < count; i++) {
continue;
}
}
const struct mail_sort_node *n2)
{
}
{
struct mail_sort_node node;
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. */
}
}
{
struct mail_sort_node *node;
"%s: Broken %s indexes, resetting",
&ctx->nonzero_nodes);
}
{
const struct mail_sort_node *nodes;
unsigned int i, count;
/* 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 */
if (index_sort_add_sort_ids(ctx) == 0)
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. */
}
}