content: /*
   * Copyright (C) 2014 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.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://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package com.android.internal.midi;
  
  import java.util.Iterator;
  import java.util.SortedMap;
  import java.util.TreeMap;
  
  /**
   * Store arbitrary timestamped events using a Long timestamp.
   * Only one Thread can write into the buffer.
   * And only one Thread can read from the buffer.
   */
  public class EventScheduler {
      private static final long NANOS_PER_MILLI = 1000000;
  
      private final Object mLock = new Object();
      volatile private SortedMap<Long, FastEventQueue> mEventBuffer;
      private FastEventQueue mEventPool = null;
      private int mMaxPoolSize = 200;
      private boolean mClosed;
  
      public EventScheduler() {
          mEventBuffer = new TreeMap<Long, FastEventQueue>();
      }
  
      // If we keep at least one node in the list then it can be atomic
      // and non-blocking.
      private class FastEventQueue {
          // One thread takes from the beginning of the list.
          volatile SchedulableEvent mFirst;
          // A second thread returns events to the end of the list.
          volatile SchedulableEvent mLast;
          volatile long mEventsAdded;
          volatile long mEventsRemoved;
  
          FastEventQueue(SchedulableEvent event) {
              mFirst = event;
              mLast = mFirst;
              mEventsAdded = 1;
              mEventsRemoved = 0;
          }
  
          int size() {
              return (int)(mEventsAdded - mEventsRemoved);
          }
  
          /**
           * Do not call this unless there is more than one event
           * in the list.
           * @return first event in the list
           */
          public SchedulableEvent remove() {
              // Take first event.
              mEventsRemoved++;
              SchedulableEvent event = mFirst;
              mFirst = event.mNext;
              event.mNext = null;
              return event;
          }
  
          /**
           * @param event
           */
          public void add(SchedulableEvent event) {
              event.mNext = null;
              mLast.mNext = event;
              mLast = event;
              mEventsAdded++;
          }
      }
  
      /**
       * Base class for events that can be stored in the EventScheduler.
       */
      public static class SchedulableEvent {
          private long mTimestamp;
          volatile private SchedulableEvent mNext = null;
  
          /**
           * @param timestamp
           */
          public SchedulableEvent(long timestamp) {
              mTimestamp = timestamp;
          }
  
          /**
           * @return timestamp
           */
          public long getTimestamp() {
              return mTimestamp;
          }
  
          /**
           * The timestamp should not be modified when the event is in the
           * scheduling buffer.
           */
          public void setTimestamp(long timestamp) {
              mTimestamp = timestamp;
          }
      }
  
      /**
       * Get an event from the pool.
       * Always leave at least one event in the pool.
       * @return event or null
       */
      public SchedulableEvent removeEventfromPool() {
          SchedulableEvent event = null;
          if (mEventPool != null && (mEventPool.size() > 1)) {
              event = mEventPool.remove();
          }
          return event;
      }
  
      /**
       * Return events to a pool so they can be reused.
       *
       * @param event
       */
      public void addEventToPool(SchedulableEvent event) {
          if (mEventPool == null) {
              mEventPool = new FastEventQueue(event);
          // If we already have enough items in the pool then just
          // drop the event. This prevents unbounded memory leaks.
          } else if (mEventPool.size() < mMaxPoolSize) {
              mEventPool.add(event);
          }
      }
  
      /**
       * Add an event to the scheduler. Events with the same time will be
       * processed in order.
       *
       * @param event
       */
      public void add(SchedulableEvent event) {
          synchronized (mLock) {
              FastEventQueue list = mEventBuffer.get(event.getTimestamp());
              if (list == null) {
                  long lowestTime = mEventBuffer.isEmpty() ? Long.MAX_VALUE
                          : mEventBuffer.firstKey();
                  list = new FastEventQueue(event);
                  mEventBuffer.put(event.getTimestamp(), list);
                  // If the event we added is earlier than the previous earliest
                  // event then notify any threads waiting for the next event.
                  if (event.getTimestamp() < lowestTime) {
                      mLock.notify();
                  }
              } else {
                  list.add(event);
              }
          }
      }
  
      private SchedulableEvent removeNextEventLocked(long lowestTime) {
          SchedulableEvent event;
          FastEventQueue list = mEventBuffer.get(lowestTime);
          // Remove list from tree if this is the last node.
          if ((list.size() == 1)) {
              mEventBuffer.remove(lowestTime);
          }
          event = list.remove();
          return event;
      }
  
      /**
       * Check to see if any scheduled events are ready to be processed.
       *
       * @param timestamp
       * @return next event or null if none ready
       */
      public SchedulableEvent getNextEvent(long time) {
          SchedulableEvent event = null;
          synchronized (mLock) {
              if (!mEventBuffer.isEmpty()) {
                  long lowestTime = mEventBuffer.firstKey();
                  // Is it time for this list to be processed?
                  if (lowestTime <= time) {
                      event = removeNextEventLocked(lowestTime);
                  }
              }
          }
          // Log.i(TAG, "getNextEvent: event = " + event);
          return event;
      }
  
      /**
       * Return the next available event or wait until there is an event ready to
       * be processed. This method assumes that the timestamps are in nanoseconds
       * and that the current time is System.nanoTime().
       *
       * @return event
       * @throws InterruptedException
       */
      public SchedulableEvent waitNextEvent() throws InterruptedException {
          SchedulableEvent event = null;
          synchronized (mLock) {
              while (!mClosed) {
                  long millisToWait = Integer.MAX_VALUE;
                  if (!mEventBuffer.isEmpty()) {
                      long now = System.nanoTime();
                      long lowestTime = mEventBuffer.firstKey();
                      // Is it time for the earliest list to be processed?
                      if (lowestTime <= now) {
                          event = removeNextEventLocked(lowestTime);
                          break;
                      } else {
                          // Figure out how long to sleep until next event.
                          long nanosToWait = lowestTime - now;
                          // Add 1 millisecond so we don't wake up before it is
                          // ready.
                          millisToWait = 1 + (nanosToWait / NANOS_PER_MILLI);
                          // Clip 64-bit value to 32-bit max.
                          if (millisToWait > Integer.MAX_VALUE) {
                              millisToWait = Integer.MAX_VALUE;
                          }
                      }
                  }
                  mLock.wait((int) millisToWait);
              }
          }
          return event;
      }
  
      protected void flush() {
          // Replace our event buffer with a fresh empty one
          mEventBuffer = new TreeMap<Long, FastEventQueue>();
      }
  
      public void close() {
          synchronized (mLock) {
              mClosed = true;
              mLock.notify();
          }
      }
  }
  