index-sort-string.c revision 3e937db1db323cc690bbadb552c17e8492589b8b
/* Copyright (c) 2006-2008 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"
#include <stdlib.h>
struct mail_sort_node {
};
struct sort_string_context {
struct mail_search_sort_program *program;
const char **sort_strings;
unsigned int first_missing_sort_id_idx;
unsigned int regetting:1;
unsigned int have_all_wanted:1;
unsigned int no_writing:1;
};
static char expunged_msg;
static struct sort_string_context *static_zero_cmp_context;
static struct mail_search_sort_program *static_sort_node_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;
default:
i_unreached();
}
sizeof(uint32_t),
sizeof(uint32_t));
}
{
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 index_transaction_context *t =
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 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;
}
{
int ret;
if (ret != 0)
return ret;
}
{
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++) {
}
/* 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 void
{
struct mail_sort_node *nodes;
/* 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;
}
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. */
if (left_idx > 0) {
if (left_sort_id == 0) {
left_sort_id = 1;
}
}
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;
}
/* 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);
left_sort_id += skip;
}
}
}
static void
{
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;
}
}
{
struct index_transaction_context *t =
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;
}
}
{
return -1;
return 1;
}
{
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 *nodes;
unsigned int i, count;
/* fast path: we have all sort IDs */
for (i = 0; i < count; i++) {
}
} else {
/* 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 */
/* sort all messages without sort IDs */
/* merge zero and non-zero arrays into sorted_nodes */
/* give sort IDs to messages missing them */
for (i = 0; i < count; i++) {
}
}
/* NOTE: we already freed nonzero_nodes and made it point to
sorted_nodes. */
}
}