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 part of dart.io; | 5 part of dart.io; |
6 | 6 |
7 class _Timer extends LinkedListEntry<_Timer> implements Timer { | 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)) |
| 9 // `add`. |
| 10 // |
| 11 // To ensure the timers are ordered by insertion time, the _Timer class has a |
| 12 // `_id` field set when added to the heap. |
| 13 // |
| 14 // [0] http://en.wikipedia.org/wiki/Binary_heap |
| 15 class _TimerHeap { |
| 16 List<_Timer> _list; |
| 17 int _used = 0; |
| 18 |
| 19 _TimerHeap([int initSize = 7]) |
| 20 : _list = new List<_Timer>(initSize); |
| 21 |
| 22 bool get isEmpty => _used == 0; |
| 23 bool get isNotEmpty => _used > 0; |
| 24 |
| 25 _Timer get first => _list[0]; |
| 26 |
| 27 bool isFirst(_Timer timer) => timer._indexOrNext == 0; |
| 28 |
| 29 void add(_Timer timer) { |
| 30 if (_used == _list.length) { |
| 31 _resize(); |
| 32 } |
| 33 timer._indexOrNext = _used++; |
| 34 _list[timer._indexOrNext] = timer; |
| 35 _bubbleUp(timer); |
| 36 } |
| 37 |
| 38 _Timer removeFirst() { |
| 39 var f = first; |
| 40 remove(f); |
| 41 return f; |
| 42 } |
| 43 |
| 44 void remove(_Timer timer) { |
| 45 _used--; |
| 46 timer._id = -1; |
| 47 if (isEmpty) { |
| 48 _list[0] = null; |
| 49 timer._indexOrNext = null; |
| 50 return; |
| 51 } |
| 52 var last = _list[_used]; |
| 53 if (!identical(last, timer)) { |
| 54 last._indexOrNext = timer._indexOrNext; |
| 55 _list[last._indexOrNext] = last; |
| 56 if (last._compareTo(timer) < 0) { |
| 57 _bubbleUp(last); |
| 58 } else { |
| 59 _bubbleDown(last); |
| 60 } |
| 61 } |
| 62 _list[_used] = null; |
| 63 timer._indexOrNext = null; |
| 64 } |
| 65 |
| 66 void _resize() { |
| 67 var newList = new List(_list.length * 2 + 1); |
| 68 newList.setRange(0, _used, _list); |
| 69 _list = newList; |
| 70 } |
| 71 |
| 72 void _bubbleUp(_Timer timer) { |
| 73 while (!isFirst(timer)) { |
| 74 Timer parent = _parent(timer); |
| 75 if (timer._compareTo(parent) < 0) { |
| 76 _swap(timer, parent); |
| 77 } else { |
| 78 break; |
| 79 } |
| 80 } |
| 81 } |
| 82 |
| 83 void _bubbleDown(_Timer timer) { |
| 84 while (true) { |
| 85 int leftIndex = _leftChildIndex(timer._indexOrNext); |
| 86 int rightIndex = _rightChildIndex(timer._indexOrNext); |
| 87 _Timer newest = timer; |
| 88 if (leftIndex < _used && _list[leftIndex]._compareTo(newest) < 0) { |
| 89 newest = _list[leftIndex]; |
| 90 } |
| 91 if (rightIndex < _used && _list[rightIndex]._compareTo(newest) < 0) { |
| 92 newest = _list[rightIndex]; |
| 93 } |
| 94 if (identical(newest, timer)) { |
| 95 // We are where we should be, break. |
| 96 break; |
| 97 } |
| 98 _swap(newest, timer); |
| 99 } |
| 100 } |
| 101 |
| 102 void _swap(_Timer first, _Timer second) { |
| 103 int tmp = first._indexOrNext; |
| 104 first._indexOrNext = second._indexOrNext; |
| 105 second._indexOrNext = tmp; |
| 106 _list[first._indexOrNext] = first; |
| 107 _list[second._indexOrNext] = second; |
| 108 } |
| 109 |
| 110 Timer _parent(_Timer timer) => _list[_parentIndex(timer._indexOrNext)]; |
| 111 Timer _leftChild(_Timer timer) => _list[_leftChildIndex(timer._indexOrNext)]; |
| 112 Timer _rightChild(_Timer timer) => |
| 113 _list[_rightChildIndex(timer._indexOrNext)]; |
| 114 |
| 115 static int _parentIndex(int index) => (index - 1) ~/ 2; |
| 116 static int _leftChildIndex(int index) => 2 * index + 1; |
| 117 static int _rightChildIndex(int index) => 2 * index + 2; |
| 118 } |
| 119 |
| 120 class _Timer implements Timer { |
8 // Disables the timer. | 121 // Disables the timer. |
9 static const int _NO_TIMER = -1; | 122 static const int _NO_TIMER = -1; |
10 | 123 |
11 // Timers are ordered by wakeup time. | 124 // Timers are ordered by wakeup time. |
12 static LinkedList<_Timer> _timers = new LinkedList<_Timer>(); | 125 static _TimerHeap _heap = new _TimerHeap(); |
| 126 static _Timer _firstZeroTimer; |
| 127 static _Timer _lastZeroTimer; |
| 128 static int _idCount = 0; |
13 | 129 |
14 static RawReceivePort _receivePort; | 130 static RawReceivePort _receivePort; |
15 static bool _handling_callbacks = false; | 131 static bool _handlingCallbacks = false; |
16 | 132 |
17 Function _callback; | 133 Function _callback; |
18 int _milliSeconds; | 134 int _milliSeconds; |
19 int _wakeupTime = 0; | 135 int _wakeupTime = 0; |
| 136 var _indexOrNext; |
| 137 int _id = -1; |
20 | 138 |
21 static Timer _createTimer(void callback(Timer timer), | 139 static Timer _createTimer(void callback(Timer timer), |
22 int milliSeconds, | 140 int milliSeconds, |
23 bool repeating) { | 141 bool repeating) { |
24 _Timer timer = new _Timer._internal(); | 142 _Timer timer = new _Timer._internal(); |
25 timer._callback = callback; | 143 timer._callback = callback; |
26 if (milliSeconds > 0) { | 144 if (milliSeconds > 0) { |
27 // Add one because DateTime.now() is assumed to round down | 145 // Add one because DateTime.now() is assumed to round down |
28 // to nearest millisecond, not up, so that time + duration is before | 146 // to nearest millisecond, not up, so that time + duration is before |
29 // duration milliseconds from now. Using micosecond timers like | 147 // duration milliseconds from now. Using micosecond timers like |
30 // Stopwatch allows detecting that the timer fires early. | 148 // Stopwatch allows detecting that the timer fires early. |
31 timer._wakeupTime = | 149 timer._wakeupTime = |
32 new DateTime.now().millisecondsSinceEpoch + 1 + milliSeconds; | 150 new DateTime.now().millisecondsSinceEpoch + 1 + milliSeconds; |
33 } | 151 } |
34 timer._milliSeconds = repeating ? milliSeconds : -1; | 152 timer._milliSeconds = repeating ? milliSeconds : -1; |
35 timer._addTimerToList(); | 153 if (timer._addTimerToHeap()) { |
36 if (identical(timer, _timers.first)) { | |
37 // The new timer is the first in queue. Update event handler. | 154 // The new timer is the first in queue. Update event handler. |
38 timer._notifyEventHandler(); | 155 _notifyEventHandler(); |
39 } | 156 } |
40 return timer; | 157 return timer; |
41 } | 158 } |
42 | 159 |
43 factory _Timer(int milliSeconds, void callback(Timer timer)) { | 160 factory _Timer(int milliSeconds, void callback(Timer timer)) { |
44 return _createTimer(callback, milliSeconds, false); | 161 return _createTimer(callback, milliSeconds, false); |
45 } | 162 } |
46 | 163 |
47 factory _Timer.periodic(int milliSeconds, void callback(Timer timer)) { | 164 factory _Timer.periodic(int milliSeconds, void callback(Timer timer)) { |
48 return _createTimer(callback, milliSeconds, true); | 165 return _createTimer(callback, milliSeconds, true); |
49 } | 166 } |
50 | 167 |
51 _Timer._internal() {} | 168 _Timer._internal() {} |
52 | 169 |
| 170 bool get _isInHeap => _id >= 0; |
| 171 |
53 void _clear() { | 172 void _clear() { |
54 _callback = null; | 173 _callback = null; |
55 _milliSeconds = 0; | 174 } |
56 _wakeupTime = 0; | 175 |
| 176 int _compareTo(_Timer other) { |
| 177 int c = _wakeupTime - other._wakeupTime; |
| 178 if (c != 0) return c; |
| 179 return _id - other._id; |
57 } | 180 } |
58 | 181 |
59 bool get _repeating => _milliSeconds >= 0; | 182 bool get _repeating => _milliSeconds >= 0; |
60 | 183 |
61 bool get isActive => _callback != null; | 184 bool get isActive => _callback != null; |
62 | 185 |
63 // Cancels a set timer. The timer is removed from the timer list and if | 186 // Cancels a set timer. The timer is removed from the timer list and if |
64 // the given timer is the earliest timer the native timer is reset. | 187 // the given timer is the earliest timer the native timer is reset. |
65 void cancel() { | 188 void cancel() { |
66 _clear(); | 189 _clear(); |
67 // Return if already canceled. | 190 if (!_isInHeap) return; |
68 if (list == null) return; | 191 assert(_wakeupTime != 0); |
69 assert(!_timers.isEmpty); | 192 bool update = _firstZeroTimer == null && _heap.isFirst(this); |
70 _Timer first = _timers.first; | 193 _heap.remove(this); |
71 unlink(); | 194 if (update) { |
72 if (identical(first, this)) { | |
73 _notifyEventHandler(); | 195 _notifyEventHandler(); |
74 } | 196 } |
75 } | 197 } |
76 | 198 |
77 void _advanceWakeupTime() { | 199 void _advanceWakeupTime() { |
78 assert(_milliSeconds >= 0); | 200 assert(_milliSeconds >= 0); |
79 _wakeupTime += _milliSeconds; | 201 _wakeupTime += _milliSeconds; |
80 } | 202 } |
81 | 203 |
82 // Adds a timer to the timer list. Timers with the same wakeup time are | 204 // Adds a timer to the timer list. Timers with the same wakeup time are |
83 // enqueued in order and notified in FIFO order. | 205 // enqueued in order and notified in FIFO order. |
84 void _addTimerToList() { | 206 bool _addTimerToHeap() { |
85 _Timer entry = _timers.isEmpty ? null : _timers.first; | 207 if (_wakeupTime == 0) { |
86 // If timer is last, add to end. | 208 if (_firstZeroTimer == null) { |
87 if (entry == null || _timers.last._wakeupTime <= _wakeupTime) { | 209 _lastZeroTimer = _firstZeroTimer = this; |
88 _timers.add(this); | 210 return true; |
89 return; | 211 } else { |
| 212 _lastZeroTimer = _lastZeroTimer._indexOrNext = this; |
| 213 return false; |
| 214 } |
| 215 } else { |
| 216 _id = _idCount++; |
| 217 _heap.add(this); |
| 218 return _firstZeroTimer == null && _heap.isFirst(this); |
90 } | 219 } |
91 // Otherwise scan through and find the right position. | |
92 while (entry != null) { | |
93 if (_wakeupTime < entry._wakeupTime) { | |
94 entry.insertBefore(this); | |
95 return; | |
96 } | |
97 entry = entry.next; | |
98 } | |
99 _timers.add(this); | |
100 } | 220 } |
101 | 221 |
102 | 222 |
103 void _notifyEventHandler() { | 223 static void _notifyEventHandler() { |
104 if (_handling_callbacks) { | 224 if (_handlingCallbacks) { |
105 // While we are already handling callbacks we will not notify the event | 225 // While we are already handling callbacks we will not notify the event |
106 // handler. _handleTimeout will call _notifyEventHandler once all pending | 226 // handler. _handleTimeout will call _notifyEventHandler once all pending |
107 // timers are processed. | 227 // timers are processed. |
108 return; | 228 return; |
109 } | 229 } |
110 | 230 |
111 if (_timers.isEmpty) { | 231 if (_firstZeroTimer == null && _heap.isEmpty) { |
112 // No pending timers: Close the receive port and let the event handler | 232 // No pending timers: Close the receive port and let the event handler |
113 // know. | 233 // know. |
114 if (_receivePort != null) { | 234 if (_receivePort != null) { |
115 _EventHandler._sendData(null, _receivePort, _NO_TIMER); | 235 _EventHandler._sendData(null, _receivePort, _NO_TIMER); |
116 _shutdownTimerHandler(); | 236 _shutdownTimerHandler(); |
117 } | 237 } |
118 } else { | 238 } else { |
119 if (_receivePort == null) { | 239 if (_receivePort == null) { |
120 // Create a receive port and register a message handler for the timer | 240 // Create a receive port and register a message handler for the timer |
121 // events. | 241 // events. |
122 _createTimerHandler(); | 242 _createTimerHandler(); |
123 } | 243 } |
124 _EventHandler._sendData(null, | 244 _EventHandler._sendData(null, |
125 _receivePort, | 245 _receivePort, |
126 _timers.first._wakeupTime); | 246 _firstZeroTimer != null ? |
| 247 0 : _heap.first._wakeupTime); |
127 } | 248 } |
128 } | 249 } |
129 | 250 |
| 251 static void _handleTimeout(_) { |
| 252 int currentTime = new DateTime.now().millisecondsSinceEpoch; |
| 253 // Collect all pending timers. |
| 254 var timer = _firstZeroTimer; |
| 255 var nextTimer = _lastZeroTimer; |
| 256 _firstZeroTimer = _lastZeroTimer = null; |
| 257 while (_heap.isNotEmpty && _heap.first._wakeupTime <= currentTime) { |
| 258 var next = _heap.removeFirst(); |
| 259 if (timer == null) { |
| 260 nextTimer = timer = next; |
| 261 } else { |
| 262 nextTimer = nextTimer._indexOrNext = next; |
| 263 } |
| 264 } |
| 265 |
| 266 // Trigger all of the pending timers. New timers added as part of the |
| 267 // callbacks will be enqueued now and notified in the next spin at the |
| 268 // earliest. |
| 269 _handlingCallbacks = true; |
| 270 try { |
| 271 while (timer != null) { |
| 272 var next = timer._indexOrNext; |
| 273 timer._indexOrNext = null; |
| 274 // One of the timers in the pending_timers list can cancel |
| 275 // one of the later timers which will set the callback to |
| 276 // null. |
| 277 if (timer._callback != null) { |
| 278 var callback = timer._callback; |
| 279 if (!timer._repeating) { |
| 280 // Mark timer as inactive. |
| 281 timer._callback = null; |
| 282 } |
| 283 callback(timer); |
| 284 // Re-insert repeating timer if not canceled. |
| 285 if (timer._repeating && timer._callback != null) { |
| 286 timer._advanceWakeupTime(); |
| 287 timer._addTimerToHeap(); |
| 288 } |
| 289 } |
| 290 timer = next; |
| 291 } |
| 292 } finally { |
| 293 _handlingCallbacks = false; |
| 294 _notifyEventHandler(); |
| 295 } |
| 296 } |
130 | 297 |
131 // Creates a receive port and registers the timer handler on that | 298 // Creates a receive port and registers the timer handler on that |
132 // receive port. | 299 // receive port. |
133 void _createTimerHandler() { | 300 static void _createTimerHandler() { |
134 | |
135 void _handleTimeout() { | |
136 int currentTime = new DateTime.now().millisecondsSinceEpoch; | |
137 | |
138 // Collect all pending timers. | |
139 var pending_timers = new List(); | |
140 while (!_timers.isEmpty) { | |
141 _Timer entry = _timers.first; | |
142 if (entry._wakeupTime <= currentTime) { | |
143 entry.unlink(); | |
144 pending_timers.add(entry); | |
145 } else { | |
146 break; | |
147 } | |
148 } | |
149 | |
150 // Trigger all of the pending timers. New timers added as part of the | |
151 // callbacks will be enqueued now and notified in the next spin at the | |
152 // earliest. | |
153 _handling_callbacks = true; | |
154 try { | |
155 for (var timer in pending_timers) { | |
156 // One of the timers in the pending_timers list can cancel | |
157 // one of the later timers which will set the callback to | |
158 // null. | |
159 if (timer._callback != null) { | |
160 var callback = timer._callback; | |
161 if (!timer._repeating) { | |
162 //Mark timer as inactive. | |
163 timer._callback = null; | |
164 } | |
165 callback(timer); | |
166 // Re-insert repeating timer if not canceled. | |
167 if (timer._repeating && timer._callback != null) { | |
168 timer._advanceWakeupTime(); | |
169 timer._addTimerToList(); | |
170 } | |
171 } | |
172 } | |
173 } finally { | |
174 _handling_callbacks = false; | |
175 _notifyEventHandler(); | |
176 } | |
177 } | |
178 | |
179 if(_receivePort == null) { | 301 if(_receivePort == null) { |
180 _receivePort = new RawReceivePort((_) { _handleTimeout(); }); | 302 _receivePort = new RawReceivePort(_handleTimeout); |
181 } | 303 } |
182 } | 304 } |
183 | 305 |
184 void _shutdownTimerHandler() { | 306 static void _shutdownTimerHandler() { |
185 _receivePort.close(); | 307 _receivePort.close(); |
186 _receivePort = null; | 308 _receivePort = null; |
187 } | 309 } |
188 } | 310 } |
189 | 311 |
190 // Provide a closure which will allocate a Timer object to be able to hook | 312 // Provide a closure which will allocate a Timer object to be able to hook |
191 // up the Timer interface in dart:isolate with the implementation here. | 313 // up the Timer interface in dart:isolate with the implementation here. |
192 _getTimerFactoryClosure() { | 314 _getTimerFactoryClosure() { |
193 return (int milliSeconds, void callback(Timer timer), bool repeating) { | 315 return (int milliSeconds, void callback(Timer timer), bool repeating) { |
194 if (repeating) { | 316 if (repeating) { |
195 return new _Timer.periodic(milliSeconds, callback); | 317 return new _Timer.periodic(milliSeconds, callback); |
196 } | 318 } |
197 return new _Timer(milliSeconds, callback); | 319 return new _Timer(milliSeconds, callback); |
198 }; | 320 }; |
199 } | 321 } |
200 | 322 |
201 | 323 |
OLD | NEW |