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