/src/CMake/Utilities/cmnghttp2/lib/nghttp2_map.c

Source
/*
 * 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_HASHBITS 4

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

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

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

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

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

  tablelen = 1u << map->hashbits;

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

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

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

  return 0;
}

static size_t map_hash(const nghttp2_map *map, nghttp2_map_key_type key) {
  /* hasher from
     https://github.com/rust-lang/rustc-hash/blob/dc5c33f1283de2da64d8d7a06401d91aded03ad4/src/lib.rs
     We do not perform finalization here because we use top bits
     anyway. */
  uint32_t h = ((uint32_t)key + map->seed) * 0x93d765dd;
  return (size_t)((h * 2654435769u) >> (32 - map->hashbits));
}

static void map_bucket_swap(nghttp2_map_bucket *a, nghttp2_map_bucket *b) {
  nghttp2_map_bucket c = *a;

  *a = *b;
  *b = c;
}

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

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

  tablelen = 1u << map->hashbits;

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

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

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

static int map_insert(nghttp2_map *map, nghttp2_map_key_type key, void *data) {
  size_t idx = map_hash(map, key);
  nghttp2_map_bucket b = {
    .key = key,
    .data = data,
  };
  nghttp2_map_bucket *bkt;
  size_t mask = (1u << map->hashbits) - 1;

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

    if (bkt->data == NULL) {
      *bkt = b;
      ++map->size;
      return 0;
    }

    if (b.psl > bkt->psl) {
      map_bucket_swap(bkt, &b);
    } 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;
    }

    ++b.psl;
    idx = (idx + 1) & mask;
  }
}

static int map_resize(nghttp2_map *map, size_t new_hashbits) {
  size_t i;
  nghttp2_map_bucket *bkt;
  size_t tablelen;
  int rv;
  nghttp2_map new_map = {
    .table = nghttp2_mem_calloc(map->mem, 1u << new_hashbits,
                                sizeof(nghttp2_map_bucket)),
    .mem = map->mem,
    .seed = map->seed,
    .hashbits = new_hashbits,
  };
  (void)rv;

  if (new_map.table == NULL) {
    return NGHTTP2_ERR_NOMEM;
  }

  if (map->size) {
    tablelen = 1u << map->hashbits;

    for (i = 0; i < tablelen; ++i) {
      bkt = &map->table[i];
      if (bkt->data == NULL) {
        continue;
      }

      rv = map_insert(&new_map, bkt->key, bkt->data);

      assert(0 == rv);
    }
  }

  nghttp2_mem_free(map->mem, map->table);
  map->table = new_map.table;
  map->hashbits = new_hashbits;

  return 0;
}

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

  assert(data);

  /* Load factor is 7/8 */
  /* Under the very initial condition, that is map->size == 0 and
     map->hashbits == 0, 8 > 7 still holds nicely. */
  if ((map->size + 1) * 8 > (1u << map->hashbits) * 7) {
    if (map->hashbits) {
      rv = map_resize(map, map->hashbits + 1);
      if (rv != 0) {
        return rv;
      }
    } else {
      rv = map_resize(map, NGHTTP2_INITIAL_HASHBITS);
      if (rv != 0) {
        return rv;
      }
    }
  }

  rv = map_insert(map, key, data);
  if (rv != 0) {
    return rv;
  }

  return 0;
}

void *nghttp2_map_find(const nghttp2_map *map, nghttp2_map_key_type key) {
  size_t idx;
  nghttp2_map_bucket *bkt;
  size_t psl = 0;
  size_t mask;

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

  idx = map_hash(map, key);
  mask = (1u << map->hashbits) - 1;

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

    if (bkt->data == NULL || psl > bkt->psl) {
      return NULL;
    }

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

    ++psl;
    idx = (idx + 1) & mask;
  }
}

int nghttp2_map_remove(nghttp2_map *map, nghttp2_map_key_type key) {
  size_t idx;
  nghttp2_map_bucket *b, *bkt;
  size_t psl = 0;
  size_t mask;

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

  idx = map_hash(map, key);
  mask = (1u << map->hashbits) - 1;

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

    if (bkt->data == NULL || psl > bkt->psl) {
      return NGHTTP2_ERR_INVALID_ARGUMENT;
    }

    if (bkt->key == key) {
      b = bkt;
      idx = (idx + 1) & mask;

      for (;;) {
        bkt = &map->table[idx];
        if (bkt->data == NULL || bkt->psl == 0) {
          b->data = NULL;
          break;
        }

        --bkt->psl;
        *b = *bkt;
        b = bkt;

        idx = (idx + 1) & mask;
      }

      --map->size;

      return 0;
    }

    ++psl;
    idx = (idx + 1) & mask;
  }
}

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

  memset(map->table, 0, sizeof(*map->table) * (1u << map->hashbits));
  map->size = 0;
}

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

