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/ext/transport/chttp2/transport/stream_map.h"
22
23 #include <string.h>
24
25 #include <grpc/support/alloc.h>
26 #include <grpc/support/log.h>
27
grpc_chttp2_stream_map_init(grpc_chttp2_stream_map * map,size_t initial_capacity)28 void grpc_chttp2_stream_map_init(grpc_chttp2_stream_map* map,
29 size_t initial_capacity) {
30 GPR_ASSERT(initial_capacity > 1);
31 map->keys =
32 static_cast<uint32_t*>(gpr_malloc(sizeof(uint32_t) * initial_capacity));
33 map->values =
34 static_cast<void**>(gpr_malloc(sizeof(void*) * initial_capacity));
35 map->count = 0;
36 map->free = 0;
37 map->capacity = initial_capacity;
38 }
39
grpc_chttp2_stream_map_destroy(grpc_chttp2_stream_map * map)40 void grpc_chttp2_stream_map_destroy(grpc_chttp2_stream_map* map) {
41 gpr_free(map->keys);
42 gpr_free(map->values);
43 }
44
compact(uint32_t * keys,void ** values,size_t count)45 static size_t compact(uint32_t* keys, void** values, size_t count) {
46 size_t i, out;
47
48 for (i = 0, out = 0; i < count; i++) {
49 if (values[i]) {
50 keys[out] = keys[i];
51 values[out] = values[i];
52 out++;
53 }
54 }
55
56 return out;
57 }
58
grpc_chttp2_stream_map_add(grpc_chttp2_stream_map * map,uint32_t key,void * value)59 void grpc_chttp2_stream_map_add(grpc_chttp2_stream_map* map, uint32_t key,
60 void* value) {
61 size_t count = map->count;
62 size_t capacity = map->capacity;
63 uint32_t* keys = map->keys;
64 void** values = map->values;
65
66 GPR_ASSERT(count == 0 || keys[count - 1] < key);
67 GPR_ASSERT(value);
68 GPR_ASSERT(grpc_chttp2_stream_map_find(map, key) == nullptr);
69
70 if (count == capacity) {
71 if (map->free > capacity / 4) {
72 count = compact(keys, values, count);
73 map->free = 0;
74 } else {
75 /* resize when less than 25% of the table is free, because compaction
76 won't help much */
77 map->capacity = capacity = 3 * capacity / 2;
78 map->keys = keys = static_cast<uint32_t*>(
79 gpr_realloc(keys, capacity * sizeof(uint32_t)));
80 map->values = values =
81 static_cast<void**>(gpr_realloc(values, capacity * sizeof(void*)));
82 }
83 }
84
85 keys[count] = key;
86 values[count] = value;
87 map->count = count + 1;
88 }
89
find(grpc_chttp2_stream_map * map,uint32_t key)90 static void** find(grpc_chttp2_stream_map* map, uint32_t key) {
91 size_t min_idx = 0;
92 size_t max_idx = map->count;
93 size_t mid_idx;
94 uint32_t* keys = map->keys;
95 void** values = map->values;
96 uint32_t mid_key;
97
98 if (max_idx == 0) return nullptr;
99
100 while (min_idx < max_idx) {
101 /* find the midpoint, avoiding overflow */
102 mid_idx = min_idx + ((max_idx - min_idx) / 2);
103 mid_key = keys[mid_idx];
104
105 if (mid_key < key) {
106 min_idx = mid_idx + 1;
107 } else if (mid_key > key) {
108 max_idx = mid_idx;
109 } else /* mid_key == key */
110 {
111 return &values[mid_idx];
112 }
113 }
114
115 return nullptr;
116 }
117
grpc_chttp2_stream_map_delete(grpc_chttp2_stream_map * map,uint32_t key)118 void* grpc_chttp2_stream_map_delete(grpc_chttp2_stream_map* map, uint32_t key) {
119 void** pvalue = find(map, key);
120 void* out = nullptr;
121 if (pvalue != nullptr) {
122 out = *pvalue;
123 *pvalue = nullptr;
124 map->free += (out != nullptr);
125 /* recognize complete emptyness and ensure we can skip
126 * defragmentation later */
127 if (map->free == map->count) {
128 map->free = map->count = 0;
129 }
130 GPR_ASSERT(grpc_chttp2_stream_map_find(map, key) == nullptr);
131 }
132 return out;
133 }
134
grpc_chttp2_stream_map_find(grpc_chttp2_stream_map * map,uint32_t key)135 void* grpc_chttp2_stream_map_find(grpc_chttp2_stream_map* map, uint32_t key) {
136 void** pvalue = find(map, key);
137 return pvalue != nullptr ? *pvalue : nullptr;
138 }
139
grpc_chttp2_stream_map_size(grpc_chttp2_stream_map * map)140 size_t grpc_chttp2_stream_map_size(grpc_chttp2_stream_map* map) {
141 return map->count - map->free;
142 }
143
grpc_chttp2_stream_map_rand(grpc_chttp2_stream_map * map)144 void* grpc_chttp2_stream_map_rand(grpc_chttp2_stream_map* map) {
145 if (map->count == map->free) {
146 return nullptr;
147 }
148 if (map->free != 0) {
149 map->count = compact(map->keys, map->values, map->count);
150 map->free = 0;
151 GPR_ASSERT(map->count > 0);
152 }
153 return map->values[(static_cast<size_t>(rand())) % map->count];
154 }
155
grpc_chttp2_stream_map_for_each(grpc_chttp2_stream_map * map,void (* f)(void * user_data,uint32_t key,void * value),void * user_data)156 void grpc_chttp2_stream_map_for_each(grpc_chttp2_stream_map* map,
157 void (*f)(void* user_data, uint32_t key,
158 void* value),
159 void* user_data) {
160 size_t i;
161
162 for (i = 0; i < map->count; i++) {
163 if (map->values[i]) {
164 f(user_data, map->keys[i], map->values[i]);
165 }
166 }
167 }
168