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
37void 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
45void nghttp3_map_free(nghttp3_map *map) {
46  if (!map) {
47    return;
48  }
49
50  nghttp3_mem_free(map->mem, map->table);
51}
52
53void 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
69int 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
95static uint32_t hash(nghttp3_map_key_type key) {
96  return (uint32_t)((key * 11400714819323198485llu) >> 32);
97}
98
99static size_t h2idx(uint32_t hash, uint32_t bits) {
100  return hash >> (32 - bits);
101}
102
103static 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
108static 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
123static 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
130void 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
150static 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. */
184static 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
217int 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
247void *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
277int 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
328void 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
337size_t nghttp3_map_size(nghttp3_map *map) { return map->size; }
338