btree.java

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

  {
    Block rootBlock = _rootBlock; // store.readBlock(rootBlockId);
    rootBlock.allocate();

    try {
      Lock rootLock = rootBlock.getLock();
      xa.lockReadAndWrite(rootLock);
      
      try {
	splitRoot(rootBlock, xa);
      } finally {
	xa.unlockReadAndWrite(rootLock);
      }
    } finally {
      rootBlock.free();
    }
  }

  /**
   * Splits the current leaf into two.  Half of the entries go to the
   * left leaf and half go to the right leaf.
   */
  private void splitRoot(Block parentBlock, Transaction xa)
    throws IOException
  {
    long parentId = parentBlock.getBlockId();
    
    //System.out.println("INDEX SPLIT ROOT: " + (parentId / BLOCK_SIZE));
    log.finer("btree splitting root " + (parentId / BLOCK_SIZE));

    Block leftBlock = null;
    Block rightBlock = null;

    try {
      parentBlock.setFlushDirtyOnCommit(false);
      parentBlock.setDirty(0, Store.BLOCK_SIZE);

      byte []parentBuffer = parentBlock.getBuffer();

      int parentFlags = getInt(parentBuffer, FLAGS_OFFSET);

      leftBlock = _store.allocateIndexBlock();
      leftBlock.setFlushDirtyOnCommit(false);
      leftBlock.setDirty(0, Store.BLOCK_SIZE);
      
      long leftBlockId = leftBlock.getBlockId();
    
      rightBlock = _store.allocateIndexBlock();
      rightBlock.setFlushDirtyOnCommit(false);
      rightBlock.setDirty(0, Store.BLOCK_SIZE);
      
      long rightBlockId = rightBlock.getBlockId();

      int length = getLength(parentBuffer);

      int pivot = (length - 1) / 2;

      if (length <= 2 || _n < length || pivot < 1 || length <= pivot)
	throw new IllegalStateException(length + " is an illegal length, or pivot " + pivot + " is bad, with n=" + _n);

      int pivotOffset = HEADER_SIZE + pivot * _tupleSize;
      long pivotValue = getPointer(parentBuffer, pivotOffset);

      byte []leftBuffer = leftBlock.getBuffer();

      System.arraycopy(parentBuffer, HEADER_SIZE,
		       leftBuffer, HEADER_SIZE,
		       pivotOffset + _tupleSize - HEADER_SIZE);
      setInt(leftBuffer, FLAGS_OFFSET, parentFlags);
      setLength(leftBuffer, pivot + 1);
      setPointer(leftBuffer, PARENT_OFFSET, parentId);
      setPointer(leftBuffer, NEXT_OFFSET, rightBlockId);

      byte []rightBuffer = rightBlock.getBuffer();

      if (length - pivot - 1 < 0)
	throw new IllegalStateException("illegal length " + pivot + " " + length);

      System.arraycopy(parentBuffer, pivotOffset + _tupleSize,
		       rightBuffer, HEADER_SIZE,
		       (length - pivot - 1) * _tupleSize);

      setInt(rightBuffer, FLAGS_OFFSET, parentFlags);
      setLength(rightBuffer, length - pivot - 1);
      setPointer(rightBuffer, PARENT_OFFSET, parentId);
      setPointer(rightBuffer, NEXT_OFFSET,
		 getPointer(parentBuffer, NEXT_OFFSET));

      System.arraycopy(parentBuffer, pivotOffset,
		       parentBuffer, HEADER_SIZE,
		       _tupleSize);
      setPointer(parentBuffer, HEADER_SIZE, leftBlockId);

      setInt(parentBuffer, FLAGS_OFFSET, LEAF_FLAG);
      setLength(parentBuffer, 1);
      setPointer(parentBuffer, NEXT_OFFSET, rightBlockId);
    } finally {
      if (leftBlock != null)
	leftBlock.free();
      
      if (rightBlock != null)
	rightBlock.free();
    }
  }
  
  public void remove(byte []keyBuffer,
		      int keyOffset,
		      int keyLength,
		      Transaction xa)
    throws SQLException
  {
    try {
      Block rootBlock = _rootBlock; // _store.readBlock(_rootBlockId);
      rootBlock.allocate();

      try {
	Lock rootLock = rootBlock.getLock();
	xa.lockRead(rootLock);

	try {
	  remove(rootBlock, keyBuffer, keyOffset, keyLength, xa);
	} finally {
	  xa.unlockRead(rootLock);
	}
      } finally {
	rootBlock.free();
      }
    } catch (IOException e) {
      throw new SQLExceptionWrapper(e.toString(), e);
    }
  }

  /**
   * Recursively remove a key from the index.
   *
   * block is read-locked by the parent.
   */
  private boolean remove(Block block,
			 byte []keyBuffer,
			 int keyOffset,
			 int keyLength,
			 Transaction xa)
    throws IOException, SQLException
  {
    byte []buffer = block.getBuffer();
    long blockId = block.getBlockId();

    boolean isLeaf = isLeaf(buffer);
      
    if (isLeaf) {
      Lock blockLock = block.getLock();
      
      xa.lockWrite(blockLock);

      try {
	block.setFlushDirtyOnCommit(false);
	block.setDirty(0, Store.BLOCK_SIZE);

	removeLeafEntry(blockId, buffer,
			keyBuffer, keyOffset, keyLength);
      } finally {
	xa.unlockWrite(blockLock);
      }
    }
    else {
      long childId;
	
      childId = lookupTuple(blockId, buffer,
			    keyBuffer, keyOffset, keyLength,
			    isLeaf);

      if (childId == FAIL)
	return true;

      Block childBlock = _store.readBlock(childId);
      try {
	boolean isJoin = false;

	Lock childLock = childBlock.getLock();
	xa.lockRead(childLock);

	try {
	  isJoin = ! remove(childBlock,
			    keyBuffer, keyOffset, keyLength,
			    xa);
	} finally {
	  xa.unlockRead(childLock);
	}

	if (isJoin) {
	  if (joinBlocks(block, childBlock, xa)) {
	    xa.deallocateBlock(childBlock);
	  }
	}
      } finally {
	childBlock.free();
      }
    }
      
    return _minN <= getLength(buffer);
  }

  /**
   * Performs any block-merging cleanup after the delete.
   *
   * parent is read-locked by the parent.
   * block is not locked.
   *
   * @return true if the block should be deleted/freed
   */
  private boolean joinBlocks(Block parent,
			     Block block,
			     Transaction xa)
    throws IOException, SQLException
  {
    byte []parentBuffer = parent.getBuffer();
    int parentLength = getLength(parentBuffer);

    long blockId = block.getBlockId();
    byte []buffer = block.getBuffer();
    
    //System.out.println("INDEX JOIN: " + debugId(blockId));

    Lock parentLock = parent.getLock();
    xa.lockWrite(parentLock);
    try {
      long leftBlockId = getLeftBlockId(parent, blockId);
      long rightBlockId = getRightBlockId(parent, blockId);

      // try to shift from left and right first
      if (leftBlockId > 0) {
	Block leftBlock = _store.readBlock(leftBlockId);

	try {
	  byte []leftBuffer = leftBlock.getBuffer();
	
	  Lock leftLock = leftBlock.getLock();
	  xa.lockReadAndWrite(leftLock);
	  
	  try {
	    int leftLength = getLength(leftBuffer);

	    Lock blockLock = block.getLock();
	    xa.lockReadAndWrite(blockLock);
	    
	    try {
	      if (_minN < leftLength
		  && isLeaf(buffer) == isLeaf(leftBuffer)) {
		parent.setFlushDirtyOnCommit(false);
		parent.setDirty(0, Store.BLOCK_SIZE);
	    
		leftBlock.setFlushDirtyOnCommit(false);
		leftBlock.setDirty(0, Store.BLOCK_SIZE);
	  
		//System.out.println("MOVE_FROM_LEFT: " + debugId(blockId) + " from " + debugId(leftBlockId));
		moveFromLeft(parentBuffer, leftBuffer, buffer, blockId);

		return false;
	      }
	    } finally {
	      xa.unlockReadAndWrite(blockLock);
	    }
	  } finally {
	    xa.unlockReadAndWrite(leftLock);
	  }
	} finally {
	  leftBlock.free();
	}
      }

      if (rightBlockId > 0) {
	Block rightBlock = _store.readBlock(rightBlockId);

	try {
	  byte []rightBuffer = rightBlock.getBuffer();
	
	  Lock blockLock = block.getLock();
	  xa.lockReadAndWrite(blockLock);

	  try {
	    Lock rightLock = rightBlock.getLock();
	    xa.lockReadAndWrite(rightLock);
	      
	    try {
	      int rightLength = getLength(rightBuffer);

	      if (_minN < rightLength
		  && isLeaf(buffer) == isLeaf(rightBuffer)) {
		parent.setFlushDirtyOnCommit(false);
		parent.setDirty(0, Store.BLOCK_SIZE);
	    
		rightBlock.setFlushDirtyOnCommit(false);
		rightBlock.setDirty(0, Store.BLOCK_SIZE);

		//System.out.println("MOVE_FROM_RIGHT: " + debugId(blockId) + " from " + debugId(rightBlockId));
	    
		moveFromRight(parentBuffer, buffer, rightBuffer, blockId);

		return false;
	      }
	    } finally {
	      xa.unlockReadAndWrite(rightLock);
	    }
	  } finally {
	    xa.unlockReadAndWrite(blockLock);
	  }
	} finally {
	  rightBlock.free();
	}
      }

      if (parentLength < 2)
	return false;
    
      if (leftBlockId > 0) {
	Block leftBlock = _store.readBlock(leftBlockId);
      
	try {
	  byte []leftBuffer = leftBlock.getBuffer();
	  
	  Lock leftLock = leftBlock.getLock();
	  xa.lockReadAndWrite(leftLock);

	  try {
	    int leftLength = getLength(leftBuffer);
	    
	    Lock blockLock = block.getLock();
	    xa.lockReadAndWrite(blockLock);

	    try {
	      int length = getLength(buffer);
	      
	      if (isLeaf(leftBuffer) == isLeaf(buffer)
		  && length + leftLength <= _n) {
		parent.setFlushDirtyOnCommit(false);
		parent.setDirty(0, Store.BLOCK_SIZE);
	  
		leftBlock.setFlushDirtyOnCommit(false);
		leftBlock.setDirty(0, Store.BLOCK_SIZE);
      
		//System.out.println("MERGE_LEFT: " + debugId(blockId) + " from " + debugId(leftBlockId));
	    
		mergeLeft(parentBuffer, leftBuffer, buffer, blockId);

		return true;
	      }
	    } finally {
	      xa.unlockReadAndWrite(blockLock);
	    }
	  } finally {
	    xa.unlockReadAndWrite(leftLock);
	  }
	} finally {
	  leftBlock.free();
	}
      }
    
      if (rightBlockId > 0) {
	Block rightBlock = _store.readBlock(rightBlockId);

	try {
	  byte []rightBuffer = rightBlock.getBuffer();

	  Lock blockLock = block.getLock();
	  xa.lockReadAndWrite(blockLock);

	  try {
	    Lock rightLock = rightBlock.getLock();
	    xa.lockReadAndWrite(rightLock);

	    try {
	      int length = getLength(buffer);
	      int rightLength = getLength(rightBuffer);
	      
	      if (isLeaf(rightBuffer) == isLeaf(buffer)
		  && length + rightLength <= _n) {
		rightBlock.setFlushDirtyOnCommit(false);
		rightBlock.setDirty(0, Store.BLOCK_SIZE);
	  
		parent.setFlushDirtyOnCommit(false);
		parent.setDirty(0, Store.BLOCK_SIZE);
	  
		//System.out.println("MERGE_RIGHT: " + debugId(blockId) + " from " + debugId(rightBlockId));
	    
		mergeRight(parentBuffer, buffer, rightBuffer, blockId);

		return true;
	      }
	    } finally {
	      xa.unlockReadAndWrite(rightLock);
	    }
	  } finally {
	    xa.unlockReadAndWrite(blockLock);
	  }
	} finally {
	  rightBlock.free();
	}
      }

      return false;
    } finally {
      xa.unlockWrite(parentLock);
    }
  }

  /**
   * Returns the index to the left of the current one
   */
  private long getLeftBlockId(Block parent, long blockId)
  {
    byte []buffer = parent.getBuffer();
    
    int length = getLength(buffer);

    if (length < 1)
      throw new IllegalStateException("zero length for " + debugId(parent.getBlockId()));

    int offset = HEADER_SIZE;
    int tupleSize = _tupleSize;
    int end = offset + length * tupleSize;

    for (; offset < end; offset += tupleSize) {
      long pointer = getPointer(buffer, offset);

      if (pointer == blockId) {
	if (HEADER_SIZE < offset) {
	  return getPointer(buffer, offset - tupleSize);
	}
	else
	  return -1;
      }
    }
    
    long pointer = getPointer(buffer, NEXT_OFFSET);
    
    if (pointer == blockId)
      return getPointer(buffer, HEADER_SIZE + (length - 1) * tupleSize);
    else
      throw new IllegalStateException("Can't find " + debugId(blockId) + " in parent " + debugId(parent.getBlockId()));
  }

  /**
   * Takes the last entry from the left block and moves it to the
   * first entry in the current block.
   *
   * @param parentBuffer the parent block buffer
   * @param leftBuffer the left block buffer
   * @param buffer the block's buffer
   * @param index the index of the block
   */
  private void moveFromLeft(byte []parentBuffer,
			    byte []leftBuffer,
			    byte []buffer,
			    long blockId)
  {
    int parentLength = getLength(parentBuffer);

    int tupleSize = _tupleSize;
    int parentOffset = HEADER_SIZE;
    int parentEnd = parentOffset + parentLength * tupleSize;

    int leftLength = getLength(leftBuffer);

    int length = getLength(buffer);

    // pointer in the parent to the left defaults to the tail - 1
    int parentLeftOffset = -1;

    if (blockId == getPointer(parentBuffer, NEXT_OFFSET)) {
      // parentLeftOffset = parentOffset - tupleSize;
      parentLeftOffset = parentEnd - tupleSize;
    }
    else {
      for (parentOffset += tupleSize;
	   parentOffset < parentEnd;
	   parentOffset += tupleSize) {
	long pointer = getPointer(parentBuffer, parentOffset);

	if (pointer == blockId) {
	  parentLeftOffset = parentOffset - tupleSize;
	  break;
	}
      }
    }

    if (parentLeftOffset < 0) {
      log.warning("Can't find parent left in deletion borrow left ");
      return;
    }

    // shift the data in the buffer
    System.arraycopy(buffer, HEADER_SIZE,
		     buffer, HEADER_SIZE + tupleSize,
		     length * tupleSize);

    // copy the last item in the left to the buffer
    System.arraycopy(leftBuffer, HEADER_SIZE + (leftLength - 1) * tupleSize,
		     buffer, HEADER_SIZE,
		     tupleSize);

    // add the buffer length
    setLength(buffer, length + 1);

    // subtract from the left length
    leftLength -= 1;
    setLength(leftBuffer, leftLength);

    // copy the entry from the new left tail to the parent
    System.arraycopy(leftBuffer,
		     HEADER_SIZE + (leftLength - 1) * tupleSize + PTR_SIZE,
		     parentBuffer, parentLeftOffset + PTR_SIZE,
		     tupleSize - PTR_SIZE);
  }

  /**
   * Returns the index to the left of the current one
   */
  private void mergeLeft(byte []parentBuffer,
			 byte []leftBuffer,
			 byte []buffer,
			 long blockId)
  {
    int leftLength = getLength(leftBuffer);
    int length = getLength(buffer);

    int parentLength = getLength(parentBuffer);

    int tupleSize = _tupleSize;
    int parentOffset = HEADER_SIZE;
    int parentEnd = parentOffset + parentLength * tupleSize;

    for (parentOffset += tupleSize;
	 parentOffset < parentEnd;
	 parentOffset += tupleSize) {
      long pointer = getPointer(parentBuffer, parentOffset);

      if (pointer == blockId) {
	int leftOffset = HEADER_SIZE + leftLength * tupleSize;