bytebufferheap.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.sort;

import com.mellowtech.disc.ByteComparable;
import java.nio.ByteBuffer;


/**
 * A Heap that is backed up by a java.nio.ByteBuffer.
 *
 * @author Martin Svensson
 * @version 1.0
 */
public class ByteBufferHeap implements BufferHeap{
  
  private int heap[];
  private float inc;
  private int size;
  private ByteBuffer bb;
  private ByteComparable bc;

  /**
   * Create a new heap that uses a specified ByteBuffer for
   * comparing objects and a specific comparator for the
   * actal byte comparison
   * @param bb buffer of bytes
   * @param bc byte comparator
   * @exception Exception if an error occurs
   */
  public ByteBufferHeap(ByteBuffer bb, ByteComparable bc) throws Exception{
    this(100, 2.0f, bb, bc);
  }

  /**
   * Create a new heap that uses a specified ByteBuffer for
   * comparing objects and a specific comparator for the
   * actal byte comparison
   * @param initSize preallocate X number of offsets
   * @param bb buffer of bytes
   * @param bc byte comparator
   * @exception Exception if an error occurs
   */
  public ByteBufferHeap(int initSize, ByteBuffer bb, ByteComparable bc) throws Exception{
    this(initSize, 2.0f, bb, bc);
  }

  /**
   * Create a new heap that uses a specified ByteBuffer for
   * comparing objects and a specific comparator for the
   * actal byte comparison
   * @param initSize preallocate X number of offsets
   * @param incrementFactor how much the array of offsets should grow when it is full, defaults to 200 %
   * @param bb buffer of bytes
   * @param bc byte comparator
   * @exception Exception if an error occurs
   */
  public ByteBufferHeap(int initSize, float incrementFactor, ByteBuffer bb, ByteComparable bc)
    throws Exception{
    
    if(bb == null || bc == null)
      throw new Exception("The ByteBuffer and ByteComparable can not be null");
    this.bb = bb;
    this.bc = bc;
    heap = new int[initSize];
    inc = incrementFactor;
    size = 0;
  }

  /**
   * Clears this heap by setting the size to 0
   *
   */
  public void clear(){
    size = 0;
  }
  
  /************IMPLEMENTED BUFFERHEAP METHODS*****************************/
  public void insert(int c) throws Exception{
    if(c < 0)
      throw new Exception("Only positive pointers allowed");
	
    if(size == heap.length) resize();
    
    //bubble up:
    int child = ++size;
    
    while((child > 1) && bc.byteCompare(c, heap[(child / 2)-1], bb) < 0){
      heap[child - 1] = heap[(child / 2) - 1];
      child /= 2;
    }
    heap[child-1] = c;
    
  }

  public int get(){
    return heap[0];
  }

  public int delete(){
    if(size == 0)
      return -1;

    int T = heap[0];
    size--;
    heap[0] = heap[size];
    bubbleDown(heap, 1, size, bb, bc);
    return T;
  }

  /************************END IMPLEMENTED BUFFERHEAP METHODS****************/

  /**
   * Turn an array of offsets into a heap of offsets.
   *
   * @param objs array of offsets
   * @param bb a buffer that stores the objects
   * @param bc a byte comparator
   * @return a new ByteBufferHeap
   * @exception Exception if an error occurs
   */
  public static final ByteBufferHeap heapify(int[] objs, ByteBuffer bb, ByteComparable bc)
    throws Exception{

    ByteBufferHeap h = new ByteBufferHeap(bb, bc);
    int N = objs.length;
    for(int k = N/2; k > 0; k--){
      bubbleDown(objs, k, N, bb, bc);
    }
    h.size = objs.length;
    h.heap = objs;
    return h;
  }

  /**
   * Sort an array of offsets
   * @param objs an array of offsets to be sorted
   * @param bb the buffer that stores the objects
   * @param bc a byte comparator
   */
  public static final void heapSort(int[] objs, ByteBuffer bb, ByteComparable bc){
    int N = objs.length;
    for(int k = N/2; k > 0; k--){
      bubbleDownReverse(objs, k, N, bb, bc);
    }
    do{
      int T = objs[0];
      objs[0] = objs[N - 1];
      objs[N - 1] = T;
      N = N - 1;
      bubbleDownReverse(objs, 1, N, bb, bc);
    } 
    while (N > 1);
  }
  
  public String toString(){
    StringBuffer sb = new StringBuffer();
    for(int i = 0; i < size; i++)
      sb.append(heap[i]+"\t");
    return sb.toString();
  }

  private void resize(){
    int o[] = new int[Math.round(heap.length * inc)];
    System.arraycopy(heap, 0, o, 0, heap.length);
    heap = o;
  }

  private static final void bubbleDown(int[] objs, int node, int max,
				       ByteBuffer bb, ByteComparable bc){
    
    int T = objs[node - 1];
    int half = max/2;
    while(node <= half){
      int j = node + node;

      if((j < max) && (bc.byteCompare(objs[j - 1], objs[j], bb) > 0)){
	j++;
      }

      if(bc.byteCompare(T, objs[j-1], bb) > 0){
	objs[node - 1] = objs[j - 1];
	node = j;
      }
      else
	break;
    }
    objs[node - 1] = T;
  }

  private static final void bubbleDownReverse(int[] objs, int k, int N,
					      ByteBuffer bb, ByteComparable bc){
    //int T = a[k - 1];
    int T = objs[k - 1];
    while(k <= N/2){
      int j = k + k;
      if((j < N) && bc.byteCompare(objs[j - 1], objs[j], bb) < 0){
	j++;
      }
      if(bc.byteCompare(T, objs[j-1], bb) >= 0){
	break;
      }
      else{
	objs[k - 1] = objs[j - 1];
	k = j;
      }
    }
    objs[k - 1] = T;
  }
}