| // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | |
| // for details. All rights reserved. Use of this source code is governed by a | |
| // BSD-style license that can be found in the LICENSE file. | |
| // part of "isolate_patch.dart"; | |
| // Timer heap implemented as a array-based binary heap[0]. | |
| // This allows for O(1) `first`, O(log(n)) `remove`/`removeFirst` and O(log(n)) | |
| // `add`. | |
| // | |
| // To ensure the timers are ordered by insertion time, the _Timer class has a | |
| // `_id` field set when added to the heap. | |
| // | |
| // [0] http://en.wikipedia.org/wiki/Binary_heap | |
| class _TimerHeap { | |
| List<_Timer> _list; | |
| int _used = 0; | |
| _TimerHeap([int initSize = 7]) : _list = new List<_Timer>(initSize); | |
| bool get isEmpty => _used == 0; | |
| _Timer get first => _list[0]; | |
| bool isFirst(_Timer timer) => timer._indexOrNext == 0; | |
| void add(_Timer timer) { | |
| if (_used == _list.length) { | |
| _resize(); | |
| } | |
| timer._indexOrNext = _used++; | |
| _list[timer._indexOrNext] = timer; | |
| _bubbleUp(timer); | |
| } | |
| _Timer removeFirst() { | |
| var f = first; | |
| remove(f); | |
| return f; | |
| } | |
| void remove(_Timer timer) { | |
| _used--; | |
| if (isEmpty) { | |
| _list[0] = null; | |
| timer._indexOrNext = null; | |
| return; | |
| } | |
| var last = _list[_used]; | |
| if (!identical(last, timer)) { | |
| last._indexOrNext = timer._indexOrNext; | |
| _list[last._indexOrNext] = last; | |
| if (last._compareTo(timer) < 0) { | |
| _bubbleUp(last); | |
| } else { | |
| _bubbleDown(last); | |
| } | |
| } | |
| _list[_used] = null; | |
| timer._indexOrNext = null; | |
| } | |
| void _resize() { | |
| var newList = new List<_Timer>(_list.length * 2 + 1); | |
| newList.setRange(0, _used, _list); | |
| _list = newList; | |
| } | |
| void _bubbleUp(_Timer timer) { | |
| while (!isFirst(timer)) { | |
| Timer parent = _parent(timer); | |
| if (timer._compareTo(parent) < 0) { | |
| _swap(timer, parent); | |
| } else { | |
| break; | |
| } | |
| } | |
| } | |
| void _bubbleDown(_Timer timer) { | |
| while (true) { | |
| int leftIndex = _leftChildIndex(timer._indexOrNext); | |
| int rightIndex = _rightChildIndex(timer._indexOrNext); | |
| _Timer newest = timer; | |
| if (leftIndex < _used && _list[leftIndex]._compareTo(newest) < 0) { | |
| newest = _list[leftIndex]; | |
| } | |
| if (rightIndex < _used && _list[rightIndex]._compareTo(newest) < 0) { | |
| newest = _list[rightIndex]; | |
| } | |
| if (identical(newest, timer)) { | |
| // We are where we should be, break. | |
| break; | |
| } | |
| _swap(newest, timer); | |
| } | |
| } | |
| void _swap(_Timer first, _Timer second) { | |
| int tmp = first._indexOrNext; | |
| first._indexOrNext = second._indexOrNext; | |
| second._indexOrNext = tmp; | |
| _list[first._indexOrNext] = first; | |
| _list[second._indexOrNext] = second; | |
| } | |
| Timer _parent(_Timer timer) => _list[_parentIndex(timer._indexOrNext)]; | |
| Timer _leftChild(_Timer timer) => _list[_leftChildIndex(timer._indexOrNext)]; | |
| Timer _rightChild(_Timer timer) => | |
| _list[_rightChildIndex(timer._indexOrNext)]; | |
| static int _parentIndex(int index) => (index - 1) ~/ 2; | |
| static int _leftChildIndex(int index) => 2 * index + 1; | |
| static int _rightChildIndex(int index) => 2 * index + 2; | |
| } | |
| class _Timer implements Timer { | |
| // Cancels the timer in the event handler. | |
| static const _NO_TIMER = -1; | |
| // We distinguish what kind of message arrived based on the value being sent. | |
| static const _ZERO_EVENT = 1; | |
| static const _TIMEOUT_EVENT = null; | |
| // Timers are ordered by wakeup time. Timers with a timeout value of > 0 do | |
| // end up on the TimerHeap. Timers with a timeout of 0 are queued in a list. | |
| static final _heap = new _TimerHeap(); | |
| static _Timer _firstZeroTimer; | |
| static _Timer _lastZeroTimer; | |
| // We use an id to be able to sort timers with the same expiration time. | |
| // ids are recycled after ID_MASK enqueues or when the timer queue is empty. | |
| static const _ID_MASK = 0x1fffffff; | |
| static int _idCount = 0; | |
| static RawReceivePort _receivePort; | |
| static SendPort _sendPort; | |
| static int _scheduledWakeupTime; | |
| static bool _handlingCallbacks = false; | |
| Function _callback; // Closure to call when timer fires. null if canceled. | |
| int _wakeupTime; // Expiration time. | |
| final int _milliSeconds; // Duration specified at creation. | |
| final bool _repeating; // Indicates periodic timers. | |
| var _indexOrNext; // Index if part of the TimerHeap, link otherwise. | |
| int _id; // Incrementing id to enable sorting of timers with same expiry. | |
| int _tick = 0; // Backing for [tick], | |
| // Get the next available id. We accept collisions and reordering when the | |
| // _idCount overflows and the timers expire at the same millisecond. | |
| static int _nextId() { | |
| var result = _idCount; | |
| _idCount = (_idCount + 1) & _ID_MASK; | |
| return result; | |
| } | |
| _Timer._internal( | |
| this._callback, this._wakeupTime, this._milliSeconds, this._repeating) | |
| : _id = _nextId(); | |
| static Timer _createTimer( | |
| void callback(Timer timer), int milliSeconds, bool repeating) { | |
| // Negative timeouts are treated as if 0 timeout. | |
| if (milliSeconds < 0) { | |
| milliSeconds = 0; | |
| } | |
| // Add one because DateTime.now() is assumed to round down | |
| // to nearest millisecond, not up, so that time + duration is before | |
| // duration milliseconds from now. Using microsecond timers like | |
| // Stopwatch allows detecting that the timer fires early. | |
| int now = VMLibraryHooks.timerMillisecondClock(); | |
| int wakeupTime = (milliSeconds == 0) ? now : (now + 1 + milliSeconds); | |
| _Timer timer = | |
| new _Timer._internal(callback, wakeupTime, milliSeconds, repeating); | |
| // Enqueue this newly created timer in the appropriate structure and | |
| // notify if necessary. | |
| timer._enqueue(); | |
| return timer; | |
| } | |
| factory _Timer(int milliSeconds, void callback(Timer timer)) { | |
| return _createTimer(callback, milliSeconds, false); | |
| } | |
| factory _Timer.periodic(int milliSeconds, void callback(Timer timer)) { | |
| return _createTimer(callback, milliSeconds, true); | |
| } | |
| bool get _isInHeap => _indexOrNext is int; | |
| int _compareTo(_Timer other) { | |
| int c = _wakeupTime - other._wakeupTime; | |
| if (c != 0) return c; | |
| return _id - other._id; | |
| } | |
| bool get isActive => _callback != null; | |
| int get tick => _tick; | |
| // Cancels a set timer. The timer is removed from the timer heap if it is a | |
| // non-zero timer. Zero timers are kept in the list as they need to consume | |
| // the corresponding pending message. | |
| void cancel() { | |
| _callback = null; | |
| // Only heap timers are really removed. Zero timers need to consume their | |
| // corresponding wakeup message so they are left in the queue. | |
| if (!_isInHeap) return; | |
| bool update = _heap.isFirst(this); | |
| _heap.remove(this); | |
| if (update) { | |
| _notifyEventHandler(); | |
| } | |
| } | |
| void _advanceWakeupTime() { | |
| // Recalculate the next wakeup time. For repeating timers with a 0 timeout | |
| // the next wakeup time is now. | |
| _id = _nextId(); | |
| if (_milliSeconds > 0) { | |
| _wakeupTime += _milliSeconds; | |
| } else { | |
| _wakeupTime = VMLibraryHooks.timerMillisecondClock(); | |
| } | |
| } | |
| // Adds a timer to the heap or timer list. Timers with the same wakeup time | |
| // are enqueued in order and notified in FIFO order. | |
| void _enqueue() { | |
| if (_milliSeconds == 0) { | |
| if (_firstZeroTimer == null) { | |
| _lastZeroTimer = this; | |
| _firstZeroTimer = this; | |
| } else { | |
| _lastZeroTimer._indexOrNext = this; | |
| _lastZeroTimer = this; | |
| } | |
| // Every zero timer gets its own event. | |
| _notifyZeroHandler(); | |
| } else { | |
| _heap.add(this); | |
| if (_heap.isFirst(this)) { | |
| _notifyEventHandler(); | |
| } | |
| } | |
| } | |
| // Enqueue one message for each zero timer. To be able to distinguish from | |
| // EventHandler messages we send a _ZERO_EVENT instead of a _TIMEOUT_EVENT. | |
| static void _notifyZeroHandler() { | |
| if (_sendPort == null) { | |
| _createTimerHandler(); | |
| } | |
| _sendPort.send(_ZERO_EVENT); | |
| } | |
| // Handle the notification of a zero timer. Make sure to also execute non-zero | |
| // timers with a lower expiration time. | |
| static List _queueFromZeroEvent() { | |
| var pendingTimers = new List(); | |
| assert(_firstZeroTimer != null); | |
| // Collect pending timers from the timer heap that have an expiration prior | |
| // to the currently notified zero timer. | |
| var timer; | |
| while (!_heap.isEmpty && (_heap.first._compareTo(_firstZeroTimer) < 0)) { | |
| timer = _heap.removeFirst(); | |
| pendingTimers.add(timer); | |
| } | |
| // Append the first zero timer to the pending timers. | |
| timer = _firstZeroTimer; | |
| _firstZeroTimer = timer._indexOrNext; | |
| timer._indexOrNext = null; | |
| pendingTimers.add(timer); | |
| return pendingTimers; | |
| } | |
| static void _notifyEventHandler() { | |
| if (_handlingCallbacks) { | |
| // While we are already handling callbacks we will not notify the event | |
| // handler. _handleTimeout will call _notifyEventHandler once all pending | |
| // timers are processed. | |
| return; | |
| } | |
| // If there are no pending timers. Close down the receive port. | |
| if ((_firstZeroTimer == null) && _heap.isEmpty) { | |
| // No pending timers: Close the receive port and let the event handler | |
| // know. | |
| if (_sendPort != null) { | |
| _cancelWakeup(); | |
| _shutdownTimerHandler(); | |
| } | |
| return; | |
| } else if (_heap.isEmpty) { | |
| // Only zero timers are left. Cancel any scheduled wakeups. | |
| _cancelWakeup(); | |
| return; | |
| } | |
| // Only send a message if the requested wakeup time differs from the | |
| // already scheduled wakeup time. | |
| var wakeupTime = _heap.first._wakeupTime; | |
| if ((_scheduledWakeupTime == null) || | |
| (wakeupTime != _scheduledWakeupTime)) { | |
| _scheduleWakeup(wakeupTime); | |
| } | |
| } | |
| static List _queueFromTimeoutEvent() { | |
| var pendingTimers = new List(); | |
| if (_firstZeroTimer != null) { | |
| // Collect pending timers from the timer heap that have an expiration | |
| // prior to the next zero timer. | |
| // By definition the first zero timer has been scheduled before the | |
| // current time, meaning all timers which are "less than" the first zero | |
| // timer are expired. The first zero timer will be dispatched when its | |
| // corresponding message is delivered. | |
| var timer; | |
| while (!_heap.isEmpty && (_heap.first._compareTo(_firstZeroTimer) < 0)) { | |
| timer = _heap.removeFirst(); | |
| pendingTimers.add(timer); | |
| } | |
| } else { | |
| // Collect pending timers from the timer heap which have expired at this | |
| // time. | |
| var currentTime = VMLibraryHooks.timerMillisecondClock(); | |
| var timer; | |
| while (!_heap.isEmpty && (_heap.first._wakeupTime <= currentTime)) { | |
| timer = _heap.removeFirst(); | |
| pendingTimers.add(timer); | |
| } | |
| } | |
| return pendingTimers; | |
| } | |
| static void _runTimers(List pendingTimers) { | |
| // If there are no pending timers currently reset the id space before we | |
| // have a chance to enqueue new timers. | |
| if (_heap.isEmpty && (_firstZeroTimer == null)) { | |
| _idCount = 0; | |
| } | |
| // Fast exit if no pending timers. | |
| if (pendingTimers.length == 0) { | |
| return; | |
| } | |
| // Trigger all of the pending timers. New timers added as part of the | |
| // callbacks will be enqueued now and notified in the next spin at the | |
| // earliest. | |
| _handlingCallbacks = true; | |
| var i = 0; | |
| try { | |
| for (; i < pendingTimers.length; i++) { | |
| // Next pending timer. | |
| var timer = pendingTimers[i]; | |
| timer._indexOrNext = null; | |
| // One of the timers in the pending_timers list can cancel | |
| // one of the later timers which will set the callback to | |
| // null. Or the pending zero timer has been canceled earlier. | |
| if (timer._callback != null) { | |
| var callback = timer._callback; | |
| if (!timer._repeating) { | |
| // Mark timer as inactive. | |
| timer._callback = null; | |
| } else if (timer._milliSeconds > 0) { | |
| var ms = timer._milliSeconds; | |
| int overdue = | |
| VMLibraryHooks.timerMillisecondClock() - timer._wakeupTime; | |
| if (overdue > ms) { | |
| int missedTicks = overdue ~/ ms; | |
| timer._wakeupTime += missedTicks * ms; | |
| timer._tick += missedTicks; | |
| } | |
| } | |
| timer._tick += 1; | |
| callback(timer); | |
| // Re-insert repeating timer if not canceled. | |
| if (timer._repeating && (timer._callback != null)) { | |
| timer._advanceWakeupTime(); | |
| timer._enqueue(); | |
| } | |
| // Execute pending micro tasks. | |
| var immediateCallback = _removePendingImmediateCallback(); | |
| if (immediateCallback != null) { | |
| immediateCallback(); | |
| } | |
| } | |
| } | |
| } finally { | |
| _handlingCallbacks = false; | |
| // Re-queue timers we didn't get to. | |
| for (i++; i < pendingTimers.length; i++) { | |
| var timer = pendingTimers[i]; | |
| timer._enqueue(); | |
| } | |
| _notifyEventHandler(); | |
| } | |
| } | |
| static void _handleMessage(msg) { | |
| var pendingTimers; | |
| if (msg == _ZERO_EVENT) { | |
| pendingTimers = _queueFromZeroEvent(); | |
| assert(pendingTimers.length > 0); | |
| } else { | |
| assert(msg == _TIMEOUT_EVENT); | |
| _scheduledWakeupTime = null; // Consumed the last scheduled wakeup now. | |
| pendingTimers = _queueFromTimeoutEvent(); | |
| } | |
| _runTimers(pendingTimers); | |
| // Notify the event handler or shutdown the port if no more pending | |
| // timers are present. | |
| _notifyEventHandler(); | |
| } | |
| // Tell the event handler to wake this isolate at a specific time. | |
| static void _scheduleWakeup(int wakeupTime) { | |
| if (_sendPort == null) { | |
| _createTimerHandler(); | |
| } | |
| VMLibraryHooks.eventHandlerSendData(null, _sendPort, wakeupTime); | |
| _scheduledWakeupTime = wakeupTime; | |
| } | |
| // Cancel pending wakeups in the event handler. | |
| static void _cancelWakeup() { | |
| if (_sendPort != null) { | |
| VMLibraryHooks.eventHandlerSendData(null, _sendPort, _NO_TIMER); | |
| _scheduledWakeupTime = null; | |
| } | |
| } | |
| // Create a receive port and register a message handler for the timer | |
| // events. | |
| static void _createTimerHandler() { | |
| assert(_receivePort == null); | |
| assert(_sendPort == null); | |
| _receivePort = new RawReceivePort(_handleMessage); | |
| _sendPort = _receivePort.sendPort; | |
| _scheduledWakeupTime = null; | |
| } | |
| static void _shutdownTimerHandler() { | |
| _receivePort.close(); | |
| _receivePort = null; | |
| _sendPort = null; | |
| _scheduledWakeupTime = null; | |
| } | |
| // The Timer factory registered with the dart:async library by the embedder. | |
| static Timer _factory( | |
| int milliSeconds, void callback(Timer timer), bool repeating) { | |
| if (repeating) { | |
| return new _Timer.periodic(milliSeconds, callback); | |
| } | |
| return new _Timer(milliSeconds, callback); | |
| } | |
| } | |
| @pragma("vm:entry-point", "call") | |
| _setupHooks() { | |
| VMLibraryHooks.timerFactory = _Timer._factory; | |
| } |