code: /*
   * Copyright (c) 2009 Stanford University, unless otherwise specified.
   * All rights reserved.
   *
   * This software was developed by the Pervasive Parallelism Laboratory of
   * Stanford University, California, USA.
   *
   * Permission to use, copy, modify, and distribute this software in source
   * or binary form for any purpose with or without fee is hereby granted,
   * 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. Neither the name of Stanford University 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 REGENTS 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 REGENTS 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 edu.stanford.ppl.concurrent;
  
  /** A <code>Epoch</code> has a lifecycle consisting of three phases: active,
   *  closing, and closed.  During the active phase partipants may arrive and
   *  leave the epoch.  Once a close has been requested, new participants are not
   *  allowed, only leaving is possible.  Once close has been requested and all
   *  participants have left, the epoch is transitioned to the closed state.
   *  <p>
   *  Entry is performed with {@link #attemptArrive}, which returns a non-null
   *  ticket on success or null if {@link #beginClose} has already been called.
   *  Each successful call to <code>attemptArrive</code> must be paired by a call
   *  to {@link Ticket#leave} on the returned ticket.
   *  <p>
   *  The abstract method {@link #onClosed} will be invoked exactly once after
   *  the epoch becomes closed.  It will be passed the sum of the values passed
   *  to {@link Ticket#leave}.  There is no way to query the current participant
   *  count or state of the epoch without changing it.
   *  <p>
   *  Internally the epoch responds to contention by increasing its size,
   *  striping the participant count across multiple objects (and hopefully
   *  multiple cache lines).  Once close has begun, the epoch converts itself to
   *  a single-shot hierarchical barrier, that also performs a hierarchical
   *  reduction of the leave parameters.
   */
  abstract public class Epoch {
  
      /** Represents a single successful arrival to an {@link Epoch}. */ 
      public interface Ticket {
          /** Informs the epoch that returned this ticket that the participant
           *  has left.  This method should be called exactly once per ticket.
           *  The sum of the <code>data</code> values for all tickets will be
           *  computed and passed to {@link Epoch#onClosed}. 
           */
          void leave(int data);
      }
  
      private final Root _root = new Root();
  
      /** Returns a {@link Ticket} indicating a successful arrival, if no call to
       *  {@link #beginClose} has been made for this epoch, or returns null if
       *  close has already begun.  {@link Ticket#leave} must be called exactly
       *  once on any returned ticket.
       */
      public Ticket attemptArrive() {
          return _root.attemptArrive();
      }
  
      /** Prevents new arrivals from succeeding, then returns immediately.
       *  {@link #onClosed} will be called after all outstanding tickets have
       *  been returned.  To block until close is complete, add some sort of
       *  synchronization logic to the user-defined implementation of {@link
       *  #onClosed}.
       */
      public void beginClose() {
          _root.beginClose();
      }
  
      /** Override this method to provide user-defined behavior.
       *  <code>dataSum</code> will be the sum of the <code>data</code> values
       *  passed to {@link Ticket#leave} for all tickets in this epoch.
       *  <p>
       *  As a simple example, a blocking close operation may be defined by:<pre>
       *    class BlockingEpoch extends Epoch {
       *        private final CountDownLatch _closed = new CountDownLatch(1);
       *
       *        public void blockingClose() throws InterruptedException {
       *            beginClose();
       *            _closed.await();
       *        }
       *
       *        protected void onClosed(int dataSum) {
       *            _closed.countDown(1);
       *        }
       *    }
       *  </pre>
       */
      abstract protected void onClosed(int dataSum);
  
      //////////////// debugging stuff
  
      int computeSpread() {
          return _root.computeSpread();
      }
  
      //////////////// internal implementation
  
      private class Root extends EpochNode {
          protected void onClosed(final int dataSum) {
              Epoch.this.onClosed(dataSum);
          }
      }
  }
  