sortbuffer.java

derby database source code.good for you.

/*

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

   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.services.sanity.SanityManager;
import org.apache.derby.iapi.error.StandardException;
import org.apache.derby.iapi.store.access.SortObserver;

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

/**

  This class implements an in-memory ordered set
  based on the balanced binary tree algorithm from
  Knuth Vol. 3, Sec. 6.2.3, pp. 451-471.
  Nodes are always maintained in order,
  so that inserts and deletes can be intermixed.
  <P>
  This algorithm will insert/delete N elements
  in O(N log(N)) time using O(N) space. 

**/

class SortBuffer
{
	/**
	Returned from insert when the row was inserted
	without incident.
	**/
	public static final int INSERT_OK = 0;

	/**
	Returned from insert when the row which was
	inserted was a duplicate.  The set will have
	aggregated it in.
	**/
	public static final int INSERT_DUPLICATE = 1;

	/**
	Returned from insert when the row was not able to be
	inserted because the set was full.
	**/
	public static final int INSERT_FULL = 2;

	/**
	The sort this set is associated with.
	**/
	private MergeSort sort;

	/**
	Where to allocate nodes from.
	**/
	private NodeAllocator allocator = null;

	/**
	Special head node for the tree.  Head.rightLink is the
	root of the tree.
	**/
	private Node head = null;

	/**
	The current height of the tree.
	**/
	private int height = 0;

	/**
	Set, as a side effect of deleteLeftMost (only), to the
	key from the node that was deleted from the tree.  This
	field is only valid after a call to deleteLeftMost.
	**/
	private DataValueDescriptor[] deletedKey;

	/**
	Set, as a side effect of deleteLeftMost and rotateRight,
	if the subtree they're working on decreased in height.
	This field is only valid after a call to deleteLeftMost
	or rotateRight.
	**/
	private boolean subtreeShrunk;

	/**
	Set by the setNextAux() method.  This value is stuffed
	into the aux field of the next node that's allocated.
	**/
	private int nextAux;

	/**
	Read by the getLastAux() method.  This value is read out
	of the last node that was deallocated from the tree.
	**/
	private int lastAux;

	/**
	Arrange that the next node allocated in the tree have
	it's aux field set to the argument.
	**/
	public void setNextAux(int aux)
	{
		nextAux = aux;
	}

	/**
	Retrieve the aux value from the last node deallocated
	from the tree.
	**/
	public int getLastAux()
	{
		return lastAux;
	}

	/**
	Construct doesn't do anything, callers must call init
	and check its return code.
	**/
	public SortBuffer(MergeSort sort)
	{
		this.sort = sort;
	}

	/**
	Initialize.  Returns false if the allocator
	couldn't be initialized.
	**/
	public boolean init()
	{
		allocator = new NodeAllocator();

		boolean initOK = false;

		if (sort.sortBufferMin > 0)
			initOK = allocator.init(sort.sortBufferMin, sort.sortBufferMax);
		else
			initOK = allocator.init(sort.sortBufferMax);

		if (initOK == false)
		{
			allocator = null;
			return false;
		}
		reset();
		return true;
	}

	public void reset()
	{
		allocator.reset();
		head = allocator.newNode();
		height = 0;
	}

	public void close()
	{
		if (allocator != null)
			allocator.close();
		allocator = null;
		height = 0;
		head = null;
	}

	/**
	Grow by a certain percent if we can
	*/
	public void grow(int percent)
	{
		if (percent > 0)
			allocator.grow(percent);
	}


	/**
	Return the number of elements this sorter can sort.
	It's the capacity of the node allocator minus one
	because the sorter uses one node for the head.
	**/
	public int capacity()
	{
		if (allocator == null)
			return 0;
		return allocator.capacity() - 1;
	}

	/**
	Insert a key k into the tree. Returns true if the
	key was inserted, false if the tree is full.  Silently
	ignores duplicate keys.
	<P>
	See Knuth Vol. 3, Sec. 6.2.3, pp. 455-457 for the algorithm.
	**/
	public int insert(DataValueDescriptor[] k)
		throws StandardException
	{
		int c;
		Node p, q, r, s, t;

		if (head.rightLink == null)
		{
			if ((sort.sortObserver != null) && 
				((k = sort.sortObserver.insertNonDuplicateKey(k)) == null))
			{
				return INSERT_DUPLICATE;
			}

			q = allocator.newNode();
			q.key = k;
			q.aux = nextAux;
			head.rightLink = q;
			height = 1;
			return INSERT_OK;
		}

		// [A1. Initialize]
		t = head;
		p = s = head.rightLink;

		// Search
		while (true)
		{
			// [A2. Compare]
			c = sort.compare(k, p.key);
			if (c == 0)
			{
				// The new key compares equal to the
				// current node's key.

				// See if we can use the aggregators
				// to get rid of the new key.
				if ((sort.sortObserver != null) &&
					((k = sort.sortObserver.insertDuplicateKey(k, p.key)) == null))
				{
					return INSERT_DUPLICATE;
				}

				// Keep the duplicate key...
				// Allocate a new node for the key.
				q = allocator.newNode();
				if (q == null)
					return INSERT_FULL;
				q.aux = nextAux;

				// Link the new node onto the current
				// node's duplicate chain.  The assumption
				// is made that a newly allocated node 
				// has null left and right links.
				q.key = k;
				q.dupChain = p.dupChain;
				p.dupChain = q;

				// From the caller's perspective this was
				// not a duplicate insertion.
				return INSERT_OK;
			}

			if (c < 0)
			{
				// [A3. Move left]
				q = p.leftLink;
				if (q == null)
				{
					q = allocator.newNode();
					if (q == null)
						return INSERT_FULL;
					q.aux = nextAux;
					p.leftLink = q;
					break;
				}
			}
			else // c > 0
			{
				// [A4. Move right]
				q = p.rightLink;
				if (q == null)
				{
					q = allocator.newNode();
					if (q == null)
						return INSERT_FULL;
					q.aux = nextAux;
					p.rightLink = q;
					break;
				}
			}

			if (q.balance != 0)
			{
				t = p;
				s = q;
			}
			p = q;
		}

		/*
		 * [A5. Insert]
		 * Node has been allocated and placed for k.
		 * Initialize it.
		 */

		if ((sort.sortObserver != null) && 
			((k = sort.sortObserver.insertNonDuplicateKey(k)) == null))
		{
			return INSERT_DUPLICATE;
		}
		q.key = k;

		/*
		 * [A6. Adjust balance factors for nodes between
		 * s and q]
		 */

		c = sort.compare(k, s.key);
		if (c < 0)
			r = p = s.leftLink;
		else
			r = p = s.rightLink;

		while (p != q)
		{
			if (sort.compare(k, p.key) < 0)
			{
				p.balance = -1;
				p = p.leftLink;
			}
			else // sort.compare(k, p.key) > 0
			{
				p.balance = 1;
				p = p.rightLink;
			}
		}

		// [A7. Balancing act]

		int a = (c > 0 ? 1 : ((c == 0) ? 0 : -1));

		if (s.balance == 0)
		{
			//debug("A7 (i). The tree has gotten higher");
			s.balance = a;
			height++;
			return INSERT_OK;
		}

		if (s.balance == -a)