blockfile.java

实现数据库的storage manager 功能

/*
 * Copyright (c) 2000-2004, Rickard C鰏ter, Martin Svensson
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 * 
 * Redistributions of source code must retain the above copyright notice, 
 * this list of conditions and the following disclaimer. 
 * Redistributions in binary form must reproduce the above copyright notice, 
 * this list of conditions and the following disclaimer in the documentation 
 * and/or other materials provided with the distribution. 
 * Neither the name of SICS nor the names of its contributors 
 * may be used to endorse or promote products derived from this software 
 * without specific prior written permission. 
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 *
 *
 */

package com.mellowtech.disc;

import java.io.*;
import java.util.*;
import java.nio.*;

/**
 * The BlockFile is a simple representation of a file divided into
 * equal size blocks. The blocks in the file can be of any size. The 
 * BlockFile allows for insertion/deletion of blocks anywhere in the file,
 * without any rearrangement of the actual data. This guaratees for
 * fast inserts and deletes. However, this also means that the BlockFile
 * over time becomes defragmented. Defragementation can be taken care of
 * by calling the method defragment(). Once a BlockFile has been created
 * the size of each block can't be changed.<br><br>
 *
 * The BlockFile works by using a logical and physical mapping. The logical
 * mapping of blocks is kept in memory and it is only the logical mapping
 * that is changed when blocks are inserted and deleted. Thus, the logical
 * and physical mapping does not nessecarily have to be the same. So the first
 * logical block could be at the last physical position in the file. To
 * rearange the blocks the defragment() method should be used.<br><br>
 * 
 * The BlockFile use two physical files. One to store the data and one to
 * store the logical/physical mapping and other header information. The average
 * overhead when using the block file are 2 bytes extra for each block. The
 * BlockFile will, however, allocate room for 256 blocks to start with.
 *
 * @author Martin Svensson
 * @version 1.0
 */
public class BlockFile{
  
  /**
   * Describe constant <code>DEFAULT_BLOCK_SIZE</code> here.
   *
   */
  public static final int DEFAULT_BLOCK_SIZE = 1024;
  /**
   * Describe constant <code>BLOCK_FILE_EXTENSION</code> here.
   *
   */
  public static final String BLOCK_FILE_EXTENSION = ".blf";
  /**
   * Describe constant <code>POINTER_FILE_EXTENSION</code> here.
   *
   */
  public static final String POINTER_FILE_EXTENSION = ".ptr";
  
  private short[] pointers;
  

  private int blockSize, currentBlock, numBlocks, maxBlocs;
  private short highBlock;
  private String fileName;
  private RandomAccessFile file;
  //private AbstractCache fileCache;
  private int writeOps = 0, readOps = 0;
  
  
  /**
   * Opens an already existing blockfile.
   *
   * @param fileName Physical filename. Do not use file extension.
   * @exception IOException if the the blockfile could not be read from disc
   */
  public BlockFile(String fileName) throws IOException{
    this(DEFAULT_BLOCK_SIZE, fileName, false);
  }


  /**
   * Eiter opens or creates a new blockfile.
   *
   * @param fileName Physical filename. Do not use file extension.
   * @param create If true a new block file will be created.
   * @exception IOException if the the blockfile could not be read from disc
   */
  public BlockFile(String fileName, boolean create) throws IOException{
    this(DEFAULT_BLOCK_SIZE, fileName, create);
  }


  /**
   * Use this primarily for create a new blockfile.
   *
   * @param blockSize the size of each block in this file. This is ignored when 
   * opening an existing file. The size is in bytes.
   * @param fileName pysical filename. Do not use extension.
   * @param create if true create a new file.
   * @exception IOException if the the blockfile could not be read from disc
   */
  public BlockFile(int blockSize, String fileName, boolean create) throws IOException{
    this.blockSize = blockSize;
    this.fileName = fileName;
    
    if(create){
      this.pointers = new short[256];
      blockSize = blockSize;
      createFile();
    }
    else{
      openFile();
    }
  }
  
  /**
   * Closes the blockfile. This method has to be called in order to guarantee that 
   * the block file stays intact. Specifically closeFile write header information to
   * disc.
   *
   * @exception IOException if read/write operations on the blockfile fails.
   */
  public void closeFile() throws IOException{
    //flush possible cache:
    /*if(fileCache != null)
      fileCache.emptyCache();*/
    writeHeader();
    file.close();
  }

  
  /**
   * Returns the block size.
   *
   * @return block size.
   */
  public int getBlockSize(){
    return blockSize;
  }

