Minor typo.
[finddup.git] / finddup.c
1
2 /*
3  *  finddup is a simple utility to find duplicated files, files common
4  *  to several directories, or files present in one directory and not
5  *  in another one.
6  *
7  *  Copyright (c) 2010, 2011 Francois Fleuret
8  *  Written by Francois Fleuret <francois@fleuret.org>
9  *
10  *  This file is part of finddup.
11  *
12  *  finddup is free software: you can redistribute it and/or modify it
13  *  under the terms of the GNU General Public License version 3 as
14  *  published by the Free Software Foundation.
15  *
16  *  finddup is distributed in the hope that it will be useful, but WITHOUT
17  *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
18  *  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
19  *  License for more details.
20  *
21  *  You should have received a copy of the GNU General Public License
22  *  along with finddup.  If not, see <http://www.gnu.org/licenses/>.
23  *
24  */
25
26 #define VERSION_NUMBER "1.2.1"
27
28 #define _DEFAULT_SOURCE
29
30 #include <sys/types.h>
31 #include <sys/stat.h>
32 #include <sys/param.h>
33 #include <sys/wait.h>
34 #include <dirent.h>
35 #include <stdlib.h>
36 #include <stdio.h>
37 #include <unistd.h>
38 #include <errno.h>
39 #include <string.h>
40 #include <sys/ioctl.h>
41 #include <locale.h>
42 #include <getopt.h>
43 #include <fcntl.h>
44
45 /* 1M really helps compared to 64k */
46 #define READ_BUFFER_SIZE (1024 * 1024)
47
48 #define PROGRESS_BUFFER_SIZE 1024
49
50 typedef int64_t size_sum_t;
51
52 /* Yeah, global variables! */
53
54 int ignore_dotfiles = 0; /* 1 means ignore files and directories
55                             starting with a dot */
56
57 int ignore_empty_files = 0; /* 1 means ignore empty files */
58
59 int show_realpaths = 0; /* 1 show the canonical absolute pathname for
60                            printed files */
61
62 int show_progress = 0; /* 1 means show a progress bar when we are in a
63                           tty */
64
65 int show_hits = 1; /* 1 means to show the files from dir2
66                       corresponding to the ones from dir1 */
67
68 int show_groups = 1; /* 1 means to show the group IDs when printing
69                         file names */
70
71 int same_inodes_are_different = 0; /* 1 means that comparison between
72                                       two files with same inode will
73                                       always be false */
74
75 int sort_by_time = 0; /* 1 means to sort files in each group according
76                          to the modification time */
77
78 int trim_first = 0; /* remove the first entry in each group */
79
80 char *command_to_exec = 0; /* the name of the command to exec for each
81                               group of identical files */
82
83 char *result_file_prefix = 0; /* The prefix to use to write result */
84
85 /********************************************************************/
86
87 /* malloc with error checking.  */
88
89 void *safe_malloc(size_t n) {
90   void *p = malloc(n);
91   if (!p && n != 0) {
92     fprintf(stderr,
93             "finddup: Can not allocate memory: %s\n", strerror(errno));
94     exit(EXIT_FAILURE);
95   }
96   return p;
97 }
98
99 /********************************************************************/
100
101 int ignore_entry(const char *name) {
102   return
103     strcmp(name, ".") == 0 ||
104     strcmp(name, "..") == 0 ||
105     (ignore_dotfiles && name[0] == '.' && name[1] != '/');
106 }
107
108 /**********************************************************************/
109
110 struct file_node {
111   struct file_node *next;
112   char *name;
113   size_t size;
114   time_t atime, mtime, ctime;
115   ino_t inode;
116   int group_id; /* one per identical file content */
117   int dir_id; /* 1 for DIR1, and 2 for DIR2 */
118 };
119
120 void file_list_delete(struct file_node *head) {
121   struct file_node *next;
122   while(head) {
123     next = head->next;
124     free(head->name);
125     free(head);
126     head = next;
127   }
128 }
129
130 int file_list_length(struct file_node *head) {
131   int l = 0;
132   while(head) {
133     l++;
134     head = head->next;
135   }
136   return l;
137 }
138
139 /**********************************************************************/
140
141 int same_content(struct file_node *f1, struct file_node *f2,
142                  char *buffer1, char *buffer2) {
143   int fd1, fd2, s1, s2;
144
145   fd1 = open(f1->name, O_RDONLY);
146   fd2 = open(f2->name, O_RDONLY);
147
148   if(fd1 >= 0 && fd2 >= 0) {
149     while(1) {
150       s1 = read(fd1, buffer1, READ_BUFFER_SIZE);
151       s2 = read(fd2, buffer2, READ_BUFFER_SIZE);
152
153       if(s1 < 0 || s2 < 0) {
154         close(fd1);
155         close(fd2);
156         return 0;
157       }
158
159       if(s1 == s2) {
160         if(s1 == 0) {
161           close(fd1);
162           close(fd2);
163           return 1;
164         } else {
165           if(memcmp(buffer1, buffer2, s1)) {
166             /* printf("size_to_read = %d\n", size_to_read); */
167             close(fd1);
168             close(fd2);
169             return 0;
170           }
171         }
172       } else {
173         fprintf(stderr,
174                 "finddup: Different read size without error on files of same size.\n");
175         exit(EXIT_FAILURE);
176       }
177     }
178   } else {
179
180     if(fd1 < 0) {
181       fprintf(stderr,
182               "finddup: Can not open \"%s\" error: %s\n",
183               f1->name,
184               strerror(errno));
185     }
186
187     if(fd2 < 0) {
188       fprintf(stderr,
189               "finddup: Can not open \"%s\" error: %s\n",
190               f2->name,
191               strerror(errno));
192     }
193
194     exit(EXIT_FAILURE);
195   }
196 }
197
198 int same_files(struct file_node *f1, struct file_node *f2,
199                char *buffer1, char *buffer2) {
200   if(same_inodes_are_different && f1->inode == f2->inode) {
201     return 0;
202   }
203
204   return f1->size == f2->size && same_content(f1, f2, buffer1, buffer2);
205 }
206
207 /**********************************************************************/
208
209 struct file_node *scan_directory_rec(struct file_node *tail, const char *name) {
210   DIR *dir;
211   struct dirent *dir_e;
212   struct stat sb;
213   struct file_node *tmp;
214   char subname[PATH_MAX + 1];
215
216   if(lstat(name, &sb) != 0) {
217     fprintf(stderr, "finddup: Can not stat \"%s\": %s\n", name, strerror(errno));
218     exit(EXIT_FAILURE);
219   }
220
221   if(S_ISLNK(sb.st_mode)) {
222     return tail;
223   }
224
225   dir = opendir(name);
226
227   if(dir) {
228     while((dir_e = readdir(dir))) {
229       if(!ignore_entry(dir_e->d_name)) {
230         snprintf(subname, PATH_MAX, "%s/%s", name, dir_e->d_name);
231         tail = scan_directory_rec(tail, subname);
232       }
233     }
234     closedir(dir);
235   } else {
236     if(S_ISREG(sb.st_mode)) {
237       if(!ignore_entry(name)) {
238         if(!ignore_empty_files || sb.st_size > 0) {
239           tmp = safe_malloc(sizeof(struct file_node));
240           tmp->next = tail;
241           tmp->name = strdup(name);
242           tmp->size = sb.st_size;
243           tmp->atime = sb.st_atime;
244           tmp->mtime = sb.st_mtime;
245           tmp->ctime = sb.st_ctime;
246           tmp->inode = sb.st_ino;
247           tmp->group_id = -1;
248           tmp->dir_id = -1;
249           tail = tmp;
250         }
251       }
252     }
253   }
254
255   return tail;
256 }
257
258 struct file_node *scan_directory(struct file_node *tail, const char *name) {
259   struct file_node *result;
260   int length;
261
262   if(show_progress) {
263     fprintf(stderr, "Scanning '%s' ... ", name);
264   }
265
266   result = scan_directory_rec(tail, name);
267   length = file_list_length(result);
268
269   if(show_progress) {
270     fprintf(stderr, "done (%d file%s).\n",
271             length, (length > 1 ? "s" : ""));
272   }
273
274
275   return result;
276 }
277
278 void write_one_entry_to_file(FILE *out, struct file_node *node) {
279   char tmp[PATH_MAX + 1];
280   if(show_realpaths) {
281     if(realpath(node->name, tmp)) {
282       if(show_groups) {
283         fprintf(out, "%d %s\n", node->group_id, tmp);
284       } else {
285         fprintf(out, "%s\n", tmp);
286       }
287     } else {
288       fprintf(stderr,
289               "finddup: Can not get the realpath of \"%s\": %s\n",
290               node->name,
291               strerror(errno));
292       exit(EXIT_FAILURE);
293     }
294   } else {
295     if(show_groups) {
296       fprintf(out, "%d %s\n", node->group_id, node->name);
297     } else {
298       fprintf(out, "%s\n", node->name);
299     }
300   }
301 }
302
303 int compare_nodes(const void *x1, const void *x2) {
304   const struct file_node **f1, **f2;
305
306   f1 = (const struct file_node **) x1;
307   f2 = (const struct file_node **) x2;
308
309   if((*f1)->group_id < (*f2)->group_id) {
310     return -1;
311   } else if((*f1)->group_id > (*f2)->group_id) {
312     return 1;
313   } else {
314     if(sort_by_time) {
315       if((*f1)->mtime < (*f2)->mtime) {
316         return -1;
317       } else if((*f1)->mtime > (*f2)->mtime) {
318         return 1;
319       } else {
320         return 0;
321       }
322     } else {
323       if((*f1)->dir_id < (*f2)->dir_id) {
324         return -1;
325       } else if((*f1)->dir_id > (*f2)->dir_id) {
326         return 1;
327       } else {
328         return 0;
329       }
330     }
331   }
332 }
333
334 void exec_command(int nb, struct file_node **nodes) {
335   char **args;
336   int max_group_size = 0, group_size = 0, m, n, status;
337   pid_t pid;
338
339   for(n = 0; n < nb; n++) {
340     if(n > 0 && nodes[n]->group_id != nodes[n-1]->group_id) {
341       group_size = 0;
342     }
343     group_size++;
344     if(group_size > max_group_size) {
345       max_group_size = group_size;
346     }
347   }
348
349   args = safe_malloc((max_group_size + 2) * sizeof(char *));
350   args[0] = command_to_exec;
351
352   n = 0;
353   while(n < nb) {
354     m = n;
355     if(trim_first) { m++; }
356     while(n < nb && nodes[n]->group_id == nodes[m]->group_id) {
357       if(n >= m) {
358         args[n - m + 1] = nodes[n]->name;
359       }
360       n++;
361     }
362     args[n - m + 1] = 0;
363     pid = fork();
364     if(pid < 0) {
365     } else if(pid == 0) {
366       if(execvp(command_to_exec, args) < 0) {
367         perror("execvp");
368         exit(EXIT_FAILURE);
369       }
370     } else {
371       while(wait(&status) != pid);
372       if(status > 0) {
373         exit(EXIT_FAILURE);
374       }
375     }
376   }
377
378   free(args);
379 }
380
381 void write_groups_in_files(int nb, struct file_node **nodes) {
382   FILE *file = 0;
383   int current_group = -1, n, first_of_group;
384   char filename[PATH_MAX + 1];
385
386   for(n = 0; n < nb; n++) {
387     first_of_group = (n == 0);
388     if(nodes[n]->group_id != current_group) {
389       if(file) { fclose(file); }
390       sprintf(filename, "%s%06d", result_file_prefix, nodes[n]->group_id);
391       file = fopen(filename, "w");
392       current_group = nodes[n]->group_id;
393       printf("Writing %s.\n" , filename);
394       first_of_group = 1;
395     }
396
397     if(!trim_first || !first_of_group) {
398       write_one_entry_to_file(file, nodes[n]);
399     }
400   }
401
402   if(file) { fclose(file); }
403 }
404
405 void print_result(struct file_node *list1, struct file_node *list2) {
406   struct file_node *node1, *node2;
407   struct file_node **nodes;
408   int nb, n, first_of_group;
409
410   nb = 0;
411   for(node1 = list1; node1; node1 = node1->next) {
412     if(node1->group_id >= 0) { nb++; }
413   }
414
415   if(list2) {
416     for(node2 = list2; node2; node2 = node2->next) {
417       if(node2->group_id >= 0) { nb++; }
418     }
419   }
420
421   nodes = safe_malloc(nb * sizeof(struct file_node *));
422
423   n = 0;
424   for(node1 = list1; node1; node1 = node1->next) {
425     if(node1->group_id >= 0) {
426       nodes[n++] = node1;
427     }
428   }
429
430   if(list2) {
431     for(node2 = list2; node2; node2 = node2->next) {
432       if(node2->group_id >= 0) {
433         nodes[n++] = node2;
434       }
435     }
436   }
437
438   qsort(nodes, nb, sizeof(struct file_node *), compare_nodes);
439
440   if(command_to_exec) {
441     exec_command(nb, nodes);
442   } else if(result_file_prefix) {
443     write_groups_in_files(nb, nodes);
444   } else {
445     for(n = 0; n < nb; n++) {
446       first_of_group = (n == 0);
447       if(n > 0 && nodes[n]->group_id != nodes[n-1]->group_id) {
448         if(!show_groups) {
449           printf("\n");
450         }
451         first_of_group = 1;
452       }
453       if(!trim_first || !first_of_group) {
454         write_one_entry_to_file(stdout, nodes[n]);
455       }
456     }
457   }
458
459   free(nodes);
460 }
461
462 struct progress_state {
463   int bar_width;
464   int nb_values, value;
465   int last_position;
466 };
467
468 void print_progress(struct progress_state *state) {
469   int position, k, normalizer;
470   struct winsize win;
471   char buffer[PROGRESS_BUFFER_SIZE];
472   char *s;
473
474   normalizer = (state->nb_values > 1 ? state->nb_values - 1 : 1);
475
476   if(show_progress) {
477     /* We use the previous bar_width to compute the position, so that
478        we avoid doing too many ioctls */
479     position = (state->bar_width * state->value) / normalizer;
480     if(state->bar_width <= 0 || position != state->last_position) {
481       if(!ioctl (STDERR_FILENO, TIOCGWINSZ, (char *) &win)) {
482         /* Something weird is going on if the previous test is wrong */
483         if(win.ws_col >= PROGRESS_BUFFER_SIZE - 3) {
484           state->bar_width = PROGRESS_BUFFER_SIZE - 10;
485         } else {
486           state->bar_width = win.ws_col - 7;
487         }
488         position = (state->bar_width * state->value) / normalizer;
489         state->last_position = position;
490         s = buffer;
491         for(k = 0; k < position; k++) {
492           *(s++) = '+';
493         }
494         for(; k < state->bar_width; k++) {
495           *(s++) = '-';
496         }
497
498         /* We need four % because of the fprintf that follows */
499         sprintf(s, " [%3d%%]\r",
500                 (100 * state->value) / normalizer);
501
502         fprintf(stderr, "%s", buffer);
503       }
504     }
505   }
506 }
507
508 void start(const char *dirname1, const char *dirname2) {
509   struct file_node *list1, *list2;
510   struct file_node *node1, *node2;
511   struct progress_state progress_state;
512   int not_in, found;
513   int nb_groups, nb_nodes;
514   int list1_length;
515
516   char *buffer1 = safe_malloc(sizeof(char) * READ_BUFFER_SIZE);
517   char *buffer2 = safe_malloc(sizeof(char) * READ_BUFFER_SIZE);
518
519   not_in = 0;
520
521   list1 = scan_directory(0, dirname1);
522   list1_length = file_list_length(list1);
523
524   if(dirname2) {
525     if(strncmp(dirname2, "not:", 4) == 0) {
526       not_in = 1;
527       /* groups are not computed in the not: mode */
528       show_groups = 0;
529       dirname2 += 4;
530     } else if(strncmp(dirname2, "and:", 4) == 0) {
531       dirname2 += 4;
532     }
533     list2 = scan_directory(0, dirname2);
534   } else {
535     list2 = list1;
536   }
537
538   if(show_progress) {
539     fprintf(stderr,
540             "Now looking for identical files (this may take a while).\n");
541   }
542
543   nb_groups = 0;
544   nb_nodes = 0;
545
546   progress_state.bar_width = -1;
547   progress_state.last_position = -1;
548   progress_state.nb_values = list1_length;
549
550   if(not_in) {
551     for(node1 = list1; node1; node1 = node1->next) {
552       progress_state.value = nb_nodes;
553       print_progress(&progress_state);
554       nb_nodes++;
555
556       found = 0;
557
558       for(node2 = list2; !found && node2; node2 = node2->next) {
559         if(same_files(node1, node2, buffer1, buffer2)) {
560           found = 1;
561         }
562       }
563
564       if(!found) {
565         if(show_realpaths) {
566           printf("%s\n", realpath(node1->name, 0));
567         } else {
568           printf("%s\n", node1->name);
569         }
570       }
571     }
572
573   } else {
574     for(node1 = list1; node1; node1 = node1->next) {
575       progress_state.value = nb_nodes;
576       print_progress(&progress_state);
577       nb_nodes++;
578
579       for(node2 = list2; node2; node2 = node2->next) {
580         if(node1->group_id < 0 || node2->group_id < 0) {
581           if(same_files(node1, node2, buffer1, buffer2)) {
582             if(node1->group_id < 0) {
583               if(node2->group_id >= 0) {
584                 node1->group_id = node2->group_id;
585               } else {
586                 node1->group_id = nb_groups;
587                 node1->dir_id = 1;
588                 nb_groups++;
589               }
590             }
591             if(node2->group_id < 0) {
592               node2->group_id = node1->group_id;
593               node2->dir_id = 2;
594             }
595           }
596         }
597       }
598     }
599   }
600
601   if(show_progress) {
602     fprintf(stderr, "\n");
603   }
604
605   if(dirname2) {
606     print_result(list1, list2);
607     file_list_delete(list1);
608     file_list_delete(list2);
609   } else {
610     print_result(list1, 0);
611     file_list_delete(list1);
612   }
613
614   free(buffer1);
615   free(buffer2);
616 }
617
618 void usage(FILE *out) {
619   fprintf(out, "Usage: finddup [OPTION]... [DIR1 [[and:|not:]DIR2]]\n");
620   fprintf(out, "Version %s (%s)\n", VERSION_NUMBER, UNAME);
621   fprintf(out, "Without DIR2, lists duplicated files found in DIR1, or the current directory if DIR1 is not provided. With DIR2, lists files common to both directories. With the not: prefix, lists files found in DIR1 which do not exist in DIR2. The and: prefix is the default and should be used only if you have a directory starting with 'not:'\n");
622   fprintf(out, "\n");
623   /*            01234567890123456789012345678901234567890123456789012345678901234567890123456789*/
624   fprintf(out, "   -v, --version              prints the version number and exit\n");
625   fprintf(out, "   -h, --help                 show this help\n");
626   fprintf(out, "   -d, --ignore-dots          ignore dot files and directories\n");
627   fprintf(out, "   -0, --ignore-empty         ignore empty files\n");
628   fprintf(out, "   -c, --hide-matchings       do not show which files in DIR2 corresponds to\n");
629   fprintf(out, "                              those in DIR1\n");
630   fprintf(out, "   -g, --no-group-ids         do not show the file groups\n");
631   fprintf(out, "   -t, --time-sort            sort according to modification time in each group\n");
632   fprintf(out, "   -q, --trim-first           do not show the first file in each group\n");
633   fprintf(out, "   -p, --show-progress        show progress\n");
634   fprintf(out, "   -r, --real-paths           show the real file paths\n");
635   fprintf(out, "   -i, --same-inodes-are-different\n");
636   fprintf(out, "                              consider files with same inode as different\n");
637   fprintf(out, "   -e <command>, --exec <command>\n");
638   fprintf(out, "                              execute the provided command for each group of\n");
639   fprintf(out, "                              identical files, with their names as arguments\n");
640   fprintf(out, "   -f <string>, --result-prefix <string>\n");
641   fprintf(out, "                              for each group of identical files, write one\n");
642   fprintf(out, "                              result file whose name is the given prefix string\n");
643   fprintf(out, "                              followed by the group number, and containing\n");
644   fprintf(out, "                              one filename per line\n");
645   fprintf(out, "\n");
646   fprintf(out, "Report bugs and comments to <francois@fleuret.org>.\n");
647 }
648
649 /**********************************************************************/
650
651 static struct option long_options[] = {
652   { "version", no_argument, 0, 'v' },
653   { "help", no_argument, 0, 'h' },
654   { "same-inodes-are-different", no_argument, 0, 'i' },
655   { "real-paths", no_argument, 0, 'r' },
656   { "hide-matchings", no_argument, 0, 'c' },
657   { "no-group-ids", no_argument, 0, 'g' },
658   { "time-sort", no_argument, 0, 't' },
659   { "trim-first", no_argument, 0, 'q' },
660   { "ignore-dots", no_argument, 0, 'd' },
661   { "ignore-empty", no_argument, 0, '0' },
662   { "show-progress", no_argument, 0, 'p' },
663   { "exec", 1, 0, 'e' },
664   { "result-prefix", 1, 0, 'f' },
665   { 0, 0, 0, 0 }
666 };
667
668 int main(int argc, char **argv) {
669   int c;
670
671   setlocale (LC_ALL, "");
672
673   while ((c = getopt_long(argc, argv, "vhircgtqd0pme:f:",
674                           long_options, NULL)) != -1) {
675     switch (c) {
676
677     case 'v':
678       printf("finddup version %s (%s)\n", VERSION_NUMBER, UNAME);
679       exit(EXIT_SUCCESS);
680       break;
681
682     case 'h':
683       usage(stdout);
684       exit(EXIT_SUCCESS);
685
686       break;
687
688     case 'd':
689       ignore_dotfiles = 1;
690       break;
691
692     case '0':
693       ignore_empty_files = 1;
694       break;
695
696     case 'r':
697       show_realpaths = 1;
698       break;
699
700     case 'i':
701       same_inodes_are_different = 1;
702       break;
703
704     case 'g':
705       show_groups = 0;
706       break;
707
708     case 't':
709       sort_by_time = 1;
710       break;
711
712     case 'q':
713       trim_first = 1;
714       break;
715
716     case 'p':
717       show_progress = 1;
718       break;
719
720     case 'c':
721       show_hits = 0;
722       break;
723
724     case 'e':
725       if(command_to_exec != 0) {
726         free(command_to_exec);
727       }
728       command_to_exec = strdup(optarg);
729       break;
730
731     case 'f':
732       if(result_file_prefix != 0) {
733         free(result_file_prefix);
734       }
735       result_file_prefix = strdup(optarg);
736       show_groups = 0;
737       break;
738
739     default:
740       usage(stderr);
741       exit(EXIT_FAILURE);
742     }
743   }
744
745   if(!isatty(STDERR_FILENO)) {
746     show_progress = 0;
747   }
748
749   if(optind + 2 == argc) {
750     start(argv[optind], argv[optind + 1]);
751   } else if(optind + 1 == argc) {
752     same_inodes_are_different = 1;
753     start(argv[optind], 0);
754   } else if(optind == argc) {
755     same_inodes_are_different = 1;
756     start(".", 0);
757   } else {
758     usage(stderr);
759     exit(EXIT_FAILURE);
760   }
761
762   exit(EXIT_SUCCESS);
763 }