bplus.cpp

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

        CO(pci->level) = -1;
      }

    return ( IX_OK );
  } /* first_key */


int  last_key(IX_DESC *pix)
  {
    long  ads;
    pci = pix;
    block_ptr = &(pci->root);
    CB(0) = 0L;
    pci->level = 0;
    if(last_entry() >= 0)
      {
        while ((ads = ENT_ADR(block_ptr,last_entry())->idxptr) != NULLREC)
             retrieve_block(++(pci->level), ads);
      }
    CO(pci->level) = block_ptr->bend;
    return ( IX_OK );
  } /* last_key */


/*  get next, previous entries  */

int  next_key(ENTRY *pe, IX_DESC *pix)
  {

    RECPOS  address;
    pci = pix;
    retrieve_block(pci->level, CB(pci->level));
    address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
    while (address != NULLREC)
      {
         retrieve_block(++(pci->level), address);
         CO(pci->level) = -1;
         address = block_ptr->p0;
      }
    next_entry(CO(pci->level));
    if (CO(pci->level) == block_ptr->bend)
      {
        do
          { if(pci->level == 0)
              {
                last_key(pci);
                return (EOIX);
              }
            --(pci->level);
            retrieve_block(pci->level, CB(pci->level));
            next_entry(CO(pci->level));
          } while (CO(pci->level) == block_ptr->bend);
      }
    copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
    return ( IX_OK );
  } /* next_key */


int  prev_key(ENTRY *pe,   IX_DESC *pix)
  {
    RECPOS  address;
    pci = pix;
    retrieve_block(pci->level, CB(pci->level));
    prev_entry(CO(pci->level));
    if (CO(pci->level) == -1)
      address = block_ptr->p0;
    else
      address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
    if (address != NULLREC)
      { do
          {
            retrieve_block(++(pci->level), address);
            address = ENT_ADR(block_ptr, last_entry())->idxptr;
          } while (address != NULLREC);
      }
    if (CO(pci->level) == -1)
      { do
          {
            if(pci->level == 0)
              {
                first_key(pci);
                return (EOIX);
              }
            --(pci->level);
          } while (CO(pci->level) == -1);
        retrieve_block(pci->level, CB(pci->level));
      }
    copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
    return ( IX_OK );
  } /* prev_key */


/*  insert new entries into tree  */

int  split(  int l, ENTRY *pe, ENTRY *e)
  {
    int  half, ins_pos, size;
    ins_pos = CO(pci->level);
    half = scan_blk(block_ptr->bend / 2 + sizeof(RECPOS));
    if (half == ins_pos)
      *e = *pe;
    else
      {
         copy_entry(e, ENT_ADR(block_ptr, half));
         size = ENT_SIZE(e);
         movedown(block_ptr, half, size);
         block_ptr->bend -= size;
      }
    spare_block = &BUFBLOCK(new_cache());
    memcpy(spare_block->entries,
           ENT_ADR(block_ptr,half),
           block_ptr->bend - half);
    spare_block->brec = get_free();
    spare_block->bend = block_ptr->bend - half;
    spare_block->p0 = e->idxptr;
    block_ptr->bend = half;
    e->idxptr = spare_block->brec;
    if (ins_pos < half)
      ins_block(block_ptr,pe,ins_pos);
    else if (ins_pos > half)
      {
         ins_pos -= ENT_SIZE(e);
         ins_block(spare_block,pe,ins_pos - half);
         CB(l) = e->idxptr;
         CO(l) = CO(l) - half;
      }
    write_if(pci->ixfile, spare_block->brec,
             (char *) spare_block, sizeof(BLOCK));
	return 1;

  } /* split */


void  ins_level(  int l, ENTRY *e)
  {
    int  i;
    if ( l < 0)
      {  for (i = 1; i < MAX_LEVELS; i++)
           {  CO(MAX_LEVELS - i) = CO(MAX_LEVELS - i - 1);
              CB(MAX_LEVELS - i) = CB(MAX_LEVELS - i - 1);
           }
         memcpy(spare_block, &(pci->root), sizeof(BLOCK));
         spare_block->brec = get_free();
         write_if(pci->ixfile, spare_block->brec,
                  (char *) spare_block, sizeof(BLOCK));
         pci->root.p0 = spare_block->brec;
         copy_entry((ENTRY *) (pci->root.entries), e);
         pci->root.bend = ENT_SIZE(e);
         CO(0) = 0;
         pci->level = 0;
         (pci->dx.nl)++;
      }
    else ins_block(block_ptr,e,CO(l));
  } /* ins_level */


