/*
 *
 */
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifdef unix
#include <unistd.h>
#else
#include "getopt.h"
#endif

static int no_header;
static int print_pos;
static int quiet;
static const char *cur_name;

static char *myname;

static long
filesize(FILE *fp)
{
	fseek(fp, 0, SEEK_END);
	return ftell(fp);
}/* filesize */

#define FB_NOT_FOUND ((size_t)-1)

static size_t
fbsearch(FILE *fp, const void *key, size_t base, size_t nelm, size_t esize, int (*cmp)(FILE *fp, const void *key, size_t base, size_t esize))
{
	if (nelm == 0)
		return FB_NOT_FOUND;
	else {
		int cp;
		size_t half = nelm / 2;
		size_t mid = base + half * esize;
		cp = (*cmp)(fp, key, mid, esize);
		if (cp == 0)
			return mid;
		else if (cp < 0)
			return fbsearch(fp, key, base, half, esize, cmp);
		else
			return fbsearch(fp, key, mid + esize, nelm - half - 1, esize, cmp);
	}
}/* fbsearch */

static int
comp(FILE *fp, const void *key, size_t base, size_t esize)
{
	const unsigned char *k = (const unsigned char *)key;
	int cp = 0;
	fseek(fp, base, SEEK_SET);
	while (*k != '\0' && cp == 0) {
		if (esize-- == 0)
			cp = *k++;
		else {
			int ch = getc(fp);
			cp = *k++ - ch;
			if (ch == EOF)
				rewind(fp);
		}
	}/* while */
	//printf("cmp: %lu = %d\n", base, cp);
	return cp;
}/* comp */

static int
output(FILE *fp, size_t base, size_t rec_size)
{
	int ch = 0;
	if (cur_name != NULL && !no_header) {
		fputs(cur_name, stdout);
		putchar(':');
	}
	if (print_pos)
		printf("%lu:", (unsigned long)base);
	fseek(fp, base, SEEK_SET);
	while (rec_size-- > 0 && (ch = getc(fp)) != EOF)
		putc(ch, stdout);
	return ch;
}/* output */

static size_t
bs0(FILE *fp, size_t rec_size, const char *key)
{
	size_t fsize = filesize(fp);
	size_t nelm = fsize / rec_size;
	size_t q = fbsearch(fp, key, 0, nelm, rec_size, comp);
	return q;
}/* bs0 */


static size_t
bs1(FILE *fp, size_t rec_size, const char *key)
{
	size_t q = bs0(fp, rec_size, key);
	if (q != FB_NOT_FOUND && !quiet) {
		/* search backword */
		q -= rec_size;
		while (comp(fp, key, q, rec_size) == 0)
			q -= rec_size;
		q += rec_size;
		{
			/* output all matching lines */
			size_t qq = q;
			while (comp(fp, key, qq, rec_size) == 0) {
				output(fp, qq, rec_size);
				qq += rec_size;
			}/* while */
		}
	}
	return q;
}/* bs1 */

static int
skip_to_eol(FILE *fp)
{
	int n = 0;
	int ch = 0;
	while (ch != '\n' && (ch = getc(fp)) != EOF)
		n++;
	return n;
}/* skip_to_eol */


static int
fnain(FILE *fp, const char *key, size_t rec_size)
{
	int err = 1;
	size_t q;
	if (rec_size == 0) {
		rec_size = skip_to_eol(fp);
		rewind(fp);
	}
	if (rec_size != 0) {
		q = bs1(fp, rec_size, key);
		if (q != FB_NOT_FOUND)
			err = 0;
	}
	return err;
}/* fnain */

static int
nain(const char *name, const char *key, size_t rec_size)
{
	int err = -1;
	FILE *fp = fopen(name, "rb");
	if (fp != NULL) {
		cur_name = name;
		err = fnain(fp, key, rec_size);
		fclose(fp);
	}
	else
		fprintf(stderr, "%s: %s: %s\n", myname, name, strerror(errno));
	return err;
}/* nain */

static char *usage_msg = "usage: %s pattern file ...\n";

int
main(int argc, char *argv[])
{
	int ex = 1, ch, show_usage = 0;
	int opt_h = 0;
	size_t rec_size = 0;
	myname = argv[0];
	while ((ch = getopt(argc, argv, "hk:nqV")) != EOF) {
		switch (ch) {
		default:
		case 'V':
			show_usage++;
			break;
		case 'h':
			opt_h++;
			break;
		case 'k':
			rec_size = strtol(optarg, NULL, 0);
			break;
		case 'n':
			print_pos++;
			break;
		case 'q':
			quiet++;
			break;
		}/* switch */
	}/* while */
	if (argc - optind < 2)
		show_usage++;
	if (show_usage) {
		fprintf(stderr, usage_msg, myname);
	}
	else {
		char *key = argv[optind];
		int i;
		int nf = 0;
		int nerr = 0;
		no_header = (argc - (optind + 1)) == 1 || opt_h;
		for (i = optind + 1; i < argc; i++) {
			int err = nain(argv[i], key, rec_size);
			if (err < 0)
				nerr++;
			else if (err == 0)
				nf++;
		}/* for */
		ex = nerr > 0 ? 2 : nf > 0 ? 0 : 1;
	}
	return ex;
}/* main */