WIP - not ready for review

Source/platform/TimerHeap.h

+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef TimerHeap_h
+#define TimerHeap_h
+
+#include "wtf/HashSet.h"
+#include "wtf/Noncopyable.h"
+#include "wtf/Threading.h"
+#include "wtf/Vector.h"
+
+namespace blink {
+
+class TimerBase;
+class TimerHeapEntry;
+
+// Gets notified by a TimerHeap when the item at the front of the
+// queue may have changed--either it's a different item, or the "next
+// fire time" of the item has changed.
+class TimerQueueObserver {
+    WTF_MAKE_NONCOPYABLE(TimerQueueObserver);
+
+public:
+    TimerQueueObserver();
+    virtual ~TimerQueueObserver();
+
+    virtual void nextFiringTimerChanged() = 0;
+};
+
+// FIXME: That this is a heap is an implementation detail; rename it
+// to TimerQueue or TimerPriorityQueue or NextFiringTimerQueue or
+// something like that.
+
+// Timers are stored in a min-heap, keyed by firing time. There's one
+// heap per-thread; the timers in each heap are serviced by one
+// platform timer (the "real" timer) whose schedule is set by the
+// timer that's at the the top of the heap (ie the timer that should
+// fire next).
+class TimerHeap {
+    WTF_MAKE_NONCOPYABLE(TimerHeap);
+
+public:
+    // Gets the thread-static TimerHeap for the current thread.
+    static TimerHeap& get();
+
+    // Creates a TimerHeap that will notify the observer when the head
+    // of the queue changes. The observer must live as long as the
+    // queue is being modified.
+    TimerHeap(TimerQueueObserver*);
+    virtual ~TimerHeap();
+
+    // Does a consistency check of the entire TimerHeap structure.
+    void check() const;
+
+    // Used by TimerThread
+    bool isEmpty() const;
+    TimerBase* first() const;
+
+    // Used by TimerHeapEntry
+    void didChangeValue(TimerBase&, double oldValue);
+
+private:
+    friend class TimerHeapIterator;
+    friend class TimerHeapReference;
+
+    // Performs a consistency check of a specific entry.
+    void check(const TimerHeapEntry&) const;
+
+    // Checks whether an entry is in the heap, if so, that the heap
+    // property holds around the entry.
+    bool hasValidHeapPosition(const TimerHeapEntry&) const;
+    bool parentHeapPropertyHolds(const TimerHeapEntry&) const;
+    bool childHeapPropertyHolds(const TimerHeapEntry&, size_t childIndex) const;
+
+    // Percolates a timer that is in the heap whose key got smaller up
+    // in the heap, if necessary. Used by didChangeValue.
+    void didDecreaseKey(TimerBase*);
+
+    // Like didDecreaseKey, but pushes a timer in the heap whose key
+    // got larger deeper into the heap, if necessary.
+    void didIncreaseKey(TimerBase*);
+
+    void insert(TimerBase*);
+    void remove(TimerBase*);
+    void pop(TimerBase*);
+
+    TimerQueueObserver* m_observer;
+    ThreadIdentifier m_thread;
+    Vector<TimerBase*> m_heap;
+    HashSet<TimerBase*> m_entries;
+    size_t m_currentHeapInsertionOrder;
+};
+
+} // namespace blink
+
+#endif // TimerHeap_h