/src/nghttp2/lib/nghttp2_map.c

Source (jump to first uncovered line)
/*
 * nghttp2 - HTTP/2 C Library
 *
 * Copyright (c) 2017 ngtcp2 contributors
 * Copyright (c) 2012 nghttp2 contributors
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#include "nghttp2_map.h"

#include <string.h>
#include <assert.h>
#include <stdio.h>

#include "nghttp2_helper.h"

#define NGHTTP2_INITIAL_TABLE_LENBITS 4

void nghttp2_map_init(nghttp2_map *map, nghttp2_mem *mem) {
  map->mem = mem;
  map->tablelen = 0;
  map->tablelenbits = 0;
  map->table = NULL;
  map->size = 0;
}

void nghttp2_map_free(nghttp2_map *map) {
  if (!map) {
    return;
  }

  nghttp2_mem_free(map->mem, map->table);
}

void nghttp2_map_each_free(nghttp2_map *map, int (*func)(void *data, void *ptr),
                           void *ptr) {
  uint32_t i;
  nghttp2_map_bucket *bkt;

  for (i = 0; i < map->tablelen; ++i) {
    bkt = &map->table[i];

    if (bkt->data == NULL) {
      continue;
    }

    func(bkt->data, ptr);
  }
}

int nghttp2_map_each(nghttp2_map *map, int (*func)(void *data, void *ptr),
                     void *ptr) {
  int rv;
  uint32_t i;
  nghttp2_map_bucket *bkt;

  if (map->size == 0) {
    return 0;
  }

  for (i = 0; i < map->tablelen; ++i) {
    bkt = &map->table[i];

    if (bkt->data == NULL) {
      continue;
    }

    rv = func(bkt->data, ptr);
    if (rv != 0) {
      return rv;
    }
  }

  return 0;
}

static uint32_t hash(nghttp2_map_key_type key) {
  return (uint32_t)key * 2654435769u;
}

static size_t h2idx(uint32_t hash, uint32_t bits) {
  return hash >> (32 - bits);
}

static size_t distance(uint32_t tablelen, uint32_t tablelenbits,
                       nghttp2_map_bucket *bkt, size_t idx) {
  return (idx - h2idx(bkt->hash, tablelenbits)) & (tablelen - 1);
}

static void map_bucket_swap(nghttp2_map_bucket *bkt, uint32_t *phash,
                            nghttp2_map_key_type *pkey, void **pdata) {
  uint32_t h = bkt->hash;
  nghttp2_map_key_type key = bkt->key;
  void *data = bkt->data;

  bkt->hash = *phash;
  bkt->key = *pkey;
  bkt->data = *pdata;

  *phash = h;
  *pkey = key;
  *pdata = data;
}

static void map_bucket_set_data(nghttp2_map_bucket *bkt, uint32_t hash,
                                nghttp2_map_key_type key, void *data) {
  bkt->hash = hash;
  bkt->key = key;
  bkt->data = data;
}

#ifndef WIN32
void nghttp2_map_print_distance(nghttp2_map *map) {
  uint32_t i;
  size_t idx;
  nghttp2_map_bucket *bkt;

  for (i = 0; i < map->tablelen; ++i) {
    bkt = &map->table[i];

    if (bkt->data == NULL) {
      fprintf(stderr, "@%u <EMPTY>\n", i);
      continue;
    }

    idx = h2idx(bkt->hash, map->tablelenbits);
    fprintf(stderr, "@%u hash=%08x key=%d base=%zu distance=%zu\n", i,
            bkt->hash, bkt->key, idx,
            distance(map->tablelen, map->tablelenbits, bkt, idx));
  }
}
#endif /* !WIN32 */

