/*
 * 
 * Copyright 2004 Sun Microsystems, Inc. All Rights Reserved.
 * 
 * The contents of this file are subject to the Sun Community Source
 * License v3.0/Jini Technology Specific Attachment v 1.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://wwws.sun.com/software/jini/licensing/SCSL3_JiniTSA1.html.
 * Software distributed under the License is distributed on an "AS IS"
 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
 * the License for the specific language governing rights and limitations
 * under the License.
 * 
 * The Reference Code is Jini Technology Core Platform code, v2.0. The
 * Developer of the Reference Code is Sun Microsystems, Inc.
 * 
 * Contributor(s): Sun Microsystems, Inc.
 * 
 * The contents of this file comply with the Jini Technology Core
 * Platform Compatibility Kit, v2.0A.
 * 
 * Tester(s): Sun Microsystems, Inc.
 * 
 * Test Platform(s):
 * Java 2 SDK, Standard Edition, Version 1.4.2_03 for Solaris(TM)SPARC/x86
 * Java 2 SDK, Standard Edition, Version 1.4.2_03 for Linux (Intel x86)
 * Java 2 SDK, Standard Edition, Version 1.4.2_03 for Windows (Intel Platform)
 * 
 */
package com.sun.jini.outrigger;

import java.util.Hashtable;
import java.util.Set;
import java.util.logging.Level;
import java.util.logging.Logger;

import net.jini.core.entry.UnusableEntryException;
import net.jini.core.transaction.CannotJoinException;
import net.jini.core.transaction.server.TransactionConstants;

/**
 * <code>EntryHolder</code>s hold all the entries of a exact given
 * class. <code>OutriggerServerImpl</code> has one
 * <code>EntryHolder</code> for each entry class it knows about. A
 * simple implementation is used that simply stores the entries in a
 * list.
 *
 * @author Sun Microsystems, Inc.
 */
class EntryHolder implements TransactionConstants {
    /** The list that holds the handles */
    private final FastList contents = new FastList();

    /** 
     * The map of cookies to handles, shared with the
     * <code>EntryHolderSet</code> and every other
     * <code>EntryHolder</code>.  
     */
    private final Hashtable idMap;

    /** The server we are working for */
    private final OutriggerServerImpl space;

    /** Logger for logging information about entry matching */
    private static final Logger matchingLogger = 
	Logger.getLogger(OutriggerServerImpl.matchingLoggerName);

    /** Logger for logging information about iterators */
    private static final Logger iteratorLogger =
	Logger.getLogger(OutriggerServerImpl.iteratorLoggerName);

    /**
     * Create a new <code>EntryHolder</code> with the shared
     * <code>idMap</code>, and which will hold classes of the given
     * <code>className</code>.  The <code>idMap</code> is shared with
     * <code>EntryHolderSet</code> so that there is one table that can
     * map ID to <code>EntryRep</code>
     */
    EntryHolder(OutriggerServerImpl space, Hashtable idMap) {
	this.space = space;
	this.idMap = idMap;
    }

