Read-only archive view · 1993-10-26 · 16,016 bytes · SHA-256 E58932CA7F6514B01F5C8257FC19EB5ED4034E28F7A2EDE303B0D501F8C7B852
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "fcntl.h"
#if MSDOS
#include "io.h"
#include "sys\stat.h"
#endif
#include "xbindex.h"
#define FREE_LEVEL (-1)
#define BOF_REL 0
extern int sizef();
extern int compf();
extern int ndum;
extern int fs;
extern ENTRY dume;
int split_size = IXB_SPACE;
int comb_size = (IXB_SPACE/2);
IX_DESC *pci;
BLOCK spare_block;
#if !MSDOS
void memmove(char *to,char *from,unsigned int count)
{
movmem(from,to,count);
}
#endif
int make_index(char *fn,int dupok,int field_no)
{
/* SI is not need just to create an index, SI is used when the index is
opened with a datafile. */
int dupixok;
dupixok = dupok;
if (creatix(fn,fs,&dume,ndum,field_no)<0)
return(0);
else
return(1);
}
int first_key(ENTRY *pe,IX_DESC *pix)
{
if (go_first(pix)==IX_OK)
{
get_current(pe,pix);
return((int)pe->rptr);
}
else
return(0);
}
int last_key(ENTRY *pe,IX_DESC *pix)
{
if (go_last(pix)==IX_OK)
{
get_current(pe,pix);
return((int)pe->rptr);
}
else
return(0);
}
int next_key(ENTRY *pe,IX_DESC *pix)
{
if (get_next(pe,pix) == IX_OK)
return((int)pe->rptr);
else
return(EOIX);
}
int prev_key(ENTRY *pe,IX_DESC *pix)
{
if (get_previous(pe,pix) == IX_OK)
return((int)pe->rptr);
else
return(EOIX);
}
int find_key(ENTRY *pe,IX_DESC *pix)
{
if (find_ix(pe,pix) == IX_OK)
{
get_current(pe,pix);
return((int)pe->rptr);
}
else
return(0);
}
int add_key(ENTRY *pe,IX_DESC *pix)
{
if (find_ins(pe,pix) == IX_OK)
return(1);
else
return(0);
}
int locate_key(ENTRY *pe,IX_DESC *pix)
{
return(0);
}
int delete_key(ENTRY *pe,IX_DESC *pix)
{
if (find_del(pe,pix)==IX_FAIL)
return(0);
else
return(1);
}
/* book code - "The C Toolbox" by William Hunt */
int prev_entry(BLOCK *pb,int off)
{
if (off <= 0)
return (-1) ;
off = scan_blk(pb,off);
return(off);
}
int next_entry(BLOCK *pb,int off)
{
if (off >= pb->bend)
return(-1);
off = off+ENT_SIZE(ENT_ADR(pb,off));
if (off >= pb->bend)
return(-1);
return(off);
}
void copy_entry(ENTRY *to,ENTRY *from)
{
int ne;
ne = ENT_SIZE(from);
memmove((char *)to,(char *)from,ne);
}
int scan_blk(BLOCK *pb,int n)
{
int i,last;
i=0;last=0;
while(i<n)
{
last = i;
i = i+ENT_SIZE(ENT_ADR(pb,i));
}
return(last);
}
int last_entry(BLOCK *pb)
{
return(scan_blk(pb,pb->bend));
}
FILE *creat_if(char fn[])
{
return(fopen(fn,"wb+"));
}
int read_if(RECPOS start,char buf[],int nrd)
{
fseek(pci->ixfile,start,BOF_REL);
return(fread(buf,nrd,1,pci->ixfile));
}
int write_if(RECPOS start,char buf[],int nwrt)
{
fseek(pci->ixfile,start,BOF_REL);
return(fwrite(buf,nwrt,1,pci->ixfile));
}
/* may need to examine this */
int close_if()
{
if (fclose(pci->ixfile)==0)
return(1);
else
return(0);
}
FILE *open_if(char fn[])
{
return(fopen(fn,"rb+"));
}
void make_free(RECPOS fstart,RECPOS filesize)
{
BLOCK *pb;
RECPOS r;
pb = &spare_block;
pci->dx.ff = NULLREC;
for (r=fstart;r<filesize;r=r+IXB_SIZE)
write_free(r,pb);
}
RECPOS get_free()
{
RECPOS r, rt;
r=pci->dx.ff;
if (r!=NULLREC)
{
read_if(r,(char *)&rt,sizeof(RECPOS));
pci->dx.ff = rt;
}
return(r);
}
void write_free(RECPOS r,BLOCK *pb)
{
pb->lvl=FREE_LEVEL;
memset((char *)&pb->entries,0,IXB_SPACE);
pb->brec=pci->dx.ff;
write_block(r,pb);
pci->dx.ff = r;
}
void init_bio()
{
init_cache();
}
int retrieve_block(int l,RECPOS r,BLOCK *pb,int current)
{
if (chk_cache(l,r) !=0)
get_cache(l,r,pb);
else
{
read_block(r,pb);
pb->brec = r;
pb->lvl = l;
if (current)
put_cache(l,pb);
}
return(IX_OK);
}
void update_block(BLOCK *pb)
{
if (chk_cache(pb->lvl,pb->brec) !=0)
put_cache(pb->lvl,pb);
write_block(pb->brec,pb);
}
int get_block(int l,BLOCK *pb)
{
RECPOS r;
r = get_free();
if (r==NULLREC)
return(IX_FAIL);
pb->brec = r;
pb->lvl = l;
return(IX_OK);
}
void put_free(BLOCK *pb)
{
scrub_cache(pb->brec);
pb->lvl = FREE_LEVEL;
write_free(pb->brec,pb);
}
int read_block(RECPOS r,BLOCK *pb)
{
int ret;
ret = read_if(r,(char *)pb,sizeof(BLOCK));
return(ret);
}
int write_block(RECPOS r,BLOCK *pb)
{
int ret;
ret = write_if(r,(char*)pb,sizeof(BLOCK));
return(ret);
}
void init_cache()
{
int l;
for (l=0;l<MAX_LEVELS;l++)
pci->cache[l].brec = NULLREC;
}
int chk_cache(int l, RECPOS r)
{
/* BLOCK *pb; */
if (pci->cache[l].brec != r)
return(0);
return(1);
}
int get_cache(int l,RECPOS r,BLOCK *to)
{
BLOCK *pb;
if (pci->cache[l].brec != r)
return(0);
pb = &pci->cache[l];
memmove((char*)to,(char *)pb,sizeof(BLOCK));
pb->brec = r;
return(1);
}
void put_cache(int l, BLOCK *pb)
{
BLOCK *to;
to = &pci->cache[l];
memmove((char *)to,(char *)pb,sizeof(BLOCK));
}
void scrub_cache(RECPOS r)
{
int l;
for (l=0;l<pci->dx.nl;l++)
{
if ((r==NULLREC) || (r==pci->cache[l].brec))
pci->cache[l].brec = NULLREC;
}
}
int openix(char name[],IX_DESC *pix,int (*cfun) (),int (*sfun) ())
{
FILE *ret;
pci = pix;
ret = open_if(name);
if (ret == 0)
return(IX_FAIL);
pci->ixfile = ret;
read_if(0L,(char *)&pix->dx,sizeof(IX_DISK));
pci->pcomp = cfun;
pci->psize = sfun;
init_bio();
go_first(pix);
return(IX_OK);
}
void closeix(IX_DESC *pix)
{
pci = pix;
write_if(0L,(char *)&pci->dx,sizeof(IX_DISK));
close_if();
}
int creatix(char name[],long filesize,ENTRY *pdum,int ndum,int field_no)
{
BLOCK b;
IX_DESC ixd;
FILE *ret;
memset((char *)&ixd,0,sizeof(IX_DESC));
pci = &ixd;
ret = creat_if(name);
if (ret == 0)
return(IX_FAIL);
ixd.ixfile = ret;
ixd.dx.nl = MAX_LEVELS;
ixd.dx.order = field_no;
memmove((char *)&ixd.dx.dume,(char *)pdum,ndum);
memset((char *)&b,0,sizeof(BLOCK));
write_block(0L,&b);
ixd.dx.rb = wrt_dum(pdum,ndum);
make_free(((RECPOS)(MAX_LEVELS+1))*IXB_SIZE,filesize);
closeix(&ixd);
return(IX_OK);
}
RECPOS wrt_dum(ENTRY *pdum, int ndum)
{
BLOCK b;
int l;
RECPOS r;
pdum->rptr = NULLREC;
r = 0;
for (l=0;l<MAX_LEVELS;l++)
{
r=r+IXB_SIZE;
memmove((char *)&b.entries,(char *)pdum,ndum);
b.lvl = l;
b.bend = ndum;
write_block(r,&b);
pdum->rptr = r;
}
return(r);
}
void removeix(char name[])
{
unlink(name);
}
int go_first(IX_DESC *pix)
{
BLOCK b;
pci = pix;
first_ix(pci->dx.nl-1,pci->dx.rb,&b);
return(IX_OK);
}
void first_ix(int l,RECPOS r,BLOCK *pb)
{
CB(l) = r;
CO(l) = 0;
retrieve_block(l,CB(l),pb,CURR);
if (l > 0)
first_ix(l-1,ENT_ADR(pb,0)->rptr,pb);
}
int go_last(IX_DESC *pix)
{
BLOCK b;
pci = pix;
final_ix(pci->dx.nl-1,pci->dx.rb,&b);
return(IX_OK);
}
void final_ix(int l, RECPOS r, BLOCK *pb)
{
int off;
CB(l) = r;
retrieve_block(l,r,pb,CURR);
off = last_entry(pb);
CO(l) = off;
if (l > 0)
final_ix(l-1,ENT_ADR(pb,off)->rptr,pb);
}
int get_next(ENTRY *pe,IX_DESC *pix)
{
BLOCK b;
pci = pix;
copy_current(0,pe);
if (call(pci->pcomp)(pe,&pci->dx.dume)==0)
return(EOIX);
if (next_ix(0,&b) != NULLREC)
{
copy_current(0,pe);
return(IX_OK);
}
else
return(EOIX);
}
RECPOS next_ix(int l,BLOCK *pb)
{
int off;
RECPOS newblk;
RECPOS temp;
if (l >= pci->dx.nl)
return(NULLREC);
retrieve_block(l,CB(l),pb,CURR);
off = next_entry(pb,CO(l));
if (off >= 0)
CO(l) = off;
else
{
newblk=next_ix(l+1,pb);
if (newblk!=NULLREC)
{
CB(l) = newblk;
retrieve_block(l,CB(l),pb,CURR);
CO(l) = 0;
}
else
return(NULLREC);
}
temp = (RECPOS)(ENT_ADR(pb,CO(l))->rptr);
return(temp);
}
int get_previous(ENTRY *pe,IX_DESC *pix)
{
BLOCK b;
pci = pix;
if (last_ix(0,&b) != NULLREC)
{
copy_current(0,pe);
return(IX_OK);
}
else return(EOIX);
}
RECPOS last_ix(int l,BLOCK *pb)
{
int off;
RECPOS newblk;
if (l >= pci->dx.nl)
return(NULLREC);
retrieve_block(l,CB(l),pb,CURR);
off = prev_entry(pb,CO(l));
if (off >= 0)
CO(l) = off;
else
{
newblk = last_ix(l+1,pb);
if (newblk != NULLREC)
{
CB(l) = newblk;
retrieve_block(l,CB(l),pb,CURR);
CO(l) = last_entry(pb);
}
else return(NULLREC);
}
return((RECPOS)ENT_ADR(pb,CO(l))->rptr);
}
void get_current(ENTRY *pe,IX_DESC *pix)
{
pci = pix;
copy_current(0,pe);
}
int find_block(ENTRY *pe,BLOCK *pb,int *poff,int (*comp_fun) ())
{
int i;
int ret;
ENTRY *p;
i = 0;
while(i<pb->bend)
{
p = ENT_ADR(pb,i);
ret = call(comp_fun)(pe,ENT_ADR(pb,i));
if (ret<=0)
break;
i = next_entry(pb,i);
}
*poff = i;
return(ret);
}
void ins_block(BLOCK *pb,ENTRY *pe,int off)
{
int ne;
ne = ENT_SIZE(pe);
moveup(pb,off,ne);
copy_entry(ENT_ADR(pb,off),pe);
pb->bend = pb->bend + ne;
}
void del_block(BLOCK *pb,int off)
{
int ne;
ne = ENT_SIZE(ENT_ADR(pb,off));
movedown(pb,off,ne);
pb->bend = pb->bend - ne;
}
void moveup(BLOCK *pb,int off,int n)
{
/* ENTRY *p; */
memmove((char *)ENT_ADR(pb,off+n),
(char *)ENT_ADR(pb,off),
pb->bend-off);
}
void movedown(BLOCK *pb,int off,int n)
{
/* ENTRY *p; */
memmove((char *)ENT_ADR(pb,off),
(char *)ENT_ADR(pb,off+n),
pb->bend-(off+n));
}
void combine(BLOCK *pl,BLOCK *pr)
{
moveup(pr,0,pl->bend);
memmove((char *)ENT_ADR(pr,0),(char *)ENT_ADR(pl,0),pl->bend);
pr->bend = pr->bend + pl->bend;
}
int find_ix(ENTRY *pe,IX_DESC *pix)
{
int ret;
ENTRY tempe;
pci = pix;
if (call(pci->pcomp)(pe,&pci->dx.dume)>=0)
{
go_last(pix);
return(1);
}
ret = find_level(pci->dx.nl-1,pe,pci->dx.rb);
if (ret==0)
{
copy_current(0,&tempe);
pe->rptr=tempe.rptr;
}
return(ret);
}
int find_level(int l,ENTRY *pe,RECPOS r)
{
BLOCK b;
int ret,off;
retrieve_block(l,r,&b,CURR);
ret=find_block(pe,&b,&off,pci->pcomp);
CB(l) = r;
CO(l) = off;
if (l>0)
ret = find_level(l-1,pe,ENT_ADR(&b,off)->rptr);
return(ret);
}
int insert_ix(ENTRY *pe,IX_DESC *pix)
{
int ret;
BLOCK b;
pci = pix;
ret = ins_level(0,pe,&b);
if (ret==IX_OK)
next_ix(0,&b);
return(ret);
}
int ins_level(int l,ENTRY *pe,BLOCK *pb)
{
/* RECPOS r; */
int ret;
if (l>=pci->dx.nl)
return(IX_FAIL);
retrieve_block(l,CB(l),pb,CURR);
if ((pb->bend+ENT_SIZE(pe)) <= split_size)
{
ins_block(pb,pe,CO(l));
update_block(pb);
ret = IX_OK;
}
else
ret = split(l,pe,pb);
return(ret);
}
int split(int l,ENTRY *pe,BLOCK *pb)
{
int half,ins_pos,last,ret;
BLOCK *pbb;
ENTRY e;
ins_pos = CO(l);
if ((l+1) >= pci->dx.nl)
return(IX_FAIL);
pbb = (BLOCK *) calloc(1,sizeof(BLOCK)+sizeof(ENTRY));
if (pbb == NULL)
return(IX_FAIL);
pbb->bend = 0;
combine(pb,pbb);
ins_block(pbb,pe,CO(l));
last = scan_blk(pbb,pbb->bend/2);
half = next_entry(pbb,last);
if (get_block(l,pbb)==IX_FAIL)
{
free((void *)pbb);
return(IX_FAIL);
}
copy_entry(&e,ENT_ADR(pbb,last));
e.rptr = pbb->brec;
ret=ins_level(l+1,&e,pb);
if (ret != IX_OK)
{
free((void *)pbb);
put_free(pbb);
return(ret);
}
memmove((char *)ENT_ADR(pb,0),(char *)ENT_ADR(pbb,half),pbb->bend-half);
pb->bend = pbb->bend - half;
pb->brec = CB(l);
pb->lvl = l;
update_block(pb);
pbb->bend = half;
update_block(pbb);
if(ins_pos >= half)
{
CO(l) = CO(l)-half;
next_ix(l+1,pb);
}
else
CB(l) = e.rptr;
free((void *)pbb);
return(ret);
}
int delete_ix(IX_DESC *pix)
{
ENTRY tempe;
BLOCK b;
int ret;
pci = pix;
copy_current(0,&tempe);
if (call(pci->pcomp)(&tempe,&pci->dx.dume)==0)
return(IX_FAIL);
ret = del_level(0,&b);
return(ret);
}
int del_level(int l,BLOCK *pb)
{
/* RECPOS r; */
int ret;
ENTRY tempe;
ret = IX_OK;
retrieve_block(l,CB(l),pb,CURR);
del_block(pb,CO(l));
if (pb->bend == 0)
{
put_free(pb);
ret=del_level(l+1,pb);
copy_current(l+1,&tempe);
/* first_ix(l,pb,tempe.rptr) (sic) */
first_ix(l,tempe.rptr,pb);
return(ret);
}
if (CO(l) >= pb->bend)
fix_last(l,pb->brec,ENT_ADR(pb,last_entry(pb)));
if (pb->bend < comb_size)
ret = compress(l,pb);
else
update_block(pb);
retrieve_block(l,CB(l),pb,CURR);
if (CO(l) >= pb->bend)
/* first_ix(l,pb,next_ix(l+1)); (sic) */
first_ix(l,next_ix(l+1,pb),pb);
return(ret);
}
int compress(int l,BLOCK *pb)
{
/* int nb; */
BLOCK *pt;
/* ENTRY tempe; */
if ((l+1) == pci->dx.nl)
{
update_block(pb);
return(IX_OK);
}
pt = neighbor(l,LEFTN);
if ((pt!=NULL) && (pt->bend+pb->bend <= IXB_SPACE))
{
combine(pt,pb);
update_block(pb);
put_free(pt);
CO(l)=CO(l)+pt->bend;
last_ix(l+1,pb);
del_level(l+1,pb);
return(IX_OK);
}
pt = neighbor(l,RIGHTN);
if ((pt!=NULL) && (pt->bend+pb->bend <= IXB_SPACE))
{
combine(pb,pt);
update_block(pt);
CB(l) = pt->brec;
put_free(pb);
del_level(l+1,pb);
return(IX_OK);
}
update_block(pb);
return(IX_OK);
}
int fix_last(int l,RECPOS r, ENTRY *pe)
{
ENTRY tempe;
copy_entry(&tempe,pe);
tempe.rptr = r;
return(replace_entry(l+1,&tempe));
}
int replace_entry(int l,ENTRY *pe)
{
BLOCK b;
int ret;
retrieve_block(l,CB(l),&b,CURR);
if (CO(l) == last_entry(&b))
fix_last(l,CB(l),pe);
del_block(&b,CO(l));
if ((b.bend+ENT_SIZE(pe)) <= split_size)
{
ins_block(&b,pe,CO(l));
update_block(&b);
ret = IX_OK;
}
else
ret = split(l,pe,&b);
return(ret);
}
BLOCK *neighbor(int l,int direction)
{
RECPOS rnext;
int off;
BLOCK *pb;
pb=&spare_block;
l++;
retrieve_block(l,CB(l),pb,CURR);
if (direction == RIGHTN)
off = next_entry(pb,CO(l));
else
off = prev_entry(pb,CO(l));
if (off < 0)
return(NULL);
rnext = ENT_ADR(pb,off)->rptr;
retrieve_block(l-1,rnext,pb,NOT_CURR);
return(pb);
}
int copy_current(int l,ENTRY *pe)
{
BLOCK *pb;
pb = &spare_block;
retrieve_block(l,CB(l),pb,CURR);
copy_entry(pe,ENT_ADR(pb,CO(l)));
return(IX_OK);
}
int find_exact(ENTRY *pe,IX_DESC *pix)
{
int ret;
ENTRY e;
pci = pix;
copy_entry(&e,pe);
ret = find_ix(&e,pix);
while(ret == 0)
{
if (e.rptr==pe->rptr)
return(0);
if (get_next(&e,pix)==EOIX)
return(1);
ret=call(pci->pcomp) (&e,pe);
}
return(ret);
}
int find_ins(ENTRY *pe, IX_DESC *pix)
{
/* int ret;
ENTRY tempe; */
if (find_exact(pe,pix) == 0)
return(IX_FAIL);
return(insert_ix(pe,pix));
}
int find_del(ENTRY *pe,IX_DESC *pix)
{
/* int ret;
ENTRY tempe; */
if (find_exact(pe,pix) != 0)
return(IX_FAIL);
return(delete_ix(pix));
}