Coverage Report

Created: 2019-04-21 11:35

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