    /**
     * Return an <code>EntryRep</code> object that matches the given
     * template, or <code>null</code> if none does. Optionally
     * removes the found entry. If the entry is removed, the removal
     * will be logged to the store.
     *
     * @param tmplRep	The template to match against
     * @param txnMgr    If non-null the transaction (represented as 
     *                  a <code>TransactableMgr</code> to perform
     *                  the operation under. May be <code>null</code>
     *                  if the operation is not to be done under
     *                  a transaction.
     * @param takeIt	<code>true</code> if <code>hasMatch</code> should
     *			remove the matching entry.
     * @param conflictSet If non-null the <code>TransactableMgr</code>
     *                  objects of any transactions that prevent 
     *                  a non-null value from being retured will
     *                  be added to <code>conflictSet</code>. May
     *                  be <code>null</code> in which case
     *                  conflicting transaction will not be recorded.
     *                  This method assumes that any concurrent access
     *                  is being arbitrated by the set or by the caller.
     * @param lockedEntrySet If non-null the ID of any entries that
     *                  can't be retured because of conflicting
     *                  transaction will be added to
     *                  <code>lockedEntrySet</code>. May be
     *                  <code>null</code> in which case unavailable
     *                  entries will not be recorded.  This method 
     *                  assumes that any concurrent access is being
     *                  arbitrated by the set or by the caller.
     * @throws CannotJoinException if a match is found and
     *         the operation is to be performed under a transaction,
     *         but the transaction is no longer active.
     * @see #attemptCapture 
     */
    EntryRep hasMatch(EntryRep tmpl, TransactableMgr txn, boolean takeIt,
		      Set conflictSet, Set lockedEntrySet)
	throws CannotJoinException
    {
	matchingLogger.entering("EntryHolder", "hasMatch");

	EntryHandle handle = (EntryHandle) contents.head();
	if (handle == null)
	    return null;     // Nothing here

	final EntryHandleTmplDesc desc = 
	    EntryHandle.descFor(tmpl, handle.rep().numFields());
	final long startTime = System.currentTimeMillis();

	for (;handle != null; handle = (EntryHandle) handle.next()) {
	    if (handle.removed())
		continue;

	    // Quick reject -- see the if handle mask is incompatible
	    if ((handle.hash() & desc.mask) != desc.hash)
		continue;

	    final EntryRep rep = handle.rep();

	    if (!tmpl.matches(rep))
		continue;
		    
	    final EntryRep result =
		confirmAvailabilityWithTxn(rep, handle, txn, 
		    takeIt, startTime, conflictSet, lockedEntrySet);

	    if (result != null)
		return result;
	}

	return null;
    }

    /**
     * Debug method:  Dump out the state of this holder, printing out
     * the name of the dump first.
     */
    void dump(String name) {
	try {
	    System.out.println(name);
	    for (EntryHandle handle = (EntryHandle) contents.head();
		 handle != null;
		 handle = (EntryHandle) handle.next())
	    {
		EntryRep rep = handle.rep();
		System.out.println("    " + rep + ", " + rep.entry());
	    }
	} catch (UnusableEntryException e) {
	    e.printStackTrace();
	}
    }

    /**
     * Atomically check to see if the passed entry can be read/taken by
     * the specified operation using the specified transaction and if
     * it can read/take it and return <code>true</code>, otherwise
     * return <code>false</code>. If the entry is removed, the removal
     * will be logged to the store.
     * @param entry The <code>EntryHandle</code> of the entry
     *              the caller wants to read/take.
     * @param txn   If non-null the transaction to perform
     *              this operation under. Note, if non-null and 
     *              <code>txn</code> is not active <code>false</code>
     *              will be returned.
     * @param takeIt <code>true</code> if the caller is trying
     *              take the passed entry, <code>false</code>
     *              otherwise.
     * @param conflictSet If non-null and the entry can not be
     *              read/taken because of transaction conflicts the
     *              conflicting transaction(s) will be added to this set.
     *              This method assumes that any concurrent access is
     *              being arbitrated by the set or by the caller.
     * @param lockedEntrySet If the entry can not be read/taken
     *              because of a transaction conflict, the ID of the
     *              entry will be added to this set. This method
     *              assumes that any concurrent access is being arbitrated
     *              by the set or by the caller.
     * @param now an estimate of the current time in milliseconds
     *            since the beginning of the epoch.
     * @return <code>true</code> if the entry could be read/taken and
     *         <code>false</code> otherwise.
     * @throws NullPointerException if entry is <code>null</code>.
     */
    boolean attemptCapture(EntryHandle handle, TransactableMgr txn,
	boolean takeIt, Set conflictSet, Set lockedEntrySet, long now)
    {
	try {
	    return null != confirmAvailabilityWithTxn(handle.rep(), handle,
		txn, takeIt, now, conflictSet, lockedEntrySet);
	} catch (CannotJoinException e) {
	    return false;
	}
    }

