?? 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);
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -