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/alarm_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 37497 : static void adjust_upwards(grpc_alarm **first, gpr_uint32 i, grpc_alarm *t) {
47 105867 : while (i > 0) {
48 66988 : gpr_uint32 parent = (gpr_uint32)(((int)i - 1) / 2);
49 66988 : if (gpr_time_cmp(first[parent]->deadline, t->deadline) >= 0) break;
50 30873 : first[i] = first[parent];
51 30873 : first[i]->heap_index = i;
52 30873 : i = parent;
53 : }
54 37497 : first[i] = t;
55 37497 : t->heap_index = i;
56 37497 : }
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 38887 : static void adjust_downwards(grpc_alarm **first, gpr_uint32 i,
62 : gpr_uint32 length, grpc_alarm *t) {
63 : for (;;) {
64 38887 : gpr_uint32 left_child = 1u + 2u * i;
65 : gpr_uint32 right_child;
66 : gpr_uint32 next_i;
67 38887 : if (left_child >= length) break;
68 22512 : right_child = left_child + 1;
69 44657 : next_i = right_child < length &&
70 22145 : gpr_time_cmp(first[left_child]->deadline,
71 22145 : first[right_child]->deadline) < 0
72 : ? right_child
73 33770 : : left_child;
74 22512 : if (gpr_time_cmp(t->deadline, first[next_i]->deadline) >= 0) break;
75 17621 : first[i] = first[next_i];
76 17621 : first[i]->heap_index = i;
77 17621 : i = next_i;
78 17621 : }
79 21266 : first[i] = t;
80 21266 : t->heap_index = i;
81 21266 : }
82 :
83 : #define SHRINK_MIN_ELEMS 8
84 : #define SHRINK_FULLNESS_FACTOR 2
85 :
86 31875 : static void maybe_shrink(grpc_alarm_heap *heap) {
87 62645 : if (heap->alarm_count >= 8 &&
88 30770 : heap->alarm_count <= heap->alarm_capacity / SHRINK_FULLNESS_FACTOR / 2) {
89 30 : heap->alarm_capacity = heap->alarm_count * SHRINK_FULLNESS_FACTOR;
90 30 : heap->alarms =
91 30 : gpr_realloc(heap->alarms, heap->alarm_capacity * sizeof(grpc_alarm *));
92 : }
93 31875 : }
94 :
95 26396 : static void note_changed_priority(grpc_alarm_heap *heap, grpc_alarm *alarm) {
96 26396 : gpr_uint32 i = alarm->heap_index;
97 26396 : gpr_uint32 parent = (gpr_uint32)(((int)i - 1) / 2);
98 26396 : if (gpr_time_cmp(heap->alarms[parent]->deadline, alarm->deadline) < 0) {
99 5130 : adjust_upwards(heap->alarms, i, alarm);
100 : } else {
101 21266 : adjust_downwards(heap->alarms, i, heap->alarm_count, alarm);
102 : }
103 26396 : }
104 :
105 80266 : void grpc_alarm_heap_init(grpc_alarm_heap *heap) {
106 80266 : memset(heap, 0, sizeof(*heap));
107 80266 : }
108 :
109 80266 : void grpc_alarm_heap_destroy(grpc_alarm_heap *heap) { gpr_free(heap->alarms); }
110 :
111 32367 : int grpc_alarm_heap_add(grpc_alarm_heap *heap, grpc_alarm *alarm) {
112 32367 : if (heap->alarm_count == heap->alarm_capacity) {
113 1055 : heap->alarm_capacity =
114 1055 : GPR_MAX(heap->alarm_capacity + 1, heap->alarm_capacity * 3 / 2);
115 1055 : heap->alarms =
116 1055 : gpr_realloc(heap->alarms, heap->alarm_capacity * sizeof(grpc_alarm *));
117 : }
118 32367 : alarm->heap_index = heap->alarm_count;
119 32367 : adjust_upwards(heap->alarms, heap->alarm_count, alarm);
120 32367 : heap->alarm_count++;
121 32367 : return alarm->heap_index == 0;
122 : }
123 :
124 31875 : void grpc_alarm_heap_remove(grpc_alarm_heap *heap, grpc_alarm *alarm) {
125 31875 : gpr_uint32 i = alarm->heap_index;
126 31875 : if (i == heap->alarm_count - 1) {
127 5479 : heap->alarm_count--;
128 5479 : maybe_shrink(heap);
129 37354 : return;
130 : }
131 26396 : heap->alarms[i] = heap->alarms[heap->alarm_count - 1];
132 26396 : heap->alarms[i]->heap_index = i;
133 26396 : heap->alarm_count--;
134 26396 : maybe_shrink(heap);
135 26396 : note_changed_priority(heap, heap->alarms[i]);
136 : }
137 :
138 654690 : int grpc_alarm_heap_is_empty(grpc_alarm_heap *heap) {
139 654690 : return heap->alarm_count == 0;
140 : }
141 :
142 2704 : grpc_alarm *grpc_alarm_heap_top(grpc_alarm_heap *heap) {
143 2704 : return heap->alarms[0];
144 : }
145 :
146 924 : void grpc_alarm_heap_pop(grpc_alarm_heap *heap) {
147 924 : grpc_alarm_heap_remove(heap, grpc_alarm_heap_top(heap));
148 924 : }
|
