WebCore:
[WebKit-https.git] / WebCore / platform / Timer.cpp
1 /*
2  * Copyright (C) 2006 Apple Computer, Inc.  All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27 #include "Timer.h"
28
29 #include "SharedTimer.h"
30 #include "SystemTime.h"
31 #include <math.h>
32 #include <limits>
33 #include <wtf/HashSet.h>
34 #include <wtf/Vector.h>
35
36 using namespace std;
37
38 namespace WebCore {
39
40 // Timers are stored in a heap data structure, used to implement a priority queue.
41 // This allows us to efficiently determine which timer needs to fire the soonest.
42 // Then we set a single shared system timer to fire at that time.
43 //
44 // When a timer's "next fire time" changes, we need to move it around in the priority queue.
45
46 // ----------------
47
48 static bool deferringTimers;
49 static Vector<TimerBase*>* timerHeap;
50 static HashSet<const TimerBase*>* timersReadyToFire;
51
52 // ----------------
53
54 // Class to represent elements in the heap when calling the standard library heap algorithms.
55 // Maintains the m_heapIndex value in the timers themselves, which allows us to do efficient
56 // modification of the heap.
57 class TimerHeapElement {
58 public:
59     explicit TimerHeapElement(int i) : m_index(i), m_timer((*timerHeap)[m_index]) { checkConsistency(); }
60
61     TimerHeapElement(const TimerHeapElement&);
62     TimerHeapElement& operator=(const TimerHeapElement&);
63
64     TimerBase* timer() const { return m_timer; }
65
66     void checkConsistency() const {
67         ASSERT(m_index >= 0);
68         ASSERT(m_index < (timerHeap ? static_cast<int>(timerHeap->size()) : 0));
69     }
70
71 private:
72     TimerHeapElement();
73
74     int m_index;
75     TimerBase* m_timer;
76 };
77
78 inline TimerHeapElement::TimerHeapElement(const TimerHeapElement& o)
79     : m_index(-1), m_timer(o.timer())
80 {
81 }
82
83 inline TimerHeapElement& TimerHeapElement::operator=(const TimerHeapElement& o)
84 {
85     TimerBase* t = o.timer();
86     m_timer = t;
87     if (m_index != -1) {
88         checkConsistency();
89         (*timerHeap)[m_index] = t;
90         t->m_heapIndex = m_index;
91     }
92     return *this;
93 }
94
95 inline bool operator<(const TimerHeapElement& a, const TimerHeapElement& b)
96 {
97     // The comparisons below are "backwards" because the heap puts the largest 
98     // element first and we want the lowest time to be the first one in the heap.
99     double aFireTime = a.timer()->m_nextFireTime;
100     double bFireTime = b.timer()->m_nextFireTime;
101     if (bFireTime != aFireTime)
102         return bFireTime < aFireTime;
103     
104     // We need to look at the difference of the insertion orders instead of comparing the two 
105     // outright in case of overflow. 
106     unsigned difference = a.timer()->m_heapInsertionOrder - b.timer()->m_heapInsertionOrder;
107     return difference < UINT_MAX / 2;
108 }
109
110 // ----------------
111
112 // Class to represent iterators in the heap when calling the standard library heap algorithms.
113 // Returns TimerHeapElement for elements in the heap rather than the TimerBase pointers themselves.
114 class TimerHeapIterator : public iterator<random_access_iterator_tag, TimerHeapElement, int> {
115 public:
116     TimerHeapIterator() : m_index(-1) { }
117     TimerHeapIterator(int i) : m_index(i) { checkConsistency(); }
118
119     TimerHeapIterator& operator++() { checkConsistency(); ++m_index; checkConsistency(); return *this; }
120     TimerHeapIterator operator++(int) { checkConsistency(); checkConsistency(1); return m_index++; }
121
122     TimerHeapIterator& operator--() { checkConsistency(); --m_index; checkConsistency(); return *this; }
123     TimerHeapIterator operator--(int) { checkConsistency(); checkConsistency(-1); return m_index--; }
124
125     TimerHeapIterator& operator+=(int i) { checkConsistency(); m_index += i; checkConsistency(); return *this; }
126     TimerHeapIterator& operator-=(int i) { checkConsistency(); m_index -= i; checkConsistency(); return *this; }
127
128     TimerHeapElement operator*() const { return TimerHeapElement(m_index); }
129     TimerHeapElement operator[](int i) const { return TimerHeapElement(m_index + i); }
130
131     int index() const { return m_index; }
132
133     void checkConsistency(int offset = 0) const {
134         ASSERT(m_index + offset >= 0);
135         ASSERT(m_index + offset <= (timerHeap ? static_cast<int>(timerHeap->size()) : 0));
136     }
137
138 private:
139     int m_index;
140 };
141
142 inline bool operator==(TimerHeapIterator a, TimerHeapIterator b) { return a.index() == b.index(); }
143 inline bool operator!=(TimerHeapIterator a, TimerHeapIterator b) { return a.index() != b.index(); }
144 inline bool operator<(TimerHeapIterator a, TimerHeapIterator b) { return a.index() < b.index(); }
145
146 inline TimerHeapIterator operator+(TimerHeapIterator a, int b) { return a.index() + b; }
147 inline TimerHeapIterator operator+(int a, TimerHeapIterator b) { return a + b.index(); }
148
149 inline TimerHeapIterator operator-(TimerHeapIterator a, int b) { return a.index() - b; }
150 inline int operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.index() - b.index(); }
151
152 // ----------------
153
154 void updateSharedTimer()
155 {
156     if (timersReadyToFire || deferringTimers || !timerHeap || timerHeap->isEmpty())
157         stopSharedTimer();
158     else
159         setSharedTimerFireTime(timerHeap->first()->m_nextFireTime);
160 }
161
162 // ----------------
163
164 TimerBase::TimerBase()
165     : m_nextFireTime(0), m_repeatInterval(0), m_heapIndex(-1)
166 {
167     // We only need to do this once, but probably not worth trying to optimize it.
168     setSharedTimerFiredFunction(sharedTimerFired);
169 }
170
171 TimerBase::~TimerBase()
172 {
173     stop();
174
175     ASSERT(!inHeap());
176 }
177
178 void TimerBase::start(double nextFireInterval, double repeatInterval)
179 {
180     m_repeatInterval = repeatInterval;
181     setNextFireTime(currentTime() + nextFireInterval);
182 }
183
184 void TimerBase::stop()
185 {
186     m_repeatInterval = 0;
187     setNextFireTime(0);
188
189     ASSERT(m_nextFireTime == 0);
190     ASSERT(m_repeatInterval == 0);
191     ASSERT(!inHeap());
192 }
193
194 bool TimerBase::isActive() const
195 {
196     return m_nextFireTime || (timersReadyToFire && timersReadyToFire->contains(this));
197 }
198
199 double TimerBase::nextFireInterval() const
200 {
201     ASSERT(isActive());
202     double current = currentTime();
203     if (m_nextFireTime < current)
204         return 0;
205     return m_nextFireTime - current;
206 }
207
208 inline void TimerBase::checkHeapIndex() const
209 {
210     ASSERT(timerHeap);
211     ASSERT(!timerHeap->isEmpty());
212     ASSERT(m_heapIndex >= 0);
213     ASSERT(m_heapIndex < static_cast<int>(timerHeap->size()));
214     ASSERT((*timerHeap)[m_heapIndex] == this);
215 }
216
217 inline void TimerBase::checkConsistency() const
218 {
219     // Timers should be in the heap if and only if they have a non-zero next fire time.
220     ASSERT(inHeap() == (m_nextFireTime != 0));
221     if (inHeap())
222         checkHeapIndex();
223 }
224
225 void TimerBase::heapDecreaseKey()
226 {
227     ASSERT(m_nextFireTime != 0);
228     checkHeapIndex();
229     push_heap(TimerHeapIterator(0), TimerHeapIterator(m_heapIndex + 1));
230     checkHeapIndex();
231 }
232
233 inline void TimerBase::heapDelete()
234 {
235     ASSERT(m_nextFireTime == 0);
236     heapPop();
237     timerHeap->removeLast();
238     m_heapIndex = -1;
239 }
240
241 inline void TimerBase::heapDeleteMin()
242 {
243     ASSERT(m_nextFireTime == 0);
244     heapPopMin();
245     timerHeap->removeLast();
246     m_heapIndex = -1;
247 }
248
249 inline void TimerBase::heapIncreaseKey()
250 {
251     ASSERT(m_nextFireTime != 0);
252     heapPop();
253     heapDecreaseKey();
254 }
255
256 inline void TimerBase::heapInsert()
257 {
258     ASSERT(!inHeap());
259     if (!timerHeap)
260         timerHeap = new Vector<TimerBase*>;
261     timerHeap->append(this);
262     m_heapIndex = timerHeap->size() - 1;
263     heapDecreaseKey();
264 }
265
266 inline void TimerBase::heapPop()
267 {
268     // Temporarily force this timer to have the minimum key so we can pop it.
269     double fireTime = m_nextFireTime;
270     m_nextFireTime = -numeric_limits<double>::infinity();
271     heapDecreaseKey();
272     heapPopMin();
273     m_nextFireTime = fireTime;
274 }
275
276 void TimerBase::heapPopMin()
277 {
278     ASSERT(this == timerHeap->first());
279     checkHeapIndex();
280     pop_heap(TimerHeapIterator(0), TimerHeapIterator(timerHeap->size()));
281     checkHeapIndex();
282     ASSERT(this == timerHeap->last());
283 }
284
285 void TimerBase::setNextFireTime(double newTime)
286 {
287     // Keep heap valid while changing the next-fire time.
288
289     if (timersReadyToFire)
290         timersReadyToFire->remove(this);
291
292     double oldTime = m_nextFireTime;
293     if (oldTime != newTime) {
294         m_nextFireTime = newTime;
295         static unsigned currentHeapInsertionOrder;
296         m_heapInsertionOrder = currentHeapInsertionOrder++;
297
298         bool wasFirstTimerInHeap = m_heapIndex == 0;
299
300         if (oldTime == 0)
301             heapInsert();
302         else if (newTime == 0)
303             heapDelete();
304         else if (newTime < oldTime)
305             heapDecreaseKey();
306         else
307             heapIncreaseKey();
308
309         bool isFirstTimerInHeap = m_heapIndex == 0;
310
311         if (wasFirstTimerInHeap || isFirstTimerInHeap)
312             updateSharedTimer();
313     }
314
315     checkConsistency();
316 }
317
318 void TimerBase::collectFiringTimers(double fireTime, Vector<TimerBase*>& firingTimers)
319 {
320     while (!timerHeap->isEmpty() && timerHeap->first()->m_nextFireTime <= fireTime) {
321         TimerBase* timer = timerHeap->first();
322         firingTimers.append(timer);
323         timersReadyToFire->add(timer);
324         timer->m_nextFireTime = 0;
325         timer->heapDeleteMin();
326     }
327 }
328
329 void TimerBase::fireTimers(double fireTime, const Vector<TimerBase*>& firingTimers)
330 {
331     int size = firingTimers.size();
332     for (int i = 0; i != size; ++i) {
333         TimerBase* timer = firingTimers[i];
334
335         // If not in the set, this timer has been deleted or re-scheduled in another timer's fired function.
336         // So either we don't want to fire it at all or we will fire it next time the shared timer goes off.
337         // It might even have been deleted; that's OK because we won't do anything else with the pointer.
338         if (!timersReadyToFire->contains(timer))
339             continue;
340
341         // Setting the next fire time has a side effect of removing the timer from the firing timers set.
342         double interval = timer->repeatInterval();
343         timer->setNextFireTime(interval ? fireTime + interval : 0);
344
345         // Once the timer has been fired, it may be deleted, so do nothing else with it after this point.
346         timer->fired();
347
348         // Catch the case where the timer asked timers to fire in a nested event loop.
349         if (!timersReadyToFire)
350             break;
351     }
352 }
353
354 void TimerBase::sharedTimerFired()
355 {
356     // Do a re-entrancy check.
357     if (timersReadyToFire)
358         return;
359
360     double fireTime = currentTime();
361     Vector<TimerBase*> firingTimers;
362     HashSet<const TimerBase*> firingTimersSet;
363
364     timersReadyToFire = &firingTimersSet;
365
366     collectFiringTimers(fireTime, firingTimers);
367     fireTimers(fireTime, firingTimers);
368
369     timersReadyToFire = 0;
370
371     updateSharedTimer();
372 }
373
374 void TimerBase::fireTimersInNestedEventLoop()
375 {
376     timersReadyToFire = 0;
377     updateSharedTimer();
378 }
379
380 // ----------------
381
382 bool isDeferringTimers()
383 {
384     return deferringTimers;
385 }
386
387 void setDeferringTimers(bool shouldDefer)
388 {
389     if (shouldDefer == deferringTimers)
390         return;
391     deferringTimers = shouldDefer;
392     updateSharedTimer();
393 }
394
395 }