fdupes.c

   1 /* FDUPES Copyright (c) 1999-2002 Adrian Lopez
   2
   3    Permission is hereby granted, free of charge, to any person
   4    obtaining a copy of this software and associated documentation files
   5    (the "Software"), to deal in the Software without restriction,
   6    including without limitation the rights to use, copy, modify, merge,
   7    publish, distribute, sublicense, and/or sell copies of the Software,
   8    and to permit persons to whom the Software is furnished to do so,
   9    subject to the following conditions:
  10
  11    The above copyright notice and this permission notice shall be
  12    included in all copies or substantial portions of the Software.
  13
  14    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  15    OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  16    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  17    IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  18    CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  19    TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  20    SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
  21
  22 #include <stdio.h>
  23 #include <stdarg.h>
  24 #include <string.h>
  25 #include <sys/stat.h>
  26 #include <dirent.h>
  27 #include <unistd.h>
  28 #include <stdlib.h>
  29 #ifndef OMIT_GETOPT_LONG
  30 #include <getopt.h>
  31 #endif
  32 #include <string.h>
  33 #include <errno.h>
  34 #include <libgen.h>
  35
  36 #include "md5/md5.h"
  37
  38 #define ISFLAG(a,b) ((a & b) == b)
  39 #define SETFLAG(a,b) (a |= b)
  40
  41 #define F_RECURSE           0x0001
  42 #define F_HIDEPROGRESS      0x0002
  43 #define F_DSAMELINE         0x0004
  44 #define F_FOLLOWLINKS       0x0008
  45 #define F_DELETEFILES       0x0010
  46 #define F_EXCLUDEEMPTY      0x0020
  47 #define F_CONSIDERHARDLINKS 0x0040
  48 #define F_SHOWSIZE          0x0080
  49 #define F_OMITFIRST         0x0100
  50 #define F_RECURSEAFTER      0x0200
  51 #define F_NOPROMPT          0x0400
  52 #define F_SUMMARIZEMATCHES  0x0800
  53 #define F_EXCLUDEHIDDEN     0x1000
  54 #define F_PERMISSIONS       0x2000
  55 #define F_REVERSE           0x4000
  56 #define F_IMMEDIATE         0x8000
  57
  58 typedef enum {
  59   ORDER_TIME = 0,
  60   ORDER_NAME
  61 } ordertype_t;
  62
  63 char *program_name;
  64
  65 unsigned long flags = 0;
  66
  67 #define CHUNK_SIZE 8192
  68
  69 #define INPUT_SIZE 256
  70
  71 #define PARTIAL_MD5_SIZE 4096
  72
  73 #define MD5_DIGEST_LENGTH 16
  74
  75 /*
  76
  77 TODO: Partial sums (for working with very large files).
  78
  79 typedef struct _signature
  80 {
  81   md5_state_t state;
  82   md5_byte_t  digest[16];
  83 } signature_t;
  84
  85 typedef struct _signatures
  86 {
  87   int         num_signatures;
  88   signature_t *signatures;
  89 } signatures_t;
  90
  91 */
  92
  93 typedef struct _file {
  94   char *d_name;
  95   off_t size;
  96   md5_byte_t *crcpartial;
  97   md5_byte_t *crcsignature;
  98   dev_t device;
  99   ino_t inode;
 100   time_t mtime;
 101   int hasdupes; /* true only if file is first on duplicate chain */
 102   struct _file *duplicates;
 103   struct _file *next;
 104 } file_t;
 105
 106 typedef struct _filetree {
 107   file_t *file;
 108   struct _filetree *left;
 109   struct _filetree *right;
 110 } filetree_t;
 111
 112 void errormsg(char *message, ...)
 113 {
 114   va_list ap;
 115
 116   va_start(ap, message);
 117
 118   fprintf(stderr, "\r%40s\r%s: ", "", program_name);
 119   vfprintf(stderr, message, ap);
 120 }
 121
 122 void escapefilename(char *escape_list, char **filename_ptr)
 123 {
 124   int x;
 125   int tx;
 126   char *tmp;
 127   char *filename;
 128
 129   filename = *filename_ptr;
 130
 131   tmp = (char*) malloc(strlen(filename) * 2 + 1);
 132   if (tmp == NULL) {
 133     errormsg("out of memory!\n");
 134     exit(1);
 135   }
 136
 137   for (x = 0, tx = 0; x < strlen(filename); x++) {
 138     if (strchr(escape_list, filename[x]) != NULL) tmp[tx++] = '\\';
 139     tmp[tx++] = filename[x];
 140   }
 141
 142   tmp[tx] = '\0';
 143
 144   if (x != tx) {
 145     *filename_ptr = realloc(*filename_ptr, strlen(tmp) + 1);
 146     if (*filename_ptr == NULL) {
 147       errormsg("out of memory!\n");
 148       exit(1);
 149     }
 150     strcpy(*filename_ptr, tmp);
 151   }
 152 }
 153
 154 off_t filesize(char *filename) {
 155   struct stat s;
 156
 157   if (stat(filename, &s) != 0) return -1;
 158
 159   return s.st_size;
 160 }
 161
 162 dev_t getdevice(char *filename) {
 163   struct stat s;
 164
 165   if (stat(filename, &s) != 0) return 0;
 166
 167   return s.st_dev;
 168 }
 169
 170 ino_t getinode(char *filename) {
 171   struct stat s;
 172
 173   if (stat(filename, &s) != 0) return 0;
 174
 175   return s.st_ino;
 176 }
 177
 178 time_t getmtime(char *filename) {
 179   struct stat s;
 180
 181   if (stat(filename, &s) != 0) return 0;
 182
 183   return s.st_mtime;
 184 }
 185
 186 char **cloneargs(int argc, char **argv)
 187 {
 188   int x;
 189   char **args;
 190
 191   args = (char **) malloc(sizeof(char*) * argc);
 192   if (args == NULL) {
 193     errormsg("out of memory!\n");
 194     exit(1);
 195   }
 196
 197   for (x = 0; x < argc; x++) {
 198     args[x] = (char*) malloc(strlen(argv[x]) + 1);
 199     if (args[x] == NULL) {
 200       free(args);
 201       errormsg("out of memory!\n");
 202       exit(1);
 203     }
 204
 205     strcpy(args[x], argv[x]);
 206   }
 207
 208   return args;
 209 }
 210
 211 int findarg(char *arg, int start, int argc, char **argv)
 212 {
 213   int x;
 214
 215   for (x = start; x < argc; x++)
 216     if (strcmp(argv[x], arg) == 0)
 217       return x;
 218
 219   return x;
 220 }
 221
 222 /* Find the first non-option argument after specified option. */
 223 int nonoptafter(char *option, int argc, char **oldargv,
 224                       char **newargv, int optind)
 225 {
 226   int x;
 227   int targetind;
 228   int testind;
 229   int startat = 1;
 230
 231   targetind = findarg(option, 1, argc, oldargv);
 232
 233   for (x = optind; x < argc; x++) {
 234     testind = findarg(newargv[x], startat, argc, oldargv);
 235     if (testind > targetind) return x;
 236     else startat = testind;
 237   }
 238
 239   return x;
 240 }
 241
 242 int grokdir(char *dir, file_t **filelistp)
 243 {
 244   DIR *cd;
 245   file_t *newfile;
 246   struct dirent *dirinfo;
 247   int lastchar;
 248   int filecount = 0;
 249   struct stat info;
 250   struct stat linfo;
 251   static int progress = 0;
 252   static char indicator[] = "-\\|/";
 253   char *fullname, *name;
 254
 255   cd = opendir(dir);
 256
 257   if (!cd) {
 258     errormsg("could not chdir to %s\n", dir);
 259     return 0;
 260   }
 261
 262   while ((dirinfo = readdir(cd)) != NULL) {
 263     if (strcmp(dirinfo->d_name, ".") && strcmp(dirinfo->d_name, "..")) {
 264       if (!ISFLAG(flags, F_HIDEPROGRESS)) {
 265         fprintf(stderr, "\rBuilding file list %c ", indicator[progress]);
 266         progress = (progress + 1) % 4;
 267       }
 268
 269       newfile = (file_t*) malloc(sizeof(file_t));
 270
 271       if (!newfile) {
 272         errormsg("out of memory!\n");
 273         closedir(cd);
 274         exit(1);
 275       } else newfile->next = *filelistp;
 276
 277       newfile->device = 0;
 278       newfile->inode = 0;
 279       newfile->crcsignature = NULL;
 280       newfile->crcpartial = NULL;
 281       newfile->duplicates = NULL;
 282       newfile->hasdupes = 0;
 283
 284       newfile->d_name = (char*)malloc(strlen(dir)+strlen(dirinfo->d_name)+2);
 285
 286       if (!newfile->d_name) {
 287         errormsg("out of memory!\n");
 288         free(newfile);
 289         closedir(cd);
 290         exit(1);
 291       }
 292
 293       strcpy(newfile->d_name, dir);
 294       lastchar = strlen(dir) - 1;
 295       if (lastchar >= 0 && dir[lastchar] != '/')
 296         strcat(newfile->d_name, "/");
 297       strcat(newfile->d_name, dirinfo->d_name);
 298
 299       if (ISFLAG(flags, F_EXCLUDEHIDDEN)) {
 300         fullname = strdup(newfile->d_name);
 301         name = basename(fullname);
 302         if (name[0] == '.' && strcmp(name, ".") && strcmp(name, "..") ) {
 303           free(newfile->d_name);
 304           free(newfile);
 305           continue;
 306         }
 307         free(fullname);
 308       }
 309
 310       if (filesize(newfile->d_name) == 0 && ISFLAG(flags, F_EXCLUDEEMPTY)) {
 311         free(newfile->d_name);
 312         free(newfile);
 313         continue;
 314       }
 315
 316       if (stat(newfile->d_name, &info) == -1) {
 317         free(newfile->d_name);
 318         free(newfile);
 319         continue;
 320       }
 321
 322       if (lstat(newfile->d_name, &linfo) == -1) {
 323         free(newfile->d_name);
 324         free(newfile);
 325         continue;
 326       }
 327
 328       if (S_ISDIR(info.st_mode)) {
 329         if (ISFLAG(flags, F_RECURSE) && (ISFLAG(flags, F_FOLLOWLINKS) || !S_ISLNK(linfo.st_mode)))
 330           filecount += grokdir(newfile->d_name, filelistp);
 331         free(newfile->d_name);
 332         free(newfile);
 333       } else {
 334         if (S_ISREG(linfo.st_mode) || (S_ISLNK(linfo.st_mode) && ISFLAG(flags, F_FOLLOWLINKS))) {
 335           *filelistp = newfile;
 336           filecount++;
 337         } else {
 338           free(newfile->d_name);
 339           free(newfile);
 340         }
 341       }
 342     }
 343   }
 344
 345   closedir(cd);
 346
 347   return filecount;
 348 }
 349
 350 md5_byte_t *getcrcsignatureuntil(char *filename, off_t max_read)
 351 {
 352   off_t fsize;
 353   off_t toread;
 354   md5_state_t state;
 355   static md5_byte_t digest[MD5_DIGEST_LENGTH];
 356   static md5_byte_t chunk[CHUNK_SIZE];
 357   FILE *file;
 358
 359   md5_init(&state);
 360
 361
 362   fsize = filesize(filename);
 363
 364   if (max_read != 0 && fsize > max_read)
 365     fsize = max_read;
 366
 367   file = fopen(filename, "rb");
 368   if (file == NULL) {
 369     errormsg("error opening file %s\n", filename);
 370     return NULL;
 371   }
 372
 373   while (fsize > 0) {
 374     toread = (fsize >= CHUNK_SIZE) ? CHUNK_SIZE : fsize;
 375     if (fread(chunk, toread, 1, file) != 1) {
 376       errormsg("error reading from file %s\n", filename);
 377       fclose(file);
 378       return NULL;
 379     }
 380     md5_append(&state, chunk, toread);
 381     fsize -= toread;
 382   }
 383
 384   md5_finish(&state, digest);
 385
 386   fclose(file);
 387
 388   return digest;
 389 }
 390
 391 md5_byte_t *getcrcsignature(char *filename)
 392 {
 393   return getcrcsignatureuntil(filename, 0);
 394 }
 395
 396 md5_byte_t *getcrcpartialsignature(char *filename)
 397 {
 398   return getcrcsignatureuntil(filename, PARTIAL_MD5_SIZE);
 399 }
 400
 401 int md5cmp(const md5_byte_t *a, const md5_byte_t *b)
 402 {
 403   int x;
 404
 405   for (x = 0; x < MD5_DIGEST_LENGTH; ++x)
 406   {
 407     if (a[x] < b[x])
 408       return -1;
 409     else if (a[x] > b[x])
 410       return 1;
 411   }
 412
 413   return 0;
 414 }
 415
 416 void md5copy(md5_byte_t *to, const md5_byte_t *from)
 417 {
 418   int x;
 419
 420   for (x = 0; x < MD5_DIGEST_LENGTH; ++x)
 421     to[x] = from[x];
 422 }
 423
 424 void purgetree(filetree_t *checktree)
 425 {
 426   if (checktree->left != NULL) purgetree(checktree->left);
 427
 428   if (checktree->right != NULL) purgetree(checktree->right);
 429
 430   free(checktree);
 431 }
 432
 433 void getfilestats(file_t *file)
 434 {
 435   file->size = filesize(file->d_name);
 436   file->inode = getinode(file->d_name);
 437   file->device = getdevice(file->d_name);
 438   file->mtime = getmtime(file->d_name);
 439 }
 440
 441 int registerfile(filetree_t **branch, file_t *file)
 442 {
 443   getfilestats(file);
 444
 445   *branch = (filetree_t*) malloc(sizeof(filetree_t));
 446   if (*branch == NULL) {
 447     errormsg("out of memory!\n");
 448     exit(1);
 449   }
 450
 451   (*branch)->file = file;
 452   (*branch)->left = NULL;
 453   (*branch)->right = NULL;
 454
 455   return 1;
 456 }
 457
 458 int same_permissions(char* name1, char* name2)
 459 {
 460     struct stat s1, s2;
 461
 462     if (stat(name1, &s1) != 0) return -1;
 463     if (stat(name2, &s2) != 0) return -1;
 464
 465     return (s1.st_mode == s2.st_mode &&
 466             s1.st_uid == s2.st_uid &&
 467             s1.st_gid == s2.st_gid);
 468 }
 469
 470 int is_hardlink(filetree_t *checktree, file_t *file)
 471 {
 472   file_t *dupe;
 473   ino_t inode;
 474   dev_t device;
 475
 476   inode = getinode(file->d_name);
 477   device = getdevice(file->d_name);
 478
 479   if ((inode == checktree->file->inode) &&
 480       (device == checktree->file->device))
 481         return 1;
 482
 483   if (checktree->file->hasdupes)
 484   {
 485     dupe = checktree->file->duplicates;
 486
 487     do {
 488       if ((inode == dupe->inode) &&
 489           (device == dupe->device))
 490             return 1;
 491
 492       dupe = dupe->duplicates;
 493     } while (dupe != NULL);
 494   }
 495
 496   return 0;
 497 }
 498
 499 file_t **checkmatch(filetree_t **root, filetree_t *checktree, file_t *file)
 500 {
 501   int cmpresult;
 502   md5_byte_t *crcsignature;
 503   off_t fsize;
 504
 505   /* If device and inode fields are equal one of the files is a
 506      hard link to the other or the files have been listed twice
 507      unintentionally. We don't want to flag these files as
 508      duplicates unless the user specifies otherwise.
 509   */
 510
 511   if (!ISFLAG(flags, F_CONSIDERHARDLINKS) && is_hardlink(checktree, file))
 512     return NULL;
 513
 514   fsize = filesize(file->d_name);
 515
 516   if (fsize < checktree->file->size)
 517     cmpresult = -1;
 518   else
 519     if (fsize > checktree->file->size) cmpresult = 1;
 520   else
 521     if (ISFLAG(flags, F_PERMISSIONS) &&
 522         !same_permissions(file->d_name, checktree->file->d_name))
 523         cmpresult = -1;
 524   else {
 525     if (checktree->file->crcpartial == NULL) {
 526       crcsignature = getcrcpartialsignature(checktree->file->d_name);
 527       if (crcsignature == NULL) {
 528         errormsg ("cannot read file %s\n", checktree->file->d_name);
 529         return NULL;
 530       }
 531
 532       checktree->file->crcpartial = (md5_byte_t*) malloc(MD5_DIGEST_LENGTH * sizeof(md5_byte_t));
 533       if (checktree->file->crcpartial == NULL) {
 534         errormsg("out of memory\n");
 535         exit(1);
 536       }
 537       md5copy(checktree->file->crcpartial, crcsignature);
 538     }
 539
 540     if (file->crcpartial == NULL) {
 541       crcsignature = getcrcpartialsignature(file->d_name);
 542       if (crcsignature == NULL) {
 543         errormsg ("cannot read file %s\n", file->d_name);
 544         return NULL;
 545       }
 546
 547       file->crcpartial = (md5_byte_t*) malloc(MD5_DIGEST_LENGTH * sizeof(md5_byte_t));
 548       if (file->crcpartial == NULL) {
 549         errormsg("out of memory\n");
 550         exit(1);
 551       }
 552       md5copy(file->crcpartial, crcsignature);
 553     }
 554
 555     cmpresult = md5cmp(file->crcpartial, checktree->file->crcpartial);
 556     /*if (cmpresult != 0) errormsg("    on %s vs %s\n", file->d_name, checktree->file->d_name);*/
 557
 558     if (cmpresult == 0) {
 559       if (checktree->file->crcsignature == NULL) {
 560         crcsignature = getcrcsignature(checktree->file->d_name);
 561         if (crcsignature == NULL) return NULL;
 562
 563         checktree->file->crcsignature = (md5_byte_t*) malloc(MD5_DIGEST_LENGTH * sizeof(md5_byte_t));
 564         if (checktree->file->crcsignature == NULL) {
 565           errormsg("out of memory\n");
 566           exit(1);
 567         }
 568         md5copy(checktree->file->crcsignature, crcsignature);
 569       }
 570
 571       if (file->crcsignature == NULL) {
 572         crcsignature = getcrcsignature(file->d_name);
 573         if (crcsignature == NULL) return NULL;
 574
 575         file->crcsignature = (md5_byte_t*) malloc(MD5_DIGEST_LENGTH * sizeof(md5_byte_t));
 576         if (file->crcsignature == NULL) {
 577           errormsg("out of memory\n");
 578           exit(1);
 579         }
 580         md5copy(file->crcsignature, crcsignature);
 581       }
 582
 583       cmpresult = md5cmp(file->crcsignature, checktree->file->crcsignature);
 584       /*if (cmpresult != 0) errormsg("P   on %s vs %s\n",
 585           file->d_name, checktree->file->d_name);
 586       else errormsg("P F on %s vs %s\n", file->d_name,
 587           checktree->file->d_name);
 588       printf("%s matches %s\n", file->d_name, checktree->file->d_name);*/
 589     }
 590   }
 591
 592   if (cmpresult < 0) {
 593     if (checktree->left != NULL) {
 594       return checkmatch(root, checktree->left, file);
 595     } else {
 596       registerfile(&(checktree->left), file);
 597       return NULL;
 598     }
 599   } else if (cmpresult > 0) {
 600     if (checktree->right != NULL) {
 601       return checkmatch(root, checktree->right, file);
 602     } else {
 603       registerfile(&(checktree->right), file);
 604       return NULL;
 605     }
 606   } else
 607   {
 608     getfilestats(file);
 609     return &checktree->file;
 610   }
 611 }
 612
 613 /* Do a bit-for-bit comparison in case two different files produce the
 614    same signature. Unlikely, but better safe than sorry. */
 615
 616 int confirmmatch(FILE *file1, FILE *file2)
 617 {
 618   unsigned char c1[CHUNK_SIZE];
 619   unsigned char c2[CHUNK_SIZE];
 620   size_t r1;
 621   size_t r2;
 622
 623   fseek(file1, 0, SEEK_SET);
 624   fseek(file2, 0, SEEK_SET);
 625
 626   do {
 627     r1 = fread(c1, sizeof(unsigned char), sizeof(c1), file1);
 628     r2 = fread(c2, sizeof(unsigned char), sizeof(c2), file2);
 629
 630     if (r1 != r2) return 0; /* file lengths are different */
 631     if (memcmp (c1, c2, r1)) return 0; /* file contents are different */
 632   } while (r2);
 633
 634   return 1;
 635 }
 636
 637 void summarizematches(file_t *files)
 638 {
 639   int numsets = 0;
 640   double numbytes = 0.0;
 641   int numfiles = 0;
 642   file_t *tmpfile;
 643
 644   while (files != NULL)
 645   {
 646     if (files->hasdupes)
 647     {
 648       numsets++;
 649
 650       tmpfile = files->duplicates;
 651       while (tmpfile != NULL)
 652       {
 653         numfiles++;
 654         numbytes += files->size;
 655         tmpfile = tmpfile->duplicates;
 656       }
 657     }
 658
 659     files = files->next;
 660   }
 661
 662   if (numsets == 0)
 663     printf("No duplicates found.\n\n");
 664   else
 665   {
 666     if (numbytes < 1024.0)
 667       printf("%d duplicate files (in %d sets), occupying %.0f bytes.\n\n", numfiles, numsets, numbytes);
 668     else if (numbytes <= (1000.0 * 1000.0))
 669       printf("%d duplicate files (in %d sets), occupying %.1f kilobytes\n\n", numfiles, numsets, numbytes / 1000.0);
 670     else
 671       printf("%d duplicate files (in %d sets), occupying %.1f megabytes\n\n", numfiles, numsets, numbytes / (1000.0 * 1000.0));
 672
 673   }
 674 }
 675
 676 void printmatches(file_t *files)
 677 {
 678   file_t *tmpfile;
 679
 680   while (files != NULL) {
 681     if (files->hasdupes) {
 682       if (!ISFLAG(flags, F_OMITFIRST)) {
 683         if (ISFLAG(flags, F_SHOWSIZE)) printf("%lld byte%seach:\n", (long long int)files->size,
 684          (files->size != 1) ? "s " : " ");
 685         if (ISFLAG(flags, F_DSAMELINE)) escapefilename("\\ ", &files->d_name);
 686         printf("%s%c", files->d_name, ISFLAG(flags, F_DSAMELINE)?' ':'\n');
 687       }
 688       tmpfile = files->duplicates;
 689       while (tmpfile != NULL) {
 690         if (ISFLAG(flags, F_DSAMELINE)) escapefilename("\\ ", &tmpfile->d_name);
 691         printf("%s%c", tmpfile->d_name, ISFLAG(flags, F_DSAMELINE)?' ':'\n');
 692         tmpfile = tmpfile->duplicates;
 693       }
 694       printf("\n");
 695
 696     }
 697
 698     files = files->next;
 699   }
 700 }
 701
 702 /*
 703 #define REVISE_APPEND "_tmp"
 704 char *revisefilename(char *path, int seq)
 705 {
 706   int digits;
 707   char *newpath;
 708   char *scratch;
 709   char *dot;
 710
 711   digits = numdigits(seq);
 712   newpath = malloc(strlen(path) + strlen(REVISE_APPEND) + digits + 1);
 713   if (!newpath) return newpath;
 714
 715   scratch = malloc(strlen(path) + 1);
 716   if (!scratch) return newpath;
 717
 718   strcpy(scratch, path);
 719   dot = strrchr(scratch, '.');
 720   if (dot)
 721   {
 722     *dot = 0;
 723     sprintf(newpath, "%s%s%d.%s", scratch, REVISE_APPEND, seq, dot + 1);
 724   }
 725
 726   else
 727   {
 728     sprintf(newpath, "%s%s%d", path, REVISE_APPEND, seq);
 729   }
 730
 731   free(scratch);
 732
 733   return newpath;
 734 } */
 735
 736 int relink(char *oldfile, char *newfile)
 737 {
 738   dev_t od;
 739   dev_t nd;
 740   ino_t oi;
 741   ino_t ni;
 742
 743   od = getdevice(oldfile);
 744   oi = getinode(oldfile);
 745
 746   if (link(oldfile, newfile) != 0)
 747     return 0;
 748
 749   /* make sure we're working with the right file (the one we created) */
 750   nd = getdevice(newfile);
 751   ni = getinode(newfile);
 752
 753   if (nd != od || oi != ni)
 754     return 0; /* file is not what we expected */
 755
 756   return 1;
 757 }
 758
 759 void deletefiles(file_t *files, int prompt, FILE *tty)
 760 {
 761   int counter;
 762   int groups = 0;
 763   int curgroup = 0;
 764   file_t *tmpfile;
 765   file_t *curfile;
 766   file_t **dupelist;
 767   int *preserve;
 768   char *preservestr;
 769   char *token;
 770   char *tstr;
 771   int number;
 772   int sum;
 773   int max = 0;
 774   int x;
 775   int i;
 776
 777   curfile = files;
 778
 779   while (curfile) {
 780     if (curfile->hasdupes) {
 781       counter = 1;
 782       groups++;
 783
 784       tmpfile = curfile->duplicates;
 785       while (tmpfile) {
 786         counter++;
 787         tmpfile = tmpfile->duplicates;
 788       }
 789
 790       if (counter > max) max = counter;
 791     }
 792
 793     curfile = curfile->next;
 794   }
 795
 796   max++;
 797
 798   dupelist = (file_t**) malloc(sizeof(file_t*) * max);
 799   preserve = (int*) malloc(sizeof(int) * max);
 800   preservestr = (char*) malloc(INPUT_SIZE);
 801
 802   if (!dupelist || !preserve || !preservestr) {
 803     errormsg("out of memory\n");
 804     exit(1);
 805   }
 806
 807   while (files) {
 808     if (files->hasdupes) {
 809       curgroup++;
 810       counter = 1;
 811       dupelist[counter] = files;
 812
 813       if (prompt) printf("[%d] %s\n", counter, files->d_name);
 814
 815       tmpfile = files->duplicates;
 816
 817       while (tmpfile) {
 818         dupelist[++counter] = tmpfile;
 819         if (prompt) printf("[%d] %s\n", counter, tmpfile->d_name);
 820         tmpfile = tmpfile->duplicates;
 821       }
 822
 823       if (prompt) printf("\n");
 824
 825       if (!prompt) /* preserve only the first file */
 826       {
 827          preserve[1] = 1;
 828          for (x = 2; x <= counter; x++) preserve[x] = 0;
 829       }
 830
 831       else /* prompt for files to preserve */
 832
 833       do {
 834         printf("Set %d of %d, preserve files [1 - %d, all]",
 835           curgroup, groups, counter);
 836         if (ISFLAG(flags, F_SHOWSIZE)) printf(" (%lld byte%seach)", (long long int)files->size,
 837           (files->size != 1) ? "s " : " ");
 838         printf(": ");
 839         fflush(stdout);
 840
 841         if (!fgets(preservestr, INPUT_SIZE, tty))
 842           preservestr[0] = '\n'; /* treat fgets() failure as if nothing was entered */
 843
 844         i = strlen(preservestr) - 1;
 845
 846         while (preservestr[i]!='\n'){ /* tail of buffer must be a newline */
 847           tstr = (char*)
 848             realloc(preservestr, strlen(preservestr) + 1 + INPUT_SIZE);
 849           if (!tstr) { /* couldn't allocate memory, treat as fatal */
 850             errormsg("out of memory!\n");
 851             exit(1);
 852           }
 853
 854           preservestr = tstr;
 855           if (!fgets(preservestr + i + 1, INPUT_SIZE, tty))
 856           {
 857             preservestr[0] = '\n'; /* treat fgets() failure as if nothing was entered */
 858             break;
 859           }
 860           i = strlen(preservestr)-1;
 861         }
 862
 863         for (x = 1; x <= counter; x++) preserve[x] = 0;
 864
 865         token = strtok(preservestr, " ,\n");
 866
 867         while (token != NULL) {
 868           if (strcasecmp(token, "all") == 0)
 869             for (x = 0; x <= counter; x++) preserve[x] = 1;
 870
 871           number = 0;
 872           sscanf(token, "%d", &number);
 873           if (number > 0 && number <= counter) preserve[number] = 1;
 874
 875           token = strtok(NULL, " ,\n");
 876         }
 877
 878         for (sum = 0, x = 1; x <= counter; x++) sum += preserve[x];
 879       } while (sum < 1); /* make sure we've preserved at least one file */
 880
 881       printf("\n");
 882
 883       for (x = 1; x <= counter; x++) {
 884         if (preserve[x])
 885           printf("   [+] %s\n", dupelist[x]->d_name);
 886         else {
 887           if (remove(dupelist[x]->d_name) == 0) {
 888             printf("   [-] %s\n", dupelist[x]->d_name);
 889           } else {
 890             printf("   [!] %s ", dupelist[x]->d_name);
 891             printf("-- unable to delete file!\n");
 892           }
 893         }
 894       }
 895       printf("\n");
 896     }
 897
 898     files = files->next;
 899   }
 900
 901   free(dupelist);
 902   free(preserve);
 903   free(preservestr);
 904 }
 905
 906 int sort_pairs_by_arrival(file_t *f1, file_t *f2)
 907 {
 908   if (f2->duplicates != 0)
 909     return !ISFLAG(flags, F_REVERSE) ? 1 : -1;
 910
 911   return !ISFLAG(flags, F_REVERSE) ? -1 : 1;
 912 }
 913
 914 int sort_pairs_by_mtime(file_t *f1, file_t *f2)
 915 {
 916   if (f1->mtime < f2->mtime)
 917     return !ISFLAG(flags, F_REVERSE) ? -1 : 1;
 918   else if (f1->mtime > f2->mtime)
 919     return !ISFLAG(flags, F_REVERSE) ? 1 : -1;
 920
 921   return 0;
 922 }
 923
 924 int sort_pairs_by_filename(file_t *f1, file_t *f2)
 925 {
 926   return strcmp(f1->d_name, f2->d_name);
 927 }
 928
 929 void registerpair(file_t **matchlist, file_t *newmatch,
 930                   int (*comparef)(file_t *f1, file_t *f2))
 931 {
 932   file_t *traverse;
 933   file_t *back;
 934
 935   (*matchlist)->hasdupes = 1;
 936
 937   back = 0;
 938   traverse = *matchlist;
 939   while (traverse)
 940   {
 941     if (comparef(newmatch, traverse) <= 0)
 942     {
 943       newmatch->duplicates = traverse;
 944
 945       if (back == 0)
 946       {
 947         *matchlist = newmatch; /* update pointer to head of list */
 948
 949         newmatch->hasdupes = 1;
 950         traverse->hasdupes = 0; /* flag is only for first file in dupe chain */
 951       }
 952       else
 953         back->duplicates = newmatch;
 954
 955       break;
 956     }
 957     else
 958     {
 959       if (traverse->duplicates == 0)
 960       {
 961         traverse->duplicates = newmatch;
 962
 963         if (back == 0)
 964           traverse->hasdupes = 1;
 965
 966         break;
 967       }
 968     }
 969
 970     back = traverse;
 971     traverse = traverse->duplicates;
 972   }
 973 }
 974
 975 void deletesuccessor(file_t **existing, file_t *duplicate,
 976       int (*comparef)(file_t *f1, file_t *f2))
 977 {
 978   file_t *to_keep;
 979   file_t *to_delete;
 980
 981   if (comparef(duplicate, *existing) >= 0)
 982   {
 983     to_keep = *existing;
 984     to_delete = duplicate;
 985   }
 986   else
 987   {
 988     to_keep = duplicate;
 989     to_delete = *existing;
 990
 991     *existing = duplicate;
 992   }
 993
 994   if (!ISFLAG(flags, F_HIDEPROGRESS)) fprintf(stderr, "\r%40s\r", " ");
 995
 996   printf("   [+] %s\n", to_keep->d_name);
 997   if (remove(to_delete->d_name) == 0) {
 998     printf("   [-] %s\n", to_delete->d_name);
 999   } else {
1000     printf("   [!] %s ", to_delete->d_name);
1001     printf("-- unable to delete file!\n");
1002   }
1003
1004   printf("\n");
1005 }
1006
1007 void help_text()
1008 {
1009   printf("Usage: fdupes [options] DIRECTORY...\n\n");
1010
1011   printf(" -r --recurse     \tfor every directory given follow subdirectories\n");
1012   printf("                  \tencountered within\n");
1013   printf(" -R --recurse:    \tfor each directory given after this option follow\n");
1014   printf("                  \tsubdirectories encountered within (note the ':' at\n");
1015   printf("                  \tthe end of the option, manpage for more details)\n");
1016   printf(" -s --symlinks    \tfollow symlinks\n");
1017   printf(" -H --hardlinks   \tnormally, when two or more files point to the same\n");
1018   printf("                  \tdisk area they are treated as non-duplicates; this\n");
1019   printf("                  \toption will change this behavior\n");
1020   printf(" -n --noempty     \texclude zero-length files from consideration\n");
1021   printf(" -A --nohidden    \texclude hidden files from consideration\n");
1022   printf(" -f --omitfirst   \tomit the first file in each set of matches\n");
1023   printf(" -1 --sameline    \tlist each set of matches on a single line\n");
1024   printf(" -S --size        \tshow size of duplicate files\n");
1025   printf(" -m --summarize   \tsummarize dupe information\n");
1026   printf(" -q --quiet       \thide progress indicator\n");
1027   printf(" -d --delete      \tprompt user for files to preserve and delete all\n");
1028   printf("                  \tothers; important: under particular circumstances,\n");
1029   printf("                  \tdata may be lost when using this option together\n");
1030   printf("                  \twith -s or --symlinks, or when specifying a\n");
1031   printf("                  \tparticular directory more than once; refer to the\n");
1032   printf("                  \tfdupes documentation for additional information\n");
1033   /*printf(" -l --relink      \t(description)\n");*/
1034   printf(" -N --noprompt    \ttogether with --delete, preserve the first file in\n");
1035   printf("                  \teach set of duplicates and delete the rest without\n");
1036   printf("                  \tprompting the user\n");
1037   printf(" -I --immediate   \tdelete duplicates as they are encountered, without\n");
1038   printf("                  \tgrouping into sets; implies --noprompt\n");
1039   printf(" -p --permissions \tdon't consider files with different owner/group or\n");
1040   printf("                  \tpermission bits as duplicates\n");
1041   printf(" -o --order=BY    \tselect sort order for output, linking and deleting; by\n");
1042   printf("                  \tmtime (BY='time'; default) or filename (BY='name')\n");
1043   printf(" -i --reverse     \treverse order while sorting\n");
1044   printf(" -v --version     \tdisplay fdupes version\n");
1045   printf(" -h --help        \tdisplay this help message\n\n");
1046 #ifdef OMIT_GETOPT_LONG
1047   printf("Note: Long options are not supported in this fdupes build.\n\n");
1048 #endif
1049 }
1050
1051 int main(int argc, char **argv) {
1052   int x;
1053   int opt;
1054   FILE *file1;
1055   FILE *file2;
1056   file_t *files = NULL;
1057   file_t *curfile;
1058   file_t **match = NULL;
1059   filetree_t *checktree = NULL;
1060   int filecount = 0;
1061   int progress = 0;
1062   char **oldargv;
1063   int firstrecurse;
1064   ordertype_t ordertype = ORDER_TIME;
1065
1066 #ifndef OMIT_GETOPT_LONG
1067   static struct option long_options[] =
1068   {
1069     { "omitfirst", 0, 0, 'f' },
1070     { "recurse", 0, 0, 'r' },
1071     { "recursive", 0, 0, 'r' },
1072     { "recurse:", 0, 0, 'R' },
1073     { "recursive:", 0, 0, 'R' },
1074     { "quiet", 0, 0, 'q' },
1075     { "sameline", 0, 0, '1' },
1076     { "size", 0, 0, 'S' },
1077     { "symlinks", 0, 0, 's' },
1078     { "hardlinks", 0, 0, 'H' },
1079     { "relink", 0, 0, 'l' },
1080     { "noempty", 0, 0, 'n' },
1081     { "nohidden", 0, 0, 'A' },
1082     { "delete", 0, 0, 'd' },
1083     { "version", 0, 0, 'v' },
1084     { "help", 0, 0, 'h' },
1085     { "noprompt", 0, 0, 'N' },
1086     { "immediate", 0, 0, 'I'},
1087     { "summarize", 0, 0, 'm'},
1088     { "summary", 0, 0, 'm' },
1089     { "permissions", 0, 0, 'p' },
1090     { "order", 1, 0, 'o' },
1091     { "reverse", 0, 0, 'i' },
1092     { 0, 0, 0, 0 }
1093   };
1094 #define GETOPT getopt_long
1095 #else
1096 #define GETOPT getopt
1097 #endif
1098
1099   program_name = argv[0];
1100
1101   oldargv = cloneargs(argc, argv);
1102
1103   while ((opt = GETOPT(argc, argv, "frRq1SsHlnAdvhNImpo:i"
1104 #ifndef OMIT_GETOPT_LONG
1105           , long_options, NULL
1106 #endif
1107           )) != EOF) {
1108     switch (opt) {
1109     case 'f':
1110       SETFLAG(flags, F_OMITFIRST);
1111       break;
1112     case 'r':
1113       SETFLAG(flags, F_RECURSE);
1114       break;
1115     case 'R':
1116       SETFLAG(flags, F_RECURSEAFTER);
1117       break;
1118     case 'q':
1119       SETFLAG(flags, F_HIDEPROGRESS);
1120       break;
1121     case '1':
1122       SETFLAG(flags, F_DSAMELINE);
1123       break;
1124     case 'S':
1125       SETFLAG(flags, F_SHOWSIZE);
1126       break;
1127     case 's':
1128       SETFLAG(flags, F_FOLLOWLINKS);
1129       break;
1130     case 'H':
1131       SETFLAG(flags, F_CONSIDERHARDLINKS);
1132       break;
1133     case 'n':
1134       SETFLAG(flags, F_EXCLUDEEMPTY);
1135       break;
1136     case 'A':
1137       SETFLAG(flags, F_EXCLUDEHIDDEN);
1138       break;
1139     case 'd':
1140       SETFLAG(flags, F_DELETEFILES);
1141       break;
1142     case 'v':
1143       printf("fdupes %s\n", VERSION);
1144       exit(0);
1145     case 'h':
1146       help_text();
1147       exit(1);
1148     case 'N':
1149       SETFLAG(flags, F_NOPROMPT);
1150       break;
1151     case 'I':
1152       SETFLAG(flags, F_IMMEDIATE);
1153       break;
1154     case 'm':
1155       SETFLAG(flags, F_SUMMARIZEMATCHES);
1156       break;
1157     case 'p':
1158       SETFLAG(flags, F_PERMISSIONS);
1159       break;
1160     case 'o':
1161       if (!strcasecmp("name", optarg)) {
1162         ordertype = ORDER_NAME;
1163       } else if (!strcasecmp("time", optarg)) {
1164         ordertype = ORDER_TIME;
1165       } else {
1166         errormsg("invalid value for --order: '%s'\n", optarg);
1167         exit(1);
1168       }
1169       break;
1170     case 'i':
1171       SETFLAG(flags, F_REVERSE);
1172       break;
1173
1174     default:
1175       fprintf(stderr, "Try `fdupes --help' for more information.\n");
1176       exit(1);
1177     }
1178   }
1179
1180   if (optind >= argc) {
1181     errormsg("no directories specified\n");
1182     exit(1);
1183   }
1184
1185   if (ISFLAG(flags, F_RECURSE) && ISFLAG(flags, F_RECURSEAFTER)) {
1186     errormsg("options --recurse and --recurse: are not compatible\n");
1187     exit(1);
1188   }
1189
1190   if (ISFLAG(flags, F_SUMMARIZEMATCHES) && ISFLAG(flags, F_DELETEFILES)) {
1191     errormsg("options --summarize and --delete are not compatible\n");
1192     exit(1);
1193   }
1194
1195   if (ISFLAG(flags, F_RECURSEAFTER)) {
1196     firstrecurse = nonoptafter("--recurse:", argc, oldargv, argv, optind);
1197
1198     if (firstrecurse == argc)
1199       firstrecurse = nonoptafter("-R", argc, oldargv, argv, optind);
1200
1201     if (firstrecurse == argc) {
1202       errormsg("-R option must be isolated from other options\n");
1203       exit(1);
1204     }
1205
1206     /* F_RECURSE is not set for directories before --recurse: */
1207     for (x = optind; x < firstrecurse; x++)
1208       filecount += grokdir(argv[x], &files);
1209
1210     /* Set F_RECURSE for directories after --recurse: */
1211     SETFLAG(flags, F_RECURSE);
1212
1213     for (x = firstrecurse; x < argc; x++)
1214       filecount += grokdir(argv[x], &files);
1215   } else {
1216     for (x = optind; x < argc; x++)
1217       filecount += grokdir(argv[x], &files);
1218   }
1219
1220   if (!files) {
1221     if (!ISFLAG(flags, F_HIDEPROGRESS)) fprintf(stderr, "\r%40s\r", " ");
1222     exit(0);
1223   }
1224
1225   curfile = files;
1226
1227   while (curfile) {
1228     if (!checktree)
1229       registerfile(&checktree, curfile);
1230     else
1231       match = checkmatch(&checktree, checktree, curfile);
1232
1233     if (match != NULL) {
1234       file1 = fopen(curfile->d_name, "rb");
1235       if (!file1) {
1236         curfile = curfile->next;
1237         continue;
1238       }
1239
1240       file2 = fopen((*match)->d_name, "rb");
1241       if (!file2) {
1242         fclose(file1);
1243         curfile = curfile->next;
1244         continue;
1245       }
1246
1247       if (confirmmatch(file1, file2)) {
1248         if (ISFLAG(flags, F_DELETEFILES) && ISFLAG(flags, F_IMMEDIATE))
1249           deletesuccessor(match, curfile,
1250               (ordertype == ORDER_TIME) ? sort_pairs_by_mtime : sort_pairs_by_filename );
1251         else
1252           registerpair(match, curfile,
1253               (ordertype == ORDER_TIME) ? sort_pairs_by_mtime : sort_pairs_by_filename );
1254       }
1255
1256       fclose(file1);
1257       fclose(file2);
1258     }
1259
1260     curfile = curfile->next;
1261
1262     if (!ISFLAG(flags, F_HIDEPROGRESS)) {
1263       fprintf(stderr, "\rProgress [%d/%d] %d%% ", progress, filecount,
1264        (int)((float) progress / (float) filecount * 100.0));
1265       progress++;
1266     }
1267   }
1268
1269   if (!ISFLAG(flags, F_HIDEPROGRESS)) fprintf(stderr, "\r%40s\r", " ");
1270
1271   if (ISFLAG(flags, F_DELETEFILES))
1272   {
1273     if (ISFLAG(flags, F_NOPROMPT))
1274     {
1275       deletefiles(files, 0, 0);
1276     }
1277     else
1278     {
1279       if (freopen("/dev/tty", "r", stdin) == 0)
1280       {
1281         errormsg("could not open terminal for input\n");
1282         exit(1);
1283       }
1284
1285       deletefiles(files, 1, stdin);
1286     }
1287   }
1288
1289   else
1290
1291     if (ISFLAG(flags, F_SUMMARIZEMATCHES))
1292       summarizematches(files);
1293
1294     else
1295
1296       printmatches(files);
1297
1298   while (files) {
1299     curfile = files->next;
1300     free(files->d_name);
1301     free(files->crcsignature);
1302     free(files->crcpartial);
1303     free(files);
1304     files = curfile;
1305   }
1306
1307   for (x = 0; x < argc; x++)
1308     free(oldargv[x]);
1309
1310   free(oldargv);
1311
1312   purgetree(checktree);
1313
1314   return 0;
1315 }