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