| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 part of dart.io; | |
| 6 | |
| 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 | |
| 24 _Timer get first => _list[0]; | |
| 25 | |
| 26 bool isFirst(_Timer timer) => timer._indexOrNext == 0; | |
| 27 | |
| 28 void add(_Timer timer) { | |
| 29 if (_used == _list.length) { | |
| 30 _resize(); | |
| 31 } | |
| 32 timer._indexOrNext = _used++; | |
| 33 _list[timer._indexOrNext] = timer; | |
| 34 _bubbleUp(timer); | |
| 35 } | |
| 36 | |
| 37 _Timer removeFirst() { | |
| 38 var f = first; | |
| 39 remove(f); | |
| 40 return f; | |
| 41 } | |
| 42 | |
| 43 void remove(_Timer timer) { | |
| 44 _used--; | |
| 45 if (isEmpty) { | |
| 46 _list[0] = null; | |
| 47 timer._indexOrNext = null; | |
| 48 return; | |
| 49 } | |
| 50 var last = _list[_used]; | |
| 51 if (!identical(last, timer)) { | |
| 52 last._indexOrNext = timer._indexOrNext; | |
| 53 _list[last._indexOrNext] = last; | |
| 54 if (last._compareTo(timer) < 0) { | |
| 55 _bubbleUp(last); | |
| 56 } else { | |
| 57 _bubbleDown(last); | |
| 58 } | |
| 59 } | |
| 60 _list[_used] = null; | |
| 61 timer._indexOrNext = null; | |
| 62 } | |
| 63 | |
| 64 void _resize() { | |
| 65 var newList = new List(_list.length * 2 + 1); | |
| 66 newList.setRange(0, _used, _list); | |
| 67 _list = newList; | |
| 68 } | |
| 69 | |
| 70 void _bubbleUp(_Timer timer) { | |
| 71 while (!isFirst(timer)) { | |
| 72 Timer parent = _parent(timer); | |
| 73 if (timer._compareTo(parent) < 0) { | |
| 74 _swap(timer, parent); | |
| 75 } else { | |
| 76 break; | |
| 77 } | |
| 78 } | |
| 79 } | |
| 80 | |
| 81 void _bubbleDown(_Timer timer) { | |
| 82 while (true) { | |
| 83 int leftIndex = _leftChildIndex(timer._indexOrNext); | |
| 84 int rightIndex = _rightChildIndex(timer._indexOrNext); | |
| 85 _Timer newest = timer; | |
| 86 if (leftIndex < _used && _list[leftIndex]._compareTo(newest) < 0) { | |
| 87 newest = _list[leftIndex]; | |
| 88 } | |
| 89 if (rightIndex < _used && _list[rightIndex]._compareTo(newest) < 0) { | |
| 90 newest = _list[rightIndex]; | |
| 91 } | |
| 92 if (identical(newest, timer)) { | |
| 93 // We are where we should be, break. | |
| 94 break; | |
| 95 } | |
| 96 _swap(newest, timer); | |
| 97 } | |
| 98 } | |
| 99 | |
| 100 void _swap(_Timer first, _Timer second) { | |
| 101 int tmp = first._indexOrNext; | |
| 102 first._indexOrNext = second._indexOrNext; | |
| 103 second._indexOrNext = tmp; | |
| 104 _list[first._indexOrNext] = first; | |
| 105 _list[second._indexOrNext] = second; | |
| 106 } | |
| 107 | |
| 108 Timer _parent(_Timer timer) => _list[_parentIndex(timer._indexOrNext)]; | |
| 109 Timer _leftChild(_Timer timer) => _list[_leftChildIndex(timer._indexOrNext)]; | |
| 110 Timer _rightChild(_Timer timer) => | |
| 111 _list[_rightChildIndex(timer._indexOrNext)]; | |
| 112 | |
| 113 static int _parentIndex(int index) => (index - 1) ~/ 2; | |
| 114 static int _leftChildIndex(int index) => 2 * index + 1; | |
| 115 static int _rightChildIndex(int index) => 2 * index + 2; | |
| 116 } | |
| 117 | |
| 118 class _Timer implements Timer { | |
| 119 // Cancels the timer in the event handler. | |
| 120 static const int _NO_TIMER = -1; | |
| 121 | |
| 122 // Timers are ordered by wakeup time. | |
| 123 static _TimerHeap _heap = new _TimerHeap(); | |
| 124 static _Timer _firstZeroTimer; | |
| 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; | |
| 130 static int _idCount = 0; | |
| 131 | |
| 132 static RawReceivePort _receivePort; | |
| 133 static SendPort _sendPort; | |
| 134 static int _scheduledWakeupTime; | |
| 135 // Keep track whether at least one message is pending in the event loop. This | |
| 136 // way we do not have to notify for every pending _firstZeroTimer. | |
| 137 static var _messagePending = false; | |
| 138 | |
| 139 static bool _handlingCallbacks = false; | |
| 140 | |
| 141 Function _callback; // Closure to call when timer fires. null if canceled. | |
| 142 int _wakeupTime; // Expiration time. | |
| 143 int _milliSeconds; // Duration specified at creation. | |
| 144 bool _repeating; // Indicates periodic timers. | |
| 145 var _indexOrNext; // Index if part of the TimerHeap, link otherwise. | |
| 146 int _id; // Incrementing id to enable sorting of timers with same expiry. | |
| 147 | |
| 148 // Get the next available id. We accept collisions and reordering when the | |
| 149 // _idCount overflows and the timers expire at the same millisecond. | |
| 150 static int _nextId() { | |
| 151 var result = _idCount; | |
| 152 _idCount = (_idCount + 1) & _ID_MASK; | |
| 153 return result; | |
| 154 } | |
| 155 | |
| 156 _Timer._internal(this._callback, | |
| 157 this._wakeupTime, | |
| 158 this._milliSeconds, | |
| 159 this._repeating) : _id = _nextId(); | |
| 160 | |
| 161 static Timer _createTimer(void callback(Timer timer), | |
| 162 int milliSeconds, | |
| 163 bool repeating) { | |
| 164 // Negative timeouts are treated as if 0 timeout. | |
| 165 if (milliSeconds < 0) { | |
| 166 milliSeconds = 0; | |
| 167 } | |
| 168 // Add one because DateTime.now() is assumed to round down | |
| 169 // to nearest millisecond, not up, so that time + duration is before | |
| 170 // duration milliseconds from now. Using microsecond timers like | |
| 171 // Stopwatch allows detecting that the timer fires early. | |
| 172 int now = new DateTime.now().millisecondsSinceEpoch; | |
| 173 int wakeupTime = (milliSeconds == 0) ? now : (now + 1 + milliSeconds); | |
| 174 | |
| 175 _Timer timer = new _Timer._internal(callback, | |
| 176 wakeupTime, | |
| 177 milliSeconds, | |
| 178 repeating); | |
| 179 | |
| 180 if (timer._addTimerToHeap()) { | |
| 181 // The new timer is the first in queue. Update event handler. | |
| 182 _notifyEventHandler(); | |
| 183 } | |
| 184 return timer; | |
| 185 } | |
| 186 | |
| 187 factory _Timer(int milliSeconds, void callback(Timer timer)) { | |
| 188 return _createTimer(callback, milliSeconds, false); | |
| 189 } | |
| 190 | |
| 191 factory _Timer.periodic(int milliSeconds, void callback(Timer timer)) { | |
| 192 return _createTimer(callback, milliSeconds, true); | |
| 193 } | |
| 194 | |
| 195 bool get _isInHeap => _indexOrNext is int; | |
| 196 | |
| 197 void _clear() { | |
| 198 _callback = null; | |
| 199 } | |
| 200 | |
| 201 int _compareTo(_Timer other) { | |
| 202 int c = _wakeupTime - other._wakeupTime; | |
| 203 if (c != 0) return c; | |
| 204 return _id - other._id; | |
| 205 } | |
| 206 | |
| 207 bool get isActive => _callback != null; | |
| 208 | |
| 209 // Cancels a set timer. The timer is removed from the timer list and if | |
| 210 // the given timer is the earliest timer the event handler is notified. | |
| 211 void cancel() { | |
| 212 _clear(); | |
| 213 if (!_isInHeap) return; | |
| 214 // Only heap timers are really removed. Others are just dropped on | |
| 215 // notification. | |
| 216 bool update = (_firstZeroTimer == null) && _heap.isFirst(this); | |
| 217 _heap.remove(this); | |
| 218 if (update) { | |
| 219 _notifyEventHandler(); | |
| 220 } | |
| 221 } | |
| 222 | |
| 223 void _advanceWakeupTime() { | |
| 224 // Recalculate the next wakeup time. For repeating timers with a 0 timeout | |
| 225 // the next wakeup time is now. | |
| 226 _id = _nextId(); | |
| 227 if (_milliSeconds > 0) { | |
| 228 _wakeupTime += _milliSeconds; | |
| 229 } else { | |
| 230 _wakeupTime = new DateTime.now().millisecondsSinceEpoch; | |
| 231 } | |
| 232 } | |
| 233 | |
| 234 // Adds a timer to the heap or timer list. Timers with the same wakeup time | |
| 235 // are enqueued in order and notified in FIFO order. | |
| 236 bool _addTimerToHeap() { | |
| 237 if (_milliSeconds == 0) { | |
| 238 if (_firstZeroTimer == null) { | |
| 239 _lastZeroTimer = this; | |
| 240 _firstZeroTimer = this; | |
| 241 return true; | |
| 242 } else { | |
| 243 _lastZeroTimer._indexOrNext = this; | |
| 244 _lastZeroTimer = this; | |
| 245 return false; | |
| 246 } | |
| 247 } else { | |
| 248 _heap.add(this); | |
| 249 return _firstZeroTimer == null && _heap.isFirst(this); | |
| 250 } | |
| 251 } | |
| 252 | |
| 253 | |
| 254 static void _notifyEventHandler() { | |
| 255 if (_handlingCallbacks) { | |
| 256 // While we are already handling callbacks we will not notify the event | |
| 257 // handler. _handleTimeout will call _notifyEventHandler once all pending | |
| 258 // timers are processed. | |
| 259 return; | |
| 260 } | |
| 261 | |
| 262 if ((_firstZeroTimer == null) && _heap.isEmpty) { | |
| 263 // No pending timers: Close the receive port and let the event handler | |
| 264 // know. | |
| 265 if (_receivePort != null) { | |
| 266 _EventHandler._sendData(null, _sendPort, _NO_TIMER); | |
| 267 _shutdownTimerHandler(); | |
| 268 } | |
| 269 } else { | |
| 270 if (_receivePort == null) { | |
| 271 // Create a receive port and register a message handler for the timer | |
| 272 // events. | |
| 273 _createTimerHandler(); | |
| 274 } | |
| 275 if (_firstZeroTimer != null) { | |
| 276 if (!_messagePending) { | |
| 277 _sendPort.send(null); | |
| 278 _messagePending = true; // Reset when the port receives a message. | |
| 279 } | |
| 280 } else { | |
| 281 var wakeupTime = _heap.first._wakeupTime; | |
| 282 if ((_scheduledWakeupTime == null) || | |
| 283 (wakeupTime != _scheduledWakeupTime)) { | |
| 284 _EventHandler._sendData(null, _sendPort, wakeupTime); | |
| 285 _scheduledWakeupTime = wakeupTime; | |
| 286 } | |
| 287 } | |
| 288 } | |
| 289 } | |
| 290 | |
| 291 static void _handleTimeout(pendingImmediateCallback) { | |
| 292 // Fast exit if no timers have been scheduled. | |
| 293 if (_heap.isEmpty && (_firstZeroTimer == null)) { | |
| 294 assert(_receivePort == null); | |
| 295 return; | |
| 296 } | |
| 297 | |
| 298 // Collect all pending timers. | |
| 299 var head = null; | |
| 300 var tail = null; | |
| 301 if (_heap.isEmpty) { | |
| 302 // Only immediate timers are scheduled. Take over the whole list as is. | |
| 303 assert(_firstZeroTimer != null); | |
| 304 assert(_lastZeroTimer != null); | |
| 305 head = _firstZeroTimer; | |
| 306 tail = _lastZeroTimer; | |
| 307 _firstZeroTimer = null; | |
| 308 _lastZeroTimer = null; | |
| 309 } else { | |
| 310 assert(!_heap.isEmpty); | |
| 311 // Keep track of the lowest wakeup times for both the list and heap. If | |
| 312 // the respective queue is empty move its time beyond the current time. | |
| 313 var currentTime = new DateTime.now().millisecondsSinceEpoch; | |
| 314 var heapTime = _heap.first._wakeupTime; | |
| 315 var listTime = (_firstZeroTimer == null) ? | |
| 316 (currentTime + 1) : _firstZeroTimer._wakeupTime; | |
| 317 | |
| 318 while ((heapTime <= currentTime) || (listTime <= currentTime)) { | |
| 319 var timer; | |
| 320 // Consume the timers in order by removing from heap or list based on | |
| 321 // their wakeup time and update the queue's time. | |
| 322 assert((heapTime != listTime) || | |
| 323 ((_heap.first != null) && (_firstZeroTimer != null))); | |
| 324 if ((heapTime < listTime) || | |
| 325 ((heapTime == listTime) && | |
| 326 (_heap.first._id < _firstZeroTimer._id))) { | |
| 327 timer = _heap.removeFirst(); | |
| 328 heapTime = _heap.isEmpty ? | |
| 329 (currentTime + 1) : _heap.first._wakeupTime; | |
| 330 } else { | |
| 331 timer = _firstZeroTimer; | |
| 332 assert(timer._milliSeconds == 0); | |
| 333 _firstZeroTimer = timer._indexOrNext; | |
| 334 if (_firstZeroTimer == null) { | |
| 335 _lastZeroTimer = null; | |
| 336 listTime = currentTime + 1; | |
| 337 } else { | |
| 338 // We want to drain all entries from the list as they should have | |
| 339 // been pending for 0 ms. To prevent issues with current time moving | |
| 340 // we ensure that the listTime does not go beyond current, unless | |
| 341 // the list is empty. | |
| 342 listTime = _firstZeroTimer._wakeupTime; | |
| 343 if (listTime > currentTime) { | |
| 344 listTime = currentTime; | |
| 345 } | |
| 346 } | |
| 347 } | |
| 348 | |
| 349 // Append this timer to the pending timer list. | |
| 350 timer._indexOrNext = null; | |
| 351 if (head == null) { | |
| 352 assert(tail == null); | |
| 353 head = timer; | |
| 354 tail = timer; | |
| 355 } else { | |
| 356 tail._indexOrNext = timer; | |
| 357 tail = timer; | |
| 358 } | |
| 359 } | |
| 360 } | |
| 361 | |
| 362 // No timers queued: Early exit. | |
| 363 if (head == null) { | |
| 364 return; | |
| 365 } | |
| 366 | |
| 367 // If there are no pending timers currently reset the id space before we | |
| 368 // have a chance to enqueue new timers. | |
| 369 assert(_firstZeroTimer == null); | |
| 370 if (_heap.isEmpty) { | |
| 371 _idCount = 0; | |
| 372 } | |
| 373 | |
| 374 // Trigger all of the pending timers. New timers added as part of the | |
| 375 // callbacks will be enqueued now and notified in the next spin at the | |
| 376 // earliest. | |
| 377 _handlingCallbacks = true; | |
| 378 try { | |
| 379 while (head != null) { | |
| 380 // Dequeue the first candidate timer. | |
| 381 var timer = head; | |
| 382 head = timer._indexOrNext; | |
| 383 timer._indexOrNext = null; | |
| 384 | |
| 385 // One of the timers in the pending_timers list can cancel | |
| 386 // one of the later timers which will set the callback to | |
| 387 // null. | |
| 388 if (timer._callback != null) { | |
| 389 var callback = timer._callback; | |
| 390 if (!timer._repeating) { | |
| 391 // Mark timer as inactive. | |
| 392 timer._callback = null; | |
| 393 } | |
| 394 callback(timer); | |
| 395 // Re-insert repeating timer if not canceled. | |
| 396 if (timer._repeating && (timer._callback != null)) { | |
| 397 timer._advanceWakeupTime(); | |
| 398 timer._addTimerToHeap(); | |
| 399 } | |
| 400 // Execute pending micro tasks. | |
| 401 pendingImmediateCallback(); | |
| 402 } | |
| 403 } | |
| 404 } finally { | |
| 405 _handlingCallbacks = false; | |
| 406 _notifyEventHandler(); | |
| 407 } | |
| 408 } | |
| 409 | |
| 410 // Creates a receive port and registers an empty handler on that port. Just | |
| 411 // the triggering of the event loop will ensure that timers are executed. | |
| 412 static _ignoreMessage(_) { | |
| 413 _messagePending = false; | |
| 414 } | |
| 415 | |
| 416 static void _createTimerHandler() { | |
| 417 assert(_receivePort == null); | |
| 418 _receivePort = new RawReceivePort(_ignoreMessage); | |
| 419 _sendPort = _receivePort.sendPort; | |
| 420 _scheduledWakeupTime = null; | |
| 421 _messagePending = false; | |
| 422 } | |
| 423 | |
| 424 static void _shutdownTimerHandler() { | |
| 425 _receivePort.close(); | |
| 426 _receivePort = null; | |
| 427 _sendPort = null; | |
| 428 _scheduledWakeupTime = null; | |
| 429 _messagePending = false; | |
| 430 } | |
| 431 | |
| 432 // The Timer factory registered with the dart:async library by the embedder. | |
| 433 static Timer _factory(int milliSeconds, | |
| 434 void callback(Timer timer), | |
| 435 bool repeating) { | |
| 436 if (repeating) { | |
| 437 return new _Timer.periodic(milliSeconds, callback); | |
| 438 } | |
| 439 return new _Timer(milliSeconds, callback); | |
| 440 } | |
| 441 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 878323002:
- Move timer implementation closer to the rest of message handling. (Closed)
Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/