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                         msg->id = beg + 1;
  92                         msg->id_len = end - beg - 1;
  93                 }
  94         }
  95         if (rply_hdr) {
  96                 int len = hdr_len(rply_hdr);
  97                 char *beg = memchr(rply_hdr, '<', len);
  98                 char *end = beg ? memchr(rply_hdr, '>', len) : NULL;
  99                 if (beg && end) {
 100                         msg->rply = beg + 1;
 101                         msg->rply_len = end - beg - 1;
 102                 }
 103         }
 104 }
 105
 106 void sort_inc(struct sort *sort)
 107 {
 108         struct mbox *mbox = sort->mbox;
 109         int beg = sort->n;
 110         int i;
 111         if (sort->n == mbox->n)
 112                 return;
 113         sort->n = mbox->n;
 114         for (i = beg; i < sort->n; i++) {
 115                 struct thread *thread = &sort->threads[i];
 116                 struct mail *mail = &mbox->mails[i];
 117                 thread->mail = mail;
 118                 if (sort->kind & SORT_THREAD) {
 119                         sort->id_sorted[i] = thread;
 120                         make_hdrs(thread);
 121                 } else {
 122                         sort->mails[i] = mail;
 123                         sort->sorted[i] = thread;
 124                 }
 125         }
 126         if (sort->kind & SORT_THREAD) {
 127                 qsort(sort->id_sorted, sort->n,
 128                         sizeof(*sort->id_sorted), thread_cmp);
 129                 create_tree(sort, beg);
 130                 make_sorted(sort);
 131         }
 132 }
 133
 134 struct sort *sort_alloc(struct mbox *mbox, int kind)
 135 {
 136         struct sort *sort = malloc(sizeof(*sort));
 137         memset(sort, 0, sizeof(*sort));
 138         sort->mbox = mbox;
 139         sort->kind = kind;
 140         sort_inc(sort);
 141         return sort;
 142 }
 143
 144 void sort_free(struct sort *sort)
 145 {
 146         free(sort);
 147 }
 148
 149 static int thread_depth(struct thread *msg)
 150 {
 151         int i = 0;
 152         while ((msg = msg->parent))
 153                 i++;
 154         return i;
 155 }
 156
 157 char *sort_draw(struct sort *sort, int id, char *s, int len)
 158 {
 159         struct thread *msg = sort->sorted[id];
 160         int depth = thread_depth(msg);
 161         char *d = s + len;
 162         int i;
 163         for (i = 0; i < depth && s < d; i++) {
 164                 *s++ = ' ';
 165                 *s++ = ' ';
 166         }
 167         return s;
 168 }