home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume22 / nn6.4 / part11 / sort.c < prev   
Encoding:
C/C++ Source or Header  |  1990-06-07  |  7.4 KB  |  301 lines
  1. /*
  2.  *    (c) Copyright 1990, Kim Fabricius Storm.  All rights reserved.
  3.  *
  4.  *    Article sorting.
  5.  */
  6.  
  7. #include "config.h"
  8. #include "articles.h"
  9.  
  10.  
  11.  
  12. export int subject_match_limit = 20;     /* "strncmp" limit for subjects */
  13. export int match_skip_prefix = 0; /* skip first N bytes in matches */
  14. export int match_parts_equal = 0; /* match digits as equal */
  15.  
  16. export int sort_mode = 1;        /* default sort mode */
  17.  
  18. /*
  19.  *    String matching macroes.
  20.  *
  21.  *     MATCH_DROP(t, a) and MATCH_DROP(t, b) must both be proven false
  22.  *    before MATCH_???(t, a, b) is used.
  23.  */
  24.  
  25. #define    MATCH_DROP(table, c) ( c & 0200 || table[c] == 0 )
  26. #define MATCH_EQ(table, a, b) ( a == b || table[a] == table[b] )
  27. #define MATCH_LS_EQ(table, a, b) ( a <= b || table[a] <= table[b] )
  28. #define MATCH_LS(table, a, b) ( a < b || table[a] < table[b] )
  29. #define    MATCH_CMP(table, a, b) (table[a] - table[b])
  30.  
  31. static char match_subject[128] = {
  32.  
  33. /*  NUL SOH STX ETX EOT ENQ ACK BEL BS  TAB NL  VT  FF  CR  SO  SI  */
  34.     00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
  35.  
  36. /*  DLE DC1 DC2 DC3 DC4 NAK SYN ETB CAN EM  SUB ESC FS  GS  RS  US  */
  37.     00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00,
  38.  
  39. /*  SP  !   "   #   $   %   &   '   (   )   *   +   ,   -   .   /   */
  40.     00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 99, 00, 00, 00, 00,
  41. /*                                              ^^                  */
  42.  
  43. /*  0   1   2   3   4   5   6   7   8   9   :   ;   <   =   >   ?   */
  44.      1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 00, 00, 00, 00, 00, 00,
  45.  
  46. /*  @   A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   */
  47.     00, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
  48.  
  49. /*  P   Q   R   S   T   U   V   W   X   Y   Z   [   \   ]   ^   _   */
  50.     26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 00, 00,
  51.  
  52. /*  `   a   b   c   d   e   f   g   h   i   j   k   l   m   n   o   */
  53.     00, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
  54.  
  55. /*  p   q   r   s   t   u   v   w   x   y   z   {   |   }   ~   DEL */
  56.     26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 00, 00
  57. };
  58.  
  59.  
  60. static order_subj_date(ah1, ah2)
  61. article_header **ah1, **ah2;
  62. {
  63.     register char *a = (**ah1).subject, *b = (**ah2).subject;
  64.     register char ca, cb;
  65.     register int p, len;
  66.  
  67.     if (match_skip_prefix) {
  68.     if ((**ah1).subj_length > match_skip_prefix) {
  69.         if ((**ah2).subj_length > match_skip_prefix) {
  70.         a += match_skip_prefix;
  71.         b += match_skip_prefix;
  72.         } else
  73.         return 1;
  74.     } else {
  75.         if ((**ah2).subj_length > match_skip_prefix) {
  76.         return -1;
  77.         }
  78.     }
  79.     }
  80.  
  81.     for (len = 0; ; len++, a++, b++) {
  82.     while ((ca = *a) && MATCH_DROP(match_subject, ca)) a++;
  83.     while ((cb = *b) && MATCH_DROP(match_subject, cb)) b++;
  84.  
  85.     if (ca == NUL) {
  86.         if (cb == NUL) break;
  87.         if (len >= subject_match_limit) break;
  88.         return -1;
  89.     }
  90.  
  91.     if (cb == NUL) {
  92.         if (len >= subject_match_limit) break;
  93.         return 1;
  94.     }
  95.  
  96.     if (p = MATCH_CMP(match_subject, ca, cb)) return p;
  97.     }
  98.  
  99.     if ((**ah1).t_stamp > (**ah2).t_stamp) return 1;
  100.     if ((**ah1).t_stamp < (**ah2).t_stamp) return -1;
  101.     return 0;
  102. }
  103.  
  104. /* data_subj_date can only be used after root_t_stamp is set */
  105.  
  106. static order_date_subj_date(ah1, ah2)
  107. article_header **ah1, **ah2;
  108. {
  109.     register time_stamp t1 = (**ah1).root_t_stamp;
  110.     register time_stamp t2 = (**ah2).root_t_stamp;
  111.  
  112.     if (t1 > t2) return 1;
  113.     if (t1 < t2) return -1;
  114.     return order_subj_date(ah1, ah2);    /* get original order */
  115. }
  116.  
  117.  
  118. static order_arrival(a, b)
  119. article_header **a, **b;
  120. {
  121.     register long i;
  122.  
  123.     if ((i = (int)((*a)->a_number - (*b)->a_number)) == 0)
  124.     i = (*a)->fpos - (*b)->fpos;
  125.  
  126.     return (i > 0) ? 1 : (i < 0) ? -1 : 0;
  127. }
  128.  
  129. static order_date(ah1, ah2)
  130. register article_header **ah1, **ah2;
  131. {
  132.     if ((**ah1).t_stamp > (**ah2).t_stamp) return 1;
  133.     if ((**ah1).t_stamp < (**ah2).t_stamp) return -1;
  134.     return 0;
  135. }
  136.  
  137. static order_from_date(ah1, ah2)
  138. register article_header **ah1, **ah2;
  139. {
  140.     register int i;
  141.  
  142.     if (i = strcmp((**ah1).sender, (**ah2).sender)) return i;
  143.     return order_date(ah1, ah2);
  144. }
  145.  
  146. static flag_type article_equal(ah1, ah2) /* ah1.hdr == ah2.hdr */
  147. article_header **ah1, **ah2;
  148. {
  149.     register char *a = (**ah1).subject, *b = (**ah2).subject;
  150.     register int len;
  151.  
  152.     if (match_skip_prefix) {
  153.     if ((**ah1).subj_length > match_skip_prefix) {
  154.         if ((**ah2).subj_length > match_skip_prefix) {
  155.         a += match_skip_prefix;
  156.         b += match_skip_prefix;
  157.         }
  158.     }
  159.     }
  160.  
  161.     for (len = 0;; len++, a++, b++) {
  162.     while (*a && MATCH_DROP(match_subject, *a)) a++;
  163.     while (*b && MATCH_DROP(match_subject, *b)) b++;
  164.  
  165.     if (*a == NUL) {
  166.         if (*b == NUL) break;
  167.         if (len >= subject_match_limit) return A_ALMOST_SAME;
  168.         return 0;
  169.     }
  170.  
  171.     if (*b == NUL) {
  172.         if (len >= subject_match_limit) return A_ALMOST_SAME;
  173.         return 0;
  174.     }
  175.  
  176.     if (!MATCH_EQ(match_subject, *a, *b)) {
  177.         if (len >= subject_match_limit)
  178.         return A_ALMOST_SAME;
  179.         if (match_parts_equal && isdigit(*a) && isdigit(*b))
  180.         return A_ALMOST_SAME;
  181.         return 0;
  182.     }
  183.     }
  184.  
  185.     return A_SAME;
  186. }
  187.  
  188. sort_articles(mode)
  189. int mode;
  190. {
  191.     register article_header **app;
  192.     register long n;
  193.     register flag_type same;
  194.     fct_type cmp;
  195.  
  196.     for (n = n_articles; --n >= 0;)
  197.     articles[n]->flag &= ~(A_SAME|A_ALMOST_SAME|A_NEXT_SAME);
  198.  
  199.     if (n_articles <= 1) return;
  200.  
  201.     if (mode == -1) mode = sort_mode;
  202.  
  203.     switch (mode) {
  204.      default:
  205.      case 0:            /* arrival (no sort) */
  206.     cmp = order_arrival;
  207.     break;
  208.      case 1:            /* date-subject-date */
  209.      case 2:            /* subject-date */
  210.     cmp = order_subj_date;
  211.     break;
  212.      case 3:            /* date only */
  213.     cmp = order_date;
  214.     break;
  215.      case 4:            /* sender-date */
  216.     cmp = order_from_date;
  217.     break;
  218.     }
  219.  
  220.     quicksort(articles, n_articles, article_header *, cmp);
  221.  
  222.     articles[0]->root_t_stamp = articles[0]->t_stamp;
  223.     for (n = n_articles - 1, app = articles + 1; --n >= 0; app++) {
  224.     if (same = article_equal(app, app - 1)) {
  225.         app[0]->root_t_stamp = app[-1]->root_t_stamp;
  226.         app[0]->flag |= same;
  227.         app[-1]->flag |= A_NEXT_SAME;
  228.     } else {
  229.         app[0]->root_t_stamp = app[0]->t_stamp;
  230.     }
  231.     }
  232.  
  233.     if (mode == 1)
  234.     quicksort(articles, n_articles, article_header *, order_date_subj_date);
  235. }
  236.  
  237.  
  238. /*
  239.  * Eliminate articles with the A_KILL flag set preserving the present ordering.
  240.  * This will only release the last entries in the articles array.
  241.  * Neither strings nor articles headers are released.
  242.  */
  243.  
  244. elim_articles(list, list_lgt)
  245. register article_number *list;
  246. int list_lgt;
  247. {
  248.     register article_header **srca, **desta;
  249.     register article_number n, count;
  250.     register flag_type same;
  251.     int changed, llen;
  252.  
  253.     count = 0;
  254.     changed = 0, llen = 0;
  255.     for (n = 0, srca = desta = articles; n < n_articles; n++, srca++) {
  256.     if ((*srca)->attr == A_KILL) {
  257.         if (list_lgt > 0) {
  258.         if (n < *list) {
  259.             if (llen) changed = 1;
  260.         } else
  261.         if (n == *list) {
  262.             if (llen) {
  263.             llen++;
  264.             list_lgt--;
  265.             *list++ = -1;
  266.             } else
  267.             ++(*list);
  268.             changed = 1;
  269.         }
  270.         }
  271.         continue;
  272.     }
  273.     if (list_lgt > 0 && n == *list) {
  274.         *list++ = count;
  275.         list_lgt--;
  276.         llen++;
  277.     }
  278.     count++;
  279.     *desta++ = *srca;
  280.     }
  281.     if (list_lgt > 0) {
  282.     if (!llen) *list = 0;
  283.     changed = 1;
  284.     }
  285.     n_articles = count;
  286.  
  287.     if (changed && n_articles > 0) {
  288.     srca = articles;
  289.     srca[0]->flag &= ~(A_SAME|A_ALMOST_SAME|A_NEXT_SAME);
  290.     for (n = n_articles - 1, srca++; --n >= 0; srca++) {
  291.         srca[0]->flag &= ~(A_SAME|A_ALMOST_SAME|A_NEXT_SAME);
  292.         if (same = article_equal(srca, srca - 1)) {
  293.         srca[0]->flag |= same;
  294.         srca[-1]->flag |= A_NEXT_SAME;
  295.         }
  296.     }
  297.     }
  298.  
  299.     return changed;
  300. }
  301.