/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/ADT/PriorityQueue.h
Line | Count | Source |
1 | | //===- llvm/ADT/PriorityQueue.h - Priority queues ---------------*- C++ -*-===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | // This file defines the PriorityQueue class. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #ifndef LLVM_ADT_PRIORITYQUEUE_H |
15 | | #define LLVM_ADT_PRIORITYQUEUE_H |
16 | | |
17 | | #include <algorithm> |
18 | | #include <queue> |
19 | | |
20 | | namespace llvm { |
21 | | |
22 | | /// PriorityQueue - This class behaves like std::priority_queue and |
23 | | /// provides a few additional convenience functions. |
24 | | /// |
25 | | template<class T, |
26 | | class Sequence = std::vector<T>, |
27 | | class Compare = std::less<typename Sequence::value_type> > |
28 | | class PriorityQueue : public std::priority_queue<T, Sequence, Compare> { |
29 | | public: |
30 | | explicit PriorityQueue(const Compare &compare = Compare(), |
31 | | const Sequence &sequence = Sequence()) |
32 | | : std::priority_queue<T, Sequence, Compare>(compare, sequence) |
33 | 9.79k | {} MachinePipeliner.cpp:llvm::PriorityQueue<llvm::MachineInstr*, std::__1::vector<llvm::MachineInstr*, std::__1::allocator<llvm::MachineInstr*> >, (anonymous namespace)::FuncUnitSorter>::PriorityQueue((anonymous namespace)::FuncUnitSorter const&, std::__1::vector<llvm::MachineInstr*, std::__1::allocator<llvm::MachineInstr*> > const&) Line | Count | Source | 33 | 113 | {} |
llvm::PriorityQueue<clang::CFGBlock const*, llvm::SmallVector<clang::CFGBlock const*, 20u>, clang::PostOrderCFGView::BlockOrderCompare>::PriorityQueue(clang::PostOrderCFGView::BlockOrderCompare const&, llvm::SmallVector<clang::CFGBlock const*, 20u> const&) Line | Count | Source | 33 | 9.68k | {} |
|
34 | | |
35 | | template<class Iterator> |
36 | | PriorityQueue(Iterator begin, Iterator end, |
37 | | const Compare &compare = Compare(), |
38 | | const Sequence &sequence = Sequence()) |
39 | | : std::priority_queue<T, Sequence, Compare>(begin, end, compare, sequence) |
40 | | {} |
41 | | |
42 | | /// erase_one - Erase one element from the queue, regardless of its |
43 | | /// position. This operation performs a linear search to find an element |
44 | | /// equal to t, but then uses all logarithmic-time algorithms to do |
45 | | /// the erase operation. |
46 | | /// |
47 | | void erase_one(const T &t) { |
48 | | // Linear-search to find the element. |
49 | | typename Sequence::size_type i = find(this->c, t) - this->c.begin(); |
50 | | |
51 | | // Logarithmic-time heap bubble-up. |
52 | | while (i != 0) { |
53 | | typename Sequence::size_type parent = (i - 1) / 2; |
54 | | this->c[i] = this->c[parent]; |
55 | | i = parent; |
56 | | } |
57 | | |
58 | | // The element we want to remove is now at the root, so we can use |
59 | | // priority_queue's plain pop to remove it. |
60 | | this->pop(); |
61 | | } |
62 | | |
63 | | /// reheapify - If an element in the queue has changed in a way that |
64 | | /// affects its standing in the comparison function, the queue's |
65 | | /// internal state becomes invalid. Calling reheapify() resets the |
66 | | /// queue's state, making it valid again. This operation has time |
67 | | /// complexity proportional to the number of elements in the queue, |
68 | | /// so don't plan to use it a lot. |
69 | | /// |
70 | | void reheapify() { |
71 | | std::make_heap(this->c.begin(), this->c.end(), this->comp); |
72 | | } |
73 | | |
74 | | /// clear - Erase all elements from the queue. |
75 | | /// |
76 | | void clear() { |
77 | | this->c.clear(); |
78 | | } |
79 | | }; |
80 | | |
81 | | } // End llvm namespace |
82 | | |
83 | | #endif |