bfh.c

btree的实现源代码

		return FAILED;
	}
	/* Is the request on a user block boundry ? */
	if( ( (block_addr - (2*BFHBLOCK) -1) % bfh->block_size ) != 0){
		Debug( "Invalid block address\n");
		return FAILED;
	}
	/* Go to the requested block's switch byte */
	if(lseek(bfh->file_fd, block_addr - 1L,0) == -1L){
		Debug( "Cant seek\n");
		return FAILED;
	}
	if(read(bfh->file_fd, &inuse, 1) == -1){
		Debug( "Cant read key in\n");
		return FAILED;
	}
	inuse &= BFHBLOCKINUSE;
	/* User can only write a block they are already using */
	if(!inuse){
		Debug( "BfhWriteBlock attempt to overwrite free list entry\n");
		return FAILED;
	}
	/* Now we are in position over the user block */
	if(write(bfh->file_fd,ptr,bfh->block_size-1) == -1){
		Debug( "Cant write bdata\n");
		return FAILED;
	}
	bfh->date_updated = time(NULL);
	return SUCCESS;
}

/*
 NAME:	ReadBlock

 DESCRIPTION: 	Read the block at the user specified address

 RETURN:	SUCCESS or FAILED or EMPTY
*/

int BfhReadBlock(	BFH * bfh, /* pointer to descriptor */
			char * ptr, /* address in which to place data */
			long block_addr /* block id */)
{  

	char cswitch;

	Trace("BfhReadBlock(%x, %x, %ld)\n",
		(unsigned)bfh, (unsigned)ptr, block_addr);

	/* Is the request beyond the last block in the file? */
	if( block_addr > ((bfh->add_block_addr - bfh->block_size) + 1)){
		Debug( "Cant read beyond end of file\n");
		return FAILED;
	}
	/* Is the request below the first block in the file? */
	if(block_addr < ((2*BFHBLOCK) + 1) ){
		Debug( "Invalid block address\n");
		return FAILED;
	}
	/* Is the request on a user block boundry ? */
	if( ( (block_addr - (2*BFHBLOCK) -1) % bfh->block_size ) != 0){
		Debug( "Invalid block address\n");
		return FAILED;
	}
	/* Go to the switch byte for the block */
	if(lseek(bfh->file_fd, block_addr - 1L,0) == -1L){
		Debug( "Cant seek\n");
		return FAILED;
	}
	if(read(bfh->file_fd,&cswitch,1) != 1) {
		Debug( "Cant read switch\n");
		return FAILED;
	}
	/* If in use, return day, else return EMPTY */
	if(cswitch & BFHBLOCKINUSE){
		if(read(bfh->file_fd,ptr,bfh->block_size-1) != (bfh->block_size-1)) {
			Debug( "Cant read bdata\n");
			return FAILED;
		}
	}else{
		return EMPTY;
	}
	return SUCCESS;
}

/*
 NAME:	NewBlock

 DESCRIPTION: 	Get the first empty block, or initialize a new block
		and return its user address

 RETURN:	The user address ofthe file of a new block, or the value
		-1L on failure
*/



