btree.java

来自「RESIN 3.2 最新源码」· Java 代码 · 共 1,613 行 · 第 1/3 页

/*
 * Copyright (c) 1998-2008 Caucho Technology -- all rights reserved
 *
 * This file is part of Resin(R) Open Source
 *
 * Each copy or derived work must preserve the copyright notice and this
 * notice unmodified.
 *
 * Resin Open Source is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Resin Open Source is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE, or any warranty
 * of NON-INFRINGEMENT.  See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Resin Open Source; if not, write to the
 *
 *   Free Software Foundation, Inc.
 *   59 Temple Place, Suite 330
 *   Boston, MA 02111-1307  USA
 *
 * @author Scott Ferguson
 */

package com.caucho.db.index;

import com.caucho.db.Database;
import com.caucho.db.store.Block;
import com.caucho.db.store.BlockManager;
import com.caucho.db.store.Lock;
import com.caucho.db.store.Store;
import com.caucho.db.store.Transaction;
import com.caucho.log.Log;
import com.caucho.sql.SQLExceptionWrapper;
import com.caucho.util.L10N;
import com.caucho.vfs.Path;

import java.io.IOException;
import java.sql.SQLException;
import java.util.ArrayList;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * Structure of the table:
 *
 * <pre>
 * b4 - flags
 * b4 - length
 * b8 - parent
 * b8 - next
 * tuples*
 * </pre>
 * 
 * Structure of a tuple:
 *
 * <pre>
 * b8  - ptr to the actual data
 * key - the tuple's key
 * </pre>
 */
public final class BTree {
  private final static L10N L = new L10N(BTree.class);
  private final static Logger log = Log.open(BTree.class);
  
  public final static long FAIL = 0;
  private final static int BLOCK_SIZE = Store.BLOCK_SIZE;
  private final static int PTR_SIZE = 8;

  private final static int FLAGS_OFFSET = 0;
  private final static int LENGTH_OFFSET = FLAGS_OFFSET + 4;
  private final static int PARENT_OFFSET = LENGTH_OFFSET + 4;
  private final static int NEXT_OFFSET = PARENT_OFFSET + PTR_SIZE;
  private final static int HEADER_SIZE = NEXT_OFFSET + PTR_SIZE;

  private final static int LEAF_FLAG = 1;

  private BlockManager _blockManager;

  private final Lock _lock;
  private Store _store;
  
  private long _rootBlockId;
  private Block _rootBlock;
  
  private int _keySize;
  private int _tupleSize;
  private int _n;
  private int _minN;
  
  private KeyCompare _keyCompare;

  private int _blockCount;

  private volatile boolean _isStarted;

  /**
   * Creates a new BTree with the given backing.
   *
   * @param store the underlying store containing the btree.
   */
  public BTree(Store store,
	       long rootBlockId,
	       int keySize,
	       KeyCompare keyCompare)
    throws IOException
  {
    if (keyCompare == null)
      throw new NullPointerException();
    
    _store = store;
    _blockManager = _store.getBlockManager();
    
    _rootBlockId = rootBlockId;
    _rootBlock = store.readBlock(rootBlockId);
      
    _lock = new Lock("index:" + store.getName());
    
    if (BLOCK_SIZE < keySize + HEADER_SIZE)
      throw new IOException(L.l("BTree key size `{0}' is too large.",
                                keySize));

    _keySize = keySize;

    _tupleSize = keySize + PTR_SIZE;

    _n = (BLOCK_SIZE - HEADER_SIZE) / _tupleSize;
    _minN = (_n + 1) / 2;
    if (_minN < 0)
      _minN = 1;

    _keyCompare = keyCompare;
  }

  /**
   * Returns the index root.
   */
  public long getIndexRoot()
  {
    return _rootBlockId;
  }

  /**
   * Creates and initializes the btree.
   */
  public void create()
    throws IOException
  {
  }
  
  public long lookup(byte []keyBuffer,
		     int keyOffset,
		     int keyLength,
		     Transaction xa)
    throws IOException, SQLException
  {
    return lookup(keyBuffer, keyOffset, keyLength, xa, _rootBlockId);
  }
  
  private long lookup(byte []keyBuffer,
		     int keyOffset,
		     int keyLength,
		     Transaction xa,
		     long blockId)
    throws IOException, SQLException
  {
    Block block;

    if (blockId == _rootBlockId) {
      block = _rootBlock;
      block.allocate();
    }
    else
      block = _store.readBlock(blockId);

    try {
      Lock blockLock = block.getLock();
      xa.lockRead(blockLock);

      try {
	byte []buffer = block.getBuffer();

	boolean isLeaf = isLeaf(buffer);
      
	long value = lookupTuple(blockId, buffer,
				 keyBuffer, keyOffset, keyLength,
				 isLeaf);

	if (isLeaf || value == FAIL)
	  return value;
	else
	  return lookup(keyBuffer, keyOffset, keyLength,
			xa, value);
      } finally {
        xa.unlockRead(blockLock);
      }
    } finally {
      block.free();
    }
  }
  
