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 <grpc/support/port_platform.h>
20
21 #include "src/core/lib/iomgr/timer_heap.h"
22
23 #include <string.h>
24
25 #include <grpc/support/alloc.h>
26
27 #include "src/core/lib/gpr/useful.h"
28 #include "src/core/lib/iomgr/port.h"
29
30 // Adjusts a heap so as to move a hole at position i closer to the root,
31 // until a suitable position is found for element t. Then, copies t into that
32 // position. This functor is called each time immediately after modifying a
33 // value in the underlying container, with the offset of the modified element as
34 // its argument.
adjust_upwards(grpc_timer ** first,uint32_t i,grpc_timer * t)35 static void adjust_upwards(grpc_timer** first, uint32_t i, grpc_timer* t) {
36 while (i > 0) {
37 uint32_t parent = static_cast<uint32_t>((static_cast<int>(i) - 1) / 2);
38 if (first[parent]->deadline <= t->deadline) break;
39 first[i] = first[parent];
40 first[i]->heap_index = i;
41 i = parent;
42 }
43 first[i] = t;
44 t->heap_index = i;
45 }
46
47 // Adjusts a heap so as to move a hole at position i farther away from the root,
48 // until a suitable position is found for element t. Then, copies t into that
49 // position.
adjust_downwards(grpc_timer ** first,uint32_t i,uint32_t length,grpc_timer * t)50 static void adjust_downwards(grpc_timer** first, uint32_t i, uint32_t length,
51 grpc_timer* t) {
52 for (;;) {
53 uint32_t left_child = 1u + 2u * i;
54 if (left_child >= length) break;
55 uint32_t right_child = left_child + 1;
56 uint32_t next_i = right_child < length && first[left_child]->deadline >
57 first[right_child]->deadline
58 ? right_child
59 : left_child;
60 if (t->deadline <= first[next_i]->deadline) break;
61 first[i] = first[next_i];
62 first[i]->heap_index = i;
63 i = next_i;
64 }
65 first[i] = t;
66 t->heap_index = i;
67 }
68
69 #define SHRINK_MIN_ELEMS 8
70 #define SHRINK_FULLNESS_FACTOR 2
71
maybe_shrink(grpc_timer_heap * heap)72 static void maybe_shrink(grpc_timer_heap* heap) {
73 if (heap->timer_count >= 8 &&
74 heap->timer_count <= heap->timer_capacity / SHRINK_FULLNESS_FACTOR / 2) {
75 heap->timer_capacity = heap->timer_count * SHRINK_FULLNESS_FACTOR;
76 heap->timers = static_cast<grpc_timer**>(
77 gpr_realloc(heap->timers, heap->timer_capacity * sizeof(grpc_timer*)));
78 }
79 }
80
note_changed_priority(grpc_timer_heap * heap,grpc_timer * timer)81 static void note_changed_priority(grpc_timer_heap* heap, grpc_timer* timer) {
82 uint32_t i = timer->heap_index;
83 uint32_t parent = static_cast<uint32_t>((static_cast<int>(i) - 1) / 2);
84 if (heap->timers[parent]->deadline > timer->deadline) {
85 adjust_upwards(heap->timers, i, timer);
86 } else {
87 adjust_downwards(heap->timers, i, heap->timer_count, timer);
88 }
89 }
90
grpc_timer_heap_init(grpc_timer_heap * heap)91 void grpc_timer_heap_init(grpc_timer_heap* heap) {
92 memset(heap, 0, sizeof(*heap));
93 }
94
grpc_timer_heap_destroy(grpc_timer_heap * heap)95 void grpc_timer_heap_destroy(grpc_timer_heap* heap) { gpr_free(heap->timers); }
96
grpc_timer_heap_add(grpc_timer_heap * heap,grpc_timer * timer)97 bool grpc_timer_heap_add(grpc_timer_heap* heap, grpc_timer* timer) {
98 if (heap->timer_count == heap->timer_capacity) {
99 heap->timer_capacity =
100 std::max(heap->timer_capacity + 1, heap->timer_capacity * 3 / 2);
101 heap->timers = static_cast<grpc_timer**>(
102 gpr_realloc(heap->timers, heap->timer_capacity * sizeof(grpc_timer*)));
103 }
104 timer->heap_index = heap->timer_count;
105 adjust_upwards(heap->timers, heap->timer_count, timer);
106 heap->timer_count++;
107 return timer->heap_index == 0;
108 }
109
grpc_timer_heap_remove(grpc_timer_heap * heap,grpc_timer * timer)110 void grpc_timer_heap_remove(grpc_timer_heap* heap, grpc_timer* timer) {
111 uint32_t i = timer->heap_index;
112 if (i == heap->timer_count - 1) {
113 heap->timer_count--;
114 maybe_shrink(heap);
115 return;
116 }
117 heap->timers[i] = heap->timers[heap->timer_count - 1];
118 heap->timers[i]->heap_index = i;
119 heap->timer_count--;
120 maybe_shrink(heap);
121 note_changed_priority(heap, heap->timers[i]);
122 }
123
grpc_timer_heap_is_empty(grpc_timer_heap * heap)124 bool grpc_timer_heap_is_empty(grpc_timer_heap* heap) {
125 return heap->timer_count == 0;
126 }
127
grpc_timer_heap_top(grpc_timer_heap * heap)128 grpc_timer* grpc_timer_heap_top(grpc_timer_heap* heap) {
129 return heap->timers[0];
130 }
131
grpc_timer_heap_pop(grpc_timer_heap * heap)132 void grpc_timer_heap_pop(grpc_timer_heap* heap) {
133 grpc_timer_heap_remove(heap, grpc_timer_heap_top(heap));
134 }
135