code.vuplus.com Git - vuplus_webkit/blob - 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