1 //
2 //
3 // Copyright 2015 gRPC authors.
4 //
5 // Licensed under the Apache License, Version 2.0 (the "License");
6 // you may not use this file except in compliance with the License.
7 // You may obtain a copy of the License at
8 //
9 // http://www.apache.org/licenses/LICENSE-2.0
10 //
11 // Unless required by applicable law or agreed to in writing, software
12 // distributed under the License is distributed on an "AS IS" BASIS,
13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 // See the License for the specific language governing permissions and
15 // limitations under the License.
16 //
17 //
18
19 #include "src/core/lib/event_engine/posix_engine/timer_heap.h"
20
21 #include <grpc/support/port_platform.h>
22 #include <stdint.h>
23
24 #include <algorithm>
25
26 #include "src/core/lib/event_engine/posix_engine/timer.h"
27
28 namespace grpc_event_engine {
29 namespace experimental {
30
31 // Adjusts a heap so as to move a hole at position i closer to the root,
32 // until a suitable position is found for element t. Then, copies t into that
33 // position. This functor is called each time immediately after modifying a
34 // value in the underlying container, with the offset of the modified element as
35 // its argument.
AdjustUpwards(size_t i,Timer * t)36 void TimerHeap::AdjustUpwards(size_t i, Timer* t) {
37 while (i > 0) {
38 size_t parent = (i - 1) / 2;
39 if (timers_[parent]->deadline <= t->deadline) break;
40 timers_[i] = timers_[parent];
41 timers_[i]->heap_index = i;
42 i = parent;
43 }
44 timers_[i] = t;
45 t->heap_index = i;
46 }
47
48 // Adjusts a heap so as to move a hole at position i farther away from the root,
49 // until a suitable position is found for element t. Then, copies t into that
50 // position.
AdjustDownwards(size_t i,Timer * t)51 void TimerHeap::AdjustDownwards(size_t i, Timer* t) {
52 for (;;) {
53 size_t left_child = 1 + (2 * i);
54 if (left_child >= timers_.size()) break;
55 size_t right_child = left_child + 1;
56 size_t next_i =
57 right_child < timers_.size() &&
58 timers_[left_child]->deadline > timers_[right_child]->deadline
59 ? right_child
60 : left_child;
61 if (t->deadline <= timers_[next_i]->deadline) break;
62 timers_[i] = timers_[next_i];
63 timers_[i]->heap_index = i;
64 i = next_i;
65 }
66 timers_[i] = t;
67 t->heap_index = i;
68 }
69
NoteChangedPriority(Timer * timer)70 void TimerHeap::NoteChangedPriority(Timer* timer) {
71 uint32_t i = timer->heap_index;
72 uint32_t parent = static_cast<uint32_t>((static_cast<int>(i) - 1) / 2);
73 if (timers_[parent]->deadline > timer->deadline) {
74 AdjustUpwards(i, timer);
75 } else {
76 AdjustDownwards(i, timer);
77 }
78 }
79
Add(Timer * timer)80 bool TimerHeap::Add(Timer* timer) {
81 timer->heap_index = timers_.size();
82 timers_.push_back(timer);
83 AdjustUpwards(timer->heap_index, timer);
84 return timer->heap_index == 0;
85 }
86
Remove(Timer * timer)87 void TimerHeap::Remove(Timer* timer) {
88 uint32_t i = timer->heap_index;
89 if (i == timers_.size() - 1) {
90 timers_.pop_back();
91 return;
92 }
93 timers_[i] = timers_[timers_.size() - 1];
94 timers_[i]->heap_index = i;
95 timers_.pop_back();
96 NoteChangedPriority(timers_[i]);
97 }
98
is_empty()99 bool TimerHeap::is_empty() { return timers_.empty(); }
100
Top()101 Timer* TimerHeap::Top() { return timers_[0]; }
102
Pop()103 void TimerHeap::Pop() { Remove(Top()); }
104
105 } // namespace experimental
106 } // namespace grpc_event_engine
107