page.c

R+树的c实现源码

/* #define DEBUG 1 */
# include <stdio.h>
#include <sys/types.h>
#include <sys/file.h>
#include "macros.h"
#include "options.h"
#include "index.h"
#include "global.h"
#include "assert.h"

extern int	pageNo;

#ifdef DEBUG
	extern int magicNum;
#endif

struct Node *
GetOnePage( idxp, offset )
int idxp;
off_t offset;
{
    struct Node *node;
    char ws[PAGESIZE];
    short int level;
    int n;

#ifdef DEBUG
	printf("I TRY TO GET A LEAF/NONLEAF PAGE AT OFFSET %d\n",offset);
	printf("GLOBAL pageNo = %d\n",pageNo);
#endif
    assert( offset >= 0 );
    node = (struct Node *) myalloc (sizeof(struct Node));
    lseek( idxp, offset*LPAGESIZE, L_SET );
    n = read( idxp, ws, PAGESIZE );
    bcopy(ws+COUNT_SIZE,(char *) &level, LEVEL_SIZE);

    if (level == 0) RReadOneLPage( idxp, ws, node, offset);
    else RReadOnePage( idxp, ws, node, offset);
    return node;
}

int
ReadOnePage( idxp,node,offset,level )
int		idxp;
struct Node	*node;
off_t		offset;
int	level;
{
    char ws[PAGESIZE];
    int n;

    assert( offset >= 0 );
    assert(node);
    lseek( idxp, offset*LPAGESIZE, L_SET );
    n = read( idxp, ws, PAGESIZE );

    if (level == 0) RReadOneLPage( idxp, ws, node, offset);
    else RReadOnePage( idxp, ws, node, offset);

    return ;
}

int
RReadOnePage( idxp,ws,node,offset )
int		idxp;
char		*ws;
struct Node	*node;
off_t		offset;
{
    int n;
    register int i, j;
    int d1, d2;

#ifdef DEBUG
    int CheckFullCover();
    int mmm=1;
    struct Branch ba[NODECARD+1];

    if (offset == magicNum)
        mmm = 1;
#endif
#ifdef DEBUG
	printf("\tI TRY TO READ A PAGE AT OFFSET %d\n",offset);
#endif

    assert( offset >= 0 );
    node->pageNo = offset;
    bcopy(ws,(char *) &(node->count), COUNT_SIZE);
    bcopy(ws+COUNT_SIZE,(char *) &(node->level), LEVEL_SIZE);

    for( i=0; i<NUMDIMS; i++ ) {
        d1 = HEAD_SIZE + i * COORD_SIZE;
        d2 = d1 + COORD_SIZE * NUMDIMS;
	bcopy(ws+d1,(char *) &(node->rect.boundary[i]), COORD_SIZE);
	bcopy(ws+d2,(char *) &(node->rect.boundary[i+NUMDIMS]), COORD_SIZE);
    }
    for ( i=0; i<NODECARD; i++ ) {
        for( j=0; j<NUMDIMS; j++ ) {
            d1 = HEAD_SIZE + COORD_SIZE * NUMSIDES + i * BRANCHSIZE + j * POINTER_SIZE;
            d2 = d1 + COORD_SIZE * NUMDIMS;
	    bcopy(ws+d1,(char *) &(node->branch[i].minrect.boundary[j]), COORD_SIZE);
	    bcopy(ws+d2,(char *) &(node->branch[i].minrect.boundary[j+NUMDIMS]), COORD_SIZE);
        }
        for( j=0; j<NUMDIMS; j++ ) { 
            d1 = HEAD_SIZE + 2 * COORD_SIZE * NUMSIDES + i * BRANCHSIZE + j * POINTER_SIZE;
            d2 = d1 + COORD_SIZE * NUMDIMS;
	    bcopy(ws+d1,(char *) &(node->branch[i].rect.boundary[j]), COORD_SIZE);
	    bcopy(ws+d2,(char *) &(node->branch[i].rect.boundary[j+NUMDIMS]), COORD_SIZE);
        }
        d1 = HEAD_SIZE + 3 * COORD_SIZE * NUMSIDES + i * BRANCHSIZE; 
	bcopy(ws+d1,(char *) &(node->branch[i].son), POINTER_SIZE);
    }
    if ( pageNo == 0 )  /* the reading page must be the root node */
	bcopy(ws+PAGESIZE-sizeof(int) ,(char *) &pageNo, sizeof(int));

#ifdef DEBUG
    if ( node->level > 0 ) {
        if (CheckFullCover( node ) == FALSE)  {
	    ba[0].rect = node->rect;
            for (i=0; i<NODECARD; i++)
                if (node->branch[i].son >= 0)
                    ba[mmm++].rect = node->branch[i].rect;
/*            draw( ba, mmm ); */
        }
    }
#endif
#ifdef DEBUG
	printf("\tI READ PAGE NUMBER %d LEVEL=%d AT OFFSET %d\n",node->pageNo,node->level,offset);
#endif

    return ;
}