  /**
   * Inserts the new value for the given key.
   *
   * @return false if the block needs to be split
   */
  public void insert(byte []keyBuffer,
		     int keyOffset,
		     int keyLength,
		     long value,
		     Transaction xa,
		     boolean isOverride)
    throws SQLException
  {
    try {
      while (! insert(keyBuffer, keyOffset, keyLength,
		      value, xa, isOverride,
		      _rootBlockId)) {
	splitRoot(_rootBlockId, xa);
      }
    } catch (IOException e) {
      log.log(Level.FINE, e.toString(), e);
      
      throw new SQLExceptionWrapper(e.toString(), e);
    }
  }

  /**
   * Inserts the new value for the given key.
   *
   * @return false if the block needs to be split
   */
  private boolean insert(byte []keyBuffer,
			 int keyOffset,
			 int keyLength,
			 long value,
			 Transaction xa,
			 boolean isOverride,
			 long blockId)
    throws IOException, SQLException
  {
    Block block;

    if (blockId == _rootBlockId) {
      block = _rootBlock;
      block.allocate();
    }
    else
      block = _store.readBlock(blockId);
    
    try {
      Lock blockLock = block.getLock();
      xa.lockRead(blockLock);
      
      try {
	byte []buffer = block.getBuffer();

	int length = getLength(buffer);

	if (length == _n) {
	  // return false if the block needs to be split
	  return false;
	}
	
	if (isLeaf(buffer)) {
	  insertValue(keyBuffer, keyOffset, keyLength,
		      value, xa, isOverride, block);

	  return true;
	}

	long childBlockId = lookupTuple(blockId, buffer,
					keyBuffer, keyOffset, keyLength,
					false);

	while (! insert(keyBuffer, keyOffset, keyLength,
			value, xa, isOverride,
			childBlockId)) {
	  split(block, childBlockId, xa);

	  childBlockId = lookupTuple(blockId, buffer,
				     keyBuffer, keyOffset, keyLength,
				     false);
	}

	return true;
      } finally {
	xa.unlockRead(blockLock);
      }
    } finally {
      block.free();
    }
  }
    
  /**
   * Inserts into the next block given the current block and the given key.
   */
  private void insertValue(byte []keyBuffer,
			   int keyOffset,
			   int keyLength,
			   long value,
			   Transaction xa,
			   boolean isOverride,
			   Block block)
    throws IOException, SQLException
  {
    byte []buffer = block.getBuffer();

    Lock blockLock = block.getLock();
    xa.lockWrite(blockLock);
    try {
      block.setFlushDirtyOnCommit(false);
      block.setDirty(0, Store.BLOCK_SIZE);
	    
      insertLeafBlock(block.getBlockId(), buffer,
		      keyBuffer, keyOffset, keyLength,
		      value,
		      isOverride);
    } finally {
      xa.unlockWrite(blockLock);
    }
  }

  /**
   * Inserts into the next block given the current block and the given key.
   */
  private long insertLeafBlock(long blockId,
                               byte []buffer,
                               byte []keyBuffer,
                               int keyOffset,
                               int keyLength,
                               long value,
			       boolean isOverride)
    throws IOException, SQLException
  {
    int offset = HEADER_SIZE;
    int tupleSize = _tupleSize;
    int length = getLength(buffer);

    for (int i = 0; i < length; i++) {
      int cmp = _keyCompare.compare(keyBuffer, keyOffset,
				    buffer, offset + PTR_SIZE,
				    keyLength);

      if (0 < cmp) {
        offset += tupleSize;
        continue;
      }
      else if (cmp == 0) {
	if (! isOverride) {
	  long oldValue = getPointer(buffer, offset);

	  if (value != oldValue)
	    throw new SQLException(L.l("'{0}' insert of key '{1}' fails index uniqueness.",
				       _store,
				       _keyCompare.toString(keyBuffer, keyOffset, keyLength)));
	}
	
        setPointer(buffer, offset, value);
        //writeBlock(blockIndex, block);
        
        return 0;
      }
      else if (length < _n) {
        return addKey(blockId, buffer, offset, i, length,
                      keyBuffer, keyOffset, keyLength, value);
      }
      else {
	throw new IllegalStateException("ran out of key space");
      }
    }

    if (length < _n) {
      return addKey(blockId, buffer, offset, length, length,
                    keyBuffer, keyOffset, keyLength, value);
    }

    throw new IllegalStateException();

    // return split(blockIndex, block);
  }

