DSort

dsort.c

/**
 * @file dsort.c
 *
 * @author Ondřej Hošek (0925631)
 *
 * @brief DSort
 * @details Concatenates the output of two programs, sorts it, and outputs
 *          duplicate lines.
 *
 * @date 2011-04-12
 */
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <assert.h>
#include <errno.h>
#include <string.h>
#include <sys/wait.h>

#include "msa.h"

/** Maximum line length, sans NULL. */
#define MAX_LINE_LEN 1023

/** The environment with which this process has been launched. */
extern char **environ;

/**
 * The name of the program binary (from argv[0]).
 *
 * @note Unscrupulously global because it is only set once, is common to all
 * threads, and its globality strongly simplifies access.
 */
const char *progname;

/**
 * Launch a program and open a pipe to its standard input and output.
 *
 * @param argstrings Array of argument strings, including the program name.
 * @param progin By-ref to writable file object pointer representing the
 *               launched program's standard input.
 * @param progout By-ref to readable file object pointer representing the
 *                launched program's standard output.
 * @return PID of the spawned child process; -1 on failure.
 */
static pid_t pipeprog(char * const *argstrings, FILE **progin, FILE **progout)
{
	int p2cpipe[2];
	int c2ppipe[2];
	pid_t fk;

	/* set up pipes */
	if (pipe(p2cpipe) != 0)
	{
		(void)fprintf(stderr,
			"%s: Couldn't open pipe: %s\n",
			progname, strerror(errno)
		);
		return -1;
	}
	if (pipe(c2ppipe) != 0)
	{
		(void)fprintf(stderr,
			"%s: Couldn't open pipe: %s\n",
			progname, strerror(errno)
		);
		(void)close(p2cpipe[0]);
		(void)close(p2cpipe[1]);
		return -1;
	}

	fk = fork();

	if (fk == -1)
	{
		/* fork() failed */
		(void)fprintf(stderr,
			"%s: Couldn't fork process: %s\n",
			progname, strerror(errno)
		);
		return -1;
	}
	else if (fk == 0)
	{
		/* I'm the child */

		/* close unneeded pipe ends */
		(void)close(c2ppipe[0]);
		(void)close(p2cpipe[1]);

		/* turn pipe ends into stdin (0) and stdout (1) */
		if (dup2(p2cpipe[0], 0) == -1)
		{
			(void)fprintf(stderr,
				"%s: Error replacing stdin: %s\n",
				progname, strerror(errno)
			);
			(void)close(c2ppipe[1]);
			(void)close(p2cpipe[0]);
			exit(EXIT_FAILURE);
		}
		if (dup2(c2ppipe[1], 1) == -1)
		{
			(void)fprintf(stderr,
				"%s: Error replacing stdout: %s\n",
				progname, strerror(errno)
			);
			(void)close(c2ppipe[1]);
			(void)close(p2cpipe[0]);
			exit(EXIT_FAILURE);
		}

		/* execute the program */
		if (execve(argstrings[0], argstrings, environ) == -1)
		{
			(void)fprintf(stderr,
				"%s: Error executing program: %s\n",
				progname, strerror(errno)
			);
			(void)close(c2ppipe[1]);
			(void)close(p2cpipe[0]);
			exit(EXIT_FAILURE);
		}

		/* execve doesn't return */
		assert(0 && "execve returned...");
	}
	else
	{
		/* I'm the parent */

		/* close unneeded pipe ends */
		(void)close(p2cpipe[0]);
		(void)close(c2ppipe[1]);

		/* prepare the file objects */
		*progin = fdopen(p2cpipe[1], "w");
		if (*progin == NULL)
		{
			(void)fprintf(stderr,
				"%s: Couldn't open file descriptor: %s\n",
				progname, strerror(errno)
			);
			(void)close(p2cpipe[1]);
			(void)close(c2ppipe[0]);
			return -1;
		}

		*progout = fdopen(c2ppipe[0], "r");
		if (*progout == NULL)
		{
			(void)fprintf(stderr,
				"%s: Couldn't open file descriptor: %s\n",
				progname, strerror(errno)
			);
			(void)fclose(*progin);
			(void)close(p2cpipe[1]);
			(void)close(c2ppipe[0]);
			return -1;
		}

		/* done */
		return fk;
	}
}

