/* ======================================================================
The Bodington System Software License, Version 1.0
  
Copyright (c) 2001 The University of Leeds.  All rights reserved.
  
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

1.  Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.

2.  Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.

3.  The end-user documentation included with the redistribution, if any,
must include the following acknowledgement:  "This product includes
software developed by the University of Leeds
(http://www.bodington.org/)."  Alternately, this acknowledgement may
appear in the software itself, if and wherever such third-party
acknowledgements normally appear.

4.  The names "Bodington", "Nathan Bodington", "Bodington System",
"Bodington Open Source Project", and "The University of Leeds" must not be
used to endorse or promote products derived from this software without
prior written permission. For written permission, please contact
d.gardner@leeds.ac.uk.

5.  The name "Bodington" may not appear in the name of products derived
from this software without prior written permission of the University of
Leeds.

THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
WARRANTIES, INCLUDING, BUT NOT LIMITED TO,  TITLE,  THE IMPLIED WARRANTIES 
OF QUALITY  AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO 
EVENT SHALL THE UNIVERSITY OF LEEDS OR ITS CONTRIBUTORS BE LIABLE FOR 
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 
GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
POSSIBILITY OF SUCH DAMAGE.
=========================================================

This software was originally created by the University of Leeds and may contain voluntary 
contributions from others.  For more information on the Bodington Open Source Project, please 
see http://bodington.org/

====================================================================== */
package org.bodington.pool;

import java.util.Hashtable;


/**
 * This is a thread safe class used to implement a pool of some type of
 * limited availability resourse, for example a database connection pool.
 * It is possible to indicate an owner when claiming a resource and
 * configure usage limits per user.
 * To make good use of this class it should be subclassed and the
 * subclass is likely to override the methods createObject,
 * initialiseObject and poolObject.  Code in this class in the methods
 * getObject and freeObject will guarantee that for a particular slot 
 * in the pool those three methods can only be called by one thread at
 * a time.
 * The synchronized blocks in this class don't do anything that might
 * cause exceptions or errors.  They consist of simple
 * equality checks, assignments and arithmetic on primitive
 * data types or object references.  This is a design principle that
 * should be preserved in future versions.
 * Callers of getObject are entirely responsible for calling freeObject
 * at a later time.  A good way to do this is to put the getObject call
 * inside a try clause and the freeObject call inside the finally clause.
 * Code should be careful to match one call of getObject with one call
 * of freeObject and make sure the correct object reference is used.
 * @author Jon Maber
 */
