home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume26 / agrep-2.01 / part02 / mgrep.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-08  |  8.2 KB  |  330 lines
  1. /* Copyright (c) 1991 Sun Wu and Udi Manber.  All Rights Reserved. */
  2. /* multipattern matcher */
  3. #include <stdio.h>
  4. #define MAXPAT  256
  5. #define MAXLINE 1024
  6. #define MAXSYM  256
  7. #define MAXMEMBER1 4096
  8. #define MAXPATFILE 260000
  9. #define BLOCKSIZE  8192
  10. #define MAXHASH    8192
  11. #define mm        8191
  12. #define max_num    30000  
  13. #define W_DELIM       252
  14. #define L_DELIM    10 
  15.  
  16. extern COUNT, FNAME, SILENT, FILENAMEONLY, num_of_matched;
  17. extern INVERSE;
  18. extern WORDBOUND, WHOLELINE, NOUPPER;
  19. extern unsigned char  CurrentFileName[], Progname[]; 
  20. extern total_line;
  21.  
  22. int LONG  = 0;
  23. int SHORT = 0;
  24. int p_size=0;
  25. unsigned char SHIFT1[MAXMEMBER1];
  26. unsigned char tr[MAXSYM];
  27. unsigned char tr1[MAXSYM];
  28. struct pat_list {
  29.     int  index;
  30.     struct pat_list *next;
  31. } *HASH[MAXHASH];
  32. struct pat_list  *pt, *qt;
  33. unsigned char buf[MAXPATFILE+BLOCKSIZE];
  34. unsigned char pat_spool[MAXPATFILE+2*max_num+MAXPAT];
  35. unsigned char *patt[max_num];
  36. unsigned char pat_len[max_num];
  37.  
  38.  
  39. prepf(fp)
  40. int fp;
  41. {
  42.     int length=0, i, p=1, pdx=0, num_pat;
  43.     unsigned char *pat_ptr=pat_spool, temp[10];
  44.     unsigned Mask = 15;
  45.     int num_read;
  46.  
  47.     while((num_read = read(fp, buf+length, BLOCKSIZE)) > 0) {
  48.     length = length + num_read;
  49.     if(length > MAXPATFILE) {
  50.         fprintf(stderr, "%s: maximum pattern file size is %d\n", Progname, MAXPATFILE);
  51.         exit(2);
  52.     }
  53.     }
  54.     buf[length] = '\n';
  55.     i = 0; p=1;
  56.     while(i<length) {
  57.     patt[p] = pat_ptr;
  58.     if(WORDBOUND) *pat_ptr++ = W_DELIM;
  59.     if(WHOLELINE) *pat_ptr++ = L_DELIM;
  60.     while((*pat_ptr = buf[i++]) != '\n') pat_ptr++;
  61.     if(WORDBOUND) *pat_ptr++ = W_DELIM;
  62.     if(WHOLELINE) *pat_ptr++ = L_DELIM;           /* Can't be both on */
  63.     *pat_ptr++ = 0;
  64.     p++;  
  65.     }
  66.     if(p>max_num) {
  67.     fprintf(stderr, "%s: maximum number of patterns is %d\n", Progname, max_num); 
  68.     exit(2);
  69.     }
  70.     for(i=1; i<20; i++) *pat_ptr = i;  /* boundary safety zone */
  71.     for(i=0; i< MAXSYM; i++) tr[i] = i;
  72.     if(NOUPPER) {
  73.     for(i='A'; i<= 'Z'; i++) tr[i] = i + 'a' - 'A';
  74.     }
  75.     if(WORDBOUND) {
  76.     tr['\n'] = tr['\t'] = tr[' '] = tr[','] = tr[';'] = tr[':'] = W_DELIM;
  77.         tr['!'] = tr['"'] = tr['?'] = tr['<'] = tr['>'] = W_DELIM;
  78.     tr['='] = tr['['] = tr[']'] = W_DELIM; 
  79.         tr['('] = tr[')'] = tr['$'] = tr['/'] = tr['\\'] = W_DELIM;
  80.     }
  81.     for(i=0; i< MAXSYM; i++) tr1[i] = tr[i]&Mask;
  82. #ifdef DEBUG
  83.   for(i=1; i<p; i++) printf("%s\n", patt[i]); fflush(stdout);
  84.   printf("\n\n");
  85. #endif
  86.     num_pat = p-1;
  87.     p_size = MAXPAT;
  88.     for(i=1 ; i <= num_pat; i++) {
  89.     p = strlen(patt[i]);
  90.     pat_len[i] = p;
  91.     if(p!=0 && p < p_size) p_size = p;
  92.     }
  93.     if(p_size == 0) {
  94.     fprintf(stderr, "%s: the pattern file is empty\n");
  95.     exit(2);
  96.     }
  97.     if(length > 400 && p_size > 2) LONG = 1;
  98.     if(p_size == 1) SHORT = 1;
  99.     for(i=0; i<MAXMEMBER1; i++) SHIFT1[i] = p_size - 2;
  100.     for(i=0; i<MAXHASH; i++) {
  101.     HASH[i] = 0;
  102.     }
  103.     for(i=1; i<= num_pat; i++) f_prep(i, patt[i]);
  104. }
  105.  
  106.  
  107. mgrep(fd)
  108. int fd;
  109. { 
  110.     register char r_newline = '\n';
  111.     unsigned char text[2*BLOCKSIZE+MAXLINE]; 
  112.     register int buf_end, num_read, i=0, j, start, end, residue = 0;
  113.  
  114.     text[MAXLINE-1] = '\n';  /* initial case */
  115.     start = MAXLINE-1;
  116.  
  117.     while( (num_read = read(fd, text+MAXLINE, BLOCKSIZE)) > 0) 
  118.     {
  119.        if(INVERSE && COUNT) countline(text+MAXLINE, num_read);
  120.        buf_end = end = MAXLINE + num_read -1 ;
  121.        while(text[end]  != r_newline && end > MAXLINE) end--;
  122.        residue = buf_end - end  + 1 ;
  123.        text[start-1] = r_newline;
  124.        if(SHORT) m_short(text, start, end);
  125.        else      monkey1(text, start, end);
  126.        if(FILENAMEONLY && num_of_matched) {
  127.         printf("%s\n", CurrentFileName);
  128.         return;
  129.        }
  130.        start = MAXLINE - residue;
  131.        if(start < 0) {
  132.             start = 1; 
  133.        }
  134.        strncpy(text+start, text+end, residue);
  135.     } /* end of while(num_read = ... */
  136.     text[MAXLINE] = '\n';
  137.     text[start-1] = '\n';
  138.     if(residue > 1) {
  139.         if(SHORT) m_short(text, start, end);
  140.         else      monkey1(text, start, end);
  141.     }
  142.     return;
  143. } /* end mgrep */
  144.  
  145. countline(text, len)
  146. unsigned char *text; int len;
  147. {
  148. int i;
  149.     for (i=0; i<len; i++) if(text[i] == '\n') total_line++;
  150. }
  151.  
  152.  
  153. monkey1( text, start, end  ) 
  154. int start, end; register unsigned char *text;
  155. {
  156. register unsigned char *textend;
  157. register unsigned hash, i;
  158. register unsigned char shift; 
  159. register int  m1, j, Long=LONG; 
  160. int pat_index, m=p_size; 
  161. int MATCHED=0;
  162. register unsigned char *qx;
  163. register struct pat_list *p;
  164. unsigned char *lastout;
  165. int OUT=0;
  166.  
  167. textend = text + end;
  168. m1 = m - 1;
  169. lastout = text+start+1;
  170. text = text + start + m1 ;
  171. while (text <= textend) {
  172.     hash=tr1[*text];
  173.     hash=(hash<<4)+(tr1[*(text-1)]);
  174.     if(Long) hash=(hash<<4)+(tr1[*(text-2)]);
  175.     shift = SHIFT1[hash];
  176.     if(shift == 0) {
  177.         hash=0;
  178.         for(i=0;i<=m1;i++)  {
  179.             hash=(hash<<4)+(tr1[*(text-i)]);
  180.         }
  181.         hash=hash&mm;
  182.         p = HASH[hash];
  183.         while(p != 0) {
  184.             pat_index = p->index;
  185.             p = p->next;
  186.             qx = text-m1;
  187.             j = 0;
  188.             while(tr[patt[pat_index][j]] == tr[*(qx++)]) j++;
  189.                 if (j > m1 ) { 
  190.                if(pat_len[pat_index] <= j) {
  191.                 if(text > textend) return;
  192.                         num_of_matched++;
  193.                         if(FILENAMEONLY || SILENT)  return;
  194.                 MATCHED=1;
  195.                     if(COUNT) {
  196.                       while (*text != '\n') text++;
  197.                 }
  198.                 else {
  199.                     if(!INVERSE) {
  200.                       if(FNAME) printf("%s: ",CurrentFileName);
  201.                                   while(*(--text) != '\n');
  202.                                   while(*(++text) != '\n') putchar(*text);
  203.                       printf("\n");
  204.                     }
  205.                     else {
  206.                       if(FNAME) printf("%s: ",CurrentFileName);
  207.                                   while(*(--text) != '\n');
  208.                     if(lastout < text) OUT=1;
  209.                     while(lastout < text) putchar(*lastout++);
  210.                     if(OUT) {
  211.                         putchar('\n');
  212.                         OUT=0;
  213.                     }
  214.                                   while(*(++text) != '\n');
  215.                     lastout=text+1;
  216.                     }
  217.                 }
  218. /*
  219.                 else {
  220.                       if(FNAME) printf("%s: ",CurrentFileName);
  221.                                   while(*(--text) != '\n');
  222.                                   while(*(++text) != '\n') putchar(*text);
  223.                       printf("\n");
  224.                 }
  225. */
  226.                }
  227.                     }
  228.             if(MATCHED) break;
  229.         }
  230.         if(!MATCHED) shift = 1;
  231.         else {
  232.             MATCHED = 0;
  233.             shift = m1;
  234.         }
  235.         }
  236.     text = text + shift;
  237.   }
  238.   if(INVERSE && !COUNT) while(lastout <= textend) putchar(*lastout++);
  239. }
  240.  
  241. m_short( text, start, end  ) 
  242. int start, end; register unsigned char *text;
  243. {
  244. register unsigned char *textend;
  245. register unsigned i; 
  246. register int  j; 
  247. register struct pat_list *p, *q;
  248. register int pat_index; 
  249. int MATCHED=0;
  250. int OUT=0;
  251. unsigned char *lastout;
  252. unsigned char *qx;
  253.  
  254. textend = text + end;
  255. lastout = text + start + 1;
  256. text = text + start - 1 ;
  257. while (++text <= textend) {
  258.         p = HASH[*text];
  259.         while(p != 0) {
  260.             pat_index = p->index;
  261.             p = p->next;
  262.             qx = text;
  263.             j = 0;
  264.             while(tr[patt[pat_index][j]] == tr[*(qx++)]) j++;
  265.             if(pat_len[pat_index] <= j) {
  266.                 if(text >= textend) return;
  267.                         num_of_matched++;
  268.                         if(FILENAMEONLY || SILENT)  return;
  269.                     if(COUNT) {
  270.                       while (*text != '\n') text++;
  271.                 }
  272.                 else {
  273.                       if(FNAME) printf("%s: ",CurrentFileName);
  274.                     if(!INVERSE) {
  275.                                   while(*(--text) != '\n');
  276.                                   while(*(++text) != '\n') putchar(*text);
  277.                       printf("\n");
  278.                     MATCHED = 1;
  279.                     }
  280.                     else {
  281.                                   while(*(--text) != '\n');
  282.                     if(lastout < text) OUT=1;
  283.                     while(lastout < text) putchar(*lastout++);
  284.                     if(OUT) {
  285.                         putchar('\n');
  286.                         OUT=0;
  287.                     }
  288.                                   while(*(++text) != '\n');
  289.                     lastout=text+1;
  290.                     MATCHED = 1;
  291.                     }
  292.                 }
  293.                     }
  294.             if(MATCHED) break;
  295.         }
  296.         MATCHED = 0;
  297.   } /* while */
  298.   if(INVERSE && !COUNT) while(lastout <= textend) putchar(*lastout++);
  299. }
  300.  
  301. f_prep(pat_index, Pattern)
  302. unsigned char *Pattern ; int pat_index;
  303. {
  304. int i, j, m;
  305. register unsigned hash, Mask=15;
  306.     m = p_size;
  307.     for (i = m-1; i>=(1+LONG); i--) {
  308.         hash = (Pattern[i] & Mask);
  309.         hash = (hash << 4) + (Pattern[i-1]& Mask);
  310.         if(LONG) hash = (hash << 4) + (Pattern[i-2] & Mask);
  311.         if(SHIFT1[hash] >= m-1-i) SHIFT1[hash] = m-1-i;
  312.     }
  313.     if(SHORT) Mask = 255;  /* 011111111 */
  314.     hash = 0;
  315.     for(i = m-1; i>=0; i--)  {
  316.         hash = (hash << 4) + (tr[Pattern[i]]&Mask);
  317.     }
  318. /*
  319.     if(INVERSE) hash = Pattern[1];
  320. */
  321.     hash=hash&mm;
  322.     qt = (struct pat_list *) malloc(sizeof(struct pat_list));
  323.     qt->index = pat_index;
  324.     pt = HASH[hash];
  325.     qt->next = pt;
  326.     HASH[hash] = qt;
  327. }
  328.  
  329.  
  330.