sort.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include "mbox.h"
   5 #include "sort.h"
   6
   7 #define LEN(a)                  (sizeof(a) / sizeof((a)[0]))
   8
   9 struct msg {
  10         struct mail *mail;
  11         char *id;       /* message-id header value */
  12         int id_len;     /* message-id length */
  13         char *rply;     /* reply-to header value */
  14         int rply_len;   /* reply-to length */
  15         int date;       /* message receiving date */
  16         int depth;      /* depth of message in the thread */
  17         int oidx;       /* the original index of the message */
  18         struct msg *parent;
  19         struct msg *head;
  20         struct msg *tail;
  21         struct msg *next;
  22 };
  23
  24 static int id_cmp(char *i1, int l1, char *i2, int l2)
  25 {
  26         if (l1 != l2)
  27                 return l2 - l1;
  28         return strncmp(i1, i2, l1);
  29 }
  30
  31 static int msgcmp_id(void *v1, void *v2)
  32 {
  33         struct msg *t1 = *(struct msg **) v1;
  34         struct msg *t2 = *(struct msg **) v2;
  35         return id_cmp(t1->id, t1->id_len, t2->id, t2->id_len);
  36 }
  37
  38 static int msgcmp_date(void *v1, void *v2)
  39 {
  40         struct msg *t1 = *(struct msg **) v1;
  41         struct msg *t2 = *(struct msg **) v2;
  42         return t1->date == t2->date ? t1->oidx - t2->oidx : t1->date - t2->date;
  43 }
  44
  45 static char *months[] = {
  46         "Jan", "Feb", "Mar", "Apr", "May", "Jun",
  47         "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"
  48 };
  49
  50 static char *readtok(char *s, char *d)
  51 {
  52         while (*s == ' ' || *s == ':')
  53                 s++;
  54         while (!strchr(" \t\r\n:", *s))
  55                 *d++ = *s++;
  56         *d = '\0';
  57         return s;
  58 }
  59
  60 static int fromdate(char *s)
  61 {
  62         char tok[128];
  63         int year, mon, day, hour, min, sec;
  64         int i;
  65         /* parsing "From ali Tue Apr 16 20:18:40 2013" */
  66         s = readtok(s, tok);            /* From */
  67         s = readtok(s, tok);            /* username */
  68         s = readtok(s, tok);            /* day of week */
  69         s = readtok(s, tok);            /* month name */
  70         mon = 0;
  71         for (i = 0; i < LEN(months); i++)
  72                 if (!strcmp(months[i], tok))
  73                         mon = i;
  74         s = readtok(s, tok);            /* day of month */
  75         day = atoi(tok);
  76         s = readtok(s, tok);            /* hour */
  77         hour = atoi(tok);
  78         s = readtok(s, tok);            /* minute */
  79         min = atoi(tok);
  80         s = readtok(s, tok);            /* seconds */
  81         sec = atoi(tok);
  82         s = readtok(s, tok);            /* year */
  83         year = atoi(tok);
  84         return ((year - 1970) * 400 + mon * 31 + day) * 24 * 3600 +
  85                 hour * 3600 + min * 60 + sec;
  86 }
  87
  88 static struct msg *msg_byid(struct msg **msgs, int n, char *id, int len)
  89 {
  90         int l = 0;
  91         int h = n;
  92         while (l < h) {
  93                 int m = (l + h) / 2;
  94                 int d = id_cmp(id, len, msgs[m]->id, msgs[m]->id_len);
  95                 if (!d)
  96                         return msgs[m];
  97                 if (d < 0)
  98                         h = m;
  99                 else
 100                         l = m + 1;
 101         }
 102         return NULL;
 103 }
 104
 105 static void msgs_tree(struct msg **all, struct msg **sorted_id, int n)
 106 {
 107         int i;
 108         for (i = 0; i < n; i++) {
 109                 struct msg *msg = all[i];
 110                 struct msg *dad;
 111                 if (!msg->rply)
 112                         continue;
 113                 dad = msg_byid(sorted_id, n, msg->rply, msg->rply_len);
 114                 if (!dad)
 115                         continue;
 116                 msg->parent = dad;
 117                 msg->depth = dad->depth + 1;
 118                 if (!msg->parent->head)
 119                         msg->parent->head = msg;
 120                 else
 121                         msg->parent->tail->next = msg;
 122                 msg->parent->tail = msg;
 123         }
 124 }
 125
 126 static void hdr_init(struct msg *msg)
 127 {
 128         char *id_hdr = mail_hdr(msg->mail, "Message-ID:");
 129         char *rply_hdr = mail_hdr(msg->mail, "In-Reply-To:");
 130         if (id_hdr) {
 131                 int len = hdr_len(id_hdr);
 132                 char *beg = memchr(id_hdr, '<', len);
 133                 char *end = beg ? memchr(id_hdr, '>', len) : NULL;
 134                 if (beg && end) {
 135                         while (*beg == '<')
 136                                 beg++;
 137                         msg->id = beg;
 138                         msg->id_len = end - beg;
 139                 }
 140         }
 141         if (rply_hdr) {
 142                 int len = hdr_len(rply_hdr);
 143                 char *beg = memchr(rply_hdr, '<', len);
 144                 char *end = beg ? memchr(rply_hdr, '>', len) : NULL;
 145                 if (beg && end) {
 146                         while (*beg == '<')
 147                                 beg++;
 148                         msg->rply = beg;
 149                         msg->rply_len = end - beg;
 150                 }
 151         }
 152         msg->date = fromdate(msg->mail->head);
 153 }
 154
 155 static struct msg **put_msg(struct msg **sorted, struct msg *msg)
 156 {
 157         struct msg *cur = msg->head;
 158         *sorted++ = msg;
 159         while (cur) {
 160                 sorted = put_msg(sorted, cur);
 161                 cur = cur->next;
 162         }
 163         return sorted;
 164 }
 165
 166 static void msgs_sort(struct msg **sorted, struct msg **msgs, int n)
 167 {
 168         int i;
 169         for (i = 0; i < n; i++)
 170                 if (!msgs[i]->parent)
 171                         sorted = put_msg(sorted, msgs[i]);
 172 }
 173
 174 int sort_mails(struct mail **mails, int *levels, int n)
 175 {
 176         struct msg *msgs = malloc(n * sizeof(*msgs));
 177         struct msg **sorted_date = malloc(n * sizeof(*sorted_date));
 178         struct msg **sorted_id = malloc(n * sizeof(*sorted_id));
 179         struct msg **sorted = malloc(n * sizeof(*sorted));
 180         int i;
 181         if (!msgs || !sorted_date || !sorted_id) {
 182                 free(msgs);
 183                 free(sorted_date);
 184                 free(sorted_id);
 185                 free(sorted);
 186                 return 1;
 187         }
 188         for (i = 0; i < n; i++) {
 189                 struct msg *msg = &msgs[i];
 190                 msg->oidx = i;
 191                 msg->mail = mails[i];
 192                 sorted_id[i] = msg;
 193                 sorted_date[i] = msg;
 194                 hdr_init(msg);
 195         }
 196         qsort(sorted_date, n, sizeof(*sorted_date), (void *) msgcmp_date);
 197         qsort(sorted_id, n, sizeof(*sorted_id), (void *) msgcmp_id);
 198         msgs_tree(sorted_date, sorted_id, n);
 199         msgs_sort(sorted, sorted_date, n);
 200         for (i = 0; i < n; i++)
 201                 mails[i] = sorted[i]->mail;
 202         for (i = 0; i < n; i++)
 203                 levels[i] = sorted[i]->depth;
 204         free(msgs);
 205         free(sorted_date);
 206         free(sorted_id);
 207         free(sorted);
 208         return 0;
 209 }