# Find files with similar contents

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;
}


• I see no reason to mess with errno. It is quite a fragile facility by itself.
• 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 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. – OEP Jan 19 '15 at 16:26