bplus.cpp

计算机英汉机器翻译系统中的英语词性标注方法实现

/********************************************************************/
/*                                                                  */
/*             BPLUS file indexing program - Version 1.0            */
/*                                                                  */
/*                      A "shareware program"                       */
/*                                                                  */
/*                                                                  */
/*                      Copyright (C) 1987 by                       */
/*                                                                  */
/*                      Hunter and Associates                       */
/*                      7050 NW Zinfandel Lane                      */
/*                      Corvallis, Oregon  97330                    */
/*                      (503) 745 - 7186                            */
/*                                                                  */
/********************************************************************/

#include "stdafx.h"
#include "io.h"
#include <fcntl.h>
#include <sys/stat.h>


#include "bplus.h"


/*  macros, constants, data types  */

#define  NULLREC      (-1L)
#define  FREE_BLOCK   (-2)

#define  ENT_ADR(pb,off)  ((ENTRY*)((char*)((pb)->entries) + off))
#define  ENT_SIZE(pe)     strlen((pe)->key) + 1 + 2 * sizeof(RECPOS)
#define  BUFDIRTY(j)      (mci->cache[j].dirty)
#define  BUFHANDLE(j)     (mci->cache[j].handle)
#define  BUFBLOCK(j)      (mci->cache[j].mb)
#define  BUFCOUNT(j)      (mci->cache[j].count)
#define  CB(j)            (pci->pos[j].cblock)
#define  CO(j)            (pci->pos[j].coffset)


/*  declare some global variables  */

IX_DESC      *pci;
IX_BUFFER    bt_buffer;
IX_BUFFER    *mci = &bt_buffer;
BLOCK        *block_ptr;
BLOCK        *spare_block;
int          cache_ptr = 0;
int          cache_init = 0;
int          split_size = IXB_SPACE;
int          comb_size  = (IXB_SPACE/2);

void  error(int, long);
void  read_if(long, char *, int);
void  write_if(int, long, char *, int);
int   creat_if(char *);
int   open_if(char *);
void  close_if(int);
void  update_block(void);
void  init_cache(void);
int   find_cache(RECPOS);
int   new_cache(void);
void  load_cache(RECPOS);
void  get_cache(RECPOS);
void  retrieve_block(int, RECPOS);
int   prev_entry(int);
int   next_entry(int);
int   copy_entry(ENTRY *, ENTRY *);
int   scan_blk(int);
int   last_entry(void);
int   write_free( RECPOS, BLOCK *);
RECPOS  get_free(void);
int   find_block(ENTRY *, int *);
void  movedown(BLOCK *, int, int);
void  moveup(BLOCK *, int, int);
void  ins_block(BLOCK *, ENTRY *, int);
void  del_block(BLOCK *, int);
int   split(int, ENTRY *, ENTRY *);
void  ins_level(int, ENTRY *);
int   insert_ix(ENTRY *, IX_DESC *);
int   find_ix(ENTRY *, IX_DESC *, int);
int   combineblk(RECPOS, int);
void  replace_entry(ENTRY *);
void print_blk(BLOCK *);


/*  file I/O for B-PLUS module  */

void  error(  int j,long l)
{
	static char *msg[3] = {"ERROR - CANNOT OPEN/CLOSE FILE",
						   "ERROR WHILE READING FILE",
						   "ERROR WHILE WRITING FILE"};
	CString strTmp;
	strTmp.Format("\n  %s - Record Number %ld\n", msg[j], l);
	AfxMessageBox(strTmp);
	exit(1);
} /* error */


void  read_if(long start, char *buf,  int nwrt)
{
	long err;
	err = start - lseek(pci->ixfile, start, SEEK_SET);
	if (err == 0) err = nwrt - read(pci->ixfile, buf, nwrt);
	if (err != 0) error(1, start);
} /* read_if */


void  write_if(int handle, long start, char *buf, int nwrt)
{
	long err;
	err = start - lseek(handle, start, SEEK_SET);
	if (err == 0) err = nwrt - write(handle, buf, nwrt);
	if (err != 0) error(2, start);
} /* write_if */


