finddup.c

   1
   2 /*
   3  *  finddup is a simple utility find duplicated files, files common to
   4  *  several directories, or files present in one directory and not in
   5  *  another one.
   6  *
   7  *  Copyright (c) 2010 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 "0.6"
  27
  28 #define _BSD_SOURCE
  29
  30 #include <sys/types.h>
  31 #include <sys/stat.h>
  32 #include <sys/param.h>
  33 #include <dirent.h>
  34 #include <stdlib.h>
  35 #include <stdio.h>
  36 #include <unistd.h>
  37 #include <errno.h>
  38 #include <string.h>
  39 #include <sys/ioctl.h>
  40 #include <locale.h>
  41 #include <getopt.h>
  42 #include <fcntl.h>
  43
  44 #define BUFFER_SIZE 4096
  45
  46 typedef int64_t size_sum_t;
  47
  48 /* Yeah, global variables! */
  49
  50 int ignore_dotfiles = 0; /* 1 means ignore files and directories
  51                             starting with a dot */
  52
  53 int show_realpaths = 0; /* 1 means ignore files and directories
  54                             starting with a dot */
  55
  56 int show_progress = 0; /* 1 means show a progress bar when we are in a
  57                           tty */
  58
  59 int show_hits = 1; /* 1 means to show the files from dir2
  60                       corresponding to the ones from dir1 */
  61
  62 int show_groups = 1; /* 1 means to show the group IDs when printing
  63                         file names */
  64
  65 /********************************************************************/
  66
  67 /* malloc with error checking.  */
  68
  69 void *safe_malloc(size_t n) {
  70   void *p = malloc(n);
  71   if (!p && n != 0) {
  72     printf("Can not allocate memory: %s\n", strerror(errno));
  73     exit(EXIT_FAILURE);
  74   }
  75   return p;
  76 }
  77
  78 /********************************************************************/
  79
  80 int ignore_entry(const char *name) {
  81   return
  82     strcmp(name, ".") == 0 ||
  83     strcmp(name, "..") == 0 ||
  84     (ignore_dotfiles && name[0] == '.');
  85 }
  86
  87 void print_size_sum(size_sum_t s) {
  88   char tmp[100];
  89   char *a = tmp + sizeof(tmp)/sizeof(char);
  90   *(--a) = '\0';
  91   if(s) {
  92     while(s) {
  93       *(--a) = s%10 + '0';
  94       s /= 10;
  95     }
  96   } else {
  97     *(--a) = '0';
  98   }
  99   printf(a);
 100 }
 101
 102 /**********************************************************************/
 103
 104 struct file_with_size {
 105   char *filename;
 106   size_t size;
 107   ino_t inode;
 108   struct file_with_size *next;
 109   int group_id;
 110 };
 111
 112 void file_list_delete(struct file_with_size *head) {
 113   struct file_with_size *next;
 114   while(head) {
 115     next = head->next;
 116     free(head->filename);
 117     free(head);
 118     head = next;
 119   }
 120 }
 121
 122 int file_list_length(struct file_with_size *head) {
 123   int l = 0;
 124   while(head) {
 125     l++;
 126     head = head->next;
 127   }
 128   return l;
 129 }
 130
 131 /**********************************************************************/
 132
 133 int same_content(struct file_with_size *f1, struct file_with_size *f2) {
 134   int fd1, fd2, s1, s2;
 135   char buffer1[BUFFER_SIZE], buffer2[BUFFER_SIZE];
 136
 137   fd1 = open(f1->filename, O_RDONLY);
 138   fd2 = open(f2->filename, O_RDONLY);
 139
 140   if(fd1 >= 0 && fd2 >= 0) {
 141     while(1) {
 142       s1 = read(fd1, buffer1, BUFFER_SIZE);
 143       s2 = read(fd2, buffer2, BUFFER_SIZE);
 144
 145       if(s1 < 0 || s2 < 0) {
 146         close(fd1);
 147         close(fd2);
 148         return 0;
 149       }
 150
 151       if(s1 == s2) {
 152         if(s1 == 0) {
 153           close(fd1);
 154           close(fd2);
 155           return 1;
 156         } else {
 157           if(strncmp(buffer1, buffer2, s1)) {
 158             close(fd1);
 159             close(fd2);
 160             return 0;
 161           }
 162         }
 163       } else {
 164         fprintf(stderr,
 165                 "Different read size without error on files of same size.\n");
 166         exit(EXIT_FAILURE);
 167       }
 168     }
 169   } else {
 170
 171     if(fd1 < 0) {
 172       fprintf(stderr,
 173               "Can not open \"%s\" error: %s\n",
 174               f1->filename,
 175               strerror(errno));
 176     }
 177
 178     if(fd2 < 0) {
 179       fprintf(stderr,
 180               "Can not open \"%s\" error: %s\n",
 181               f2->filename,
 182               strerror(errno));
 183     }
 184     exit(EXIT_FAILURE);
 185   }
 186 }
 187
 188 int same_files(struct file_with_size *f1, struct file_with_size *f2) {
 189   return f1->size == f2->size && same_content(f1, f2);
 190 }
 191
 192 /**********************************************************************/
 193
 194 struct file_with_size *scan_directory(struct file_with_size *tail,
 195                                       const char *name) {
 196   DIR *dir;
 197   struct dirent *dir_e;
 198   struct stat sb;
 199   struct file_with_size *tmp;
 200   char subname[PATH_MAX + 1];
 201
 202   if(lstat(name, &sb) != 0) {
 203     fprintf(stderr, "Can not stat \"%s\": %s\n", name, strerror(errno));
 204     exit(EXIT_FAILURE);
 205   }
 206
 207   if(S_ISLNK(sb.st_mode)) {
 208     return tail;
 209   }
 210
 211   dir = opendir(name);
 212
 213   if(dir) {
 214     while((dir_e = readdir(dir))) {
 215       if(!ignore_entry(dir_e->d_name)) {
 216         snprintf(subname, PATH_MAX, "%s/%s", name, dir_e->d_name);
 217         tail = scan_directory(tail, subname);
 218       }
 219     }
 220     closedir(dir);
 221   } else {
 222     if(S_ISREG(sb.st_mode)) {
 223       tmp = safe_malloc(sizeof(struct file_with_size));
 224       tmp->next = tail;
 225       tmp->filename = strdup(name);
 226       tmp->size = sb.st_size;
 227       tmp->inode = sb.st_ino;
 228       tmp->group_id = -1;
 229       tail = tmp;
 230     }
 231   }
 232
 233   return tail;
 234 }
 235
 236 void print_file(struct file_with_size *node) {
 237   char tmp[PATH_MAX + 1];
 238   if(show_realpaths) {
 239     if(show_groups) {
 240       realpath(node->filename, tmp);
 241       printf("%d %s\n", node->group_id, tmp);
 242     } else {
 243       realpath(node->filename, tmp);
 244       printf("%s\n", tmp);
 245     }
 246   } else {
 247     if(show_groups) {
 248       printf("%d %s\n", node->group_id, node->filename);
 249     } else {
 250       printf("%s\n", node->filename);
 251     }
 252   }
 253 }
 254
 255 int compare_nodes(const void *x1, const void *x2) {
 256   const struct file_with_size **f1, **f2;
 257
 258   f1 = (const struct file_with_size **) x1;
 259   f2 = (const struct file_with_size **) x2;
 260
 261   if((*f1)->group_id < (*f2)->group_id) {
 262     return -1;
 263   } else if((*f1)->group_id > (*f2)->group_id) {
 264     return 1;
 265   } else {
 266     return 0;
 267   }
 268 }
 269
 270
 271 void print_result(struct file_with_size *list1, struct file_with_size *list2) {
 272   struct file_with_size *node1, *node2;
 273   struct file_with_size **nodes;
 274   int nb, n;
 275
 276   nb = 0;
 277   for(node1 = list1; node1; node1 = node1->next) {
 278     if(node1->group_id >= 0) { nb++; }
 279   }
 280
 281   if(show_hits) {
 282     for(node2 = list2; node2; node2 = node2->next) {
 283       if(node2->group_id >= 0) { nb++; }
 284     }
 285   }
 286
 287   nodes = safe_malloc(nb * sizeof(struct file_with_size *));
 288
 289   n = 0;
 290   for(node1 = list1; node1; node1 = node1->next) {
 291     if(node1->group_id >= 0) {
 292       nodes[n++] = node1;
 293     }
 294   }
 295
 296   if(show_hits) {
 297     for(node2 = list2; node2; node2 = node2->next) {
 298       if(node2->group_id >= 0) {
 299         nodes[n++] = node2;
 300       }
 301     }
 302   }
 303
 304   qsort(nodes, nb, sizeof(struct file_with_size *), compare_nodes);
 305
 306   for(n = 0; n < nb; n++) {
 307     print_file(nodes[n]);
 308   }
 309
 310   free(nodes);
 311 }
 312
 313 void start(const char *dirname1, const char *dirname2) {
 314   struct file_with_size *list1, *list2;
 315   struct file_with_size *node1, *node2;
 316   struct stat sb1, sb2;
 317   int not_in, found, same_dir;
 318   int k, p, pp, l1, n;
 319
 320   if(strncmp(dirname2, "not:", 4) == 0) {
 321     not_in = 1;
 322     dirname2 += 4;
 323   } else {
 324     not_in = 0;
 325   }
 326
 327   if(lstat(dirname1, &sb1) != 0) {
 328     fprintf(stderr, "Can not stat \"%s\": %s\n", dirname1, strerror(errno));
 329     exit(EXIT_FAILURE);
 330   }
 331
 332   if(lstat(dirname2, &sb2) != 0) {
 333     fprintf(stderr, "Can not stat \"%s\": %s\n", dirname2, strerror(errno));
 334     exit(EXIT_FAILURE);
 335   }
 336
 337   same_dir = (sb1.st_ino == sb2.st_ino);
 338
 339   if(show_progress) {
 340     fprintf(stderr, "Scanning %s ... ", dirname1);
 341   }
 342
 343   list1 = scan_directory(0, dirname1);
 344
 345   if(same_dir) {
 346     list2 = list1;
 347   } else {
 348     if(show_progress) {
 349       fprintf(stderr, "%s ... ", dirname2);
 350     }
 351     list2 = scan_directory(0, dirname2);
 352   }
 353
 354   if(show_progress) {
 355     fprintf(stderr, "done.\n");
 356   }
 357
 358   k = 0;
 359   pp = -1;
 360   n = 0;
 361   l1 = file_list_length(list1);
 362
 363   if(not_in) {
 364     for(node1 = list1; node1; node1 = node1->next) {
 365       if(show_progress) {
 366         p = (100 * n)/l1;
 367         if(p > pp) {
 368           fprintf(stderr, "%d%%\n", p);
 369           pp = p;
 370         }
 371         n++;
 372       }
 373
 374       found = 0;
 375
 376       for(node2 = list2; !found && node2; node2 = node2->next) {
 377         if(node1->inode != node2->inode && same_files(node1, node2)) {
 378           found = 1;
 379         }
 380       }
 381
 382       if(!found) {
 383         if(show_realpaths) {
 384           printf("%s\n", realpath(node1->filename, 0));
 385         } else {
 386           printf("%s\n", node1->filename);
 387         }
 388       }
 389     }
 390
 391   } else {
 392     for(node1 = list1; node1; node1 = node1->next) {
 393       if(show_progress) {
 394         p = (100 * n)/l1;
 395         if(p > pp) {
 396           fprintf(stderr, "%d%%\n", p);
 397           pp = p;
 398         }
 399         n++;
 400       }
 401
 402       for(node2 = list2; node2; node2 = node2->next) {
 403         if(node1->inode != node2->inode && same_files(node1, node2)) {
 404           if(node1->group_id < 0) {
 405             if(node2->group_id >= 0) {
 406               node1->group_id = node2->group_id;
 407             } else {
 408               node1->group_id = k;
 409               k++;
 410             }
 411           }
 412           if(node2->group_id < 0) {
 413             node2->group_id = node1->group_id;
 414           }
 415         }
 416       }
 417     }
 418   }
 419
 420   print_result(list1, list2);
 421
 422   file_list_delete(list1);
 423   if(!same_dir) {
 424     file_list_delete(list2);
 425   }
 426 }
 427
 428 void print_help(FILE *out) {
 429   fprintf(out, "Usage: finddup [OPTION]... DIR1 [[not:]DIR2]\n");
 430   fprintf(out, "Version %s (%s)\n", VERSION_NUMBER, UNAME);
 431   fprintf(out, "Without DIR2, lists duplicated files found in DIR1. With DIR2, lists files common to both directories. With the not: prefix, lists files found in DIR1 which do not exist in DIR2.\n");
 432   fprintf(out, "\n");
 433   fprintf(out, "   -h   show this help\n");
 434   fprintf(out, "   -d   ignore dot files and directories\n");
 435   fprintf(out, "   -c   do not show which files in DIR2 corresponds to those in DIR1\n");
 436   fprintf(out, "   -g   do not show the file groups\n");
 437   fprintf(out, "   -p   show progress\n");
 438   fprintf(out, "   -r   show the real file paths\n");
 439   fprintf(out, "\n");
 440   fprintf(out, "Report bugs and comments to <francois@fleuret.org>\n");
 441 }
 442
 443 /**********************************************************************/
 444
 445 int main(int argc, char **argv) {
 446   int c;
 447   struct file_with_size *root;
 448
 449   root = 0;
 450
 451   setlocale (LC_ALL, "");
 452
 453   while (1) {
 454     c = getopt(argc, argv, "hrcgdp");
 455     if (c == -1)
 456       break;
 457
 458     switch (c) {
 459
 460     case 'h':
 461       print_help(stdout);
 462       exit(EXIT_SUCCESS);
 463
 464       break;
 465
 466     case 'd':
 467       ignore_dotfiles = 1;
 468       break;
 469
 470     case 'r':
 471       show_realpaths = 1;
 472       break;
 473
 474     case 'g':
 475       show_groups = 0;
 476       break;
 477
 478     case 'p':
 479       show_progress = 1;
 480       break;
 481
 482     case 'c':
 483       show_hits = 0;
 484       break;
 485
 486     default:
 487       exit(EXIT_FAILURE);
 488     }
 489   }
 490
 491   if(optind + 1 < argc) {
 492     start(argv[optind], argv[optind + 1]);
 493   } else if(optind < argc) {
 494     start(argv[optind], argv[optind]);
 495   } else {
 496     print_help(stderr);
 497     exit(EXIT_FAILURE);
 498   }
 499
 500   exit(EXIT_SUCCESS);
 501 }