1 /*
2 * nghttp2 - HTTP/2 C Library
3 *
4 * Copyright (c) 2017 ngtcp2 contributors
5 * Copyright (c) 2012 nghttp2 contributors
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining
8 * a copy of this software and associated documentation files (the
9 * "Software"), to deal in the Software without restriction, including
10 * without limitation the rights to use, copy, modify, merge, publish,
11 * distribute, sublicense, and/or sell copies of the Software, and to
12 * permit persons to whom the Software is furnished to do so, subject to
13 * the following conditions:
14 *
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
22 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
23 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
24 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25 */
26 #include "nghttp2_map.h"
27
28 #include <string.h>
29 #include <assert.h>
30 #include <stdio.h>
31
32 #include "nghttp2_helper.h"
33
34 #define NGHTTP2_INITIAL_TABLE_LENBITS 4
35
nghttp2_map_init(nghttp2_map * map,nghttp2_mem * mem)36 void nghttp2_map_init(nghttp2_map *map, nghttp2_mem *mem) {
37 map->mem = mem;
38 map->hashbits = 0;
39 map->table = NULL;
40 map->size = 0;
41 }
42
nghttp2_map_free(nghttp2_map * map)43 void nghttp2_map_free(nghttp2_map *map) {
44 if (!map) {
45 return;
46 }
47
48 nghttp2_mem_free(map->mem, map->table);
49 }
50
nghttp2_map_each(const nghttp2_map * map,int (* func)(void * data,void * ptr),void * ptr)51 int nghttp2_map_each(const nghttp2_map *map, int (*func)(void *data, void *ptr),
52 void *ptr) {
53 int rv;
54 size_t i;
55 nghttp2_map_bucket *bkt;
56 size_t tablelen;
57
58 if (map->size == 0) {
59 return 0;
60 }
61
62 tablelen = 1u << map->hashbits;
63
64 for (i = 0; i < tablelen; ++i) {
65 bkt = &map->table[i];
66
67 if (bkt->data == NULL) {
68 continue;
69 }
70
71 rv = func(bkt->data, ptr);
72 if (rv != 0) {
73 return rv;
74 }
75 }
76
77 return 0;
78 }
79
hash(nghttp2_map_key_type key,size_t bits)80 static size_t hash(nghttp2_map_key_type key, size_t bits) {
81 return (size_t)(((uint32_t)key * 2654435769u) >> (32 - bits));
82 }
83
map_bucket_swap(nghttp2_map_bucket * a,nghttp2_map_bucket * b)84 static void map_bucket_swap(nghttp2_map_bucket *a, nghttp2_map_bucket *b) {
85 nghttp2_map_bucket c = *a;
86
87 *a = *b;
88 *b = c;
89 }
90
91 #ifndef WIN32
nghttp2_map_print_distance(const nghttp2_map * map)92 void nghttp2_map_print_distance(const nghttp2_map *map) {
93 size_t i;
94 size_t idx;
95 nghttp2_map_bucket *bkt;
96 size_t tablelen;
97
98 if (map->size == 0) {
99 return;
100 }
101
102 tablelen = 1u << map->hashbits;
103
104 for (i = 0; i < tablelen; ++i) {
105 bkt = &map->table[i];
106
107 if (bkt->data == NULL) {
108 fprintf(stderr, "@%zu <EMPTY>\n", i);
109 continue;
110 }
111
112 idx = hash(bkt->key, map->hashbits);
113 fprintf(stderr, "@%zu hash=%zu key=%d base=%zu distance=%u\n", i,
114 hash(bkt->key, map->hashbits), bkt->key, idx, bkt->psl);
115 }
116 }
117 #endif /* !WIN32 */
118
insert(nghttp2_map_bucket * table,size_t hashbits,nghttp2_map_key_type key,void * data)119 static int insert(nghttp2_map_bucket *table, size_t hashbits,
120 nghttp2_map_key_type key, void *data) {
121 size_t idx = hash(key, hashbits);
122 nghttp2_map_bucket b = {0, key, data}, *bkt;
123 size_t mask = (1u << hashbits) - 1;
124
125 for (;;) {
126 bkt = &table[idx];
127
128 if (bkt->data == NULL) {
129 *bkt = b;
130 return 0;
131 }
132
133 if (b.psl > bkt->psl) {
134 map_bucket_swap(bkt, &b);
135 } else if (bkt->key == key) {
136 /* TODO This check is just a waste after first swap or if this
137 function is called from map_resize. That said, there is no
138 difference with or without this conditional in performance
139 wise. */
140 return NGHTTP2_ERR_INVALID_ARGUMENT;
141 }
142
143 ++b.psl;
144 idx = (idx + 1) & mask;
145 }
146 }
147
map_resize(nghttp2_map * map,size_t new_hashbits)148 static int map_resize(nghttp2_map *map, size_t new_hashbits) {
149 size_t i;
150 nghttp2_map_bucket *new_table;
151 nghttp2_map_bucket *bkt;
152 size_t tablelen;
153 int rv;
154 (void)rv;
155
156 new_table = nghttp2_mem_calloc(map->mem, 1u << new_hashbits,
157 sizeof(nghttp2_map_bucket));
158 if (new_table == NULL) {
159 return NGHTTP2_ERR_NOMEM;
160 }
161
162 if (map->size) {
163 tablelen = 1u << map->hashbits;
164
165 for (i = 0; i < tablelen; ++i) {
166 bkt = &map->table[i];
167 if (bkt->data == NULL) {
168 continue;
169 }
170
171 rv = insert(new_table, new_hashbits, bkt->key, bkt->data);
172
173 assert(0 == rv);
174 }
175 }
176
177 nghttp2_mem_free(map->mem, map->table);
178 map->hashbits = new_hashbits;
179 map->table = new_table;
180
181 return 0;
182 }
183
nghttp2_map_insert(nghttp2_map * map,nghttp2_map_key_type key,void * data)184 int nghttp2_map_insert(nghttp2_map *map, nghttp2_map_key_type key, void *data) {
185 int rv;
186
187 assert(data);
188
189 /* Load factor is 0.75 */
190 /* Under the very initial condition, that is map->size == 0 and
191 map->hashbits == 0, 4 > 3 still holds nicely. */
192 if ((map->size + 1) * 4 > (1u << map->hashbits) * 3) {
193 if (map->hashbits) {
194 rv = map_resize(map, map->hashbits + 1);
195 if (rv != 0) {
196 return rv;
197 }
198 } else {
199 rv = map_resize(map, NGHTTP2_INITIAL_TABLE_LENBITS);
200 if (rv != 0) {
201 return rv;
202 }
203 }
204 }
205
206 rv = insert(map->table, map->hashbits, key, data);
207 if (rv != 0) {
208 return rv;
209 }
210
211 ++map->size;
212
213 return 0;
214 }
215
nghttp2_map_find(const nghttp2_map * map,nghttp2_map_key_type key)216 void *nghttp2_map_find(const nghttp2_map *map, nghttp2_map_key_type key) {
217 size_t idx;
218 nghttp2_map_bucket *bkt;
219 size_t psl = 0;
220 size_t mask;
221
222 if (map->size == 0) {
223 return NULL;
224 }
225
226 idx = hash(key, map->hashbits);
227 mask = (1u << map->hashbits) - 1;
228
229 for (;;) {
230 bkt = &map->table[idx];
231
232 if (bkt->data == NULL || psl > bkt->psl) {
233 return NULL;
234 }
235
236 if (bkt->key == key) {
237 return bkt->data;
238 }
239
240 ++psl;
241 idx = (idx + 1) & mask;
242 }
243 }
244
nghttp2_map_remove(nghttp2_map * map,nghttp2_map_key_type key)245 int nghttp2_map_remove(nghttp2_map *map, nghttp2_map_key_type key) {
246 size_t idx;
247 nghttp2_map_bucket *b, *bkt;
248 size_t psl = 0;
249 size_t mask;
250
251 if (map->size == 0) {
252 return NGHTTP2_ERR_INVALID_ARGUMENT;
253 }
254
255 idx = hash(key, map->hashbits);
256 mask = (1u << map->hashbits) - 1;
257
258 for (;;) {
259 bkt = &map->table[idx];
260
261 if (bkt->data == NULL || psl > bkt->psl) {
262 return NGHTTP2_ERR_INVALID_ARGUMENT;
263 }
264
265 if (bkt->key == key) {
266 b = bkt;
267 idx = (idx + 1) & mask;
268
269 for (;;) {
270 bkt = &map->table[idx];
271 if (bkt->data == NULL || bkt->psl == 0) {
272 b->data = NULL;
273 break;
274 }
275
276 --bkt->psl;
277 *b = *bkt;
278 b = bkt;
279
280 idx = (idx + 1) & mask;
281 }
282
283 --map->size;
284
285 return 0;
286 }
287
288 ++psl;
289 idx = (idx + 1) & mask;
290 }
291 }
292
nghttp2_map_clear(nghttp2_map * map)293 void nghttp2_map_clear(nghttp2_map *map) {
294 if (map->size == 0) {
295 return;
296 }
297
298 memset(map->table, 0, sizeof(*map->table) * (1u << map->hashbits));
299 map->size = 0;
300 }
301
nghttp2_map_size(const nghttp2_map * map)302 size_t nghttp2_map_size(const nghttp2_map *map) { return map->size; }
303