Coverage Report

Created: 2026-03-12 06:35

Line	Count	Source
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	0	#define NGHTTP2_INITIAL_HASHBITS 4
35
36	0	void nghttp2_map_init(nghttp2_map map, uint32_t seed, nghttp2_mem mem) {
37	0	map->mem = mem;
38	0	map->hashbits = 0;
39	0	map->table = NULL;
40	0	map->seed = seed;
41	0	map->size = 0;
42	0	}
43
44	0	void nghttp2_map_free(nghttp2_map *map) {
45	0	if (!map) {
46	0	return;
47	0	}
48
49	0	nghttp2_mem_free(map->mem, map->table);
50	0	}
51
52		int nghttp2_map_each(const nghttp2_map map, int (func)(void data, void ptr),
53	0	void *ptr) {
54	0	int rv;
55	0	size_t i;
56	0	nghttp2_map_bucket *bkt;
57	0	size_t tablelen;
58
59	0	if (map->size == 0) {
60	0	return 0;
61	0	}
62
63	0	tablelen = 1u << map->hashbits;
64
65	0	for (i = 0; i < tablelen; ++i) {
66	0	bkt = &map->table[i];
67
68	0	if (bkt->data == NULL) {
69	0	continue;
70	0	}
71
72	0	rv = func(bkt->data, ptr);
73	0	if (rv != 0) {
74	0	return rv;
75	0	}
76	0	}
77
78	0	return 0;
79	0	}
80
81	0	static size_t map_hash(const nghttp2_map *map, nghttp2_map_key_type key) {
82		/* hasher from
83		https://github.com/rust-lang/rustc-hash/blob/dc5c33f1283de2da64d8d7a06401d91aded03ad4/src/lib.rs
84		We do not perform finalization here because we use top bits
85		anyway. */
86	0	uint32_t h = ((uint32_t)key + map->seed) * 0x93d765dd;
87	0	return (size_t)((h * 2654435769u) >> (32 - map->hashbits));
88	0	}
89
90	0	static void map_bucket_swap(nghttp2_map_bucket a, nghttp2_map_bucket b) {
91	0	nghttp2_map_bucket c = *a;
92
93	0	a = b;
94	0	*b = c;
95	0	}
96
97		#ifndef WIN32
98	0	void nghttp2_map_print_distance(const nghttp2_map *map) {
99	0	size_t i;
100	0	size_t idx;
101	0	nghttp2_map_bucket *bkt;
102	0	size_t tablelen;
103
104	0	if (map->size == 0) {
105	0	return;
106	0	}
107
108	0	tablelen = 1u << map->hashbits;
109
110	0	for (i = 0; i < tablelen; ++i) {
111	0	bkt = &map->table[i];
112
113	0	if (bkt->data == NULL) {
114	0	fprintf(stderr, "@%zu <EMPTY>\n", i);
115	0	continue;
116	0	}
117
118	0	idx = map_hash(map, bkt->key);
119	0	fprintf(stderr, "@%zu hash=%zu key=%d base=%zu distance=%u\n", i,
120	0	map_hash(map, bkt->key), bkt->key, idx, bkt->psl);
121	0	}
122	0	}
123		#endif /* !defined(WIN32) */
124
125	0	static int map_insert(nghttp2_map map, nghttp2_map_key_type key, void data) {
126	0	size_t idx = map_hash(map, key);
127	0	nghttp2_map_bucket b = {
128	0	.key = key,
129	0	.data = data,
130	0	};
131	0	nghttp2_map_bucket *bkt;
132	0	size_t mask = (1u << map->hashbits) - 1;
133
134	0	for (;;) {
135	0	bkt = &map->table[idx];
136
137	0	if (bkt->data == NULL) {
138	0	*bkt = b;
139	0	++map->size;
140	0	return 0;
141	0	}
142
143	0	if (b.psl > bkt->psl) {
144	0	map_bucket_swap(bkt, &b);
145	0	} else if (bkt->key == key) {
146		/* TODO This check is just a waste after first swap or if this
147		function is called from map_resize. That said, there is no
148		difference with or without this conditional in performance
149		wise. */
150	0	return NGHTTP2_ERR_INVALID_ARGUMENT;
151	0	}
152
153	0	++b.psl;
154	0	idx = (idx + 1) & mask;
155	0	}
156	0	}
157
158	0	static int map_resize(nghttp2_map *map, size_t new_hashbits) {
159	0	size_t i;
160	0	nghttp2_map_bucket *bkt;
161	0	size_t tablelen;
162	0	int rv;
163	0	nghttp2_map new_map = {
164	0	.table = nghttp2_mem_calloc(map->mem, 1u << new_hashbits,
165	0	sizeof(nghttp2_map_bucket)),
166	0	.mem = map->mem,
167	0	.seed = map->seed,
168	0	.hashbits = new_hashbits,
169	0	};
170	0	(void)rv;
171
172	0	if (new_map.table == NULL) {
173	0	return NGHTTP2_ERR_NOMEM;
174	0	}
175
176	0	if (map->size) {
177	0	tablelen = 1u << map->hashbits;
178
179	0	for (i = 0; i < tablelen; ++i) {
180	0	bkt = &map->table[i];
181	0	if (bkt->data == NULL) {
182	0	continue;
183	0	}
184
185	0	rv = map_insert(&new_map, bkt->key, bkt->data);
186
187	0	assert(0 == rv);
188	0	}
189	0	}
190
191	0	nghttp2_mem_free(map->mem, map->table);
192	0	map->table = new_map.table;
193	0	map->hashbits = new_hashbits;
194
195	0	return 0;
196	0	}
197
198	0	int nghttp2_map_insert(nghttp2_map map, nghttp2_map_key_type key, void data) {
199	0	int rv;
200
201	0	assert(data);
202
203		/* Load factor is 7/8 */
204		/* Under the very initial condition, that is map->size == 0 and
205		map->hashbits == 0, 8 > 7 still holds nicely. */
206	0	if ((map->size + 1) * 8 > (1u << map->hashbits) * 7) {
207	0	if (map->hashbits) {
208	0	rv = map_resize(map, map->hashbits + 1);
209	0	if (rv != 0) {
210	0	return rv;
211	0	}
212	0	} else {
213	0	rv = map_resize(map, NGHTTP2_INITIAL_HASHBITS);
214	0	if (rv != 0) {
215	0	return rv;
216	0	}
217	0	}
218	0	}
219
220	0	rv = map_insert(map, key, data);
221	0	if (rv != 0) {
222	0	return rv;
223	0	}
224
225	0	return 0;
226	0	}
227
228	0	void nghttp2_map_find(const nghttp2_map map, nghttp2_map_key_type key) {
229	0	size_t idx;
230	0	nghttp2_map_bucket *bkt;
231	0	size_t psl = 0;
232	0	size_t mask;
233
234	0	if (map->size == 0) {
235	0	return NULL;
236	0	}
237
238	0	idx = map_hash(map, key);
239	0	mask = (1u << map->hashbits) - 1;
240
241	0	for (;;) {
242	0	bkt = &map->table[idx];
243
244	0	if (bkt->data == NULL \|\| psl > bkt->psl) {
245	0	return NULL;
246	0	}
247
248	0	if (bkt->key == key) {
249	0	return bkt->data;
250	0	}
251
252	0	++psl;
253	0	idx = (idx + 1) & mask;
254	0	}
255	0	}
256
257	0	int nghttp2_map_remove(nghttp2_map *map, nghttp2_map_key_type key) {
258	0	size_t idx;
259	0	nghttp2_map_bucket b, bkt;
260	0	size_t psl = 0;
261	0	size_t mask;
262
263	0	if (map->size == 0) {
264	0	return NGHTTP2_ERR_INVALID_ARGUMENT;
265	0	}
266
267	0	idx = map_hash(map, key);
268	0	mask = (1u << map->hashbits) - 1;
269
270	0	for (;;) {
271	0	bkt = &map->table[idx];
272
273	0	if (bkt->data == NULL \|\| psl > bkt->psl) {
274	0	return NGHTTP2_ERR_INVALID_ARGUMENT;
275	0	}
276
277	0	if (bkt->key == key) {
278	0	b = bkt;
279	0	idx = (idx + 1) & mask;
280
281	0	for (;;) {
282	0	bkt = &map->table[idx];
283	0	if (bkt->data == NULL \|\| bkt->psl == 0) {
284	0	b->data = NULL;
285	0	break;
286	0	}
287
288	0	--bkt->psl;
289	0	b = bkt;
290	0	b = bkt;
291
292	0	idx = (idx + 1) & mask;
293	0	}
294
295	0	--map->size;
296
297	0	return 0;
298	0	}
299
300	0	++psl;
301	0	idx = (idx + 1) & mask;
302	0	}
303	0	}
304
305	0	void nghttp2_map_clear(nghttp2_map *map) {
306	0	if (map->size == 0) {
307	0	return;
308	0	}
309
310	0	memset(map->table, 0, sizeof(map->table) (1u << map->hashbits));
311	0	map->size = 0;
312	0	}
313
314	0	size_t nghttp2_map_size(const nghttp2_map *map) { return map->size; }