| // 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. |
| |
| // 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(_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 int _NO_TIMER = -1; |
| |
| // Timers are ordered by wakeup time. |
| static _TimerHeap _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 int _ID_MASK = 0x1fffffff; |
| static int _idCount = 0; |
| |
| static RawReceivePort _receivePort; |
| static SendPort _sendPort; |
| static int _scheduledWakeupTime; |
| // Keep track whether at least one message is pending in the event loop. This |
| // way we do not have to notify for every pending _firstZeroTimer. |
| static var _messagePending = false; |
| |
| static bool _handlingCallbacks = false; |
| |
| Function _callback; // Closure to call when timer fires. null if canceled. |
| int _wakeupTime; // Expiration time. |
| int _milliSeconds; // Duration specified at creation. |
| 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. |
| |
| // 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 = new DateTime.now().millisecondsSinceEpoch; |
| int wakeupTime = (milliSeconds == 0) ? now : (now + 1 + milliSeconds); |
| |
| _Timer timer = new _Timer._internal(callback, |
| wakeupTime, |
| milliSeconds, |
| repeating); |
| |
| if (timer._addTimerToHeap()) { |
| // The new timer is the first in queue. Update event handler. |
| _notifyEventHandler(); |
| } |
| 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; |
| |
| void _clear() { |
| _callback = null; |
| } |
| |
| int _compareTo(_Timer other) { |
| int c = _wakeupTime - other._wakeupTime; |
| if (c != 0) return c; |
| return _id - other._id; |
| } |
| |
| bool get isActive => _callback != null; |
| |
| // Cancels a set timer. The timer is removed from the timer list and if |
| // the given timer is the earliest timer the event handler is notified. |
| void cancel() { |
| _clear(); |
| if (!_isInHeap) return; |
| // Only heap timers are really removed. Others are just dropped on |
| // notification. |
| bool update = (_firstZeroTimer == null) && _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 = new DateTime.now().millisecondsSinceEpoch; |
| } |
| } |
| |
| // Adds a timer to the heap or timer list. Timers with the same wakeup time |
| // are enqueued in order and notified in FIFO order. |
| bool _addTimerToHeap() { |
| if (_milliSeconds == 0) { |
| if (_firstZeroTimer == null) { |
| _lastZeroTimer = this; |
| _firstZeroTimer = this; |
| return true; |
| } else { |
| _lastZeroTimer._indexOrNext = this; |
| _lastZeroTimer = this; |
| return false; |
| } |
| } else { |
| _heap.add(this); |
| return _firstZeroTimer == null && _heap.isFirst(this); |
| } |
| } |
| |
| |
| 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 ((_firstZeroTimer == null) && _heap.isEmpty) { |
| // No pending timers: Close the receive port and let the event handler |
| // know. |
| if (_receivePort != null) { |
| VMLibraryHooks.eventHandlerSendData(null, _sendPort, _NO_TIMER); |
| _shutdownTimerHandler(); |
| } |
| } else { |
| if (_receivePort == null) { |
| // Create a receive port and register a message handler for the timer |
| // events. |
| _createTimerHandler(); |
| } |
| if (_firstZeroTimer != null) { |
| if (!_messagePending) { |
| _sendPort.send(null); |
| _messagePending = true; // Reset when the port receives a message. |
| } |
| } else { |
| var wakeupTime = _heap.first._wakeupTime; |
| if ((_scheduledWakeupTime == null) || |
| (wakeupTime != _scheduledWakeupTime)) { |
| VMLibraryHooks.eventHandlerSendData(null, _sendPort, wakeupTime); |
| _scheduledWakeupTime = wakeupTime; |
| } |
| } |
| } |
| } |
| |
| static void _handleTimeout() { |
| // Fast exit if no timers have been scheduled. |
| if (_heap.isEmpty && (_firstZeroTimer == null)) { |
| assert(_receivePort == null); |
| return; |
| } |
| |
| // Collect all pending timers. |
| var head = null; |
| var tail = null; |
| if (_heap.isEmpty) { |
| // Only immediate timers are scheduled. Take over the whole list as is. |
| assert(_firstZeroTimer != null); |
| assert(_lastZeroTimer != null); |
| head = _firstZeroTimer; |
| tail = _lastZeroTimer; |
| _firstZeroTimer = null; |
| _lastZeroTimer = null; |
| } else { |
| assert(!_heap.isEmpty); |
| // Keep track of the lowest wakeup times for both the list and heap. If |
| // the respective queue is empty move its time beyond the current time. |
| var currentTime = new DateTime.now().millisecondsSinceEpoch; |
| var heapTime = _heap.first._wakeupTime; |
| var listTime = (_firstZeroTimer == null) ? |
| (currentTime + 1) : _firstZeroTimer._wakeupTime; |
| |
| while ((heapTime <= currentTime) || (listTime <= currentTime)) { |
| var timer; |
| // Consume the timers in order by removing from heap or list based on |
| // their wakeup time and update the queue's time. |
| assert((heapTime != listTime) || |
| ((_heap.first != null) && (_firstZeroTimer != null))); |
| if ((heapTime < listTime) || |
| ((heapTime == listTime) && |
| (_heap.first._id < _firstZeroTimer._id))) { |
| timer = _heap.removeFirst(); |
| heapTime = _heap.isEmpty ? |
| (currentTime + 1) : _heap.first._wakeupTime; |
| } else { |
| timer = _firstZeroTimer; |
| assert(timer._milliSeconds == 0); |
| _firstZeroTimer = timer._indexOrNext; |
| if (_firstZeroTimer == null) { |
| _lastZeroTimer = null; |
| listTime = currentTime + 1; |
| } else { |
| // We want to drain all entries from the list as they should have |
| // been pending for 0 ms. To prevent issues with current time moving |
| // we ensure that the listTime does not go beyond current, unless |
| // the list is empty. |
| listTime = _firstZeroTimer._wakeupTime; |
| if (listTime > currentTime) { |
| listTime = currentTime; |
| } |
| } |
| } |
| |
| // Append this timer to the pending timer list. |
| timer._indexOrNext = null; |
| if (head == null) { |
| assert(tail == null); |
| head = timer; |
| tail = timer; |
| } else { |
| tail._indexOrNext = timer; |
| tail = timer; |
| } |
| } |
| } |
| |
| // No timers queued: Early exit. |
| if (head == null) { |
| return; |
| } |
| |
| // If there are no pending timers currently reset the id space before we |
| // have a chance to enqueue new timers. |
| assert(_firstZeroTimer == null); |
| if (_heap.isEmpty) { |
| _idCount = 0; |
| } |
| |
| // 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; |
| try { |
| while (head != null) { |
| // Dequeue the first candidate timer. |
| var timer = head; |
| head = timer._indexOrNext; |
| 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. |
| if (timer._callback != null) { |
| var callback = timer._callback; |
| if (!timer._repeating) { |
| // Mark timer as inactive. |
| timer._callback = null; |
| } |
| callback(timer); |
| // Re-insert repeating timer if not canceled. |
| if (timer._repeating && (timer._callback != null)) { |
| timer._advanceWakeupTime(); |
| timer._addTimerToHeap(); |
| } |
| // Execute pending micro tasks. |
| _runPendingImmediateCallback(); |
| } |
| } |
| } finally { |
| _handlingCallbacks = false; |
| _notifyEventHandler(); |
| } |
| } |
| |
| // Creates a receive port and registers an empty handler on that port. Just |
| // the triggering of the event loop will ensure that timers are executed. |
| static _ignoreMessage(_) { |
| _messagePending = false; |
| } |
| |
| static void _createTimerHandler() { |
| assert(_receivePort == null); |
| _receivePort = new RawReceivePort(_ignoreMessage); |
| _sendPort = _receivePort.sendPort; |
| _scheduledWakeupTime = null; |
| _messagePending = false; |
| } |
| |
| static void _shutdownTimerHandler() { |
| _receivePort.close(); |
| _receivePort = null; |
| _sendPort = null; |
| _scheduledWakeupTime = null; |
| _messagePending = false; |
| } |
| |
| // 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); |
| } |
| } |
| |
| _setupHooks() { |
| VMLibraryHooks.timerFactory = _Timer._factory; |
| } |