long BfhNewBlock(BFH * bfh /* poiner to bfh descriptor */)
{
	struct free_block_id free_list_id;
	long blocknumber;
	char cswitch = 0;
	int status;

	Trace("BfhNewBlock(%x)\n", (unsigned)bfh);
	if(bfh==NULL){
		Debug("NULL bfh\n");
		return -1L;
	}
	/* This Case:  No free block in list */
	if(bfh->first_free_block_addr == -1L){
		if(lseek(bfh->file_fd,bfh->add_block_addr,SEEK_SET) == -1L){
			Debug("Cant lseek\n");
			return -1L;
		}
		/* put the switch into place */
		cswitch = bfh->mask | BFHBLOCKINUSE;
		if(write(bfh->file_fd,&cswitch,1) != 1){
 			Debug( "Cant write\n");
			return -1L;
		}
		if((status=write(bfh->file_fd,bfh->empty_rec,bfh->block_size)) != bfh->block_size){
 			Debug( "wrote %d bytes from %d blank bytes\n", status,bfh->block_size);
			return -1L;
		}
		blocknumber = bfh->add_block_addr;
		bfh->add_block_addr += bfh->block_size;
		return ( blocknumber + 1L );
	}
	/* where is the next one?, save it */
	blocknumber = bfh->first_free_block_addr;

	/* This Case: Only one free block*/
	if(bfh->first_free_block_addr == bfh->last_free_block_addr){
		bfh->first_free_block_addr = -1L;
		bfh->last_free_block_addr = -1L;
		if(lseek(bfh->file_fd,blocknumber,0) == -1L){
			Debug("Cant lseek\n");
			return -1L;
		}
		/* put the switch into place */
		cswitch = bfh->mask | BFHBLOCKINUSE;
		if(write(bfh->file_fd,&cswitch,1) != 1){
 			Debug( "Cant write\n");
			return -1L;
		}
		return (blocknumber + 1L) ;
	}
        /* Otherwise there must be more than one*/

        /* This Case: Multiple free blocks*/
	/* Get the free list info */
	if(lseek(bfh->file_fd,bfh->first_free_block_addr + 1,0) == -1L) {
 		Debug( "Cant seek\n");
		return -1L;
	}
	if(read(bfh->file_fd,&free_list_id,sizeof(struct free_block_id)) 
		!= sizeof(struct free_block_id) ){
		Debug( "Cant read\n");
		return -1L;
	}
	/* We'll give the user the first free block on list */
	bfh->first_free_block_addr = free_list_id.next_block;
        /* Go to the next block and mark it as the first*/
	if(lseek(bfh->file_fd,bfh->first_free_block_addr+1,0) == -1L){
 		Debug( "Cant seek\n");
		return -1L;
        }
	if( read(bfh->file_fd,&free_list_id,sizeof(struct free_block_id)) 
		!= sizeof(struct free_block_id) ){
		Debug( "Cant read\n");
		return -1L;
	}
	/* Change it */
       	free_list_id.previous_block = -1L;
	/* Reposition */
	if(lseek(bfh->file_fd,bfh->first_free_block_addr+1,0) == -1L){
 		Debug( "Cant seek\n");
		return -1L;
        }
	/* write it back */
	if( write(bfh->file_fd,&free_list_id,sizeof(struct free_block_id)) 
		!= sizeof(struct free_block_id) ){
		Debug( "Cant write\n");
		return -1L;
	}
	/* set the switch */
	if(lseek(bfh->file_fd,blocknumber,0) == -1L){
		Debug("Cant lseek\n");
		return -1L;
	}
	/* put the switch into place */
	cswitch = bfh->mask | BFHBLOCKINUSE;
	if(write(bfh->file_fd,&cswitch,1) != 1){
 		Debug( "Cant write\n");
		return -1L;
	}
	return (blocknumber + 1L);
}/* end BfhNewBlock(BFH * bfh) */

/*
 NAME:	FreeBlock

 DESCRIPTION:	Add the block at the designated address to the free list

 RETURN:	SUCCESS or FAIL
*/

int BfhFreeBlock(BFH * bfh /*poiner to bfh descriptor */, 
		long user_address /* block ID to free */)
{
	struct free_block_id free_list_id;
	long old_last_block, old_first_block;
	char cswitch;
	long address;

	Trace("BfhFreeBlock(%x, %ld)\n", (unsigned)bfh, user_address);
	address = --user_address;

	/* Is the request beyond the last block in the file? */
	if( address > ((bfh->add_block_addr - bfh->block_size) + 1)){
		Debug( "Request beyond end of file\n");
		return FAILED;
	}
	/* Is the request below the first block in the file? */
	if(address < (2*BFHBLOCK) ){
		Debug( "Invalid block address\n");
		return FAILED;
	}
	/* Is the request on a user block boundry ? */
	if(
	    (((address - (2*BFHBLOCK)) + bfh->block_size)  % bfh->block_size ) 
			!= 0){
		Debug( "Invalid block address\n");
		return FAILED;
	}
	old_last_block = bfh->last_free_block_addr;
	/* if there is already a free block mark the old one*/
	/* go to the last free block*/
	cswitch = 0;
	if(bfh->last_free_block_addr != -1L) {
		/* if it is a high block, put it on the end of */
		/* the list*/
		if(address > bfh->first_free_block_addr){
			if(lseek(bfh->file_fd,bfh->last_free_block_addr+1,0) == -1L){
 				Debug("Couldnt seek\n");
				return FAILED;
			}
			if(read(bfh->file_fd,&free_list_id,sizeof(struct free_block_id)) != sizeof(struct free_block_id)) {
 				Debug("Read failure\n");
				return FAILED;
			}
			/* mark it with the next block id*/
			free_list_id.next_block = address ;
			/* write it back*/
			if(lseek(bfh->file_fd,bfh->last_free_block_addr+1,0) == -1L) {
				Debug("Couldnt seek\n");
				return FAILED;
			}
			if(write(bfh->file_fd,&free_list_id,sizeof(struct free_block_id)) != sizeof(struct free_block_id)) {
 				Debug( "Couldnt write\n");
				return FAILED;
			}
			/* mark the new last block*/
			free_list_id.previous_block = old_last_block;
			free_list_id.next_block = -1L;
			bfh->last_free_block_addr = address;
		}else{
			/* if it is a low block, put it on the front of */
			/* the list*/
			old_first_block = bfh->first_free_block_addr;
			if(lseek(bfh->file_fd,bfh->first_free_block_addr+1,0) == -1L){
       				Debug("Couldnt seek\n");
       				return FAILED;
			}
			if(read(bfh->file_fd,&free_list_id,
				sizeof(struct free_block_id)) != 
				sizeof(struct free_block_id)) 
			{
				Debug("Read failure\n");
				return FAILED;
			}
			/* mark it with the next block id*/
			free_list_id.previous_block = address ;
			/* write it back*/
			if(lseek(bfh->file_fd,bfh->first_free_block_addr+1,0) == -1L) {
				Debug("Couldnt seek\n");
				return FAILED;
			}
			if(write(bfh->file_fd,&free_list_id,
				sizeof(struct free_block_id)) != 
				sizeof(struct free_block_id)) 
			{
				Debug( "Couldnt write\n");
				return FAILED;
			}
			/* mark the new last block*/
			free_list_id.previous_block = -1;
			free_list_id.next_block = old_first_block;
			bfh->first_free_block_addr = address;
		}
	}else{	
		/*bfh->last_free_block_addr == -1L */
		/* the new one will be the only one*/
		if( bfh->last_free_block_addr == bfh->first_free_block_addr ){
			bfh->first_free_block_addr = address;
			bfh->last_free_block_addr = address;
			free_list_id.previous_block = -1L;
			free_list_id.next_block = -1L;
		}else{
			Debug("Cant be a first free block without a last free block\n");
			return FAILED;
		}
	} 
	/* mark the last block*/
	/* set up the free list structure*/

	/* mark the new last block*/
	if(lseek(bfh->file_fd,address,0) == -1L) {
		Debug("Couldnt seek\n");
		return FAILED;
	}
	if(write(bfh->file_fd,&cswitch,1) != 1) {
 		Debug( "Couldnt write\n");
		return FAILED;
	}
	if(write(bfh->file_fd,&free_list_id,sizeof(struct free_block_id)) != sizeof(struct free_block_id)) {
 		Debug( "Couldnt write\n");
		return FAILED;
	}
	return SUCCESS;
}
	
