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