/**
 * Launch a command through a shell and open a pipe to its standard input and
 * output.
 *
 * @param cmd Command string to pass to shell.
 * @param progin By-ref to writable file object pointer representing the
 *               launched program's standard input.
 * @param progout By-ref to readable file object pointer representing the
 *                launched program's standard output.
 * @return PID of the spawned child process; -1 on failure.
 */
static pid_t pipeprogshell(const char *cmd, FILE **progin, FILE **progout)
{
	char *args[4];
	args[0] = "/bin/sh";
	args[1] = "-c";
	/* this const-stripping is kinda stupid, but I don't know a better way */
	args[2] = (char *)cmd;
	args[3] = NULL;
	return pipeprog(args, progin, progout);
}

/**
 * The main entry point of the application.
 *
 * @param argc Number of commandline arguments.
 * @param argv Array of commandline arguments.
 * @return Exit code.
 */
int main(int argc, char **argv)
{
	FILE *pin;
	FILE *pout;
	char ln[MAX_LINE_LEN+1];
	msa_t lines;
	size_t i;
	pid_t uniqpid;

	progname = argv[0];

	if (argc != 3)
	{
		(void)fprintf(stderr, "Usage: %s COMMAND1 COMMAND2\n", progname);
		return EXIT_FAILURE;
	}

	/* allocate MSA */
	msa_create(&lines);

	/* for both commands */
	for (i = 1; i <= 2; ++i)
	{
		pid_t subpid = pipeprogshell(argv[i], &pin, &pout);

		/* launch command */
		if (subpid == -1)
		{
			/* diagnostics already provided by pipeprog */
			msa_destroy(&lines);
			return EXIT_FAILURE;
		}

		/* provide no input */
		(void)fclose(pin);

		/* read output line by line and place it in the array */
		while (!feof(pout))
		{
			if (fgets(ln, MAX_LINE_LEN+1, pout) != NULL)
			{
				msa_add(&lines, ln);
			}
		}

		/* close output */
		(void)fclose(pout);

		/* waitpid is an antidote for BRAAAAAAAINS */
		(void)waitpid(subpid, NULL, 0);
	}

	/* sort the array */
	msa_sort(&lines);

	/* launch uniq -d */
	uniqpid = pipeprogshell("uniq -d", &pin, &pout);
	if (uniqpid == -1)
	{
		/* diagnostics already provided by pipeprog */
		msa_destroy(&lines);
		return EXIT_FAILURE;
	}

	/* feed it with our lines */
	for (i = 0; i < lines.count; ++i)
	{
		(void)fprintf(pin, "%s", lines.arr[i]);
	}
	(void)fclose(pin);

	/* forget our lines again */
	msa_destroy(&lines);

	/* read and print output from uniq -d */
	while (!feof(pout))
	{
		if (fgets(ln, MAX_LINE_LEN+1, pout) != NULL)
		{
			(void)printf("%s", ln);
		}
	}

	/* close uniq's stdout */
	(void)fclose(pout);

	/* zombie string theorist: "BRAAAAAAAAAANES" */
	(void)waitpid(uniqpid, NULL, 0);

	return 0;
}

msa.c

/**
 * @file msa.c
 *
 * @author Ondřej Hošek (0925631)
 *
 * @brief Magical String Array
 * @details A string array which automagically expands its contents as needed.
 *
 * @date 2011-04-12
 */

#include "msa.h"

#include <string.h>

/** Default MSA capacity. */
static const int DEFAULT_CAPACITY = 2;

/** MSA capacity increment size. */
static const int CAPACITY_INCREMENT = 8;

/* utility functions */

/**
 * Compare two strings using strcmp. Useful for qsort(3), bsearch(3), et al.
 *
 * @param left Pointer to the first string (pointer-to-pointer-to-char).
 * @param right Pointer to the first string (pointer-to-pointer-to-char).
 * @return Less than zero if left ordered before right.
 *         Zero if left and right equally ordered.
 *         More than zero if right ordered before left.
 */
