#include "config.h"
#include "Timer.h"
#include "SharedTimer.h"
#include <limits.h>
#include <limits>
#include <math.h>
#include <wtf/CurrentTime.h>
#include <wtf/HashSet.h>
#include <wtf/Vector.h>
#import "WebCoreThread.h"
using namespace std;
namespace WebCore {
static Vector<TimerBase*>* timerHeap;
static HashSet<const TimerBase*>* timersReadyToFire;
class TimerHeapElement {
public:
explicit TimerHeapElement(int i) : m_index(i), m_timer((*timerHeap)[m_index]) { checkConsistency(); }
TimerHeapElement(const TimerHeapElement&);
TimerHeapElement& operator=(const TimerHeapElement&);
TimerBase* timer() const { return m_timer; }
void checkConsistency() const
{
ASSERT(m_index >= 0);
ASSERT(m_index < (timerHeap ? static_cast<int>(timerHeap->size()) : 0));
}
private:
TimerHeapElement();
int m_index;
TimerBase* m_timer;
};
inline TimerHeapElement::TimerHeapElement(const TimerHeapElement& o)
: m_index(-1), m_timer(o.timer())
{
}
inline TimerHeapElement& TimerHeapElement::operator=(const TimerHeapElement& o)
{
TimerBase* t = o.timer();
m_timer = t;
if (m_index != -1) {
checkConsistency();
(*timerHeap)[m_index] = t;
t->m_heapIndex = m_index;
}
return *this;
}
inline bool operator<(const TimerHeapElement& a, const TimerHeapElement& b)
{
double aFireTime = a.timer()->m_nextFireTime;
double bFireTime = b.timer()->m_nextFireTime;
if (bFireTime != aFireTime)
return bFireTime < aFireTime;
unsigned difference = a.timer()->m_heapInsertionOrder - b.timer()->m_heapInsertionOrder;
return difference < UINT_MAX / 2;
}
class TimerHeapIterator : public iterator<random_access_iterator_tag, TimerHeapElement, int> {
public:
TimerHeapIterator() : m_index(-1) { }
TimerHeapIterator(int i) : m_index(i) { checkConsistency(); }
TimerHeapIterator& operator++() { checkConsistency(); ++m_index; checkConsistency(); return *this; }
TimerHeapIterator operator++(int) { checkConsistency(); checkConsistency(1); return m_index++; }
TimerHeapIterator& operator--() { checkConsistency(); --m_index; checkConsistency(); return *this; }
TimerHeapIterator operator--(int) { checkConsistency(); checkConsistency(-1); return m_index--; }
TimerHeapIterator& operator+=(int i) { checkConsistency(); m_index += i; checkConsistency(); return *this; }
TimerHeapIterator& operator-=(int i) { checkConsistency(); m_index -= i; checkConsistency(); return *this; }
TimerHeapElement operator*() const { return TimerHeapElement(m_index); }
TimerHeapElement operator[](int i) const { return TimerHeapElement(m_index + i); }
int index() const { return m_index; }
void checkConsistency(int offset = 0) const
{
ASSERT_UNUSED(offset, m_index + offset >= 0);
ASSERT_UNUSED(offset, m_index + offset <= (timerHeap ? static_cast<int>(timerHeap->size()) : 0));
}
private:
int m_index;
};
inline bool operator==(TimerHeapIterator a, TimerHeapIterator b) { return a.index() == b.index(); }
inline bool operator!=(TimerHeapIterator a, TimerHeapIterator b) { return a.index() != b.index(); }
inline bool operator<(TimerHeapIterator a, TimerHeapIterator b) { return a.index() < b.index(); }
inline TimerHeapIterator operator+(TimerHeapIterator a, int b) { return a.index() + b; }
inline TimerHeapIterator operator+(int a, TimerHeapIterator b) { return a + b.index(); }
inline TimerHeapIterator operator-(TimerHeapIterator a, int b) { return a.index() - b; }
inline int operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.index() - b.index(); }
void updateSharedTimer()
{
if (timersReadyToFire || !timerHeap || timerHeap->isEmpty())
stopSharedTimer();
else
setSharedTimerFireTime(timerHeap->first()->m_nextFireTime);
}
TimerBase::TimerBase()
: m_nextFireTime(0), m_repeatInterval(0), m_heapIndex(-1)
{
setSharedTimerFiredFunction(sharedTimerFired);
}
TimerBase::~TimerBase()
{
stop();
ASSERT(!inHeap());
}
void TimerBase::start(double nextFireInterval, double repeatInterval)
{
m_repeatInterval = repeatInterval;
setNextFireTime(currentTime() + nextFireInterval);
}
void TimerBase::stop()
{
m_repeatInterval = 0;
setNextFireTime(0);
ASSERT(m_nextFireTime == 0);
ASSERT(m_repeatInterval == 0);
ASSERT(!inHeap());
}
bool TimerBase::isActive() const
{
return m_nextFireTime || (timersReadyToFire && timersReadyToFire->contains(this));
}
double TimerBase::nextFireInterval() const
{
ASSERT(isActive());
double current = currentTime();
if (m_nextFireTime < current)
return 0;
return m_nextFireTime - current;
}
inline void TimerBase::checkHeapIndex() const
{
ASSERT(timerHeap);
ASSERT(!timerHeap->isEmpty());
ASSERT(m_heapIndex >= 0);
ASSERT(m_heapIndex < static_cast<int>(timerHeap->size()));
ASSERT((*timerHeap)[m_heapIndex] == this);
}
inline void TimerBase::checkConsistency() const
{
ASSERT(inHeap() == (m_nextFireTime != 0));
if (inHeap())
checkHeapIndex();
}
void TimerBase::heapDecreaseKey()
{
ASSERT(m_nextFireTime != 0);
checkHeapIndex();
push_heap(TimerHeapIterator(0), TimerHeapIterator(m_heapIndex + 1));
checkHeapIndex();
}
inline void TimerBase::heapDelete()
{
ASSERT(m_nextFireTime == 0);
heapPop();
timerHeap->removeLast();
m_heapIndex = -1;
}
inline void TimerBase::heapDeleteMin()
{
ASSERT(m_nextFireTime == 0);
heapPopMin();
timerHeap->removeLast();
m_heapIndex = -1;
}
inline void TimerBase::heapIncreaseKey()
{
ASSERT(m_nextFireTime != 0);
heapPop();
heapDecreaseKey();
}
inline void TimerBase::heapInsert()
{
ASSERT(!inHeap());
if (!timerHeap)
timerHeap = new Vector<TimerBase*>;
timerHeap->append(this);
m_heapIndex = timerHeap->size() - 1;
heapDecreaseKey();
}
inline void TimerBase::heapPop()
{
double fireTime = m_nextFireTime;
m_nextFireTime = -numeric_limits<double>::infinity();
heapDecreaseKey();
heapPopMin();
m_nextFireTime = fireTime;
}
void TimerBase::heapPopMin()
{
ASSERT(this == timerHeap->first());
checkHeapIndex();
pop_heap(TimerHeapIterator(0), TimerHeapIterator(timerHeap->size()));
checkHeapIndex();
ASSERT(this == timerHeap->last());
}
void TimerBase::setNextFireTime(double newTime)
{
if (timersReadyToFire)
timersReadyToFire->remove(this);
double oldTime = m_nextFireTime;
if (oldTime != newTime) {
m_nextFireTime = newTime;
static unsigned currentHeapInsertionOrder;
m_heapInsertionOrder = currentHeapInsertionOrder++;
bool wasFirstTimerInHeap = m_heapIndex == 0;
if (oldTime == 0)
heapInsert();
else if (newTime == 0)
heapDelete();
else if (newTime < oldTime)
heapDecreaseKey();
else
heapIncreaseKey();
bool isFirstTimerInHeap = m_heapIndex == 0;
if (wasFirstTimerInHeap || isFirstTimerInHeap)
updateSharedTimer();
}
checkConsistency();
}
void TimerBase::collectFiringTimers(double fireTime, Vector<TimerBase*>& firingTimers)
{
while (!timerHeap->isEmpty() && timerHeap->first()->m_nextFireTime <= fireTime) {
TimerBase* timer = timerHeap->first();
firingTimers.append(timer);
timersReadyToFire->add(timer);
timer->m_nextFireTime = 0;
timer->heapDeleteMin();
}
}
void TimerBase::fireTimers(double fireTime, const Vector<TimerBase*>& firingTimers)
{
ASSERT(WebThreadIsLocked() || !WebThreadIsEnabled());
int size = firingTimers.size();
for (int i = 0; i != size; ++i) {
TimerBase* timer = firingTimers[i];
if (!timersReadyToFire->contains(timer))
continue;
double interval = timer->repeatInterval();
timer->setNextFireTime(interval ? fireTime + interval : 0);
timer->fired();
if (!timersReadyToFire)
break;
}
}
void TimerBase::sharedTimerFired()
{
if (timersReadyToFire)
return;
double fireTime = currentTime();
Vector<TimerBase*> firingTimers;
HashSet<const TimerBase*> firingTimersSet;
timersReadyToFire = &firingTimersSet;
collectFiringTimers(fireTime, firingTimers);
fireTimers(fireTime, firingTimers);
timersReadyToFire = 0;
updateSharedTimer();
}
void TimerBase::fireTimersInNestedEventLoop()
{
timersReadyToFire = 0;
updateSharedTimer();
}
}