/* ======================================================================
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.util;


import java.util.*;
import java.lang.ref.*;

import org.apache.log4j.Logger;

import org.bodington.database.PersistentObject;
import org.bodington.database.PrimaryKey;
import org.bodington.database.IndexKey;


/**
 * A cache that uses SoftReferences to eat up as much memory as is going.
 * @author buckett
 */
public class SoftCache implements java.lang.Runnable
	{
    
    private static Logger log = Logger.getLogger(SoftCache.class);
    
	private Thread cachechecker;
        private boolean destroyed = false;
	private int checkinterval;   //in seconds
	private String name;
	private int hit = 0;
	private int miss = 0;
    private int indexHit, indexMiss;

	private Hashtable   table,                  // SoftReference indexed by PrimaryKey
	                    reversetable,           // PrimaryKey indexed by SoftReference
	                    indextables,            // PrimaryKey indexed by IndexKey               (multiple tables)
	                    reverseindextables,     // IndexKey indexed by PrimaryKey               (multiple tables)
	                    nullindextables;        // Long (system time) indexed by IndexKey       (multiple tables)
	                    
	ReferenceQueue queue;                       // garbage collector puts defunct soft references in here
	


	public SoftCache( int checkevery )
	{
	    queue = new ReferenceQueue();
	    
	    table=new Hashtable( 50000 );
	    reversetable=new Hashtable( 50000 );
	    
	    indextables=new Hashtable();
	    reverseindextables=new Hashtable();
	    nullindextables=new Hashtable();
	    
	    checkinterval=checkevery;
	    cachechecker= new Thread( this, "SoftCache" );
	    // this is set as a daemon so it can easily be destroyed when the VM shuts down
	    // without a call to System.exit()
	    cachechecker.setDaemon( true );
	    name=cachechecker.toString();
	    cachechecker.start();
	    
	    log.info( "Current Heap Size: " + Runtime.getRuntime().totalMemory() );
	}

    public synchronized void destroy()
    {
        destroyed=true;
        if ( cachechecker != null && cachechecker.isAlive() )
            cachechecker.interrupt();
    }
        
    public synchronized void put( PrimaryKey key, PersistentObject value )
    	{
            if ( destroyed )
                throw new IllegalStateException( "SoftCache is destroyed" );
            
		//null key not acceptable
		//null value not acceptable
		if ( value==null || key==null ) return;

		remove( key );
		SoftReference entry = new SoftReference( value, queue );
	   	table.put( key, entry );
	   	reversetable.put( entry, key );
	   	
	   	
	   	// if this is a new or edited object there may be matching
	   	// indices that were cached but not matching before
	   	// these will be overwritten by the put method
	   	
	   	IndexKey[] ikeylist = value.getIndexKeys();  //relies on getIndexKeys() methods executing fast
	   	if ( ikeylist!=null )
	   	    {
	   	    for ( int i=0; i<ikeylist.length; i++ )
	   	        if ( ikeylist[i]!=null )
	   	            put( ikeylist[i], key );
	   	    }
	   	    
    	}


    private synchronized void put( IndexKey ikey, PrimaryKey pkey )
        {
            if ( destroyed )
                throw new IllegalStateException( "SoftCache is destroyed" );

        if ( ikey == null )
            return;
            
        //only cache index to null if allowed by index key
        if ( pkey==null && !ikey.cacheNull() )
            return;

        // only index non null objects that are in the cache
        if ( pkey!=null && !table.containsKey( pkey ) )
            return;
            
        // there is a separate hash table set for each class of index key
        // because an object may have multiple index keys of different types
        // (but never two index keys of the same type)
        Hashtable nitable = getNullIndexTable( ikey );

        if ( pkey==null )
            {
            nitable.put( ikey, new Long( System.currentTimeMillis() ) );
            
            // no need to look in itable for old keys because if was in the
            // cache and now the object has been deleted the delete method
            // will have called the remove method in the cache
            }
        else
            {
            Hashtable itable = getIndexTable( ikey );
            Hashtable ritable = getReverseIndexTable( ikey );
            
            itable.put( ikey, pkey );
            ritable.put( pkey, ikey );
            // if this is a brand new object it may have match an old
            // failed search - remove from that table.
            nitable.remove( ikey );
            }
        }


    /**
     * This caches the fact that there is no objects associated with this key.
     * @param ikey
     */
    public synchronized void put( IndexKey ikey )
        {
            if ( destroyed )
                throw new IllegalStateException( "SoftCache is destroyed" );
            
        //now w'ere in synch'ed code check there isn't now a
        //record against this index.
        PersistentObject pobj = get( ikey );
        if ( pobj!=null )
            return;
        
        // this ikey doesn't reference any record in the database or cache.
        put( ikey, null );
        }

    
    
    
    public synchronized PersistentObject get(PrimaryKey key)
    	{
            if ( destroyed )
                throw new IllegalStateException( "SoftCache is destroyed" );
            
		if ( key==null ) return null;

    	SoftReference entry=(SoftReference)table.get( key );

    	if ( entry !=null )
    	{
    	    hit++;
			return (PersistentObject)entry.get();
    	}
		miss++;
		return null;
    	}

    /**
     * @return <code>true</code> means not only that there isn't a matching
     *         object in the cache - it isn't in the data store either (it was
     *         checked earlier and no new or altered object matching the index
     *         key has been saved yet).
     */
    public synchronized boolean notExists( IndexKey ikey )
        {
            if ( destroyed )
                throw new IllegalStateException( "SoftCache is destroyed" );
        Hashtable nitable = getNullIndexTable( ikey );
        if ( nitable.containsKey( ikey ) )
            {
            // refresh timestamp
            nitable.put( ikey, new Long( System.currentTimeMillis() ) );
            return true;
            }
        return false;
        }

    public synchronized PersistentObject get( IndexKey ikey )
        {
            if ( destroyed )
                throw new IllegalStateException( "SoftCache is destroyed" );
            
        // returning null means that the object isn't in the cache
        // it may be in the data store despite this.
            
            if ( ! notExists( ikey ) )
            {
                PersistentObject obj;  
                PrimaryKey pkey = getPrimaryKey( ikey );
                if ( pkey != null )
                {            
                    obj = get( pkey );
                    if ( obj != null )
                    {
                        if ( obj.matchesKey( ikey ) )
                        {
                            indexHit++;
                            return obj;
                        }
                    }
                }
                // Only increment miss if we tried and failed to get it.
                indexMiss++;
            }
            return null;
        }
        
    private synchronized PrimaryKey getPrimaryKey( IndexKey ikey )
        {
            if ( destroyed )
                throw new IllegalStateException( "SoftCache is destroyed" );
            
        //get the hashtable
        Hashtable itable = getIndexTable( ikey );
        //return pkey from hashtable  (may be special nullpkey)
        return (PrimaryKey)itable.get( ikey );
        }


	public synchronized void remove( PrimaryKey key )
		{
            if ( destroyed )
                throw new IllegalStateException( "SoftCache is destroyed" );
            
		SoftReference entry=(SoftReference)table.get( key );
		if ( entry!=null )
			reversetable.remove( entry );
		table.remove( key );
		
		removeIndices( key );
		}


	private synchronized void removeIndices( PrimaryKey key )
		{
            if ( destroyed )
                throw new IllegalStateException( "SoftCache is destroyed" );
            
		Enumeration enumeration = reverseindextables.elements();
		Hashtable ritable, itable;
		IndexKey ikey;
		
		// check very type of index for this primary key
		// and erase from index and reverse index tables
		while ( enumeration.hasMoreElements() )
		    {
		    ritable = (Hashtable)enumeration.nextElement();
		    ikey = (IndexKey)ritable.get( key );
		    if ( ikey!= null )
    	        {
                itable = getIndexTable( ikey );
                itable.remove( ikey );
                ritable.remove( key );
		        }
		    
		    }
		}

	private synchronized void reportIndices()
		{
            if ( destroyed )
                throw new IllegalStateException( "SoftCache is destroyed" );
            
		Hashtable ritable, itable, nitable;
		IndexKey ikey;
		String indexclass;
		
		// check very type of index for this primary key
		// and erase from index and reverse index tables
		log.debug( "Soft Cache indices... (" + indextables.size() + ")" );

		Enumeration enumeration = indextables.keys();
		while ( enumeration.hasMoreElements() )
		    {
		    indexclass = (String)enumeration.nextElement();
		    log.debug( "Table of " + indexclass.toString() );

		    itable = (Hashtable)indextables.get( indexclass );
            if ( itable!=null )
    		    log.debug( "There are " + itable.size() + " elements in the index table" );

		    ritable = (Hashtable)reverseindextables.get( indexclass );
		    if ( ritable!=null )
		        log.debug( "There are " + ritable.size() + " elements in the reverse index table" );

		    nitable = (Hashtable)nullindextables.get( indexclass );
		    if ( nitable!=null )
		        log.debug( "There are " + nitable.size() + " elements in the null index table" );
		    }
		}

    public void run()
    	{
		int i, removed, nremoved=0, checkcount, checkdelay;
		PrimaryKey key;
		Reference entry;
		Object obj;

		for ( checkcount=0; !destroyed; checkcount++ )
			{
			if ( Runtime.getRuntime().freeMemory() < 10*1024*1024 )
			    checkdelay = 1;
			else
			    checkdelay = checkinterval;

			//do nowt for a bit
			try  { Thread.sleep( 1000*checkdelay ); }
			catch ( InterruptedException ex )
				{
				log.debug( "#" + name + "# Interrupted" );
                                if ( destroyed )
                                    return;
				}

			log.debug(  table.size() + " in table " + reversetable.size() + " in reversetable." );

			reportIndices();

			for ( removed=0; (entry=queue.poll()) !=null; removed++ )
				{

				synchronized (this )
					{
					key = (PrimaryKey)reversetable.get( entry );
					if ( key != null )
					    {
						table.remove( key );
						this.removeIndices( key );
						}
					reversetable.remove( entry );
					}

				Thread.yield();
				}

                if ( destroyed )
                    return;

            // check table of failed search indices and trim out old ones
            // check every 10 cycles
            nremoved=0;
            if ( (checkcount % 10) == 0 )
                {
    			log.debug( "checking null index keys" );
			    synchronized (this )
				    {
				    Long timestamp;
				    long now = System.currentTimeMillis();
				    Enumeration enumeration = nullindextables.elements();
				    Enumeration ikeyenum;
				    Hashtable nitable;
				    IndexKey ikey;
				    while ( enumeration.hasMoreElements() && nremoved < 1000 )
				        {
				        nitable = (Hashtable)enumeration.nextElement();
				        ikeyenum = nitable.keys();
				        while ( ikeyenum.hasMoreElements() )
				            {
				            ikey = (IndexKey)ikeyenum.nextElement();
				            timestamp = (Long) nitable.get( ikey );
				            // older than 3 minutes?
				            if ( now > (timestamp.longValue() + (3*60*1000)) )
				                {
				                // remove it from the table
				                nitable.remove( ikey );
				                nremoved++;
				                }
				            }
				        }
				    }
				}

            if (removed > 0 || nremoved > 0)
                log.debug( "removed entries: " + removed + " removed null indices: " + nremoved  );
			log.debug( "Free Heap Space " + Runtime.getRuntime().freeMemory() );
			
            if ( destroyed )
                return;
			
		    logUsage();
			log.debug("Ratio: PrimaryKeys "+ hit + "/" + (hit+miss)+
                " IndexKeys "+ indexHit+ "/" + (indexHit+indexMiss));
			
			}
    	}

	
	private synchronized void logUsage()
	{
	    Enumeration enumeration = table.elements();
	    Object obj;
	    SoftReference ref;
	    Hashtable counters = new Hashtable();
	    Counter count;
	    Class c;
	    
	    while ( enumeration.hasMoreElements() )
	    {
		ref = (SoftReference)enumeration.nextElement();
		obj = ref.get();
		if ( obj == null )
		    continue;
		c = obj.getClass();
		count = (Counter)counters.get( c );
		if ( count == null )
		{
		    count = new Counter();
		    counters.put( c, count );
		}
		count.increment();
	    }
	    
	    enumeration = counters.keys();
	    while( enumeration.hasMoreElements() )
	    {
		c = (Class)enumeration.nextElement();
		count = (Counter)counters.get( c );
		log.debug( "Usage " + c.getName() + " " + count.intValue() );
	    }
	}
	
	
	
    private Hashtable getIndexTable( IndexKey ikey )
        {
        // tables are keyed against the name of the class of IndexKey
        // so one Hashtable per type if IndexKey
        Hashtable table = (Hashtable)indextables.get( ikey.getClass().getName() );
        if ( table==null )
            {
            table = new Hashtable( 10000 );
            indextables.put( ikey.getClass().getName(), table );
            }
        return table;
        }


    private Hashtable getReverseIndexTable( IndexKey ikey )
        {
        // tables are keyed against the name of the class of IndexKey
        // so one Hashtable per type if IndexKey
        Hashtable table = (Hashtable)reverseindextables.get( ikey.getClass().getName() );
        if ( table==null )
            {
            table = new Hashtable( 10000 );
            reverseindextables.put( ikey.getClass().getName(), table );
            }
        return table;
        }


    private Hashtable getNullIndexTable( IndexKey ikey )
        {
        // tables are keyed against the name of the class of IndexKey
        // so one Hashtable per type if IndexKey
        Hashtable table = (Hashtable)nullindextables.get( ikey.getClass().getName() );
        if ( table==null )
            {
            table = new Hashtable( 10000 );
            nullindextables.put( ikey.getClass().getName(), table );
            }
        return table;
        }


	}