    /* Now that we know we have a match, make sure that the the
     * item in question is still in the space and hasn't been
     * subject to other transactional-interference...
     */
    private EntryRep confirmAvailabilityWithTxn(EntryRep rep, 
	      EntryHandle handle, TransactableMgr txnMgr, boolean takeIt, 
	      long time, Set conflictSet, Set lockedEntrySet)
	throws CannotJoinException
    {
	// Now that we know we have a match, make sure that the the
	// item in question is still in the space and hasn't been
	// subject to other transactional-interference...

	// Lock the txn first (since that what everybody else does that)
	// to ensure that the locking always happens in A cannonical
	// order. We lock the transaction (txn) object to ensure that the
	// transaction hasn't been altered behind our backs. Other, cheaper
	// actions with the space (write, etc.) are handled nicely in 
	// OutriggerServerImpl. But, this one (reading/taking) was expensive
	// enough that we wanted to do it here, where the window is
	// smallest.
	// Bug 4394263...
	
	final Txn txn = (Txn)txnMgr;
	try {
	    if (txn != null) 
		txn.ensureActive();

	    final EntryRep rslt = confirmAvailability(rep, handle, txn,
		takeIt, time, conflictSet, lockedEntrySet);

	    if (takeIt && rslt != null)
		space.takeOp(rslt, txn);
	    
	    return rslt; 
	} finally {
	    if (txn != null) 
		txn.allowStateChange();
	}
    }

    /**
     * With the EntryRep <code>rep</code> passed in, verify that the
     * entry hasn't been taken by someone else, hasn't expired, etc.
     * Also, verify that the entry is really (legally) visible to this
     * transaction at this time. If this is a <code>take</code>, it
     * it is removed. If this operation is under a transaction, the
     * entry is locked appropriately.
     * @see grab -- a helper routine
     */
    private EntryRep
	confirmAvailability(EntryRep rep, EntryHandle handle,
	      TransactableMgr txn, boolean takeIt, long time,
	      Set conflictSet, Set lockedEntrySet)
    {
	if (handle.removed())
	    return null;

	synchronized (handle) {
	    // get rid of stale entries
	    if (isExpired(time, handle))
		return null;
	    if (handle.removed())    // oh, well -- someone got it first
		return null;
	    int op = (takeIt ? TransactableMgr.TAKE : TransactableMgr.READ);
	    if (!handle.canPerform(txn, op)) {
		// Before deciding this is a conflict, we have to
		// make sure we are not conflicting with ourselves.
		if (handle.onlyMgr(txn))
		    // We are just conflicting with ourselves, this entry
		    // must have been taken by this txn already ... oh well
		    return null;
	       
		// Must be a real conflict, log if we were told too
		if (matchingLogger.isLoggable(Level.FINER)) {
		    matchingLogger.log(Level.FINER, "match, but can''t " +
			"perform {0}; handle.knownMgr(txn) == {1}", 
			new Object[] {new Integer(op), 
				      new Boolean(handle.knownMgr(txn))});
		}

		if (conflictSet != null) {
		    handle.addTxns(conflictSet);
		} 

		if (lockedEntrySet != null) {
		    lockedEntrySet.add(rep.id());
		}

		return null;
	    }

	    if (grab(handle, txn, op, takeIt, false))
		return rep;

	    return null;
	}
    }

