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