/*
mairix - message index builder and finder for maildir folders.
**********************************************************************
* Copyright (C) Richard P. Curnow 2002,2003,2004,2005,2007
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of version 2 of the GNU General Public License as
* published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License along
* with this program; if not, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
*
**********************************************************************
*/
/* Handle complete database */
#include "mairix.h"
#include "reader.h"
#include <ctype.h>
#include <assert.h>
#include <sys/time.h>
#include <unistd.h>
struct sortable_token {/*{{{*/
char *text;
int index;
};
/*}}}*/
static int compare_sortable_tokens(const void *a, const void *b)/*{{{*/
{
const struct sortable_token *aa = (const struct sortable_token *) a;
const struct sortable_token *bb = (const struct sortable_token *) b;
int foo;
foo = strcmp(aa->text, bb->text);
if (foo) {
return foo;
} else {
if (aa->index < bb->index) return -1;
else if (aa->index > bb->index) return +1;
else return 0;
}
}
/*}}}*/
static void check_toktable_enc_integrity(int n_msgs, struct toktable *table)/*{{{*/
{
/* FIXME : Check reachability of tokens that are displaced from their natural
* hash bucket (if deletions have occurred during purge). */
int idx, incr;
int i, k;
unsigned char *j, *last_char;
int broken_chains = 0;
struct sortable_token *sort_list;
int any_duplicates;
for (i=0; i<table->size; i++) {
struct token *tok = table->tokens[i];
if (tok) {
idx = 0;
incr = 0;
last_char = tok->match0.msginfo + tok->match0.n;
for (j = tok->match0.msginfo; j < last_char; ) {
incr = read_increment(&j);
idx += incr;
}
if (idx != tok->match0.highest) {
fprintf(stderr, "broken encoding chain for token <%s>, highest=%ld\n", tok->text, tok->match0.highest);
fflush(stderr);
broken_chains = 1;
}
if (idx >= n_msgs) {
fprintf(stderr, "end of chain higher than number of message paths (%d) for token <%s>\n", n_msgs, tok->text);
fflush(stderr);
broken_chains = 1;
}
}
}
assert(!broken_chains);
/* Check there are no duplicated tokens in the table. */
sort_list = new_array(struct sortable_token, table->n);
k = 0;
for (i=0; i<table->size; i++) {
struct token *tok = table->tokens[i];
if (tok) {
sort_list[k].text = new_string(tok->text);
sort_list[k].index = i;
k++;
}
}
assert(k == table->n);
qsort(sort_list, table->n, sizeof(struct sortable_token), compare_sortable_tokens);
/* Check for uniqueness of neighbouring token texts */
any_duplicates = 0;
for (i=0; i<(table->n - 1); i++) {
if (!strcmp(sort_list[i].text, sort_list[i+1].text)) {
fprintf(stderr, "Token table contains duplicated token %s at indices %d and %d\n",
sort_list[i].text, sort_list[i].index, sort_list[i+1].index);
any_duplicates = 1;
}
}
/* release */
for (i=0; i<table->n; i++) {
free(sort_list[i].text);
}
free(sort_list);
if (any_duplicates) {
fprintf(stderr, "Token table contained duplicate entries, aborting\n");
assert(0);
}
}
/*}}}*/
static int compare_strings(const void *a, const void *b)/*{{{*/
{
const char **aa = (const char **) a;
const char **bb = (const char **) b;
return strcmp(*aa, *bb);
}
/*}}}*/
static void check_message_path_integrity(struct database *db)/*{{{*/
{
/* TODO : for now only checks integrity of non-mbox paths. */
/* Check there are no duplicates */
int i;
int n;
int has_duplicate = 0;
char **paths;
paths = new_array(char *, db->n_msgs);
for (i=0, n=0; i<db->n_msgs; i++) {
switch (db->type[i]) {
case MTY_DEAD:
case MTY_MBOX:
break;
case MTY_FILE:
paths[n++] = db->msgs[i].src.mpf.path;
break;
}
}
qsort(paths, n, sizeof(char *), compare_strings);
for (i=1; i<n; i++) {
if (!strcmp(paths[i-1], paths[i])) {
fprintf(stderr, "Path <%s> repeated\n", paths[i]);
has_duplicate = 1;
}
}
fflush(stderr);
assert(!has_duplicate);
free(paths);
return;
}
/*}}}*/
void check_database_integrity(struct database *db)/*{{{*/
{
if (verbose) fprintf(stderr, "Checking message path integrity\n");
check_message_path_integrity(db);
/* Just check encoding chains for now */
if (verbose) fprintf(stderr, "Checking to\n");
check_toktable_enc_integrity(db->n_msgs, db->to);
if (verbose) fprintf(stderr, "Checking cc\n");
check_toktable_enc_integrity(db->n_msgs, db->cc);
if (verbose) fprintf(stderr, "Checking from\n");
check_toktable_enc_integrity(db->n_msgs, db->from);
if (verbose) fprintf(stderr, "Checking subject\n");
check_toktable_enc_integrity(db->n_msgs, db->subject);
if (verbose) fprintf(stderr, "Checking body\n");
check_toktable_enc_integrity(db->n_msgs, db->body);
if (verbose) fprintf(stderr, "Checking attachment_name\n");
check_toktable_enc_integrity(db->n_msgs, db->attachment_name);
}
/*}}}*/
struct database *new_database(void)/*{{{*/
{
struct database *result = new(struct database);
struct timeval tv;
pid_t pid;
result->to = new_toktable();
result->cc = new_toktable();
result->from = new_toktable();
result->subject = new_toktable();
result->body = new_toktable();
result->attachment_name = new_toktable();
result->msg_ids = new_toktable2();
gettimeofday(&tv, NULL);
pid = getpid();
result->hash_key = tv.tv_sec ^ (pid ^ (tv.tv_usec << 15));
result->msgs = NULL;
result->type = NULL;
result->n_msgs = 0;
result->max_msgs = 0;
result->mboxen = NULL;
result->n_mboxen = 0;
result->max_mboxen = 0;
return result;
}
/*}}}*/
void free_database(struct database *db)/*{{{*/
{
int i;
free_toktable(db->to);
free_toktable(db->cc);
free_toktable(db->from);
free_toktable(db->subject);
free_toktable(db->body);
free_toktable(db->attachment_name);
free_toktable2(db->msg_ids);
if (db->msgs) {
for (i=0; i<db->n_msgs; i++) {
switch (db->type[i]) {
case MTY_DEAD:
break;
case MTY_MBOX:
break;
case MTY_FILE:
assert(db->msgs[i].src.mpf.path);
free(db->msgs[i].src.mpf.path);
break;
}
}
free(db->msgs);
free(db->type);
}
free(db);
}
/*}}}*/
static int get_max (int a, int b) {/*{{{*/
return (a > b) ? a : b;
}
/*}}}*/
static void import_toktable(char *data, unsigned int hash_key, int n_msgs, struct toktable_db *in, struct toktable *out)/*{{{*/
{
int n, size, i;
n = in->n;
size = 1;
while (size < n) size <<= 1;
size <<= 1; /* safe hash table size */
out->size = size;
out->mask = size - 1;
out->n = n;
out->tokens = new_array(struct token *, size);
memset(out->tokens, 0, size * sizeof(struct token *));
out->hwm = (n + size) >> 1;
for (i=0; i<n; i++) {
unsigned int hash, index;
char *text;
unsigned char *enc;
int enc_len;
struct token *nt;
int enc_hi;
int idx, incr;
unsigned char *j;
/* Recover enc_len and enc_hi from the data */
enc = (unsigned char *) data + in->enc_offsets[i];
idx = 0;
for (j = enc; *j != 0xff; ) {
incr = read_increment(&j);
idx += incr;
}
enc_len = j - enc;
enc_hi = idx;
text = data + in->tok_offsets[i];
hash = hashfn((unsigned char *) text, strlen(text), hash_key);
nt = new(struct token);
nt->hashval = hash;
nt->text = new_string(text);
/* Allow a bit of headroom for adding more entries later */
nt->match0.max = get_max(16, enc_len + (enc_len >> 1));
nt->match0.n = enc_len;
nt->match0.highest = enc_hi;
assert(nt->match0.highest < n_msgs);
nt->match0.msginfo = new_array(unsigned char, nt->match0.max);
memcpy(nt->match0.msginfo, enc, nt->match0.n);
index = hash & out->mask;
while (out->tokens[index]) {
/* Audit to look for corrupt database with multiple entries for the same
* string. */
if (!strcmp(nt->text, out->tokens[index]->text)) {
fprintf(stderr, "\n!!! Corrupt token table found in database, token <%s> duplicated, aborting\n",
nt->text);
fprintf(stderr, " Delete the database file and rebuild from scratch as a workaround\n");
/* No point going on - need to find out why the database got corrupted
* in the 1st place. Workaround for user - rebuild database from
* scratch by deleting it then rerunning. */
unlock_and_exit(1);
}
++index;
index &= out->mask;
}
out->tokens[index] = nt;
}
}
/*}}}*/
static void import_toktable2(char *data, unsigned int hash_key, int n_msgs, struct toktable2_db *in, struct toktable2 *out)/*{{{*/
{
int n, size, i;
n = in->n;
size = 1;
while (size < n) size <<= 1;
size <<= 1; /* safe hash table size */
out->size = size;
out->mask = size - 1;
out->n = n;
out->tokens = new_array(struct token2 *, size);
memset(out->tokens, 0, size * sizeof(struct token *));
out->hwm = (n + size) >> 1;
for (i=0; i<n; i++) {
unsigned int hash, index;
char *text;
struct token2 *nt;
unsigned char *enc0, *enc1;
int enc0_len, enc1_len;
int enc0_hi, enc1_hi;
int idx, incr;
unsigned char *j;
/*{{{ do enc0*/
enc0 = (unsigned char *) data + in->enc0_offsets[i];
idx = 0;
for (j = enc0; *j != 0xff; ) {
incr = read_increment(&j);
idx += incr;
}
enc0_len = j - enc0;
enc0_hi = idx;
/*}}}*/
/*{{{ do enc1*/
enc1 = (unsigned char *) data + in->enc1_offsets[i];
idx = 0;
for (j = enc1; *j != 0xff; ) {
incr = read_increment(&j);
idx += incr;
}
enc1_len = j - enc1;
enc1_hi = idx;
/*}}}*/
text = data + in->tok_offsets[i];
hash = hashfn((unsigned char *) text, strlen(text), hash_key);
nt = new(struct token2);
nt->hashval = hash;
nt->text = new_string(text);
/* Allow a bit of headroom for adding more entries later */
/*{{{ set up match0 chain */
nt->match0.max = get_max(16, enc0_len + (enc0_len >> 1));
nt->match0.n = enc0_len;
nt->match0.highest = enc0_hi;
assert(nt->match0.highest < n_msgs);
nt->match0.msginfo = new_array(unsigned char, nt->match0.max);
memcpy(nt->match0.msginfo, enc0, nt->match0.n);
/*}}}*/
/*{{{ set up match1 chain */
nt->match1.max = get_max(16, enc1_len + (enc1_len >> 1));
nt->match1.n = enc1_len;
nt->match1.highest = enc1_hi;
assert(nt->match1.highest < n_msgs);
nt->match1.msginfo = new_array(unsigned char, nt->match1.max);
memcpy(nt->match1.msginfo, enc1, nt->match1.n);
/*}}}*/
index = hash & out->mask;
while (out->tokens[index]) {
++index;
index &= out->mask;
}
out->tokens[index] = nt;
}
}
/*}}}*/
struct database *new_database_from_file(char *db_filename, int do_integrity_checks)/*{{{*/
{
/* Read existing database from file for doing incremental update */
struct database *result;
struct read_db *input;
int i, n, N;
result = new_database();
input = open_db(db_filename);
if (!input) {
/* Nothing to initialise */
if (verbose) printf("Database file was empty, creating a new database\n");
return result;
}
/* Build pathname information */
n = result->n_msgs = input->n_msgs;
result->max_msgs = input->n_msgs; /* let it be extended as-and-when */
result->msgs = new_array(struct msgpath, n);
result->type = new_array(enum message_type, n);
result->hash_key = input->hash_key;
/* Set up mbox structures */
N = result->n_mboxen = result->max_mboxen = input->n_mboxen;
result->mboxen = N ? (new_array(struct mbox, N)) : NULL;
for (i=0; i<N; i++) {
int nn;
if (input->mbox_paths_table[i]) {
result->mboxen[i].path = new_string(input->data + input->mbox_paths_table[i]);
} else {
/* mbox is dead. */
result->mboxen[i].path = NULL;
}
result->mboxen[i].file_mtime = input->mbox_mtime_table[i];
result->mboxen[i].file_size = input->mbox_size_table[i];
nn = result->mboxen[i].n_msgs = input->mbox_entries_table[i];
result->mboxen[i].max_msgs = nn;
result->mboxen[i].start = new_array(off_t, nn);
result->mboxen[i].len = new_array(size_t, nn);
result->mboxen[i].check_all = new_array(checksum_t, nn);
/* Copy the entire checksum table in one go. */
memcpy(result->mboxen[i].check_all,
input->data + input->mbox_checksum_table[i],
nn * sizeof(checksum_t));
result->mboxen[i].n_so_far = 0;
}
for (i=0; i<n; i++) {
switch (rd_msg_type(input, i)) {
case DB_MSG_DEAD:
result->type[i] = MTY_DEAD;
break;
case DB_MSG_FILE:
result->type[i] = MTY_FILE;
result->msgs[i].src.mpf.path = new_string(input->data + input->path_offsets[i]);
result->msgs[i].src.mpf.mtime = input->mtime_table[i];
result->msgs[i].src.mpf.size = input->size_table[i];
break;
case DB_MSG_MBOX:
{
unsigned int mbi, msgi;
int n;
struct mbox *mb;
result->type[i] = MTY_MBOX;
decode_mbox_indices(input->path_offsets[i], &mbi, &msgi);
result->msgs[i].src.mbox.file_index = mbi;
mb = &result->mboxen[mbi];
assert(mb->n_so_far == msgi);
n = mb->n_so_far;
result->msgs[i].src.mbox.msg_index = n;
mb->start[n] = input->mtime_table[i];
mb->len[n] = input->size_table[i];
++mb->n_so_far;
}
break;
}
result->msgs[i].seen = (input->msg_type_and_flags[i] & FLAG_SEEN) ? 1:0;
result->msgs[i].replied = (input->msg_type_and_flags[i] & FLAG_REPLIED) ? 1:0;
result->msgs[i].flagged = (input->msg_type_and_flags[i] & FLAG_FLAGGED) ? 1:0;
result->msgs[i].date = input->date_table[i];
result->msgs[i].tid = input->tid_table[i];
}
import_toktable(input->data, input->hash_key, result->n_msgs, &input->to, result->to);
import_toktable(input->data, input->hash_key, result->n_msgs, &input->cc, result->cc);
import_toktable(input->data, input->hash_key, result->n_msgs, &input->from, result->from);
import_toktable(input->data, input->hash_key, result->n_msgs, &input->subject, result->subject);
import_toktable(input->data, input->hash_key, result->n_msgs, &input->body, result->body);
import_toktable(input->data, input->hash_key, result->n_msgs, &input->attachment_name, result->attachment_name);
import_toktable2(input->data, input->hash_key, result->n_msgs, &input->msg_ids, result->msg_ids);
close_db(input);
if (do_integrity_checks) {
check_database_integrity(result);
}
return result;
}
/*}}}*/
static void add_angled_terms(int file_index, unsigned int hash_key, struct toktable2 *table, int add_to_chain1, char *s)/*{{{*/
{
char *left, *right;
if (s) {
left = strchr(s, '<');
while (left) {
right = strchr(left, '>');
if (right) {
*right = '\0';
add_token2_in_file(file_index, hash_key, left+1, table, add_to_chain1);
*right = '>'; /* restore */
} else {
break;
}
left = strchr(right, '<');
}
}
}
/*}}}*/
/* Macro for what characters can make up token strings.
The following characters have special meanings:
0x2b +
0x2d -
0x2e .
0x40 @
0x5f _
since they can occur within email addresses and message IDs when considered
as a whole rather than as individual words. Underscore (0x5f) is considered
a word-character always too.
*/
static unsigned char special_table[256] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 00-0f */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 10-1f */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 2, 2, 0, /* 20-2f */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 30-3f */
2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 40-4f */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, /* 50-5f */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 60-6f */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 70-7f */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 80-8f */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 90-9f */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* a0-af */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* b0-bf */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* c0-cf */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* d0-df */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* e0-ef */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 /* f0-ff */
};
#if 0
#define CHAR_VALID(x,mask) (isalnum((unsigned char) x) || (special_table[(unsigned int)(unsigned char) x] & mask))
#endif
static inline int char_valid_p(char x, unsigned int mask)/*{{{*/
{
unsigned char xx = (unsigned char) x;
if (isalnum(xx)) return 1;
else if (special_table[(unsigned int) xx] & mask) return 1;
else return 0;
}
/*}}}*/
static void tokenise_string(int file_index, unsigned int hash_key, struct toktable *table, char *data, int match_mask)/*{{{*/
{
char *ss, *es, old_es;
ss = data;
for (;;) {
while (*ss && !char_valid_p(*ss,match_mask)) ss++;
if (!*ss) break;
es = ss + 1;
while (*es && char_valid_p(*es,match_mask)) es++;
/* deal with token [ss,es) */
old_es = *es;
*es = '\0';
/* FIXME: Ought to do this by passing start and length - clean up later */
add_token_in_file(file_index, hash_key, ss, table);
*es = old_es;
if (!*es) break;
ss = es;
}
}
/*}}}*/
static void tokenise_html_string(int file_index, unsigned int hash_key, struct toktable *table, char *data)/*{{{*/
{
char *ss, *es, old_es;
/* FIXME : Probably want to rewrite this as an explicit FSM */
ss = data;
for (;;) {
/* Assume < and > are never valid token characters ! */
while (*ss && !char_valid_p(*ss, 1)) {
if (*ss++ == '<') {
/* Skip over HTML tag */
while (*ss && (*ss != '>')) ss++;
}
}
if (!*ss) break;
es = ss + 1;
while (*es && char_valid_p(*es, 1)) es++;
/* deal with token [ss,es) */
old_es = *es;
*es = '\0';
/* FIXME: Ought to do this by passing start and length - clean up later */
add_token_in_file(file_index, hash_key, ss, table);
*es = old_es;
if (!*es) break;
ss = es;
}
}
/*}}}*/
void tokenise_message(int file_index, struct database *db, struct rfc822 *msg)/*{{{*/
{
struct attachment *a;
/* Match on whole addresses in these headers as well as the individual words */
if (msg->hdrs.to) {
tokenise_string(file_index, db->hash_key, db->to, msg->hdrs.to, 1);
tokenise_string(file_index, db->hash_key, db->to, msg->hdrs.to, 2);
}
if (msg->hdrs.cc) {
tokenise_string(file_index, db->hash_key, db->cc, msg->hdrs.cc, 1);
tokenise_string(file_index, db->hash_key, db->cc, msg->hdrs.cc, 2);
}
if (msg->hdrs.from) {
tokenise_string(file_index, db->hash_key, db->from, msg->hdrs.from, 1);
tokenise_string(file_index, db->hash_key, db->from, msg->hdrs.from, 2);
}
if (msg->hdrs.subject) tokenise_string(file_index, db->hash_key, db->subject, msg->hdrs.subject, 1);
for (a=msg->atts.next; a!=&msg->atts; a=a->next) {
switch (a->ct) {
case CT_TEXT_PLAIN:
tokenise_string(file_index, db->hash_key, db->body, a->data.normal.bytes, 1);
break;
case CT_TEXT_HTML:
tokenise_html_string(file_index, db->hash_key, db->body, a->data.normal.bytes);
break;
case CT_MESSAGE_RFC822:
/* Just recurse for now - maybe we should have separate token tables
* for tokens occurring in embedded messages? */
if (a->data.rfc822) {
tokenise_message(file_index, db, a->data.rfc822);
}
break;
default:
/* Don't do anything - unknown text format or some nasty binary stuff.
* In future, we could have all kinds of 'plug-ins' here, e.g.
* something that can parse PDF to get the basic text strings out of
* the pages? */
break;
}
if (a->filename) {
add_token_in_file(file_index, db->hash_key, a->filename, db->attachment_name);
}
}
/* Deal with threading information */
add_angled_terms(file_index, db->hash_key, db->msg_ids, 1, msg->hdrs.message_id);
add_angled_terms(file_index, db->hash_key, db->msg_ids, 0, msg->hdrs.in_reply_to);
add_angled_terms(file_index, db->hash_key, db->msg_ids, 0, msg->hdrs.references);
}
/*}}}*/
static void scan_maildir_flags(struct msgpath *m)/*{{{*/
{
const char *p, *start;
start = m->src.mpf.path;
m->seen = 0;
m->replied = 0;
m->flagged = 0;
for (p=start; *p; p++) {}
for (p--; (p >= start) && ((*p) != ':'); p--) {}
if (p >= start) {
if (!strncmp(p, ":2,", 3)) {
p += 3;
while (*p) {
switch (*p) {
case 'F': m->flagged = 1; break;
case 'R': m->replied = 1; break;
case 'S': m->seen = 1; break;
default: break;
}
p++;
}
}
}
}
/*}}}*/
static void scan_new_messages(struct database *db, int start_at)/*{{{*/
{
int i;
for (i=start_at; i<db->n_msgs; i++) {
struct rfc822 *msg = NULL;
switch (db->type[i]) {
case MTY_DEAD:
assert(0);
break;
case MTY_MBOX:
assert(0); /* Should never get here - mbox messages are scanned elsewhere. */
break;
case MTY_FILE:
if (verbose) fprintf(stderr, "Scanning <%s>\n", db->msgs[i].src.mpf.path);
msg = make_rfc822(db->msgs[i].src.mpf.path);
break;
}
if(msg)
{
db->msgs[i].date = msg->hdrs.date;
scan_maildir_flags(&db->msgs[i]);
tokenise_message(i, db, msg);
free_rfc822(msg);
}
else
fprintf(stderr, "Skipping %s (could not parse message)\n", db->msgs[i].src.mpf.path);
}
}
/*}}}*/
static inline void set_bit(unsigned long *x, int n)/*{{{*/
{
int set;
unsigned long mask;
set = (n >> 5);
mask = (1UL << (n & 31));
x[set] |= mask;
}
/*}}}*/
static inline int isset_bit(unsigned long *x, int n)/*{{{*/
{
int set;
unsigned long mask;
set = (n >> 5);
mask = (1UL << (n & 31));
return (x[set] & mask) ? 1 : 0;
}
/*}}}*/
static int find_base(int *table, int index) {/*{{{*/
int a = index;
/* TODO : make this compress the path lengths down to the base entry */
while (table[a] != a) {
a = table[a];
}
return a;
}
/*}}}*/
static void find_threading(struct database *db)/*{{{*/
{
/* ix is a table mapping path array index to the lowest path array index that
* is known to share at least one message ID in its hdrs somewhere (i.e. they
* must be in the same thread) */
int *ix;
int i, m, np, nm, sm;
int next_tid;
np = db->n_msgs;
nm = db->msg_ids->n;
sm = db->msg_ids->size;
ix = new_array(int, np);
for (i=0; i<np; i++) {
ix[i] = i; /* default - every message in a thread of its own */
}
for (m=0; m<sm; m++) {
struct token2 *tok = db->msg_ids->tokens[m];
if (tok) {
unsigned char *j = tok->match0.msginfo;
unsigned char *last_char = j + tok->match0.n;
int cur = 0, incr, first=1;
int new_base=-1, old_base;
while (j < last_char) {
incr = read_increment(&j);
cur += incr;
if (first) {
new_base = find_base(ix, cur);
first = 0;
} else {
old_base = find_base(ix, cur);
if (old_base < new_base) {
ix[new_base] = old_base;
new_base = old_base;
} else if (old_base > new_base) {
assert(new_base != -1);
ix[old_base] = new_base;
}
}
}
}
}
/* Now make each entry point directly to its base */
for (i=0; i<np; i++) {
if (ix[i] != i) {
/* Sure to work as we're going up from the bottom */
ix[i] = ix[ix[i]];
}
}
/* Now allocate contiguous thread group numbers */
next_tid = 0;
for (i=0; i<np; i++) {
if (ix[i] == i) {
db->msgs[i].tid = next_tid++;
} else {
db->msgs[i].tid = db->msgs[ix[i]].tid;
}
}
free(ix);
return;
}
/*}}}*/
static int lookup_msgpath(struct msgpath *sorted_paths, int n_msgs, char *key)/*{{{*/
{
/* Implement bisection search */
int l, h, m, r;
l = 0, h = n_msgs;
m = -1;
while (h > l) {
m = (h + l) >> 1;
/* Should only get called on 'file' type messages - TBC */
r = strcmp(sorted_paths[m].src.mpf.path, key);
if (r == 0) break;
if (l == m) return -1;
if (r > 0) h = m;
else l = m;
}
return m;
}
/*}}}*/
void maybe_grow_message_arrays(struct database *db)/*{{{*/
{
if (db->n_msgs == db->max_msgs) {
if (db->max_msgs <= 128) {
db->max_msgs = 256;
} else {
db->max_msgs += (db->max_msgs >> 1);
}
db->msgs = grow_array(struct msgpath, db->max_msgs, db->msgs);
db->type = grow_array(enum message_type, db->max_msgs, db->type);
}
}
/*}}}*/
static void add_msg_path(struct database *db, char *path, time_t mtime, size_t message_size)/*{{{*/
{
maybe_grow_message_arrays(db);
db->type[db->n_msgs] = MTY_FILE;
db->msgs[db->n_msgs].src.mpf.path = new_string(path);
db->msgs[db->n_msgs].src.mpf.mtime = mtime;
db->msgs[db->n_msgs].src.mpf.size = message_size;
++db->n_msgs;
}
/*}}}*/
static int do_stat(struct msgpath *mp)/*{{{*/
{
struct stat sb;
int status;
status = stat(mp->src.mpf.path, &sb);
if ((status < 0) ||
!S_ISREG(sb.st_mode)) {
return 0;
} else {
mp->src.mpf.mtime = sb.st_mtime;
mp->src.mpf.size = sb.st_size;
return 1;
}
}
/*}}}*/
int update_database(struct database *db, struct msgpath *sorted_paths, int n_msgs, int do_fast_index)/*{{{*/
{
/* The incoming list must be sorted into order, to make binary searching
* possible. We search for each existing path in the incoming sorted array.
* If the date differs, or the file no longer exist, the existing database
* entry for that file is nulled. (These are only recovered if the database
* is actively compressed.) If the date differed, a new entry for the file
* is put at the end of the list. Similarly, any new file goes at the end.
* These new entries are all rescanned to find tokens and add them to the
* database. */
char *file_in_db, *file_in_new_list;
int matched_index;
int i, new_entries_start_at;
int any_new, n_newly_pruned, n_already_dead;
int status;
file_in_db = new_array(char, n_msgs);
file_in_new_list = new_array(char, db->n_msgs);
bzero(file_in_db, n_msgs);
bzero(file_in_new_list, db->n_msgs);
n_already_dead = 0;
n_newly_pruned = 0;
for (i=0; i<db->n_msgs; i++) {
switch (db->type[i]) {
case MTY_FILE:
matched_index = lookup_msgpath(sorted_paths, n_msgs, db->msgs[i].src.mpf.path);
if (matched_index >= 0) {
if (do_fast_index) {
/* Assume the presence of a matching path is good enough without
* even bothering to stat the file that's there now. */
file_in_db[matched_index] = 1;
file_in_new_list[i] = 1;
} else {
status = do_stat(sorted_paths + matched_index);
if (status) {
if (sorted_paths[matched_index].src.mpf.mtime == db->msgs[i].src.mpf.mtime) {
/* Treat stale files as though the path has changed. */
file_in_db[matched_index] = 1;
file_in_new_list[i] = 1;
} else {
fprintf(stderr, "mtime failed for '%s'\n", sorted_paths[matched_index].src.mpf.path);
}
} else {
/* This path will get treated as dead, and be re-stated below.
* When that stat fails, the path won't get added to the db. */
}
}
}
break;
case MTY_MBOX:
/* Nothing to do on this pass. */
break;
case MTY_DEAD:
break;
}
}
/* Add new entries to database */
new_entries_start_at = db->n_msgs;
for (i=0; i<db->n_msgs; i++) {
/* Weed dead entries */
switch (db->type[i]) {
case MTY_FILE:
if (!file_in_new_list[i]) {
free(db->msgs[i].src.mpf.path);
db->msgs[i].src.mpf.path = NULL;
db->type[i] = MTY_DEAD;
++n_newly_pruned;
}
break;
case MTY_MBOX:
{
int msg_index, file_index, number_valid;
int mbox_valid;
msg_index = db->msgs[i].src.mbox.msg_index;
file_index = db->msgs[i].src.mbox.file_index;
assert (file_index < db->n_mboxen);
mbox_valid = (db->mboxen[file_index].path) ? 1 : 0;
number_valid = db->mboxen[file_index].n_old_msgs_valid;
if (!mbox_valid || (msg_index >= number_valid)) {
db->type[i] = MTY_DEAD;
++n_newly_pruned;
}
}
break;
case MTY_DEAD:
/* already dead */
++n_already_dead;
break;
}
}
if (verbose) {
fprintf(stderr, "%d newly dead messages, %d messages now dead in total\n", n_newly_pruned, n_newly_pruned+n_already_dead);
}
any_new = 0;
for (i=0; i<n_msgs; i++) {
if (!file_in_db[i]) {
int status;
any_new = 1;
/* The 'sorted_paths' array is only used for file-per-message folders. */
status = do_stat(sorted_paths + i);
if (status) {
/* We only add files that could be successfully stat()'d as regular
* files. */
add_msg_path(db, sorted_paths[i].src.mpf.path, sorted_paths[i].src.mpf.mtime, sorted_paths[i].src.mpf.size);
} else {
fprintf(stderr, "Cannot add '%s' to database; stat() failed\n", sorted_paths[i].src.mpf.path);
}
}
}
if (any_new) {
scan_new_messages(db, new_entries_start_at);
}
/* Add newly found mbox messages. */
any_new |= add_mbox_messages(db);
if (any_new) {
find_threading(db);
} else {
if (verbose) fprintf(stderr, "No new messages found\n");
}
free(file_in_db);
free(file_in_new_list);
return any_new || (n_newly_pruned > 0);
}
/*}}}*/
static void recode_encoding(struct matches *m, int *new_idx)/*{{{*/
{
unsigned char *new_enc, *old_enc;
unsigned char *j, *last_char;
int incr, idx, n_idx;
old_enc = m->msginfo;
j = old_enc;
last_char = old_enc + m->n;
new_enc = new_array(unsigned char, m->max); /* Probably not bigger than this. */
m->n = 0;
m->highest = 0;
m->msginfo = new_enc;
idx = 0;
while (j < last_char) {
incr = read_increment(&j);
idx += incr;
n_idx = new_idx[idx];
if (n_idx >= 0) {
check_and_enlarge_encoding(m);
insert_index_on_encoding(m, n_idx);
}
}
free(old_enc);
}
/*}}}*/
static void recode_toktable(struct toktable *tbl, int *new_idx)/*{{{*/
{
/* Re-encode the vectors according to the new path indices */
int i;
int any_dead = 0;
int any_moved, pass;
for (i=0; i<tbl->size; i++) {
struct token *tok = tbl->tokens[i];
if (tok) {
recode_encoding(&tok->match0, new_idx);
if (tok->match0.n == 0) {
/* Delete this token. Gotcha - there may be tokens further on in the
* array that didn't get their natural hash bucket due to collisions.
* Need to shuffle such tokens up to guarantee that the buckets between
* the natural one and the one where they are now are all occupied, to
* prevent their lookups failing. */
#if 0
fprintf(stderr, "Token <%s> (bucket %d) no longer has files containing it, deleting\n", tok->text, i);
#endif
free_token(tok);
tbl->tokens[i] = NULL;
--tbl->n; /* Maintain number in use counter */
any_dead = 1;
}
}
}
if (any_dead) {
/* Now close gaps. This has to be done in a second pass, otherwise we get a
* problem with moving entries that need deleting back before the current
scan point. */
pass = 1;
for (;;) {
int i;
if (verbose) {
fprintf(stderr, "Pass %d\n", pass);
}
any_moved = 0;
for (i=0; i<tbl->size; i++) {
if (tbl->tokens[i]) {
int nat_bucket_i;
nat_bucket_i = tbl->tokens[i]->hashval & tbl->mask;
if (nat_bucket_i != i) {
/* Find earliest bucket that we could move i to */
int j = nat_bucket_i;
while (j != i) {
if (!tbl->tokens[j]) {
/* put it here */
#if 0
fprintf(stderr, "Moved <%s> from bucket %d to %d (natural bucket %d)\n", tbl->tokens[i]->text, i, j, nat_bucket_i);
#endif
tbl->tokens[j] = tbl->tokens[i];
tbl->tokens[i] = NULL;
any_moved = 1;
break;
} else {
j++;
j &= tbl->mask;
}
}
if (tbl->tokens[i]) {
#if 0
fprintf(stderr, "NOT moved <%s> from bucket %d (natural bucket %d)\n", tbl->tokens[i]->text, i, nat_bucket_i);
#endif
}
}
}
}
if (!any_moved) break;
pass++;
}
}
}
/*}}}*/
static void recode_toktable2(struct toktable2 *tbl, int *new_idx)/*{{{*/
{
/* Re-encode the vectors according to the new path indices */
int i;
int any_dead = 0;
int any_moved, pass;
for (i=0; i<tbl->size; i++) {
struct token2 *tok = tbl->tokens[i];
if (tok) {
recode_encoding(&tok->match0, new_idx);
recode_encoding(&tok->match1, new_idx);
if ((tok->match0.n == 0) && (tok->match1.n == 0)) {
/* Delete this token. Gotcha - there may be tokens further on in the
* array that didn't get their natural hash bucket due to collisions.
* Need to shuffle such tokens up to guarantee that the buckets between
* the natural one and the one where they are now are all occupied, to
* prevent their lookups failing. */
#if 0
fprintf(stderr, "Token <%s> (bucket %d) no longer has files containing it, deleting\n", tok->text, i);
#endif
free_token2(tok);
tbl->tokens[i] = NULL;
--tbl->n; /* Maintain number in use counter */
any_dead = 1;
}
}
}
if (any_dead) {
/* Now close gaps. This has to be done in a second pass, otherwise we get a
* problem with moving entries that need deleting back before the current
scan point. */
pass = 1;
for (;;) {
int i;
if (verbose) {
fprintf(stderr, "Pass %d\n", pass);
}
any_moved = 0;
for (i=0; i<tbl->size; i++) {
if (tbl->tokens[i]) {
int nat_bucket_i;
nat_bucket_i = tbl->tokens[i]->hashval & tbl->mask;
if (nat_bucket_i != i) {
/* Find earliest bucket that we could move i to */
int j = nat_bucket_i;
while (j != i) {
if (!tbl->tokens[j]) {
/* put it here */
#if 0
fprintf(stderr, "Moved <%s> from bucket %d to %d (natural bucket %d)\n", tbl->tokens[i]->text, i, j, nat_bucket_i);
#endif
tbl->tokens[j] = tbl->tokens[i];
tbl->tokens[i] = NULL;
any_moved = 1;
break;
} else {
j++;
j &= tbl->mask;
}
}
if (tbl->tokens[i]) {
#if 0
fprintf(stderr, "NOT moved <%s> from bucket %d (natural bucket %d)\n", tbl->tokens[i]->text, i, nat_bucket_i);
#endif
}
}
}
}
if (!any_moved) break;
pass++;
}
}
}
/*}}}*/
int cull_dead_messages(struct database *db, int do_integrity_checks)/*{{{*/
{
/* Return true if any culled */
int *new_idx, i, j, n_old;
int any_culled = 0;
/* Check db is OK before we start on this. (Check afterwards is done in the
* writer.c code.) */
if (do_integrity_checks) {
check_database_integrity(db);
}
if (verbose) {
fprintf(stderr, "Culling dead messages\n");
}
n_old = db->n_msgs;
new_idx = new_array(int, n_old);
for (i=0, j=0; i<n_old; i++) {
switch (db->type[i]) {
case MTY_FILE:
case MTY_MBOX:
new_idx[i] = j++;
break;
case MTY_DEAD:
new_idx[i] = -1;
any_culled = 1;
break;
}
}
recode_toktable(db->to, new_idx);
recode_toktable(db->cc, new_idx);
recode_toktable(db->from, new_idx);
recode_toktable(db->subject, new_idx);
recode_toktable(db->body, new_idx);
recode_toktable(db->attachment_name, new_idx);
recode_toktable2(db->msg_ids, new_idx);
/* And crunch down the filename table */
for (i=0, j=0; i<n_old; i++) {
switch (db->type[i]) {
case MTY_DEAD:
break;
case MTY_FILE:
case MTY_MBOX:
if (i > j) {
db->msgs[j] = db->msgs[i];
db->type[j] = db->type[i];
}
j++;
break;
}
}
db->n_msgs = j;
free(new_idx);
/* .. and cull dead mboxen */
cull_dead_mboxen(db);
return any_culled;
}
/*}}}*/
syntax highlighted by Code2HTML, v. 0.9.1