Index: sdk/lib/io/timer_impl.dart |
diff --git a/sdk/lib/io/timer_impl.dart b/sdk/lib/io/timer_impl.dart |
index ecbf17f451ee6f6d292e1e46f66846415370f823..883d09e42488bbefb6614636d2d12a9e363f82c4 100644 |
--- a/sdk/lib/io/timer_impl.dart |
+++ b/sdk/lib/io/timer_impl.dart |
@@ -4,135 +4,19 @@ |
part of dart.io; |
-// 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]; |
- 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 (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 { |
+class _Timer extends LinkedListEntry<_Timer> implements Timer { |
// Disables the timer. |
static const int _NO_TIMER = -1; |
// Timers are ordered by wakeup time. |
- static _TimerHeap _heap = new _TimerHeap(); |
- static _Timer _firstZeroTimer; |
- static _Timer _lastZeroTimer; |
- static int _idCount = 0; |
+ static LinkedList<_Timer> _timers = new LinkedList<_Timer>(); |
static RawReceivePort _receivePort; |
- static bool _handlingCallbacks = false; |
+ static bool _handling_callbacks = false; |
Function _callback; |
int _milliSeconds; |
int _wakeupTime = 0; |
- var _indexOrNext; |
- int _id = -1; |
static Timer _createTimer(void callback(Timer timer), |
int milliSeconds, |
@@ -148,7 +32,8 @@ class _Timer implements Timer { |
new DateTime.now().millisecondsSinceEpoch + 1 + milliSeconds; |
} |
timer._milliSeconds = repeating ? milliSeconds : -1; |
- if (timer._addTimerToHeap()) { |
+ timer._addTimerToList(); |
+ if (identical(timer, _timers.first)) { |
// The new timer is the first in queue. Update event handler. |
timer._notifyEventHandler(); |
} |
@@ -165,16 +50,10 @@ class _Timer implements Timer { |
_Timer._internal() {} |
- bool get _isInHeap => _id >= 0; |
- |
void _clear() { |
_callback = null; |
- } |
- |
- int _compareTo(_Timer other) { |
- int c = _wakeupTime - other._wakeupTime; |
- if (c != 0) return c; |
- return _id - other._id; |
+ _milliSeconds = 0; |
+ _wakeupTime = 0; |
} |
bool get _repeating => _milliSeconds >= 0; |
@@ -185,11 +64,12 @@ class _Timer implements Timer { |
// the given timer is the earliest timer the native timer is reset. |
void cancel() { |
_clear(); |
- if (!_isInHeap) return; |
- assert(_wakeupTime != 0); |
- bool update = _firstZeroTimer == null && _heap.isFirst(this); |
- _heap.remove(this); |
- if (update) { |
+ // Return if already canceled. |
+ if (list == null) return; |
+ assert(!_timers.isEmpty); |
+ _Timer first = _timers.first; |
+ unlink(); |
+ if (identical(first, this)) { |
_notifyEventHandler(); |
} |
} |
@@ -201,32 +81,34 @@ class _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. |
- bool _addTimerToHeap() { |
- if (_wakeupTime == 0) { |
- if (_firstZeroTimer == null) { |
- _lastZeroTimer = _firstZeroTimer = this; |
- return true; |
- } else { |
- _lastZeroTimer = _lastZeroTimer._indexOrNext = this; |
- return false; |
+ 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; |
} |
- } else { |
- _id = _idCount++; |
- _heap.add(this); |
- return _firstZeroTimer == null && _heap.isFirst(this); |
+ entry = entry.next; |
} |
+ _timers.add(this); |
} |
void _notifyEventHandler() { |
- if (_handlingCallbacks) { |
+ if (_handling_callbacks) { |
// 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) { |
+ if (_timers.isEmpty) { |
// No pending timers: Close the receive port and let the event handler |
// know. |
if (_receivePort != null) { |
@@ -241,63 +123,61 @@ class _Timer implements Timer { |
} |
_EventHandler._sendData(null, |
_receivePort, |
- _firstZeroTimer != null ? |
- 0 : _heap.first._wakeupTime); |
+ _timers.first._wakeupTime); |
} |
} |
- 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; |
+ |
+ // 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; |
+ } |
} |
- } |
- // 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(); |
+ // 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(); |
+ } |
} |
} |
- timer = next; |
+ } finally { |
+ _handling_callbacks = false; |
+ _notifyEventHandler(); |
} |
- } finally { |
- _handlingCallbacks = false; |
- _notifyEventHandler(); |
} |
- } |
- // Creates a receive port and registers the timer handler on that |
- // receive port. |
- void _createTimerHandler() { |
if(_receivePort == null) { |
- _receivePort = new RawReceivePort(_handleTimeout); |
+ _receivePort = new RawReceivePort((_) { _handleTimeout(); }); |
} |
} |