/**
 * Copyright (c) 2004-2005, Regents of the University of California
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 *
 * 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.
 *
 * Neither the name of the University of California, Los Angeles nor the
 * names of its contributors may be used to endorse or promote products
 * derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR 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.
 */

package avrora.sim.clock;

import avrora.sim.*;
import cck.util.Util;
import java.util.HashMap;

/**
 * The <code>BarrierSynchronizer</code> class implements a global timer among multiple simulators by inserting
 * periodic events into the queue of each simulator.
 *
 * @author Ben L. Titzer, Daniel Lee
 */
public class BarrierSynchronizer extends Synchronizer {

    /**
     * <code>period</code> is the number of cycles on a member local clock per cycle on the global clock. Some
     * re-coding must be done if microcontrollers running at difference speeds are to be accurately
     * simulated.
     */
    protected long period;
    protected final HashMap<SimulatorThread, SynchEvent> threadMap;
    protected final Simulator.Event action;

    protected final Object condition;
    protected int goal;
    protected int meet_count;
    protected int wait_count;

    protected WaitSlot waitSlotList;

    /**
     * The constructor for the <code>IntervalSynchronizer</code> class creates a new synchronizer
     * with the specified period, that will fire the specified event each time all threads meet at
     * a synchronization point.
     * @param p the period in clock cycles which to synchronize the threads
     * @param a the event to fire each time all threads meet at a synchronization point
     */
    public BarrierSynchronizer(long p, Simulator.Event a) {
        period = p;
        action = a;
        threadMap = new HashMap<SimulatorThread, SynchEvent>();
        condition = new Object();
    }

    /**
     * The <code>SynchEvent</code> class represents an event that is inserted into the event
     * queue of each simulator at the same global time. When this event fires, it will stop the thread
     * running this simulator by waiting on a shared
     * condition variable. The last thread to fire the event will then notify the condition variable
     * which frees the other threads to run again in parallel.
     */
    protected class SynchEvent implements Simulator.Event {

        protected final SimulatorThread thread;
        protected final MainClock clock;
        protected boolean removed;
        protected boolean met;
        protected WaitSlot waitSlot;

        protected SynchEvent(SimulatorThread t) {
            thread = t;
            clock = t.getSimulator().getClock();
        }

        /**
         * The <code>fire()</code> method of this event is called by the individual event queues of each
         * simulator as they reach this point in time. The implementation of this method waits for all threads
         * to join.
         */
        public void fire() {
            try {
                synchronized (condition) {
                    // if we have been removed since the last synchronization, return!
                    if ( removed ) return;

                    met = true;

                    // increment the count of the number of threads that have entered
                    meet_count++;

                    if ( !signalOthers() )
                        condition.wait();

                    met = false;
                }
                // if we have been removed since the last synchronization, don't insert synch event
                if ( removed ) return;

                // we have not been removed, we can reinsert the synch event
                clock.insertEvent(this, period);
            } catch (InterruptedException e) {
                throw Util.unexpected(e);
            }
        }

    }

    /**
     * The <code>signalOthers()</code> method is used to check whether the thread that has just arrived
     * should signal other threads to continue.
     * @return true if this thread signalled the others to continue; false if this thread should stop
     * and wait for the other threads before continuing
     */
    protected boolean signalOthers() {

        // check for any waiters that need to be woken
        checkWaiters();

        // have we reached the goal?
        if (meet_count < goal) {
            return false;
        } else {
            // last thread to arrive sets the count to zero and notifies all other threads
            meet_count = 0;
            wait_count = 0;
            // perform the action that should be run while all threads are stopped (serial)
            action.fire();
            // release threads
            condition.notifyAll();
            return true;
        }
    }

    /**
     * The <code>start()</code> method starts the threads executing, and the synchronizer
     * will add whatever synchronization to their execution that is necessary to preserve
     * the global timing properties of simulation.
     */
    public synchronized void start() {
        for (SimulatorThread thread : threadMap.keySet()) {
            thread.start();
        }
    }

    /**
     * The <code>join()</code> method will block the caller until all of the threads in
     * this synchronization interval have terminated, either through <code>stop()</code>
     * being called, or terminating normally such as through a timeout.
     */
    public void join() throws InterruptedException {
        for (SimulatorThread thread : threadMap.keySet()) {
            thread.join();
        }
    }

    /**
     * The <code>stop()</code> method will terminate all the simulation threads. It is
     * not guaranteed to stop all the simulation threads at the same global time.
     */
    public synchronized void stop() {
        for (SimulatorThread thread : threadMap.keySet()) {
            thread.getSimulator().stop();
        }
    }

    /**
     * The <code>pause()</code> method temporarily pauses the simulation. The nodes are
     * not guaranteed to stop at the same global time. This method will return when all
     * threads in the simulation have been paused and will no longer make progress until
     * the <code>start()</code> method is called again.
     */
    public synchronized void pause() {
        throw Util.unimplemented();
    }

    /**
     * The <code>synch()</code> method will pause all of the nodes at the same global time.
     * This method can only be called when the simulation is paused. It will run all threads
     * forward until the global time specified and pause them.
     * @param globalTime the global time in clock cycles to run all threads ahead to
     */
    public synchronized void synch(long globalTime) {
        throw Util.unimplemented();
    }

