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 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 40 void grpc_chttp2_stream_map_destroy(grpc_chttp2_stream_map* map) { 41 gpr_free(map->keys); 42 gpr_free(map->values); 43 } 44 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 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 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 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 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 140 size_t grpc_chttp2_stream_map_size(grpc_chttp2_stream_map* map) { 141 return map->count - map->free; 142 } 143 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 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