sortedblock.java

实现数据库的storage manager 功能

  /**
   * Appends a key to this block. Note that this method does not guarantee that the block
   * stays sorted.
   *
   * @param key Key to insert
   * @return true if the insert was successfull
   */
  public boolean insertKeyUnsorted(ByteStorable key){
    if(!fitsKey(key))
      return false;
    int pPos = buffer.capacity() - bytesWritten - key.byteSize();
    setPhysicalPos(high, pPos);
    high++;
    writeNumElements(high);
    bytesWritten += key.byteSize();
    writeBytesWritten(bytesWritten);
    buffer.position(pPos);
    key.toBytes(buffer);
    return true;
  }

  
  /**
   * This will update a previously stored key. Use with caution since
   * it will just overwrite the current data at the given index.
   * Thus, the keySize cannot have changed.
   *
   * @param key a value of type 'ByteStorable'
   * @param index a value of type 'int'
   */
  public void updateKey(ByteStorable key, int index){
    buffer.position(getPhysicalPos(index));
    key.toBytes(buffer);
  }

  /**
   * Inserts a key in this block. Perfoms a binary search to find the
   * correct position.
   *
   * @param key The key to insert.
   * @return the index if successfull or < 0 otherwise.
   * @see SortedBlock#insertKeyUnsorted
   */
  public int insertKey(ByteStorable key){
    //check if it can be inserted here:
    if(!fitsKey(key))
      return -1;
    int pos = binarySearch(key);
    if(pos >= 0)
      return -1;
    pos++;
    pos = Math.abs(pos);

    //calculate physical position:
    int pPos = buffer.capacity() - bytesWritten - key.byteSize();
    
    //shift all the elments to the right of pos to fit the pPos (i.e. a short)
    if(pos < high)
      byteBufferCopy(getIndexPos(pos),
		     getIndexPos(pos+1),
		     (high - pos) * ptrSize);
    

    setPhysicalPos(pos, pPos);
    high++;
    writeNumElements(high);
    bytesWritten += key.byteSize();
    writeBytesWritten(bytesWritten);
    buffer.position(pPos);
    key.toBytes(buffer);
    return pos;
  }
  
  
  /**
   * Splits a block in two. The new block will contain the upper half of this block's keys.
   * The resved space is also copied
   *
   * @return A SortedBlock with keys greater than this block's keys
   */
  public SortedBlock splitBlock(){
    SortedBlock sb = new SortedBlock();
    byte[] newBlock = new byte[block.length];
    sb.setBlock(newBlock, keyType, true, ptrSize, (short) (reservedSpace - 2));
    int half = bytesWritten / 2;
    ByteStorable lastKey;
    int numWritten = 0;
 
    //snacka med Rickard om den h鋜 l鰏ningen:
    while(numWritten < half){
      lastKey = getLastKey();
      sb.insertKey(lastKey);
      deleteKey(lastKey);
      numWritten += lastKey.byteSize();
    }
    //finally copy the reserved space:
    System.arraycopy(block, getReservedSpaceStart(), 
		     sb.getBlock(), getReservedSpaceStart(),
		     reservedSpace - 2);
		     
    return sb;
  }

  /**
   * Merge this block with another block. The merge will override any
   * reservedspace in the other block. So if you want to save that do that
   * prior to calling this method.
   *
   * @param sortedBlock The block to merge with this block.
   */
  public void mergeBlock(SortedBlock sortedBlock){
    //save the reserved space into sortedBlock:
    System.arraycopy(block, getReservedSpaceStart(), 
		     sortedBlock.getBlock(), getReservedSpaceStart(),
		     reservedSpace - 2);

    ByteStorable thisFirst = getFirstKey();
    ByteStorable otherFirst = sortedBlock.getFirstKey();
    if(thisFirst.compareTo(otherFirst) < 0){ //this is less
      mergeBlock(this, sortedBlock);
      this.setBlock(block, keyType, false, ptrSize);
    }
    else{
      mergeBlock(sortedBlock, this);
      this.setBlock(sortedBlock.getBlock(), keyType, false, ptrSize);
    }
  }

  
  /**
   * If the keys in this block has been inserted unsorted use sort to
   * sort the contents. This method works as follows:<br>
   * it reads in every key into an CBytalbe[], and then either calls
   * Arrays.sort or sort.<br>
   * If you are reading in many keys at once it is a good idea to first store
   * them in an array than call sort, and then insert them using insertUnsorted
   * into this block.
   *
   * @param mergeSort If true use the mergeSort in Arrays.sort, otherwise
   * use quicksort
   * @see SortedBlock#sort
   * @see SortedBlock#insertKeyUnsorted
   */
  public void sort(boolean mergeSort){
    ByteStorable toSort[] = new ByteStorable[high];
    for(int i = 0; i < high; i++){
      toSort[i] = getKey(i);
    }
    if(mergeSort)
      java.util.Arrays.sort(toSort);
    else
      com.mellowtech.disc.sort.Sorters.quickSort(toSort);
    this.setBlock(block, keyType, true, ptrSize);
    for(int i = 0; i < high; i++){
      insertKeyUnsorted(toSort[i]);
    }
  }
  
  
  /**
   * Redistribute the keys in a number of blocks as evenly as possible.
   * @param blocks An array of sorted blocks that should be redistributed.
   */
  public static void redistribute(SortedBlock[] blocks){
    //first the total num bytes written and calculate the
    //optimal bytes in each block:
    int totalBytes = 0;
    int optimalBytes = 0;
    for(int i = 0; i < blocks.length; i++)
      totalBytes += blocks[i].getDataBytes();
    optimalBytes = calculateOptimum(totalBytes, blocks.length);
    
    //now loop from the end:
    int blockBytes;
    for(int i = blocks.length - 1; i > 0; i--){
      blockBytes = blocks[i].getDataBytes();
      if(blockBytes > optimalBytes)
	putKeysPrevious(blocks, i, optimalBytes);
      else if(blockBytes < optimalBytes)
	getKeysPrevious(blocks, i, optimalBytes);
    }
  }
  
  /**
   * Remove a key at a given position
   *
   * @param pos position
   * @return the deleted key
   */
  public ByteStorable deleteKey(int pos){
    if(pos < 0)
      return null;

    //read the physical position:
    int pPos = getPhysicalPos(pos);
    buffer.position(pPos);
    ByteStorable toDelete = (ByteStorable) keyType.fromBytes(buffer);
    int firstPos = buffer.capacity() - bytesWritten;
    int byteSize = toDelete.byteSize();
    if(pos < high - 1){ //we have to compact the array:
      byteBufferCopy(getIndexPos(pos+1),
		     getIndexPos(pos),
		     (high - 1 - pos) * ptrSize);
      
    
    }
    //now compact the data:
    byteBufferCopy(firstPos, firstPos+byteSize, pPos - firstPos);
    

    //finally update all positions less than pos by adding toDelete.byteSize() to
    //their byte positions (we have to loop through the entire array):
    high--;
    for(int i = 0; i < high; i++){
      int oPos = getPhysicalPos(i);
      if(oPos < pPos)
	setPhysicalPos(i, oPos + byteSize);
    }
    writeNumElements(high);
    bytesWritten -= byteSize;
    writeBytesWritten(bytesWritten);
    return toDelete;
  }
  /**
   * Deletes a key from this block.
   * @param key The key to delete
   * @return The deleted key read from this block.
   */
  public ByteStorable deleteKey(ByteStorable key){
    return deleteKey(binarySearch(key));
  }

  /**
   * Returns true if this block cotains the given key.
   * @param key the key to search for.
   * @return true if the key was found
   */
  public boolean containsKey(ByteStorable key){
    return (binarySearch(key)>=0)?true:false;
  }
  
  /**
   * Binary search. Works in the same fashion as Arrays.binarySearch.
   * @param key The key to search for
   * @return position
   * @see java.util.Arrays
   */
  public int binarySearch(ByteStorable key){
    int highSearch = high - 1;
    int low = 0, mid, pos;
    ByteStorable current;

    while (low <= highSearch) {
      mid =(low + highSearch)/2;
      buffer.position(getPhysicalPos(mid));
      current = (ByteStorable) keyType.fromBytes(buffer);
      int cmp = current.compareTo(key);
      if (cmp < 0)
	low = mid + 1;
      else if (cmp > 0)
	highSearch = mid - 1;
      else
	return mid; // key found
    }
    return -(low + 1);
  }

  public String toString(){
    StringBuffer sbuff = new StringBuffer();
    int high = readNumberOfElements();
    sbuff.append("number of items: "+high+"\n");
    sbuff.append("number of bytes written: "+readBytesWritten()+"\n");
    sbuff.append("load factor: "+ (double)((double)getBytesWritten()/(double)buffer.capacity()));
    sbuff.append("\nsort order:\n");
    
    for(int i = 0; i < high; i++){
      int offset = getPhysicalPos(i);
      //System.out.println(offset);
      sbuff.append("offset: "+offset);
      buffer.position(offset);
      sbuff.append(" item: "+keyType.fromBytes(buffer)+"\n");
    }
    return sbuff.toString();
  }

  private static int calculateOptimum(int total, int divider){
    int optimal = total/divider;
    int remainder = total % divider;
    optimal = (remainder > divider / 2)?optimal+1:
      optimal;
    return optimal;
  }
  
  private static void putKeysPrevious(SortedBlock[]  blocks, int index, int optimal){
    int blockBytes;
    ByteStorable current;
    int diff;
    int diffPut;
    while(true){
      blockBytes = blocks[index].getDataBytes();
      diff = Math.abs(blockBytes - optimal);
      current = blocks[index].getFirstKey();
      diffPut = Math.abs(blockBytes - current.byteSize() - optimal);
      //the action of removing the current key will get this block
      //closer to the optimal
      if(diffPut < diff && blocks[index-1].fitsKey(current)){
	blocks[index].deleteKey(current);
	blocks[index-1].insertKey(current);
      }
      else
	return;
    }
  }

  private static void getKeysPrevious(SortedBlock[]  blocks, int index, int optimal){
    int blockBytes;
    ByteStorable current;
    int diff;
    int diffPut;
    while(true){
      blockBytes = blocks[index].getDataBytes();
      diff = Math.abs(blockBytes - optimal);
      current = blocks[index-1].getLastKey();
      diffPut = Math.abs(blockBytes + current.byteSize() - optimal);
      //the action of removing the current key will get this block
      //closer to the optimal
      if(diffPut < diff && blocks[index].fitsKey(current)){
	blocks[index].insertKey(current);
	blocks[index-1].deleteKey(current);
      }
      else
	return;
    }
  }

  private void mergeBlock(SortedBlock smaller, SortedBlock larger){
    int highSmall = smaller.getNumberOfElements();
    int highLarge = larger.getNumberOfElements();
    //int sLastPtrPos = headerSize + (highSmall * ptrSize);
    int sBytesWritten = smaller.getDataBytes();
    int lBytesWritten = larger.getDataBytes();
    int physicalPos;

    //now insert the larger pointers into the smaller block and
    //update their physical pointer position for the bytes alread written, i.e
    //the positon will be position - sBytesWritten
    for(int i = 0; i < highLarge; i++){
      physicalPos = larger.getPhysicalPos(i);
      smaller.setPhysicalPos(highSmall + i, physicalPos - sBytesWritten);
    }
    
    //copy the data from larger starting at positon larger.length - sBytesWritten):
    System.arraycopy(larger.getBlock(), larger.getBlock().length - lBytesWritten,
		     smaller.getBlock(), smaller.getBlock().length - lBytesWritten - sBytesWritten,
		     lBytesWritten);
    //finally update the bytesWritten and number of pointers:
    smaller.writeNumElements(highSmall + highLarge);
    smaller.writeBytesWritten(sBytesWritten + lBytesWritten);
  }

  private void byteBufferCopy(int srcPos, int destPos, int length){
    if(tmpArr.length < length)
      tmpArr = new byte[length];
    buffer.position(srcPos);
    buffer.get(tmpArr, 0, length);
    buffer.position(destPos);
    buffer.put(tmpArr, 0, length);
  }
  

  /*********************************INNER CLASSES**************************/
  class SBIterator implements Iterator{
    int count = high;
    int cursor = 0;
    int lastRet = -1;

    public SBIterator(ByteStorable start){
      cursor = binarySearch(start);
      if(cursor >= 0)
	return;
      cursor++;
      cursor = Math.abs(cursor);
    }

    public SBIterator(){
    }

    public boolean hasNext(){
      return (cursor < count);
    }
    
    public Object next(){
      check();
      if(cursor > count)
	throw new NoSuchElementException();
      Object key = getKey(cursor);
      lastRet = cursor++;
      return key;
    }

    public void remove(){
      if(lastRet == -1)
	throw new IllegalStateException();
      check();
      deleteKey(lastRet);
      if(lastRet < cursor)
	cursor--;
      lastRet = -1;
      count = high;
    }

    private void check(){
      if(count != high)
	throw new ConcurrentModificationException();
    }
  }

  
}