index-sort.c revision 0a7b04d11facda69783978a0f1ebc12b4e70f572
/* Copyright (c) 2006-2007 Dovecot authors, see the included COPYING file */
/* The idea in here is that we use a 32bit integer (sort ID) which specifies
the sort order for primary sort condition. With fixed size fields (time,
size) we use the field itself as the sort ID. They can be looked up fast
enough from cache file, so we don't add them to index file.
Strings can't be used as sort IDs directly. The way they're currently
handled is that the whole 32bit integer space is used for them 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, a large amount of the IDs are renumbered.
*/
#include "lib.h"
#include "array.h"
#include "bsearch-insert-pos.h"
#include "str.h"
#include "unichar.h"
#include "message-address.h"
#include "imap-base-subject.h"
#include "index-storage.h"
#include "index-sort.h"
#include <stdlib.h>
#define RENUMBER_SPACE 100
struct mail_sort_node {
};
struct mail_search_sort_program {
struct mailbox_transaction_context *t;
const struct mail_sort_node *nodes_ptr;
unsigned int nodes_count, iter_idx;
unsigned int first_missing_sort_id_idx;
unsigned int reverse:1;
unsigned int sort_ids_added:1;
unsigned int missing_sort_ids:1;
};
struct sort_cmp_context {
struct mail_search_sort_program *program;
};
static struct sort_cmp_context static_node_cmp_context;
struct mail_search_sort_program *
const enum mail_sort_type *sort_program)
{
struct mail_search_sort_program *program;
unsigned int i;
return NULL;
/* we support internal sorting by the primary condition */
program->t = t;
/* primary reversion isn't stored to sort_program. we handle it by
iterating backwards at the end. */
for (i = 1; i < MAX_SORT_PROGRAM_SIZE; i++) {
if (sort_program[i] == MAIL_SORT_END)
break;
}
if (i == MAX_SORT_PROGRAM_SIZE)
i_panic("index_sort_program_init(): Invalid sort program");
case MAIL_SORT_ARRIVAL:
break;
case MAIL_SORT_DATE:
break;
case MAIL_SORT_SIZE:
break;
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();
}
return program;
}
{
}
{
struct message_address *addr;
const char *str;
return "";
(const unsigned char *)str,
}
static void
{
const char *str;
switch (sort_type & MAIL_SORT_MASK) {
case MAIL_SORT_SUBJECT:
return;
return;
case MAIL_SORT_CC:
break;
case MAIL_SORT_FROM:
break;
case MAIL_SORT_TO:
break;
default:
i_unreached();
}
}
{
time_t t;
if (mail_get_received_date(mail, &t) < 0)
t = 0;
/* FIXME: truncation isn't good.. */
return t <= 0 ? 1 :
}
{
time_t t;
t = 0;
if (t == 0) {
if (mail_get_received_date(mail, &t) < 0)
return 1;
}
/* FIXME: truncation isn't good.. */
return t <= 0 ? 1 :
}
{
return 1;
/* FIXME: elsewhere we support 64bit message sizes, but here
we support only 32bit sizes.. It's a bit too much trouble
to support 64bit here currently, so until such messages
actually start showing up somewhere, 32bit is enough */
return size + 1;
}
const enum mail_sort_type *sort_program,
const struct mail_sort_node *n1,
const struct mail_sort_node *n2)
{
enum mail_sort_type sort_type;
int ret = 0;
switch (sort_type) {
case MAIL_SORT_CC:
case MAIL_SORT_FROM:
case MAIL_SORT_TO:
case MAIL_SORT_SUBJECT:
} T_FRAME_END;
break;
case MAIL_SORT_ARRIVAL:
break;
case MAIL_SORT_DATE:
break;
case MAIL_SORT_SIZE:
break;
case MAIL_SORT_END:
case MAIL_SORT_MASK:
case MAIL_SORT_FLAG_REVERSE:
i_unreached();
}
if (ret == 0)
/* primary reversion isn't in sort_program */
if ((*sort_program & MAIL_SORT_FLAG_REVERSE) != 0)
return ret;
}
{
return -1;
return 1;
}
{
const enum mail_sort_type *sort_program;
/* Use sort IDs only if both have them */
return -1;
return 1;
} else {
}
}
static void
unsigned int right_idx)
{
struct mail_sort_node *nodes;
unsigned int i, count, rightmost_idx;
unsigned int skip;
bool have_right_sort_id = FALSE;
/* get the sort IDs from left and right */
/* 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) {
left_idx--;
i_assert(left_sort_id != 0);
}
while (right_idx < rightmost_idx) {
break;
}
}
left_idx++;
}
right_idx--;
}
/* give (new) sort IDs to all nodes in left_idx..right_idx range.
divide the available space so that each messagets an equal sized
share. some messages' sort strings may be equivalent, so give them
the same sort IDs. */
);
/* 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;
str_truncate(left_str, 0);
}
}
}
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;
);
}
}
static void
{
/* insert missing nodes */
/* sort everything. use sort_ids whenever possible */
/* we can now build the sort_ids */
/* @UNSAFE: and finally get the range sorted back by sequence */
for (i = 0; i < count; i++)
}
{
struct index_transaction_context *t =
(struct index_transaction_context *)program->t;
const void *data;
/* add messages that have sort_ids. they're always at the beginning
of the mailbox. */
/* the rest don't have sort_ids either */
break;
}
}
/* add the missing sort IDs to index */
}
/* set missing sort_ids to wanted nodes */
}
{
struct index_transaction_context *t =
(struct index_transaction_context *)program->t;
const void *data;
struct mail_sort_node node;
/* no indexing for this field */
return;
}
}
}
{
struct mail_sort_node *nodes;
if (program->missing_sort_ids) {
}
}
{
const struct mail_sort_node *node;
return FALSE;
} else {
return FALSE;
}
return TRUE;
}