int  insert_ix(ENTRY *pe, IX_DESC *pix)
  {
    ENTRY    e, ee;
    pci = pix;
    ee = *pe;
    do
      {
         if(CO(pci->level) >= 0)
           CO(pci->level) +=
                  ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level)));
         else
           CO(pci->level) = 0;
         update_block();
         if( (block_ptr->bend + ENT_SIZE(&ee)) <= split_size)
           {
             ins_level(pci->level, &ee);
             break;
           }
         else
           {
             split(pci->level,&ee, &e);
              ee = e;
              pci->level--;
              if (pci->level < 0)
                {
                  ins_level(pci->level, &e);
                  break;
                }
              retrieve_block(pci->level, CB(pci->level));
           }
      }
    while (1);
    return ( IX_OK );
  } /* insert_ix */


/*  BPLUS find and add key functions  */

int  find_ix(  ENTRY *pe,   IX_DESC *pix, int find)
  {
    int      level, off, ret;
    RECPOS   ads;
    ENTRY    found;
    pci = pix;
    ads = 0L;
    level = ret = 0;
    while (ads != NULLREC)
      {  pci->level = level;
         retrieve_block(level, ads);
         if (find_block(pe, &off) == 0) ret = 1;
         if (ret && find) break;
         if (off == -1)
           ads = block_ptr->p0;
         else
           ads = ENT_ADR(block_ptr, off)->idxptr;
         CO(level++) = off;
       }
     return ( ret );
   } /* find_ix */


int  find_key(ENTRY *pe,   IX_DESC *pix)
  {
    int ret;
    ret = find_ix(pe, pix, 1);
    if ( ret ) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
    return ( ret );
  } /* find_key */


int  add_key(ENTRY *pe,   IX_DESC *pix)
  {
    int ret;
    ret = find_ix(pe, pix, 0);
    if ( ret && (pci->duplicate == 0)) return ( IX_FAIL );
    pe->idxptr = NULLREC;
    return (insert_ix(pe, pix));
  } /* add_key */


int  locate_key(  ENTRY *pe,   IX_DESC *pix)

  {
    int ret;
    ENTRY e;
    ret = find_ix(pe, pix, 1);
    if (ret) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
    else if (next_key(pe,pix) == EOIX) ret = EOIX;
    return ( ret );
  } /* locate_key */


int  find_exact(ENTRY *pe, IX_DESC * pix)
  {
    int  ret;
    ENTRY e;
    copy_entry(&e, pe);
    ret = find_key(&e, pix);
    if ( ret && pci->duplicate)
      {
        do
          {
            ret = (e.recptr == pe->recptr);
            if( !ret )  ret = next_key(&e, pci);
            if (ret) ret = (strcmp(e.key, pe->key) == 0);
            if ( !ret ) return ( 0 );
          } while ( !ret );
      }
    copy_entry(pe, &e);
    return ( ret );
  } /* find_exact */


/* BPLUS delete key functions */

int  delete_key(ENTRY *pe, IX_DESC *pix)
  {
     ENTRY   e;
     RECPOS  ads;
     int     h, leveli, levelf;
     if (!find_exact(pe, pix))  return( IX_FAIL );
     h = 1;
     if ((ads = pe->idxptr) != NULLREC)
       {
          leveli = pci->level;
          do
            {
               retrieve_block(++(pci->level), ads);
               CO(pci->level) = -1;
            }
          while ((ads = block_ptr->p0) != NULLREC);
          CO(pci->level) = 0;
          copy_entry(&e, ENT_ADR(block_ptr, CO(pci->level)));
          levelf = pci->level;
          pci->level = leveli;
          replace_entry(&e);
          pci->level = levelf;
       }
     while ( h )
       {
          retrieve_block(pci->level, CB(pci->level));
          del_block(block_ptr, CO(pci->level));
          update_block();
          if ( (pci->level == 0) && (block_ptr->bend == 0))
          /* tree was reduced in height */
            {
              if (pci->root.p0 != NULLREC)
                {
                  retrieve_block(++pci->level, pci->root.p0);
                  memcpy(&(pci->root), block_ptr, sizeof(BLOCK));
                  (pci->dx.nl)--;
                  write_free(block_ptr->brec, block_ptr);
                  BUFDIRTY(cache_ptr) = 0;
                  BUFHANDLE(cache_ptr) = 0;
                }
              break;
            }
          h = (block_ptr->bend < comb_size) && (pci->level > 0);
          if ( h )
              h = combineblk(CB(pci->level), block_ptr->bend);
       }
    return( IX_OK );
  } /* delete_key */


