/* elmo - ELectronic Mail Operator Copyright (C) 2002, 2003, 2004 rzyjontko This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; version 2. 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. ---------------------------------------------------------------------- operations on mail array */ #define _GNU_SOURCE 1 /**************************************************************************** * IMPLEMENTATION HEADERS ****************************************************************************/ #include #include #include "xmalloc.h" #include "mail.h" #include "hash.h" #include "multree.h" #include "misc.h" #include "memchunk.h" #include "error.h" #include "gettext.h" #include "clock.h" #include "debug.h" /**************************************************************************** * IMPLEMENTATION PRIVATE DEFINITIONS / ENUMERATIONS / SIMPLE TYPEDEFS ****************************************************************************/ #define INITIAL_MAIL_COUNT 100 #define CHUNK_SIZE 1000 #define INFO_MAGIC 0x1D10A1DA #define INFO_VERSION 11 /**************************************************************************** * IMPLEMENTATION PRIVATE CLASS PROTOTYPES / EXTERNAL CLASS REFERENCES ****************************************************************************/ /**************************************************************************** * IMPLEMENTATION PRIVATE STRUCTURES / UTILITY CLASSES ****************************************************************************/ struct mail_array_info { unsigned magic; /* magic number = INFO_MAGIC */ int version; /* version = INFO_VERSION */ int size; /* messages count */ }; /**************************************************************************** * IMPLEMENTATION REQUIRED EXTERNAL REFERENCES (AVOID) ****************************************************************************/ /**************************************************************************** * IMPLEMENTATION PRIVATE DATA ****************************************************************************/ /**************************************************************************** * INTERFACE DATA ****************************************************************************/ /**************************************************************************** * IMPLEMENTATION PRIVATE FUNCTION PROTOTYPES ****************************************************************************/ /**************************************************************************** * IMPLEMENTATION PRIVATE FUNCTIONS ****************************************************************************/ static void find_parent (mail_array_t *marray, htable_t *table, int index) { int i; mail_t *parent = NULL; mail_t *mail = mail_array_get (marray, index); entry_t *entry = NULL; if (mail == NULL) return; if (mail->in_reply_to){ for (i = mail->in_reply_to->count; i; i--){ entry = htable_lookup (table, mail->in_reply_to->array[i - 1]); if (entry) break; } } if (entry){ parent = mail_array_get (marray, (int) entry->content); mail->parent = (int) entry->content; parent->child_count++; } else { mail->parent = -1; } } static void put_msgid_into_hash (mail_array_t *marray, htable_t *table, int index) { mail_t *mail = mail_array_get (marray, index); entry_t *entry = NULL; if (mail == NULL) return; if (! mail->msg_id) return; entry = htable_insert (table, mail->msg_id, (void *) index); if (entry->content != (void *) index) mail->flags |= FLAG_DUPLICATE; } static int is_not_reply (mail_t *mail) { return mail->parent == -1; } static int is_old (mail_t *mail) { return (mail->flags & FLAG_OLD) && ! (mail->flags & FLAG_READ); } static int is_read (mail_t *mail) { return mail->flags & FLAG_READ; } static int is_not_read (mail_t *mail) { return ! (mail->flags & FLAG_READ); } static int count_true (mail_array_t *marray, int (*is_true)(mail_t *)) { int i; int result = 0; mail_t *mail; for (i = 0; i < marray->count; i++){ mail = mail_array_get (marray, i); if (is_true (mail)) result++; } return result; } static int first_true (mail_array_t *marray, int (*is_true)(mail_t *), int start) { int i; mail_t *mail; for (i = start; i < marray->count; i++){ mail = mail_array_get (marray, i); if (is_true (mail)) return i; } return -1; } static int first_true_backward (mail_array_t *marray, int (*is_true)(mail_t *), int start) { int i; mail_t *mail; for (i = start; i >= 0; i--){ mail = mail_array_get (marray, i); if (is_true (mail)) return i; } return -1; } /**************************************************************************** * MAIL ARRAY DUMPING FUNCTIONS ****************************************************************************/ static void dump_address (memchunk_t *chunk, address_t *addr) { if (addr == NULL) memchunk_intdump (chunk, -1); else memchunk_intdump (chunk, addr->index); } static void dump_raddress (memchunk_t *chunk, raddress_t *raddr) { int i; if (raddr == NULL){ memchunk_intdump (chunk, 0); return; } memchunk_intdump (chunk, raddr->count); for (i = 0; i < raddr->count; i++){ dump_address (chunk, raddr->array[i]); } } static void dump_mail_but_place (memchunk_t *chunk, mail_t *mail) { dump_address (chunk, mail->from); dump_address (chunk, mail->reply_to); memchunk_strdump (chunk, mail->subject); memchunk_strdump (chunk, mail->date_str); dump_raddress (chunk, mail->to); dump_raddress (chunk, mail->cc); dump_raddress (chunk, mail->bcc); dump_address (chunk, mail->recv_for); memchunk_strdump (chunk, mail->msg_id); rstring_dump (chunk, mail->in_reply_to); memchunk_intdump (chunk, mail->flags); memchunk_intdump (chunk, mail->date); memchunk_strdump (chunk, mail->mua); mime_dump (chunk, mail->mime->mime); rstring_dump (chunk, mail->headers); memchunk_strdump (chunk, mail->smtp); } static int index_address (raddress_t *table, address_t *addr, int index) { if (addr == NULL) return index; if (addr->index == -1){ raddress_add (table, addr); addr->index = index++; } return index; } static int index_raddress (raddress_t *table, raddress_t *raddr, int index) { int i; if (raddr == NULL) return index; for (i = 0; i < raddr->count; i++) index = index_address (table, raddr->array[i], index); return index; } static int index_mail (raddress_t *table, mail_t *mail, int index) { index = index_address (table, mail->from, index); index = index_address (table, mail->reply_to, index); index = index_raddress (table, mail->to, index); index = index_raddress (table, mail->cc, index); index = index_raddress (table, mail->bcc, index); index = index_address (table, mail->recv_for, index); return index; } static void dump_address_table (memchunk_t *chunk, mail_array_t *marray) { int i; int index = 0; raddress_t *table = raddress_create (); address_reset_indexes (); for (i = 0; i < marray->count; i++) index = index_mail (table, marray->array + i, index); raddress_dump (table, chunk); raddress_destroy (table); } /**************************************************************************** * MAIL ARRAY READING FUNCTIONS ****************************************************************************/ static address_t * address_from_table (memchunk_t *chunk, raddress_t *table) { int index = memchunk_intget (chunk); if (table == NULL || index == -1) return NULL; if (index >= table->count){ debug_msg (DEBUG_ERROR, "index %d > than table->count %d", index, table->count); return NULL; } return table->array[index]; } static raddress_t * raddress_from_table (memchunk_t *chunk, raddress_t *table) { int i; int cnt = memchunk_intget (chunk); raddress_t *result; if (cnt <= 0) return NULL; result = raddress_create_size (cnt + 1); for (i = 0; i < cnt; i++){ raddress_add (result, address_from_table (chunk, table)); } return result; } static void read_mail_but_place (memchunk_t *chunk, mail_t *mail, raddress_t *table) { mail->from = address_from_table (chunk, table); mail->reply_to = address_from_table (chunk, table); mail->subject = memchunk_strget (chunk); mail->date_str = memchunk_strget (chunk); mail->to = raddress_from_table (chunk, table); mail->cc = raddress_from_table (chunk, table); mail->bcc = raddress_from_table (chunk, table); mail->recv_for = address_from_table (chunk, table); mail->msg_id = memchunk_strget (chunk); mail->in_reply_to = rstring_read (chunk); mail->flags = memchunk_intget (chunk); mail->date = memchunk_intget (chunk); mail->mua = memchunk_strget (chunk); mail->mime = mime_info_read (chunk); mail->headers = rstring_read (chunk); mail->smtp = memchunk_strget (chunk); } /**************************************************************************** * INTERFACE FUNCTIONS ****************************************************************************/ void mail_clear (mail_t *mail) { mail->subject = NULL; mail->from = NULL; mail->to = NULL; mail->cc = NULL; mail->bcc = NULL; mail->recv_for = NULL; mail->reply_to = NULL; mail->msg_id = NULL; mail->in_reply_to = NULL; mail->tree = NULL; mail->date_str = NULL; mail->tree_len = 0; mail->flags = 0; mail->parent = -1; mail->child_count = 0; mail->is_last_child = 0; mail->place.generic = NULL; mail->date = 0; mail->mua = NULL; mail->type = BOX_INVALID; mail->mime = NULL; mail->headers = NULL; mail->smtp = NULL; } void mail_destroy (mail_t *mail, box_type_t type) { if (mail->subject) xfree (mail->subject); if (mail->msg_id) xfree (mail->msg_id); if (mail->in_reply_to){ rstring_delete (mail->in_reply_to); } if (mail->date_str) xfree (mail->date_str); if (mail->tree) xfree (mail->tree); if (type == BOX_MAILDIR || type == BOX_SENDER){ if (mail->place.file_name) xfree (mail->place.file_name); mail->place.file_name = NULL; } if (mail->mua) xfree (mail->mua); if (mail->mime) mime_info_destroy (mail->mime); if (mail->to) raddress_destroy (mail->to); if (mail->cc) raddress_destroy (mail->cc); if (mail->bcc) raddress_destroy (mail->bcc); if (mail->headers) rstring_delete (mail->headers); if (mail->smtp) xfree (mail->smtp); } mail_array_t * mail_array_create_size (int size, box_type_t type, const char *path) { mail_array_t *result = xmalloc (sizeof (mail_array_t)); result->count = 0; result->not_replies_count = -1; result->old_count = -1; result->read_count = -1; result->have_parents = 0; result->order = ORDER_NO; result->size = size; result->type = type; result->path = xstrdup (path); result->array = xmalloc (size * sizeof (mail_t)); return result; } mail_array_t * mail_array_create (box_type_t type, const char *path) { return mail_array_create_size (INITIAL_MAIL_COUNT, type, path); } void mail_array_destroy (mail_array_t *marray) { int i; for (i = 0; i < marray->count; i++){ mail_destroy (marray->array + i, marray->type); } if (marray->path) xfree (marray->path); if (marray->array) xfree (marray->array); xfree (marray); } void mail_array_substitute (mail_array_t *marray, mail_array_t *with) { if (marray->path) xfree (marray->path); if (marray->array) xfree (marray->array); marray->path = with->path; marray->array = with->array; marray->size = with->size; marray->count = with->count; marray->type = with->type; marray->not_replies_count = -1; marray->old_count = -1; marray->read_count = -1; marray->have_parents = 0; marray->order = ORDER_NO; xfree (with); } void mail_array_insert (mail_array_t *marray, mail_t *mail) { if (marray->count == marray->size){ marray->size = (marray->size + 1) * 2; marray->array = xrealloc (marray->array, marray->size * sizeof (mail_t)); } memcpy (marray->array + marray->count, mail, sizeof (mail_t)); marray->not_replies_count = -1; marray->old_count = -1; marray->read_count = -1; marray->have_parents = 0; marray->order = ORDER_NO; marray->count++; } mail_t * mail_array_get (mail_array_t *marray, int index) { if (marray == NULL) return NULL; if (index < 0 || index >= marray->count) return NULL; return marray->array + index; } void mail_array_find_parents (mail_array_t *marray) { int i; htable_t *id_table; id_table = htable_create (misc_logarithm (marray->count)); for (i = 0; i < marray->count; i++){ put_msgid_into_hash (marray, id_table, i); } for (i = 0; i < marray->count; i++){ find_parent (marray, id_table, i); } htable_destroy (id_table, NULL); marray->have_parents = 1; } int mail_array_not_replies (mail_array_t *marray) { if (marray->not_replies_count != -1) return marray->not_replies_count; return count_true (marray, is_not_reply); } int mail_array_old (mail_array_t *marray) { if (marray->old_count != -1) return marray->old_count; return count_true (marray, is_old); } int mail_array_read (mail_array_t *marray) { if (marray->read_count != -1) return marray->read_count; return count_true (marray, is_read); } int mail_array_first_unread_index (mail_array_t *marray) { return first_true (marray, is_not_read, 0); } int mail_array_dump (mail_array_t *marray, FILE *fp, void (*dump_place)(memchunk_t *, mail_t *)) { struct mail_array_info info; memchunk_t *chunk = memchunk_create_size (CHUNK_SIZE); int i; info.magic = INFO_MAGIC; info.version = INFO_VERSION; info.size = marray->count; if (fwrite (&info, sizeof (info), 1, fp) != 1){ error_ (errno, "fwrite"); memchunk_destroy (chunk); return 1; } memchunk_reset (chunk); dump_address_table (chunk, marray); if (memchunk_dump (chunk, fp)){ memchunk_destroy (chunk); return 1; } for (i = 0; i < marray->count; i++){ memchunk_reset (chunk); dump_mail_but_place (chunk, marray->array + i); dump_place (chunk, marray->array + i); if (memchunk_dump (chunk, fp)){ memchunk_destroy (chunk); return 1; } } memchunk_destroy (chunk); return 0; } mail_array_t * mail_array_read_from_file (FILE *fp, box_type_t type, const char *path, void (*read_place)(memchunk_t *, mail_t *)) { struct mail_array_info info; int i; mail_array_t *result; memchunk_t *chunk; int p; raddress_t *table; if (fread (&info, sizeof (info), 1, fp) != 1){ error_ (errno, "fread"); fclose (fp); return NULL; } if (info.magic != INFO_MAGIC){ error_ (0, _("cache file has invalid format")); fclose (fp); return NULL; } if (info.version != INFO_VERSION){ error_ (0, _("cache file format changed since last version")); fclose (fp); return NULL; } chunk = memchunk_create_size (CHUNK_SIZE); result = mail_array_create_size (info.size, type, path); if (memchunk_read (chunk, fp)){ memchunk_destroy (chunk); return NULL; } table = raddress_read (chunk); p = progress_setup (info.size, _("reading box (messages)")); for (i = 0; i < info.size; i++){ memchunk_reset (chunk); if (memchunk_read (chunk, fp)){ memchunk_destroy (chunk); mail_array_destroy (result); return NULL; } memchunk_rewind (chunk); mail_clear (result->array + i); read_mail_but_place (chunk, result->array + i, table); read_place (chunk, result->array + i); progress_advance (p, 1); } result->count = info.size; if (table) raddress_destroy (table); progress_close (p); memchunk_destroy (chunk); return result; } /**************************************************************************** * SORTING PRIVATE DATA ****************************************************************************/ /** * threading requires having another array */ static mail_array_t *thread_array = NULL; static mail_array_t *sorted_array = NULL; /** * this is used in threading */ static multree_t *root = NULL; static multree_t **nodes_array = NULL; /**************************************************************************** * SORTING FUNCTIONS (IMPLEMENTATION PRIVATE) ****************************************************************************/ static int date_cmp (const void *a, const void *b) { mail_t *aa = (mail_t *) a; mail_t *bb = (mail_t *) b; return (aa->date > bb->date) - (aa->date < bb->date); } static int date_cmp_rev (const void *a, const void *b) { return - date_cmp (a, b); } static int from_cmp (const void *a, const void *b) { mail_t *aa = (mail_t *) a; mail_t *bb = (mail_t *) b; if (aa->from == NULL || aa->from->name == NULL) return 1; if (bb->from == NULL || bb->from->name == NULL) return -1; return strcoll (aa->from->name, bb->from->name); } static int from_cmp_rev (const void *a, const void *b) { return - from_cmp (a, b); } static int subject_cmp (const void *a, const void *b) { mail_t *aa = (mail_t *) a; mail_t *bb = (mail_t *) b; if (aa->subject == NULL) return 1; if (bb->subject == NULL) return -1; return strcoll (aa->subject, bb->subject); } static int subject_cmp_rev (const void *a, const void *b) { return - subject_cmp (a, b); } static int smtp_cmp (const void *a, const void *b) { mail_t *aa = (mail_t *) a; mail_t *bb = (mail_t *) b; if (aa->smtp == NULL) return 1; if (bb->smtp == NULL) return -1; return strcmp (aa->smtp, bb->smtp); } static void prepare_nodes_array (mail_array_t *marray) { int i; mail_t *mail; for (i = 0; i < marray->count; i++){ mail = mail_array_get (marray, i); nodes_array[i] = multree_create (mail->child_count); nodes_array[i]->data = (void *) i; } } static void insert_mail (multree_t *node) { mail_t *mail = mail_array_get (sorted_array, (int) node->data); multree_t *parent_node; if (node == root) return; if (mail->parent != -1){ parent_node = nodes_array[mail->parent]; if (parent_node->children[parent_node->children_filled - 1] == node) mail->is_last_child = 1; else mail->is_last_child = 0; } mail_array_insert (thread_array, mail); /** * it's a nasty hack: we don't need any information in an old array * (where mail is still stored) so we can put in mail->date it's index * in a new array */ mail->date = thread_array->count - 1; } /** * this function uses the nasty hack in insert_mail, it finds parents * from the information stored in mail->date * * I know, it's terrible, but see how efficiently it works :) */ static void refind_parents (void) { int i; mail_t *new_mail; mail_t *old_mail; mail_t *old_parent; for (i = 0; i < sorted_array->count; i++){ old_mail = mail_array_get (sorted_array, i); old_parent = mail_array_get (sorted_array, old_mail->parent); new_mail = mail_array_get (thread_array, old_mail->date); if (new_mail == NULL) continue; if (old_parent) new_mail->parent = old_parent->date; else new_mail->parent = -1; } } /**************************************************************************** * SORTING FUNCTIONS (INTERFACE) ****************************************************************************/ void mail_array_sort_external (mail_array_t *marray, int (*cmp)(const void *, const void *)) { qsort (marray->array, marray->count, sizeof (mail_t), cmp); marray->have_parents = 0; marray->order = ORDER_EXTERNAL; } void mail_array_sort_date (mail_array_t *marray) { marray->have_parents = 0; if (marray->order != ORDER_DATE){ qsort (marray->array, marray->count, sizeof (mail_t), date_cmp); marray->order = ORDER_DATE; } else { qsort (marray->array, marray->count, sizeof (mail_t), date_cmp_rev); marray->order = ORDER_DATE_REV; } } void mail_array_sort_from (mail_array_t *marray) { marray->have_parents = 0; if (marray->order != ORDER_FROM){ qsort (marray->array, marray->count, sizeof (mail_t), from_cmp); marray->order = ORDER_FROM; } else { qsort (marray->array, marray->count, sizeof (mail_t), from_cmp_rev); marray->order = ORDER_FROM_REV; } } void mail_array_sort_subject (mail_array_t *marray) { marray->have_parents = 0; if (marray->order != ORDER_SUBJECT){ qsort (marray->array, marray->count, sizeof (mail_t), subject_cmp); marray->order = ORDER_SUBJECT; } else { qsort (marray->array, marray->count, sizeof (mail_t), subject_cmp_rev); marray->order = ORDER_SUBJECT_REV; } } void mail_array_sort_smtp (mail_array_t *marray) { marray->have_parents = 0; if (marray->order == ORDER_SMTP) return; qsort (marray->array, marray->count, sizeof (mail_t), smtp_cmp); marray->order = ORDER_SMTP; } void mail_array_sort_threads (mail_array_t *marray) { int i; int not_replies = mail_array_not_replies (marray); mail_t *mail; multree_t *parent; if (marray->order == ORDER_THREAD) return; /** * step 0: find parents (if necessary) */ if (! marray->have_parents) mail_array_find_parents (marray); /** * step 1: prepare new mail array and other important data structures */ thread_array = mail_array_create_size (marray->size, marray->type, NULL); sorted_array = marray; root = multree_create (not_replies); root->data = (void *) -1; nodes_array = xcalloc (marray->count, sizeof (multree_t *)); prepare_nodes_array (marray); /** * step 2: create the tree */ for (i = 0; i < marray->count; i++){ mail = mail_array_get (marray, i); if (mail->parent == -1) parent = root; else parent = nodes_array[mail->parent]; multree_add_child (parent, nodes_array[i]); } /** * step 3: sorting */ multree_preorder (root, insert_mail); multree_postorder (root, multree_node_destroy); /** * step 4: switch to the new array */ refind_parents (); if (marray->array) xfree (marray->array); marray->array = thread_array->array; marray->order = ORDER_THREAD; xfree (thread_array); /** * step 5: free resources */ if (nodes_array) xfree (nodes_array); root = NULL; nodes_array = NULL; thread_array = NULL; sorted_array = NULL; } /**************************************************************************** * SEARCHING PRIVATE DATA ****************************************************************************/ static void *search_ptr = NULL; static const void *search_subject = NULL; static const void *search_from = NULL; /**************************************************************************** * SEARCHING FUNCTIONS (IMPLEMENTATION PRIVATE) ****************************************************************************/ static int search_for_place (mail_t *mail) { return mail->place.generic == search_ptr; } static int search_for_subject (mail_t *mail) { if (mail->subject == NULL) return 0; if (strstr (mail->subject, search_subject)) return 1; return 0; } static int search_for_from (mail_t *mail) { if (mail->from == NULL) return 0; if (strstr (mail->from->full, search_from)) return 1; return 0; } static int search_unread (mail_t *mail) { if (mail->flags & FLAG_READ) return 0; return 1; } /**************************************************************************** * SEARCHING FUNCTIONS (INTERFACE) ****************************************************************************/ int mail_array_find_place (mail_array_t *marray, void *ptr) { int result; search_ptr = ptr; result = first_true (marray, search_for_place, 0); search_ptr = NULL; return result; } int mail_array_find (mail_array_t *marray, int (*fun)(mail_t *), int start) { return first_true (marray, fun, start); } int mail_array_find_back (mail_array_t *marray, int (*fun)(mail_t *), int start) { return first_true_backward (marray, fun, start); } int mail_array_find_subject (mail_array_t *marray, const char *subject, int start) { int result; search_subject = subject; result = first_true (marray, search_for_subject, start); search_subject = NULL; return result; } int mail_array_find_from (mail_array_t *marray, const char *from, int start) { int result; search_from = from; result = first_true (marray, search_for_from, start); search_from = NULL; return result; } int mail_array_find_unread (mail_array_t *marray, int start) { int result; result = first_true (marray, search_unread, start); if (result != -1) return result; return first_true (marray, search_unread, 0); } int mail_array_find_unread_back (mail_array_t *marray, int start) { int result; result = first_true_backward (marray, search_unread, start); if (result != -1) return result; return first_true_backward (marray, search_unread, marray->count - 1); } /**************************************************************************** * INTERFACE CLASS BODIES ****************************************************************************/ /**************************************************************************** * * END MODULE mail.c * ****************************************************************************/