  private long addKey(long blockId, byte []buffer, int offset,
		      int index, int length,
                      byte []keyBuffer, int keyOffset, int keyLength,
                      long value)
    throws IOException
  {
    int tupleSize = _tupleSize;

    if (index < length) {
      if (offset + tupleSize < HEADER_SIZE)
	throw new IllegalStateException();
      
      System.arraycopy(buffer, offset,
                       buffer, offset + tupleSize,
                       (length - index) * tupleSize);
    }
    
    setPointer(buffer, offset, value);
    setLength(buffer, length + 1);

    if (log.isLoggable(Level.FINEST))
      log.finest("btree insert at " + debugId(blockId) + ":" + offset + " value:" + debugId(value));

    if (offset + PTR_SIZE < HEADER_SIZE)
      throw new IllegalStateException();
      
    System.arraycopy(keyBuffer, keyOffset,
		     buffer, offset + PTR_SIZE,
		     keyLength);
          
    for (int j = PTR_SIZE + keyLength; j < tupleSize; j++)
      buffer[offset + j] = 0;

    return -value;
  }

  /**
   * The length in lBuf is assumed to be the length of the buffer.
   */
  private void split(Block parent,
		     long blockId,
		     Transaction xa)
    throws IOException, SQLException
  {
    Lock parentLock = parent.getLock();
    xa.lockWrite(parentLock);
    
    try {
      Block block = _store.readBlock(blockId);

      try {
	Lock blockLock = block.getLock();
	xa.lockReadAndWrite(blockLock);
	
	try {
	  split(parent, block, xa);
	} finally {
	  xa.unlockReadAndWrite(blockLock);
	}
      } finally {
	block.free();
      }
    } finally {
      xa.unlockWrite(parentLock);
    }
  }

  /**
   * The length in lBuf is assumed to be the length of the buffer.
   */
  private void split(Block parentBlock,
		     Block block,
		     Transaction xa)
    throws IOException, SQLException
  {
    long parentId = parentBlock.getBlockId();
    long blockId = block.getBlockId();
    
    log.finer("btree splitting " + debugId(blockId));
    
    block.setFlushDirtyOnCommit(false);
    block.setDirty(0, Store.BLOCK_SIZE);

    byte []buffer = block.getBuffer();
    int length = getLength(buffer);

    // Check length to avoid possible timing issue, since we release the
    // read lock for the block between the initial check in insert() and
    // getting it back in split()
    if (length < _n / 2)
      return;

    if (length < 2)
      throw new IllegalStateException(L.l("illegal length '{0}' for block {1}",
					  length, debugId(blockId)));
      
    //System.out.println("INDEX SPLIT: " + debugId(blockId) + " " + length + " " + block + " " + buffer);

    Block leftBlock = null;

    try {
      parentBlock.setFlushDirtyOnCommit(false);
      parentBlock.setDirty(0, Store.BLOCK_SIZE);
    
      byte []parentBuffer = parentBlock.getBuffer();
      int parentLength = getLength(parentBuffer);
    
      leftBlock = _store.allocateIndexBlock();
      leftBlock.setFlushDirtyOnCommit(false);
      leftBlock.setDirty(0, Store.BLOCK_SIZE);
      
      byte []leftBuffer = leftBlock.getBuffer();
      long leftBlockId = leftBlock.getBlockId();

      int pivot = length / 2;

      int pivotSize = pivot * _tupleSize;
      int pivotEnd = HEADER_SIZE + pivotSize;

      System.arraycopy(buffer, HEADER_SIZE,
		       leftBuffer, HEADER_SIZE,
		       pivotSize);

      setInt(leftBuffer, FLAGS_OFFSET, getInt(buffer, FLAGS_OFFSET));
      setLength(leftBuffer, pivot);
      // XXX: NEXT_OFFSET needs to work with getRightIndex
      setPointer(leftBuffer, NEXT_OFFSET, 0);
      setPointer(leftBuffer, PARENT_OFFSET, parentId);

      System.arraycopy(buffer, pivotEnd,
		       buffer, HEADER_SIZE,
		       length * _tupleSize - pivotEnd);

      setLength(buffer, length - pivot);

      insertLeafBlock(parentId, parentBuffer,
		      leftBuffer, pivotEnd - _tupleSize + PTR_SIZE, _keySize,
		      leftBlockId,
		      true);
    } finally {
      if (leftBlock != null)
	leftBlock.free();
    }
  }

  /**
   * The length in lBuf is assumed to be the length of the buffer.
   */
  private void splitRoot(long rootBlockId,
			 Transaction xa)
    throws IOException, SQLException