Line data Source code
1 : /*
2 : *
3 : * Copyright 2015, Google Inc.
4 : * All rights reserved.
5 : *
6 : * Redistribution and use in source and binary forms, with or without
7 : * modification, are permitted provided that the following conditions are
8 : * met:
9 : *
10 : * * Redistributions of source code must retain the above copyright
11 : * notice, this list of conditions and the following disclaimer.
12 : * * Redistributions in binary form must reproduce the above
13 : * copyright notice, this list of conditions and the following disclaimer
14 : * in the documentation and/or other materials provided with the
15 : * distribution.
16 : * * Neither the name of Google Inc. nor the names of its
17 : * contributors may be used to endorse or promote products derived from
18 : * this software without specific prior written permission.
19 : *
20 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 : * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 : * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 : * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 : * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 : * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 : * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 : *
32 : */
33 :
34 : #include "src/core/iomgr/timer_heap.h"
35 :
36 : #include <string.h>
37 :
38 : #include <grpc/support/alloc.h>
39 : #include <grpc/support/useful.h>
40 :
41 : /* Adjusts a heap so as to move a hole at position i closer to the root,
42 : until a suitable position is found for element t. Then, copies t into that
43 : position. This functor is called each time immediately after modifying a
44 : value in the underlying container, with the offset of the modified element as
45 : its argument. */
46 39663 : static void adjust_upwards(grpc_timer **first, gpr_uint32 i, grpc_timer *t) {
47 112093 : while (i > 0) {
48 70440 : gpr_uint32 parent = (gpr_uint32)(((int)i - 1) / 2);
49 70440 : if (gpr_time_cmp(first[parent]->deadline, t->deadline) >= 0) break;
50 32767 : first[i] = first[parent];
51 32767 : first[i]->heap_index = i;
52 32765 : i = parent;
53 : }
54 39663 : first[i] = t;
55 39663 : t->heap_index = i;
56 39663 : }
57 :
58 : /* Adjusts a heap so as to move a hole at position i farther away from the root,
59 : until a suitable position is found for element t. Then, copies t into that
60 : position. */
61 39356 : static void adjust_downwards(grpc_timer **first, gpr_uint32 i,
62 : gpr_uint32 length, grpc_timer *t) {
63 : for (;;) {
64 39356 : gpr_uint32 left_child = 1u + 2u * i;
65 : gpr_uint32 right_child;
66 : gpr_uint32 next_i;
67 39356 : if (left_child >= length) break;
68 22665 : right_child = left_child + 1;
69 44950 : next_i = right_child < length &&
70 22285 : gpr_time_cmp(first[left_child]->deadline,
71 22285 : first[right_child]->deadline) < 0
72 : ? right_child
73 34002 : : left_child;
74 22665 : if (gpr_time_cmp(t->deadline, first[next_i]->deadline) >= 0) break;
75 17746 : first[i] = first[next_i];
76 17746 : first[i]->heap_index = i;
77 17746 : i = next_i;
78 17746 : }
79 21610 : first[i] = t;
80 21610 : t->heap_index = i;
81 21610 : }
82 :
83 : #define SHRINK_MIN_ELEMS 8
84 : #define SHRINK_FULLNESS_FACTOR 2
85 :
86 33976 : static void maybe_shrink(grpc_timer_heap *heap) {
87 66245 : if (heap->timer_count >= 8 &&
88 32269 : heap->timer_count <= heap->timer_capacity / SHRINK_FULLNESS_FACTOR / 2) {
89 32 : heap->timer_capacity = heap->timer_count * SHRINK_FULLNESS_FACTOR;
90 32 : heap->timers =
91 32 : gpr_realloc(heap->timers, heap->timer_capacity * sizeof(grpc_timer *));
92 : }
93 33976 : }
94 :
95 26791 : static void note_changed_priority(grpc_timer_heap *heap, grpc_timer *timer) {
96 26791 : gpr_uint32 i = timer->heap_index;
97 26791 : gpr_uint32 parent = (gpr_uint32)(((int)i - 1) / 2);
98 26791 : if (gpr_time_cmp(heap->timers[parent]->deadline, timer->deadline) < 0) {
99 5181 : adjust_upwards(heap->timers, i, timer);
100 : } else {
101 21610 : adjust_downwards(heap->timers, i, heap->timer_count, timer);
102 : }
103 26791 : }
104 :
105 110698 : void grpc_timer_heap_init(grpc_timer_heap *heap) {
106 110698 : memset(heap, 0, sizeof(*heap));
107 110698 : }
108 :
109 110634 : void grpc_timer_heap_destroy(grpc_timer_heap *heap) { gpr_free(heap->timers); }
110 :
111 34482 : int grpc_timer_heap_add(grpc_timer_heap *heap, grpc_timer *timer) {
112 34482 : if (heap->timer_count == heap->timer_capacity) {
113 1398 : heap->timer_capacity =
114 1398 : GPR_MAX(heap->timer_capacity + 1, heap->timer_capacity * 3 / 2);
115 1398 : heap->timers =
116 1398 : gpr_realloc(heap->timers, heap->timer_capacity * sizeof(grpc_timer *));
117 : }
118 34482 : timer->heap_index = heap->timer_count;
119 34482 : adjust_upwards(heap->timers, heap->timer_count, timer);
120 34482 : heap->timer_count++;
121 34482 : return timer->heap_index == 0;
122 : }
123 :
124 33976 : void grpc_timer_heap_remove(grpc_timer_heap *heap, grpc_timer *timer) {
125 33976 : gpr_uint32 i = timer->heap_index;
126 33976 : if (i == heap->timer_count - 1) {
127 7185 : heap->timer_count--;
128 7185 : maybe_shrink(heap);
129 41161 : return;
130 : }
131 26791 : heap->timers[i] = heap->timers[heap->timer_count - 1];
132 26791 : heap->timers[i]->heap_index = i;
133 26791 : heap->timer_count--;
134 26791 : maybe_shrink(heap);
135 26791 : note_changed_priority(heap, heap->timers[i]);
136 : }
137 :
138 905750 : int grpc_timer_heap_is_empty(grpc_timer_heap *heap) {
139 905750 : return heap->timer_count == 0;
140 : }
141 :
142 4304 : grpc_timer *grpc_timer_heap_top(grpc_timer_heap *heap) {
143 4304 : return heap->timers[0];
144 : }
145 :
146 1515 : void grpc_timer_heap_pop(grpc_timer_heap *heap) {
147 1515 : grpc_timer_heap_remove(heap, grpc_timer_heap_top(heap));
148 1515 : }
|
