Unreviewed, rolling out r126169.
[WebKit-https.git] / Source / WebCore / platform / Timer.cpp
1 /*
2  * Copyright (C) 2006, 2008 Apple Inc. All rights reserved.
3  * Copyright (C) 2009 Google Inc. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
25  */
26
27 #include "config.h"
28 #include "Timer.h"
29
30 #include "SharedTimer.h"
31 #include "ThreadGlobalData.h"
32 #include "ThreadTimers.h"
33 #include <limits.h>
34 #include <limits>
35 #include <math.h>
36 #include <wtf/CurrentTime.h>
37 #include <wtf/HashSet.h>
38 #include <wtf/Vector.h>
39
40 using namespace std;
41
42 namespace WebCore {
43
44 class TimerHeapReference;
45
46 // Timers are stored in a heap data structure, used to implement a priority queue.
47 // This allows us to efficiently determine which timer needs to fire the soonest.
48 // Then we set a single shared system timer to fire at that time.
49 //
50 // When a timer's "next fire time" changes, we need to move it around in the priority queue.
51
52 // Simple accessors to thread-specific data.
53 static Vector<TimerBase*>& timerHeap()
54 {
55     return threadGlobalData().threadTimers().timerHeap();
56 }
57
58 // ----------------
59
60 class TimerHeapPointer {
61 public:
62     TimerHeapPointer(TimerBase** pointer) : m_pointer(pointer) { }
63     TimerHeapReference operator*() const;
64     TimerBase* operator->() const { return *m_pointer; }
65 private:
66     TimerBase** m_pointer;
67 };
68
69 class TimerHeapReference {
70 public:
71     TimerHeapReference(TimerBase*& reference) : m_reference(reference) { }
72     operator TimerBase*() const { return m_reference; }
73     TimerHeapPointer operator&() const { return &m_reference; }
74     TimerHeapReference& operator=(TimerBase*);
75     TimerHeapReference& operator=(TimerHeapReference);
76 private:
77     TimerBase*& m_reference;
78 };
79
80 inline TimerHeapReference TimerHeapPointer::operator*() const
81 {
82     return *m_pointer;
83 }
84
85 inline TimerHeapReference& TimerHeapReference::operator=(TimerBase* timer)
86 {
87     m_reference = timer;
88     Vector<TimerBase*>& heap = timerHeap();
89     if (&m_reference >= heap.data() && &m_reference < heap.data() + heap.size())
90         timer->m_heapIndex = &m_reference - heap.data();
91     return *this;
92 }
93
94 inline TimerHeapReference& TimerHeapReference::operator=(TimerHeapReference b)
95 {
96     TimerBase* timer = b;
97     return *this = timer;
98 }
99
100 inline void swap(TimerHeapReference a, TimerHeapReference b)
101 {
102     TimerBase* timerA = a;
103     TimerBase* timerB = b;
104
105     // Invoke the assignment operator, since that takes care of updating m_heapIndex.
106     a = timerB;
107     b = timerA;
108 }
109
110 // ----------------
111
112 // Class to represent iterators in the heap when calling the standard library heap algorithms.
113 // Uses a custom pointer and reference type that update indices for pointers in the heap.
114 class TimerHeapIterator : public iterator<random_access_iterator_tag, TimerBase*, ptrdiff_t, TimerHeapPointer, TimerHeapReference> {
115 public:
116     explicit TimerHeapIterator(TimerBase** pointer) : m_pointer(pointer) { checkConsistency(); }
117
118     TimerHeapIterator& operator++() { checkConsistency(); ++m_pointer; checkConsistency(); return *this; }
119     TimerHeapIterator operator++(int) { checkConsistency(1); return TimerHeapIterator(m_pointer++); }
120
121     TimerHeapIterator& operator--() { checkConsistency(); --m_pointer; checkConsistency(); return *this; }
122     TimerHeapIterator operator--(int) { checkConsistency(-1); return TimerHeapIterator(m_pointer--); }
123
124     TimerHeapIterator& operator+=(ptrdiff_t i) { checkConsistency(); m_pointer += i; checkConsistency(); return *this; }
125     TimerHeapIterator& operator-=(ptrdiff_t i) { checkConsistency(); m_pointer -= i; checkConsistency(); return *this; }
126
127     TimerHeapReference operator*() const { return TimerHeapReference(*m_pointer); }
128     TimerHeapReference operator[](ptrdiff_t i) const { return TimerHeapReference(m_pointer[i]); }
129     TimerBase* operator->() const { return *m_pointer; }
130
131 private:
132     void checkConsistency(ptrdiff_t offset = 0) const
133     {
134         ASSERT(m_pointer >= timerHeap().data());
135         ASSERT(m_pointer <= timerHeap().data() + timerHeap().size());
136         ASSERT_UNUSED(offset, m_pointer + offset >= timerHeap().data());
137         ASSERT_UNUSED(offset, m_pointer + offset <= timerHeap().data() + timerHeap().size());
138     }
139
140     friend bool operator==(TimerHeapIterator, TimerHeapIterator);
141     friend bool operator!=(TimerHeapIterator, TimerHeapIterator);
142     friend bool operator<(TimerHeapIterator, TimerHeapIterator);
143     friend bool operator>(TimerHeapIterator, TimerHeapIterator);
144     friend bool operator<=(TimerHeapIterator, TimerHeapIterator);
145     friend bool operator>=(TimerHeapIterator, TimerHeapIterator);
146     
147     friend TimerHeapIterator operator+(TimerHeapIterator, size_t);
148     friend TimerHeapIterator operator+(size_t, TimerHeapIterator);
149     
150     friend TimerHeapIterator operator-(TimerHeapIterator, size_t);
151     friend ptrdiff_t operator-(TimerHeapIterator, TimerHeapIterator);
152
153     TimerBase** m_pointer;
154 };
155
156 inline bool operator==(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer == b.m_pointer; }
157 inline bool operator!=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer != b.m_pointer; }
158 inline bool operator<(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer < b.m_pointer; }
159 inline bool operator>(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer > b.m_pointer; }
160 inline bool operator<=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer <= b.m_pointer; }
161 inline bool operator>=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer >= b.m_pointer; }
162
163 inline TimerHeapIterator operator+(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer + b); }
164 inline TimerHeapIterator operator+(size_t a, TimerHeapIterator b) { return TimerHeapIterator(a + b.m_pointer); }
165
166 inline TimerHeapIterator operator-(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer - b); }
167 inline ptrdiff_t operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer - b.m_pointer; }
168
169 // ----------------
170
171 class TimerHeapLessThanFunction {
172 public:
173     bool operator()(TimerBase*, TimerBase*) const;
174 };
175
176 inline bool TimerHeapLessThanFunction::operator()(TimerBase* a, TimerBase* b) const
177 {
178     // The comparisons below are "backwards" because the heap puts the largest 
179     // element first and we want the lowest time to be the first one in the heap.
180     double aFireTime = a->m_nextFireTime;
181     double bFireTime = b->m_nextFireTime;
182     if (bFireTime != aFireTime)
183         return bFireTime < aFireTime;
184     
185     // We need to look at the difference of the insertion orders instead of comparing the two 
186     // outright in case of overflow. 
187     unsigned difference = a->m_heapInsertionOrder - b->m_heapInsertionOrder;
188     return difference < numeric_limits<unsigned>::max() / 2;
189 }
190
191 // ----------------
192
193 TimerBase::TimerBase()
194     : m_nextFireTime(0)
195     , m_repeatInterval(0)
196     , m_heapIndex(-1)
197 #ifndef NDEBUG
198     , m_thread(currentThread())
199 #endif
200 {
201 }
202
203 TimerBase::~TimerBase()
204 {
205     stop();
206     ASSERT(!inHeap());
207 }
208
209 void TimerBase::start(double nextFireInterval, double repeatInterval)
210 {
211     ASSERT(m_thread == currentThread());
212
213     m_repeatInterval = repeatInterval;
214     setNextFireTime(monotonicallyIncreasingTime() + nextFireInterval);
215 }
216
217 void TimerBase::stop()
218 {
219     ASSERT(m_thread == currentThread());
220
221     m_repeatInterval = 0;
222     setNextFireTime(0);
223
224     ASSERT(m_nextFireTime == 0);
225     ASSERT(m_repeatInterval == 0);
226     ASSERT(!inHeap());
227 }
228
229 double TimerBase::nextFireInterval() const
230 {
231     ASSERT(isActive());
232     double current = monotonicallyIncreasingTime();
233     if (m_nextFireTime < current)
234         return 0;
235     return m_nextFireTime - current;
236 }
237
238 inline void TimerBase::checkHeapIndex() const
239 {
240     ASSERT(!timerHeap().isEmpty());
241     ASSERT(m_heapIndex >= 0);
242     ASSERT(m_heapIndex < static_cast<int>(timerHeap().size()));
243     ASSERT(timerHeap()[m_heapIndex] == this);
244 }
245
246 inline void TimerBase::checkConsistency() const
247 {
248     // Timers should be in the heap if and only if they have a non-zero next fire time.
249     ASSERT(inHeap() == (m_nextFireTime != 0));
250     if (inHeap())
251         checkHeapIndex();
252 }
253
254 void TimerBase::heapDecreaseKey()
255 {
256     ASSERT(m_nextFireTime != 0);
257     checkHeapIndex();
258     TimerBase** heapData = timerHeap().data();
259     push_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + m_heapIndex + 1), TimerHeapLessThanFunction());
260     checkHeapIndex();
261 }
262
263 inline void TimerBase::heapDelete()
264 {
265     ASSERT(m_nextFireTime == 0);
266     heapPop();
267     timerHeap().removeLast();
268     m_heapIndex = -1;
269 }
270
271 void TimerBase::heapDeleteMin()
272 {
273     ASSERT(m_nextFireTime == 0);
274     heapPopMin();
275     timerHeap().removeLast();
276     m_heapIndex = -1;
277 }
278
279 inline void TimerBase::heapIncreaseKey()
280 {
281     ASSERT(m_nextFireTime != 0);
282     heapPop();
283     heapDecreaseKey();
284 }
285
286 inline void TimerBase::heapInsert()
287 {
288     ASSERT(!inHeap());
289     timerHeap().append(this);
290     m_heapIndex = timerHeap().size() - 1;
291     heapDecreaseKey();
292 }
293
294 inline void TimerBase::heapPop()
295 {
296     // Temporarily force this timer to have the minimum key so we can pop it.
297     double fireTime = m_nextFireTime;
298     m_nextFireTime = -numeric_limits<double>::infinity();
299     heapDecreaseKey();
300     heapPopMin();
301     m_nextFireTime = fireTime;
302 }
303
304 void TimerBase::heapPopMin()
305 {
306     ASSERT(this == timerHeap().first());
307     checkHeapIndex();
308     Vector<TimerBase*>& heap = timerHeap();
309     TimerBase** heapData = heap.data();
310     pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction());
311     checkHeapIndex();
312     ASSERT(this == timerHeap().last());
313 }
314
315 void TimerBase::setNextFireTime(double newTime)
316 {
317     ASSERT(m_thread == currentThread());
318
319     // Keep heap valid while changing the next-fire time.
320     double oldTime = m_nextFireTime;
321     if (oldTime != newTime) {
322         m_nextFireTime = newTime;
323         static unsigned currentHeapInsertionOrder;
324         m_heapInsertionOrder = currentHeapInsertionOrder++;
325
326         bool wasFirstTimerInHeap = m_heapIndex == 0;
327
328         if (oldTime == 0)
329             heapInsert();
330         else if (newTime == 0)
331             heapDelete();
332         else if (newTime < oldTime)
333             heapDecreaseKey();
334         else
335             heapIncreaseKey();
336
337         bool isFirstTimerInHeap = m_heapIndex == 0;
338
339         if (wasFirstTimerInHeap || isFirstTimerInHeap)
340             threadGlobalData().threadTimers().updateSharedTimer();
341     }
342
343     checkConsistency();
344 }
345
346 void TimerBase::fireTimersInNestedEventLoop()
347 {
348     // Redirect to ThreadTimers.
349     threadGlobalData().threadTimers().fireTimersInNestedEventLoop();
350 }
351
352 } // namespace WebCore
353