B+ Tree Source Analysis

소개글

B+ Tree Source Analysis에 대한 보고서 자료입니다.

본문내용

) == BT_ERR) {
bt_perror(globf,"cannot goto EOF");
return;
}
} else {
d = BT_EOF;
if(bt_goto(globf,BT_BOF) == BT_ERR) {
bt_perror(globf,"cannot goto BOF");
return;
}
}
while((ret = bt_traverse(globf,d,buf,BUFSIZ,&retlen,&junk)) == BT_OK) {
printk(buf,retlen,junk);
}
if(ret == BT_ERR)
bt_perror(globf,"error traversing!");
}
------------------------------ btravrs.c --------------------
#include
#include
#include "btconf.h"
#include "btree.h"
#include "btintern.h"
#ifndef lint
static char *rcsid = "$Header: /atreus/mjr/hacks/btree/btlib/RCS/btravrs.c,v 1.1 89/10/24 10:09:06 mjr Rel $";
#endif
bt_traverse(b,d,kbuf,maxlen,retlen,retrrv)
BT_INDEX *b;
int d;
bt_chrp kbuf;
int maxlen;
int *retlen;
off_t *retrrv;
{
struct bt_cache *p;
off_t savp;
/* if the current page is not set, just zing up to the head */
/* or the tail - the opposite side of the tree, whatever it is */
if(b->cpag == BT_NULL)
if(bt_goto(b,d == BT_EOF ? BT_BOF:BT_EOF) == BT_ERR)
return(BT_ERR);
/* save */
savp = b->cpag;
if((p = bt_rpage(b,b->cpag)) == NULL)
return(BT_ERR);
/* adjust current key # */
if(d == BT_EOF)
b->cky++;
else
b->cky--;
/* have we run out of keys in the page ? */
while((d == BT_EOF && b->cky >= KEYCNT(p->p)) ||
(d == BT_BOF && b->cky < 0)) {
if(d == BT_EOF)
b->cpag = RSIB(p->p);
else
b->cpag = LSIB(p->p);
/* we are there - wherever there is */
if(b->cpag != BT_NULL) {
if((p = bt_rpage(b,b->cpag)) == NULL)
return(BT_ERR);
/* reset current key */
if(d == BT_EOF)
b->cky = 0;
else
b->cky = KEYCNT(p->p) - 1;
} else {
/* we have actually HIT the end */
/* restore current page */
b->cpag = savp;
/* and point the key just past the end of the page */
if(d == BT_EOF)
b->cky = KEYCNT(p->p);
else
b->cky = -1;
*retlen = 0;
*retrrv = 0;
return(d);
}
}
if(bt_keyof(b->cky,p->p,kbuf,retlen,retrrv,maxlen) == BT_ERR)
return(BT_ERR);
/* mark all as well with tree */
bt_clearerr(b);
return(BT_OK);
}
-----------------------btree.h -----------------------------------
/* forward decls. */
extern BT_INDEX *bt_open();
extern BT_INDEX *bt_optopen();
extern void bt_perror();
------------------------------ testrack.c ----------------- ----
/* see if the key is a duplicate that was already deleted */
/* and if so, do not try to re-delete it */
ret = bt_find(d,buf,strlen(buf),&rrv);
if(ret == BT_NF) {
/* not in the deleted index, so delete it and add it */
/* step 1: delete from real index */
if(bt_delete(b,buf,strlen(buf)) != BT_OK) {
bt_perror(b,"delete failed\n");
die(b,d,16);
}
/* step 2: add it to the deleted index */
if(bt_insert(d,buf,strlen(buf),-1L,1) != BT_OK) {
bt_perror(d,"insert in deleted failed\n");
die(b,d,17);
}
} else {
if(ret != BT_OK) {
bt_perror(d,"search for deleted failed\n");
die(b,d,18);
}
}
}
-----------------------------btest.c ------------------------
void do_close()
{
if(globf != NULL) {
if(bt_close(globf) == BT_OK)
(void)printf("closed OK\n");
else
(void)printf("error closing\n");
} else {
(void)printf("nothing open\n");
}
globf = NULL;
}

키워드

B+,   tree,   검색,   분석,   소스