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()
inhash_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;
}