← Back to branch summary

~ubuntu-branches/ubuntu/raring/qtwebkit-source/raring-proposed

« back to all changes in this revision

Viewing changes to Source/WebCore/platform/Timer.cpp

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2013-02-18 14:24:18 UTC
  • Revision ID: package-import@ubuntu.com-20130218142418-eon0jmjg3nj438uy
Tags: upstream-2.3
Import upstream version 2.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
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_unalignedNextFireTime(0)
 
196
    , m_repeatInterval(0)
 
197
    , m_heapIndex(-1)
 
198
#ifndef NDEBUG
 
199
    , m_thread(currentThread())
 
200
#endif
 
201
{
 
202
}
 
203
 
 
204
TimerBase::~TimerBase()
 
205
{
 
206
    stop();
 
207
    ASSERT(!inHeap());
 
208
}
 
209
 
 
210
void TimerBase::start(double nextFireInterval, double repeatInterval)
 
211
{
 
212
    ASSERT(m_thread == currentThread());
 
213
 
 
214
    m_repeatInterval = repeatInterval;
 
215
    setNextFireTime(monotonicallyIncreasingTime() + nextFireInterval);
 
216
}
 
217
 
 
218
void TimerBase::stop()
 
219
{
 
220
    ASSERT(m_thread == currentThread());
 
221
 
 
222
    m_repeatInterval = 0;
 
223
    setNextFireTime(0);
 
224
 
 
225
    ASSERT(m_nextFireTime == 0);
 
226
    ASSERT(m_repeatInterval == 0);
 
227
    ASSERT(!inHeap());
 
228
}
 
229
 
 
230
double TimerBase::nextFireInterval() const
 
231
{
 
232
    ASSERT(isActive());
 
233
    double current = monotonicallyIncreasingTime();
 
234
    if (m_nextFireTime < current)
 
235
        return 0;
 
236
    return m_nextFireTime - current;
 
237
}
 
238
 
 
239
inline void TimerBase::checkHeapIndex() const
 
240
{
 
241
    ASSERT(!timerHeap().isEmpty());
 
242
    ASSERT(m_heapIndex >= 0);
 
243
    ASSERT(m_heapIndex < static_cast<int>(timerHeap().size()));
 
244
    ASSERT(timerHeap()[m_heapIndex] == this);
 
245
}
 
246
 
 
247
inline void TimerBase::checkConsistency() const
 
248
{
 
249
    // Timers should be in the heap if and only if they have a non-zero next fire time.
 
250
    ASSERT(inHeap() == (m_nextFireTime != 0));
 
251
    if (inHeap())
 
252
        checkHeapIndex();
 
253
}
 
254
 
 
255
void TimerBase::heapDecreaseKey()
 
256
{
 
257
    ASSERT(m_nextFireTime != 0);
 
258
    checkHeapIndex();
 
259
    TimerBase** heapData = timerHeap().data();
 
260
    push_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + m_heapIndex + 1), TimerHeapLessThanFunction());
 
261
    checkHeapIndex();
 
262
}
 
263
 
 
264
inline void TimerBase::heapDelete()
 
265
{
 
266
    ASSERT(m_nextFireTime == 0);
 
267
    heapPop();
 
268
    timerHeap().removeLast();
 
269
    m_heapIndex = -1;
 
270
}
 
271
 
 
272
void TimerBase::heapDeleteMin()
 
273
{
 
274
    ASSERT(m_nextFireTime == 0);
 
275
    heapPopMin();
 
276
    timerHeap().removeLast();
 
277
    m_heapIndex = -1;
 
278
}
 
279
 
 
280
inline void TimerBase::heapIncreaseKey()
 
281
{
 
282
    ASSERT(m_nextFireTime != 0);
 
283
    heapPop();
 
284
    heapDecreaseKey();
 
285
}
 
286
 
 
287
inline void TimerBase::heapInsert()
 
288
{
 
289
    ASSERT(!inHeap());
 
290
    timerHeap().append(this);
 
291
    m_heapIndex = timerHeap().size() - 1;
 
292
    heapDecreaseKey();
 
293
}
 
294
 
 
295
inline void TimerBase::heapPop()
 
296
{
 
297
    // Temporarily force this timer to have the minimum key so we can pop it.
 
298
    double fireTime = m_nextFireTime;
 
299
    m_nextFireTime = -numeric_limits<double>::infinity();
 
300
    heapDecreaseKey();
 
301
    heapPopMin();
 
302
    m_nextFireTime = fireTime;
 
303
}
 
304
 
 
305
void TimerBase::heapPopMin()
 
306
{
 
307
    ASSERT(this == timerHeap().first());
 
308
    checkHeapIndex();
 
309
    Vector<TimerBase*>& heap = timerHeap();
 
310
    TimerBase** heapData = heap.data();
 
311
    pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction());
 
312
    checkHeapIndex();
 
313
    ASSERT(this == timerHeap().last());
 
314
}
 
315
 
 
316
void TimerBase::setNextFireTime(double newUnalignedTime)
 
317
{
 
318
    ASSERT(m_thread == currentThread());
 
319
 
 
320
    if (m_unalignedNextFireTime != newUnalignedTime)
 
321
        m_unalignedNextFireTime = newUnalignedTime;
 
322
 
 
323
    // Keep heap valid while changing the next-fire time.
 
324
    double oldTime = m_nextFireTime;
 
325
    double newTime = alignedFireTime(newUnalignedTime);
 
326
    if (oldTime != newTime) {
 
327
        m_nextFireTime = newTime;
 
328
        static unsigned currentHeapInsertionOrder;
 
329
        m_heapInsertionOrder = currentHeapInsertionOrder++;
 
330
 
 
331
        bool wasFirstTimerInHeap = m_heapIndex == 0;
 
332
 
 
333
        if (oldTime == 0)
 
334
            heapInsert();
 
335
        else if (newTime == 0)
 
336
            heapDelete();
 
337
        else if (newTime < oldTime)
 
338
            heapDecreaseKey();
 
339
        else
 
340
            heapIncreaseKey();
 
341
 
 
342
        bool isFirstTimerInHeap = m_heapIndex == 0;
 
343
 
 
344
        if (wasFirstTimerInHeap || isFirstTimerInHeap)
 
345
            threadGlobalData().threadTimers().updateSharedTimer();
 
346
    }
 
347
 
 
348
    checkConsistency();
 
349
}
 
350
 
 
351
void TimerBase::fireTimersInNestedEventLoop()
 
352
{
 
353
    // Redirect to ThreadTimers.
 
354
    threadGlobalData().threadTimers().fireTimersInNestedEventLoop();
 
355
}
 
356
 
 
357
void TimerBase::didChangeAlignmentInterval()
 
358
{
 
359
    setNextFireTime(m_unalignedNextFireTime);
 
360
}
 
361
 
 
362
double TimerBase::nextUnalignedFireInterval() const
 
363
{
 
364
    ASSERT(isActive());
 
365
    return max(m_unalignedNextFireTime - monotonicallyIncreasingTime(), 0.0);
 
366
}
 
367
 
 
368
} // namespace WebCore
 
369