OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 import 'dart:_internal' hide Symbol; | 5 import 'dart:_internal' hide Symbol; |
6 | 6 |
7 // Timer heap implemented as a array-based binary heap[0]. | 7 // Timer heap implemented as a array-based binary heap[0]. |
8 // This allows for O(1) `first`, O(log(n)) `remove`/`removeFirst` and O(log(n)) | 8 // This allows for O(1) `first`, O(log(n)) `remove`/`removeFirst` and O(log(n)) |
9 // `add`. | 9 // `add`. |
10 // | 10 // |
11 // To ensure the timers are ordered by insertion time, the _Timer class has a | 11 // To ensure the timers are ordered by insertion time, the _Timer class has a |
12 // `_id` field set when added to the heap. | 12 // `_id` field set when added to the heap. |
13 // | 13 // |
14 // [0] http://en.wikipedia.org/wiki/Binary_heap | 14 // [0] http://en.wikipedia.org/wiki/Binary_heap |
15 class _TimerHeap { | 15 class _TimerHeap { |
16 List<_Timer> _list; | 16 List<_Timer> _list; |
17 int _used = 0; | 17 int _used = 0; |
18 | 18 |
19 _TimerHeap([int initSize = 7]) : _list = new List<_Timer>(initSize); | 19 _TimerHeap([int initSize = 7]) |
| 20 : _list = new List<_Timer>(initSize); |
20 | 21 |
21 bool get isEmpty => _used == 0; | 22 bool get isEmpty => _used == 0; |
22 | 23 |
23 _Timer get first => _list[0]; | 24 _Timer get first => _list[0]; |
24 | 25 |
25 bool isFirst(_Timer timer) => timer._indexOrNext == 0; | 26 bool isFirst(_Timer timer) => timer._indexOrNext == 0; |
26 | 27 |
27 void add(_Timer timer) { | 28 void add(_Timer timer) { |
28 if (_used == _list.length) { | 29 if (_used == _list.length) { |
29 _resize(); | 30 _resize(); |
(...skipping 102 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
132 // ids are recycled after ID_MASK enqueues or when the timer queue is empty. | 133 // ids are recycled after ID_MASK enqueues or when the timer queue is empty. |
133 static const _ID_MASK = 0x1fffffff; | 134 static const _ID_MASK = 0x1fffffff; |
134 static int _idCount = 0; | 135 static int _idCount = 0; |
135 | 136 |
136 static RawReceivePort _receivePort; | 137 static RawReceivePort _receivePort; |
137 static SendPort _sendPort; | 138 static SendPort _sendPort; |
138 static int _scheduledWakeupTime; | 139 static int _scheduledWakeupTime; |
139 | 140 |
140 static bool _handlingCallbacks = false; | 141 static bool _handlingCallbacks = false; |
141 | 142 |
142 Function _callback; // Closure to call when timer fires. null if canceled. | 143 Function _callback; // Closure to call when timer fires. null if canceled. |
143 int _wakeupTime; // Expiration time. | 144 int _wakeupTime; // Expiration time. |
144 final int _milliSeconds; // Duration specified at creation. | 145 final int _milliSeconds; // Duration specified at creation. |
145 final bool _repeating; // Indicates periodic timers. | 146 final bool _repeating; // Indicates periodic timers. |
146 var _indexOrNext; // Index if part of the TimerHeap, link otherwise. | 147 var _indexOrNext; // Index if part of the TimerHeap, link otherwise. |
147 int _id; // Incrementing id to enable sorting of timers with same expiry. | 148 int _id; // Incrementing id to enable sorting of timers with same expiry. |
| 149 |
148 | 150 |
149 // Get the next available id. We accept collisions and reordering when the | 151 // Get the next available id. We accept collisions and reordering when the |
150 // _idCount overflows and the timers expire at the same millisecond. | 152 // _idCount overflows and the timers expire at the same millisecond. |
151 static int _nextId() { | 153 static int _nextId() { |
152 var result = _idCount; | 154 var result = _idCount; |
153 _idCount = (_idCount + 1) & _ID_MASK; | 155 _idCount = (_idCount + 1) & _ID_MASK; |
154 return result; | 156 return result; |
155 } | 157 } |
156 | 158 |
157 _Timer._internal( | |
158 this._callback, this._wakeupTime, this._milliSeconds, this._repeating) | |
159 : _id = _nextId(); | |
160 | 159 |
161 static Timer _createTimer( | 160 _Timer._internal(this._callback, |
162 void callback(Timer timer), int milliSeconds, bool repeating) { | 161 this._wakeupTime, |
| 162 this._milliSeconds, |
| 163 this._repeating) : _id = _nextId(); |
| 164 |
| 165 |
| 166 static Timer _createTimer(void callback(Timer timer), |
| 167 int milliSeconds, |
| 168 bool repeating) { |
163 // Negative timeouts are treated as if 0 timeout. | 169 // Negative timeouts are treated as if 0 timeout. |
164 if (milliSeconds < 0) { | 170 if (milliSeconds < 0) { |
165 milliSeconds = 0; | 171 milliSeconds = 0; |
166 } | 172 } |
167 // Add one because DateTime.now() is assumed to round down | 173 // Add one because DateTime.now() is assumed to round down |
168 // to nearest millisecond, not up, so that time + duration is before | 174 // to nearest millisecond, not up, so that time + duration is before |
169 // duration milliseconds from now. Using microsecond timers like | 175 // duration milliseconds from now. Using microsecond timers like |
170 // Stopwatch allows detecting that the timer fires early. | 176 // Stopwatch allows detecting that the timer fires early. |
171 int now = VMLibraryHooks.timerMillisecondClock(); | 177 int now = VMLibraryHooks.timerMillisecondClock(); |
172 int wakeupTime = (milliSeconds == 0) ? now : (now + 1 + milliSeconds); | 178 int wakeupTime = (milliSeconds == 0) ? now : (now + 1 + milliSeconds); |
173 | 179 |
174 _Timer timer = | 180 _Timer timer = new _Timer._internal(callback, |
175 new _Timer._internal(callback, wakeupTime, milliSeconds, repeating); | 181 wakeupTime, |
| 182 milliSeconds, |
| 183 repeating); |
176 // Enqueue this newly created timer in the appropriate structure and | 184 // Enqueue this newly created timer in the appropriate structure and |
177 // notify if necessary. | 185 // notify if necessary. |
178 timer._enqueue(); | 186 timer._enqueue(); |
179 return timer; | 187 return timer; |
180 } | 188 } |
181 | 189 |
| 190 |
182 factory _Timer(int milliSeconds, void callback(Timer timer)) { | 191 factory _Timer(int milliSeconds, void callback(Timer timer)) { |
183 return _createTimer(callback, milliSeconds, false); | 192 return _createTimer(callback, milliSeconds, false); |
184 } | 193 } |
185 | 194 |
| 195 |
186 factory _Timer.periodic(int milliSeconds, void callback(Timer timer)) { | 196 factory _Timer.periodic(int milliSeconds, void callback(Timer timer)) { |
187 return _createTimer(callback, milliSeconds, true); | 197 return _createTimer(callback, milliSeconds, true); |
188 } | 198 } |
189 | 199 |
| 200 |
190 bool get _isInHeap => _indexOrNext is int; | 201 bool get _isInHeap => _indexOrNext is int; |
191 | 202 |
| 203 |
192 int _compareTo(_Timer other) { | 204 int _compareTo(_Timer other) { |
193 int c = _wakeupTime - other._wakeupTime; | 205 int c = _wakeupTime - other._wakeupTime; |
194 if (c != 0) return c; | 206 if (c != 0) return c; |
195 return _id - other._id; | 207 return _id - other._id; |
196 } | 208 } |
197 | 209 |
| 210 |
198 bool get isActive => _callback != null; | 211 bool get isActive => _callback != null; |
199 | 212 |
| 213 |
200 // Cancels a set timer. The timer is removed from the timer heap if it is a | 214 // Cancels a set timer. The timer is removed from the timer heap if it is a |
201 // non-zero timer. Zero timers are kept in the list as they need to consume | 215 // non-zero timer. Zero timers are kept in the list as they need to consume |
202 // the corresponding pending message. | 216 // the corresponding pending message. |
203 void cancel() { | 217 void cancel() { |
204 _callback = null; | 218 _callback = null; |
205 // Only heap timers are really removed. Zero timers need to consume their | 219 // Only heap timers are really removed. Zero timers need to consume their |
206 // corresponding wakeup message so they are left in the queue. | 220 // corresponding wakeup message so they are left in the queue. |
207 if (!_isInHeap) return; | 221 if (!_isInHeap) return; |
208 bool update = _heap.isFirst(this); | 222 bool update = _heap.isFirst(this); |
209 _heap.remove(this); | 223 _heap.remove(this); |
210 if (update) { | 224 if (update) { |
211 _notifyEventHandler(); | 225 _notifyEventHandler(); |
212 } | 226 } |
213 } | 227 } |
214 | 228 |
| 229 |
215 void _advanceWakeupTime() { | 230 void _advanceWakeupTime() { |
216 // Recalculate the next wakeup time. For repeating timers with a 0 timeout | 231 // Recalculate the next wakeup time. For repeating timers with a 0 timeout |
217 // the next wakeup time is now. | 232 // the next wakeup time is now. |
218 _id = _nextId(); | 233 _id = _nextId(); |
219 if (_milliSeconds > 0) { | 234 if (_milliSeconds > 0) { |
220 _wakeupTime += _milliSeconds; | 235 _wakeupTime += _milliSeconds; |
221 } else { | 236 } else { |
222 _wakeupTime = VMLibraryHooks.timerMillisecondClock(); | 237 _wakeupTime = VMLibraryHooks.timerMillisecondClock(); |
223 } | 238 } |
224 } | 239 } |
225 | 240 |
| 241 |
226 // Adds a timer to the heap or timer list. Timers with the same wakeup time | 242 // Adds a timer to the heap or timer list. Timers with the same wakeup time |
227 // are enqueued in order and notified in FIFO order. | 243 // are enqueued in order and notified in FIFO order. |
228 void _enqueue() { | 244 void _enqueue() { |
229 if (_milliSeconds == 0) { | 245 if (_milliSeconds == 0) { |
230 if (_firstZeroTimer == null) { | 246 if (_firstZeroTimer == null) { |
231 _lastZeroTimer = this; | 247 _lastZeroTimer = this; |
232 _firstZeroTimer = this; | 248 _firstZeroTimer = this; |
233 } else { | 249 } else { |
234 _lastZeroTimer._indexOrNext = this; | 250 _lastZeroTimer._indexOrNext = this; |
235 _lastZeroTimer = this; | 251 _lastZeroTimer = this; |
236 } | 252 } |
237 // Every zero timer gets its own event. | 253 // Every zero timer gets its own event. |
238 _notifyZeroHandler(); | 254 _notifyZeroHandler(); |
239 } else { | 255 } else { |
240 _heap.add(this); | 256 _heap.add(this); |
241 if (_heap.isFirst(this)) { | 257 if (_heap.isFirst(this)) { |
242 _notifyEventHandler(); | 258 _notifyEventHandler(); |
243 } | 259 } |
244 } | 260 } |
245 } | 261 } |
246 | 262 |
| 263 |
247 // Enqeue one message for each zero timer. To be able to distinguish from | 264 // Enqeue one message for each zero timer. To be able to distinguish from |
248 // EventHandler messages we send a _ZERO_EVENT instead of a _TIMEOUT_EVENT. | 265 // EventHandler messages we send a _ZERO_EVENT instead of a _TIMEOUT_EVENT. |
249 static void _notifyZeroHandler() { | 266 static void _notifyZeroHandler() { |
250 if (_sendPort == null) { | 267 if (_sendPort == null) { |
251 _createTimerHandler(); | 268 _createTimerHandler(); |
252 } | 269 } |
253 _sendPort.send(_ZERO_EVENT); | 270 _sendPort.send(_ZERO_EVENT); |
254 } | 271 } |
255 | 272 |
| 273 |
256 // Handle the notification of a zero timer. Make sure to also execute non-zero | 274 // Handle the notification of a zero timer. Make sure to also execute non-zero |
257 // timers with a lower expiration time. | 275 // timers with a lower expiration time. |
258 static List _queueFromZeroEvent() { | 276 static List _queueFromZeroEvent() { |
259 var pendingTimers = new List(); | 277 var pendingTimers = new List(); |
260 assert(_firstZeroTimer != null); | 278 assert(_firstZeroTimer != null); |
261 // Collect pending timers from the timer heap that have an expiration prior | 279 // Collect pending timers from the timer heap that have an expiration prior |
262 // to the currently notified zero timer. | 280 // to the currently notified zero timer. |
263 var timer; | 281 var timer; |
264 while (!_heap.isEmpty && (_heap.first._compareTo(_firstZeroTimer) < 0)) { | 282 while (!_heap.isEmpty && (_heap.first._compareTo(_firstZeroTimer) < 0)) { |
265 timer = _heap.removeFirst(); | 283 timer = _heap.removeFirst(); |
266 pendingTimers.add(timer); | 284 pendingTimers.add(timer); |
267 } | 285 } |
268 // Append the first zero timer to the pending timers. | 286 // Append the first zero timer to the pending timers. |
269 timer = _firstZeroTimer; | 287 timer = _firstZeroTimer; |
270 _firstZeroTimer = timer._indexOrNext; | 288 _firstZeroTimer = timer._indexOrNext; |
271 timer._indexOrNext = null; | 289 timer._indexOrNext = null; |
272 pendingTimers.add(timer); | 290 pendingTimers.add(timer); |
273 return pendingTimers; | 291 return pendingTimers; |
274 } | 292 } |
275 | 293 |
| 294 |
276 static void _notifyEventHandler() { | 295 static void _notifyEventHandler() { |
277 if (_handlingCallbacks) { | 296 if (_handlingCallbacks) { |
278 // While we are already handling callbacks we will not notify the event | 297 // While we are already handling callbacks we will not notify the event |
279 // handler. _handleTimeout will call _notifyEventHandler once all pending | 298 // handler. _handleTimeout will call _notifyEventHandler once all pending |
280 // timers are processed. | 299 // timers are processed. |
281 return; | 300 return; |
282 } | 301 } |
283 | 302 |
284 // If there are no pending timers. Close down the receive port. | 303 // If there are no pending timers. Close down the receive port. |
285 if ((_firstZeroTimer == null) && _heap.isEmpty) { | 304 if ((_firstZeroTimer == null) && _heap.isEmpty) { |
(...skipping 12 matching lines...) Expand all Loading... |
298 | 317 |
299 // Only send a message if the requested wakeup time differs from the | 318 // Only send a message if the requested wakeup time differs from the |
300 // already scheduled wakeup time. | 319 // already scheduled wakeup time. |
301 var wakeupTime = _heap.first._wakeupTime; | 320 var wakeupTime = _heap.first._wakeupTime; |
302 if ((_scheduledWakeupTime == null) || | 321 if ((_scheduledWakeupTime == null) || |
303 (wakeupTime != _scheduledWakeupTime)) { | 322 (wakeupTime != _scheduledWakeupTime)) { |
304 _scheduleWakeup(wakeupTime); | 323 _scheduleWakeup(wakeupTime); |
305 } | 324 } |
306 } | 325 } |
307 | 326 |
| 327 |
308 static List _queueFromTimeoutEvent() { | 328 static List _queueFromTimeoutEvent() { |
309 var pendingTimers = new List(); | 329 var pendingTimers = new List(); |
310 if (_firstZeroTimer != null) { | 330 if (_firstZeroTimer != null) { |
311 // Collect pending timers from the timer heap that have an expiration | 331 // Collect pending timers from the timer heap that have an expiration |
312 // prior to the next zero timer. | 332 // prior to the next zero timer. |
313 // By definition the first zero timer has been scheduled before the | 333 // By definition the first zero timer has been scheduled before the |
314 // current time, meaning all timers which are "less than" the first zero | 334 // current time, meaning all timers which are "less than" the first zero |
315 // timer are expired. The first zero timer will be dispatched when its | 335 // timer are expired. The first zero timer will be dispatched when its |
316 // corresponding message is delivered. | 336 // corresponding message is delivered. |
317 var timer; | 337 var timer; |
318 while (!_heap.isEmpty && (_heap.first._compareTo(_firstZeroTimer) < 0)) { | 338 while (!_heap.isEmpty && (_heap.first._compareTo(_firstZeroTimer) < 0)) { |
319 timer = _heap.removeFirst(); | 339 timer = _heap.removeFirst(); |
320 pendingTimers.add(timer); | 340 pendingTimers.add(timer); |
321 } | 341 } |
322 } else { | 342 } else { |
323 // Collect pending timers from the timer heap which have expired at this | 343 // Collect pending timers from the timer heap which have expired at this |
324 // time. | 344 // time. |
325 var currentTime = VMLibraryHooks.timerMillisecondClock(); | 345 var currentTime = VMLibraryHooks.timerMillisecondClock(); |
326 var timer; | 346 var timer; |
327 while (!_heap.isEmpty && (_heap.first._wakeupTime <= currentTime)) { | 347 while (!_heap.isEmpty && (_heap.first._wakeupTime <= currentTime)) { |
328 timer = _heap.removeFirst(); | 348 timer = _heap.removeFirst(); |
329 pendingTimers.add(timer); | 349 pendingTimers.add(timer); |
330 } | 350 } |
331 } | 351 } |
332 return pendingTimers; | 352 return pendingTimers; |
333 } | 353 } |
334 | 354 |
| 355 |
335 static void _runTimers(List pendingTimers) { | 356 static void _runTimers(List pendingTimers) { |
336 // If there are no pending timers currently reset the id space before we | 357 // If there are no pending timers currently reset the id space before we |
337 // have a chance to enqueue new timers. | 358 // have a chance to enqueue new timers. |
338 if (_heap.isEmpty && (_firstZeroTimer == null)) { | 359 if (_heap.isEmpty && (_firstZeroTimer == null)) { |
339 _idCount = 0; | 360 _idCount = 0; |
340 } | 361 } |
341 | 362 |
342 // Fast exit if no pending timers. | 363 // Fast exit if no pending timers. |
343 if (pendingTimers.length == 0) { | 364 if (pendingTimers.length == 0) { |
344 return; | 365 return; |
(...skipping 29 matching lines...) Expand all Loading... |
374 if (immediateCallback != null) { | 395 if (immediateCallback != null) { |
375 immediateCallback(); | 396 immediateCallback(); |
376 } | 397 } |
377 } | 398 } |
378 } | 399 } |
379 } finally { | 400 } finally { |
380 _handlingCallbacks = false; | 401 _handlingCallbacks = false; |
381 } | 402 } |
382 } | 403 } |
383 | 404 |
| 405 |
384 static void _handleMessage(msg) { | 406 static void _handleMessage(msg) { |
385 var pendingTimers; | 407 var pendingTimers; |
386 if (msg == _ZERO_EVENT) { | 408 if (msg == _ZERO_EVENT) { |
387 pendingTimers = _queueFromZeroEvent(); | 409 pendingTimers = _queueFromZeroEvent(); |
388 assert(pendingTimers.length > 0); | 410 assert(pendingTimers.length > 0); |
389 } else { | 411 } else { |
390 assert(msg == _TIMEOUT_EVENT); | 412 assert(msg == _TIMEOUT_EVENT); |
391 _scheduledWakeupTime = null; // Consumed the last scheduled wakeup now. | 413 _scheduledWakeupTime = null; // Consumed the last scheduled wakeup now. |
392 pendingTimers = _queueFromTimeoutEvent(); | 414 pendingTimers = _queueFromTimeoutEvent(); |
393 } | 415 } |
394 _runTimers(pendingTimers); | 416 _runTimers(pendingTimers); |
395 // Notify the event handler or shutdown the port if no more pending | 417 // Notify the event handler or shutdown the port if no more pending |
396 // timers are present. | 418 // timers are present. |
397 _notifyEventHandler(); | 419 _notifyEventHandler(); |
398 } | 420 } |
399 | 421 |
| 422 |
400 // Tell the event handler to wake this isolate at a specific time. | 423 // Tell the event handler to wake this isolate at a specific time. |
401 static void _scheduleWakeup(int wakeupTime) { | 424 static void _scheduleWakeup(int wakeupTime) { |
402 if (_sendPort == null) { | 425 if (_sendPort == null) { |
403 _createTimerHandler(); | 426 _createTimerHandler(); |
404 } | 427 } |
405 VMLibraryHooks.eventHandlerSendData(null, _sendPort, wakeupTime); | 428 VMLibraryHooks.eventHandlerSendData(null, _sendPort, wakeupTime); |
406 _scheduledWakeupTime = wakeupTime; | 429 _scheduledWakeupTime = wakeupTime; |
407 } | 430 } |
408 | 431 |
| 432 |
409 // Cancel pending wakeups in the event handler. | 433 // Cancel pending wakeups in the event handler. |
410 static void _cancelWakeup() { | 434 static void _cancelWakeup() { |
411 assert(_sendPort != null); | 435 assert(_sendPort != null); |
412 VMLibraryHooks.eventHandlerSendData(null, _sendPort, _NO_TIMER); | 436 VMLibraryHooks.eventHandlerSendData(null, _sendPort, _NO_TIMER); |
413 _scheduledWakeupTime = null; | 437 _scheduledWakeupTime = null; |
414 } | 438 } |
415 | 439 |
| 440 |
416 // Create a receive port and register a message handler for the timer | 441 // Create a receive port and register a message handler for the timer |
417 // events. | 442 // events. |
418 static void _createTimerHandler() { | 443 static void _createTimerHandler() { |
419 assert(_receivePort == null); | 444 assert(_receivePort == null); |
420 assert(_sendPort == null); | 445 assert(_sendPort == null); |
421 _receivePort = new RawReceivePort(_handleMessage); | 446 _receivePort = new RawReceivePort(_handleMessage); |
422 _sendPort = _receivePort.sendPort; | 447 _sendPort = _receivePort.sendPort; |
423 _scheduledWakeupTime = null; | 448 _scheduledWakeupTime = null; |
424 } | 449 } |
425 | 450 |
| 451 |
426 static void _shutdownTimerHandler() { | 452 static void _shutdownTimerHandler() { |
427 _receivePort.close(); | 453 _receivePort.close(); |
428 _receivePort = null; | 454 _receivePort = null; |
429 _sendPort = null; | 455 _sendPort = null; |
430 _scheduledWakeupTime = null; | 456 _scheduledWakeupTime = null; |
431 } | 457 } |
432 | 458 |
| 459 |
433 // The Timer factory registered with the dart:async library by the embedder. | 460 // The Timer factory registered with the dart:async library by the embedder. |
434 static Timer _factory( | 461 static Timer _factory(int milliSeconds, |
435 int milliSeconds, void callback(Timer timer), bool repeating) { | 462 void callback(Timer timer), |
| 463 bool repeating) { |
436 if (repeating) { | 464 if (repeating) { |
437 return new _Timer.periodic(milliSeconds, callback); | 465 return new _Timer.periodic(milliSeconds, callback); |
438 } | 466 } |
439 return new _Timer(milliSeconds, callback); | 467 return new _Timer(milliSeconds, callback); |
440 } | 468 } |
441 } | 469 } |
442 | 470 |
| 471 |
443 _setupHooks() { | 472 _setupHooks() { |
444 VMLibraryHooks.timerFactory = _Timer._factory; | 473 VMLibraryHooks.timerFactory = _Timer._factory; |
445 } | 474 } |
OLD | NEW |