home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume25 / classify / classify.c < prev    next >
C/C++ Source or Header  |  1992-02-28  |  17KB  |  564 lines
  1.  
  2. /*
  3.  * `classify':  Sort files into groups by content
  4.  * Copyright (C) 1991  Mark-Jason Dominus.  All rights reserved.
  5.  *
  6.  * This program is free software; you can redistribute it and/or modify
  7.  * it under the terms of the GNU General Public License as published by
  8.  * the Free Software Foundation; either version 1, or (at your option)
  9.  * any later version.
  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.  * You should have received a copy of the GNU General Public License
  17.  * along with this program; if not, write to the Free Software
  18.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19.  */
  20.  
  21. #include <stdio.h>
  22. #include <ctype.h>
  23. #include <string.h>
  24.  
  25.   /* Return codes from `compare()' and macros for handling them. */
  26. #define SAME 1
  27. #define DIFFERENT 0
  28. #define BADFILE1 4
  29. #define BADFILE2 8
  30. #define BADFILEBOTH (BADFILE1 | BADFILE2)
  31. #define ERROR(RC) ((RC != SAME) && (RC != DIFFERENT))
  32.  
  33. /* Allocate a new object and return a pointer to it. */
  34. #define NEW(type) ((type *) malloc(sizeof(type)))
  35.  
  36. /* Are strings a and b equal?  ('equal', not 'eq') */
  37. #define STREQ(a,b) (strcmp((a),(b)) == 0)
  38.  
  39. /* Flags set by command-line options. */
  40. int foldflag = 0, blankflag = 0, whiteflag = 0;
  41.  
  42. /* Format option and codes. */
  43. char formopt = 's';
  44.  
  45. /* Explanation of data structure used in this program:
  46.  
  47.    Each 'masternode'is a linked list of filenames.  The filenames in each
  48.    masternode are the names of files that are identical, modulo some
  49.    whitespace and upper/lower-case distinctions.
  50.  
  51.    The masternodes are linked together in a linked list called `list'.
  52.  
  53.    Example:
  54.    
  55.    list
  56.    |
  57.    V          data            next           next 
  58.    masternode------>filenode------->filenode------>NULL
  59.    |                  |               |
  60.    | next             | data          | data
  61.    |                  V               V
  62.    |               filename1         filename2
  63.    |
  64.    V          data           next 
  65.    masternode------>filenode------>NULL
  66.    |                  |
  67.    | next             | data
  68.    |                  V
  69.    V               filename3
  70.    NULL
  71.  
  72.    This would represent three files: filename1, filename2, and filename3,
  73.    of which filename1 and filename2 had the same contents, and filename3
  74.    was different from both.
  75.  
  76.    Note:  if j is a pointer to a masternode, then j->data->data is the
  77.    first filename in j's masternode.
  78.    */
  79.    
  80. typedef struct s_fnode {
  81.   char *data;
  82.   struct s_fnode *next;
  83. } filenode;
  84.  
  85. typedef struct s_mnode {
  86.   filenode *data;
  87.   struct s_mnode *next;
  88. } masternode;
  89.  
  90. main(argc,argv)
  91.      int argc;
  92.      char *argv[];
  93. {
  94.   /* Look at these absurd declarations! */
  95.   int i, compare(), match, numfileargs, parseargs();
  96.   void usage(), mappend(), fappend();
  97.   masternode *list, *j, *mnew, *newmasternode();
  98.   filenode *fnew, *k, *newfilenode();
  99.   FILE *checkit;
  100.   /* Didn't anyone ever tell you it wasn't polite to point? */
  101.  
  102.   /* Parse the arguments and obliterate switch options like `-f'. */
  103.   numfileargs = parseargs(argc,argv);
  104.   /* Anything that survives obliteration is assumed to be a filename. */
  105.  
  106.   /* No, no--what is the good of comparing only one file? */
  107.   if (numfileargs < 2) usage(argv[0]);
  108.  
  109.   /* Find the name of the first file on the command line. */
  110.   for (i=1; argv[i] == NULL; i++) ;
  111.  
  112.   /* This program has two essentially separate functions.
  113.    * One is to take a list of files and group identical ones.
  114.    * The other is to see which of files 2...n are identical to
  115.    * file 1.
  116.    *
  117.    * If you specify -m or -M, you get the second
  118.    * functionality. Otherwise, you get the first.
  119.    *
  120.    * What follows right here is the second functionality.
  121.    */
  122.  
  123.   if (formopt == 'm' || formopt == 'M') {
  124.  
  125.     /* The first file the user named is the one to check the others against.
  126.      */
  127.     char *master = argv[i];    
  128.     
  129.     /* If the user said '-M', echo the name of the master 
  130.      * file; if not, suppress it. */
  131.     if (formopt == 'M')
  132.       printf("%s\n",master);
  133.     
  134.     for (i += 1; i<argc; i++) {
  135.       if (argv[i] == NULL) continue;
  136.  
  137.       /* If for some reason the name of the master file appears more than
  138.      once on the command line, suppress it. (This happens all the time
  139.      in shell scripts.)
  140.      */
  141.       if (STREQ(argv[i], master)) continue;
  142.               
  143.       match = compare(master, argv[i]);
  144.       if (match == SAME)
  145.     printf("%s\n", argv[i]);
  146.       /* If `match' was an error return, `compare()' printed an error */
  147.       /* message for us and we need do nothing special. */
  148.     }
  149.  
  150.     exit(0); /* This part of the program can't fail. */
  151.   }
  152.  
  153.   /* If we're here, then the user didn't select -m or -M, and we
  154.      do the normal thing, which is to look at all the files and sort them
  155.      into groups.
  156.      */
  157.  
  158.   /* This next bit of code catches a peculiar bug: If it were not here, and
  159.      if we couldn't open the first file named on the command line, we would
  160.      put it into the linked list anyway (list->data->data = argv[i]) and
  161.      subsequent files would get checked against it, yielding many error
  162.      messages, much wasted time, and erroneous output--there would be a
  163.      `Class 1' with the bad file alone in it.
  164.  
  165.      Putting in this check allows us to make much simpler
  166.      list-initialization code.  I hate writing special-case code for
  167.      starting off linked lists!
  168.      */
  169.   while (((checkit = fopen(argv[i],"r")) == NULL) &&
  170.      i < argc)
  171.     fprintf(stderr, "Couldn't open file %s.\n", argv[i++]);
  172.   fclose(checkit);
  173.  
  174.   if (i == argc) exit(0); /* Couldn't read *any* of the input files. */
  175.  
  176.   /* Initialize linked lists */
  177.   list = newmasternode();
  178.   list->data->data = argv[i];
  179.   /* Wasn't that simple?  Told you so. */
  180.   
  181.   for (i += 1; i < argc; i++) { /* Loop through filenames... */
  182.     if (argv[i] == NULL) continue; /* ... skipping nulls ... */
  183.     match = DIFFERENT;
  184.     j=list; 
  185.     do {
  186.       /* ... matching the current file with the file at the head of each */
  187.       /* class-list ... */
  188.       match = compare(argv[i], j->data->data); 
  189.       if (match == DIFFERENT) j = j->next; 
  190.       /* ... until we run out of class lists or find a match or an error. */
  191.     } while (j && (match == DIFFERENT)); 
  192.  
  193.     /* Now, if there was an error, then... */
  194.     if (ERROR(match)) {
  195.       /* ... I hope it was in the current file--that's no problem; we just
  196.      obliterate it from the list of files to check, and move on, but...
  197.      */
  198.       if ((match & BADFILE1) == BADFILE1) {
  199.     argv[i] = NULL;
  200.     continue;
  201.       }
  202.       /* ... if the problem was with the file in the class list, I am very
  203.      upset, because it _was_ okay when I put it into the list.
  204.      (I have violated Steinbach's Guideline for Systems Programming:
  205.      ``Never test for an error condition you don't know how to
  206.      handle.''  But actually I could handle this; we could delete the
  207.      bogus file from the class-list in which it appears.  This is a lot
  208.      of work and it will happen only very rarely and in bizarre
  209.      circumstances, so I choose not to bother.  So sue me.
  210.      */
  211.       else if ((match & BADFILE2) == BADFILE2) {
  212.     fprintf(stderr,"WARNING:\tSomething went wrong with file %s\n",
  213.         j->data->data);
  214.     fprintf(stderr,"since the last time I looked at it.\n");
  215.     /* Yes, Virginia, this is correct behavior. */
  216.       }
  217.     }
  218.  
  219.     /* Okay, there was no error, but the current file was *not* like
  220.        any of the ones we've seen so far.  Make a new classification and
  221.        put the current filename into it.
  222.        */
  223.     else if (match == DIFFERENT) {
  224.       mnew = newmasternode();
  225.       mnew->data->data = argv[i];
  226.       mappend(list,mnew);
  227.     }
  228.     /* Ah, we found a match--the current file is identical to the ones in */
  229.     /* the classification j->data. */
  230.     else {
  231. #ifdef DEBUG
  232.       fprintf(stderr, "%s matched %s.\n", argv[i], j->data->data);
  233. #endif
  234.       fnew = newfilenode();
  235.       fnew->data = argv[i];
  236.       fappend(j->data, fnew);
  237.     }
  238.   } /* for (i += 1; ... ) */
  239.  
  240.   /* We are out of the main loop and all the files have been handled,
  241.      one way or another.  Now it is time to spit out the output.
  242.      */
  243.  
  244.   /* `formopt' is '1' if the user selected the `-1' option.  It means 
  245.    * that the proram should not do the default thing, which is to make a 
  246.    * nice long report of who matched whom, but rather should just dump out 
  247.    * a list of files each of which represents exactly one of the classes. */
  248.   if (formopt == '1') {
  249.     for (j=list; j; j=j->next)
  250.       printf("%s\n", j->data->data);
  251.   }
  252.   /* `formopt' is 's' if the user selected the '-s' option.  That 
  253.    * means that the program should make a short, awkable kind of
  254.    * output, with one line per class, filenames separated by a single
  255.    * space.  Note that we do not number the lines.  (I almost had it
  256.    * number the lines.)  The idea is that if the user wanted the lines
  257.    * numbered, they would pipe the output through 'cat -n'. */
  258.   else if (formopt == 's') {
  259.     for (j=list; j; j=j->next) {
  260.       for (k = j->data; k; k=k->next) 
  261.     printf("%s ", k->data);
  262.       printf("\n");
  263.     }
  264.   }
  265.   /* Here we make the nice long report. The temptation to add many
  266.      bells and whistles and have the program accept a format-specification
  267.      string and so on is very tempting, but I will not give in to foolish
  268.      creeping featurism.  At least, not any more than I already have.
  269.      Actually, a short-form option, the puts the output in the form
  270.              1 foo.c bar.c baz.c la.c
  271.          2 la de da oakum yokum
  272.          3 cruft FOCUS
  273.          4 adventure
  274.      might be very useful, because as it is you can't really feed this
  275.      program's output to AWK in a reasonable way.
  276.      */
  277.   /* Note added in proof:  I gave in to creeping featurism.  See the 
  278.    * '-s' option.  Sigh.  At least I did not make it number the lines. */
  279.   else {
  280.     for (j=list, i=1; j; j=j->next, i++) {
  281.       printf("\nClass %d:\n",i);
  282.       for (k = j->data; k; k=k->next) {
  283.     printf("\t%s\n",k->data);
  284.       }
  285.     }
  286.   }
  287.    
  288.   exit(0); /* Au 'voir! */
  289. }
  290.  
  291. /* This next `compare' routine is what I used to do, but there are good
  292.    reasons for not using either diff(1) or cmp(1): 
  293.  
  294.    1.  Do not use diff(1) because it is too intelligent (intelligent ->
  295.    slow.)  Diff tells you where the files differ and that is not what we
  296.    want--we just want to know if they are different or not.
  297.  
  298.    2.  Do not use cmp(1) because we want to use this program for comparing
  299.    things like /etc/rc.local and /etc/motd which are very likely to differ
  300.    only in a few whitespaces, and we want this program to report that such
  301.    files are identical, even though cmp says they're not.
  302.  
  303.    Maybe UNIX needs a nice, simple, flexible file-compare utility?  Naah,
  304.    you can always string awk and sed and things onto the front of cmp.  But
  305.    that's too slow for us here.
  306.    */
  307.  
  308. /* Do not do this:
  309.   int  
  310.   compare(path1,path2)
  311. char *path1, *path2;
  312. {
  313.   char compare[1024];
  314.  
  315.   sprintf(compare,"cmp -s %s %s",path1,path2); 
  316.   sprintf(compare,"diff -w %s %s > /dev/null 2>&1",path1,path2); 
  317.   return((system(compare) >> 8 == 0) ? SAME : DIFFERENT );
  318. }
  319. */
  320.  
  321. /* So this is what we do instead. */
  322.  
  323. int
  324.   compare(path1, path2)
  325. char *path1, *path2;
  326. {
  327.   FILE *file1, *file2;
  328.   int c1,c2;
  329.  
  330.   if ((file1 = fopen(path1,"r")) == NULL) {
  331.     fprintf(stderr, "Couldn't open file %s.\n", path1);
  332.     return(BADFILE1);
  333.   }
  334.   if ((file2 = fopen(path2,"r")) == NULL) {
  335.     fprintf(stderr, "Couldn't open file %s.\n", path2);
  336.     return(BADFILE2); /* For symmetry, even though this program will become
  337.              quite irate if `compare' ever returns this code.
  338.              */
  339.   }
  340.  
  341.   do {
  342.     do {
  343.       c1 = getc(file1);
  344.       /* You may need to make a Karnaugh map to understand this termination
  345.      condition, but it essentially means to ignore the right white spaces
  346.      if the right option flags are set, and I have tested it for you,
  347.      so you may assume it is doing the thing that the man page says it
  348.      does.
  349.      */
  350.     } while (! ((!blankflag && !whiteflag) ||
  351.         ((c1 != ' ' && c1 != '\t') && (c1 != '\n'  || !whiteflag)))
  352.          ) ;
  353.     do {
  354.       c2 = getc(file2);
  355.     } while (! ((!blankflag && !whiteflag) || /* Ditto */
  356.         ((c2 != ' ' && c2 != '\t') && (c2 != '\n'  || !whiteflag)))
  357.          ) ;
  358.  
  359.     /* Fold case if requested with `-f' flag. */
  360.     if (foldflag) {
  361.       c1 = (isupper(c1) ? tolower(c1) : c1);
  362.       c2 = (isupper(c2) ? tolower(c2) : c2);
  363.     }
  364.     
  365.     if (c1 != c2) {
  366.       fclose(file1);
  367.       fclose(file2);
  368.       return DIFFERENT;
  369.     }
  370.  
  371.   } while (c1 != EOF && c2 != EOF);
  372.  
  373.   fclose(file1);
  374.   fclose(file2);
  375.  
  376.   /* If we're here, then both files were identical and we tapped out at */
  377.   /* least one of them.  If we tapped out both, they really are identical. */
  378.   /* If, on the other hand, only one is finished, then it is a strict */
  379.   /* prefix of the other and so the two files are *not* the same. */
  380.   if (c1 == EOF && c2 == EOF)
  381.     return SAME;
  382.   else
  383.     return DIFFERENT;
  384. }
  385.  
  386. /* Nyahh nyah!  User is a big stupid-head! */
  387. void
  388.   usage(progname)
  389. char *progname;
  390. {
  391.   char *tail;
  392.   tail = strrchr(progname,'/');
  393.  
  394.   if (tail) progname = tail+1;
  395.   fprintf(stderr,"Usage:\t %s [-1 | -s | -l | -m | -M] [-f] [-b | -w]\n",progname);
  396.   fprintf(stderr,"\tfile1 file2 [...]\n");
  397.   fprintf(stderr,"\n\nTry %s -h\t for help.\n", progname);
  398.   exit(-1);
  399. }
  400.  
  401. /* I put this here 'cause I didn't want to write a man page. Duuhhhhh. */
  402. void
  403.   help()
  404. {
  405.   fprintf(stderr,"Classify: Examine and group identical files.\n\n");
  406.   fprintf(stderr,"Flags:\n\t-f\tFold case in file comparisions.\n");
  407.   fprintf(stderr,"\t-b\tIgnore blanks and TABs in file comparisions.\n");
  408.   fprintf(stderr,"\t-w\tIgnore all whitespace in file comparisions.\n");
  409.   fprintf(stderr,"\t-1\tPrint the name of only one file from each class.\n");
  410.   fprintf(stderr,"\t-l\tPrint  long-format output (default).\n");
  411.   fprintf(stderr,"\t-s\tPrint short-format output.\n");
  412.   fprintf(stderr,"\t-M\tPrint only names of files that match first file named.\n");
  413.   fprintf(stderr,"\t-m\tLike -M, but suppress first filename.\n");
  414.   return;
  415. }
  416.  
  417. /* Parse the args and set the flags.
  418.    We want the argument list to be free-form so you can mix filenames and
  419.    options. That is because I am a masochist.  So to save trouble, we just
  420.    obliterate the flag arguments by setting them to NULL, and then we have
  421.    the main routine ignore NULL arguments if it sees any.  Programmers who
  422.    say `but then you can't tell when you've reached the end of the arg list
  423.    because it is supposed to be a NULL-terminated array!' get a boot to the
  424.    head. 
  425.  
  426.    Returns the number of non-flag arguments.
  427.    */
  428.    
  429. int
  430.   parseargs(argc,argv)
  431. int argc;
  432. char *argv[];
  433. {
  434.   int i, j, numnonflags = argc-1;
  435.   void usage(), help();
  436.  
  437.   for (i=1; i<argc; i++) {
  438.     if (argv[i][0] != '-') continue;
  439.     numnonflags -= 1;
  440.     if (argv[i][1] == '\0') {  /* If flag is "-", stop parsing args */
  441.       /* Probably `-' should mean to read the stdin.  I will put in
  442.      that feature three days after next tishabov.
  443.  
  444.      (Translation for gentiles:  I will put the feature in on the
  445.      fourth Thursday of next week. )
  446.      */
  447.       argv[i] = NULL;
  448.       return numnonflags;
  449.     }
  450.     for (j=1; argv[i][j]; j++) {
  451.       switch (argv[i][j]) {
  452.       case '-': /* If flag is "--", stop parsing args */
  453.     if (j==1) {
  454.       argv[i] = NULL;
  455.       return;
  456.     } /* Else we got a flag like -f-w, so ignore the second "-" sign. */
  457.     break;
  458.       case 'f':
  459.     foldflag = 1;
  460.     break;
  461.       case 'b':
  462.     blankflag = 1;
  463.     break;
  464.       case 'w':
  465.     whiteflag = 1;
  466.     break;
  467.       case 'l':
  468.     formopt = 'l';
  469.     break;
  470.       case 's':
  471.     formopt = 's';
  472.     break;
  473.       case '1':
  474.     formopt = '1';
  475.     break;
  476.       case 'h':
  477.     help(); /* ``Why does this function return?''
  478.            `` `Cause you're an idiot.''
  479.            ``Oh yeah.  I forgot.''
  480.            */
  481.     exit(0);
  482.     break;
  483.       case 'm':
  484.     formopt = 'm';
  485.     break;
  486.       case 'M':
  487.     formopt = 'M';
  488.     break;
  489.       default:
  490.     fprintf(stderr, "Unknown option: -%c.\n", argv[i][j]);
  491.     usage(argv[0]);
  492.       }
  493.     }
  494.     if (argv[i][0] == '-') argv[i] = NULL; /* Obliterate flag arguments. */
  495.   }
  496.   return numnonflags;
  497. }
  498.  
  499. /* Manufacture a new masternode whose car is a new filenode.  Return a */
  500. /* pointer to the new masternode. */
  501. masternode *
  502.   newmasternode()
  503. {
  504.   masternode *foo;
  505.   filenode *newfilenode();
  506.  
  507.   foo = NEW(masternode);
  508.   foo->next = NULL;
  509.   foo->data = newfilenode();
  510.  
  511.   return(foo);
  512. }
  513.  
  514. /* Manufacture a new filenode whose car is the null string.  Return a */
  515. /* pointer to the new filenode. */
  516. filenode *
  517.   newfilenode()
  518. {
  519.   filenode *foo;
  520.   
  521.   foo = NEW(filenode);
  522.   foo->next = NULL;
  523.   foo->data = NULL;
  524.   
  525.   return(foo);
  526. }
  527.  
  528. /* head and tail are pointers to masternodes.  (i.e., they are linked lists */
  529. /* of masternodes.)  Append tail to the end of head.  (LISP pepole would */
  530. /* call this operation `nconc'.  I can't say the word `nconc' without */
  531. /* bursting out laughing, so I called it `mappend' instead.) */
  532. void
  533.   mappend(head,tail)
  534. masternode *head, *tail;
  535. {
  536.   masternode *i;
  537.  
  538.   /* Find the end of the linked list `head' */
  539.   for (i=head; i->next; i = i->next) ;
  540.  
  541.   /* Concatenate. */
  542.   i->next = tail;
  543.  
  544.   return;
  545. }
  546.   
  547. /* This is the same as mappend, except it works on filenode-lists instead */
  548. /* of masternode-lists.  Big deal.  */
  549. void
  550.   fappend(head,tail)
  551. filenode *head, *tail;
  552. {
  553.   filenode *i;
  554.   
  555.   for (i=head; i->next; i = i->next) ;
  556.  
  557.   /* nconc!  nconc!  nconc!  hahahaha! */
  558.   i->next = tail;
  559.  
  560.   return;
  561. }
  562.     
  563.  
  564.