int
RReadOneLPage( idxp,ws,node,offset )
int		idxp;
char		*ws;
struct Node	*node;
off_t		offset;
{
    int n;
    register int i, j;
    int d1, d2;
    struct Rect IntersectRect();

#ifdef DEBUG
    int CheckFullCover();
    int mmm=1;
    struct Branch ba[NODECARD+1];

    if (offset == magicNum)
        mmm = 1;
#endif

#ifdef DEBUG
	printf("\tI TRY TO READ A LEAF PAGE AT OFFSET %d\n",offset);
#endif
    assert( offset >= 0 );
    assert(node);
    node->pageNo = offset;
    bcopy(ws,(char *) &(node->count), COUNT_SIZE);
    bcopy(ws+COUNT_SIZE,(char *) &(node->level), LEVEL_SIZE);

    for( i=0; i<NUMDIMS; i++ ) {
        d1 = HEAD_SIZE + i * COORD_SIZE;
        d2 = d1 + COORD_SIZE * NUMDIMS;
	bcopy(ws+d1,(char *) &(node->rect.boundary[i]), COORD_SIZE);
	bcopy(ws+d2,(char *) &(node->rect.boundary[i+NUMDIMS]), COORD_SIZE);
    }
    for ( i=0; i<NODECARD; i++ ) {
        for( j=0; j<NUMDIMS; j++ ) {
            d1 = HEAD_SIZE + COORD_SIZE * NUMSIDES + i * LBRANCHSIZE + j * POINTER_SIZE;
            d2 = d1 + COORD_SIZE * NUMDIMS;
	    bcopy(ws+d1,(char *) &(node->branch[i].rect.boundary[j]), COORD_SIZE);
	    bcopy(ws+d2,(char *) &(node->branch[i].rect.boundary[j+NUMDIMS]), COORD_SIZE);
        }
	node->branch[i].minrect = IntersectRect(&node->branch[i].rect,&node->rect);

        d1 = HEAD_SIZE + 2 * COORD_SIZE * NUMSIDES + i * LBRANCHSIZE; 
	bcopy(ws+d1,(char *) &(node->branch[i].son), POINTER_SIZE);
    }
    if ( pageNo == 0 )  /* the reading page must be the root node */
	bcopy(ws+LPAGESIZE-sizeof(int) ,(char *) &pageNo, sizeof(int));

#ifdef DEBUG
    if ( node->level > 0 ) {
        if (CheckFullCover( node ) == FALSE)  {
	    ba[0].rect = node->rect;
            for (i=0; i<NODECARD; i++)
                if (node->branch[i].son >= 0)
                    ba[mmm++].rect = node->branch[i].rect;
/*            draw( ba, mmm ); */
        }
    }
#endif

#ifdef DEBUG
	printf("\tI READ LEAF PAGE NUMBER %d LEVEL=%d AT OFFSET %d\n",node->pageNo,node->level,offset);
#endif

    return ;
}

PutOnePage( idxp, offset, node )
int idxp;
off_t offset;
struct Node *node;
{
    if (node->level == 0) RPutOneLPage(idxp,offset,node);
    else RPutOnePage(idxp,offset,node);
}

RPutOnePage( idxp, offset, node )
int idxp;
off_t offset;
struct Node *node;
{
    char ws[PAGESIZE];
    register int i, j;
    int d1, d2;

#ifdef DEBUG
    int CheckFullCover();
    int mmm=1;
    struct Branch ba[NODECARD+1];

    if (offset == magicNum)
        mmm = 1;
    if (node->pageNo != offset)
        mmm = 1;
    
    if (node->level > 0) {
       if (CheckFullCover( node ) == FALSE)  {
/*	    PrintNode(node); */
	    printf("not full   ERROR  ERROR    ERROR    ERROR.\n");
            ba[0].rect = node->rect;
            for (i=0; i<NODECARD; i++) 
	        if (node->branch[i].son >= 0) 
	            ba[mmm++].rect = node->branch[i].rect;
/*            draw( ba, mmm ); */
        }
    }
#endif

    bcopy((char *) &(node->count),ws, COUNT_SIZE);
    bcopy((char *) &(node->level),ws+COUNT_SIZE, LEVEL_SIZE);

    for( i=0; i<NUMDIMS; i++ ) {
        d1 = HEAD_SIZE + i * COORD_SIZE;
        d2 = d1 + COORD_SIZE * NUMDIMS;
	bcopy((char *) &(node->rect.boundary[i]),ws+d1, COORD_SIZE);
	bcopy((char *) &(node->rect.boundary[i+NUMDIMS]),ws+d2, COORD_SIZE);
    }
    for ( i=0; i<NODECARD; i++ ) {
        for( j=0; j<NUMDIMS; j++ ) {
            d1 = HEAD_SIZE + COORD_SIZE * NUMSIDES + i * BRANCHSIZE + j * POINTER_SIZE;
            d2 = d1 + COORD_SIZE * NUMDIMS;
	    bcopy((char *) &(node->branch[i].minrect.boundary[j]),ws+d1, COORD_SIZE);
	    bcopy((char *) &(node->branch[i].minrect.boundary[j+NUMDIMS]),ws+d2, COORD_SIZE);
        }
        for( j=0; j<NUMDIMS; j++ ) { 
            d1 = HEAD_SIZE + 2 * COORD_SIZE * NUMSIDES + i * BRANCHSIZE + j * POINTER_SIZE;
            d2 = d1 + COORD_SIZE * NUMDIMS;
	    bcopy((char *) &(node->branch[i].rect.boundary[j]),ws+d1, COORD_SIZE);
	    bcopy((char *) &(node->branch[i].rect.boundary[j+NUMDIMS]),ws+d2, COORD_SIZE);
        }
        d1 = HEAD_SIZE + 3 * COORD_SIZE * NUMSIDES + i * BRANCHSIZE; 
	bcopy((char *) &(node->branch[i].son),ws+d1, POINTER_SIZE);
    }
    if ( offset == 0 )  /* the reading page must be the root node */
	bcopy((char *) &pageNo, ws+PAGESIZE-sizeof(int) , sizeof(int));

    lseek( idxp, offset*LPAGESIZE, L_SET ); 
    write( idxp, ws, PAGESIZE );
#ifdef DEBUG
	printf("\tI WROTE PAGE NUMBER %d LEVEL=%d AT OFFSET %d\n",node->pageNo,node->level,offset);
#endif
}