wordnet字典

/*

  binsearch.c - general binary search functions

*/

#include 
#include 

static char *Id = “$Id: binsrch.cv 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 KEY_LEN		（1024）
#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

char *read_index（long offset FILE *fp） {
    char *linep;

    linep = line;
    line[0] = ‘0‘;

    fseek（ fp offset SEEK_SET ）;
    fgets（linep LINE_LEN fp）;
    return（line）;
}

char *bin_search（char *searchkey FILE *fp）
{
    int c;
    long top mid bot diff;
    char *linep key[KEY_LEN];
    int length;

    diff=666;
    linep = line;
    line[0] = ‘\0‘;

    fseek（fp 0L 2）;
    top = 0;
    bot = ftell（fp）;
    mid = （bot - top） / 2;

    do {
	fseek（fp mid - 1 0）;
	if（mid != 1）
	    while（（c = getc（fp）） != ‘\n‘ && c != EOF）;
        last_bin_search_offset = ftell（ fp ）;
	fgets（linep LINE_LEN fp）;
	length = （int）（strchr（linep ‘ ‘） - linep）;
	strncpy（key linep length）;
	key[length] = ‘\0‘;
	if（strcmp（key searchkey） < 0） {
	    top = mid;
	    diff = （bot - top） / 2;
	    mid = top + diff;
	}
	if（strcmp（key searchkey） > 0） {
	    bot = mid;
	    diff = （bot - top） / 2;
	    mid = top + diff;
	}
    } while（（strcmp（key searchkey）） && （diff != 0））;
    
    if（!strcmp（key searchkey））
	return（line）;
    else
	return（NULL）;
}

static long offset;

static int bin_search_key（char *searchkey FILE *fp）
{
    int c;
    long top mid bot diff;
    char *linep key[KEY_LEN];
    int length offset1 offset2;

    /* do binary search to find correct place in file to insert line */

    diff=666;
    linep = line;
    line[0] = ‘\0‘;

    fseek（fp 0L 2）;
    top = 0;
    bot = ftell（fp）;
    if （bot == 0） {
	offset = 0;
	return（0）;		/* empty file */
    }
    mid = （bot - top） / 2;

    /* If only one line in file don‘t work through loop */

    length = 0;
    rewind（fp）;
    while（（c = getc（fp）） != ‘\n‘ && c != EOF）
	line[length++] =  c;
    if （getc（fp） == EOF） {	/* only 1 line in file */
	length = （int）（strchr（linep ‘ ‘） - linep）;
	strncpy（key linep length）;
	key[length] = ‘\0‘;
	if（strcmp（key searchkey） > 0） {
	    offset = 0;
	    return（0）;		/* line with key is not found */
	} else if （strcmp（key searchkey） < 0） {
	    offset = ftell（fp）;
	    return（0）;		/* line with key is not found */
	} else {
	    offset = 0;
	    return（1）;		/* line with key is found */
	}
    }

    do {
	fseek（fp mid - 1 0）;
	if（mid != 1）
	    while（（c = getc（fp）） != ‘\n‘ && c != EOF）;
	offset1 = ftell（fp）;	/* offset at start of line */
	if （fgets（linep LINE_LEN fp） != NULL） {
  	    offset2 = ftell（fp）; /* offset at start of next