  /**
   * Return current logical block index
   *
   * @return logical block index.
   */
  public int getCurrentBlockNo(){
    return currentBlock;
  }
  
  /**
   * The logical index to the first block is always 0. However, due to 
   * fragmentation the physical index of the first block can be something 
   * else than 0.
   *
   * @return the index to the first block in this file. 
   */
  public int getFirstBlockNo(){
    return 0;
  }


  /**
   * The number of blocks currently in the block (not counting deleted blocks).
   *
   * @return number of blocks.
   */
  public int getNumberOfBlocks(){
    return numBlocks;
  }
  
  /**
   * The last logical index to the last block in this file.
   *
   * @return the index of the last block in this file.
   */
  public int getLastBlockNo(){
    return numBlocks - 1;
  }

  
  /**
   * Retrieves the logical index that corresponds to a 
   * physical postion. O(n) performance. It scans
   * throuch the logcial mapping array until it finds
   * the physical mapping.
   *
   * @param physicalPos a physical block postion.
   * @return -1 if the physicalPosition does not have a logical mapping in this file
   */
  public int getLogicalBlockNo(int physicalPos){
    if(physicalPos < 0 || physicalPos > highBlock){
      return -1;
    }
    for(int i = 0; i < numBlocks; i++){
      if(pointers[i] == physicalPos)
	return i;
    }
    return -1;
  }

  /**
   * Retrieves the physical index that corresponds to a 
   * logical position. O(1) performance
   *
   * @param logicalPos an <code>int</code> value
   * @return -1 if the logicalPosition is out of range
   */
  public int getPhysicalBlockNo(int logicalPos){
    if(logicalPos < 0 || logicalPos >= numBlocks)
      return -1;
    return pointers[logicalPos];
  }

  /**
   * Iterator over the logical blocks in this file
   * @return an <code>Iterator</code> value
   */
  public Iterator iterator(){
    return new BFIterator();
  }

  /**
   * Iterator over the logical blocks in this file starting
   * from the given block.
   * @param blockNo starting block
   * @param logical true if block index is logical, false if it is physical
   * @return an <code>Iterator</code> value
   */
  public Iterator iterator(int blockNo, boolean logical){
    return new BFIterator(blockNo, logical);
  }

  
  /**
   * Reads the current block from file.
   *
   * @return an array of bytes
   * @exception IOException if physical reading fails.
   * @see BlockFile#getCurrentBlockNo()
   */
  public byte[] readCurrentBlock() throws IOException{
    return readBlock(currentBlock);
  }

  /**
   * Reads the physical block at the specified logical position in the file.
   *
   * @param blockNo the logcial index.
   * @return an array of bytes.
   * @exception IOException if physical reading fails.
   */
  public byte[] readBlock(int blockNo) throws IOException{
    byte[] b = readPhysicalBlock(pointers[blockNo]);
    currentBlock = blockNo;
    return b;
  }

  /**
   * Reads the block at the specified physical position. Note that the
   * block read can be a deleted block since the BlockFile does no such
   * checking. The operation will not change the current block position.
   *
   * @param blockNo the logcial index.
   * @return an array of bytes.
   * @exception IOException if physical reading fails.
   */
  public byte[] readPhysicalBlock(int blockNo) throws IOException{
    
    if(blockNo < 0 || blockNo > highBlock)
      return null;

    byte[] b;

    /*if(fileCache != null){
      b = (byte[]) fileCache.get(new Integer(blockNo));
      if(b != null)
	return b;
	}*/
    b = new byte[blockSize];
    file.seek(blockNo * blockSize);
    file.readFully(b);
    readOps++;

    /*if(fileCache != null){
      fileCache.put(new Integer(blockNo), b);
      }*/
    return b;
  }

  /*
  public void setCache(AbstractCache cache){
    if(this.fileCache != null){ //flush old cache
      fileCache.emptyCache();
    }
    this.fileCache = cache;
    if(this.fileCache != null)
      fileCache.setCallback(new BlockFile.Callback());
  }
  */

  /**
   * Write to the current logical index.
   *
   * @param b the bytes to be written.
   * @exception IOException if physical writing fails.
   */
  public void writeCurrentBlock(byte[] b) throws IOException{