home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / diskutil / fdf / fdf.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-08-05  |  10.4 KB  |  486 lines
  1. /*
  2.  * fdf.c
  3.  *
  4.  * find duplicates.  searches a given path and its sub-directories for
  5.  * duplicate files.  Duplicate files have the same name, size, date and
  6.  * contents.  However, the definition used by this program can be almost any
  7.  * user-specified combination of the above.
  8.  *
  9.  * Roy Bixler (original development and Atari ST version, maintenance)
  10.  * Ayman Barakat (idea)
  11.  * David Oertel (MS-DOS version)
  12.  *
  13.  * Version 1.0: March 11, 1991 (known as 'mfd - Monk find duplicates')
  14.  * Version 1.01: April 12, 1992 (now 'fdf - find duplicate files')
  15.  *
  16.  * This program is free software; you can redistribute it and/or modify
  17.  * it under the terms of the GNU General Public License as published by
  18.  * the Free Software Foundation; either version 1, or (at your option)
  19.  * any later version.
  20.  *
  21.  * This program is distributed in the hope that it will be useful,
  22.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  23.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  24.  * GNU General Public License for more details.
  25.  *
  26.  * You should have received a copy of the GNU General Public License
  27.  * along with this program; if not, write to the Free Software
  28.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  29.  */
  30.  
  31.  
  32. #include <ctype.h>
  33. #include <osbind.h>
  34. #include <param.h>
  35. #include <stdlib.h>
  36. #include <stdio.h>
  37. #include <string.h>
  38.  
  39. #include "fdfcomm.h"
  40. #include "fdfstat.h"
  41. #include "elib.h"
  42. #include "fdf.h"
  43.  
  44.  
  45. HASH_LIST *H_list[HASH_TAB_SIZE];
  46.  
  47.  
  48.  
  49. /*
  50.  * print_help
  51.  *
  52.  * prints out the help message for the program
  53.  */
  54. void print_help()
  55.  
  56. {
  57.     printf(FDF_USAGE, PROG_NAME, PROG_NAME);
  58. }
  59.  
  60.  
  61.  
  62. /*
  63.  * show_doc
  64.  *
  65.  * show full documentation
  66.  */
  67. void show_doc()
  68.  
  69. {
  70.     printf(FDF_SCHPIEL);
  71. }
  72.  
  73.  
  74.  
  75. /*
  76.  * add_to_hash_table
  77.  *
  78.  * given a file and a hash table index, add the given file to the hash table
  79.  * at the given index.  Addition is done by putting the new entry at the
  80.  * head of a linked list.
  81.  */
  82. void add_to_hash_table(FILE_LIST *f_name, int h_idx)
  83.  
  84. {
  85.     HASH_LIST *new_entry = malloc((size_t) sizeof(HASH_LIST));
  86.  
  87.     if (new_entry != NULL) {
  88.         new_entry->f_name = f_name;
  89.         new_entry->f_name->printed = 0;
  90.         new_entry->next = H_list[h_idx];
  91.         H_list[h_idx] = new_entry;
  92.     }
  93. }
  94.  
  95.  
  96. /*
  97.  * gen_hash
  98.  *
  99.  * given a linked list repesenting a list of files, generate a hash table for
  100.  * it.
  101.  */
  102. void gen_hash(FILE_LIST *flist)
  103.  
  104. {
  105.     for (;flist != NULL; flist = flist->next) {
  106.         if (!flist->added) {
  107.             if (v_flag) {
  108.                 update_total_bytes(flist->dta.dta_size);
  109.                 update_num_files();
  110.             }
  111.             if ((Match_criteria) & (NAMES_MATCH))
  112.                 add_to_hash_table(flist, hashpjw(flist->dta.dta_name));
  113.             else if ((Match_criteria) & (SIZES_MATCH))
  114.                 add_to_hash_table(flist, flist->dta.dta_size % HASH_TAB_SIZE);
  115.             else if ((Match_criteria) & (TIMES_MATCH))
  116.                 add_to_hash_table(flist,
  117.                                   ((unsigned long) (flist->dta.dta_date << 16) +
  118.                                    (unsigned long) (flist->dta.dta_time)) %
  119.                                   HASH_TAB_SIZE);
  120.             flist->added = 1;
  121.         }
  122.     }
  123. }
  124.  
  125.  
  126.  
  127. /*
  128.  * find_duplicated_name
  129.  *
  130.  * scans the generated hash table for names which occur twice (or more).
  131.  * Takes a pointer to hash table index to start the search at, modifies this
  132.  * on return to indicate where it stopped looking (either because of end of
  133.  * hash table or because a duplicated name found).  Return pointer to first
  134.  * occurrence of duplicated name found or NULL if none found.
  135.  */
  136. HASH_LIST *find_duplicated_name(int *h_idx, HASH_LIST *last_found)
  137.  
  138. {
  139.     int i;
  140.     HASH_LIST *anchor, *cur;
  141.  
  142.     anchor = last_found;
  143.     for (i = *h_idx; i < HASH_TAB_SIZE; i++)
  144.         if (H_list[i] != NULL) {
  145.             if (anchor == NULL)
  146.                 anchor = H_list[i];
  147.             for (; anchor != NULL; anchor = anchor->next)
  148.                 if (!anchor->f_name->printed)
  149.                     for (cur = anchor->next; cur != NULL; cur = cur->next)
  150.                         if ((!cur->f_name->printed) &&
  151.                             (cmpflist_eq(anchor->f_name, cur->f_name))) {
  152.                             *h_idx = i;
  153.                             return anchor;
  154.                         }
  155.         }
  156.  
  157.     *h_idx = i;
  158.     return NULL;
  159. }
  160.  
  161.  
  162.  
  163. /*
  164.  * gen_id_menu
  165.  *
  166.  * given a starting point in the file list, generate an interactive delete
  167.  * menu.  Return number of items put into the menu.
  168.  */
  169. int gen_id_menu(HASH_LIST *name_duped, FILE_LIST **menu, int max_items)
  170.  
  171. {
  172.     int n_found = 0;
  173.     long n_bytes = 0L;
  174.     HASH_LIST *cur;
  175.  
  176.     for (cur = name_duped->next;
  177.          ((cur != NULL) && (n_found < max_items));
  178.          cur = cur->next)
  179.         if ((!cur->f_name->printed) &&
  180.             (files_match(name_duped->f_name, cur->f_name))) {
  181.             if (n_found == 0) {
  182.                 if (v_flag)
  183.                     n_bytes += name_duped->f_name->dta.dta_size;
  184.                 menu[n_found++] = name_duped->f_name;
  185.             }
  186.             if (v_flag)
  187.                 n_bytes += cur->f_name->dta.dta_size;
  188.             menu[n_found++] = cur->f_name;
  189.         }
  190.  
  191.     if ((n_found) && (v_flag)) {
  192.         update_num_which_dupd();
  193.         update_num_dups(n_found, n_bytes);
  194.     }
  195.  
  196.     return n_found;
  197. }
  198.  
  199.  
  200.  
  201. /*
  202.  * id_dups
  203.  *
  204.  * given a pointer to a name which has been determined to be duplicated, print
  205.  * all the names and their path's out and ask the user which ones to delete.
  206.  */
  207. void id_dups(HASH_LIST *start)
  208.  
  209. {
  210.     int n_found, i, n_del;
  211.     FILE_LIST *cur, *menu[N_INTERACTIVE];
  212.     char menu_sel[MAX_STR], which_del[N_INTERACTIVE];
  213.  
  214.     if (!(n_found = gen_id_menu(start, menu, N_INTERACTIVE)))
  215.         return;
  216.     while (1) {
  217.         print_id_menu(menu, n_found);
  218.         printf("\nEnter list of files to delete (hit CR for none)\n");
  219.         fgets(menu_sel, MAX_STR-1, stdin);
  220.         zap_trailing_nl(menu_sel, MAX_STR-1, stdin);
  221.         if (!mark_list(menu_sel, which_del, n_found)) {
  222.             for (n_del=0, i=0; i < n_found; i++)
  223.                 if (which_del[i])
  224.                     if (!delete_path_name_file(menu[i]->path,
  225.                                                menu[i]->dta.dta_name, '\0')) {
  226.                         n_del++;
  227.                         if (v_flag) {
  228.                             update_total_del_bytes(menu[i]->dta.dta_size);
  229.                             if (v_flag > 1) {
  230.                                 printf("Deleted ");
  231.                                 print_fpath(menu[i]->path,
  232.                                             menu[i]->dta.dta_name);
  233.                                 printf("\n");
  234.                             }
  235.                         }
  236.                     }
  237.             break;
  238.         }
  239.     } 
  240.  
  241.     if (n_del)
  242.         printf("\n");
  243. }
  244.  
  245.  
  246.  
  247. /*
  248.  * print_dups
  249.  *
  250.  * given a pointer to a name which has been determined to be duplicated, print
  251.  * all the names and their path's out.
  252.  */
  253. void print_dups(HASH_LIST *name_duped)    /* now, who's being duped here? */
  254.  
  255. {
  256.     HASH_LIST *cur;
  257.  
  258.     for (cur = name_duped->next; cur != NULL; cur = cur->next)
  259.         if ((!cur->f_name->printed) &&
  260.             (files_match(name_duped->f_name, cur->f_name))) {
  261.             if (!name_duped->f_name->printed) {
  262.                 if (v_flag) {
  263.                     update_num_which_dupd();
  264.                     update_num_dups(1U, name_duped->f_name->dta.dta_size);
  265.                 }
  266.                 print_match_header(name_duped->f_name);
  267.                 print_next_match(name_duped->f_name, -1);
  268.             }
  269.             if (v_flag)
  270.                 update_num_dups(1U, cur->f_name->dta.dta_size);
  271.             print_next_match(cur->f_name, -1);
  272.         }
  273.  
  274.     if (name_duped->f_name->printed)
  275.         printf("\n");
  276. }
  277.  
  278.  
  279.  
  280. /*
  281.  * find_non_printed
  282.  *
  283.  * given a pointer to a FILE_LIST, return the pointer to the next element which
  284.  * has not been printed yet.
  285.  */
  286. HASH_LIST *find_non_printed(HASH_LIST *file)
  287.  
  288. {
  289.     for (; ((file != NULL) && (file->f_name->printed)); file = file->next);
  290.     return file;
  291. }
  292.  
  293.  
  294.  
  295. /*
  296.  * find_dups
  297.  *
  298.  * given a path, find the duplicate files and dump them to the standard output.
  299.  */
  300. void find_dups()
  301.  
  302. {
  303.     HASH_LIST *last_found, *f_found;
  304.     int i;
  305.  
  306.     gen_hash(F_list);
  307.     i = 0;
  308.     last_found = NULL;
  309.     while ((i < HASH_TAB_SIZE) &&
  310.            ((f_found = find_duplicated_name(&i, last_found)) != NULL)) {
  311.         if (i_flag)
  312.             id_dups(f_found);
  313.         else
  314.             print_dups(f_found);
  315.         last_found = find_non_printed(f_found->next);
  316.     }
  317. }
  318.  
  319.  
  320.  
  321. /*
  322.  * init_hash
  323.  *
  324.  * insure the hash table is empty
  325.  */
  326. void init_hash()
  327.  
  328. {
  329.     int i;
  330.  
  331.     for (i=0; i<HASH_TAB_SIZE; i++)
  332.         H_list[i] = NULL;
  333. }
  334.  
  335.  
  336.  
  337. /*
  338.  * set_sort_hash_criteria
  339.  *
  340.  * must guarantee that no matter what the matching criteria is, that
  341.  * duplicate files will always go to the same hash table location.
  342.  *
  343.  * This is called to make sure that, when comparing two entries in the same
  344.  * hash table bucket (i.e when calling 'cmpflist_eq()'), appropriate criteria
  345.  * are used to determine if the two entries can possibly match.  There is no
  346.  * real sorting with the hash table!
  347.  */
  348. void set_sort_hash_criteria()
  349.  
  350. {
  351.     if ((Match_criteria) & (NAMES_MATCH))
  352.         Sort_criteria = NAME_SORT;
  353.     else if ((Match_criteria) & (SIZES_MATCH))
  354.         Sort_criteria = SIZE_SORT;
  355.     else if ((Match_criteria) & (TIMES_MATCH))
  356.         Sort_criteria = TIME_SORT;
  357. }
  358.  
  359.  
  360.  
  361. /*
  362.  * get_options
  363.  *
  364.  * get the command-line options, check for consistency and set the appropriate
  365.  * variables.
  366.  */
  367. int get_options(int argc, char **argv)
  368.  
  369. {
  370.     extern int getopt(int argc, char **argv, char *opts);
  371.     extern int Optind;
  372.     extern char *optarg;
  373.     int optchar;
  374.     char a_flag = 0, c_flag = 0, d_flag = 0, n_flag = 0, s_flag = 0;
  375.  
  376.     if (argc < 2) {
  377.         print_help();
  378.         exit(-1);
  379.     }
  380.  
  381.     while ((optchar = getopt(argc, argv, GETOPT_LIST)) != EOF) {
  382.         if (isupper(optchar))
  383.             optchar = tolower(optchar);
  384.         switch (optchar) {
  385.         case 'i':
  386.             i_flag = 1;
  387.             break;
  388.         case 'l':
  389.             l_flag = 1;
  390.             break;
  391.         case 'm':
  392.             if ((optarg == NULL) || (strpbrk(optarg, "AaCcDdNnSs") != optarg)) {
  393.                 printf("%s: must specify 'a' or 'c', 'd', 'n' and/or 's' after -m\n", 
  394.                        PROG_NAME);
  395.                 print_help();
  396.                 exit(-1);
  397.             }
  398.             for (;*optarg != '\0'; optarg++) {
  399.                 if (isupper(*optarg))
  400.                     *optarg = tolower(*optarg);
  401.                 switch (*optarg) {
  402.                 case 'a':
  403.                     a_flag = 1;
  404.                     break;
  405.                 case 'c':
  406.                     c_flag = 1;
  407.                     Match_criteria |= CONTENTS_MATCH;
  408.                     break;
  409.                 case 'd':
  410.                     d_flag = 1;
  411.                     Match_criteria |= TIMES_MATCH;
  412.                     break;
  413.                 case 'n':
  414.                     n_flag = 1;
  415.                     Match_criteria |= NAMES_MATCH;
  416.                     break;
  417.                 case 's':
  418.                     s_flag = 1;
  419.                     Match_criteria |= SIZES_MATCH;
  420.                     break;
  421.                 default:
  422.                     printf("%s: invalid match criteria '%c' specified\n", 
  423.                            PROG_NAME, *optarg);
  424.                     print_help();
  425.                     exit(-1);
  426.                 }
  427.             }
  428.             break;
  429.         case 'v':
  430.             v_flag++;
  431.             break;
  432.         case '?':
  433.             show_doc();
  434.             exit(0);
  435.         default:
  436.             print_help();
  437.             exit(-1);
  438.         }
  439.     }
  440.  
  441.     if (argc == Optind) {
  442.         printf("%s: at least one path specification required\n", PROG_NAME);
  443.         print_help();
  444.         exit(-1);
  445.     }
  446.     else if (a_flag)
  447.         if ((c_flag) || (d_flag) || (n_flag) || (s_flag)) {
  448.             printf("%s: -ma option conflicts with -mc, -md, -mn or -ms\n",
  449.                    PROG_NAME);
  450.             print_help();
  451.             exit(-1);
  452.         }
  453.         else
  454.             Match_criteria = ALL_MATCH;
  455.     else if (!Match_criteria)
  456.         Match_criteria = (TIMES_MATCH|SIZES_MATCH|NAMES_MATCH);
  457.     else if (Match_criteria & CONTENTS_MATCH)
  458.         Match_criteria |= SIZES_MATCH;
  459.     set_sort_hash_criteria();
  460.  
  461.     return Optind;
  462. }
  463.  
  464.  
  465.  
  466. int main(int argc, char **argv)
  467.  
  468. {
  469.     int i;
  470.     char form_path[MAXPATHLEN];
  471.  
  472.     init_hash();
  473.     for (i = get_options(argc, argv); i < argc; i++) {
  474.         format_dir(argv[i], '\0', form_path);
  475.         if (v_flag > 1)
  476.             printf("finding duplicates under %s:\n\n", form_path);
  477.         list_files(PROG_NAME, form_path, (char) 0);
  478.     }
  479.  
  480.     find_dups();
  481.     if (v_flag)
  482.         print_stats();
  483.  
  484.     exit(0);
  485. }
  486.