ee2f95970bb15eebe9f2810b6ec39ab9126cbd12
[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     // Note, this is "backwards" because the heap puts the largest element first
98     // and we want the lowest time to be the first one in the heap.
99     return b.timer()->m_nextFireTime < a.timer()->m_nextFireTime;
100 }
101
102 // ----------------
103
104 // Class to represent iterators in the heap when calling the standard library heap algorithms.
105 // Returns TimerHeapElement for elements in the heap rather than the TimerBase pointers themselves.
106 class TimerHeapIterator : public iterator<random_access_iterator_tag, TimerHeapElement, int> {
107 public:
108     TimerHeapIterator() : m_index(-1) { }
109     TimerHeapIterator(int i) : m_index(i) { checkConsistency(); }
110
111     TimerHeapIterator& operator++() { checkConsistency(); ++m_index; checkConsistency(); return *this; }
112     TimerHeapIterator operator++(int) { checkConsistency(); checkConsistency(1); return m_index++; }
113
114     TimerHeapIterator& operator--() { checkConsistency(); --m_index; checkConsistency(); return *this; }
115     TimerHeapIterator operator--(int) { checkConsistency(); checkConsistency(-1); return m_index--; }
116
117     TimerHeapIterator& operator+=(int i) { checkConsistency(); m_index += i; checkConsistency(); return *this; }
118     TimerHeapIterator& operator-=(int i) { checkConsistency(); m_index -= i; checkConsistency(); return *this; }
119
120     TimerHeapElement operator*() const { return TimerHeapElement(m_index); }
121     TimerHeapElement operator[](int i) const { return TimerHeapElement(m_index + i); }
122
123     int index() const { return m_index; }
124
125     void checkConsistency(int offset = 0) const {
126         ASSERT(m_index + offset >= 0);
127         ASSERT(m_index + offset <= (timerHeap ? static_cast<int>(timerHeap->size()) : 0));
128     }
129
130 private:
131     int m_index;
132 };
133
134 inline bool operator==(TimerHeapIterator a, TimerHeapIterator b) { return a.index() == b.index(); }
135 inline bool operator!=(TimerHeapIterator a, TimerHeapIterator b) { return a.index() != b.index(); }
136 inline bool operator<(TimerHeapIterator a, TimerHeapIterator b) { return a.index() < b.index(); }
137
138 inline TimerHeapIterator operator+(TimerHeapIterator a, int b) { return a.index() + b; }
139 inline TimerHeapIterator operator+(int a, TimerHeapIterator b) { return a + b.index(); }
140
141 inline TimerHeapIterator operator-(TimerHeapIterator a, int b) { return a.index() - b; }
142 inline int operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.index() - b.index(); }
143
144 // ----------------
145
146 void updateSharedTimer()
147 {
148     if (timersReadyToFire || deferringTimers || !timerHeap || timerHeap->isEmpty())
149         stopSharedTimer();
150     else
151         setSharedTimerFireTime(timerHeap->first()->m_nextFireTime);
152 }
153
154 // ----------------
155
156 TimerBase::TimerBase()
157     : m_nextFireTime(0), m_repeatInterval(0), m_heapIndex(-1)
158 {
159     // We only need to do this once, but probably not worth trying to optimize it.
160     setSharedTimerFiredFunction(sharedTimerFired);
161 }
162
163 TimerBase::~TimerBase()
164 {
165     stop();
166
167     ASSERT(!inHeap());
168 }
169
170 void TimerBase::start(double nextFireInterval, double repeatInterval)
171 {
172     m_repeatInterval = repeatInterval;
173     setNextFireTime(currentTime() + nextFireInterval);
174 }
175
176 void TimerBase::stop()
177 {
178     m_repeatInterval = 0;
179     setNextFireTime(0);
180
181     ASSERT(m_nextFireTime == 0);
182     ASSERT(m_repeatInterval == 0);
183     ASSERT(!inHeap());
184 }
185
186 bool TimerBase::isActive() const
187 {
188     return m_nextFireTime || (timersReadyToFire && timersReadyToFire->contains(this));
189 }
190
191 double TimerBase::nextFireInterval() const
192 {
193     ASSERT(isActive());
194     double current = currentTime();
195     if (m_nextFireTime < current)
196         return 0;
197     return m_nextFireTime - current;
198 }
199
200 inline void TimerBase::checkHeapIndex() const
201 {
202     ASSERT(timerHeap);
203     ASSERT(!timerHeap->isEmpty());
204     ASSERT(m_heapIndex >= 0);
205     ASSERT(m_heapIndex < static_cast<int>(timerHeap->size()));
206     ASSERT((*timerHeap)[m_heapIndex] == this);
207 }
208
209 inline void TimerBase::checkConsistency() const
210 {
211     // Timers should be in the heap if and only if they have a non-zero next fire time.
212     ASSERT(inHeap() == (m_nextFireTime != 0));
213     if (inHeap())
214         checkHeapIndex();
215 }
216
217 void TimerBase::heapDecreaseKey()
218 {
219     ASSERT(m_nextFireTime != 0);
220     checkHeapIndex();
221     push_heap(TimerHeapIterator(0), TimerHeapIterator(m_heapIndex + 1));
222     checkHeapIndex();
223 }
224
225 inline void TimerBase::heapDelete()
226 {
227     ASSERT(m_nextFireTime == 0);
228     heapPop();
229     timerHeap->removeLast();
230     m_heapIndex = -1;
231 }
232
233 inline void TimerBase::heapDeleteMin()
234 {
235     ASSERT(m_nextFireTime == 0);
236     heapPopMin();
237     timerHeap->removeLast();
238     m_heapIndex = -1;
239 }
240
241 inline void TimerBase::heapIncreaseKey()
242 {
243     ASSERT(m_nextFireTime != 0);
244     heapPop();
245     heapDecreaseKey();
246 }
247
248 inline void TimerBase::heapInsert()
249 {
250     ASSERT(!inHeap());
251     if (!timerHeap)
252         timerHeap = new Vector<TimerBase*>;
253     timerHeap->append(this);
254     m_heapIndex = timerHeap->size() - 1;
255     heapDecreaseKey();
256 }
257
258 inline void TimerBase::heapPop()
259 {
260     // Temporarily force this timer to have the minimum key so we can pop it.
261     double fireTime = m_nextFireTime;
262     m_nextFireTime = -numeric_limits<double>::infinity();
263     heapDecreaseKey();
264     heapPopMin();
265     m_nextFireTime = fireTime;
266 }
267
268 void TimerBase::heapPopMin()
269 {
270     ASSERT(this == timerHeap->first());
271     checkHeapIndex();
272     pop_heap(TimerHeapIterator(0), TimerHeapIterator(timerHeap->size()));
273     checkHeapIndex();
274     ASSERT(this == timerHeap->last());
275 }
276
277 void TimerBase::setNextFireTime(double newTime)
278 {
279     // Keep heap valid while changing the next-fire time.
280
281     if (timersReadyToFire)
282         timersReadyToFire->remove(this);
283
284     double oldTime = m_nextFireTime;
285     if (oldTime != newTime) {
286         m_nextFireTime = newTime;
287
288         bool wasFirstTimerInHeap = m_heapIndex == 0;
289
290         if (oldTime == 0)
291             heapInsert();
292         else if (newTime == 0)
293             heapDelete();
294         else if (newTime < oldTime)
295             heapDecreaseKey();
296         else
297             heapIncreaseKey();
298
299         bool isFirstTimerInHeap = m_heapIndex == 0;
300
301         if (wasFirstTimerInHeap || isFirstTimerInHeap)
302             updateSharedTimer();
303     }
304
305     checkConsistency();
306 }
307
308 void TimerBase::collectFiringTimers(double fireTime, Vector<TimerBase*>& firingTimers)
309 {
310     while (!timerHeap->isEmpty() && timerHeap->first()->m_nextFireTime <= fireTime) {
311         TimerBase* timer = timerHeap->first();
312         firingTimers.append(timer);
313         timersReadyToFire->add(timer);
314         timer->m_nextFireTime = 0;
315         timer->heapDeleteMin();
316     }
317 }
318
319 void TimerBase::fireTimers(double fireTime, const Vector<TimerBase*>& firingTimers)
320 {
321     int size = firingTimers.size();
322     for (int i = 0; i != size; ++i) {
323         TimerBase* timer = firingTimers[i];
324
325         // If not in the set, this timer has been deleted or re-scheduled in another timer's fired function.
326         // So either we don't want to fire it at all or we will fire it next time the shared timer goes off.
327         // It might even have been deleted; that's OK because we won't do anything else with the pointer.
328         if (!timersReadyToFire->contains(timer))
329             continue;
330
331         // Setting the next fire time has a side effect of removing the timer from the firing timers set.
332         double interval = timer->repeatInterval();
333         timer->setNextFireTime(interval ? fireTime + interval : 0);
334
335         // Once the timer has been fired, it may be deleted, so do nothing else with it after this point.
336         timer->fired();
337
338         // Catch the case where the timer asked timers to fire in a nested event loop.
339         if (!timersReadyToFire)
340             break;
341     }
342 }
343
344 void TimerBase::sharedTimerFired()
345 {
346     // Do a re-entrancy check.
347     if (timersReadyToFire)
348         return;
349
350     double fireTime = currentTime();
351     Vector<TimerBase*> firingTimers;
352     HashSet<const TimerBase*> firingTimersSet;
353
354     timersReadyToFire = &firingTimersSet;
355
356     collectFiringTimers(fireTime, firingTimers);
357     fireTimers(fireTime, firingTimers);
358
359     timersReadyToFire = 0;
360
361     updateSharedTimer();
362 }
363
364 void TimerBase::fireTimersInNestedEventLoop()
365 {
366     timersReadyToFire = 0;
367     updateSharedTimer();
368 }
369
370 // ----------------
371
372 bool isDeferringTimers()
373 {
374     return deferringTimers;
375 }
376
377 void setDeferringTimers(bool shouldDefer)
378 {
379     if (shouldDefer == deferringTimers)
380         return;
381     deferringTimers = shouldDefer;
382     updateSharedTimer();
383 }
384
385 }