2
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ I set errno since the man pages say the return value is -1 for errors and EOF. POSIX.1-2008 says I should be using ferror() though. Treatment of whitespace is application specific so I left a few different ways the user can change the behavior. I put it in the hashing function because it was easy; it really should be somewhere else though. I will try to address your sizeof() concern. I have added a reference to the LCS algorithm on Wikipedia too. \$\endgroup\$ – OEP Jan 19 '15 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.