Find files with similar contents

Question

I'm not normally a C programmer but thought I'd take a shot at making something useful. This is a C utility I wrote to judge how similar several files are using the algorithm I think diff traditionally uses. I'm interested in general feedback. I don't write C usually but I do read it from time to time to try and pick up on the best practices.

This program takes a bunch of file paths as arguments and spits out a longest common subsequence (LCS) length for all pairs. It hashes the contents of the files first to speed up the LCS algorithm a bit.

Some things I can call attention to:

• Code portability across Unix-like systems. Am I using something that is limiting? I have read that getline() isn't everywhere...
• Use of realloc() in hash_file(). Never used it before and took a guess at how I could use it to grow a buffer dynamically.
• Best practices in general. Is there a smarter way to do something?
• Maybe encoding issues? I don't really assume any encoding until looking at whitespace characters.

This is the meat of the code, but the full source is available if you need it.

static hash_t
hash_string(const char* str)
{
  hash_t hash = 0;
  int c;

  // sdbm hash function
  while((c = *str++)) {
    if(opt_ignore_whitespace && isspace(c))
      continue;
    hash = c + (hash << 6) + (hash << 16) - hash;
  }

  // We use a hash of zero to indicate EOF.
  hash = (hash == 0) ? 1 : hash;

  return hash;
}

static void
hash_file(FILE *fp, hash_t **buffer)
{
  char *line = NULL, *linestart = NULL;
  size_t linecap = 0, linecount = 0, lineguess = 100;
  ssize_t linelen;

  if((*buffer = malloc(lineguess * sizeof(hash_t))) == NULL) {
    perror("malloc()");
    exit(EXIT_FAILURE);
  }

  errno = 0;
  while((linelen = getline(&line, &linecap, fp)) > 0) {
    ++linecount;
    linestart = line;

    // Trim whitespace
    if(opt_trim) {
      while(isspace(*linestart)) {
        ++linestart;
        --linelen;
      }
      while(isspace(linestart[linelen - 1])) {
        --linelen;
      }
      linestart[linelen] = '\0';
    }

    // Ignore the line if it is blank
    if(opt_ignore_blanks && (
        (linestart[0] == '\r' && linestart[1] == '\n') ||
        linestart[0] == '\n' ||
        linestart[0] == '\0'
      )
    ) {
      --linecount;
      continue;
    }

    // Rellocate memory if we have underestimated the file line count.
    if(linecount > lineguess) {
      lineguess *= 2;
      if((*buffer = realloc(*buffer, lineguess * sizeof(hash_t))) == NULL) {
        perror("realloc()");
        exit(EXIT_FAILURE);
      }
    }

    (*buffer)[linecount-1] = hash_string(linestart);
    errno = 0;
  }
  if(errno != 0) {
    perror("getline()");
    exit(EXIT_FAILURE);
  }

  // Shrink the buffer down to the actual file length.
  if((*buffer = realloc(*buffer, (linecount + 1) * sizeof(hash_t))) == NULL) {
    perror("realloc()");
    exit(EXIT_FAILURE);
  }

  // "Terminate" the sequence of hashes with zero.
  (*buffer)[linecount] = 0;

  if(line != NULL) {
    free(line);
  }
}

static void
hash_files(const char *const* filenames, hash_t **hashes, size_t length)
{
  size_t i;

  for(i = 0; i < length; ++i) {
    FILE *fp = fopen(filenames[i], "r");
    if(fp == NULL) {
      perror(filenames[i]);
      exit(EXIT_FAILURE);
    }
    hash_file(fp, &hashes[i]);
    fclose(fp);
  }
}

unsigned long
lcs_length(hash_t *buf1, size_t buflen1, hash_t *buf2, size_t buflen2)
{
  size_t i, j;
  unsigned long *swap, *this_row, *last_row, lookup1, lookup2, result;
  hash_t h1, h2;

  if(buflen1 == 0 || buflen2 == 0) {
    return 0;
  }

  // Make sure buf2 is the smaller buffer (to allocate less memory).
  if(buflen2 > buflen1) {
    size_t tmplen;
    hash_t *tmpbuf;

    tmpbuf = buf1;
    tmplen = buflen1;
    buf1 = buf2;
    buflen1 = buflen2;
    buf2 = tmpbuf;
    buflen2 = tmplen;
  }

  if((this_row = malloc(buflen2 * sizeof(unsigned long))) == NULL) {
    perror("malloc()");
    exit(EXIT_FAILURE);
  }

  if((last_row = malloc(buflen2 * sizeof(unsigned long))) == NULL) {
    perror("malloc()");
    exit(EXIT_FAILURE);
  }

  for(i = 0; i < buflen1; i++) {
    h1 = buf1[i];
    for(j = 0; j < buflen2; j++) {
      h2 = buf2[j];

      if(h1 == h2) {
        lookup1 = 0;
        if(i > 0 && j > 0) {
          lookup1 = last_row[j - 1];
        }
        this_row[j] = 1 + lookup1;
      }
      else {
        lookup1 = 0;
        lookup2 = 0;
        if(i > 0) {
          lookup1 = last_row[j];
        }
        if(j > 0) {
          lookup2 = this_row[j - 1];
        }
        this_row[j] = (lookup1 > lookup2) ? lookup1 : lookup2;
      }
    }
    swap = this_row;
    this_row = last_row;
    last_row = swap;
  }

  result = last_row[buflen2 - 1];
  free(this_row);
  free(last_row);
  return result;
}

Answer 1

• I see no reason to mess with errno. It is quite a fragile facility by itself.

• Reallocation by doubling the size is a sound strategy. Still, it is just a strategy, and shouldn't be hardcoded.

• Is there a reason to treat leading whitespaces (opt_trim) differently from the embedded ones (opt_ignore_whitespaces)? In any case, I'd delegate handling these options to a line reading routine, rather than handling them in a line hashing one.

• Using sizeof is a very good practice. On the other hand, using sizeof(hash_t) is not: changing the type of buffer would require much editing of an implementation. Such chores are easily avoided by using sizeof(**buffer) instead.

• I didn't really understood an algorithm. A reference would be helpful.