mergesort.java

derby database source code.good for you.

/*

   Derby - Class org.apache.derby.impl.store.access.sort.MergeSort

   Copyright 1997, 2004 The Apache Software Foundation or its licensors, as applicable.

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

      http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.

 */

package org.apache.derby.impl.store.access.sort;

import org.apache.derby.iapi.reference.SQLState;

import org.apache.derby.iapi.services.io.FormatableBitSet;

import org.apache.derby.iapi.services.io.Storable;
import org.apache.derby.iapi.services.sanity.SanityManager;
import org.apache.derby.iapi.error.StandardException;
import org.apache.derby.iapi.store.access.conglomerate.ScanControllerRowSource;
import org.apache.derby.iapi.store.access.conglomerate.Sort;
import org.apache.derby.iapi.store.access.conglomerate.SortFactory;
import org.apache.derby.iapi.store.access.conglomerate.TransactionManager;
import org.apache.derby.iapi.types.CloneableObject;
import org.apache.derby.iapi.store.access.ColumnOrdering;
import org.apache.derby.iapi.store.access.ConglomerateController;
import org.apache.derby.iapi.store.access.Qualifier;
import org.apache.derby.iapi.store.access.RowUtil;
import org.apache.derby.iapi.store.access.ScanController;
import org.apache.derby.iapi.store.access.SortObserver;
import org.apache.derby.iapi.store.access.SortController;
import org.apache.derby.iapi.store.access.TransactionController;

import org.apache.derby.iapi.store.raw.StreamContainerHandle;
import org.apache.derby.iapi.store.raw.RawStoreFactory;
import org.apache.derby.iapi.store.raw.Transaction;

import org.apache.derby.iapi.types.DataValueDescriptor;

import org.apache.derby.iapi.types.Orderable;
import org.apache.derby.iapi.types.RowLocation;

import java.util.Enumeration;
import java.util.Properties;
import java.util.Vector;

/**

  A sort implementation which does the sort in-memory if it can,
  but which can do an external merge sort so that it can sort an
  arbitrary number of rows.

**/

public final class MergeSort implements Sort
{

	/*
	 * Fields
	 */

	/**
	**/
	static final int STATE_CLOSED = 0;

	/**
	**/
	static final int STATE_INITIALIZED = 1;

	/**
	**/
	static final int STATE_INSERTING = 2;

	/**
	**/
	static final int STATE_DONE_INSERTING = 3;

	/**
	**/
	static final int STATE_SCANNING = 4;

	/**
	**/
	static final int STATE_DONE_SCANNING = 5;

	/**
	Maintains the current state of the sort as defined in
	the preceding values.  Sorts start off and end up closed.
	**/
	protected int state = STATE_CLOSED;

	/**
	The template as passed in on create.  Valid when the state
	is INITIALIZED through SCANNING, null otherwise.
	**/
	protected DataValueDescriptor[] template;

	/**
	The column ordering as passed in on create.  Valid when
	the state is INITIALIZED through SCANNING, null otherwise.
	May be null if there is no column ordering - this means
	that all rows are considered to be duplicates, and the
	sort will only emit a single row.
	**/
	protected ColumnOrdering columnOrdering[];

	/**
    A lookup table to speed up lookup of a column associated with the i'th
    column to compare.  To find the column id to compare as the i'th column
    look in columnOrderingMap[i].
	**/
	protected int columnOrderingMap[];

	/**
    A lookup table to speed up lookup of Ascending state of a column, 
	**/
	protected boolean columnOrderingAscendingMap[];

	/**
	The sort observer.  May be null.  Used as a callback.
	**/
	protected SortObserver sortObserver;

	/**
	Whether the rows are expected to be in order on insert,
	as passed in on create.
	**/
	protected boolean alreadyInOrder;

	/**
	The inserter that's being used to insert rows into the sort.
	This field is only valid when the state is INSERTING.
	**/
	protected MergeInserter inserter = null;

	/**
	The scan that's being used to return rows from the sort.
	This field is only valid when the state is SCANNING.
	**/
	protected Scan scan = null;

	/**
	A vector of merge runs, produced by the MergeInserter.
	Might be null if no merge runs were produced.
	It is a vector of container ids.
	**/
	protected Vector mergeRuns = null;

	/**
	An ordered set of the leftover rows that didn't go
	in the last merge run (might be all the rows if there
	are no merge runs).
	**/
	protected SortBuffer sortBuffer = null;

	/**
	The maximum number of entries a sort buffer can hold.
	**/
	protected int sortBufferMax;

	/**
	The minimum number of entries a sort buffer can hold.
	**/
	protected int sortBufferMin;

	/**
	Properties for mergeSort
	**/
	static Properties properties = null;

    /**
    Static initializer for MergeSort, to initialize once the properties
	for the sortBuffer.  
	**/
    static
    {
		properties = new Properties();
		properties.put(RawStoreFactory.STREAM_FILE_BUFFER_SIZE_PARAMETER, "16384");
    }

	/*
	 * Methods of Sort
	 */