static int insert(nghttp2_map_bucket *table, uint32_t tablelen,
                  uint32_t tablelenbits, uint32_t hash,
                  nghttp2_map_key_type key, void *data) {
  size_t idx = h2idx(hash, tablelenbits);
  size_t d = 0, dd;
  nghttp2_map_bucket *bkt;

  for (;;) {
    bkt = &table[idx];

    if (bkt->data == NULL) {
      map_bucket_set_data(bkt, hash, key, data);
      return 0;
    }

    dd = distance(tablelen, tablelenbits, bkt, idx);
    if (d > dd) {
      map_bucket_swap(bkt, &hash, &key, &data);
      d = dd;
    } else if (bkt->key == key) {
      /* TODO This check is just a waste after first swap or if this
         function is called from map_resize.  That said, there is no
         difference with or without this conditional in performance
         wise. */
      return NGHTTP2_ERR_INVALID_ARGUMENT;
    }

    ++d;
    idx = (idx + 1) & (tablelen - 1);
  }
}

/* new_tablelen must be power of 2 and new_tablelen == (1 <<
   new_tablelenbits) must hold. */
static int map_resize(nghttp2_map *map, uint32_t new_tablelen,
                      uint32_t new_tablelenbits) {
  uint32_t i;
  nghttp2_map_bucket *new_table;
  nghttp2_map_bucket *bkt;
  int rv;
  (void)rv;

  new_table =
      nghttp2_mem_calloc(map->mem, new_tablelen, sizeof(nghttp2_map_bucket));
  if (new_table == NULL) {
    return NGHTTP2_ERR_NOMEM;
  }

  for (i = 0; i < map->tablelen; ++i) {
    bkt = &map->table[i];
    if (bkt->data == NULL) {
      continue;
    }
    rv = insert(new_table, new_tablelen, new_tablelenbits, bkt->hash, bkt->key,
                bkt->data);

    assert(0 == rv);
  }

  nghttp2_mem_free(map->mem, map->table);
  map->tablelen = new_tablelen;
  map->tablelenbits = new_tablelenbits;
  map->table = new_table;

  return 0;
}

int nghttp2_map_insert(nghttp2_map *map, nghttp2_map_key_type key, void *data) {
  int rv;

  assert(data);

  /* Load factor is 0.75 */
  if ((map->size + 1) * 4 > map->tablelen * 3) {
    if (map->tablelen) {
      rv = map_resize(map, map->tablelen * 2, map->tablelenbits + 1);
      if (rv != 0) {
        return rv;
      }
    } else {
      rv = map_resize(map, 1 << NGHTTP2_INITIAL_TABLE_LENBITS,
                      NGHTTP2_INITIAL_TABLE_LENBITS);
      if (rv != 0) {
        return rv;
      }
    }
  }

  rv = insert(map->table, map->tablelen, map->tablelenbits, hash(key), key,
              data);
  if (rv != 0) {
    return rv;
  }
  ++map->size;
  return 0;
}

void *nghttp2_map_find(nghttp2_map *map, nghttp2_map_key_type key) {
  uint32_t h;
  size_t idx;
  nghttp2_map_bucket *bkt;
  size_t d = 0;

  if (map->size == 0) {
    return NULL;
  }

  h = hash(key);
  idx = h2idx(h, map->tablelenbits);

  for (;;) {
    bkt = &map->table[idx];

    if (bkt->data == NULL ||
        d > distance(map->tablelen, map->tablelenbits, bkt, idx)) {
      return NULL;
    }

    if (bkt->key == key) {
      return bkt->data;
    }

    ++d;
    idx = (idx + 1) & (map->tablelen - 1);
  }
}

int nghttp2_map_remove(nghttp2_map *map, nghttp2_map_key_type key) {
  uint32_t h;
  size_t idx, didx;
  nghttp2_map_bucket *bkt;
  size_t d = 0;

  if (map->size == 0) {
    return NGHTTP2_ERR_INVALID_ARGUMENT;
  }

  h = hash(key);
  idx = h2idx(h, map->tablelenbits);

  for (;;) {
    bkt = &map->table[idx];

    if (bkt->data == NULL ||
        d > distance(map->tablelen, map->tablelenbits, bkt, idx)) {
      return NGHTTP2_ERR_INVALID_ARGUMENT;
    }

    if (bkt->key == key) {
      map_bucket_set_data(bkt, 0, 0, NULL);

      didx = idx;
      idx = (idx + 1) & (map->tablelen - 1);

      for (;;) {
        bkt = &map->table[idx];
        if (bkt->data == NULL ||
            distance(map->tablelen, map->tablelenbits, bkt, idx) == 0) {
          break;
        }

        map->table[didx] = *bkt;
        map_bucket_set_data(bkt, 0, 0, NULL);
        didx = idx;

        idx = (idx + 1) & (map->tablelen - 1);
      }

      --map->size;

      return 0;
    }

    ++d;
    idx = (idx + 1) & (map->tablelen - 1);
  }
}

