home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume23 / trn / part05 / mt-process.c < prev   
Encoding:
C/C++ Source or Header  |  1991-08-22  |  33.5 KB  |  1,350 lines
  1. /* $Header: mt-process.c,v 4.3.3.3 91/01/18 19:13:20 davison Trn $
  2. **
  3. ** $Log:    mt-process.c,v $
  4. ** Revision 4.3.3.3  91/01/18  19:13:20  davison
  5. ** Removed the code that tried to exclude certain message ids.  Added -s option
  6. ** 
  7. ** Revision 4.3.3.2  90/08/20  16:40:31  davison
  8. ** Added check of caught_interrupt flag into main loops.
  9. ** 
  10. ** Revision 4.3.3.1  90/07/28  18:04:45  davison
  11. ** Initial Trn Release
  12. ** 
  13. */
  14.  
  15. #include "EXTERN.h"
  16. #include "common.h"
  17. #include "mthreads.h"
  18. #ifdef SERVER
  19. #include "server.h"
  20. #endif
  21.  
  22. #include <time.h>
  23. #ifndef TZSET
  24. # include <sys/timeb.h>
  25. #endif
  26.  
  27. char buff[1024];
  28.  
  29. char references[1024];
  30.  
  31. char subject_str[80];
  32. bool found_Re;
  33.  
  34. char author_str[20];
  35.  
  36. extern int log_verbosity, slow_down;
  37.  
  38. DOMAIN *next_domain;
  39.  
  40. void insert_article(), expire(), trim_roots(), order_roots(), trim_authors();
  41. void make_root(), use_root(), merge_roots(), set_root(), unlink_root();
  42. void link_child(), unlink_child();
  43. void free_article(), free_domain(), free_subject(), free_root(), free_author();
  44. void get_subject_str(), get_author_str();
  45. ARTICLE *get_article();
  46. SUBJECT *new_subject();
  47. AUTHOR *new_author();
  48.  
  49. #ifdef TZSET
  50. extern time_t tnow;
  51. #else
  52. extern struct timeb ftnow;
  53. #endif
  54.  
  55. #ifndef SERVER
  56. static FILE *fp_article;
  57. #endif
  58.  
  59. /* Given the upper/lower bounds of the articles in the current group, add all
  60. ** the ones that we don't know about and remove all the ones that have expired.
  61. ** The current directory must be the newgroup's spool directory.
  62. */
  63. void
  64. process_articles( first_article, last_article )
  65. ART_NUM first_article, last_article;
  66. {
  67.     register char *cp, *str;
  68.     register ARTICLE *article;
  69.     register ART_NUM i;
  70.     time_t date;
  71.     int len;
  72. #ifdef SERVER
  73.     bool orig_extra = extra_expire;
  74. #endif
  75.     extern int errno;
  76.     extern int sys_nerr;
  77.     extern char *sys_errlist[];
  78.  
  79.     if( first_article > (i = total.last+1) ) {
  80.     i = first_article;
  81.     }
  82.     added_count = last_article - i + 1;
  83.     expired_count = 0;
  84.  
  85.     for( ; i <= last_article; i++ ) {
  86.     if( caught_interrupt ) {
  87.         return;
  88.     }
  89. #ifdef SERVER
  90.     if( slow_down ) {
  91.         sleep( slow_down );
  92.     }
  93.     sprintf( buff, "HEAD %ld", (long)i );
  94.     put_server( buff );
  95.     if( get_server( buff, sizeof buff ) < 0 || *buff == CHAR_FATAL ) {
  96.         last_article = i - 1;
  97.         extra_expire = FALSE;
  98.         break;
  99.     }
  100.     if( *buff != CHAR_OK ) {
  101.         added_count--;
  102.         continue;
  103.     }
  104. #else
  105.     /* Open article in current directory. */
  106.     sprintf( buff, "%ld", (long)i );
  107.     /* Set errno for purely paranoid reasons */
  108.     errno = 0;
  109.     if( (fp_article = fopen( buff, "r" )) == Nullfp ) {
  110.         /* Missing files are ok -- they've just been expired or canceled */
  111.         if( errno != 0 && errno != ENOENT ) {
  112.         if( errno < 0 || errno > sys_nerr ) {
  113.             log_error( "Can't open `%s': Error %d.\n", buff, errno );
  114.         } else {
  115.             log_error( "Can't open `%s': %s.\n", buff,
  116.               sys_errlist[errno] );
  117.         }
  118.         }
  119.         added_count--;
  120.         continue;
  121.     }
  122. #endif
  123.  
  124.     article = Nullart;
  125.     *references = '\0';
  126.     *author_str = '\0';
  127.     *subject_str = '\0';
  128.     found_Re = 0;
  129.     date = 0;
  130.  
  131. #ifdef SERVER
  132.     while( get_server( cp = buff, sizeof buff ) == 0 ) {
  133.       process_line:
  134.         if( *cp == '.' ) {
  135.         break;
  136.         }
  137. #else
  138.     while( (cp = fgets( buff, sizeof buff, fp_article )) != Nullch ) {
  139.       process_line:
  140.         if( *cp == '\n' ) {        /* check for end of header */
  141.         break;            /* break out when found */
  142.         }
  143. #endif
  144.         if( (unsigned char)*cp <= ' ' ) {     /* skip continuation lines */
  145.         continue;        /* (except references -- see below) */
  146.         }
  147.         if( (str = index( cp, ':' )) == Nullch ) {
  148.         break;            /* end of header if no colon found */
  149.         }
  150.         if( (len = str - cp) > 10 ) {
  151.         continue;        /* skip keywords > 10 chars */
  152.         }
  153. #ifndef SERVER
  154.         cp[strlen(cp)-1] = '\0';    /* remove newline */
  155. #endif
  156.         while( cp < str ) {        /* lower-case the keyword */
  157.         if( (unsigned char)*cp <= ' ' ) { /* stop at any whitespace */
  158.             break;
  159.         }
  160.         if( isupper(*cp) ) {
  161.             *cp = tolower(*cp);
  162.         }
  163.         cp++;
  164.         }
  165.         *cp = '\0';
  166.         cp = buff;
  167.         if( len == 4 && strEQ( cp, "date" ) ) {
  168. #ifdef TZSET
  169.             date = getdate( str + 1, tnow, timezone );
  170. #else
  171.         date = getdate( str + 1, ftnow.time, (long) ftnow.timezone );
  172. #endif
  173.         } else
  174.         if( len == 4 && strEQ( cp, "from" ) ) {
  175.         get_author_str( str + 1 );
  176.         } else
  177.         if( len == 7 && strEQ( cp, "subject" ) ) {
  178.         get_subject_str( str + 1 );
  179.         } else
  180.         if( len == 10 && strEQ( cp, "message-id" ) ) {
  181.         if( !article ) {
  182.             article = get_article( str + 1 );
  183.         } else {
  184.             if( log_verbosity ) {
  185.             log_error( "Found multiple Message-IDs! [%ld].\n",
  186.                 (long)i );
  187.             }
  188.         }
  189.         } else
  190.         if( len == 10 && strEQ( cp, "references" ) ) {
  191.         /* include preceding space in saved reference */
  192.         len = strlen( str + 1 );
  193.         bcopy( str + 1, references, len + 1 );
  194.         str = references + len;
  195.         /* check for continuation lines */
  196. #ifdef SERVER
  197.         while( get_server( cp = buff, sizeof buff ) == 0 ) {
  198. #else
  199.         while( (cp = fgets( buff, sizeof buff, fp_article )) != Nullch ) {
  200. #endif
  201.             if( *cp != ' ' && *cp != '\t' ) {
  202.             goto process_line;
  203.             }
  204.             while( *++cp == ' ' || *cp == '\t' ) {
  205.             ;
  206.             }
  207.             *--cp = ' ';
  208.             /* If the references are too long, shift them over to
  209.             ** always save the most recent ones.
  210.             */
  211.             if( (len += strlen( cp )) > 1023 ) {
  212.             strcpy( buff, buff + len - 1023 );
  213.             str -= len - 1023;
  214.             len = 1023;
  215.             }
  216.             strcpy( str, cp );
  217.         }/* while */
  218.         break;
  219.         }/* if */
  220.     }/* while */
  221.     if( article ) {
  222.         insert_article( article, date, i );
  223.     } else {
  224.         if( log_verbosity ) {
  225.         log_error( "Message-ID line missing! [%ld].\n", (long)i );
  226.         }
  227.     }
  228. #ifndef SERVER
  229.     fclose( fp_article );
  230. #endif
  231.     }
  232.  
  233.     if( extra_expire || first_article > total.first ) {
  234.     expire( first_article );
  235.     }
  236.     if( caught_interrupt ) {
  237.     return;
  238.     }
  239.     trim_roots();
  240.     order_roots();
  241.     trim_authors();
  242.  
  243.     total.first = first_article;
  244.     total.last = last_article;
  245. #ifdef SERVER
  246.     extra_expire = orig_extra;
  247. #endif
  248. }
  249.  
  250. /* Search all articles for numbers less than new_first.  Traverse the list
  251. ** using the domain links so we don't have to deal with the tree structure.
  252. ** If extra_expire is true, stat() all valid articles to make sure they are
  253. ** really there and expire them if they're not.
  254. */
  255. void
  256. expire( new_first )
  257. ART_NUM new_first;
  258. {
  259.     register DOMAIN *domain;
  260.     register ARTICLE *article, *next_art, *hold;
  261.  
  262.     for( domain = &unk_domain; domain; domain = next_domain ) {
  263.     next_domain = domain->link;
  264.     for( article = domain->ids; article; article = next_art ) {
  265.         if( caught_interrupt ) {
  266.         return;
  267.         }
  268.         next_art = article->id_link;
  269.         if( !article->subject || (article->flags & NEW_ARTICLE) ) {
  270.         continue;
  271.         }
  272.         if( extra_expire && article->num >= new_first ) {
  273. #ifdef SERVER
  274.         sprintf( buff, "STAT %ld", (long)article->num );
  275.         put_server( buff );
  276.         if( get_server( buff, sizeof buff ) == 0 && *buff == CHAR_OK ) {
  277.             continue;
  278.         }
  279. #else
  280.         sprintf( buff, "%ld", (long)article->num );
  281.         if( !stat( buff, &filestat ) || errno != ENOENT ) {
  282.             continue;
  283.         }
  284. #endif
  285.         }
  286.         if( extra_expire || article->num < new_first ) {
  287.         article->subject->count--;
  288.         article->subject = 0;
  289.         article->author->count--;
  290.         article->author = 0;
  291.         /* Free expired article if it has no children.  Then check
  292.         ** if the parent(s) are also fake and can be freed.  We'll
  293.         ** free any empty roots later.
  294.         */
  295.         while( !article->children ) {
  296.             hold = article->parent;
  297.             unlink_child( article );
  298.             free_article( article );
  299.             if( hold && !hold->subject ) {
  300.             if( (article = hold) == next_art ) {
  301.                 next_art = next_art->id_link;
  302.             }
  303.             } else {
  304.             break;
  305.             }
  306.         }
  307.         expired_count++;
  308.         }/* if */
  309.     }/* for */
  310.     }/* for */
  311.     next_domain = Null(DOMAIN*);
  312. }
  313.  
  314. /* Trim the article chains down so that we don't have more than one faked
  315. ** article between the root any real ones.
  316. */
  317. void
  318. trim_roots()
  319. {
  320.     register ROOT *root, *last_root;
  321.     register ARTICLE *article, *next;
  322.     register SUBJECT *subject, *last_subj;
  323.     register int found;
  324.  
  325. #ifndef lint
  326.     last_root = (ROOT *)&root_root;
  327. #else
  328.     last_root = Null(ROOT*);
  329. #endif
  330.     for( root = root_root; root; root = last_root->link ) {
  331.     for( article = root->articles; article; article = article->siblings ) {
  332.         /* If an article has no subject, it is a "fake" reference node.
  333.         ** If all of its immediate children are also fakes, delete it
  334.         ** and graduate the children to the root.  If everyone is fake,
  335.         ** the chain dies.
  336.         */
  337.         while( !article->subject ) {
  338.         found = 0;
  339.         for( next = article->children; next; next = next->siblings ) {
  340.             if( next->subject ) {
  341.             found = 1;
  342.             break;
  343.             }
  344.         }
  345.         if( !found ) {
  346.             /* Remove this faked article and move all its children
  347.             ** up to the root.
  348.             */
  349.             next = article->children;
  350.             unlink_child( article );
  351.             free_article( article );
  352.             for( article = next; article; article = next ) {
  353.             next = article->siblings;
  354.             article->parent = Nullart;
  355.             link_child( article );
  356.             }
  357.             article = root->articles;    /* start this root over */
  358.         } else {
  359.             break;            /* else, on to next article */
  360.         }
  361.         }
  362.     }
  363.     /* Free all unused subject strings.  Begin by trying to find a
  364.     ** subject for the root's pointer.
  365.     */
  366.     for( subject = root->subjects; subject && !subject->count; subject = root->subjects ) {
  367.         root->subjects = subject->link;
  368.         free_subject( subject );
  369.         root->subject_cnt--;
  370.     }
  371.     /* Then free up any unsed intermediate subjects.
  372.     */
  373.     if( (last_subj = subject) != Null(SUBJECT*) ) {
  374.         while( (subject = subject->link) != Null(SUBJECT*) ) {
  375.         if( !subject->count ) {
  376.             last_subj->link = subject->link;
  377.             free_subject( subject );
  378.             root->subject_cnt--;
  379.             subject = last_subj;
  380.         } else {
  381.             last_subj = subject;
  382.         }
  383.         }
  384.     }
  385.     /* Now, free all roots without articles.  Flag unexpeced errors.
  386.     */
  387.     if( !root->articles ) {
  388.         if( root->subjects ) {
  389.         log_error( "** Empty root still had subjects remaining! **\n" );
  390.         }
  391.         last_root->link = root->link;
  392.         free_root( root );
  393.     } else {
  394.         last_root = root;
  395.     }
  396.     }
  397. }
  398.  
  399. /* Descend the author list, find any author names that aren't used
  400. ** anymore and free them.
  401. */
  402. void
  403. trim_authors()
  404. {
  405.     register AUTHOR *author, *last_author;
  406.  
  407. #ifndef lint
  408.     last_author = (AUTHOR *)&author_root;
  409. #else
  410.     last_author = Null(AUTHOR*);
  411. #endif
  412.     for( author = author_root; author; author = last_author->link ) {
  413.     if( !author->count ) {
  414.         last_author->link = author->link;
  415.         free_author( author );
  416.     } else {
  417.         last_author = author;
  418.     }
  419.     }
  420. }
  421.  
  422. /* Reorder the roots to place the oldest ones first (age determined by
  423. ** date of oldest article).
  424. */
  425. void
  426. order_roots()
  427. {
  428.     register ROOT *root, *next, *search;
  429.  
  430.     /* If we don't have at least two roots, we're done! */
  431.     if( !(root = root_root) || !(next = root->link) ) {
  432.     return;                        /* RETURN */
  433.     }
  434.     /* Break the old list off after the first root, and then start
  435.     ** inserting the roots into the list by date.
  436.     */
  437.     root->link = Null(ROOT*);
  438.     while( (root = next) != Null(ROOT*) ) {
  439.     next = next->link;
  440.     if( (search = root_root)->articles->date >= root->articles->date ) {
  441.         root->link = root_root;
  442.         root_root = root;
  443.     } else {
  444.         while( search->link
  445.          && search->link->articles->date < root->articles->date ) {
  446.         search = search->link;
  447.         }
  448.         root->link = search->link;
  449.         search->link = root;
  450.     }
  451.     }
  452. }
  453.  
  454. #define EQ(x,y) ((isupper(x) ? tolower(x) : (x)) == (y))
  455.  
  456. /* Parse the subject into 72 characters or less.  Remove any "Re[:^]"s from
  457. ** the front (noting that it's there), and any "(was: old)" stuff from
  458. ** the end.  Then, compact multiple whitespace characters into one space,
  459. ** trimming leading/trailing whitespace.  If it's still too long, unmercifully
  460. ** cut it off.  We don't bother with subject continuation lines either.
  461. */
  462. void
  463. get_subject_str( str )
  464. register char *str;
  465. {
  466.     register char *cp;
  467.     register int len;
  468.  
  469.     while( *str && (unsigned char)*str <= ' ' ) {
  470.     str++;
  471.     }
  472.     if( !*str ) {
  473.     bcopy( "<None>", subject_str, 7 );
  474.     return;                        /* RETURN */
  475.     }
  476.     cp = str;
  477.     while( EQ( cp[0], 'r' ) && EQ( cp[1], 'e' ) ) {    /* check for Re: */
  478.     cp += 2;
  479.     if( *cp == '^' ) {                /* allow Re^2: */
  480.         while( *++cp <= '9' && *cp >= '0' ) {
  481.         ;
  482.         }
  483.     }
  484.     if( *cp != ':' ) {
  485.         break;
  486.     }
  487.     while( *++cp == ' ' ) {
  488.         ;
  489.     }
  490.     found_Re = 1;
  491.     str = cp;
  492.     }
  493.     /* Remove "(was Re: oldsubject)", because we already know the old subjects.
  494.     ** Also match "(Re: oldsubject)".  Allow possible spaces after the ('s.
  495.     */
  496.     for( cp = str; (cp = index( cp+1, '(' )) != Nullch; ) {
  497.     while( *++cp == ' ' ) {
  498.         ;
  499.     }
  500.     if( EQ( cp[0], 'w' ) && EQ( cp[1], 'a' ) && EQ( cp[2], 's' )
  501.      && (cp[3] == ':' || cp[3] == ' ') )
  502.     {
  503.         *--cp = '\0';
  504.         break;
  505.     }
  506.     if( EQ( cp[0], 'r' ) && EQ( cp[1], 'e' )
  507.      && ((cp[2]==':' && cp[3]==' ') || (cp[2]=='^' && cp[4]==':')) ) {
  508.         *--cp = '\0';
  509.         break;
  510.     }
  511.     }
  512.     /* Copy subject to a temporary string, compacting multiple spaces/tabs */
  513.     for( len = 0, cp = subject_str; len < 72 && *str; len++ ) {
  514.     if( (unsigned char)*str <= ' ' ) {
  515.         while( *++str && (unsigned char)*str <= ' ' ) {
  516.         ;
  517.         }
  518.         *cp++ = ' ';
  519.     } else {
  520.         *cp++ = *str++;
  521.     }
  522.     }
  523.     if( cp[-1] == ' ' ) {
  524.     cp--;
  525.     }
  526.     *cp = '\0';
  527. }
  528.  
  529. /* Try to fit the author name in 16 bytes.  Use the comment portion in
  530. ** parenthesis if present.  Cut off non-commented names at the '@' or '%'.
  531. ** Then, put as many characters as we can into the 16 bytes, packing multiple
  532. ** whitespace characters into a single space.
  533. ** We should really implement a nice name shortening algorithm, or simply
  534. ** grab the name packing code from nn.
  535. */
  536. void
  537. get_author_str( str )
  538. char *str;
  539. {
  540.     register char *cp, *cp2;
  541.  
  542.     if( (cp = index( str, '(' )) != Nullch ) {
  543.     str = cp+1;
  544.     if( (cp = rindex( str, ')' )) != Nullch ) {
  545.         *cp = '\0';
  546.     }
  547.     } else {
  548.     if( (cp = index( str, '@' )) != Nullch ) {
  549.         *cp = '\0';
  550.     }
  551.     if( (cp = index( str, '%' )) != Nullch ) {
  552.         *cp = '\0';
  553.     }
  554.     }
  555.     for( cp = str, cp2 = author_str; *cp && cp2-author_str < 16; ) {
  556.     /* Pack white space and turn ctrl-chars into spaces. */
  557.     if( *cp <= ' ' ) {
  558.         while( *++cp && *cp <= ' ' ) {
  559.         ;
  560.         }
  561.         if( cp2 != author_str ) {
  562.         *cp2++ = ' ';
  563.         }
  564.     } else {
  565.         *cp2++ = *cp++;
  566.     }
  567.     }
  568.     *cp2 = '\0';
  569. }
  570.  
  571. /* Take a message-id and see if we already know about it.  If so, return it.
  572. ** If not, create it.  We separate the id into its id@domain parts, and
  573. ** link all the unique ids to one copy of the domain portion.  This saves
  574. ** a bit of space.
  575. */
  576. ARTICLE *
  577. get_article( msg_id )
  578. char *msg_id;
  579. {
  580.     register DOMAIN *domain;
  581.     register ARTICLE *article;
  582.     register char *cp, *after_at;
  583.  
  584.     /* Take message id, break it up into <id@domain>, and try to match it.
  585.     */
  586.     while( *msg_id == ' ' ) {
  587.     msg_id++;
  588.     }
  589.     cp = msg_id + strlen( msg_id ) - 1;
  590.     if( msg_id >= cp ) {
  591.     if( log_verbosity ) {
  592.         log_error( "Message-ID is empty!\n" );
  593.     }
  594.     return Nullart;
  595.     }
  596.     if( *msg_id++ != '<' ) {
  597.     if( log_verbosity ) {
  598.         log_error( "Message-ID doesn't start with '<'.\n" );
  599.     }
  600.     msg_id--;
  601.     }
  602.     if( *cp != '>' ) {
  603.     if( log_verbosity ) {
  604.         log_error( "Message-ID doesn't end with '>'.\n" );
  605.     }
  606.     cp++;
  607.     }
  608.     *cp = '\0';
  609.     if( msg_id == cp ) {
  610.     if( log_verbosity ) {
  611.         log_error( "Message-ID is null!\n" );
  612.     }
  613.     return Nullart;
  614.     }
  615.  
  616.     if( (after_at = index( msg_id, '@' )) == Nullch ) {
  617.     domain = &unk_domain;
  618.     } else {
  619.     *after_at++ = '\0';
  620.     for( cp = after_at; *cp; cp++ ) {
  621.         if( isupper(*cp) ) {
  622.         *cp = tolower(*cp);        /* lower-case domain portion */
  623.         }
  624.     }
  625.     *cp = '\0';
  626.     /* Try to find domain name in database. */
  627.     for( domain = unk_domain.link; domain; domain = domain->link ) {
  628.         if( strEQ( domain->name, after_at ) ) {
  629.         break;
  630.         }
  631.     }
  632.     if( !domain ) {        /* if domain doesn't exist, create it */
  633.       register int len = cp - after_at + 1;
  634.         domain = (DOMAIN *)safemalloc( sizeof (DOMAIN) );
  635.         total.domain++;
  636.         domain->name = safemalloc( len );
  637.         total.string2 += len;
  638.         bcopy( after_at, domain->name, len );
  639.         domain->ids = Nullart;
  640.         domain->link = unk_domain.link;
  641.         unk_domain.link = domain;
  642.     }
  643.     }
  644.     /* Try to find id in this domain. */
  645.     for( article = domain->ids; article; article = article->id_link ) {
  646.     if( strEQ( article->id, msg_id ) ) {
  647.         break;
  648.     }
  649.     }
  650.     if( !article ) {        /* If it doesn't exist, create an article */
  651.       register int len = strlen( msg_id ) + 1;
  652.     article = (ARTICLE *)safemalloc( sizeof (ARTICLE) );
  653.     bzero( article, sizeof (ARTICLE) );
  654.     total.article++;
  655.     article->num = 0;
  656.     article->id = safemalloc( len );
  657.     total.string2 += len;
  658.     bcopy( msg_id, article->id, len );
  659.     article->domain = domain;
  660.     article->id_link = domain->ids;
  661.     domain->ids = article;
  662.     }
  663.     return article;
  664. }
  665.  
  666. /* Take all the data we've accumulated about the article and shove it into
  667. ** the article tree at the best place we can possibly imagine.
  668. */
  669. void
  670. insert_article( article, date, num )
  671. ARTICLE *article;
  672. time_t date;
  673. ART_NUM num;
  674. {
  675.     register ARTICLE *node, *last;
  676.     register char *cp, *end;
  677.     int len;
  678.  
  679.     if( article->subject ) {
  680.     if( log_verbosity ) {
  681.         log_error( "We've already seen article #%ld (%s@%s)\n",
  682.         (long)num, article->id, article->domain->name );
  683.     }
  684.     return;                        /* RETURN */
  685.     }
  686.     article->date = date;
  687.     article->num = num;
  688.     article->flags = NEW_ARTICLE;
  689.  
  690.     if( !*references && found_Re ) {
  691.     if( log_verbosity > 1 ) {
  692.         log_error( "Missing reference line!  [%ld]\n", (long)num );
  693.     }
  694.     }
  695.     /* If the article has a non-zero root, it is already in a thread somewhere.
  696.     ** Unlink it to try to put it in the best possible spot.
  697.     */
  698.     if( article->root ) {
  699.     /* Check for a real or shared-fake parent.  Articles that have never
  700.     ** existed have a num of 0.  Expired articles that remain as references
  701.     ** have a valid num.  (Valid date too, but no subject.)
  702.     */
  703.     for( node = article->parent;
  704.          node && !node->num && node->child_cnt == 1;
  705.          node = node->parent )
  706.     {
  707.         ;
  708.     }
  709.     unlink_child( article );
  710.     if( node ) {            /* do we have decent parents? */
  711.         /* Yes: assume that our references are ok, and just reorder us
  712.         ** with our siblings by date.
  713.         */
  714.         link_child( article );
  715.         use_root( article, article->root );
  716.         /* Freshen the date in any faked parent articles. */
  717.         for( node = article->parent;
  718.          node && !node->num && date < node->date;
  719.          node = node->parent )
  720.         {
  721.         node->date = date;
  722.         unlink_child( node );
  723.         link_child( node );
  724.         }
  725.         return;                    /* RETURN */
  726.     }
  727.     /* We'll assume that this article has as good or better references
  728.     ** than the child that faked us initially.  Free the fake reference-
  729.     ** chain and process our references as usual.
  730.     */
  731.     for( node = article->parent; node; node = node->parent ) {
  732.         unlink_child( node );
  733.         free_article( node );
  734.     }
  735.     article->parent = Nullart;        /* neaten up */
  736.     article->siblings = Nullart;
  737.     }
  738.   check_references:
  739.     if( !*references ) {    /* If no references but "Re:" in subject, */
  740.     if( found_Re ) {    /* search for a reference in any cited text */
  741. #ifndef SERVER
  742.         for( len = 4; len && fgets( buff, sizeof buff, fp_article ); len-- ) {
  743.         if( (cp = index( buff, '<' )) && (end = index( cp, ' ' )) ) {
  744.             if( end[-1] == ',' ) {
  745.             end--;
  746.             }
  747.             *end = '\0';
  748.             if( (end = index( cp, '>' )) == Nullch ) {
  749.             end = cp + strlen( cp ) - 1;
  750.             }
  751.             if( valid_message_id( cp, end ) ) {
  752.             strcpy( references+1, cp );
  753.             *references = ' ';
  754.             if( log_verbosity > 2 ) {
  755.                 log_error( "Found cited-text reference: '%s' [%ld]\n",
  756.                 references+1, (long)num );
  757.             }
  758.             break;
  759.             }
  760.         }
  761.         }
  762. #endif
  763.     } else {
  764.         article->flags |= ROOT_ARTICLE;
  765.     }
  766.     }
  767.     /* If we have references, process them from the right end one at a time
  768.     ** until we either run into somebody, or we run out of references.
  769.     */
  770.     if( *references ) {
  771.     last = article;
  772.     node = Nullart;
  773.     end = references + strlen( references ) - 1;
  774.     while( (cp = rindex( references, ' ' )) != Nullch ) {
  775.         *cp++ = '\0';
  776.         while( end >= cp && ((unsigned char)*end <= ' ' || *end == ',') ) {
  777.         end--;
  778.         }
  779.         end[1] = '\0';
  780.         /* Quit parsing references if this one is garbage. */
  781.         if( !valid_message_id( cp, end ) ) {
  782.         if( log_verbosity ) {
  783.             log_error( "Bad ref '%s' [%ld]\n", cp, (long)num );
  784.         }
  785.         break;
  786.         }
  787.         /* Dump all domains that end in '.', such as "..." & "1@DEL." */
  788.         if( end[-1] == '.' ) {
  789.         break;
  790.         }
  791.         node = get_article( cp );
  792.         /* Check for duplicates on the reference line.  Brand-new data has
  793.         ** no date.  Data we just allocated earlier on this line has a
  794.         ** date but no root.  Special-case the article itself, since it
  795.         ** MIGHT have a root.
  796.         */
  797.         if( (node->date && !node->root) || node == article ) {
  798.         if( log_verbosity ) {
  799.             log_error( "Reference line contains duplicates [%ld]\n",
  800.             (long)num );
  801.         }
  802.         if( (node = last) == article ) {
  803.             node = Nullart;
  804.         }
  805.         continue;
  806.         }
  807.         last->parent = node;
  808.         link_child( last );
  809.         if( node->root ) {
  810.         break;
  811.         }
  812.         node->date = date;
  813.         last = node;
  814.         end = cp-2;
  815.     }
  816.     if( !node ) {
  817.         *references = '\0';
  818.         goto check_references;
  819.     }
  820.     /* Check if we ran into anybody that was already linked.  If so, we
  821.     ** just use their root.
  822.     */
  823.     if( node->root ) {
  824.         /* See if this article spans the gap between what we thought
  825.         ** were two different roots.
  826.         */
  827.         if( article->root && article->root != node->root ) {
  828.         merge_roots( node->root, article->root );
  829.         /* Set the roots of any children we brought with us. */
  830.         set_root( article, node->root );
  831.         }
  832.         use_root( article, node->root );
  833.     } else {
  834.         /* We didn't find anybody we knew, so either create a new root or
  835.         ** use the article's root if it was previously faked.
  836.         */
  837.         if( !article->root ) {
  838.         make_root( node );
  839.         use_root( article, node->root );
  840.         } else {
  841.         use_root( article, article->root );
  842.         node->root = article->root;
  843.         link_child( node );
  844.         }
  845.     }
  846.     /* Set the roots of the faked articles we created as references. */
  847.     for( node = article->parent; node && !node->root; node = node->parent ) {
  848.         node->root = article->root;
  849.     }
  850.     /* Make sure we didn't circularly link to a child article(!), by
  851.     ** ensuring that we run into the root before we run into ourself.
  852.     */
  853.     while( node && node->parent != article ) {
  854.         node = node->parent;
  855.     }
  856.     if( node ) {
  857.         /* Ugh.  Someone's tweaked reference line with an incorrect
  858.         ** article order arrived first, and one of our children is
  859.         ** really one of our ancestors. Cut off the bogus child branch
  860.         ** right where we are and link it to the root.
  861.         */
  862.         if( log_verbosity ) {
  863.         log_error("Found ancestral child -- fixing.\n");
  864.         }
  865.         unlink_child( node );
  866.         node->parent = Nullart;
  867.         link_child( node );
  868.     }
  869.     } else {
  870.     /* The article has no references.  Either turn it into a new root, or
  871.     ** re-attach fleshed-out (previously faked) article to its old root.
  872.     */
  873.     if( !article->root ) {
  874.         make_root( article );
  875.     } else {
  876.         use_root( article, article->root );
  877.         link_child( article );
  878.     }
  879.     }
  880. }
  881.  
  882. /* Check if the string we've found looks like a valid message-id reference.
  883. */
  884. int
  885. valid_message_id( start, end )
  886. register char *start, *end;
  887. {
  888.     char *mid;
  889.  
  890.     if( *end != '>' ) {
  891.     /* Compensate for spacecadets who include the header in their
  892.     ** subsitution of all '>'s into another citation character.
  893.     */
  894.     if( *end == '<' || *end == '-' || *end == '!' || *end == '%'
  895.      || *end == ')' || *end == '|' || *end == ':' || *end == '}'
  896.      || *end == '*' || *end == '+' || *end == '#' || *end == ']'
  897.      || *end == '@' ) {
  898.         if( log_verbosity ) {
  899.         log_error( "Reference ended in '%c'.\n", *end );
  900.         }
  901.         *end = '>';
  902.     }
  903.     }
  904.     /* Id must be "<...@...>" */
  905.     if( *start != '<' || *end != '>' || (mid = index( start, '@' )) == Nullch
  906.      || mid == start+1 || mid+1 == end ) {
  907.     return 0;                    /* RETURN */
  908.     }
  909.     return 1;
  910. }
  911.  
  912. /* Remove an article from its parent/siblings.  Leave parent pointer intact.
  913. */
  914. void
  915. unlink_child( child )
  916. register ARTICLE *child;
  917. {
  918.     register ARTICLE *last;
  919.  
  920.     if( !(last = child->parent) ) {
  921.     child->root->thread_cnt--;
  922.     if( (last = child->root->articles) == child ) {
  923.         child->root->articles = child->siblings;
  924.     } else {
  925.         goto sibling_search;
  926.     }
  927.     } else {
  928.     last->child_cnt--;
  929.     if( last->children == child ) {
  930.         last->children = child->siblings;
  931.     } else {
  932.         last = last->children;
  933.       sibling_search:
  934.         while( last->siblings != child ) {
  935.         last = last->siblings;
  936.         }
  937.         last->siblings = child->siblings;
  938.     }
  939.     }
  940. }
  941.  
  942. /* Link an article to its parent article.  If its parent pointer is zero,
  943. ** link it to its root.  Sorts siblings by date.
  944. */
  945. void
  946. link_child( child )
  947. register ARTICLE *child;
  948. {
  949.     register ARTICLE *node;
  950.     register ROOT *root;
  951.  
  952.     if( !(node = child->parent) ) {
  953.     root = child->root;
  954.     root->thread_cnt++;
  955.     node = root->articles;
  956.     if( !node || child->date < node->date ) {
  957.         child->siblings = node;
  958.         root->articles = child;
  959.     } else {
  960.         goto sibling_search;
  961.     }
  962.     } else {
  963.     node->child_cnt++;
  964.     node = node->children;
  965.     if( !node || child->date < node->date ) {
  966.         child->siblings = node;
  967.         child->parent->children = child;
  968.     } else {
  969.       sibling_search:
  970.         for( ; node->siblings; node = node->siblings ) {
  971.         if( node->siblings->date > child->date ) {
  972.             break;
  973.         }
  974.         }
  975.         child->siblings = node->siblings;
  976.         node->siblings = child;
  977.     }
  978.     }
  979. }
  980.  
  981. /* Create a new root for the specified article.  If the current subject_str
  982. ** matches any pre-existing root's subjects, we'll instead add it on as a
  983. ** parallel thread.
  984. */
  985. void
  986. make_root( article )
  987. ARTICLE *article;
  988. {
  989.     register ROOT *new, *node;
  990.     register SUBJECT *subject;
  991.  
  992. #ifndef NO_SUBJECT_MATCHING
  993.     /* First, check the other root's subjects for a match. */
  994.     for( node = root_root; node; node = node->link ) {
  995.     for( subject = node->subjects; subject; subject = subject->link ) {
  996.         if( subject_equal( subject->str, subject_str ) ) {
  997.         use_root( article, node );        /* use it instead */
  998.         link_child( article );
  999.         return;                    /* RETURN */
  1000.         }
  1001.     }
  1002.     }
  1003. #endif
  1004.  
  1005.     /* Create a new root. */
  1006.     new = (ROOT *)safemalloc( sizeof (ROOT) );
  1007.     total.root++;
  1008.     new->articles = article;
  1009.     new->root_num = article->num;
  1010.     new->thread_cnt = 1;
  1011.     if( article->num ) {
  1012.     article->author = new_author();
  1013.     new->subject_cnt = 1;
  1014.     new->subjects = article->subject = new_subject();
  1015.     } else {
  1016.     new->subject_cnt = 0;
  1017.     new->subjects = Null(SUBJECT*);
  1018.     }
  1019.     article->root = new;
  1020.     new->link = root_root;
  1021.     root_root = new;
  1022. }
  1023.  
  1024. /* Add this article's subject onto the indicated root's list.  Point the
  1025. ** article at the root.
  1026. */
  1027. void
  1028. use_root( article, root )
  1029. ARTICLE *article;
  1030. ROOT *root;
  1031. {
  1032.     register SUBJECT *subject;
  1033.     register ROOT *root2;
  1034.     SUBJECT *hold, *child_subj = Null(SUBJECT*);
  1035.     ARTICLE *node;
  1036.  
  1037.     article->root = root;
  1038.  
  1039.     /* If it's a fake, there's no subject to add. */
  1040.     if( !article->num ) {
  1041.     return;                        /* RETURN */
  1042.     }
  1043.  
  1044.     /* If we haven't picked a unique message number to represent this root,
  1045.     ** use the first non-zero number we encounter.  Which one doesn't matter.
  1046.     */
  1047.     if( !root->root_num ) {
  1048.     root->root_num = article->num;
  1049.     }
  1050.     article->author = new_author();
  1051.  
  1052.     /* Check if the new subject matches any of the other subjects in this root.
  1053.     ** If so, we just update the count.  If not, check all the other roots for
  1054.     ** a match.  If found, the new subject is common between the two roots, so
  1055.     ** we merge the two roots together.
  1056.     */
  1057.     root2 = root;
  1058. #ifndef NO_SUBJECT_MATCHING
  1059.     do {
  1060. #endif
  1061.     for( subject = root2->subjects; subject; subject = subject->link ) {
  1062.         if( subject_equal( subject->str, subject_str ) ) {
  1063.         article->subject = subject;
  1064.         subject->count++;
  1065. #ifndef NO_SUBJECT_MATCHING
  1066.         if( root2 != root ) {
  1067.             merge_roots( root, root2 );
  1068.         }
  1069. #endif
  1070.         return;                    /* RETURN */
  1071.         }
  1072.     }
  1073. #ifndef NO_SUBJECT_MATCHING
  1074.     if( (root2 = root2->link) == Null(ROOT*) ) {
  1075.         root2 = root_root;
  1076.     }
  1077.     } while( root2 != root );
  1078. #endif
  1079.  
  1080.     article->subject = hold = new_subject();
  1081.     root->subject_cnt++;
  1082.  
  1083.     /* Find subject of any pre-existing children.  We want to insert the new
  1084.     ** subject before a child's to keep the subject numbering intuitive
  1085.     ** in the newsreader.
  1086.     */
  1087.     for( node = article->children; node; node = node->children ) {
  1088.     if( node->subject ) {
  1089.         child_subj = node->subject;
  1090.         break;
  1091.     }
  1092.     }
  1093.     if( !(subject = root->subjects) || subject == child_subj ) {
  1094.     hold->link = root->subjects;
  1095.     root->subjects = hold;
  1096.     } else {
  1097.     while( subject->link && subject->link != child_subj ) {
  1098.         subject = subject->link;
  1099.     }
  1100.     hold->link = subject->link;
  1101.     subject->link = hold;
  1102.     }
  1103. }
  1104.  
  1105. /* Check subjects in a case-insignificant, punctuation ignoring manner.
  1106. */
  1107. int
  1108. subject_equal( str1, str2 )
  1109. register char *str1, *str2;
  1110. {
  1111.     register char ch1, ch2;
  1112.  
  1113.     while( (ch1 = *str1++) ) {
  1114.     if( ch1 == ' ' || ispunct( ch1 ) ) {
  1115.         while( *str1 && (*str1 == ' ' || ispunct( *str1 )) ) {
  1116.         str1++;
  1117.         }
  1118.         ch1 = ' ';
  1119.     } else if( isupper( ch1 ) ) {
  1120.         ch1 = tolower( ch1 );
  1121.     }
  1122.     if( !(ch2 = *str2++) ) {
  1123.         return 0;
  1124.     }
  1125.     if( ch2 == ' ' || ispunct( ch2 ) ) {
  1126.         while( *str2 && (*str2 == ' ' || ispunct( *str2 )) ) {
  1127.         str2++;
  1128.         }
  1129.         ch2 = ' ';
  1130.     } else if( isupper( ch2 ) ) {
  1131.         ch2 = tolower( ch2 );
  1132.     }
  1133.     if( ch1 != ch2 ) {
  1134.         return 0;
  1135.     }
  1136.     }
  1137.     if( *str2 ) {
  1138.     return 0;
  1139.     }
  1140.     return 1;
  1141. }
  1142.  
  1143. /* Create a new subject structure. */
  1144. SUBJECT *
  1145. new_subject()
  1146. {
  1147.     register int len = strlen( subject_str ) + 1;
  1148.     register SUBJECT *subject;
  1149.  
  1150.     subject = (SUBJECT *)safemalloc( sizeof (SUBJECT) );
  1151.     total.subject++;
  1152.     subject->count = 1;
  1153.     subject->link = Null(SUBJECT*);
  1154.     subject->str = safemalloc( len );
  1155.     total.string1 += len;
  1156.     bcopy( subject_str, subject->str, len );
  1157.  
  1158.     return subject;
  1159. }
  1160.  
  1161. /* Create a new author structure. */
  1162. AUTHOR *
  1163. new_author()
  1164. {
  1165.     register len = strlen( author_str ) + 1;
  1166.     register AUTHOR *author, *last_author;
  1167.  
  1168.     last_author = Null(AUTHOR*);
  1169.     for( author = author_root; author; author = author->link ) {
  1170. #ifndef DONT_COMPARE_AUTHORS    /* might like to define this to save time */
  1171.     if( strEQ( author->name, author_str ) ) {
  1172.         author->count++;
  1173.         return author;                /* RETURN */
  1174.     }
  1175. #endif
  1176.     last_author = author;
  1177.     }
  1178.  
  1179.     author = (AUTHOR *)safemalloc( sizeof (AUTHOR) );
  1180.     total.author++;
  1181.     author->count = 1;
  1182.     author->link = Null(AUTHOR*);
  1183.     author->name = safemalloc( len );
  1184.     total.string1 += len;
  1185.     bcopy( author_str, author->name, len );
  1186.  
  1187.     if( last_author ) {
  1188.     last_author->link = author;
  1189.     } else {
  1190.     author_root = author;
  1191.     }
  1192.     return author;
  1193. }
  1194.  
  1195. /* Insert all of root2 into root1, setting the proper root values and
  1196. ** updating subject counts.
  1197. */
  1198. void
  1199. merge_roots( root1, root2 )
  1200. ROOT *root1, *root2;
  1201. {
  1202.     register ARTICLE *node, *next;
  1203.     register SUBJECT *subject;
  1204.  
  1205.     /* Remember whoever's root num is lower.  This could screw up a
  1206.     ** newsreader's kill-thread code if someone already saw the roots as
  1207.     ** being separate, but it must be done.  The newsreader code will have
  1208.     ** to handle this as best as it can.
  1209.     */
  1210.     if( root1->root_num > root2->root_num ) {
  1211.     root1->root_num = root2->root_num;
  1212.     }
  1213.  
  1214.     for( node = root2->articles; node; node = next ) {
  1215.     /* For each article attached to root2, detach them, set the
  1216.     ** branch's root pointers to root1, and then attach it to root1.
  1217.     */
  1218.     next = node->siblings;
  1219.     unlink_child( node );
  1220.     node->siblings = Nullart;
  1221.     set_root( node, root1 );        /* sets children too */
  1222.     /* Link_child() depends on node->parent being null and node->root
  1223.     ** being set.
  1224.     */
  1225.     link_child( node );
  1226.     }
  1227.     root1->subject_cnt += root2->subject_cnt;
  1228.     if( !(subject = root1->subjects) ) {
  1229.     root1->subjects = root2->subjects;
  1230.     } else {
  1231.     while( subject->link ) {
  1232.         subject = subject->link;
  1233.     }
  1234.     subject->link = root2->subjects;
  1235.     }
  1236.     unlink_root( root2 );
  1237.     free_root( root2 );
  1238. }
  1239.  
  1240. /* When merging roots, we need to reset all the root pointers.
  1241. */
  1242. void
  1243. set_root( node, root )
  1244. ARTICLE *node;
  1245. ROOT *root;
  1246. {
  1247.     do {
  1248.     node->root = root;
  1249.     if( node->children ) {
  1250.         set_root( node->children, root );
  1251.     }
  1252.     } while( node = node->siblings );
  1253. }
  1254.  
  1255. /* Unlink a root from its neighbors. */
  1256. void
  1257. unlink_root( root )
  1258. register ROOT *root;
  1259. {
  1260.     register ROOT *node;
  1261.  
  1262.     if( (node = root_root) == root ) {
  1263.     root_root = root->link;
  1264.     } else {
  1265.     while( node->link != root ) {
  1266.         node = node->link;
  1267.     }
  1268.     node->link = root->link;
  1269.     }
  1270. }
  1271.  
  1272. /* Free an article and its message-id string.  All other resources must
  1273. ** already be free, and it must not be attached to any threads.
  1274. */
  1275. void
  1276. free_article( this )
  1277. ARTICLE *this;
  1278. {
  1279.     register ARTICLE *art;
  1280.  
  1281.     if( (art = this->domain->ids) == this ) {
  1282.     if( !(this->domain->ids = this->id_link) ) {
  1283.         free_domain( this->domain );
  1284.     }
  1285.     } else {
  1286.     while( this != art->id_link ) {
  1287.         art = art->id_link;
  1288.     }
  1289.     art->id_link = this->id_link;
  1290.     }
  1291.     total.string2 -= strlen( this->id ) + 1;
  1292.     free( this->id );
  1293.     free( this );
  1294.     total.article--;
  1295. }
  1296.  
  1297. /* Free the domain only when its last unique id has been freed. */
  1298. void
  1299. free_domain( this )
  1300. DOMAIN *this;
  1301. {
  1302.     register DOMAIN *domain;
  1303.  
  1304.     if( this == (domain = &unk_domain) ) {
  1305.     return;
  1306.     }
  1307.     if( this == next_domain ) {    /* help expire routine skip freed domains */
  1308.     next_domain = next_domain->link;
  1309.     }
  1310.     while( this != domain->link ) {
  1311.     domain = domain->link;
  1312.     }
  1313.     domain->link = this->link;
  1314.     total.string2 -= strlen( this->name ) + 1;
  1315.     free( this->name );
  1316.     free( this );
  1317.     total.domain--;
  1318. }
  1319.  
  1320. /* Free the subject structure and its string. */
  1321. void
  1322. free_subject( this )
  1323. SUBJECT *this;
  1324. {
  1325.     total.string1 -= strlen( this->str ) + 1;
  1326.     free( this->str );
  1327.     free( this );
  1328.     total.subject--;
  1329. }
  1330.  
  1331. /* Free a root.  It must already be unlinked. */
  1332. void
  1333. free_root( this )
  1334. ROOT *this;
  1335. {
  1336.     free( this );
  1337.     total.root--;
  1338. }
  1339.  
  1340. /* Free the author structure when it's not needed any more. */
  1341. void
  1342. free_author( this )
  1343. AUTHOR *this;
  1344. {
  1345.     total.string1 -= strlen( this->name ) + 1;
  1346.     free( this->name );
  1347.     free( this );
  1348.     total.author--;
  1349. }
  1350.