main.c

#include <sys/queue.h>
#include <sys/wait.h>
#include <sys/stat.h>

#include <err.h>
#include <fcntl.h>
#include <getopt.h>
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <unistd.h>

#include "lootsack.h"



struct selection {
	struct treasure item;
	SLIST_ENTRY(selection) next; /* list maintenance */
};

static SLIST_HEAD(sel_head, selection) selections;

int sort_treasure_item(const void *a, const void *b);
int make_selections(struct treasure *, size_t n, uint16_t max_w,
    struct sel_head *);
int free_selection_list(struct sel_head *h);

int parse_treasure_list(const char *path, struct treasure **out, size_t *nout);

__dead void usage(const char *progname);
void wait_and_report(pid_t pid, const char *n);

int verbose = 0;
static struct option longopts[] = {
	{ "weight", required_argument, NULL, 'w' },
	{ "verbose",      no_argument, NULL, 'v' },
};

__dead void
usage(const char *progname)
{
	fprintf(stderr, "Usage:\n\t%s [-v] -w weight -i infile\n", progname);
	exit(1);
}

int
main(int argc, char **argv)
{
	struct treasure_file_header header;
	char ch;
	int total_v, fd, selection_size, ncoins;
	uint16_t max_weight;
	struct treasure *items;
	struct selection *s;

	/* typical encumbrance thresholds of note:
	 * <  750, basically unencumbered
	 *   1000-1500, encumbered
	 *   1500-3000, overburdened
	 * > 3000 unable to move
	 */

	if (argc < 2)
		usage(*argv); /* does not return */

	fd = -1;
	items = NULL;

	while ((ch = getopt_long(argc, argv, "i:w:v", longopts, NULL)) != -1) {
		switch (ch) {
		case 'i':
			if ((fd = open(optarg, O_RDONLY)) == -1)
				err(1, "%s", optarg);
			break;
		case 'v':
			verbose = 1;
			break;
		case 'w':
			max_weight = (uint16_t) strtol(optarg, NULL, 10);
			break;
		default:
			usage(*argv); /* does not return */
		}
	}

	if (fd == -1)
		usage(*argv); /* does not return */

	if (read_treasure_bin(fd, &header, &items) == -1)
		err(1, "read_treasure_bin");

	if (verbose)
		fprintf(stderr, "Loaded %u items.\n", header.num_entries);

	selection_size = ncoins = 0;
	SLIST_INIT(&selections);
	total_v = make_selections(items, header.num_entries, max_weight,
	    &selections);
	SLIST_FOREACH(s, &selections, next) {
		if (s->item.t == COIN) {
			ncoins++;
		} else if (verbose) {
			print_treasure_item(&s->item);
		}
		selection_size++;
	}
	printf("\n\nSelected %d items and %d coins worth %d.\n", selection_size,
	    ncoins, total_v);
	free(items);
	free_selection_list(&selections);
	return 0;
}


int
make_selections(struct treasure *items, size_t n, uint16_t max_w,
    struct sel_head *h)
{
	uint16_t remaining_w;
	int acc_v;
	struct selection *s;
	struct treasure *t;
	struct treasure *sorted;
	size_t i;

	acc_v = 0;
	remaining_w = max_w;

	if ((sorted = calloc(sizeof(struct treasure), n)) == 0)
		err(1, "make_selections:calloc");

	bcopy(items, sorted, sizeof(struct treasure) * n);
	

	qsort(sorted, n, sizeof(struct treasure), &sort_treasure_item);

	/* naive greedy implementation */
	for (i = 0; i < n; i++) {
		t = sorted + i;
		if (t->w <= remaining_w) {
			if ((s = calloc(1, sizeof(struct selection))) == NULL)
				err(1, "calloc");
			bcopy(t, &s->item, sizeof(struct treasure));
			SLIST_INSERT_HEAD(h, s, next);
			acc_v += t->v;
			remaining_w -= t->w;
			if (verbose)
				fprintf(stderr, "Remaining weight: %u\n",
				    remaining_w);
		} else if (remaining_w == 0)
			break;
	}
	return acc_v;
}

int
free_selection_list(struct sel_head *h)
{
	struct selection *s;
	while (!SLIST_EMPTY(h)) {
		s = SLIST_FIRST(h);
		SLIST_REMOVE_HEAD(h, next);
		free(s);
	}
	return 0;
}

void
wait_and_report(pid_t pid, const char *n)
{
	int status;
	waitpid(pid, &status, 0);
	if (WIFEXITED(status) && WEXITSTATUS(status) != 0) {
		fprintf(stderr, "Child (%s) non-zero exit: %d\n",
		    n, WEXITSTATUS(status));
	} else if (WIFSIGNALED(status)) {
		fprintf(stderr, "Child (%s) exited by signal: %d\n",
		    n, WTERMSIG(status));
	} else if (WIFSTOPPED(status)) {
		fprintf(stderr, "Child (%s) stopped by signal: %d\n",
		    n, WSTOPSIG(status));
	}
}

int
sort_treasure_item(const void *a, const void *b)
{
	const struct treasure *tl;
	const struct treasure *tr;

	tl = a;
	tr = b;
	return SCALED_W_V_RATIO(tr) - SCALED_W_V_RATIO(tl);
}