/*

  binsearch.c - general binary search functions

*/

#include "wn.h"
#include <stdio.h>
#include <string.h>

__FBSDID("$Id: binsrch.c,v 1.15 2005/02/01 16:46:43 wn Rel $");

/* Binary search - looks for the key passed at the start of a line
   in the file associated with open file descriptor fp, and returns
   a buffer containing the line in the file. */

#define LINE_LEN	(1024*25)

static char line[LINE_LEN]; 
long last_bin_search_offset = 0;

/* General purpose binary search function to search for key as first
   item on line in open file.  Item is delimited by space. */

#undef getc

const char *
read_index(long offset, FILE *fp) {

    line[0] = '0';

    fseek(fp, offset, SEEK_SET);
    fgets(line, LINE_LEN, fp);
    return(line);
}

static int
sign(int number)
{
	if (number > 0)
		return 1;
	if (number < 0)
		return -1;
	return 0;
}

const char *
bin_search(const char *searchkey, FILE *fp)
{
	int	c;
	long	top, mid, bot; /* should be off_t */
	int	length, keylen;

	fseek(fp, 0L, 2);
	bot = ftell(fp);
	mid = bot / 2;
	keylen = strlen(searchkey);

	for (top = 0; bot - top >= 2; mid = (top + bot) / 2) {
		fseek(fp, mid - 1, 0);
		if(mid != 1)
			while((c = getc(fp)) != '\n' && c != EOF);
		last_bin_search_offset = ftell(fp);
		if (fgets(line, LINE_LEN, fp) == NULL)
			return(NULL);
		length = strchr(line, ' ') - line;
		switch (sign(strncmp(line, searchkey, length))) {
		case 0:
			/* a match up to the length! */
			if (length == keylen)
				return(line);
			if (length > keylen)
				/* the word read is longer than ours */
				goto up;
			/* FALLTHROUGH */
		case -1:
			top = mid;
			continue;
		case 1:
		up:
			bot = mid;
		}
	}
	return(NULL);
}