sort.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include "mbox.h"
   4 #include "sort.h"
   5
   6 static int thread_cmp(const void *v1, const void *v2)
   7 {
   8         struct thread *t1 = *(struct thread **) v1;
   9         struct thread *t2 = *(struct thread **) v2;
  10         if (t1->id_len != t2->id_len)
  11                 return t2->id_len - t1->id_len;
  12         return strncmp(t1->id, t2->id, t1->id_len);
  13 }
  14
  15 static int id_cmp(char *i1, int l1, char *i2, int l2)
  16 {
  17         if (l1 != l2)
  18                 return l2 - l1;
  19         return strncmp(i1, i2, l1);
  20 }
  21
  22 static struct thread *find_msg(struct thread **msgs, int n, char *id, int len)
  23 {
  24         int l = 0;
  25         int h = n;
  26         while (l < h) {
  27                 int m = (l + h) / 2;
  28                 int d = id_cmp(id, len, msgs[m]->id, msgs[m]->id_len);
  29                 if (!d)
  30                         return msgs[m];
  31                 if (d < 0)
  32                         h = m;
  33                 else
  34                         l = m + 1;
  35         }
  36         return NULL;
  37 }
  38
  39 static void create_tree(struct sort *sort, int beg)
  40 {
  41         int i;
  42         for (i = beg; i < sort->n; i++) {
  43                 struct thread *msg = &sort->threads[i];
  44                 struct thread *dad;
  45                 if (!msg->rply)
  46                         continue;
  47                 dad = find_msg(sort->id_sorted, sort->n,
  48                                         msg->rply, msg->rply_len);
  49                 if (!dad || dad >= msg)
  50                         continue;
  51                 msg->parent = dad;
  52                 if (!msg->parent->head)
  53                         msg->parent->head = msg;
  54                 else
  55                         msg->parent->tail->next = msg;
  56                 msg->parent->tail = msg;
  57         }
  58 }
  59
  60 static struct thread **put_thread(struct thread **sorted, struct thread *msg)
  61 {
  62         struct thread *cur = msg->head;
  63         *sorted++ = msg;
  64         while (cur) {
  65                 sorted = put_thread(sorted, cur);
  66                 cur = cur->next;
  67         }
  68         return sorted;
  69 }
  70
  71 static void make_sorted(struct sort *sort)
  72 {
  73         int i;
  74         struct thread **sorted = sort->sorted;
  75         for (i = 0; i < sort->n; i++)
  76                 if (!sort->threads[i].parent)
  77                         sorted = put_thread(sorted, &sort->threads[i]);
  78         for (i = 0; i < sort->n; i++)
  79                 sort->mails[i] = sort->sorted[i]->mail;
  80 }
  81
  82 static void make_hdrs(struct thread *msg)
  83 {
  84         char *id_hdr = mail_hdr(msg->mail, "Message-ID:");
  85         char *rply_hdr = mail_hdr(msg->mail, "In-Reply-To:");
  86         if (id_hdr) {
  87                 int len = hdr_len(id_hdr);
  88                 char *beg = memchr(id_hdr, '<', len);
  89                 char *end = beg ? memchr(id_hdr, '>', len) : NULL;
  90                 if (beg && end) {
  91                         while (*beg == '<')
  92                                 beg++;
  93                         msg->id = beg;
  94                         msg->id_len = end - beg;
  95                 }
  96         }
  97         if (rply_hdr) {
  98                 int len = hdr_len(rply_hdr);
  99                 char *beg = memchr(rply_hdr, '<', len);
 100                 char *end = beg ? memchr(rply_hdr, '>', len) : NULL;
 101                 if (beg && end) {
 102                         while (*beg == '<')
 103                                 beg++;
 104                         msg->rply = beg;
 105                         msg->rply_len = end - beg;
 106                 }
 107         }
 108 }
 109
 110 void sort_inc(struct sort *sort)
 111 {
 112         struct mbox *mbox = sort->mbox;
 113         int beg = sort->n;
 114         int i;
 115         if (sort->n == mbox->n)
 116                 return;
 117         sort->n = mbox->n;
 118         for (i = beg; i < sort->n; i++) {
 119                 struct thread *thread = &sort->threads[i];
 120                 struct mail *mail = &mbox->mails[i];
 121                 thread->mail = mail;
 122                 if (sort->kind & SORT_THREAD) {
 123                         sort->id_sorted[i] = thread;
 124                         make_hdrs(thread);
 125                 } else {
 126                         sort->mails[i] = mail;
 127                         sort->sorted[i] = thread;
 128                 }
 129         }
 130         if (sort->kind & SORT_THREAD) {
 131                 qsort(sort->id_sorted, sort->n,
 132                         sizeof(*sort->id_sorted), thread_cmp);
 133                 create_tree(sort, beg);
 134                 make_sorted(sort);
 135         }
 136 }
 137
 138 struct sort *sort_alloc(struct mbox *mbox, int kind)
 139 {
 140         struct sort *sort = malloc(sizeof(*sort));
 141         memset(sort, 0, sizeof(*sort));
 142         sort->mbox = mbox;
 143         sort->kind = kind;
 144         sort_inc(sort);
 145         return sort;
 146 }
 147
 148 void sort_free(struct sort *sort)
 149 {
 150         free(sort);
 151 }
 152
 153 int sort_level(struct sort *sort, int id)
 154 {
 155         struct thread *msg = sort->sorted[id];
 156         int i = 0;
 157         while ((msg = msg->parent))
 158                 i++;
 159         return i;
 160 }