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 // Timers are stored in a heap data structure, used to implement a priority queue.

    45 // This allows us to efficiently determine which timer needs to fire the soonest.

    46 // Then we set a single shared system timer to fire at that time.

    47 //

    48 // When a timer's "next fire time" changes, we need to move it around in the priority queue.

    49 

    50 // Simple accessors to thread-specific data.

    51 static Vector<TimerBase*>& timerHeap()

    52 {

    53     return threadGlobalData().threadTimers().timerHeap();

    54 }

    55 

    56 // Class to represent elements in the heap when calling the standard library heap algorithms.

    57 // Maintains the m_heapIndex value in the timers themselves, which allows us to do efficient

    58 // modification of the heap.

    59 class TimerHeapElement {

    60 public:

    61     explicit TimerHeapElement(int i)

    62         : m_index(i)

    63         , m_timer(timerHeap()[m_index])

    64     { 

    65         checkConsistency(); 

    66     }

    67 

    68     TimerHeapElement(const TimerHeapElement&);

    69     TimerHeapElement& operator=(const TimerHeapElement&);

    70 

    71     TimerBase* timer() const { return m_timer; }

    72 

    73     void checkConsistency() const

    74     {

    75         ASSERT(m_index >= 0);

    76         ASSERT(m_index < static_cast<int>(timerHeap().size()));

    77     }

    78 

    79 private:

    80     TimerHeapElement();

    81 

    82     int m_index;

    83     TimerBase* m_timer;

    84 };

    85 

    86 inline TimerHeapElement::TimerHeapElement(const TimerHeapElement& o)

    87     : m_index(-1), m_timer(o.timer())

    88 {

    89 }

    90 

    91 inline TimerHeapElement& TimerHeapElement::operator=(const TimerHeapElement& o)

    92 {

    93     TimerBase* t = o.timer();

    94     m_timer = t;

    95     if (m_index != -1) {

    96         checkConsistency();

    97         timerHeap()[m_index] = t;

    98         t->m_heapIndex = m_index;

    99     }

   100     return *this;

   101 }

   102 

   103 inline bool operator<(const TimerHeapElement& a, const TimerHeapElement& b)

   104 {

   105     // The comparisons below are "backwards" because the heap puts the largest 

   106     // element first and we want the lowest time to be the first one in the heap.

   107     double aFireTime = a.timer()->m_nextFireTime;

   108     double bFireTime = b.timer()->m_nextFireTime;

   109     if (bFireTime != aFireTime)

   110         return bFireTime < aFireTime;

   111     

   112     // We need to look at the difference of the insertion orders instead of comparing the two 

   113     // outright in case of overflow. 

   114     unsigned difference = a.timer()->m_heapInsertionOrder - b.timer()->m_heapInsertionOrder;

   115     return difference < UINT_MAX / 2;

   116 }

   117 

   118 // ----------------

   119 

   120 // Class to represent iterators in the heap when calling the standard library heap algorithms.

   121 // Returns TimerHeapElement for elements in the heap rather than the TimerBase pointers themselves.

   122 class TimerHeapIterator : public iterator<random_access_iterator_tag, TimerHeapElement, int> {

   123 public:

   124     TimerHeapIterator() : m_index(-1) { }

   125     TimerHeapIterator(int i) : m_index(i) { checkConsistency(); }

   126 

   127     TimerHeapIterator& operator++() { checkConsistency(); ++m_index; checkConsistency(); return *this; }

   128     TimerHeapIterator operator++(int) { checkConsistency(); checkConsistency(1); return m_index++; }

   129 

   130     TimerHeapIterator& operator--() { checkConsistency(); --m_index; checkConsistency(); return *this; }

   131     TimerHeapIterator operator--(int) { checkConsistency(); checkConsistency(-1); return m_index--; }

   132 

   133     TimerHeapIterator& operator+=(int i) { checkConsistency(); m_index += i; checkConsistency(); return *this; }

   134     TimerHeapIterator& operator-=(int i) { checkConsistency(); m_index -= i; checkConsistency(); return *this; }

   135 

   136     TimerHeapElement operator*() const { return TimerHeapElement(m_index); }

   137     TimerHeapElement operator[](int i) const { return TimerHeapElement(m_index + i); }

   138 

   139     int index() const { return m_index; }

   140 

   141     void checkConsistency(int offset = 0) const

   142     {

   143         ASSERT_UNUSED(offset, m_index + offset >= 0);

   144         ASSERT_UNUSED(offset, m_index + offset <= static_cast<int>(timerHeap().size()));

   145     }

   146 

   147 private:

   148     int m_index;

   149 };

   150 

   151 inline bool operator==(TimerHeapIterator a, TimerHeapIterator b) { return a.index() == b.index(); }

   152 inline bool operator!=(TimerHeapIterator a, TimerHeapIterator b) { return a.index() != b.index(); }

   153 inline bool operator<(TimerHeapIterator a, TimerHeapIterator b) { return a.index() < b.index(); }

   154 

   155 inline TimerHeapIterator operator+(TimerHeapIterator a, int b) { return a.index() + b; }

   156 inline TimerHeapIterator operator+(int a, TimerHeapIterator b) { return a + b.index(); }

   157 

   158 inline TimerHeapIterator operator-(TimerHeapIterator a, int b) { return a.index() - b; }

   159 inline int operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.index() - b.index(); }

   160 

   161 // ----------------

   162 

   163 TimerBase::TimerBase()

   164     : m_nextFireTime(0)

   165     , m_repeatInterval(0)

   166     , m_heapIndex(-1)

   167 #ifndef NDEBUG

   168     , m_thread(currentThread())

   169 #endif

   170 {

   171 }

   172 

   173 TimerBase::~TimerBase()

   174 {

   175     stop();

   176     ASSERT(!inHeap());

   177 }

   178 

   179 void TimerBase::start(double nextFireInterval, double repeatInterval)

   180 {

   181     ASSERT(m_thread == currentThread());

   182 

   183     m_repeatInterval = repeatInterval;

   184     setNextFireTime(currentTime() + nextFireInterval);

   185 }

   186 

   187 void TimerBase::stop()

   188 {

   189     ASSERT(m_thread == currentThread());

   190 

   191     m_repeatInterval = 0;

   192     setNextFireTime(0);

   193 

   194     ASSERT(m_nextFireTime == 0);

   195     ASSERT(m_repeatInterval == 0);

   196     ASSERT(!inHeap());

   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().isEmpty());

   211     ASSERT(m_heapIndex >= 0);

   212     ASSERT(m_heapIndex < static_cast<int>(timerHeap().size()));

   213     ASSERT(timerHeap()[m_heapIndex] == this);

   214 }

   215 

   216 inline void TimerBase::checkConsistency() const

   217 {

   218     // Timers should be in the heap if and only if they have a non-zero next fire time.

   219     ASSERT(inHeap() == (m_nextFireTime != 0));

   220     if (inHeap())

   221         checkHeapIndex();

   222 }

   223 

   224 void TimerBase::heapDecreaseKey()

   225 {

   226     ASSERT(m_nextFireTime != 0);

   227     checkHeapIndex();

   228     push_heap(TimerHeapIterator(0), TimerHeapIterator(m_heapIndex + 1));

   229     checkHeapIndex();

   230 }

   231 

   232 inline void TimerBase::heapDelete()

   233 {

   234     ASSERT(m_nextFireTime == 0);

   235     heapPop();

   236     timerHeap().removeLast();

   237     m_heapIndex = -1;

   238 }

   239 

   240 void TimerBase::heapDeleteMin()

   241 {

   242     ASSERT(m_nextFireTime == 0);

   243     heapPopMin();

   244     timerHeap().removeLast();

   245     m_heapIndex = -1;

   246 }

   247 

   248 inline void TimerBase::heapIncreaseKey()

   249 {

   250     ASSERT(m_nextFireTime != 0);

   251     heapPop();

   252     heapDecreaseKey();

   253 }

   254 

   255 inline void TimerBase::heapInsert()

   256 {

   257     ASSERT(!inHeap());

   258     timerHeap().append(this);

   259     m_heapIndex = timerHeap().size() - 1;

   260     heapDecreaseKey();

   261 }

   262 

   263 inline void TimerBase::heapPop()

   264 {

   265     // Temporarily force this timer to have the minimum key so we can pop it.

   266     double fireTime = m_nextFireTime;

   267     m_nextFireTime = -numeric_limits<double>::infinity();

   268     heapDecreaseKey();

   269     heapPopMin();

   270     m_nextFireTime = fireTime;

   271 }

   272 

   273 void TimerBase::heapPopMin()

   274 {

   275     ASSERT(this == timerHeap().first());

   276     checkHeapIndex();

   277     pop_heap(TimerHeapIterator(0), TimerHeapIterator(timerHeap().size()));

   278     checkHeapIndex();

   279     ASSERT(this == timerHeap().last());

   280 }

   281 

   282 void TimerBase::setNextFireTime(double newTime)

   283 {

   284     ASSERT(m_thread == currentThread());

   285 

   286     // Keep heap valid while changing the next-fire time.

   287     double oldTime = m_nextFireTime;

   288     if (oldTime != newTime) {

   289         m_nextFireTime = newTime;

   290         static unsigned currentHeapInsertionOrder;

   291         m_heapInsertionOrder = currentHeapInsertionOrder++;

   292 

   293         bool wasFirstTimerInHeap = m_heapIndex == 0;

   294 

   295         if (oldTime == 0)

   296             heapInsert();

   297         else if (newTime == 0)

   298             heapDelete();

   299         else if (newTime < oldTime)

   300             heapDecreaseKey();

   301         else

   302             heapIncreaseKey();

   303 

   304         bool isFirstTimerInHeap = m_heapIndex == 0;

   305 

   306         if (wasFirstTimerInHeap || isFirstTimerInHeap)

   307             threadGlobalData().threadTimers().updateSharedTimer();

   308     }

   309 

   310     checkConsistency();

   311 }

   312 

   313 void TimerBase::fireTimersInNestedEventLoop()

   314 {

   315     // Redirect to ThreadTimers.

   316     threadGlobalData().threadTimers().fireTimersInNestedEventLoop();

   317 }

   318 

   319 } // namespace WebCore

   320