	/**
	Open a sort controller.
	<p>
	This implementation only supports a single sort controller
	per sort.
	@see Sort#open
	**/
	public SortController open(TransactionManager tran)
		throws StandardException
	{
		if (SanityManager.DEBUG)
			SanityManager.ASSERT(state == STATE_INITIALIZED);

		// Ready to start inserting rows.
		state = STATE_INSERTING;

		// Create and initialize an inserter.  When the caller
		// closes it, it will call back to inserterIsClosed().
		this.inserter = new MergeInserter();
		if (this.inserter.initialize(this, tran) == false)
        {
			throw StandardException.newException(SQLState.SORT_COULD_NOT_INIT);
        }

		return this.inserter;
	}

	/**
	Open a scan controller.
	@see Sort#openSortScan
	**/

	public ScanController openSortScan(
    TransactionManager tran,
    boolean            hold)
			throws StandardException
	{
		if (SanityManager.DEBUG)
			SanityManager.ASSERT(state == STATE_DONE_INSERTING);

		if (mergeRuns == null || mergeRuns.size() == 0)
		{
			// There were no merge runs so we can just return
			// the rows from the sort buffer.
			scan = new SortBufferScan(this, tran, sortBuffer, hold);

			// The scan now owns the sort buffer
			sortBuffer = null;
		}
		else
		{
			// Dump the rows in the sort buffer to a merge run.
			long containerId = createMergeRun(tran, sortBuffer);
			mergeRuns.addElement(new Long(containerId));

			// If there are more merge runs than we can sort
			// at once with our sort buffer, we have to reduce
			// the number of merge runs
			if (mergeRuns.size() > ExternalSortFactory.DEFAULT_MAX_MERGE_RUN ||
				mergeRuns.size() > sortBuffer.capacity())
					multiStageMerge(tran);

			// There are now few enough merge runs to sort
			// at once, so create a scan for them.
			MergeScan mscan = 
                new MergeScan(
                    this, tran, sortBuffer, mergeRuns, sortObserver, hold);

			if (!mscan.init(tran))
            {
                throw StandardException.newException(
                        SQLState.SORT_COULD_NOT_INIT);
            }
			scan = mscan;

			// The scan now owns the sort buffer and merge runs.
			sortBuffer = null;
			mergeRuns = null;
		}

		// Ready to start retrieving rows.
		this.state = STATE_SCANNING;

		return scan;
	}

	/**
	Open a row source to get rows out of the sorter.
	@see Sort#openSortRowSource
	**/
	public ScanControllerRowSource openSortRowSource(TransactionManager tran)
			throws StandardException
	{
		if (SanityManager.DEBUG)
			SanityManager.ASSERT(state == STATE_DONE_INSERTING);

		ScanControllerRowSource rowSource = null;

		if (mergeRuns == null || mergeRuns.size() == 0)
		{
			// There were no merge runs so we can just return
			// the rows from the sort buffer.
			scan = new SortBufferRowSource(sortBuffer, tran, sortObserver, false, sortBufferMax);
			rowSource = (ScanControllerRowSource)scan;

			// The scan now owns the sort buffer
			sortBuffer = null;
		}
		else
		{
			// Dump the rows in the sort buffer to a merge run.
			long containerId = createMergeRun(tran, sortBuffer);
			mergeRuns.addElement(new Long(containerId));

			// If there are more merge runs than we can sort
			// at once with our sort buffer, we have to reduce
			// the number of merge runs
			if (mergeRuns.size() > ExternalSortFactory.DEFAULT_MAX_MERGE_RUN ||
				mergeRuns.size() > sortBuffer.capacity())	
				multiStageMerge(tran);

			// There are now few enough merge runs to sort
			// at once, so create a rowSource for them.
			MergeScanRowSource msRowSource = 
				new MergeScanRowSource(this, tran, sortBuffer, mergeRuns, sortObserver, false);
			if (!msRowSource.init(tran))
            {
                throw StandardException.newException(
                        SQLState.SORT_COULD_NOT_INIT);
            }
			scan = msRowSource;
			rowSource = msRowSource;

			// The scan now owns the sort buffer and merge runs.
			sortBuffer = null;
			mergeRuns = null;
		}

		// Ready to start retrieving rows.
		this.state = STATE_SCANNING;

		return rowSource;
	}



	/**
	Drop the sort.
	@see Sort#drop
	**/
	public void drop(TransactionController tran)
        throws StandardException
	{
		// Make sure the inserter is closed.  Note this
		// will cause the callback to doneInserting()
		// which will give us any in-progress merge
		// runs, if there are any.
		if (inserter != null)
			inserter.close();
		inserter = null;

		// Make sure the scan is closed, if there is one.
		// This will cause the callback to doneScanning().
		if (scan != null)
		{
			scan.close();
			scan = null;
		}

		// If we have a row set, get rid of it.
		if (sortBuffer != null)
		{
			sortBuffer.close();
			sortBuffer = null;
		}

		// Clean out the rest of the objects.
		template = null;
		columnOrdering = null;
		sortObserver = null;

		// If there are any merge runs, drop them.
		dropMergeRuns((TransactionManager)tran);

		// Whew!
		state = STATE_CLOSED;
	}


	/*
	 * Methods of MergeSort.  Arranged alphabetically.
	 */