home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / os2 / thread / pmmthrd.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-11  |  16.8 KB  |  559 lines
  1.  
  2. /*
  3.     PMNEWS 1.0
  4.  
  5.     Threading functions for the PMNEWS news reader
  6.  
  7.     This program is free software; you can redistribute it and/or modify
  8.     it under the terms of the GNU General Public License, version 1, as
  9.     published by the Free Software Foundation.
  10.  
  11.     This program is distributed in the hope that it will be useful,
  12.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14.     GNU General Public License for more details.
  15.  
  16.     See the file COPYING, which contains a copy of the GNU General
  17.     Public License.
  18.  
  19.  */
  20. #include  <ctype.h>
  21. #include  <string.h>
  22. #include  <stdio.h>
  23. #include  <stdlib.h>
  24. #include  <os2.h>    /* for typedefs used below */
  25. #include "defs.h"
  26. #include "pmnews.h"
  27.  
  28. /*   Since this interface requires a one-pass algorithm
  29.  *   we need to tokenize each subject and analyze it's
  30.  *   meaingful tokens with respect to all previous tokens.
  31.  *
  32.  *   Init time:
  33.  *        Allocate space for subject_token_space.
  34.  *        Initialize anchor for subject line (ARTICLE) list
  35.  *
  36.  *   For each token:
  37.  *        Search against 'trivial_token_space'.
  38.  *        If found, iterate.
  39.  *        Count the token.
  40.  *        Hash against 'subject_token_space'.
  41.  *        If not found,
  42.  *           allocate and establish word_node.
  43.  *           enter this token in the new reference list.
  44.  *           iterate.
  45.  *        enter this token in the new reference list.
  46.  *        For each ARTICLE element on this word_node:
  47.  *           Search for match in temp_hit_list (a tree).
  48.  *           If found increment count.
  49.  *           else insert element in tree and in one-way list.
  50.  *        iterate.
  51.  *        end (while tokens)
  52.  *
  53.  *   Search the temp_hit_list for the entry with the
  54.  *     highest count via the one-way list.
  55.  *
  56.  *   If that count > 75% of the total token count
  57.  *      free temp_hit_list and new_reference_list
  58.  *      return TRUE with the associated ARTICLE ptr
  59.  *   else
  60.  *      allocate an ARTICLE.
  61.  *      save the token count in the 'left' pointer
  62.  *      queue the new_reference entries to their
  63.  *        respective word_nodes (using above ARTICLE).
  64.  *      free temp_hit_list and new_reference_list
  65.  *      return TRUE
  66. */
  67.  
  68.  
  69. #define MAXTOKL 32
  70.  
  71. typedef struct hitent {
  72.   ARTICLE       *subjp;         /* pointer to base article */
  73.   UINT           nhits;         /* number of times referenced */
  74.   struct hitent *hpleft,        /* left branch of hit tree */
  75.                 *hpright,       /* right branch of hit tree */
  76.                 *hpnext;        /* one-way list */
  77.   } HITENT;
  78.  
  79.  
  80. typedef struct artref {
  81.   struct artref * nextar;   /* next in this chain */
  82.   struct artref * nextal;   /* next in allocation chain */
  83.   ARTICLE       * thread;   /* pointer to thread containing this token */
  84.   } ARTREF;
  85.  
  86. typedef struct tokel {
  87.   char           toktxt[MAXTOKL+1];   /* uppercased token */
  88.   BOOL           trivial;       /* token to be ignored */
  89.   struct tokel  *overflow;      /* collision ptr */
  90.   ARTREF        *subhead;       /* head of subject lines with this token */
  91.   } TOKEL;
  92.  
  93. typedef struct newref {
  94.   TOKEL         *reftok;        /* token referenced */
  95.   struct newref *nrnext;        /* next new reference */
  96.   } NEWREF;
  97.  
  98. typedef struct {
  99.   TOKEL *  next_ovflo;          /* next available overflow */
  100.   TOKEL *  subject_token_space; /* primary token area */
  101.   TOKEL *  limit_addr;          /* limit of acquired area */
  102.   ARTREF * headref;             /* allocation chain head for ARTREF */
  103.   ARTICLE * mainseq;            /* main chain of articles */
  104.   FILE  *   tlog;               /* debug file */
  105.   }  THREAD_ANCHOR;
  106.  
  107. #define   HASH_WIDTH  1023
  108.  
  109. static  const char *trivia[] = {
  110.   "THE",  "IN", "A", "OF",
  111.   "WITH", "TO", "BE", "IS", "FOR", "ON",
  112.   "RE:", "AN", "WAS:", "AND", "HOW"
  113.   };
  114. static const UINT numtriv = (sizeof(trivia)/sizeof(trivia[0]));
  115. /* called at completion of thread pass for the newsgroup */
  116. void thread_end( THREAD_ANCHOR * anch )
  117. {
  118.   ARTREF * warp, * warpn;
  119.  
  120. #ifdef DEBUG
  121.   fclose( anch->tlog );
  122. #endif
  123.  
  124.   warp = anch->headref;
  125.   while ( warp != NULL )
  126.      {
  127.      warpn = warp;
  128.      warp = warp->nextal;
  129.      free( warpn );
  130.      }
  131.   free( anch->subject_token_space );
  132.   free( anch );
  133.   return;
  134. }
  135.  
  136. /* valid token chars, binary 0 is invalid, \b is ignored
  137.    else it's the upper-case of char */
  138. static const char  sigchar[] = {
  139.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  140.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  141.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  142.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  143.   '\0', '\b', '\b', '\b',  '$' , '\b',  '&', '\b',
  144.   '\b', '\b', '\b', '\b', '\b' , '\b', '\0', '\b',  /* period is whitespace */
  145.    '0',  '1',  '2',  '3',  '4' ,  '5',  '6',  '7',
  146.    '8',  '9', '\0', '\b', '\b' , '\b', '\b', '\b',
  147.  
  148.   '\b',  'A',  'B',  'C',  'D' ,  'E',  'F',  'G',
  149.    'H',  'I',  'J',  'K',  'L' ,  'M',  'N',  'O',
  150.    'P',  'Q',  'R',  'S',  'T' ,  'U',  'V',  'W',
  151.    'X',  'Y',  'Z', '\b', '\b' , '\b', '\b', '\b',
  152.   '\b',  'A',  'B',  'C',  'D' ,  'E',  'F',  'G',
  153.    'H',  'I',  'J',  'K',  'L' ,  'M',  'N',  'O',
  154.    'P',  'Q',  'R',  'S',  'T' ,  'U',  'V',  'W',
  155.    'X',  'Y',  'Z', '\b', '\b' , '\b', '\b', '\0',
  156.  
  157.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  158.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  159.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  160.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  161.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  162.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  163.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  164.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  165.  
  166.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  167.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  168.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  169.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  170.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  171.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  172.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  173.   '\0', '\0', '\0', '\0', '\0' , '\0', '\0', '\0',
  174. };
  175.  
  176. /* obtain the next subject token
  177.    this involves upper-casing and removing any
  178.    punctuation
  179.    pos is where the current position in the output 'line'
  180.      is stored.
  181.    inp = current input position
  182.  
  183.    return hash value of token or -1 if end-of-line */
  184.  
  185. static int  nextokn( char ** inp, char **pos )
  186. {
  187.    char *cin, *cout, *hn;
  188.    char  ch;
  189.    UINT  hv = 0, hw = 0, cc = 0;
  190.  
  191.    cin = *inp; cout = *pos;
  192.    hn  = (char *)&hw;
  193.  
  194.    /* locate 1st significant char */
  195.    while ( ( *cin != '\0' ) && ( sigchar[*cin] <= '\b' ) )
  196.            cin++;
  197.    if ( *cin == '\0' )
  198.       return -1;
  199.  
  200.    /* process chars until white-space, uppercasing */
  201.    while ( ( *cin != '\0' ) && ( ( ch = sigchar[*cin] ) != '\0' ) )
  202.          {
  203.          if ( ch > '\b' )
  204.             {
  205.             cc++;
  206.             *hn   = ch;  hn++;
  207.             if  ( cc % sizeof(hv) == 0 )
  208.                 {  /* xor words together */
  209.                 hv ^= hw;  hn = (char *)&hw; hw = 0;
  210.                 }
  211.  
  212.             *cout = ch; cout++;
  213.             }
  214.          if ( cc == MAXTOKL )
  215.             break;
  216.          cin++;
  217.          }
  218.    *cout = '\0';
  219.    *inp = cin;
  220.    hv  ^= hw;
  221.    return hv % HASH_WIDTH;
  222. }
  223.  
  224.  
  225. /* free the hitlist and the new reference list */
  226. static void free_lists( HITENT * hp, NEWREF * nr )
  227. {
  228.    HITENT  *wh, *prvh;
  229.    NEWREF  *wr, *prvr;
  230.  
  231.    wh = hp;
  232.    while ( wh != NULL )
  233.      {
  234.      prvh = wh;
  235.      wh = wh->hpnext;
  236.      free( prvh );
  237.      }
  238.  
  239.    wr = nr;
  240.    while ( wr != NULL )
  241.      {
  242.      prvr = wr;
  243.      wr = wr->nrnext;
  244.      free( prvr );
  245.      }
  246. }
  247.  
  248. /* threading algorithm returns a pointer which it wants
  249.    passed to it with each  new subject line from the index */
  250. void * thread_init( void )
  251. {
  252.   THREAD_ANCHOR  * tmp_anch;
  253.   int   hv;
  254.   UINT  ix;
  255.   char  outt[80];
  256.   char  *op, *ip;
  257.   TOKEL *tsp, *tsw;
  258.   BOOL  found;
  259.  
  260.   tmp_anch = xmalloc( sizeof(THREAD_ANCHOR) );
  261.  
  262.   /* allocate subject token space */
  263.   tmp_anch->subject_token_space = xmalloc( sizeof(TOKEL) * (HASH_WIDTH+1)*2 );
  264.   tmp_anch->limit_addr = &(tmp_anch->subject_token_space[(HASH_WIDTH+1)*2]);
  265.   tmp_anch->next_ovflo = &(tmp_anch->subject_token_space[HASH_WIDTH]);
  266.   memset( tmp_anch->subject_token_space, 0, sizeof(TOKEL) * (HASH_WIDTH+1)*2 );
  267.   tmp_anch->mainseq = NULL;
  268.   tmp_anch->headref = NULL;
  269.  
  270.  
  271.   /* add the trivial tokens to the token space, marking them */
  272.   tsp = tmp_anch->subject_token_space;
  273.   op = &outt[0];
  274.   for ( ix = 0;  ix < numtriv; ix++ )
  275.       {
  276.       ip = (char *) trivia[ix];
  277.       hv = nextokn( &ip, &op );
  278.  
  279.       tsw = tsp + hv;
  280.       found = FALSE;
  281.       while  ( tsw->toktxt[0] != '\0' )
  282.         {
  283.         if ( strcmp( tsw->toktxt, outt ) == 0 )
  284.            {
  285.            found = TRUE;
  286.            break;
  287.            }
  288.         if ( tsw->overflow == NULL )
  289.            break;
  290.         tsw = tsw->overflow;
  291.         }
  292.  
  293.  
  294.       if ( !found )   /* ignore duplicates */
  295.          {
  296.          /* if this is a collision, allocate an overflow node */
  297.          if ( (tsp + hv)->toktxt[0] != '\0' )
  298.             {
  299.             tsw = tmp_anch->next_ovflo;
  300.             tmp_anch->next_ovflo++;
  301.             /* push the new overflow onto the primary */
  302.             tsw->overflow = (tsp + hv)->overflow;
  303.             (tsp + hv)->overflow = tsw;
  304.             }
  305.  
  306.          /* build a word node */
  307.          strcpy( tsw->toktxt, outt );
  308.          /* overflow and subhead should be NULL already */
  309.          tsw->trivial = TRUE;
  310.          }
  311.       } /* for each trivial string */
  312.  
  313. #ifdef DEBUG
  314.   tmp_anch->tlog = fopen("thread.log", "w" );
  315. #endif
  316.  
  317.   return tmp_anch;
  318. }
  319.  
  320.  
  321. /* called for each new subject line.
  322.    returns TRUE if it found a subject (ARTICLE) to thread-to,
  323.    FALSE if it had to allocate an ARTICLE.
  324.    'targ' is stored in all cases */
  325.  
  326. BOOL thread_compare( char * subjline, THREAD_ANCHOR * anch, ARTICLE **targ )
  327. {
  328.     char  *outp, *inp;
  329.     UINT   tcnt = 0;  /* token counter */
  330.     UINT   hcnt = 0;  /* hit counter */
  331.     int    hashv, hvalu;
  332.     TOKEL *tsp, *tsw;
  333.     BOOL   found;
  334.     ARTICLE *newa, *wap;
  335.     ARTREF  *wart;
  336.     HITENT  *hitanc,  /* tree anchor of hits for current subject */
  337.             *hitlist, /* one-way list anchor */
  338.             *hitw,    /* work ptr for hit searches */
  339.             **hitp;   /* ptr to previous ptr in search */
  340.     NEWREF  *anew,   /* anchor of new references for this entry */
  341.             *refw;   /* work ptr for new refs */
  342.     char   worka[257];  /* output work area for tokenizer */
  343.  
  344.     anew = NULL;
  345.     hitanc = NULL;
  346.     hitlist = NULL;
  347.     inp = subjline;      /* start of input string  */
  348.     outp = &(worka[0]);  /* output pointer start   */
  349.     memset ( outp, 0, sizeof(worka) );
  350.     tsp = anch->subject_token_space;
  351.  
  352.     /* obtain the next token */
  353.     while ( ( hashv = nextokn( &inp, &outp ) ) != -1 )
  354.       {
  355.       /* disregard trivial tokens */
  356.  
  357.       /* look up the token in the subject token space */
  358.       tsw = tsp + hashv;
  359.       found = FALSE;
  360.  
  361.       while  ( tsw->toktxt[0] != '\0' )
  362.         {
  363.         if ( strcmp( tsw->toktxt, outp ) == 0 )
  364.            {
  365.            found = TRUE;
  366.            break;
  367.            }
  368.         if ( tsw->overflow == NULL )
  369.            break;
  370.         tsw = tsw->overflow;
  371.         }
  372.  
  373.       if ( found )
  374.          {
  375.          if ( tsw->trivial )
  376.             continue;
  377.          }
  378.       else
  379.          {  /* not found */
  380.          /* if this is a collision, allocate an overflow node */
  381.          if ( (tsp + hashv)->toktxt[0] != '\0' )
  382.             {
  383.             tsw = anch->next_ovflo;
  384.             if ( tsw >= anch->limit_addr )
  385.                { /* allocate ARTICLE struct and exit */
  386.                 newa = xmalloc( sizeof(ARTICLE) );
  387.                 *targ = newa;
  388.                 return FALSE;
  389.                } /* cop out for too many tokens */
  390.             anch->next_ovflo++;
  391.             /* push the new overflow onto the primary */
  392.             tsw->overflow = (tsp + hashv)->overflow;
  393.             (tsp + hashv)->overflow = tsw;
  394.             }
  395.  
  396.          /* build a word node */
  397.          strcpy( tsw->toktxt, outp );
  398.          /* overflow and subhead should be NULL already */
  399.          tsw->trivial = FALSE;
  400.          /* push this on the new reference list */
  401.          refw = xmalloc( sizeof(NEWREF) );
  402.          refw->reftok = tsw;
  403.          refw->nrnext = anew;
  404.          anew = refw;
  405.          tcnt++;   /* count this token */
  406.          continue;
  407.          }
  408.  
  409.       /* push this on the new reference list -
  410.          this is done whether the token is known or not
  411.          in case this is a NEW thread.
  412.          If the token is already on list, skip it */
  413.       refw = anew;
  414.       while ( refw != NULL )
  415.         {
  416.         if ( refw->reftok == tsw )
  417.            break;
  418.         refw = refw->nrnext;
  419.         }
  420.       if ( ( refw != NULL ) && ( refw->reftok == tsw ) )
  421.          continue;
  422.       refw = xmalloc( sizeof(NEWREF) );
  423.       refw->reftok = tsw;
  424.       refw->nrnext = anew;
  425.       anew = refw;
  426.       /* count this token */
  427.       tcnt++;
  428.  
  429.       /* we found the token, scan thru the attached ARTICLEs and
  430.          merge pointers to them into the hit tree */
  431.  
  432.       wart = tsw->subhead;
  433.       while ( wart != NULL )
  434.          {
  435.          hitw = hitanc; hitp = NULL;
  436.          while ( ( hitw != NULL ) && ( hitw->subjp != wart->thread ) )
  437.            {
  438.            if ( wart->thread > hitw->subjp )
  439.               {
  440.               hitp = &hitw->hpleft;
  441.               hitw = hitw->hpleft;
  442.               }
  443.            else
  444.               {
  445.               hitp = &hitw->hpright;
  446.               hitw = hitw->hpright;
  447.               }
  448.            }
  449.          if ( hitw == NULL )
  450.             { /* add new tree entry */
  451.             hitw = xmalloc( sizeof(HITENT) );
  452.             /* link into one-way list */
  453.             hitw->hpnext = hitlist;  hitlist = hitw;
  454.             /* if no previous node, set anchor, else store
  455.                this element's ptr in correct branch of previous */
  456.             if ( hitp == NULL ) hitanc = hitw;
  457.             else *hitp = hitw;
  458.             hitw->subjp = wart->thread;
  459.             hitw->hpleft = hitw->hpright = NULL;
  460.             hitw->nhits = 0;
  461.             }
  462.  
  463.          hitw->nhits++;  /* increment hits */
  464.  
  465.          wart = wart->nextar;
  466.          }
  467.  
  468.       } /* while tokens */
  469.  
  470.  
  471.     /* search the hit tree as a list for the highest count
  472.        within a similarly tokenized article */
  473.     hitw = hitlist;  wap = NULL;  hvalu = 0;
  474.     while ( hitw != NULL )
  475.       {
  476.       int hweight;
  477.       hweight = hitw->nhits - (abs((int)hitw->subjp->left - tcnt));
  478.       if ( hweight > hvalu )
  479.          {
  480.          hvalu = hweight;
  481.          hcnt = hitw->nhits;
  482.          wap = hitw->subjp;  /* save associated ARTICLE */
  483.          }
  484.       hitw = hitw->hpnext;
  485.       }
  486.  
  487.  
  488.     found = FALSE;
  489.     if ( wap != NULL )
  490.        {
  491.        int    mcnt;
  492.  
  493.        /* retrieve the saved token count of the previous
  494.           subject line with highest hit count (hcnt) */
  495.        mcnt = (int)wap->left;
  496.  
  497.        /* if the current token count is 3 or less:
  498.              all tokens must match (order irrelevant).
  499.           else
  500.              the saved token count must be within  1 of the number
  501.              of hits in the current subject. */
  502.  
  503.        if ( tcnt <= 3 )
  504.           {
  505.           if ( ( hcnt == mcnt ) && ( tcnt == mcnt ) )
  506.              found = TRUE;
  507.           }
  508.        else
  509.        if ( abs(mcnt - hcnt) < 2 )
  510.            found = TRUE;
  511.        else
  512.        if ( ( hcnt > 5 ) && ( abs(mcnt - hcnt) < 3 ) )
  513.            found = TRUE;
  514.        }
  515.  
  516.     /* see if we have enough tokens to be a match */
  517.     if ( found )
  518.        { /* subject to be threaded to a previous ARTICLE */
  519. #ifdef DEBUG
  520.        fprintf( anch->tlog,
  521.         "match: %s\n %s\n hcnt: %d tcnt %d\n", subjline, wap->header, hcnt, tcnt );
  522. #endif
  523.        *targ = wap;  /* previous article */
  524.        free_lists( hitlist, anew );
  525.        return TRUE;
  526.        }
  527.     else
  528.        {
  529.        /* this is a 'new' thread */
  530. #ifdef DEBUG
  531.        fprintf(anch->tlog, "new: %s hcnt: %d tcnt %d\n", subjline, hcnt, tcnt );
  532. #endif
  533.        newa = xmalloc( sizeof(ARTICLE) );
  534.        /* main program will fill in ARTICLE, but not
  535.           modify 'left' or 'right' */
  536.        newa->left = (ARTICLE *)tcnt;  /* save token count */
  537.        *targ = newa;
  538.        if ( anch->mainseq == NULL )
  539.           anch->mainseq = newa;
  540.        /* queue the new ARTICLE to its word nodes */
  541.        refw = anew;
  542.        while ( refw != NULL )
  543.          {
  544.          wart = xmalloc( sizeof(ARTREF) );
  545.          wart->thread = newa;
  546.          wart->nextal = anch->headref;
  547.          anch->headref = wart;
  548.          wart->nextar = refw->reftok->subhead;
  549.          refw->reftok->subhead = wart;
  550.          refw = refw->nrnext;
  551.          }
  552.  
  553.        free_lists( hitlist, anew );
  554.        return FALSE;
  555.        }
  556.  
  557. }
  558.  
  559.