1 /*
2  * Copyright (C) 2014 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.android.internal.midi;
18 
19 import java.util.SortedMap;
20 import java.util.TreeMap;
21 
22 /**
23  * Store arbitrary timestamped events using a Long timestamp.
24  * Only one Thread can write into the buffer.
25  * And only one Thread can read from the buffer.
26  */
27 public class EventScheduler {
28     public static final long NANOS_PER_MILLI = 1000000;
29 
30     private final Object mLock = new Object();
31     protected volatile SortedMap<Long, FastEventQueue> mEventBuffer;
32     protected FastEventQueue mEventPool = null;
33     private int mMaxPoolSize = 200;
34     private boolean mClosed;
35 
EventScheduler()36     public EventScheduler() {
37         mEventBuffer = new TreeMap<Long, FastEventQueue>();
38     }
39 
40     /**
41      * Class for a fast event queue.
42      *
43      * If we keep at least one node in the list then it can be atomic
44      * and non-blocking.
45      */
46     public static class FastEventQueue {
47         // One thread takes from the beginning of the list.
48         volatile SchedulableEvent mFirst;
49         // A second thread returns events to the end of the list.
50         volatile SchedulableEvent mLast;
51         volatile long mEventsAdded;
52         volatile long mEventsRemoved;
53 
FastEventQueue(SchedulableEvent event)54         public FastEventQueue(SchedulableEvent event) {
55             mFirst = event;
56             mLast = mFirst;
57             mEventsAdded = 1;
58             mEventsRemoved = 0;
59         }
60 
size()61         int size() {
62             return (int)(mEventsAdded - mEventsRemoved);
63         }
64 
65         /**
66          * Do not call this unless there is more than one event
67          * in the list.
68          * @return first event in the list
69          */
remove()70         public SchedulableEvent remove() {
71             // Take first event.
72             mEventsRemoved++;
73             SchedulableEvent event = mFirst;
74             mFirst = event.mNext;
75             event.mNext = null;
76             return event;
77         }
78 
79         /**
80          * @param event
81          */
add(SchedulableEvent event)82         public void add(SchedulableEvent event) {
83             event.mNext = null;
84             mLast.mNext = event;
85             mLast = event;
86             mEventsAdded++;
87         }
88     }
89 
90     /**
91      * Base class for events that can be stored in the EventScheduler.
92      */
93     public static class SchedulableEvent {
94         private long mTimestamp;
95         volatile private SchedulableEvent mNext = null;
96 
97         /**
98          * @param timestamp
99          */
SchedulableEvent(long timestamp)100         public SchedulableEvent(long timestamp) {
101             mTimestamp = timestamp;
102         }
103 
104         /**
105          * @return timestamp
106          */
getTimestamp()107         public long getTimestamp() {
108             return mTimestamp;
109         }
110 
111         /**
112          * The timestamp should not be modified when the event is in the
113          * scheduling buffer.
114          */
setTimestamp(long timestamp)115         public void setTimestamp(long timestamp) {
116             mTimestamp = timestamp;
117         }
118     }
119 
120     /**
121      * Get an event from the pool.
122      * Always leave at least one event in the pool.
123      * @return event or null
124      */
removeEventfromPool()125     public SchedulableEvent removeEventfromPool() {
126         SchedulableEvent event = null;
127         if (mEventPool != null && (mEventPool.size() > 1)) {
128             event = mEventPool.remove();
129         }
130         return event;
131     }
132 
133     /**
134      * Return events to a pool so they can be reused.
135      *
136      * @param event
137      */
addEventToPool(SchedulableEvent event)138     public void addEventToPool(SchedulableEvent event) {
139         if (mEventPool == null) {
140             mEventPool = new FastEventQueue(event);
141         // If we already have enough items in the pool then just
142         // drop the event. This prevents unbounded memory leaks.
143         } else if (mEventPool.size() < mMaxPoolSize) {
144             mEventPool.add(event);
145         }
146     }
147 
148     /**
149      * Add an event to the scheduler. Events with the same time will be
150      * processed in order.
151      *
152      * @param event
153      */
add(SchedulableEvent event)154     public void add(SchedulableEvent event) {
155         Object lock = getLock();
156         synchronized (lock) {
157             FastEventQueue list = mEventBuffer.get(event.getTimestamp());
158             if (list == null) {
159                 long lowestTime = mEventBuffer.isEmpty() ? Long.MAX_VALUE
160                         : mEventBuffer.firstKey();
161                 list = new FastEventQueue(event);
162                 mEventBuffer.put(event.getTimestamp(), list);
163                 // If the event we added is earlier than the previous earliest
164                 // event then notify any threads waiting for the next event.
165                 if (event.getTimestamp() < lowestTime) {
166                     lock.notify();
167                 }
168             } else {
169                 list.add(event);
170             }
171         }
172     }
173 
removeNextEventLocked(long lowestTime)174     protected SchedulableEvent removeNextEventLocked(long lowestTime) {
175         SchedulableEvent event;
176         FastEventQueue list = mEventBuffer.get(lowestTime);
177         // Remove list from tree if this is the last node.
178         if ((list.size() == 1)) {
179             mEventBuffer.remove(lowestTime);
180         }
181         event = list.remove();
182         return event;
183     }
184 
185     /**
186      * Check to see if any scheduled events are ready to be processed.
187      *
188      * @param timestamp
189      * @return next event or null if none ready
190      */
getNextEvent(long time)191     public SchedulableEvent getNextEvent(long time) {
192         SchedulableEvent event = null;
193         Object lock = getLock();
194         synchronized (lock) {
195             if (!mEventBuffer.isEmpty()) {
196                 long lowestTime = mEventBuffer.firstKey();
197                 // Is it time for this list to be processed?
198                 if (lowestTime <= time) {
199                     event = removeNextEventLocked(lowestTime);
200                 }
201             }
202         }
203         // Log.i(TAG, "getNextEvent: event = " + event);
204         return event;
205     }
206 
207     /**
208      * Return the next available event or wait until there is an event ready to
209      * be processed. This method assumes that the timestamps are in nanoseconds
210      * and that the current time is System.nanoTime().
211      *
212      * @return event
213      * @throws InterruptedException
214      */
waitNextEvent()215     public SchedulableEvent waitNextEvent() throws InterruptedException {
216         SchedulableEvent event = null;
217         Object lock = getLock();
218         synchronized (lock) {
219             while (!mClosed) {
220                 long millisToWait = Integer.MAX_VALUE;
221                 if (!mEventBuffer.isEmpty()) {
222                     long now = System.nanoTime();
223                     long lowestTime = mEventBuffer.firstKey();
224                     // Is it time for the earliest list to be processed?
225                     if (lowestTime <= now) {
226                         event = removeNextEventLocked(lowestTime);
227                         break;
228                     } else {
229                         // Figure out how long to sleep until next event.
230                         long nanosToWait = lowestTime - now;
231                         // Add 1 millisecond so we don't wake up before it is
232                         // ready.
233                         millisToWait = 1 + (nanosToWait / NANOS_PER_MILLI);
234                         // Clip 64-bit value to 32-bit max.
235                         if (millisToWait > Integer.MAX_VALUE) {
236                             millisToWait = Integer.MAX_VALUE;
237                         }
238                     }
239                 }
240                 lock.wait((int) millisToWait);
241             }
242         }
243         return event;
244     }
245 
flush()246     protected void flush() {
247         // Replace our event buffer with a fresh empty one
248         mEventBuffer = new TreeMap<Long, FastEventQueue>();
249     }
250 
251     /**
252      * Stops the EventScheduler.
253      * The subscriber calling waitNextEvent() will get one final SchedulableEvent returning null.
254      */
close()255     public void close() {
256         Object lock = getLock();
257         synchronized (lock) {
258             mClosed = true;
259             lock.notify();
260         }
261     }
262 
263     /**
264      * Gets the lock. This doesn't lock it in anyway.
265      * Subclasses can override this.
266      *
267      * @return Object
268      */
getLock()269     protected Object getLock() {
270         return mLock;
271     }
272 }
273