sortedblock.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.util.*;
import java.nio.ByteBuffer;

/**
 * The SortedBlock keeps a sorted byte array of ByteStorables. The SortedBlock
 * divides the byte array into two sections, the first section is the
 * pointers to the actual keys stored in the array. All sorting, searching,
 * rearaing is done in the pointers section. Thus, keys does not have
 * to be physically sorted in the block, it is only the pointers that are
 * sorted. The SortedBlock do not have to be defragmented. Whenever keys are
 * deleted the SortedBlock automatially move that space to the unused space
 * section. So using very long keys with heavy insert/delelets can reduce
 * performance.<br><br>
 * The overhead for using the SortedBlock depends on the pointer size. It can
 * either be 4, 2, 1 byte extra for each key stored in the sorted block.
 * @author Martin Svensson
 */
public class SortedBlock{
  
  private byte[] block;
  private byte[] tmpArr = new byte[128];
  private ByteBuffer buffer;
  private ByteStorable keyType;
  private int high;
  private int bytesWritten;
  private short reservedSpace;
  //public int numComparisons;

  
  /**
   * Use for really big blocks, i.e, store up to 4000000000 keys
   */
  public static final byte PTR_BIG = 4;

  /**
   * Use for normal blocks, i.e, store up to 32000 keys
   */
  public static final byte PTR_NORMAL = 2;
  
  /**
   * Use for tiny blocks, i.e, store up to 256 keys
   */
  public static final byte PTR_TINY = 1;

  private byte ptrSize = PTR_NORMAL;
  private int headerSize = 1 + (ptrSize * 2);

  private int read(int position){
    switch(ptrSize){
    case PTR_BIG:
      return buffer.getInt(position);
    case PTR_NORMAL:
      return buffer.getShort(position);
    case PTR_TINY:
      return buffer.get(position);
    }
    return -1;
  }

  private void write(int position, int value){
    switch(ptrSize){
    case PTR_BIG:
      buffer.putInt(position, value);
      break;
    case PTR_NORMAL:
      buffer.putShort(position, (short) value);
      break;
    case PTR_TINY:
      buffer.put(position, (byte) value);
      break;
    }
  }
  
  private void setPhysicalPos(int index, int value){
    write(getIndexPos(index), value);
  }
  
  private int getIndexPos(int index){
    return reservedSpace + headerSize + (index * ptrSize);
  }

  private int getPhysicalPos(int index){
    return read(getIndexPos(index));
  }

  private void writeBytesWritten(int bytesWritten){
    write(1 + ptrSize + reservedSpace, bytesWritten);
  }

  private void writeNumElements(int numElements){
    write(1 + reservedSpace, numElements);
  }
  
  private void writeIndexPos(int index, int value){
    write(getIndexPos(index), value);
  }
  
  private int readBytesWritten(){
    return read(1 + ptrSize + reservedSpace);
  }

  private int readNumberOfElements(){
    return read(1 + reservedSpace);
  }

  private byte readPtrSize(){
    return buffer.get(reservedSpace);
  }

  private short readReservedSpace(){
    return buffer.getShort(0);
  }

  private void writeReservedSpaceLength(){
    buffer.putShort(0, (short) (reservedSpace - 2));
  }

  private void writePtrSize(){
    buffer.put(reservedSpace, ptrSize);
  }

  
  /**
   * Returns an iter.
   *
   * @return an <code>Iterator</code> value
   */
  public Iterator iterator(){
    return new SBIterator();
  }

  /**
   * Returns an iterator starting at the given key or the following one.
   *
   * @param key a given key to start from
   * @return an <code>Iterator</code> value
   */
  public Iterator iterator(ByteStorable key){
    return new SBIterator(key);
  }

  
  /**
   * The byte block has previously been initialized to be used as a sorted block.
   *
   * @param block the sortedblock bytes.
   * @param keyType the keyType always has to be provied.
   */
  public void setBlock(byte[] block, ByteStorable keyType){
    setBlock(block, keyType, false, (byte) -1, (short) -1);
  }

  /**
   * Set the block to work with.
   *
   * @param block the physical block to store keys in
   * @param keyType The type of keys that this block handles
   * @param newBlock Indicate wheter this is a new block. 
   * @param ptrSize The size of the pointers in this block. If the normal pointer size is
   * used this block can store up to 32000 keys
   * @param reservedSpace X bytes will be reserved for caller to use freely (for instance
   * for specific header information).
   */
  public void setBlock(byte[] block, ByteStorable keyType, boolean newBlock, byte ptrSize,
		       short reservedSpace){
    this.keyType = keyType;
    this.block = block;
    this.buffer = ByteBuffer.wrap(block);

    if(newBlock){
      this.reservedSpace = (short) (reservedSpace + 2); //the size has to be stored:
      high = 0; bytesWritten = 0; this.ptrSize = ptrSize;
      writeNumElements(0);
      writeBytesWritten(0);
      this.ptrSize = ptrSize;
      writeReservedSpaceLength();
      writePtrSize();
    }
    else{
      this.reservedSpace = (short) (readReservedSpace() + 2);
      this.ptrSize = readPtrSize();
      high = readNumberOfElements();
      bytesWritten = readBytesWritten();
    }
    headerSize = (this.ptrSize * 2) + 1;
  }