int  creat_if(char *fn)
{
	int   ret;
	ret = open(fn,O_RDWR|O_CREAT|O_TRUNC|O_BINARY,S_IWRITE);
	if (ret  < 0) error(0,0L);
	return (ret);
} /* creat_if */


int  open_if(char *fn)
{
	int  ret;
	ret = _open(fn,_O_RDWR|_O_BINARY);
	if (ret < 1) error(0,0L);
	return (ret);
} /* open_if */


void  close_if(int handle)
{
	if(close(handle) < 0)  error(2,0L);
} /*  close_if */


int  open_index(char *name, IX_DESC *pix, int dup)
{
	pci = pix;
	//xeddel open_if(name);
	pci->ixfile = open_if(name);
	pci->duplicate = dup;
	read_if(0L,(char *)&(pix->root), (sizeof(BLOCK) + sizeof(IX_DISK)));
	if (!cache_init)
	{
		init_cache();
		cache_init = 1;
	}
	first_key(pix);
	return ( IX_OK );
} /* open_index */


int  close_index(  IX_DESC *pix)
{
	int i;
	write_if(pix->ixfile, 0L,(char *)&(pix->root),
			   (sizeof(BLOCK) + sizeof(IX_DISK)));
	for (i = 0; i < NUM_BUFS; i++)
		if (BUFDIRTY(i) && (BUFHANDLE(i) == pix->ixfile))
		{
			write_if(BUFHANDLE(i),
				   BUFBLOCK(i).brec,
				   (char *) &BUFBLOCK(i),
				   sizeof(BLOCK));
			BUFDIRTY(i) = 0;
		}
	close_if(pix->ixfile);
	return( IX_OK );
} /* close_index */


int  make_index(char *name, IX_DESC *pix,   int dup)
{
	pci = pix;
	pci->ixfile = creat_if(name);
	pci->duplicate = dup;
	pci->dx.nl = 1;
	pci->dx.ff = NULLREC;
	pci->level = 0;
	CO(0) = -1;
	CB(0) = 0L;
	pci->root.brec = 0L;
	pci->root.bend = 0;
	pci->root.p0 = NULLREC;
	write_if(pci->ixfile, 0L,(char *)&(pix->root),
			   (sizeof(BLOCK) + sizeof(IX_DISK)));
	if (!cache_init)
	{
		init_cache();
		cache_init = 1;
	}
	first_key(pix);
	return ( IX_OK );
} /* make_index */


/*  cache I/O for BPLUS  */

void  update_block()
{
	if (block_ptr != &(pci->root))
	   BUFDIRTY(cache_ptr) = 1;
} /* update_block */


void  init_cache()
{
	register int  j;
	for (j = 0; j < NUM_BUFS; j++)
	{  
		BUFDIRTY(j) = 0;
		BUFCOUNT(j) = 0;
		BUFBLOCK(j).brec = NULLREC;
	}
} /* init_cache */


int  find_cache(  RECPOS r)
{
	register int  j;
	for (j = 0; j < NUM_BUFS; j++)
	{
		if((BUFBLOCK(j).brec == r) && (BUFHANDLE(j) == pci->ixfile))
		{
			cache_ptr = j;
			return (1);
		}  
	}
	return (-1);
} /* find_cache */


int  new_cache()
{
	register int  i;
	i = (cache_ptr + 1) % NUM_BUFS;
	if (BUFDIRTY(i)) write_if(BUFHANDLE(i),
							  BUFBLOCK(i).brec,
							  (char *) &BUFBLOCK(i),
							  sizeof(BLOCK));
	BUFHANDLE(i) = pci->ixfile;
	BUFDIRTY(i) = 0;
	return (i);
} /* new_cache */


void  load_cache(RECPOS r)
  
{
	cache_ptr = new_cache();
	read_if(r, (char *)&BUFBLOCK(cache_ptr), sizeof(BLOCK));
} /* load_cache */


void  get_cache(  RECPOS r)
{
	if (find_cache(r) < 0)
	   load_cache(r);
	block_ptr = &BUFBLOCK(cache_ptr);
} /* get_cache */


