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/transport/chttp2/stream_map.h"
35 :
36 : #include <string.h>
37 :
38 : #include <grpc/support/alloc.h>
39 : #include <grpc/support/log.h>
40 : #include <grpc/support/useful.h>
41 :
42 8127 : void grpc_chttp2_stream_map_init(grpc_chttp2_stream_map *map,
43 : size_t initial_capacity) {
44 8127 : GPR_ASSERT(initial_capacity > 1);
45 8127 : map->keys = gpr_malloc(sizeof(gpr_uint32) * initial_capacity);
46 8127 : map->values = gpr_malloc(sizeof(void *) * initial_capacity);
47 8127 : map->count = 0;
48 8127 : map->free = 0;
49 8127 : map->capacity = initial_capacity;
50 8127 : }
51 :
52 8127 : void grpc_chttp2_stream_map_destroy(grpc_chttp2_stream_map *map) {
53 8127 : gpr_free(map->keys);
54 8127 : gpr_free(map->values);
55 8127 : }
56 :
57 26438 : static size_t compact(gpr_uint32 *keys, void **values, size_t count) {
58 : size_t i, out;
59 :
60 2545089 : for (i = 0, out = 0; i < count; i++) {
61 2518651 : if (values[i]) {
62 1140734 : keys[out] = keys[i];
63 1140734 : values[out] = values[i];
64 1140734 : out++;
65 : }
66 : }
67 :
68 26438 : return out;
69 : }
70 :
71 3488071 : void grpc_chttp2_stream_map_add(grpc_chttp2_stream_map *map, gpr_uint32 key,
72 : void *value) {
73 3488071 : size_t count = map->count;
74 3488071 : size_t capacity = map->capacity;
75 3488071 : gpr_uint32 *keys = map->keys;
76 3488071 : void **values = map->values;
77 :
78 3488071 : GPR_ASSERT(count == 0 || keys[count - 1] < key);
79 3488071 : GPR_ASSERT(value);
80 :
81 3488071 : if (count == capacity) {
82 27722 : if (map->free > capacity / 4) {
83 26438 : count = compact(keys, values, count);
84 26438 : map->free = 0;
85 : } else {
86 : /* resize when less than 25% of the table is free, because compaction
87 : won't help much */
88 1284 : map->capacity = capacity = 3 * capacity / 2;
89 1284 : map->keys = keys = gpr_realloc(keys, capacity * sizeof(gpr_uint32));
90 1284 : map->values = values = gpr_realloc(values, capacity * sizeof(void *));
91 : }
92 : }
93 :
94 3488071 : keys[count] = key;
95 3488071 : values[count] = value;
96 3488071 : map->count = count + 1;
97 3488071 : }
98 :
99 4931886 : void grpc_chttp2_stream_map_move_into(grpc_chttp2_stream_map *src,
100 : grpc_chttp2_stream_map *dst) {
101 : /* if src is empty we dont need to do anything */
102 4931886 : if (src->count == src->free) {
103 4620467 : return;
104 : }
105 : /* if dst is empty we simply need to swap */
106 311419 : if (dst->count == dst->free) {
107 235424 : GPR_SWAP(grpc_chttp2_stream_map, *src, *dst);
108 235424 : return;
109 : }
110 : /* the first element of src must be greater than the last of dst...
111 : * however the maps may need compacting for this property to hold */
112 75995 : if (src->keys[0] <= dst->keys[dst->count - 1]) {
113 0 : src->count = compact(src->keys, src->values, src->count);
114 0 : src->free = 0;
115 0 : dst->count = compact(dst->keys, dst->values, dst->count);
116 0 : dst->free = 0;
117 : }
118 75995 : GPR_ASSERT(src->keys[0] > dst->keys[dst->count - 1]);
119 : /* if dst doesn't have capacity, resize */
120 75995 : if (dst->count + src->count > dst->capacity) {
121 233 : dst->capacity = GPR_MAX(dst->capacity * 3 / 2, dst->count + src->count);
122 233 : dst->keys = gpr_realloc(dst->keys, dst->capacity * sizeof(gpr_uint32));
123 233 : dst->values = gpr_realloc(dst->values, dst->capacity * sizeof(void *));
124 : }
125 75995 : memcpy(dst->keys + dst->count, src->keys, src->count * sizeof(gpr_uint32));
126 75995 : memcpy(dst->values + dst->count, src->values, src->count * sizeof(void *));
127 75995 : dst->count += src->count;
128 75995 : dst->free += src->free;
129 75995 : src->count = 0;
130 75995 : src->free = 0;
131 : }
132 :
133 15324277 : static void **find(grpc_chttp2_stream_map *map, gpr_uint32 key) {
134 15324277 : size_t min_idx = 0;
135 15324277 : size_t max_idx = map->count;
136 : size_t mid_idx;
137 15324277 : gpr_uint32 *keys = map->keys;
138 15324277 : void **values = map->values;
139 : gpr_uint32 mid_key;
140 :
141 15324277 : if (max_idx == 0) return NULL;
142 :
143 166847233 : while (min_idx < max_idx) {
144 : /* find the midpoint, avoiding overflow */
145 150596408 : mid_idx = min_idx + ((max_idx - min_idx) / 2);
146 150596408 : mid_key = keys[mid_idx];
147 :
148 150596408 : if (mid_key < key) {
149 96462888 : min_idx = mid_idx + 1;
150 54133520 : } else if (mid_key > key) {
151 40784205 : max_idx = mid_idx;
152 : } else /* mid_key == key */
153 : {
154 13349315 : return &values[mid_idx];
155 : }
156 : }
157 :
158 1450755 : return NULL;
159 : }
160 :
161 3093630 : void *grpc_chttp2_stream_map_delete(grpc_chttp2_stream_map *map,
162 : gpr_uint32 key) {
163 3093630 : void **pvalue = find(map, key);
164 3096789 : void *out = NULL;
165 3096789 : if (pvalue != NULL) {
166 3096541 : out = *pvalue;
167 3096541 : *pvalue = NULL;
168 3096541 : map->free += (out != NULL);
169 : /* recognize complete emptyness and ensure we can skip
170 : * defragmentation later */
171 3096541 : if (map->free == map->count) {
172 370339 : map->free = map->count = 0;
173 : }
174 : }
175 3096789 : return out;
176 : }
177 :
178 12211410 : void *grpc_chttp2_stream_map_find(grpc_chttp2_stream_map *map, gpr_uint32 key) {
179 12211410 : void **pvalue = find(map, key);
180 12235462 : return pvalue != NULL ? *pvalue : NULL;
181 : }
182 :
183 7877582 : size_t grpc_chttp2_stream_map_size(grpc_chttp2_stream_map *map) {
184 7877582 : return map->count - map->free;
185 : }
186 :
187 48 : void grpc_chttp2_stream_map_for_each(grpc_chttp2_stream_map *map,
188 : void (*f)(void *user_data, gpr_uint32 key,
189 : void *value),
190 : void *user_data) {
191 : size_t i;
192 :
193 320744 : for (i = 0; i < map->count; i++) {
194 320696 : if (map->values[i]) {
195 196432 : f(user_data, map->keys[i], map->values[i]);
196 : }
197 : }
198 48 : }
|
