Changeset 92556 in webkit


Ignore:
Timestamp:
Aug 6, 2011 1:17:26 PM (13 years ago)
Author:
Darin Adler
Message:

Fix Timer heap implementation to work with more libraries (other versions of STL)
​https://bugs.webkit.org/show_bug.cgi?id=65782

Reviewed by Anders Carlsson.

No behavior change, so no tests needed. Existing tests pass.

  • platform/Timer.cpp: Added TimerHeapPointer and TimerHeapReference class

alongside the TimerHeapIterator class. Also added a swap function. Also
added a TimerHeapLessThanFunction class.
(WebCore::TimerBase::heapDecreaseKey): Pass pointers in to the TimerHeapIterator
since that's how the class works now. Pass a TimerHeapLessThanFunction object
instead of letting the library use the < operator directly.
(WebCore::TimerBase::heapPopMin): Ditto.

  • platform/Timer.h: Updated for above changes.
Location:
trunk/Source/WebCore
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r92555 r92556  
     12011-08-05  Darin Adler  <darin@apple.com>
     2
     3        Fix Timer heap implementation to work with more libraries (other versions of STL)
     4        https://bugs.webkit.org/show_bug.cgi?id=65782
     5
     6        Reviewed by Anders Carlsson.
     7
     8        No behavior change, so no tests needed. Existing tests pass.
     9
     10        * platform/Timer.cpp: Added TimerHeapPointer and TimerHeapReference class
     11        alongside the TimerHeapIterator class. Also added a swap function. Also
     12        added a TimerHeapLessThanFunction class.
     13        (WebCore::TimerBase::heapDecreaseKey): Pass pointers in to the TimerHeapIterator
     14        since that's how the class works now. Pass a TimerHeapLessThanFunction object
     15        instead of letting the library use the < operator directly.
     16        (WebCore::TimerBase::heapPopMin): Ditto.
     17
     18        * platform/Timer.h: Updated for above changes.
     19
    1202011-08-06  Aron Rosenberg  <arosenberg@logitech.com>
    221

  • trunk/Source/WebCore/platform/Timer.cpp

    r91206 r92556  
    4242namespace WebCore {
    4343
     44class TimerHeapReference;
     45
    4446// Timers are stored in a heap data structure, used to implement a priority queue.
    4547// This allows us to efficiently determine which timer needs to fire the soonest.
    … …  
    5456}
    5557
    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 {
     58// ----------------
     59
     60class TimerHeapPointer {
    6061public:
    61     explicit TimerHeapElement(int i)
    62         : m_index(i)
    63         , m_timer(timerHeap()[m_index])
    64     {
    65         checkConsistency();
     62    TimerHeapPointer(TimerBase** pointer) : m_pointer(pointer) { }
     63    TimerHeapReference operator*() const;
     64    TimerBase* operator->() const { return *m_pointer; }
     65private:
     66    TimerBase** m_pointer;
     67};
     68
     69class TimerHeapReference {
     70public:
     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);
     76private:
     77    TimerBase*& m_reference;
     78};
     79
     80inline TimerHeapReference TimerHeapPointer::operator*() const
     81{
     82    return *m_pointer;
     83}
     84
     85inline 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
     94inline TimerHeapReference& TimerHeapReference::operator=(TimerHeapReference b)
     95{
     96    TimerBase* timer = b;
     97    return *this = timer;
     98}
     99
     100inline 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.
     114class TimerHeapIterator : public iterator<random_access_iterator_tag, TimerBase*, ptrdiff_t, TimerHeapPointer, TimerHeapReference> {
     115public:
     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
     131private:
     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());
    66138    }
    67139
    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;
     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;
    84154};
    85155
    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)
     156inline bool operator==(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer == b.m_pointer; }
     157inline bool operator!=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer != b.m_pointer; }
     158inline bool operator<(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer < b.m_pointer; }
     159inline bool operator>(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer > b.m_pointer; }
     160inline bool operator<=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer <= b.m_pointer; }
     161inline bool operator>=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer >= b.m_pointer; }
     162
     163inline TimerHeapIterator operator+(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer + b); }
     164inline TimerHeapIterator operator+(size_t a, TimerHeapIterator b) { return TimerHeapIterator(a + b.m_pointer); }
     165
     166inline TimerHeapIterator operator-(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer - b); }
     167inline ptrdiff_t operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer - b.m_pointer; }
     168
     169// ----------------
     170
     171class TimerHeapLessThanFunction {
     172public:
     173    bool operator()(TimerBase*, TimerBase*) const;
     174};
     175
     176inline bool TimerHeapLessThanFunction::operator()(TimerBase* a, TimerBase* b) const
    104177{
    105178    // The comparisons below are "backwards" because the heap puts the largest
    106179    // 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;
     180    double aFireTime = a->m_nextFireTime;
     181    double bFireTime = b->m_nextFireTime;
    109182    if (bFireTime != aFireTime)
    110183        return bFireTime < aFireTime;
    … …  
    112185    // We need to look at the difference of the insertion orders instead of comparing the two
    113186    // 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(); }
     187    unsigned difference = a->m_heapInsertionOrder - b->m_heapInsertionOrder;
     188    return difference < numeric_limits<unsigned>::max() / 2;
     189}
    160190
    161191// ----------------
    … …  
    226256    ASSERT(m_nextFireTime != 0);
    227257    checkHeapIndex();
    228     push_heap(TimerHeapIterator(0), TimerHeapIterator(m_heapIndex + 1));
     258    TimerBase** heapData = timerHeap().data();
     259    push_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + m_heapIndex + 1), TimerHeapLessThanFunction());
    229260    checkHeapIndex();
    230261}
    … …  
    275306    ASSERT(this == timerHeap().first());
    276307    checkHeapIndex();
    277     pop_heap(TimerHeapIterator(0), TimerHeapIterator(timerHeap().size()));
     308    Vector<TimerBase*>& heap = timerHeap();
     309    TimerBase** heapData = heap.data();
     310    pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction());
    278311    checkHeapIndex();
    279312    ASSERT(this == timerHeap().last());

  • trunk/Source/WebCore/platform/Timer.h

    r78620 r92556  
    8585#endif
    8686
    87     friend class TimerHeapElement;
    8887    friend class ThreadTimers;
    89     friend bool operator<(const TimerHeapElement&, const TimerHeapElement&);
     88    friend class TimerHeapLessThanFunction;
     89    friend class TimerHeapReference;
    9090};
    9191
Note: See TracChangeset for help on using the changeset viewer.