int  combineblk(RECPOS ads, int size)
  {
    ENTRY  e;
    RECPOS address;
    int    esize, off, ret, saveoff, ibuff;
    ret = 0;
    saveoff = CO(--(pci->level));
    retrieve_block(pci->level, CB(pci->level));
    if ((off = next_entry( saveoff )) < block_ptr->bend)
      /* combine with page on right */
      {
        if ( (ENT_SIZE(ENT_ADR(block_ptr, off)) + size) < split_size)
          {
            copy_entry(&e, ENT_ADR(block_ptr, off));
            address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
            retrieve_block(++pci->level, address);
            ibuff = cache_ptr;
            spare_block = block_ptr;
            retrieve_block(pci->level, ads);
            esize = ENT_SIZE(&e);
            if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
                 && (spare_block->bend <= block_ptr->bend + esize))
               return( ret );
            e.idxptr = spare_block->p0;
            ins_block(block_ptr, &e, block_ptr->bend);
            update_block();
            if ((block_ptr->bend + spare_block->bend) < split_size)
            /* combine the blocks */
              {
                memcpy(ENT_ADR(block_ptr, block_ptr->bend),
                       ENT_ADR(spare_block, 0),
                       spare_block->bend);
                block_ptr->bend += spare_block->bend;
                write_free(spare_block->brec, spare_block);
                BUFDIRTY(ibuff) = 0;
                BUFHANDLE(ibuff) = 0;
                --pci->level;
                ret = 1;
              }
            else
            /* move an entry up to replace the one moved */
              {
                copy_entry(&e, ENT_ADR(spare_block, 0));
                esize = ENT_SIZE(&e);
                movedown(spare_block, 0, esize);
                spare_block->bend -= esize;
                spare_block->p0 = e.idxptr;
                BUFDIRTY(ibuff) = 1;
                --(pci->level);
                replace_entry(&e);
              }
          }
      }
    else
      /* move from page on left */
      {
        if ( (ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level))) + size)
                 < split_size)
          {
            copy_entry(&e, ENT_ADR(block_ptr, saveoff));
            off = prev_entry(saveoff);
            if (CO(pci->level) == -1) address = block_ptr->p0;
            else address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
            retrieve_block(++pci->level, address);
            off = last_entry();
            ibuff = cache_ptr;
            spare_block = block_ptr;
            retrieve_block(pci->level, ads);
            esize = ENT_SIZE(&e);
            if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
                 && (spare_block->bend <= block_ptr->bend + esize))
               return( ret );
            BUFDIRTY(ibuff) = 1;
            CO(pci->level) = 0;
            e.idxptr = block_ptr->p0;
            ins_block(block_ptr, &e, 0);
            if ((block_ptr->bend + spare_block->bend) < split_size)
            /* combine the blocks */
              {
                memcpy(ENT_ADR(spare_block, spare_block->bend),
                       ENT_ADR(block_ptr, 0),
                       block_ptr->bend);
                spare_block->bend += block_ptr->bend;
                write_free(block_ptr->brec, block_ptr);
                BUFDIRTY(cache_ptr) = 0;
                BUFHANDLE(cache_ptr) = 0;
                CO(--(pci->level)) = saveoff;
                ret = 1;
              }
            else
            /* move an entry up to replace the one moved */
              {
                 block_ptr->p0 = ENT_ADR(spare_block,off)->idxptr;
                 copy_entry(&e, ENT_ADR(spare_block, off));
                 spare_block->bend = off;
                 update_block();
                 CO(--(pci->level)) = saveoff;
                 replace_entry(&e);
              }
          }
      }
    return ( ret );
  } /* combineblk */


void  replace_entry(ENTRY *pe)
  {
    retrieve_block(pci->level, CB(pci->level));
    pe->idxptr = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
    del_block(block_ptr, CO(pci->level));
    prev_entry(CO(pci->level));
    insert_ix(pe, pci);
  } /* replace_entry */