public class ObjectPool
	{

	/**
	 * The status of slots that are available to be claimed.
	 */
	public static final int STATUS_IDLE		=0;

	/**
	 * The status of slots that have been claimed and are in use.
	 */
	public static final int STATUS_BUSY		=1;

	/**
	 * The status of slots that are moving from busy to idle.
	 */
	public static final int STATUS_FREEING	=2;

	/**
	 * The status of slots that are moving from idle to busy.
	 */
	public static final int STATUS_GETTING	=3;
	
	
	Object[] pool;					// the objects in the pool, one slot each
	Object[] slot_owner;			// each slot can record an owner object
	Hashtable owner_data;			// information about each recorded owner hashed on owner
	

	int[] status;					// status inidicator for each slot.  This is always
									// accessed in synchronized code.
									
	//int timeout;
	int free_spaces;				// keeps track of number of slots free.
									// updated in synchronized code.
	
	int default_normal_timeout;		// set in initialise() can be overidden
	int default_greedy_timeout;		// set in initialise() can be overidden
	int default_owner_max;			// set in initialise() can be overidden
	int default_greedy_max;                 // set in initialise()
	
	/**
	 * The default constructor leaves the pool uninitialised.  A subclass
	 * constructor calling this constructor will have to call init() after.
	 */
	protected ObjectPool()
		{
		pool=null;			// indicates that pool isn't initialised
		}
		
	/**
	 * This constructor will initialise the pool.
	 * 
	 * @param size The number of slots in the pool.  Once initialised the size of the
	 * pool is fixed.
	 * @param owner_max The default maximum number of slots that will be allocated to each 
	 * owner.  Doesn't apply if no owner is specified when claiming a slot.
	 * @param timeout The default time to wait for a free slot when one is requested and 
	 * there are none free.
	 * @param greedy_timeout The default time to wait when an owner has exceeded its limit of
	 * slots.
	 * @exception org.bodington.pool.ObjectPoolException Thrown if there is a problem 
	 * initialising the pool.
	 */
	public ObjectPool( int size, int owner_max, int timeout, int greedy_timeout )
		throws ObjectPoolException
		{
		init( size, owner_max, timeout, greedy_timeout );
		}
		
	/**
	 * This constructor will initialise the pool.
	 * 
	 * @param size The number of slots in the pool.  Once initialised the size of the
	 * pool is fixed.
	 * @param owner_max The default maximum number of slots that will be allocated to each 
	 * owner.  Doesn't apply if no owner is specified when claiming a slot.
	 * @param timeout The default time to wait for a free slot when one is requested and 
	 * there are none free.
	 * @param greedy_max The default max number of queued requests for an owner.
	 * @param greedy_timeout The default time to wait when an owner has exceeded its limit of
	 * slots.
	 * @exception org.bodington.pool.ObjectPoolException Thrown if there is a problem 
	 * initialising the pool.
	 */
	public ObjectPool( int size, int owner_max, int timeout, int greedy_max, int greedy_timeout )
		throws ObjectPoolException
		{
		init( size, owner_max, timeout, greedy_max, greedy_timeout );
		}
		
	/**
	 * Called once by subclass constructor to initialise the pool.  Should not be
	 * called at any other time.
	 * 
	 * @param size
	 * @param owner_max
	 * @param timeout
	 * @param greedy_timeout
	 * @exception org.bodington.pool.ObjectPoolException Thrown if there is a problem 
	 * initialising the pool.
	 */
	protected void init( int size, int owner_max, int timeout, int greedy_timeout )
		throws ObjectPoolException
		{
                    // uses 2 as default default greedy max.
                    init( size, owner_max, timeout, 2, greedy_timeout );
                }
        
	/**
	 * Called once by subclass constructor to initialise the pool.  Should not be
	 * called at any other time.
	 * 
	 * @param size
	 * @param owner_max
	 * @param timeout
	 * @param greedy_max
	 * @param greedy_timeout
	 * @exception org.bodington.pool.ObjectPoolException Thrown if there is a problem 
	 * initialising the pool.
	 */
	protected void init( int size, int owner_max, int timeout, int greedy_max, int greedy_timeout )
		throws ObjectPoolException
		{
		default_owner_max = owner_max;
		default_normal_timeout = timeout;
		default_greedy_timeout = greedy_timeout;
		default_greedy_max = greedy_max;
		
		
		status = new int[size];
		pool = new Object[size];
		slot_owner = new Object[size];
		owner_data = new Hashtable( size );
		
		try
			{
			for ( int i=0; i<size; i++ )
				{
				status[i] = STATUS_IDLE;
				pool[i] = createObject();
				}
			}
		catch ( Exception ex )
			{
			throw new ObjectPoolException( 
				ObjectPoolException.REASON_CREATE_OBJECT_FAILED, 
				ex, 
				"Failed to construct ObjectPool." );
			}
			
		free_spaces = size;
		}
	
	/**
	 * For a given indexed slot gives the status of the slot.
	 * 
	 * @param i Index of the slot to examine.
	 * @return An int value indicating status.  Possible values are indicate by the
	 * static fields STATUS_*.
	 */
	public int getSlotStatus( int i )
		{
		if ( i<0 || i > pool.length )
			throw new ArrayIndexOutOfBoundsException( i );
		
		// synchronize block means we wait in case another thread is
		// changing the status
		synchronized ( this )
			{
			return status[i];
			}
		}

	/**
	 * For a given slot return a descriptive message indicating its status.
	 * 
	 * @param i Index of the slot.
	 * @return A textual description of the status.
	 */
	public String getSlotStatusMessage( int i )
		{
		if ( i<0 || i > pool.length )
			throw new ArrayIndexOutOfBoundsException( i );
		
		// synchronize block means we wait in case another thread is
		// changing the status
		synchronized ( this )
			{
			// this will use the toString() method of the owner object
			return " : " + status[i] + " owner: " + slot_owner[i];
			}
		}

	
	
	/**
	 * Claim a slot in the pool using the full range of optional parameters.
	 * 
	 * @param owner An object that indicates the owner.  When counting slots that
	 * have already been claimed by this owner the equals() method of the
	 * owner object will be used to compare it to the recorded owners 
	 * of those slots.
	 * @param max The maximum number of slots to allow this owner.
	 * @param timeout The timeout to use if no slots are free.
	 * @param greedy_timeout The timeout to use if this owner has used its maximum number
	 * of claimed slots.  However, if this owner has a number of other
	 * requests queued up this call will fail immediately.
	 * @return An initialised object from the pool.  Literally an instance of
	 * the class Object unless this ObjectPool is subclassed.
	 * @exception org.bodington.pool.ObjectPoolException Thrown if the caller is denied an object from the pool or if a
	 * problem occurs initialising the object that was to be given.
	 */
	public final Object getObject( Object owner, int max, int timeout, int greedy_timeout )
		throws ObjectPoolException
		{
		int i, n;
		long started_looking = System.currentTimeMillis();
		long now;
		boolean maxed = false;
		ObjectPoolOwnerData owner_datum=null;
		boolean inited=false;
		Object fresh_object;
                int effective_timeout;
		
		if ( pool == null )
			throw new ObjectPoolException( ObjectPoolException.REASON_NOT_INITIALISED, null,
				"The Object Pool is not initialised." );
		
		if ( owner!=null && max >= 0 )
			{
			// synchronize block means we wait in case another thread is
			// changing or examining owner information
			synchronized ( this )
				{
				// has the owner got object already?
				owner_datum = (ObjectPoolOwnerData)owner_data.get( owner );
				// if not set up a new record
				if ( owner_datum == null )
					{
					owner_datum = new ObjectPoolOwnerData();
					owner_datum.n = 0;
					owner_data.put( owner, owner_datum );
					}
				// guaranteed count of how many calls to this method
				// are outstanding for this owner - just entered 
				// this thread so increment it.
				owner_datum.getting++;
				}
			}
		
		
		try
			{
			// if this owner has claimed too many objects and/or has made many
			// requests that are still outstanding immediately reject this request
			// without even looking for a free slot
			if ( owner_datum != null && 
					(owner_datum.getting + owner_datum.n) > (max + default_greedy_max ) )
				{
				// refine the type of exception depending on whether the total
				// number of checked out objects has been reached or if the user
				// has clocked up too many pending requests.
				maxed = owner_datum != null && owner_datum.n >= max;
				if ( maxed ) 
					throw new ObjectPoolException( 
						ObjectPoolException.REASON_MAX_OBJECTS_AND_REQUESTS,
						null,
						"Maximum objects and object requests for owner exceeded. (" + owner.toString() +")" );
				else
					throw new ObjectPoolException( 
						ObjectPoolException.REASON_MAX_REQUESTS,
						null,
						"Maximum queued object requests for owner exceeded. (" + owner.toString() +")" );
				}

                        // different timeout depending on if we wait for this owner to
                        // to release an object or other owners.
                        effective_timeout = (owner_datum==null || owner_datum.n < max)?timeout:greedy_timeout;
                        
			//  not an endless loop - there is a timeout check at the bottom.
			//  all slots are repeatedly checked until timeout condition or
			//  some exception is thrown
			while ( true )
				{
				// don't check the slots if maxed out - go straight to
				// deciding whether to time out or not
				maxed = owner_datum != null && owner_datum.n >= max;
				
				// check slots from bottom to top for one that is free
				// multiple calls to this method can work up the list
				// simultaneously but when one thread picks out a particular
				// slot to use other threads will skip over that slot
				// because the status is changed for that slot
				for ( i=0; i<pool.length && !maxed; i++ )
					{
					// synchronized block means we wait in case another thread is
					// changing/examining the status or owner information.
					// This synchronized block doesn't call anything that might
					// cause exceptions or errors.  It consists of simple
					// equality checks, assignments and arithmatic on primative
					// data types.
					synchronized ( this )
						{
						// only idle slots are of interest - in particular
						// if another thread has already decided to prepare
						// this slot for use its status will have changed to
						// STATUS_GETTING.
						if ( status[i] != STATUS_IDLE )
							continue;

						// repeat the maxed out test on every loop
						// where a slot is available.  This is because another
						// thread may have caused a maxed out situation
						// recently
						maxed = owner_datum != null && owner_datum.n >= max;
						if ( maxed ) break;
						
						// while still blocking other threads claim this slot
						status[i] = STATUS_GETTING;
						// now determined to give this slot to caller
						
						if ( owner_datum != null )
							{
							// must increment count while all other threads blocked
							owner_datum.n++;
							// record who has claimed the slot
							slot_owner[i] = owner;
							}
							
						// keep track of how many slots are now free
						free_spaces--;
						}

						
					try
						{
						// this is here in case the initialise() method is 
						// rewritten not to create an object for each slot.
						// This is currently redundant.
						if ( pool[i] == null )
							pool[i] = createObject();
							
						// Prepare object for use by caller - most likely
						// that this method will be overridden in useful
						// subclasses of ObjectPool.
						fresh_object = initialiseObject( pool[i] );
						// It is possible that the pooled object was rejected
						// and a new instance created during this preparation
						// so the new instance must be referenced in the pool.
						if ( fresh_object != pool[i] )
							pool[i] = fresh_object;
						// indicate that the object is properly initialised
						// to help decide what to do in the finally clause
						// below.
						inited=true;
						}
					catch ( Exception ex )
						{
						// Subclasses of ObjectPool could throw all sorts of
						// exception in the initialiseObject method.  Here
						// an ObjectPoolException is constructed and thrown
						// based on the original exception.
						throw new ObjectPoolException(
							ObjectPoolException.REASON_INIT_OBJECT_FAILED,
							ex,
							"Unable to initialise Object in Pool." );
						}
					finally  // this clause MUST execute regardless of exceptions
						{
						// synchronize block means we wait in case another thread is
						// changing the status
						synchronized ( this )
							{
							// Either mark the slot as busy or return it to the
							// pool of idle slots depending on whether initialisation
							// of the object was completed.
							if ( inited )
								status[i] = STATUS_BUSY;	
							else
								status[i] = STATUS_IDLE;
							}
						}
						
					// if no exception was thrown return the object
					return pool[i];
					}
					

				// All slots were examined or the owner reached the maximum slots.

					
				// synchronize block is required so that wait knows
				// which object to monitor for calls to notify() or notifyAll()
				synchronized ( this )
					{
					// This loop will make the thread continue to wait until it
					// it is appropriate to search slots again or timeout.
					do
						{
						// Decide whether to throw an exception now because the search has
						// gone on long enough or whether to go into wait state
						now = System.currentTimeMillis();
						if ( effective_timeout == 0 || 
								(effective_timeout>0 && (now-started_looking) > effective_timeout) )
							{
							if ( maxed )
								throw new ObjectPoolException( 
									ObjectPoolException.REASON_MAX_OBJECTS,
									null,
									"Maximum objects for owner exceeded. (" + owner.toString() +")" );
							else
								throw new ObjectPoolException( 
									ObjectPoolException.REASON_TIMEOUT,
									null,
									"Timeout." );
							}

						try
							{
							// decide on how long to wait
							// This is the only place to call wait() in this class
							
							// A limited wait is required to implement a responsive timeout.
							// If user is maxed there is probably also a timeout to check.
							if ( effective_timeout>0 )
								wait( effective_timeout - (now - started_looking) );
							// if there is no timeout the thread should wait until
							// another thread calls freeObject() and there may be a 
							// thread free.
							else
								wait();
							}
						catch ( InterruptedException iex )
							{
							}
						// thread is running again because either the wait timed out
						// of its own accord or it was woken up by the notifyAll call
						// in freeObject()
						}
					// no point going around main loop again if there are
					// no slots available.  Check the timeout and maybe go back to waiting.
					while ( free_spaces == 0 );
					}
				// escaped the waiting/ timeout check cycle so reading to look for
				// idle slots now.
				}		
			}
		finally  // absolutely must run this code before exiting method
			{
			if ( owner_datum!=null )
				{
				// guaranteed count of how many calls to this method
				// are outstanding for this owner - about to return on 
				// this thread so decrement it.
				synchronized ( this )
					{
					owner_datum.getting--;
					}
				}
			}

		}

	/**
	 * This get method will assume default values for timeouts and
	 * does not indicate an owner.
	 * 
	 * @exception org.bodington.pool.ObjectPoolException Thrown if the caller is denied an object from the pool or if a
	 * problem occurs initialising the object that was to be given.
	 */
	public Object getObject()
		throws ObjectPoolException
		{
		return getObject( null, -1, default_normal_timeout, default_greedy_timeout );
		}
		
	/**
	 * Specifies only the timeout to use and does not indicate an
	 * owner.
	 * 
	 * @param timeout The timeout to use if no slots are free.
	 * @exception org.bodington.pool.ObjectPoolException Thrown if the caller is denied an object from the pool or if a
	 * problem occurs initialising the object that was to be given.
	 */
	public Object getObject( int timeout )
		throws ObjectPoolException
		{
		return getObject( null, -1, timeout, default_greedy_timeout );
		}
		
	/**
	 * Indicates the owner but uses default maximum slots and default
	 * timeouts.
	 * 
	 * @param owner An object that indicates the owner.  When counting slots that
	 * have already been claimed by this owner the equals() method of the
	 * owner object will be used to compare it to the recorded owners 
	 * of those slots.
	 * @exception org.bodington.pool.ObjectPoolException Thrown if the caller is denied an object from the pool or if a
	 * problem occurs initialising the object that was to be given.
	 */
	public Object getObject( Object owner )
		throws ObjectPoolException
		{
		return getObject( owner, default_owner_max, default_normal_timeout, default_greedy_timeout );
		}
		
	/**
	 * Indicates owner, maximum number of slots for the owner but
	 * default timeouts are used.
	 * 
	 * @param owner An object that indicates the owner.  When counting slots that
	 * have already been claimed by this owner the equals() method of the
	 * owner object will be used to compare it to the recorded owners 
	 * of those slots.
	 * @param max The maximum number of slots to allow this owner.
	 * @exception org.bodington.pool.ObjectPoolException Thrown if the caller is denied an object from the pool or if a
	 * problem occurs initialising the object that was to be given.
	 */
	public Object getObject( Object owner, int max )
		throws ObjectPoolException
		{
		return getObject( owner, max, default_normal_timeout, default_greedy_timeout );
		}
		
	/**
	 * Frees a slot in the pool that was previously claimed.
	 * 
	 * @param o The object that was returned by the getObject() method earlier.
	 * @exception org.bodington.pool.ObjectPoolException Thrown if there is a problem freeing the object.
	 */
	public void freeObject( Object o )
		throws ObjectPoolException
		{
		int i;
		ObjectPoolOwnerData owner_datum;
		
		if ( pool == null )
			throw new ObjectPoolException( ObjectPoolException.REASON_NOT_INITIALISED, null,
				"The Object Pool is not initialised." );

		// This loop could be avoided using a hashtable for example
		// but hashtables aren't thread safe so better to stick to
		// simpler code that allows other threads to work in the 
		// pool at the same time.
		for ( i=0; i<pool.length; i++ )
			{
			
			// This block is synchronized so it better avoid anything
			// time consuming or capable of going wrong.
			synchronized ( this )
				{
				//  looking for the busy slot
				if ( status[i] != STATUS_BUSY )
					continue;
					
				//  looking for a slot with something in it
				if ( pool[i] == null )
					continue;

				// looking for the slot that has this specific
				// object in it.
				if ( !pool[i].equals( o ) )
					continue;
				
				// indicate that it is in the process of being
				// returned to the pool.
				status[i] = STATUS_FREEING;	

				//committed to free this slot.
				
				// If there is an owner for this object update owner data.
				if ( slot_owner[i] != null )
					{
					owner_datum = (ObjectPoolOwnerData)owner_data.get( slot_owner[i] );
					if ( owner_datum!= null )
						{
						// decrement the count of slots this owner is using
						owner_datum.n--;
						// if this was the last slot owned and there are no outstanding
						// requests for objects from the owner tidy up the hashtable
						// by removing this owner.
						if ( owner_datum.n == 0 && owner_datum.getting == 0 )
							owner_data.remove( slot_owner[i] );
						}
					// clear the record of this slot owner.
					slot_owner[i] = null;
					}
				}

			// The code that cleans up the object is not synchronized.
			try
				{
				// In ObjectPool this does nothing but subclasses could do
				// useful stuff here.
				poolObject( pool[i] );
				}
			catch ( Exception ex )
				{
				// All sorts of exception could be thrown in subclasses
				throw new ObjectPoolException(
					ObjectPoolException.REASON_INIT_OBJECT_FAILED,
					ex,
					"Unable to prepare Object for return to Pool." );
				}
			finally  // must guarantee that this is called despite exceptions
				{
				synchronized ( this )
					{
					// return the slot to the pool
					status[i] = STATUS_IDLE;
					// update free spaces count
					free_spaces++;
					// wake up waiting threads - must wake up all of them because
					// the rate of calls to getObject() can be faster than calls
					// to freeObject() and some threads could be waiting forever.
					// Some woken threads may go straight back to waiting.
					notifyAll();
					}
				}
			
			return;
			}
			
		throw new ObjectPoolException(
			ObjectPoolException.REASON_INVALID_OBJECT,
			null,
			"Cannot free object from pool - it isn't in there." );
		}
		
	/**
	 * This method instantiates an object of class Object.  A
	 * subclass should override this method to instantiate an
	 * object of the appropriate class.
	 * 
	 * @return An object to place in the pool.
	 * @exception java.lang.Exception Any type of exception could be thrown.
	 */
	protected Object createObject()
		throws Exception
		{
		return new Object();
		}
		
	/**
	 * In ObjectPool this method does nothing but return the same
	 * object that was passed in but subclasses would overide this
	 * method and use it to prepare the object for use.  It is
	 * called from getObject().  If the object cannot be prepared
	 * for use this method can instantiate and prepare for use a
	 * new object - the return object need not be the same one that
	 * was passed as a parameter.
	 * 
	 * @param o The object to be prepared for use passed in by the getObject method.
	 * @return The object from the pool, ready for use.
	 * @exception java.lang.Exception Any type of exception could be thrown.
	 */
	protected Object initialiseObject( Object o )
		throws Exception
		{
		return o;
		}
		
	/**
	 * In ObjectPool this method does nothing.  Subclasses
	 * of ObjectPool override this method to "clean up" the
	 * object just before it is returned to the pool.
	 * 
	 * @param o The object that is being returned to the pool of available
	 * objects.
	 * @exception java.lang.Exception Any type of exception could be thrown.
	 */
	protected void poolObject( Object o )
		throws Exception
		{
		}
	}