/*
 NAME:	AddrBlock

 DESCRIPTION:	Convert 0 based  block number to a user block address
		representing the data block point

 RETURN:	long address
*/

long BfhAddrBlock(BFH * bfh, /* pointer to bfh descriptor */ 
		  int i /* block sequential number */)
{ /* First file block is 0*/
	long l;

	Trace("BfhAddrBlock(%x, %d)\n", (unsigned)bfh, i);
	l = ( (2*BFHBLOCK) + ((long)i * bfh->block_size) + 1L);
	return ( (l < bfh->add_block_addr)?l:-1L );
}

/*
 NAME:	BfhFullBlock

 DESCRIPTION:	provided a block number, determine if the block is free

 RETURN:	1 for a used block, 0 for a free block, -1 for an error
*/

int BfhFullBlock(BFH * bfh, /* pointer to block file descriptor */
		 int blocknum /* block sequential number */) 
{ 
	long posn;
	char cswitch;

	Trace("BfhFullBlock(%x, %d)\n", (unsigned)bfh, blocknum);
	posn = BfhAddrBlock(bfh,blocknum);
	if(posn == -1L){
		Debug("Invalid position\n");
		return -1;
	}
	if(lseek(bfh->file_fd,posn-1,0) == -1L) {
		Debug( "Couldnt seek\n");
		return -1;
	}
	if(read(bfh->file_fd,&cswitch,1) != 1) {
		Debug( "Couldnt read\n");
		return -1;
	}
	return ( cswitch & BFHBLOCKINUSE);
}

/*.*****************************************************
* Function Name: 	PrintBfhDescriptor
*
* Access from:
*
* Synopsis:
*
* Arguments:
*
* Description:
*
* Return:
*
* History:	Created from B+Tree in C++, 1995
*
* Copr 1991,1992,1995  Tue Mar 21 15:57:56 EST 1995 Larry A. Walker
*
*  Modified:
*
******************************************************/

void PrintBfhDescriptor(BFH * bf /* pointer to block file descriptor */)
{
	if(bf == NULL){
		View("NULL Bfh\n");
		return;
	}
	View("\t\tBfh Info Bfh = %x\n", (unsigned)bf);
	View("version %s, file_fd %d, file_name %s\n", 
		(char *)(bf->version), bf->file_fd, (char *)(bf->file_name));
	View("magic %ld, block_size %d, mask %d\n", 
		bf->magic, bf->block_size, bf->mask);
	View("date_created %sdate_opened %sdate_updated %s\n", 
		ctime(&(bf->date_created)) , ctime(&(bf->date_opened)) , ctime(&(bf->date_updated)));
	View("first_free_block_addr %ld, last_free_block_addr %ld, \nadd_block_addr %ld\n", 
		bf->first_free_block_addr,bf->last_free_block_addr,bf->add_block_addr );
		
} /*end  "PrintBfhDescriptor" */