void nghttp2_map_clear(nghttp2_map *map) {
  if (map->tablelen == 0) {
    return;
  }

  memset(map->table, 0, sizeof(*map->table) * map->tablelen);
  map->size = 0;
}

size_t nghttp2_map_size(nghttp2_map *map) { return map->size; }

Coverage Report

Created: 2024-05-21 06:52

Line	Count	Source (jump to first uncovered line)
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	25.7k	#define NGHTTP2_INITIAL_TABLE_LENBITS 4
35
36	13.0k	void nghttp2_map_init(nghttp2_map map, nghttp2_mem mem) {
37	13.0k	map->mem = mem;
38	13.0k	map->tablelen = 0;
39	13.0k	map->tablelenbits = 0;
40	13.0k	map->table = NULL;
41	13.0k	map->size = 0;
42	13.0k	}
43
44	13.0k	void nghttp2_map_free(nghttp2_map *map) {
45	13.0k	if (!map) {
46	0	return;
47	0	}
48
49	13.0k	nghttp2_mem_free(map->mem, map->table);
50	13.0k	}
51
52		void nghttp2_map_each_free(nghttp2_map map, int (func)(void data, void ptr),
53	13.0k	void *ptr) {
54	13.0k	uint32_t i;
55	13.0k	nghttp2_map_bucket *bkt;
56
57	219k	for (i = 0; i < map->tablelen; ++i) {
58	206k	bkt = &map->table[i];
59
60	206k	if (bkt->data == NULL) {
61	203k	continue;
62	203k	}
63
64	2.94k	func(bkt->data, ptr);
65	2.94k	}
66	13.0k	}
67
68		int nghttp2_map_each(nghttp2_map map, int (func)(void data, void ptr),
69	6.77k	void *ptr) {
70	6.77k	int rv;
71	6.77k	uint32_t i;
72	6.77k	nghttp2_map_bucket *bkt;
73
74	6.77k	if (map->size == 0) {
75	1.80k	return 0;
76	1.80k	}
77
78	84.4k	for (i = 0; i < map->tablelen; ++i) {
79	79.4k	bkt = &map->table[i];
80
81	79.4k	if (bkt->data == NULL) {
82	74.5k	continue;
83	74.5k	}
84
85	4.96k	rv = func(bkt->data, ptr);
86	4.96k	if (rv != 0) {
87	0	return rv;
88	0	}
89	4.96k	}
90
91	4.96k	return 0;
92	4.96k	}
93
94	10.2M	static uint32_t hash(nghttp2_map_key_type key) {
95	10.2M	return (uint32_t)key * 2654435769u;
96	10.2M	}
97
98	20.5M	static size_t h2idx(uint32_t hash, uint32_t bits) {
99	20.5M	return hash >> (32 - bits);
100	20.5M	}
101
102		static size_t distance(uint32_t tablelen, uint32_t tablelenbits,
103	10.2M	nghttp2_map_bucket *bkt, size_t idx) {
104	10.2M	return (idx - h2idx(bkt->hash, tablelenbits)) & (tablelen - 1);
105	10.2M	}
106
107		static void map_bucket_swap(nghttp2_map_bucket bkt, uint32_t phash,
108	0	nghttp2_map_key_type pkey, void *pdata) {
109	0	uint32_t h = bkt->hash;
110	0	nghttp2_map_key_type key = bkt->key;
111	0	void *data = bkt->data;
112
113	0	bkt->hash = *phash;
114	0	bkt->key = *pkey;
115	0	bkt->data = *pdata;
116
117	0	*phash = h;
118	0	*pkey = key;
119	0	*pdata = data;
120	0	}
121
122		static void map_bucket_set_data(nghttp2_map_bucket *bkt, uint32_t hash,
123	23.7k	nghttp2_map_key_type key, void *data) {
124	23.7k	bkt->hash = hash;
125	23.7k	bkt->key = key;
126	23.7k	bkt->data = data;
127	23.7k	}
128
129		#ifndef WIN32
130	0	void nghttp2_map_print_distance(nghttp2_map *map) {
131	0	uint32_t i;
132	0	size_t idx;
133	0	nghttp2_map_bucket *bkt;
134
135	0	for (i = 0; i < map->tablelen; ++i) {
136	0	bkt = &map->table[i];
137
138	0	if (bkt->data == NULL) {
139	0	fprintf(stderr, "@%u <EMPTY>\n", i);
140	0	continue;
141	0	}
142
143	0	idx = h2idx(bkt->hash, map->tablelenbits);
144	0	fprintf(stderr, "@%u hash=%08x key=%d base=%zu distance=%zu\n", i,
145	0	bkt->hash, bkt->key, idx,
146	0	distance(map->tablelen, map->tablelenbits, bkt, idx));
147	0	}
148	0	}
149		#endif /* !WIN32 */
150
151		static int insert(nghttp2_map_bucket *table, uint32_t tablelen,
152		uint32_t tablelenbits, uint32_t hash,
153	13.3k	nghttp2_map_key_type key, void *data) {
154	13.3k	size_t idx = h2idx(hash, tablelenbits);
155	13.3k	size_t d = 0, dd;
156	13.3k	nghttp2_map_bucket *bkt;
157
158	13.3k	for (;;) {
159	13.3k	bkt = &table[idx];
160
161	13.3k	if (bkt->data == NULL) {
162	13.3k	map_bucket_set_data(bkt, hash, key, data);
163	13.3k	return 0;
164	13.3k	}
165
166	0	dd = distance(tablelen, tablelenbits, bkt, idx);
167	0	if (d > dd) {
168	0	map_bucket_swap(bkt, &hash, &key, &data);
169	0	d = dd;
170	0	} else if (bkt->key == key) {
171		/* TODO This check is just a waste after first swap or if this
172		function is called from map_resize. That said, there is no
173		difference with or without this conditional in performance
174		wise. */
175	0	return NGHTTP2_ERR_INVALID_ARGUMENT;
176	0	}
177
178	0	++d;
179	0	idx = (idx + 1) & (tablelen - 1);
180	0	}
181	13.3k	}
182
183		/* new_tablelen must be power of 2 and new_tablelen == (1 <<
184		new_tablelenbits) must hold. */
185		static int map_resize(nghttp2_map *map, uint32_t new_tablelen,
186	12.8k	uint32_t new_tablelenbits) {
187	12.8k	uint32_t i;
188	12.8k	nghttp2_map_bucket *new_table;
189	12.8k	nghttp2_map_bucket *bkt;
190	12.8k	int rv;
191	12.8k	(void)rv;
192
193	12.8k	new_table =
194	12.8k	nghttp2_mem_calloc(map->mem, new_tablelen, sizeof(nghttp2_map_bucket));
195	12.8k	if (new_table == NULL) {
196	0	return NGHTTP2_ERR_NOMEM;
197	0	}
198
199	12.8k	for (i = 0; i < map->tablelen; ++i) {
200	0	bkt = &map->table[i];
201	0	if (bkt->data == NULL) {
202	0	continue;
203	0	}
204	0	rv = insert(new_table, new_tablelen, new_tablelenbits, bkt->hash, bkt->key,
205	0	bkt->data);
206
207	0	assert(0 == rv);
208	0	}
209
210	12.8k	nghttp2_mem_free(map->mem, map->table);
211	12.8k	map->tablelen = new_tablelen;
212	12.8k	map->tablelenbits = new_tablelenbits;
213	12.8k	map->table = new_table;
214
215	12.8k	return 0;
216	12.8k	}
217
218	13.3k	int nghttp2_map_insert(nghttp2_map map, nghttp2_map_key_type key, void data) {
219	13.3k	int rv;
220
221	13.3k	assert(data);
222
223		/* Load factor is 0.75 */
224	13.3k	if ((map->size + 1) * 4 > map->tablelen * 3) {
225	12.8k	if (map->tablelen) {
226	0	rv = map_resize(map, map->tablelen * 2, map->tablelenbits + 1);
227	0	if (rv != 0) {
228	0	return rv;
229	0	}
230	12.8k	} else {
231	12.8k	rv = map_resize(map, 1 << NGHTTP2_INITIAL_TABLE_LENBITS,
232	12.8k	NGHTTP2_INITIAL_TABLE_LENBITS);
233	12.8k	if (rv != 0) {
234	0	return rv;
235	0	}
236	12.8k	}
237	12.8k	}
238
239	13.3k	rv = insert(map->table, map->tablelen, map->tablelenbits, hash(key), key,
240	13.3k	data);
241	13.3k	if (rv != 0) {
242	0	return rv;
243	0	}
244	13.3k	++map->size;
245	13.3k	return 0;
246	13.3k	}
247
248	17.4M	void nghttp2_map_find(nghttp2_map map, nghttp2_map_key_type key) {
249	17.4M	uint32_t h;
250	17.4M	size_t idx;
251	17.4M	nghttp2_map_bucket *bkt;
252	17.4M	size_t d = 0;
253
254	17.4M	if (map->size == 0) {
255	7.20M	return NULL;
256	7.20M	}
257
258	10.2M	h = hash(key);
259	10.2M	idx = h2idx(h, map->tablelenbits);
260
261	10.2M	for (;;) {
262	10.2M	bkt = &map->table[idx];
263
264	10.2M	if (bkt->data == NULL \|\|
265	10.2M	d > distance(map->tablelen, map->tablelenbits, bkt, idx)) {
266	16.0k	return NULL;
267	16.0k	}
268
269	10.2M	if (bkt->key == key) {
270	10.2M	return bkt->data;
271	10.2M	}
272
273	270	++d;
274	270	idx = (idx + 1) & (map->tablelen - 1);
275	270	}
276	10.2M	}
277
278	10.3k	int nghttp2_map_remove(nghttp2_map *map, nghttp2_map_key_type key) {
279	10.3k	uint32_t h;
280	10.3k	size_t idx, didx;
281	10.3k	nghttp2_map_bucket *bkt;
282	10.3k	size_t d = 0;
283
284	10.3k	if (map->size == 0) {
285	0	return NGHTTP2_ERR_INVALID_ARGUMENT;
286	0	}
287
288	10.3k	h = hash(key);
289	10.3k	idx = h2idx(h, map->tablelenbits);
290
291	10.3k	for (;;) {
292	10.3k	bkt = &map->table[idx];
293
294	10.3k	if (bkt->data == NULL \|\|
295	10.3k	d > distance(map->tablelen, map->tablelenbits, bkt, idx)) {
296	0	return NGHTTP2_ERR_INVALID_ARGUMENT;
297	0	}
298
299	10.3k	if (bkt->key == key) {
300	10.3k	map_bucket_set_data(bkt, 0, 0, NULL);
301
302	10.3k	didx = idx;
303	10.3k	idx = (idx + 1) & (map->tablelen - 1);
304
305	10.3k	for (;;) {
306	10.3k	bkt = &map->table[idx];
307	10.3k	if (bkt->data == NULL \|\|
308	10.3k	distance(map->tablelen, map->tablelenbits, bkt, idx) == 0) {
309	10.3k	break;
310	10.3k	}
311
312	0	map->table[didx] = *bkt;
313	0	map_bucket_set_data(bkt, 0, 0, NULL);
314	0	didx = idx;
315
316	0	idx = (idx + 1) & (map->tablelen - 1);
317	0	}
318
319	10.3k	--map->size;
320
321	10.3k	return 0;
322	10.3k	}
323
324	0	++d;
325	0	idx = (idx + 1) & (map->tablelen - 1);
326	0	}
327	10.3k	}
328
329	0	void nghttp2_map_clear(nghttp2_map *map) {
330	0	if (map->tablelen == 0) {
331	0	return;
332	0	}
333
334	0	memset(map->table, 0, sizeof(map->table) map->tablelen);
335	0	map->size = 0;
336	0	}
337
338	96.1k	size_t nghttp2_map_size(nghttp2_map *map) { return map->size; }