Add a priority queue class, which is a wrapper around std::priority_queue

and provides fairly efficient removal of arbitrary elements. Switch
ScheduleDAGRRList from std::set to this new priority queue.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52582 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 77 insertions, 0 deletions

diff --git a/include/llvm/ADT/PriorityQueue.h b/include/llvm/ADT/PriorityQueue.h
new file mode 100644
index 0000000000..1cff0f2a0c
--- /dev/null
+++ b/include/llvm/ADT/PriorityQueue.h
@@ -0,0 +1,77 @@
+//===- llvm/ADT/PriorityQueue.h - Priority queues ---------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the PriorityQueue class.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_PRIORITY_QUEUE_H
+#define LLVM_ADT_PRIORITY_QUEUE_H
+
+#include <queue>
+
+namespace llvm {
+
+/// PriorityQueue - This class behaves like std::priority_queue and
+/// provides a few additional convenience functions.
+/// 
+template<class T,
+         class Sequence = std::vector<T>,
+         class Compare = std::less<typename Sequence::value_type> >
+class PriorityQueue : public std::priority_queue<T, Sequence, Compare> {
+public:
+  explicit PriorityQueue(const Compare &compare = Compare(),
+                         const Sequence &sequence = Sequence())
+    : std::priority_queue<T, Sequence, Compare>(compare, sequence)
+  {}
+
+  template<class Iterator>
+  PriorityQueue(Iterator begin, Iterator end,
+                const Compare &compare = Compare(),
+                const Sequence &sequence = Sequence())
+    : std::priority_queue<T, Sequence, Compare>(begin, end, compare, sequence)
+  {}
+
+  /// erase_one - Erase one element from the queue, regardless of its
+  /// position. This operation performs a linear search to find an element
+  /// equal to t, but then uses all logarithmic-time algorithms to do
+  /// the erase operation.
+  ///
+  void erase_one(const T &t) {
+    // Linear-search to find the element.
+    typename Sequence::size_type i =
+      std::find(this->c.begin(), this->c.end(), t) - this->c.begin();
+
+    // Logarithmic-time heap bubble-up.
+    while (i != 0) {
+      typename Sequence::size_type parent = (i - 1) / 2;
+      std::swap(this->c[i], this->c[parent]);
+      i = parent;
+    }
+
+    // The element we want to remove is now at the root, so we can use
+    // priority_queue's plain pop to remove it.
+    this->pop();
+  }
+
+  /// reheapify - If an element in the queue has changed in a way that
+  /// affects its standing in the comparison function, the queue's
+  /// internal state becomes invalid. Calling reheapify() resets the
+  /// queue's state, making it valid again. This operation has time
+  /// complexity proportional to the number of elements in the queue,
+  /// so don't plan to use it a lot.
+  ///
+  void reheapify() {
+    std::make_heap(this->c.begin(), this->c.end(), this->comp);
+  }
+};
+
+} // End llvm namespace
+
+#endif