void  retrieve_block(int j, RECPOS r)
  {
    if (j == 0)
       block_ptr = &(pci->root);
    else  get_cache(r);
    CB(j) = block_ptr->brec;
  } /* retrieve_block */


/*  low level functions of BPLUS  */

int  prev_entry(int off)
  {
     if (off <= 0)
       {
         off = -1;
         CO(pci->level) = off;
       }
     else
       off = scan_blk(off);
     return(off);
  } /* prev_entry */


int  next_entry(int off)
  {
     if (off == -1)
       off = 0;
     else
       {
         if (off < block_ptr->bend)
            off += ENT_SIZE(ENT_ADR(block_ptr,off));
       }
     CO(pci->level) = off;
     return (off);
  } /* next_entry */


int  copy_entry(ENTRY *to, ENTRY *from)
  {
    int me;
    me = ENT_SIZE(from);
    memcpy(to, from, me);
	return me;
  } /* copy_entry */


int  scan_blk(int n)
  {
     register int off, last;
     off = 0;
     last = -1;
     while (off < n )
       {  last = off;
          off += ENT_SIZE(ENT_ADR(block_ptr,off));
       }
     CO(pci->level) = last;
     return (last);
  } /* scan_blk */


int  last_entry()
  {
     return( scan_blk(block_ptr->bend) );
  } /* last_entry *;


/*  maintain list of free index blocks  */

int  write_free(  RECPOS r, BLOCK *pb)
  {
    pb->p0 = FREE_BLOCK;
    pb->brec = pci->dx.ff;
    write_if(pci->ixfile, r, (char *) pb, sizeof(BLOCK));
    pci->dx.ff = r;
	return 1;
  } /* write_free */


RECPOS  get_free()
  {
    RECPOS  r, rt;

    r = pci->dx.ff;
    if ( r != NULLREC )
      {  read_if(r, (char *)&rt, sizeof( RECPOS ));
         pci->dx.ff = rt;
      }
    else
      r = filelength (pci->ixfile);
    return (r);
  } /* get_free */


/*  general BPLUS block level functions  */

int  find_block(ENTRY *pe, int *poff)
  {
    register int pos, nextpos, ret;
    pos = -1;
    nextpos = 0;
    ret = 1;
    while ( nextpos < block_ptr->bend)
      {
        ret = strcmp((char *)(pe->key),
                     (char *)(ENT_ADR(block_ptr, nextpos)->key));
        if (ret <= 0)
          {
             if (ret == 0) pos = nextpos;
             break;
          }
        pos = nextpos;
        nextpos = next_entry(pos);
      }
    CO(pci->level) = pos;
    *poff = pos;
    return (ret);
  } /* find_block */


void  movedown(BLOCK *pb, int off, int n)
  {
    memcpy(ENT_ADR(pb, off),
           ENT_ADR(pb, off + n),
           pb -> bend - (off + n));
  } /* movedown */


void  moveup(BLOCK *pb, int off, int n)
  {
    memcpy(ENT_ADR(pb, off + n),
            ENT_ADR(pb, off),
            pb->bend - off);
  } /* moveup */


void  ins_block(BLOCK *pb, ENTRY *pe,   int off)
  {
    int size;
    size = ENT_SIZE(pe);
    moveup(pb,off,size);
    copy_entry(ENT_ADR(pb,off),pe);
    pb->bend += size;
  } /* ins_block */


void  del_block(BLOCK *pb, int off)
  {
    int ne;
    ne = ENT_SIZE(ENT_ADR(pb, off));
    movedown(pb, off, ne);
    pb->bend -= ne;
  } /* del_block */


/*  position at start/end of index  */

int  first_key(IX_DESC *pix)
  {
	pci = pix;
    block_ptr = &(pci->root);
    CB(0) = 0L;
    CO(0) = -1;
    pci->level = 0;
    while(block_ptr->p0 != NULLREC)
      {
        retrieve_block(++(pci->level), block_ptr->p0);