    /**
     * The <code>addNode()</code> method adds a node to this synchronization group.
     * This method should only be called before the <code>start()</code> method is
     * called.
     * @param t the simulator representing the node to add to this group
     */
    public synchronized void addNode(Simulation.Node t) {
        // if we already have this thread, do nothing
        SimulatorThread st = t.getThread();
        if (threadMap.containsKey(st)) return;

        st.setSynchronizer(this);

        // create a new synchronization event for this thread's queue
        SynchEvent event = new SynchEvent(st);
        threadMap.put(st, event);
        // insert the synch event in the thread's queue
        event.clock.insertEvent(event, period);
        goal++;
    }

    /**
     * The <code>removeNode()</code> method removes a node from this synchronization
     * group, and wakes any nodes that might be waiting on it.
     * @param t the simulator thread to remove from this synchronization group
     */
    public synchronized void removeNode(Simulation.Node t) {
        // don't try to remove a thread that's not here!
        SimulatorThread st = t.getThread();
        if ( !threadMap.containsKey(st) ) return;
        synchronized ( condition ) {
            SynchEvent e = (SynchEvent)threadMap.get(st);
            e.removed = true; // just in case the thread is still running, don't let it synch
            if ( e.met ) meet_count--;

            if ( stillWaiting(e.waitSlot) ) {
                // if this wait slot hasn't happened yet, we need to decrement wait_count
                // and to decrement the number of waiters in that slot
                e.waitSlot.numWaiters--;
                wait_count--;
            }
            threadMap.remove(e);
            goal--;
            // signal any other threads (and wake waiters as necessary) but don't wait
            signalOthers();
        }
    }

    /**
     * The <code>waitForNeighbors()</code> method is called from within the execution
     * of a node when that node needs to wait for its neighbors to catch up to it
     * in execution time. The node will be blocked until the other nodes in other
     * threads catch up in global time.
     */
    public void waitForNeighbors(long time) {

        // get the current simulator thread
        SimulatorThread thread = (SimulatorThread)Thread.currentThread();
        SynchEvent event = (SynchEvent)threadMap.get(thread);
        // if the current thread is not in the synchronizer, do nothing
        if ( event == null ) return;

        WaitSlot w;
        synchronized ( condition ) {
            // allocate a wait slot for this thread
            w = insertWaiter(event, time);
            // check for other waiters and wake them if necessary
            WaitSlot h = checkWaiters();
            // if we were at the head and just woken up, we can just return
            if ( w == h ) return;
        }

        // falling through means that we are either not at the head
        // or that not all threads have performed a meet or a wait
        try {
            // we must grab the lock for this wait slot
            synchronized ( w ) {
                 // check for intervening wakeup between dropping global lock and taking local lock
                if ( w.shouldWait )
                    w.wait();
            }
        } catch ( InterruptedException e) {
            throw Util.unexpected(e);
        }
    }

    /**
     * The <code>WaitSlot</code> class represents a slot in time where multiple threads are waiting
     * for others to catch up.
     */
    static class WaitSlot {
        final long time;
        int numWaiters;
        WaitSlot next;
        boolean shouldWait;

        WaitSlot(long t) {
            shouldWait = true;
            time = t;
        }
    }

    protected WaitSlot insertWaiter(SynchEvent event, long time) {
        // get a wait slot for this waiter
        WaitSlot w = getWaitSlot(time);

        // now this thread is officially waiting
        wait_count++;
        // remember the wait slot this waiter is in
        event.waitSlot = w;
        // increment the number of waiters in this slot
        w.numWaiters++;

        return w;
    }

    private WaitSlot getWaitSlot(long time) {
        WaitSlot prev = waitSlotList;
        // search through the wait list from front to back
        for ( WaitSlot slot = waitSlotList; ; slot = slot.next ) {
            // if we are at the end of the list, or in-between links, create a new link
            if ( slot == null || slot.time > time ) {
                return insertAfter(prev, new WaitSlot(time));
            }
            // if we matched the time of some other waiter exactly
            if ( slot.time == time ) {
                return slot;
            }
            // keep track of previous link
            prev = slot;
        }
    }

    private WaitSlot insertAfter(WaitSlot prev, WaitSlot w) {
        if ( prev != null ) {
            w.next = prev.next;
            prev.next = w;
        } else {
            waitSlotList = w;
        }
        return w;
    }

    protected WaitSlot checkWaiters() {
        // have all threads reached either a meet or a wait?
        if ( wait_count + meet_count < goal ) return null;

        // are there any waiters at all?
        if ( waitSlotList == null ) return null;

        // there is a ready wait slot, wake those threads waiting on it
        WaitSlot h = waitSlotList;
        // move the wait list ahead to the next link
        waitSlotList = h.next;
        synchronized ( h ) {
            // notify the threads waiting on this wait slot
            h.shouldWait = false;
            h.notifyAll();
        }
        // reduce the wait count by the number of waiters in this slot
        wait_count -= h.numWaiters;
        return h;
    }

    protected boolean stillWaiting(WaitSlot w) {
        if ( w == null ) return false;
        for ( WaitSlot h = waitSlotList; h != null; h = h.next )
            if ( h == w ) return true;
        return false;
    }

}
