text: /*
   * duff - Duplicate file finder
   * Copyright (c) 2005 Camilla Berglund <elmindreda@users.sourceforge.net>
   *
   * This software is provided 'as-is', without any express or implied
   * warranty. In no event will the authors be held liable for any
   * damages arising from the use of this software.
   *
   * Permission is granted to anyone to use this software for any
   * purpose, including commercial applications, and to alter it and
   * redistribute it freely, subject to the following restrictions:
   *
   *  1. The origin of this software must not be misrepresented; you
   *     must not claim that you wrote the original software. If you use
   *     this software in a product, an acknowledgment in the product
   *     documentation would be appreciated but is not required.
   *
   *  2. Altered source versions must be plainly marked as such, and
   *     must not be misrepresented as being the original software.
   *
   *  3. This notice may not be removed or altered from any source
   *     distribution.
   */
  
  #if HAVE_CONFIG_H
  #include "config.h"
  #endif
  
  #define _GNU_SOURCE
  
  #if HAVE_SYS_TYPES_H
  #include <sys/types.h>
  #endif
  
  #if HAVE_SYS_STAT_H
  #include <sys/stat.h>
  #endif
  
  #if HAVE_INTTYPES_H
  #include <inttypes.h>
  #else
  #if HAVE_STDINT_H
  #include <stdint.h>
  #endif
  #endif
  
  #if HAVE_ERRNO_H
  #include <errno.h>
  #endif
  
  #if HAVE_UNISTD_H
  #include <unistd.h>
  #endif
  
  #if HAVE_STDIO_H
  #include <stdio.h>
  #endif
  
  #if HAVE_STRING_H
  #include <string.h>
  #endif
  
  #if HAVE_STDARG_H
  #include <stdarg.h>
  #endif
  
  #if HAVE_STDLIB_H
  #include <stdlib.h>
  #endif
  
  #if HAVE_DIRENT_H
  #include <dirent.h>
  #endif
  
  #include "duff.h"
  #include "duffstring.h"
  
  /* These flags are defined and documented in duff.c.
   */
  extern int follow_links_mode;
  extern int all_files_flag;
  extern int recursive_flag;
  extern int ignore_empty_flag;
  extern int quiet_flag;
  extern int physical_flag;
  extern int excess_flag;
  extern const char* header_format;
  
  /* List head for collected entries.
   */
  static struct Entry* file_entries = NULL;
  /* List head for traversed directories.
   */
  static struct Directory* directories = NULL;
  
  /* These functions are documented below, where they are defined.
   */
  static int stat_file(const char* path, struct stat* sb, int depth);
  static int has_recursed_directory(dev_t device, ino_t inode);
  static void recurse_directory(const char* path,
                                const struct stat* sb,
  			      int depth);
  static void report_cluster(struct Entry** duplicates,
                             unsigned int number,
  			   unsigned int count);
  static int cmpentryp(const void *p1, const void *p2);
  static int compare_separators(const char *left, const char *right);
  static int count_separators(const char *str);
  static int compare_lengths(const char *left, const char *right);
  
  /* Stat:s a file according to the specified options.
   */
  static int stat_file(const char* path, struct stat* sb, int depth)
  {
  #if HAVE_LSTAT_EMPTY_STRING_BUG || HAVE_STAT_EMPTY_STRING_BUG
    if (*path == '\0')
      return -1;
  #endif
  
    if (lstat(path, sb) != 0)
    {
      if (!quiet_flag)
        warning("%s: %s", path, strerror(errno));
  
      return -1;
    }
  
    if ((sb->st_mode & S_IFMT) == S_IFLNK)
    {
      if (follow_links_mode == ALL_SYMLINKS ||
          (depth == 0 && follow_links_mode == ARG_SYMLINKS))
      {
        if (stat(path, sb) != 0)
        {
  	if (!quiet_flag)
  	  warning("%s: %s", path, strerror(errno));
  
  	return -1;
        }
  
        if ((sb->st_mode & S_IFMT) != S_IFDIR)
  	return -1;
      }
      else
        return -1;
    }
  
    return 0;
  }
  
  /* Returns true if the directory has already been recursed into.
   * NOTE: This implementation is hideous.
   */
  static int has_recursed_directory(dev_t device, ino_t inode)
  {
    struct Directory* dir;
  
    /* TODO: Implement a more efficient data structure */
  
    for (dir = directories;  dir;  dir = dir->next)
    {
      if (dir->device == device && dir->inode == inode)
        return 1;
    }
  
    return 0;
  }
  
  /* Records the specified directory as recursed.
   * NOTE: This implementation is hideous.
   */
  static void record_directory(dev_t device, ino_t inode)
  {
    struct Directory* dir;
  
    dir = (struct Directory*) malloc(sizeof(struct Directory));
    dir->device = device;
    dir->inode = inode;
    dir->next = directories;
    directories = dir;
  }
  
  /* Recurses into a directory, collecting all or all non-hidden files,
   * according to the specified options.
   */
  static void recurse_directory(const char* path,
                                const struct stat* sb,
  			      int depth)
  {
    DIR* dir;
    struct dirent* dir_entry;
    char* child_path;
    const char* name;
  
    if (has_recursed_directory(sb->st_dev, sb->st_ino))
      return;
  
    record_directory(sb->st_dev, sb->st_ino);
  
    dir = opendir(path);
    if (!dir)
    {
      if (!quiet_flag)
        warning("%s: %s", path, strerror(errno));
  
      return;
    }
  
    while ((dir_entry = readdir(dir)))
    {
      name = dir_entry->d_name;
      if (name[0] == '.')
      {
        if (!all_files_flag)
  	continue;
  
        if (strcmp(name, ".") == 0 || strcmp(name, "..") == 0)
  	continue;
      }
  
      asprintf(&child_path, "%s/%s", path, name);
      process_path(child_path, depth);
      free(child_path);
    }
    
    closedir(dir);
  }
  
  /* Processes a path name, whether from the command line or from
   * directory recursion.
   */
  void process_path(const char* path, int depth)
  {
    mode_t mode;
    struct stat sb;
    struct Entry* entry;
  
    if (stat_file(path, &sb, depth) != 0)
      return;
  
    mode = sb.st_mode & S_IFMT;
    switch (mode)
    {
      case S_IFREG:
      {
        if (sb.st_size == 0)
        {
  	if (ignore_empty_flag)
  	  return;
        }
        else
        {
  	if (access(path, R_OK) != 0)
  	{
  	  if (!quiet_flag)
  	    warning("%s: %s", path, strerror(errno));
  
  	  return;
  	}
        }
  
        /* NOTE: Check for duplicate arguments? */
  
        if (physical_flag)
        {
  	/* TODO: Make this less suboptimal */
  
  	for (entry = file_entries;  entry;  entry = entry->next)
  	{
  	  if (entry->device == sb.st_dev && entry->inode == sb.st_ino)
  	    return;
  	}
        }
  
        if ((entry = make_entry(path, &sb)) != NULL)
  	link_entry(&file_entries, entry);
  
        break;
      }
  
      case S_IFDIR:
      {
        if (recursive_flag)
        {
  	recurse_directory(path, &sb, depth + 1);
          break;
        }
  
        /* FALLTHROUGH */
      }
  
      default:
      {
        if (!quiet_flag)
          warning("%s: %s, skipping", path, get_mode_name(mode));
        break;
      }
    }
  }
  
  /* Reports a cluster to stdout, according to the specified options.
   */
  static void report_cluster(struct Entry** duplicates,
                             unsigned int number,
  			   unsigned int count)
  {
    struct Entry* entry;
    int ix;
  
    if (!excess_flag && *header_format != '\0')
      print_cluster_header(header_format,
  			 count,
  			 number,
  			 duplicates[0]->size,
  			 duplicates[0]->checksum);
  
    for (ix = excess_flag ? 1 : 0; ix < count; ++ix)
      {
        entry = duplicates[ix];
        printf("%s\n", entry->path);
        entry->status = REPORTED;
      }
  }
  
  /* Finds and reports all duplicate clusters among the collected entries.
   */
  void report_clusters(void)
  {
    int number = 1, count, ix, dup_ix, num_entries;
    struct Entry* base;
    struct Entry* entry;
    struct Entry** entries;
  
    /* Count how many entries we've added (TODO: optimize this away by incrementing the count each time we add an entry). */
  
    for (ix = 0, base = file_entries; base != NULL;  base = base->next)
      {
        ++ix;
      }
  
    if (ix == 0)
      return;
  
    /* Create an array of pointers to the entries themselves. */
  
    num_entries = ix;
    entries = (struct Entry**) malloc(num_entries * sizeof(struct Entry*));
  
    for (ix = 0, base = file_entries; base != NULL;  ++ix, base = base->next)
      {
        entries[ix] = base;
      }
  
    /* Sort the array. */
  
    qsort(entries, num_entries, sizeof(struct Entry*), cmpentryp);
  
    /* Now go through the array, finding duplicates. */
  
    for (ix = 0; ix < num_entries; ++ix)
    {
      base = entries[ix];
  
      if (base->status == INVALID)
        continue;
  
      for (dup_ix = ix + 1; dup_ix < num_entries; ++dup_ix)
      {
        entry = entries[dup_ix];
  
        if (compare_entries(base, entry) == 0)
        {
  	base->status = DUPLICATE;
  	entry->status = DUPLICATE;
        }
        else
  	/* This should give us the speedup we want: since the list of entries is now sorted by the comparison function,
  	   we should have each set of duplicates grouped together.  */
  	break;
      }
  
      count = dup_ix - ix;
  
      if (count > 1)
      {
        report_cluster(entries + ix, number, count);
        number++;
      }
      else
      {
        unlink_entry(&file_entries, base);
        free_entry(base);
      }
       
      /* When we get back to the outer loop, we'll want to skip over all the duplicates.  */
      ix = dup_ix - 1;
    }
  }
  
  static int
  cmpentryp(const void *p1, const void *p2)
  {
    /* Each actual argument to this function is "pointer to pointer to Entry". */
  
    struct Entry* left = *(struct Entry**) p1;
    struct Entry* right = *(struct Entry**) p2;
  
    int result;
  
    result = compare_entries(left, right);
    if (result != 0)
      return result;
    
    /* Stabilize the sort: since the entries compare equal in terms of content, use
       the number of path-separator characters, then the path length, then the
       path name (which must be different). */
  
    result = compare_separators(left->path, right->path);
    if (result != 0)
      return result;
  
    result = compare_lengths(left->path, right->path);
    if (result != 0)
      return result;
  
    return strcmp(left->path, right->path);
  }
  
  static int
  compare_separators(const char *left, const char *right)
  {
    int n_left = count_separators(left);
    int n_right = count_separators(right);
  
    if (n_left < n_right)
      return -1;
    if (n_left > n_right)
      return 1;
    return 0;
  }
  
  static int
  count_separators(const char *str)
  {
    int count = 0;
  
    for (count = 0; *str != '\0'; ++str)
      if (*str == '/')
        ++count;
  
    return count;
  }
  
  static int
  compare_lengths(const char *left, const char *right)
  {
    int n_left = strlen(left);
    int n_right = strlen(right);
  
    if (n_left < n_right)
      return -1;
    if (n_left > n_right)
      return 1;
    return 0;
  }
  