spanningblockfile.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.*;


/**
 * The Spanning file allows for insertion of variable length records of any size
 * tha can be grown/shrinked and deleted. Deleted space will be reused immediatley.
 */
public class SpanningBlockFile{
  public static final String SPANNING_FILE_EXTENSION = ".spf";
  public static final String SPANNING_FILE_HEADER_EXTENSION = ".sph";

  int[] dBlocks;
  TreeMap mapping; 
  int highLBlock;
  int highPBlock;
  int blockSize;
  int deletedBlocks = 0;
  String fileName;
  RandomAccessFile file;

  /**
   * Creating a new spanning file.
   *
   * @param blockSize the minimum size that will be allocated when inserting. 
   * @param fileName given file name (without extension)
   */
  public SpanningBlockFile(int blockSize, String fileName)
    throws IOException{
    this.blockSize = blockSize;
    this.fileName = fileName;
    file = new RandomAccessFile(fileName+SPANNING_FILE_EXTENSION, "rw");
    highPBlock = highLBlock = 0;
    mapping = new TreeMap();
    dBlocks = new int[256];
  }

  /**
   * Open an existing spanning file.
   *
   * @param fileName previously given file name (without extension)
   */
  public SpanningBlockFile(String fileName) throws IOException{
    this.fileName = fileName;
    file = new RandomAccessFile(fileName+SPANNING_FILE_EXTENSION, "rw");
    openFile(fileName);
  }

  /**
   * Iterator over the logical blocks in this file
   */
  public Iterator iterator(){
    return new SBFIterator();
  }

  /**
   * Iterator over the logical blocks. The iterator returns
   * objects of type Map.Entry (java.util) with keys
   * beeing recored numbers as Integers and values either
   * byte arrays or Objects converted using the provided template.
   * @param template a byte array converter
   * @return Iterator with Map.Entry objects
   */
  public Iterator entryIterator(ByteStorable template){
    return new MappingIterator(template);
  }

  /**
   * Iterator over the logical blocks starting from the given record. 
   * The iterator returns objects of type Map.Entry (java.util) with keys
   * beeing recored numbers as Integers and values either
   * byte arrays or Objects converted using the provided template.
   * @param template a byte array converter
   * @return Iterator with Map.Entry objects
   */
  public Iterator entryIterator(int start, ByteStorable template){
    return new MappingIterator(new Integer(start), template);
  }

  
  /**
   * Open an existing spanning block file.
   *
   * @param fileName the name of the file...without extension
   * @exception IOException if the an IO error occured
   */
  public void openFile(String fileName) throws IOException{
    RandomAccessFile raf = new RandomAccessFile(fileName+
						SPANNING_FILE_HEADER_EXTENSION,"rw");
    blockSize = raf.readInt(); //block size
    highLBlock = raf.readInt(); //highest logical record number
    highPBlock = raf.readInt(); //highest pysical block

    //deletedBlocks:
    deletedBlocks = raf.readInt();
    dBlocks = (deletedBlocks > 256)?new int[deletedBlocks]:
      new int[256];
    for(int i = 0; i < deletedBlocks; i++)
      dBlocks[i] = raf.readInt();

    //mapping:
    mapping = new TreeMap();
    int mSize = raf.readInt();
    Integer integer;
    Mapping m;
    for(int i = 0; i < mSize; i++){
      m = new Mapping();
      integer = new Integer(raf.readInt());
      m.size = raf.readInt();
      m.count = raf.readInt();
      m.ptrs = new int[m.count];
      for(int j = 0; j < m.count; j++){
	m.ptrs[j] = raf.readInt();
      }
      mapping.put(integer, m);
    }
  }

  /**
   * Close an open file. Header and pointer data will be saved. Always
   * call this method when closing a spanning file
   * @exception IOException if the file could not be written to disc.
   */
  public void closeFile() throws IOException{
    RandomAccessFile raf = new RandomAccessFile(fileName+
						SPANNING_FILE_HEADER_EXTENSION,"rw");
    raf.writeInt(blockSize); //block size
    raf.writeInt(highLBlock); //highest logical record number
    raf.writeInt(highPBlock); //highest pysical block

    //deleted blocks:
    raf.writeInt(deletedBlocks);
    for(int i = 0; i < deletedBlocks; i++)
      raf.writeInt(dBlocks[i]);

    //mapping:
    raf.writeInt(mapping.size());
    Mapping m;
    Integer integer;
    for(Iterator it = mapping.keySet().iterator(); it.hasNext();){
      integer = (Integer) it.next();
      m = (Mapping) mapping.get(integer);
      raf.writeInt(integer.intValue());
      raf.writeInt(m.size);
      raf.writeInt(m.count);
      for(int i = 0; i < m.count; i++)
	raf.writeInt(m.ptrs[i]);
    }
    raf.close();
    file.close();
  }

  
  /**
   * Append additional data to a relative record.
   *
   * @param rrn record number of the record to write to.
   * @param b the bytes that will be appended to the record
   * @exception IOException if the bytes could not be written to disc
   */
  public void append(int rrn, byte[] b)
    throws IOException{
    update(rrn, b, b.length);
  }

  public void append(int rrn, byte[] b, int length) throws IOException{
    update(rrn, b, getMapping(rrn).size, length);
  }

  public void update(int rrn, byte[] b, int offset) throws IOException{
    update(rrn, b, offset, b.length);
  }

  /**
   * Updateds an existing record by (over)writing bytes starting at the
   * given position and possibly expands/shrinks the record.
   *
   * @param rrn the record to update.
   * @param b the bytes to update with. If it is 0 bytes the update method
   * just returns.
   * @param offset the position in the record to start from.
   * @exception IOException if the physical writing to disc failed.
   */
  public void update(int rrn, byte[] b, int offset, int length)
    throws IOException{
    Mapping m = getMapping(rrn);
    if(m == null || offset > m.size || length == 0)
      return;
    //block to start from:
    int current = offset/blockSize;

    int fOffset = offset % blockSize;
    int bytesWritten = 0;
    while(bytesWritten < length){
      if(current == m.ptrs.length)
	growPointers(m);
      if(current >= m.count){
	m.ptrs[current] = getNextBlock();
      }
      bytesWritten += writeBytes(m.ptrs[current], b, bytesWritten, fOffset, length);
      fOffset = 0;
      current++;
    }
    m.size = offset + length;
    int i = getCount(m.size);
    if(i < m.count){ //now delete some records if possible
      for(; i < m.count; i++){
	putDeletedBlock(m.ptrs[i]);
      }
    }
    m.count = getCount(m.size);
  }

  public int insert(byte[] b) throws IOException{
    return insert(b, b.length);
  }

  /**
   * Inserts a new record into this file.
   *
   * @param b the bytes to write.
   * @return the newly created record number.
   * @exception IOException if the phsyical read/write operations failed
   */
  public int insert(byte[] b, int length)
    throws IOException{
    int rrn = highLBlock;
    int bytesWritten = 0;
    int pBlock;
    Mapping m = new Mapping();
    int i = 0;
    while(bytesWritten < length){
      pBlock = getNextBlock();
      bytesWritten += writeBytes(pBlock, b, bytesWritten, length);
      if(i == m.ptrs.length)
	growPointers(m);
      m.ptrs[i] = pBlock;
      i++;
    }
    m.count = i;
    m.size = length;
    mapping.put(new Integer(highLBlock), m);
    highLBlock++;
    return highLBlock - 1;
  }

  /**
   * Returns the bytes for the given record.
   *
   * @param rrn a record number
   * @return the bytes attatched to this record (exact)
   * @exception IOException if the data could not be read
   */