static int comparator_strcmp(const void *left, const void *right)
{
	return strcmp(*(char * const *)left, *(char * const *)right);
}

/* public-facing functions */

int msa_create(msa_t *msa)
{
	msa->capacity = DEFAULT_CAPACITY;
	msa->count = 0;
	msa->arr = malloc(msa->capacity * sizeof(char *));
	if (msa->arr == NULL)
	{
		/* malloc failed */
		msa->capacity = 0;
		return 0;
	}
	return 1;
}

void msa_destroy(msa_t *msa)
{
	size_t i;

	/* free all strings */
	for (i = 0; i < msa->count; ++i)
	{
		free(msa->arr[i]);
	}
	/* reset structure */
	msa->capacity = 0;
	msa->count = 0;
	free(msa->arr);
	msa->arr = NULL;
}

int msa_add(msa_t *msa, const char *str)
{
	char *dupedstr;

	if (++msa->count > msa->capacity)
	{
		/* not enough space; expand array by CAPACITY_INCREMENT */
		char **newarr;
		msa->capacity += CAPACITY_INCREMENT;
		newarr = realloc(msa->arr, msa->capacity * sizeof(char *));
		if (newarr == NULL)
		{
			/* realloc failed; return 0 and don't touch the existing array */
			return 0;
		}

		/* array reallocated successfully; store new pointer */
		msa->arr = newarr;
	}

	/* store new element */
	dupedstr = strdup(str);
	if (dupedstr == NULL)
	{
		/* strdup failed */
		return 0;
	}

	msa->arr[msa->count - 1] = dupedstr;
	return 1;
}

const char *msa_get(msa_t *msa, size_t idx)
{
	if (idx >= msa->count)
	{
		return NULL;
	}

	return msa->arr[idx];
}

int msa_replace(msa_t *msa, size_t idx, const char *str)
{
	char *dupedstr = strdup(str);
	if (dupedstr == NULL)
	{
		/* strdup failed */
		return 0;
	}

	/* free old and store dup'ed new string */
	free(msa->arr[idx]);
	msa->arr[idx] = dupedstr;
	return 1;
}

void msa_sort(msa_t *msa)
{
	qsort(msa->arr, msa->count, sizeof(char *), comparator_strcmp);
}

msa.h

/**
 * @file msa.h
 *
 * @author Ondřej Hošek (0925631)
 *
 * @brief Magical String Array
 * @details A string array which automagically expands its contents as needed.
 *
 * @date 2011-04-12
 */

#include <stdlib.h>

/** The Magical String Array structure. */
typedef struct
{
	/** How many items can the array house? */
	size_t capacity;

	/** How many items is the array housing right now? */
	size_t count;

	/** The string array itself. */
	char **arr;
} msa_t;

/**
 * Create an empty Magical String Array.
 *
 * @param msa Pointer to fill with a MSA structure.
 * @return 1 on success, 0 on failure (setting errno appropriately).
 */
int msa_create(msa_t *msa);

/**
 * Destroy a Magical String Array.
 *
 * @param msa Pointer to a MSA structure.
 */
void msa_destroy(msa_t *msa);

/**
 * Add a duplicate of a string to the end of a Magical String Array.
 *
 * @param msa Pointer to a MSA structure.
 * @param str String whose duplicate is to be appended to the MSA.
 * @return 1 on success, 0 on failure (setting errno appropriately).
 */
int msa_add(msa_t *msa, const char *str);

/**
 * Obtain a specific element in the Magical String Array.
 *
 * @param msa Pointer to a MSA structure.
 * @param idx Index to fetch from.
 */
const char *msa_get(msa_t *msa, size_t idx);

/**
 * Replace a specific string in the Magical String Array with another one.
 *
 * @param msa Pointer to a MSA structure.
 * @param idx Index to replace at.
 * @param str String whose duplicate will replace the element.
 * @return 1 on success, 0 on failure (setting errno appropriately).
 */
int msa_replace(msa_t *msa, size_t idx, const char *str);

/**
 * Sort the Magical String Array using qsort(3) and strcmp(3).
 *
 * @param msa Pointer to a MSA structure.
 */
void msa_sort(msa_t *msa);