    /**
     * Given an entry that we want to return as the result of a query
     * and we have confirmed we can return it, make the results of the
     * query visible to the rest of the service. We must either [a] remove
     * it from the holder (if the operation is a take without a transaction
     * or a take under the same transaction the entry was written under), 
     * [b] lock it under the transaction passed into this method (if 
     * the operation is a read or take under a transaction), or [c]
     * do nothing (read not under a transaction) as appropriate.
     * <p>
     * Also used during log recovery to recover takes.
     *
     * @param handle The handle attached to the particular EntryRep
     * @param txn The Txn object
     * @param op TAKE or READ (as a TransactableMgr constant)
     * @param takeIt Is this a TAKE (or is it [false] a READ)
     * @param recovery <code>true</code> if being called as
     *        part of store recovery.
     * @return <code>true</code> if the entry could be grabbed.
     * @throws NullPointerException if <code>handle</code> is
     *         <code>null</code>.
     */
    private boolean grab(EntryHandle handle, TransactableMgr txn, int op,
			 boolean takeIt, boolean recovery)
    {
	assert op==(takeIt?TransactableMgr.TAKE:TransactableMgr.READ);
	assert !recovery || takeIt;

	/*
	 * If this manager (txn) is known to the handle, then txn
	 * is a transaction which can operate directly on the
	 * existing handle.  If so, then we can operate on it
	 * directly.  Note that if txn is null and the handle is
	 * not managed, then txn is "known" in this sense.
	 *
	 * Else, this operation is new relative to the
	 * known transactions (possibly null) and txn.  
	 */

	if (handle.knownMgr(txn)) {    // added or read in this txn if taking
	    // take it if we have to (otherwise it must be a read
	    // there is no house keeping to be done)

	    if (takeIt) {
		// is this an entry that was written under this
		// transaction or another?

		if (handle.managed()) {
		    // It is locked by a transaction and it must
		    // be the one this take is under.

		    if (!handle.promoteToTakeIfNeeded()) {
			// this transaction wrote the entry ("this
			// transaction" maybe the null
			// transaction), just need to try and
			// remove it

			if (!remove(handle, recovery)) 
			    // Someone got to it first
			    return false;
		    }

		    // Otherwise it was read locked (now take
		    // locked and needs to still be semi-visible
		    // to ifExists queries outside of the
		    // transaction, leave it in place with its new
		    // lock type (aka "state")

		} else {
		    // Nether the entry nor this take are under a
		    // transaction (txn must be null because the
		    // that is the only way knownMgr return true, and
		    // managed() false)

		    if (!remove(handle, recovery)) 
			// Someone got to it first
			return false;
		}
	    }
	} else {
	    if (txn != null) {
		// We need to add this txn to this handle and
		// add this handle to this txn.
		handle.add(txn, op, this); // add manager to handle's list
		txn.add(handle);	    // add handle to mgr's list
	    }
	}
	return true;
    }

    /**
     * Recover a logged take.
     * @param handle The <code>EntryHandle</code> of the entry who's
     *               take is being logged.
     * @param txn    If non-null the transaction the take was performed
     *               under.
     * @throws NullPointerException if <code>handle</code> is 
     *         <code>null</code>.
     */
    void recoverTake(EntryHandle handle, Txn txn) {
	if (!grab(handle, txn, TransactableMgr.TAKE, true, true))
	    throw 
		new AssertionError("match not found while recovering take");
    }


    /**
     * Return <code>true</code> if the entry held by the given
     * <code>handle</code> has expired by the time in <code>now</code>.
     */
    private boolean isExpired(long now, EntryHandle handle) {
	/* Some callers already own the lock on handle when
	 * they call us, but the general feeling is that
	 * re-synchronizing is not costly and it is important
	 * to only call remove if we own the lock.
	 */
	synchronized (handle) {
	    final EntryRep rep = handle.rep();
	    synchronized (rep) {
		if (rep.getExpiration() > now) {
		    // Not expired
		    return false;
		}

		/* Expired, set expiration to before the beginning of
		 * time so renew() (which does not lock on the handle,
		 * but the rep...) can't renew the lease once we leave
		 * this block, even it already has a ref to the
		 * rep. Everyone else locks on the handle so
		 * and makes sure the handle has not been removed
		 * before doing anything important.
		 */
		rep.setExpiration(Long.MIN_VALUE);
	    }

	    // If we are here the lease must have expired
	    if (matchingLogger.isLoggable(Level.FINER)) {
		matchingLogger.log(Level.FINER, "expired {0} at {1} (now {2})",
		    new Object[] {rep.id(), 
				  new Long(rep.getExpiration()),
				  new Long(now)});
	    }

	    if (remove(handle, false)) {
		/* If we got to do the remove, schedule
		 * logging of the removal, otherwise
		 * someone else already did it, or will do it
		 */
		space.scheduleCancelOp(rep.id());
	    }

	    return true;
	}
    }
    
    /**
     * Add new new entry to the holder. Assumes the lock
     * on the handle is held if there is a possibility
     * of concurrent access.
     * @param handle The <code>EntryHandle</code> for the
     *               entry being added.
     * @param txn If the add is being done under a 
     *            transaction the <code>TransactableMgr</code> for
     *            that transaction.
     * @throws NullPointerException if <code>handle</code> is 
     *         <code>null</code>.
     */
    void add(EntryHandle handle, TransactableMgr txn) {
	final EntryRep rep = handle.rep();
	if (txn != null) 
	    txn.add(handle);

	contents.add(handle);
	idMap.put(rep.getCookie(), handle);

	/* Make sure info duplicated across all the handles in this
	 * holder is shared
	 */
	final EntryHandle head = (EntryHandle) contents.head();
	if (head != null && head != handle)
	    rep.shareWith(head.rep());
    }

