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 // Timer heap implemented as a array-based binary heap[0]. | 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)) | 8 // This allows for O(1) `first`, O(log(n)) `remove`/`removeFirst` and O(log(n)) |
9 // `add`. | 9 // `add`. |
10 // | 10 // |
11 // To ensure the timers are ordered by insertion time, the _Timer class has a | 11 // To ensure the timers are ordered by insertion time, the _Timer class has a |
12 // `_id` field set when added to the heap. | 12 // `_id` field set when added to the heap. |
13 // | 13 // |
14 // [0] http://en.wikipedia.org/wiki/Binary_heap | 14 // [0] http://en.wikipedia.org/wiki/Binary_heap |
15 class _TimerHeap { | 15 class _TimerHeap { |
16 List<_Timer> _list; | 16 List<_Timer> _list; |
17 int _used = 0; | 17 int _used = 0; |
18 | 18 |
19 _TimerHeap([int initSize = 7]) | 19 _TimerHeap([int initSize = 7]) |
20 : _list = new List<_Timer>(initSize); | 20 : _list = new List<_Timer>(initSize); |
21 | 21 |
22 bool get isEmpty => _used == 0; | 22 bool get isEmpty => _used == 0; |
23 bool get isNotEmpty => _used > 0; | |
24 | 23 |
25 _Timer get first => _list[0]; | 24 _Timer get first => _list[0]; |
26 | 25 |
27 bool isFirst(_Timer timer) => timer._indexOrNext == 0; | 26 bool isFirst(_Timer timer) => timer._indexOrNext == 0; |
28 | 27 |
29 void add(_Timer timer) { | 28 void add(_Timer timer) { |
30 if (_used == _list.length) { | 29 if (_used == _list.length) { |
31 _resize(); | 30 _resize(); |
32 } | 31 } |
33 timer._indexOrNext = _used++; | 32 timer._indexOrNext = _used++; |
34 _list[timer._indexOrNext] = timer; | 33 _list[timer._indexOrNext] = timer; |
35 _bubbleUp(timer); | 34 _bubbleUp(timer); |
36 } | 35 } |
37 | 36 |
38 _Timer removeFirst() { | 37 _Timer removeFirst() { |
39 var f = first; | 38 var f = first; |
40 remove(f); | 39 remove(f); |
41 return f; | 40 return f; |
42 } | 41 } |
43 | 42 |
44 void remove(_Timer timer) { | 43 void remove(_Timer timer) { |
45 _used--; | 44 _used--; |
46 timer._id = -1; | |
47 if (isEmpty) { | 45 if (isEmpty) { |
48 _list[0] = null; | 46 _list[0] = null; |
49 timer._indexOrNext = null; | 47 timer._indexOrNext = null; |
50 return; | 48 return; |
51 } | 49 } |
52 var last = _list[_used]; | 50 var last = _list[_used]; |
53 if (!identical(last, timer)) { | 51 if (!identical(last, timer)) { |
54 last._indexOrNext = timer._indexOrNext; | 52 last._indexOrNext = timer._indexOrNext; |
55 _list[last._indexOrNext] = last; | 53 _list[last._indexOrNext] = last; |
56 if (last._compareTo(timer) < 0) { | 54 if (last._compareTo(timer) < 0) { |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
111 Timer _leftChild(_Timer timer) => _list[_leftChildIndex(timer._indexOrNext)]; | 109 Timer _leftChild(_Timer timer) => _list[_leftChildIndex(timer._indexOrNext)]; |
112 Timer _rightChild(_Timer timer) => | 110 Timer _rightChild(_Timer timer) => |
113 _list[_rightChildIndex(timer._indexOrNext)]; | 111 _list[_rightChildIndex(timer._indexOrNext)]; |
114 | 112 |
115 static int _parentIndex(int index) => (index - 1) ~/ 2; | 113 static int _parentIndex(int index) => (index - 1) ~/ 2; |
116 static int _leftChildIndex(int index) => 2 * index + 1; | 114 static int _leftChildIndex(int index) => 2 * index + 1; |
117 static int _rightChildIndex(int index) => 2 * index + 2; | 115 static int _rightChildIndex(int index) => 2 * index + 2; |
118 } | 116 } |
119 | 117 |
120 class _Timer implements Timer { | 118 class _Timer implements Timer { |
121 // Disables the timer. | 119 // Cancels the timer in the event handler. |
122 static const int _NO_TIMER = -1; | 120 static const int _NO_TIMER = -1; |
123 | 121 |
124 // Timers are ordered by wakeup time. | 122 // Timers are ordered by wakeup time. |
125 static _TimerHeap _heap = new _TimerHeap(); | 123 static _TimerHeap _heap = new _TimerHeap(); |
126 static _Timer _firstZeroTimer; | 124 static _Timer _firstZeroTimer; |
127 static _Timer _lastZeroTimer; | 125 static _Timer _lastZeroTimer; |
| 126 |
| 127 // We use an id to be able to sort timers with the same expiration time. |
| 128 // ids are recycled after ID_MASK enqueues or when the timer queue is empty. |
| 129 static int _ID_MASK = 0x1fffffff; |
128 static int _idCount = 0; | 130 static int _idCount = 0; |
129 | 131 |
130 static RawReceivePort _receivePort; | 132 static RawReceivePort _receivePort; |
131 static SendPort _sendPort; | 133 static SendPort _sendPort; |
| 134 static int _scheduledWakeupTime; |
132 static bool _handlingCallbacks = false; | 135 static bool _handlingCallbacks = false; |
133 | 136 |
134 Function _callback; | 137 Function _callback; // Closure to call when timer fires. null if canceled. |
135 int _milliSeconds; | 138 int _wakeupTime; // Expiration time. |
136 int _wakeupTime = 0; | 139 int _milliSeconds; // Duration specified at creation. |
137 var _indexOrNext; | 140 bool _repeating; // Indicates periodic timers. |
138 int _id = -1; | 141 var _indexOrNext; // Index if part of the TimerHeap, link otherwise. |
| 142 int _id; // Incrementing id to enable sorting of timers with same expiry. |
| 143 |
| 144 // Get the next available id. We accept collisions and reordering when the |
| 145 // _idCount overflows and the timers expire at the same millisecond. |
| 146 static int _nextId() { |
| 147 var result = _idCount; |
| 148 _idCount = (_idCount + 1) & _ID_MASK; |
| 149 return result; |
| 150 } |
| 151 |
| 152 _Timer._internal(this._callback, |
| 153 this._wakeupTime, |
| 154 this._milliSeconds, |
| 155 this._repeating) : _id = _nextId(); |
139 | 156 |
140 static Timer _createTimer(void callback(Timer timer), | 157 static Timer _createTimer(void callback(Timer timer), |
141 int milliSeconds, | 158 int milliSeconds, |
142 bool repeating) { | 159 bool repeating) { |
143 _Timer timer = new _Timer._internal(); | 160 // Negative timeouts are treated as if 0 timeout. |
144 timer._callback = callback; | 161 if (milliSeconds < 0) { |
145 if (milliSeconds > 0) { | 162 milliSeconds = 0; |
146 // Add one because DateTime.now() is assumed to round down | |
147 // to nearest millisecond, not up, so that time + duration is before | |
148 // duration milliseconds from now. Using micosecond timers like | |
149 // Stopwatch allows detecting that the timer fires early. | |
150 timer._wakeupTime = | |
151 new DateTime.now().millisecondsSinceEpoch + 1 + milliSeconds; | |
152 } | 163 } |
153 timer._milliSeconds = repeating ? milliSeconds : -1; | 164 // Add one because DateTime.now() is assumed to round down |
| 165 // to nearest millisecond, not up, so that time + duration is before |
| 166 // duration milliseconds from now. Using microsecond timers like |
| 167 // Stopwatch allows detecting that the timer fires early. |
| 168 int now = new DateTime.now().millisecondsSinceEpoch; |
| 169 int wakeupTime = (milliSeconds == 0) ? now : (now + 1 + milliSeconds); |
| 170 |
| 171 _Timer timer = new _Timer._internal(callback, |
| 172 wakeupTime, |
| 173 milliSeconds, |
| 174 repeating); |
| 175 |
154 if (timer._addTimerToHeap()) { | 176 if (timer._addTimerToHeap()) { |
155 // The new timer is the first in queue. Update event handler. | 177 // The new timer is the first in queue. Update event handler. |
156 _notifyEventHandler(); | 178 _notifyEventHandler(); |
157 } | 179 } |
158 return timer; | 180 return timer; |
159 } | 181 } |
160 | 182 |
161 factory _Timer(int milliSeconds, void callback(Timer timer)) { | 183 factory _Timer(int milliSeconds, void callback(Timer timer)) { |
162 return _createTimer(callback, milliSeconds, false); | 184 return _createTimer(callback, milliSeconds, false); |
163 } | 185 } |
164 | 186 |
165 factory _Timer.periodic(int milliSeconds, void callback(Timer timer)) { | 187 factory _Timer.periodic(int milliSeconds, void callback(Timer timer)) { |
166 return _createTimer(callback, milliSeconds, true); | 188 return _createTimer(callback, milliSeconds, true); |
167 } | 189 } |
168 | 190 |
169 _Timer._internal() {} | 191 bool get _isInHeap => _indexOrNext is int; |
170 | |
171 bool get _isInHeap => _id >= 0; | |
172 | 192 |
173 void _clear() { | 193 void _clear() { |
174 _callback = null; | 194 _callback = null; |
175 } | 195 } |
176 | 196 |
177 int _compareTo(_Timer other) { | 197 int _compareTo(_Timer other) { |
178 int c = _wakeupTime - other._wakeupTime; | 198 int c = _wakeupTime - other._wakeupTime; |
179 if (c != 0) return c; | 199 if (c != 0) return c; |
180 return _id - other._id; | 200 return _id - other._id; |
181 } | 201 } |
182 | 202 |
183 bool get _repeating => _milliSeconds >= 0; | |
184 | |
185 bool get isActive => _callback != null; | 203 bool get isActive => _callback != null; |
186 | 204 |
187 // Cancels a set timer. The timer is removed from the timer list and if | 205 // Cancels a set timer. The timer is removed from the timer list and if |
188 // the given timer is the earliest timer the native timer is reset. | 206 // the given timer is the earliest timer the event handler is notified. |
189 void cancel() { | 207 void cancel() { |
190 _clear(); | 208 _clear(); |
191 if (!_isInHeap) return; | 209 if (!_isInHeap) return; |
192 assert(_wakeupTime != 0); | 210 // Only heap timers are really removed. Others are just dropped on |
| 211 // notification. |
193 bool update = (_firstZeroTimer == null) && _heap.isFirst(this); | 212 bool update = (_firstZeroTimer == null) && _heap.isFirst(this); |
194 _heap.remove(this); | 213 _heap.remove(this); |
195 if (update) { | 214 if (update) { |
196 _notifyEventHandler(); | 215 _notifyEventHandler(); |
197 } | 216 } |
198 } | 217 } |
199 | 218 |
200 void _advanceWakeupTime() { | 219 void _advanceWakeupTime() { |
201 assert(_milliSeconds >= 0); | 220 // Recalculate the next wakeup time. For repeating timers with a 0 timeout |
202 _wakeupTime += _milliSeconds; | 221 // the next wakeup time is now. |
| 222 _id = _nextId(); |
| 223 if (_milliSeconds > 0) { |
| 224 _wakeupTime += _milliSeconds; |
| 225 } else { |
| 226 _wakeupTime = new DateTime.now().millisecondsSinceEpoch; |
| 227 } |
203 } | 228 } |
204 | 229 |
205 // Adds a timer to the timer list. Timers with the same wakeup time are | 230 // Adds a timer to the heap or timer list. Timers with the same wakeup time |
206 // enqueued in order and notified in FIFO order. | 231 // are enqueued in order and notified in FIFO order. |
207 bool _addTimerToHeap() { | 232 bool _addTimerToHeap() { |
208 if (_wakeupTime == 0) { | 233 if (_milliSeconds == 0) { |
209 if (_firstZeroTimer == null) { | 234 if (_firstZeroTimer == null) { |
210 _lastZeroTimer = this; | 235 _lastZeroTimer = this; |
211 _firstZeroTimer = this; | 236 _firstZeroTimer = this; |
212 return true; | 237 return true; |
213 } else { | 238 } else { |
214 _lastZeroTimer._indexOrNext = this; | 239 _lastZeroTimer._indexOrNext = this; |
215 _lastZeroTimer = this; | 240 _lastZeroTimer = this; |
216 return false; | 241 return false; |
217 } | 242 } |
218 } else { | 243 } else { |
219 _id = _idCount++; | |
220 _heap.add(this); | 244 _heap.add(this); |
221 return _firstZeroTimer == null && _heap.isFirst(this); | 245 return _firstZeroTimer == null && _heap.isFirst(this); |
222 } | 246 } |
223 } | 247 } |
224 | 248 |
225 | 249 |
226 static void _notifyEventHandler() { | 250 static void _notifyEventHandler() { |
227 if (_handlingCallbacks) { | 251 if (_handlingCallbacks) { |
228 // While we are already handling callbacks we will not notify the event | 252 // While we are already handling callbacks we will not notify the event |
229 // handler. _handleTimeout will call _notifyEventHandler once all pending | 253 // handler. _handleTimeout will call _notifyEventHandler once all pending |
(...skipping 10 matching lines...) Expand all Loading... |
240 } | 264 } |
241 } else { | 265 } else { |
242 if (_receivePort == null) { | 266 if (_receivePort == null) { |
243 // Create a receive port and register a message handler for the timer | 267 // Create a receive port and register a message handler for the timer |
244 // events. | 268 // events. |
245 _createTimerHandler(); | 269 _createTimerHandler(); |
246 } | 270 } |
247 if (_firstZeroTimer != null) { | 271 if (_firstZeroTimer != null) { |
248 _sendPort.send(null); | 272 _sendPort.send(null); |
249 } else { | 273 } else { |
250 _EventHandler._sendData(null, | 274 var wakeupTime = _heap.first._wakeupTime; |
251 _sendPort, | 275 if ((_scheduledWakeupTime == null) || |
252 _heap.first._wakeupTime); | 276 (wakeupTime != _scheduledWakeupTime)) { |
| 277 _EventHandler._sendData(null, _sendPort, wakeupTime); |
| 278 _scheduledWakeupTime = wakeupTime; |
| 279 } |
253 } | 280 } |
254 } | 281 } |
255 } | 282 } |
256 | 283 |
257 static void _handleTimeout(_) { | 284 static void _handleTimeout(pendingImmediateCallback) { |
258 int currentTime = new DateTime.now().millisecondsSinceEpoch; | 285 int currentTime = new DateTime.now().millisecondsSinceEpoch; |
259 // Collect all pending timers. | 286 // Collect all pending timers. |
260 var timer = _firstZeroTimer; | 287 var head = null; |
261 var nextTimer = _lastZeroTimer; | 288 var tail = null; |
262 _firstZeroTimer = null; | 289 // Keep track of the lowest wakeup times for both the list and heap. If |
263 _lastZeroTimer = null; | 290 // the respective queue is empty move its time beyond the current time. |
264 while (_heap.isNotEmpty && _heap.first._wakeupTime <= currentTime) { | 291 var heapTime = _heap.isEmpty ? |
265 var next = _heap.removeFirst(); | 292 (currentTime + 1) : _heap.first._wakeupTime; |
266 if (timer == null) { | 293 var listTime = (_firstZeroTimer == null) ? |
267 nextTimer = next; | 294 (currentTime + 1) : _firstZeroTimer._wakeupTime; |
268 timer = next; | 295 |
| 296 while ((heapTime <= currentTime) || (listTime <= currentTime)) { |
| 297 var timer; |
| 298 // Consume the timers in order by removing from heap or list based on |
| 299 // their wakeup time and update the queue's time. |
| 300 assert((heapTime != listTime) || |
| 301 ((_heap.first != null) && (_firstZeroTimer != null))); |
| 302 if ((heapTime < listTime) || |
| 303 ((heapTime == listTime) && |
| 304 (_heap.first._id < _firstZeroTimer._id))) { |
| 305 timer = _heap.removeFirst(); |
| 306 heapTime = _heap.isEmpty ? (currentTime + 1) : _heap.first._wakeupTime; |
269 } else { | 307 } else { |
270 nextTimer._indexOrNext = next; | 308 timer = _firstZeroTimer; |
271 nextTimer = next; | 309 assert(timer._milliSeconds == 0); |
| 310 _firstZeroTimer = timer._indexOrNext; |
| 311 if (_firstZeroTimer == null) { |
| 312 _lastZeroTimer = null; |
| 313 listTime = currentTime + 1; |
| 314 } else { |
| 315 // We want to drain all entries from the list as they should have |
| 316 // been pending for 0 ms. To prevent issues with current time moving |
| 317 // we ensure that the listTime does not go beyond current, unless the |
| 318 // list is empty. |
| 319 listTime = _firstZeroTimer._wakeupTime; |
| 320 if (listTime > currentTime) { |
| 321 listTime = currentTime; |
| 322 } |
| 323 } |
272 } | 324 } |
| 325 |
| 326 // Append this timer to the pending timer list. |
| 327 timer._indexOrNext = null; |
| 328 if (head == null) { |
| 329 assert(tail == null); |
| 330 head = timer; |
| 331 tail = timer; |
| 332 } else { |
| 333 tail._indexOrNext = timer; |
| 334 tail = timer; |
| 335 } |
| 336 } |
| 337 |
| 338 // No timers queued: Early exit. |
| 339 if (head == null) { |
| 340 return; |
| 341 } |
| 342 |
| 343 // If there are no pending timers currently reset the id space before we |
| 344 // have a chance to enqueue new timers. |
| 345 assert(_firstZeroTimer == null); |
| 346 if (_heap.isEmpty) { |
| 347 _idCount = 0; |
273 } | 348 } |
274 | 349 |
275 // Trigger all of the pending timers. New timers added as part of the | 350 // Trigger all of the pending timers. New timers added as part of the |
276 // callbacks will be enqueued now and notified in the next spin at the | 351 // callbacks will be enqueued now and notified in the next spin at the |
277 // earliest. | 352 // earliest. |
278 _handlingCallbacks = true; | 353 _handlingCallbacks = true; |
279 try { | 354 try { |
280 while (timer != null) { | 355 while (head != null) { |
281 var next = timer._indexOrNext; | 356 // Dequeue the first candidate timer. |
| 357 var timer = head; |
| 358 head = timer._indexOrNext; |
282 timer._indexOrNext = null; | 359 timer._indexOrNext = null; |
| 360 |
283 // One of the timers in the pending_timers list can cancel | 361 // One of the timers in the pending_timers list can cancel |
284 // one of the later timers which will set the callback to | 362 // one of the later timers which will set the callback to |
285 // null. | 363 // null. |
286 if (timer._callback != null) { | 364 if (timer._callback != null) { |
287 var callback = timer._callback; | 365 var callback = timer._callback; |
288 if (!timer._repeating) { | 366 if (!timer._repeating) { |
289 // Mark timer as inactive. | 367 // Mark timer as inactive. |
290 timer._callback = null; | 368 timer._callback = null; |
291 } | 369 } |
292 callback(timer); | 370 callback(timer); |
293 // Re-insert repeating timer if not canceled. | 371 // Re-insert repeating timer if not canceled. |
294 if (timer._repeating && timer._callback != null) { | 372 if (timer._repeating && (timer._callback != null)) { |
295 timer._advanceWakeupTime(); | 373 timer._advanceWakeupTime(); |
296 timer._addTimerToHeap(); | 374 timer._addTimerToHeap(); |
297 } | 375 } |
| 376 // Execute pending micro tasks. |
| 377 pendingImmediateCallback(); |
298 } | 378 } |
299 timer = next; | |
300 } | 379 } |
301 } finally { | 380 } finally { |
302 _handlingCallbacks = false; | 381 _handlingCallbacks = false; |
303 _notifyEventHandler(); | 382 _notifyEventHandler(); |
304 } | 383 } |
305 } | 384 } |
306 | 385 |
307 // Creates a receive port and registers the timer handler on that | 386 // Creates a receive port and registers an empty handler on that port. Just |
308 // receive port. | 387 // the triggering of the event loop will ensure that timers are executed. |
| 388 static _ignoreMessage(_) => null; |
| 389 |
309 static void _createTimerHandler() { | 390 static void _createTimerHandler() { |
310 if(_receivePort == null) { | 391 assert(_receivePort == null); |
311 _receivePort = new RawReceivePort(_handleTimeout); | 392 _receivePort = new RawReceivePort(_ignoreMessage); |
312 _sendPort = _receivePort.sendPort; | 393 _sendPort = _receivePort.sendPort; |
313 } | 394 _scheduledWakeupTime = null; |
314 } | 395 } |
315 | 396 |
316 static void _shutdownTimerHandler() { | 397 static void _shutdownTimerHandler() { |
317 _receivePort.close(); | 398 _receivePort.close(); |
318 _receivePort = null; | 399 _receivePort = null; |
319 _sendPort = null; | 400 _sendPort = null; |
| 401 _scheduledWakeupTime = null; |
| 402 } |
| 403 |
| 404 // The Timer factory registered with the dart:async library by the embedder. |
| 405 static Timer _factory(int milliSeconds, |
| 406 void callback(Timer timer), |
| 407 bool repeating) { |
| 408 if (repeating) { |
| 409 return new _Timer.periodic(milliSeconds, callback); |
| 410 } |
| 411 return new _Timer(milliSeconds, callback); |
320 } | 412 } |
321 } | 413 } |
322 | 414 |
323 // Provide a closure which will allocate a Timer object to be able to hook | 415 // Provide a closure which will allocate a Timer object to be able to hook |
324 // up the Timer interface in dart:isolate with the implementation here. | 416 // up the Timer interface in dart:isolate with the implementation here. |
325 _getTimerFactoryClosure() { | 417 _getTimerFactoryClosure() { |
326 return (int milliSeconds, void callback(Timer timer), bool repeating) { | 418 runTimerClosure = _Timer._handleTimeout; |
327 if (repeating) { | 419 return _Timer._factory; |
328 return new _Timer.periodic(milliSeconds, callback); | |
329 } | |
330 return new _Timer(milliSeconds, callback); | |
331 }; | |
332 } | 420 } |
333 | |
334 | |
OLD | NEW |