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 }