Index: sdk/lib/io/timer_impl.dart |
diff --git a/sdk/lib/io/timer_impl.dart b/sdk/lib/io/timer_impl.dart |
index 883d09e42488bbefb6614636d2d12a9e363f82c4..5396a6aa0d6afb0d656b8c4e0adf053df236a39e 100644 |
--- a/sdk/lib/io/timer_impl.dart |
+++ b/sdk/lib/io/timer_impl.dart |
@@ -4,19 +4,137 @@ |
part of dart.io; |
-class _Timer extends LinkedListEntry<_Timer> implements Timer { |
+// 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; |
+ bool get isNotEmpty => _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--; |
+ timer._id = -1; |
+ 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 { |
// Disables the timer. |
static const int _NO_TIMER = -1; |
// Timers are ordered by wakeup time. |
- static LinkedList<_Timer> _timers = new LinkedList<_Timer>(); |
+ static _TimerHeap _heap = new _TimerHeap(); |
+ static _Timer _firstZeroTimer; |
+ static _Timer _lastZeroTimer; |
+ static int _idCount = 0; |
static RawReceivePort _receivePort; |
- static bool _handling_callbacks = false; |
+ static bool _handlingCallbacks = false; |
Function _callback; |
int _milliSeconds; |
int _wakeupTime = 0; |
+ var _indexOrNext; |
+ int _id = -1; |
static Timer _createTimer(void callback(Timer timer), |
int milliSeconds, |
@@ -32,10 +150,9 @@ class _Timer extends LinkedListEntry<_Timer> implements Timer { |
new DateTime.now().millisecondsSinceEpoch + 1 + milliSeconds; |
} |
timer._milliSeconds = repeating ? milliSeconds : -1; |
- timer._addTimerToList(); |
- if (identical(timer, _timers.first)) { |
+ if (timer._addTimerToHeap()) { |
// The new timer is the first in queue. Update event handler. |
- timer._notifyEventHandler(); |
+ _notifyEventHandler(); |
} |
return timer; |
} |
@@ -50,10 +167,16 @@ class _Timer extends LinkedListEntry<_Timer> implements Timer { |
_Timer._internal() {} |
+ bool get _isInHeap => _id >= 0; |
+ |
void _clear() { |
_callback = null; |
- _milliSeconds = 0; |
- _wakeupTime = 0; |
+ } |
+ |
+ int _compareTo(_Timer other) { |
+ int c = _wakeupTime - other._wakeupTime; |
+ if (c != 0) return c; |
+ return _id - other._id; |
} |
bool get _repeating => _milliSeconds >= 0; |
@@ -64,12 +187,11 @@ class _Timer extends LinkedListEntry<_Timer> implements Timer { |
// the given timer is the earliest timer the native timer is reset. |
void cancel() { |
_clear(); |
- // Return if already canceled. |
- if (list == null) return; |
- assert(!_timers.isEmpty); |
- _Timer first = _timers.first; |
- unlink(); |
- if (identical(first, this)) { |
+ if (!_isInHeap) return; |
+ assert(_wakeupTime != 0); |
+ bool update = _firstZeroTimer == null && _heap.isFirst(this); |
+ _heap.remove(this); |
+ if (update) { |
_notifyEventHandler(); |
} |
} |
@@ -81,34 +203,32 @@ class _Timer extends LinkedListEntry<_Timer> implements Timer { |
// Adds a timer to the timer list. Timers with the same wakeup time are |
// enqueued in order and notified in FIFO order. |
- void _addTimerToList() { |
- _Timer entry = _timers.isEmpty ? null : _timers.first; |
- // If timer is last, add to end. |
- if (entry == null || _timers.last._wakeupTime <= _wakeupTime) { |
- _timers.add(this); |
- return; |
- } |
- // Otherwise scan through and find the right position. |
- while (entry != null) { |
- if (_wakeupTime < entry._wakeupTime) { |
- entry.insertBefore(this); |
- return; |
+ bool _addTimerToHeap() { |
+ if (_wakeupTime == 0) { |
+ if (_firstZeroTimer == null) { |
+ _lastZeroTimer = _firstZeroTimer = this; |
+ return true; |
+ } else { |
+ _lastZeroTimer = _lastZeroTimer._indexOrNext = this; |
+ return false; |
} |
- entry = entry.next; |
+ } else { |
+ _id = _idCount++; |
+ _heap.add(this); |
+ return _firstZeroTimer == null && _heap.isFirst(this); |
} |
- _timers.add(this); |
} |
- void _notifyEventHandler() { |
- if (_handling_callbacks) { |
+ 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 (_timers.isEmpty) { |
+ if (_firstZeroTimer == null && _heap.isEmpty) { |
// No pending timers: Close the receive port and let the event handler |
// know. |
if (_receivePort != null) { |
@@ -123,65 +243,67 @@ class _Timer extends LinkedListEntry<_Timer> implements Timer { |
} |
_EventHandler._sendData(null, |
_receivePort, |
- _timers.first._wakeupTime); |
+ _firstZeroTimer != null ? |
+ 0 : _heap.first._wakeupTime); |
} |
} |
- |
- // Creates a receive port and registers the timer handler on that |
- // receive port. |
- void _createTimerHandler() { |
- |
- void _handleTimeout() { |
- int currentTime = new DateTime.now().millisecondsSinceEpoch; |
- |
- // Collect all pending timers. |
- var pending_timers = new List(); |
- while (!_timers.isEmpty) { |
- _Timer entry = _timers.first; |
- if (entry._wakeupTime <= currentTime) { |
- entry.unlink(); |
- pending_timers.add(entry); |
- } else { |
- break; |
- } |
+ static void _handleTimeout(_) { |
+ int currentTime = new DateTime.now().millisecondsSinceEpoch; |
+ // Collect all pending timers. |
+ var timer = _firstZeroTimer; |
+ var nextTimer = _lastZeroTimer; |
+ _firstZeroTimer = _lastZeroTimer = null; |
+ while (_heap.isNotEmpty && _heap.first._wakeupTime <= currentTime) { |
+ var next = _heap.removeFirst(); |
+ if (timer == null) { |
+ nextTimer = timer = next; |
+ } else { |
+ nextTimer = nextTimer._indexOrNext = next; |
} |
+ } |
- // 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. |
- _handling_callbacks = true; |
- try { |
- for (var timer in pending_timers) { |
- // 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._addTimerToList(); |
- } |
+ // 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 (timer != null) { |
+ var next = 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(); |
} |
} |
- } finally { |
- _handling_callbacks = false; |
- _notifyEventHandler(); |
+ timer = next; |
} |
+ } finally { |
+ _handlingCallbacks = false; |
+ _notifyEventHandler(); |
} |
+ } |
+ // Creates a receive port and registers the timer handler on that |
+ // receive port. |
+ static void _createTimerHandler() { |
if(_receivePort == null) { |
- _receivePort = new RawReceivePort((_) { _handleTimeout(); }); |
+ _receivePort = new RawReceivePort(_handleTimeout); |
} |
} |
- void _shutdownTimerHandler() { |
+ static void _shutdownTimerHandler() { |
_receivePort.close(); |
_receivePort = null; |
} |