btreeblockfileuos.java

国外的数据结构与算法分析用书

/* BtreeBlockUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */

package dslib.file;

import java.io.*;
import dslib.exception.*;

/**	This class defines a file that stores objects of type BtreeBlockUos.  
	It stores the header for a Btree file, and the records of the file. */
public class BtreeBlockFileUos extends ObjectFileUos
{
	/**	The maximum number of bytes that a header can take up
		when it is written to disk */
	protected static int headerOffset = 400;
 
	/**	The name of the file associated with this object */
	public String name;

	/**	The last address that was returned for reuse */
	public long lastReturnedAddress;
  
	/**	The next address that will be given out if there are no	
		recovered addresses left to be given out */
	public long nextAddress;

	/**	The maximum number of bytes that a block can take up
		when it is written to disk */
	protected int blockSize;
	  
	/**	The header for the file */
	protected BtreeFileHeaderUos header;

	/**	The byte offset within the file where the header is written */
	private long headerWritePosition;

	/**	Create a new BtreeBlockFileUos with the name newName and 
		set blockSize to be bs. <br>
		Analysis : Time = O(1) + 1 file read
		@param newName The name of the file where the blocks will be written
		@param bs The maximum size (in bytes) that a block will take up on disk */
	public BtreeBlockFileUos (String newName, int bs)
	{
		super(newName, "rw");
		/* The call to super will move the file pointer ahead by the number of
		   bytes that a java.io.ObjectOutputStream file header requires. */
		headerWritePosition = position();
		nextAddress = headerWritePosition + headerOffset;
		name = newName;
		blockSize = bs;
		lastReturnedAddress = -1;
	}

	/**	Open a file from an existing file with the name newName. <br>
		Analysis : Time = O(1) + 1 file read
		@param newName The name of file where a BtreeFileHeaderUos is stored */
	public BtreeBlockFileUos (String newName)
	{
		super(newName, "rw");
		/* The call to super will move the file pointer ahead by the amount of
		   bytes that a java.io.ObjectOutputStream file header takes up */
		headerWritePosition = position();
		header = (BtreeFileHeaderUos) readObject();
		name = newName;
		blockSize = header.blockSize;
		lastReturnedAddress = header.firstFreeDataAddress;
		nextAddress = header.nextAddress;
	}

	/**	Set the file header to be newHeader. <br>
		Analysis: Time = O(1) 
		@param newHeader The new header for this file */
	public void setHeader(BtreeFileHeaderUos newHeader)
	{
		header = newHeader;
	}

	/**	Produce a listing of the records in serial order. <br> 
		Analysis: Time = O(size of the file) file reads. */
	public String serialToString()
	{
		String result = new String();
		long nextObjectPosition = headerWritePosition + headerOffset;
		while (nextObjectPosition < nextAddress)
		{
			/* read an object from the next position that may contain a block */
			Object currentObject = readObjectFrom(nextObjectPosition);
			if (currentObject instanceof BtreeBlockUos)
			{
				result += currentObject.toString();
			}
			nextObjectPosition += blockSize;
		}
		return result;
	}

	/**	Write the header to disk. <br> 
		Analysis: Time = O(1) + 1 file write */
	public void writeHeader()
	{
		writeObjectAt(header, headerWritePosition);
	}

	/**	Place newBlock at a specific address within the file. <br>
		Analysis : Time = O(1) + 1 file write <br>
		PRECONDITION: <br>
		<ul>
			address >= headerOffset 
		</ul> 
		@param newBlock The block to write to disk
		@param address The address where the block will be written */
	public void writeBlock(BtreeBlockUos newBlock, long address) 
	{
		if (!(address >= headerOffset))
			throw new InvalidArgumentUosException("Cannot write a block over the file header");

		writeObjectAt(newBlock, address);
	}

	/**	Read a block from the file at address address. <br>
		Analysis: Time = O(1) file read 
		@param address The address on disk where the block will be read from */
	public BtreeBlockUos readBlock(long address)
	{
		return (BtreeBlockUos) readObjectFrom(address);
	}

	/**	Make an address available for reuse by another node. <br> 
		Analysis : Time = O(1) + 1 file write 
		@param returnedAddress The address that is to be recovered */
	public void returnAddress(long returnedAddress)
	{
		writeObjectAt(new Long(lastReturnedAddress), returnedAddress);
		lastReturnedAddress = returnedAddress;
	}

	/**	Return the next available file address. <br>
		Analysis : Time = O(1) + 1 file read. */
	public long getNextAddress()
	{
		long result;
		if (lastReturnedAddress == -1) /* There are no recovered addresses left to be reused */
		{
			result = nextAddress;
			nextAddress += blockSize;
		}
		else
		{
			result = lastReturnedAddress;
			Long longFromFile = (Long) readObjectFrom(lastReturnedAddress);
			lastReturnedAddress = longFromFile.longValue();
		} 
		return result;
	}
}