LLVM  14.0.0git
PriorityQueue.h
Go to the documentation of this file.
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  {}
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
i
i
Definition: README.txt:29
llvm::PriorityQueue::clear
void clear()
clear - Erase all elements from the queue.
Definition: PriorityQueue.h:75
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::objcarc::Sequence
Sequence
Definition: PtrState.h:41
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::PriorityQueue::reheapify
void reheapify()
reheapify - If an element in the queue has changed in a way that affects its standing in the comparis...
Definition: PriorityQueue.h:69
t
bitcast float %x to i32 %s=and i32 %t, 2147483647 %d=bitcast i32 %s to float ret float %d } declare float @fabsf(float %n) define float @bar(float %x) nounwind { %d=call float @fabsf(float %x) ret float %d } This IR(from PR6194):target datalayout="e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" target triple="x86_64-apple-darwin10.0.0" %0=type { double, double } %struct.float3=type { float, float, float } define void @test(%0, %struct.float3 *nocapture %res) nounwind noinline ssp { entry:%tmp18=extractvalue %0 %0, 0 t
Definition: README-SSE.txt:788
c
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int int c
Definition: README.txt:418
llvm::PriorityQueue
PriorityQueue - This class behaves like std::priority_queue and provides a few additional convenience...
Definition: PriorityQueue.h:27
llvm::PriorityQueue::PriorityQueue
PriorityQueue(Iterator begin, Iterator end, const Compare &compare=Compare(), const Sequence &sequence=Sequence())
Definition: PriorityQueue.h:35
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1567
llvm::ScaledNumbers::compare
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
Definition: ScaledNumber.h:251
llvm::PriorityQueue::PriorityQueue
PriorityQueue(const Compare &compare=Compare(), const Sequence &sequence=Sequence())
Definition: PriorityQueue.h:29
Compare
QP Compare Ordered outs ins xscmpudp No builtin are required Or llvm fcmp order unorder compare DP QP Compare builtin are required DP Compare
Definition: README_P9.txt:309
llvm::PriorityQueue::erase_one
void erase_one(const T &t)
erase_one - Erase one element from the queue, regardless of its position.
Definition: PriorityQueue.h:46
this
Analysis the ScalarEvolution expression for r is this
Definition: README.txt:8
std
Definition: BitVector.h:838