  /**
   * Set the block to work with. This initializer use no reserved space.
   *
   * @param block the physical block to store keys in
   * @param keyType The type of keys that this block handles
   * @param newBlock Indicate wheter this is a new block. 
   * @param ptrSize The size of the pointers in this block. If the normal pointer size is
   * used this block can store up to 32000 keys
   */
  public void setBlock(byte[] block, ByteStorable keyType, boolean newBlock, byte ptrSize){
    setBlock(block, keyType, newBlock, ptrSize, (short) 0);
  }


  /**
   * Return the current block. Be careful to manipulate a block directly 
   *(and not via SortedBlock) since the sorted block stores pointers in each block.
   *
   * @return an array of bytes containing the keys.
   */
  public byte[] getBlock(){
    return block;
  }

  /**
   * Return the current block. Be careful to manipulate a block directly 
   *(and not via SortedBlock) since the sorted block stores pointers in each block.
   *
   * @return the buffer containing the keys.
   */
  public ByteBuffer getByteBuffer(){
    return buffer;
  }

  
  /**
   * Return the type of keys this sorted block handles
   *
   * @return The type of keys this block handles
   */
  public ByteStorable getKeyType(){
    return keyType;
  }

  
  /**
   * This returs the start postion of the reserved space in this
   * sorted block. Be careful to read/write from the reserved space since the sorted block 
   * has no control over this.
   * @return an <code>int</code> value
   */
  public int getReservedSpaceStart(){
    return 2;
  }

  /**
   * Returnts the number of bytes that has been reserved in this block.
   * @return an <code>int</code> value
   */
  public int getReservedSpace(){
    return reservedSpace - 2;
  }


  /**
   * Check if this block has room for an additional key.
   *
   * @param key the key to check
   * @return True if the key can be stored in this block.
   */
  public boolean fitsKey(ByteStorable key){
    if(reservedSpace + 
       headerSize + bytesWritten + ((high+1) * ptrSize) + key.byteSize() > buffer.capacity())
      return false;
    return true;
  }
     
  /**
   * Number of keys in this block.
   * @return number of elements
   */
  public int getNumberOfElements(){
    return high;
  }


  /**
   * Number of bytes used to store the actual keys in this block (excluding pointers).
   * @return number of bytes used
   */
  public int getDataBytes(){
    return bytesWritten;
  }

  /**
   * Number of databytes and pointer bytes written in this file.
   * @return number of bytes
   */
  public int getDataAndPointersBytes(){
    return bytesWritten + (high * ptrSize);
  }

  
  /**
   * The actual storage capacity of this sortedblock. Remember that Each key stored
   * will have an additional number of bytes for its pointer.
   * @return storage in bytes
   */
  public int storageCapacity(){
    return buffer.capacity() - headerSize - reservedSpace;
  }

  /**
   * Number of bytes actually written in this block. Including the reserved space
   * @return number of bytes
   */
  public int getBytesWritten(){
    return reservedSpace + headerSize + bytesWritten + (high * ptrSize);
  }

  /**
   * The pointer size in this block, i.e 4 for integer size pointers
   *
   * @return pointer size
   */
  public byte getPointerSize(){
    return ptrSize;
  }

  
  /**
   * Checks if this block can be merged with another block.
   *
   * @param other the block to merge with.
   * @return true if the two blocks can be merged.
   */
  public boolean canMerge(SortedBlock other){
    int totDataBytes = other.getDataBytes()+getDataBytes();
    int totElements = other.getNumberOfElements() + getNumberOfElements();
    if(reservedSpace + headerSize + totDataBytes + (totElements * ptrSize) > buffer.capacity())
      return false;
    return true;
  }

  /**
   * Checks if this block can be merged with another block and an additional key.
   *
   * @param other the block to merge with.
   * @param additional a <code>ByteStorable</code> value
   * @return true if the two blocks can be merged.
   */
  public boolean canMerge(SortedBlock other, ByteStorable additional){
    int totDataBytes = other.getDataBytes()+getDataBytes()+additional.byteSize();
    int totElements = other.getNumberOfElements() + getNumberOfElements() + 1;
    if(reservedSpace + headerSize + totDataBytes + (totElements+1 * ptrSize) > buffer.capacity())
      return false;
    return true;
  }
  
  
  /**
   * Key at position index.
   * @param index positon of key
   * @return null if the block did not contain the key or the index was out of range
   */
  public ByteStorable getKey(int index){
    if(index >= high || index < 0)
      return null;
    buffer.position(getPhysicalPos(index));
    return (ByteStorable) keyType.fromBytes(buffer);
  }

  /**
   * Binary search to find a key
   *
   * @param key Key to search for
   * @return the key read from the current block
   */
  public ByteStorable getKey(ByteStorable key){
    return getKey(binarySearch(key));
  }


  /**
   * The first key in this block.
   *
   * @return null if the block is empty
   */
  public ByteStorable getFirstKey(){
    return getKey(0);
  }

  /**
   * The last key in this block.
   *
   * @return null if the block is empty
   */
  public ByteStorable getLastKey(){
    return getKey(high - 1);
  }