    /**
     * Return an enumerator over the contents of this space that are visible
     * from the given mgr.
     */
    RepEnum contents(TransactableMgr mgr) {
	return new SimpleRepEnum(mgr);
    }

    /**
     * The class that implements <code>RepEnum</code> for this class.
     */
    private class SimpleRepEnum implements RepEnum {
	/** The last node we saw */
	private EntryHandle handle;
	private TransactableMgr mgr;
	private long startTime;
	int count = 0;

	SimpleRepEnum(TransactableMgr mgr) {
	    this.mgr = mgr;
	    handle = (EntryHandle) contents.head();
	    startTime = System.currentTimeMillis();
	}

	// inherit doc comment from superclass
	public EntryRep nextRep() {
	    iteratorLogger.entering("SimpleRepEnum", "nextRep");

	    /* Since we might be accessing our iteration from a
	     * different thread than the one that began the traversal,
	     * we need to inform the FastList that this thread should
	     * be allowed to assume that traversal without throwing 
	     * an exception. FastList must therefore update its data
	     * structures to accommodate the traversal from this new
	     * thread. [It would be better if did this once per a thread...]
	     */

	    if (handle != null)
		handle.restart();

	    /* Skip over handles which are either removed or unable
	     * to perform a READ operation.
	     */

	    while (handle != null &&
		(!handle.canPerform(mgr, TransactableMgr.READ)	||
		 isExpired(startTime, handle) 			|| 
		 handle.removed()
		))
	    {
		handle = (EntryHandle) handle.next();
		iteratorLogger.log(Level.FINEST, 
				   "advanced current handle to {0}", handle);
	    }

	    if (handle == null)
		return null;

	    EntryHandle h = handle;
	    handle = (EntryHandle) h.next();
	    return h.rep();
	}
    }

    /**
     * Remove the given handle from this holder and the <code>idMap</code>.
     * If the handle isn't in this holder, this does nothing.
     * @param h the <code>EntryHandle</code> to remove.
     * @param recovery <code>true</code> if being called as part
     *        of log recovery.
     * @return <code>true</code> if this call removed <code>h</code> and
     *         <code>false</code> otherwise.
     */
    boolean remove(EntryHandle h, boolean recovery) {
	assert (recovery || Thread.holdsLock(h));

	final boolean ok = contents.remove(h);
	if (ok) {
	    idMap.remove(h.rep().getCookie());
	    /* This may cause an ifExists query to be resolved,
	     * even if this entry was not locked under a transaction 
	     */
	    if (!recovery) {
		space.recordTransition(
		    new EntryTransition(h, null, false, false));
	    }
	}

	return ok;
    }

    /**
     * Return the handle for the given <code>EntryRep</code> object.  
     * This is done via lookup in the <code>idMap</code>.  The 
     * <code>idMap</code> is doing double duty here.  The 
     * <code>LeaseDesc</code> associated with an <code>EntryRep</code> 
     * is also the rep's <code>EntryHandle</code>.
     */
    private EntryHandle handleFor(EntryRep rep) {
	return (EntryHandle) idMap.get(rep.getCookie());
    }

    /**
     * Take the given resource out of this holder.  Return
     * <code>false</code> if the specified entry wasn't in this
     * holder.
     */
    boolean cancel(EntryHandle handle) {
	synchronized (handle) {
	    return remove(handle, false);
	}
    }

    /**
     * Reap the expired elements (and the underlying FastList)
     */
    void reap() {

	// Examine each of the elements within the FastList to determine if
	// any of them have expired. If they have, ensure that they are
	// removed ("reaped") from the collection. 

	long now = System.currentTimeMillis();
	for (EntryHandle handle = (EntryHandle) contents.head();
	     handle != null;
	     handle = (EntryHandle) handle.next())
	{
	    // Don't try to remove things twice
	    if (handle.removed()) {
		continue;
	    }

	    // Calling isExpired() will both make the check and remove it
	    // if necessary.
	    isExpired(now, handle);
	}

	// This provides the FastList with an opportunity to actually
	// excise the items identified as "removed" from the list.
	contents.reap();
    }
}
