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