/src/nghttp2/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, uint64_t seed, nghttp2_mem *mem) {
  *map = (nghttp2_map){
    .mem = mem,
    .seed = seed,
  };
}

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

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

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

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

  tablelen = (size_t)1 << map->hashbits;

  for (i = 0; i < tablelen; ++i) {
    if (map->psl[i] == 0) {
      continue;
    }

    rv = func(map->data[i], ptr);
    if (rv != 0) {
      return rv;
    }
  }

  return 0;
}

/* Hasher from
   https://github.com/rust-lang/rustc-hash/blob/dc5c33f1283de2da64d8d7a06401d91aded03ad4/src/lib.rs
   to maximize the output's sensitivity to all input bits. */
#define NGHTTP2_MAP_HASHER 0xf1357aea2e62a9c5ull
/* 64-bit Fibonacci hashing constant, Golden Ratio constant, to get
   the high bits with the good distribution. */
#define NGHTTP2_MAP_FIBO 0x9e3779b97f4a7c15ull

static size_t map_index(const nghttp2_map *map, nghttp2_map_key_type key32) {
  uint64_t key = (uint64_t)key32;

  key += map->seed;
  key *= NGHTTP2_MAP_HASHER;
  return (size_t)((key * NGHTTP2_MAP_FIBO) >> (64 - map->hashbits));
}

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

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

  tablelen = (size_t)1 << map->hashbits;

  for (i = 0; i < tablelen; ++i) {
    if (map->psl[i] == 0) {
      fprintf(stderr, "@%zu <EMPTY>\n", i);
      continue;
    }

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

static void map_set_entry(nghttp2_map *map, size_t idx,
                          nghttp2_map_key_type key, void *data, size_t psl) {
  map->keys[idx] = key;
  map->data[idx] = data;
  map->psl[idx] = (uint8_t)psl;
}

#define NGHTTP2_SWAP(TYPE, A, B)                                               \
  do {                                                                         \
    TYPE t = (TYPE) * (A);                                                     \
                                                                               \
    *(A) = *(B);                                                               \
    *(B) = t;                                                                  \
  } while (0)

/*
 * map_insert inserts |key| and |data| to |map|, and returns the index
 * where the pair is stored if it succeeds.  Otherwise, it returns one
 * of the following negative error codes:
 *
 * NGHTTP2_ERR_INVALID_ARGUMENT
 *     The another data associated to |key| is already present.
 */
static nghttp2_ssize map_insert(nghttp2_map *map, nghttp2_map_key_type key,
                                void *data) {
  size_t idx = map_index(map, key);
  size_t mask = ((size_t)1 << map->hashbits) - 1;
  size_t psl = 1;
  size_t kpsl;

  for (;;) {
    kpsl = map->psl[idx];

    if (kpsl == 0) {
      map_set_entry(map, idx, key, data, psl);
      ++map->size;

      return (nghttp2_ssize)idx;
    }

    if (psl > kpsl) {
      NGHTTP2_SWAP(nghttp2_map_key_type, &key, &map->keys[idx]);
      NGHTTP2_SWAP(void *, &data, &map->data[idx]);
      NGHTTP2_SWAP(uint8_t, &psl, &map->psl[idx]);
    } else if (map->keys[idx] == key) {
      /* This check ensures that no duplicate keys are inserted.  But
         it 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;
    }

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

/* NGHTTP2_MAP_MAX_HASHBITS is the maximum number of bits used for
   hash table.  The theoretical limit of the maximum number of keys
   that can be stored is 1 << NGHTTP2_MAP_MAX_HASHBITS. */
#define NGHTTP2_MAP_MAX_HASHBITS (sizeof(size_t) * 8 - 1)

static int map_resize(nghttp2_map *map, size_t new_hashbits) {
  size_t i;
  size_t tablelen;
  nghttp2_ssize idx;
  nghttp2_map new_map = {
    .mem = map->mem,
    .seed = map->seed,
    .hashbits = new_hashbits,
  };
  void *buf;
  (void)idx;

  if (new_hashbits > NGHTTP2_MAP_MAX_HASHBITS) {
    return NGHTTP2_ERR_NOMEM;
  }

  tablelen = (size_t)1 << new_hashbits;

  buf = nghttp2_mem_calloc(map->mem, tablelen,
                           sizeof(nghttp2_map_key_type) + sizeof(void *) +
                             sizeof(uint8_t));
  if (buf == NULL) {
    return NGHTTP2_ERR_NOMEM;
  }

  new_map.keys = buf;
  new_map.data =
    (void *)((uint8_t *)new_map.keys + tablelen * sizeof(nghttp2_map_key_type));
  new_map.psl = (uint8_t *)new_map.data + tablelen * sizeof(void *);

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

    for (i = 0; i < tablelen; ++i) {
      if (map->psl[i] == 0) {
        continue;
      }

      idx = map_insert(&new_map, map->keys[i], map->data[i]);

      /* map_insert must not fail because all keys are unique during
         resize. */
      assert(idx >= 0);
    }
  }

  nghttp2_mem_free(map->mem, map->keys);
  map->keys = new_map.keys;
  map->data = new_map.data;
  map->psl = new_map.psl;
  map->hashbits = new_hashbits;

  return 0;
}

/* NGHTTP2_MAX_PSL_RESIZE_THRESH is the maximum psl threshold.  If
   reached, resize the table. */
#define NGHTTP2_MAX_PSL_RESIZE_THRESH 128

int nghttp2_map_insert(nghttp2_map *map, nghttp2_map_key_type key, void *data) {
  int rv;
  size_t tablelen;
  nghttp2_ssize idx;

  assert(data);

  /* tablelen is incorrect if map->hashbits == 0 which leads to
     tablelen = 1, but it is only used to check the load factor, and
     it works in this special case. */
  tablelen = (size_t)1 << map->hashbits;

  /* Load factor is 7 / 8.  Because tablelen is power of 2, (tablelen
     - (tablelen >> 3)) computes tablelen * 7 / 8. */
  if (map->size + 1 >= (tablelen - (tablelen >> 3))) {
    rv = map_resize(map, map->hashbits ? map->hashbits + 1
                                       : NGHTTP2_INITIAL_HASHBITS);
    if (rv != 0) {
      return rv;
    }

    idx = map_insert(map, key, data);
    if (idx < 0) {
      return (int)idx;
    }

    return 0;
  }

  idx = map_insert(map, key, data);
  if (idx < 0) {
    return (int)idx;
  }

  /* Resize if psl reaches really large value which is almost
     improbable, but just in case. */
  if (map->psl[idx] - 1 < NGHTTP2_MAX_PSL_RESIZE_THRESH) {
    return 0;
  }

  return map_resize(map, map->hashbits + 1);
}

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

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

  idx = map_index(map, key);
  mask = ((size_t)1 << map->hashbits) - 1;

  for (;;) {
    if (psl > map->psl[idx]) {
      return NULL;
    }

    if (map->keys[idx] == key) {
      return map->data[idx];
    }

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

int nghttp2_map_remove(nghttp2_map *map, nghttp2_map_key_type key) {
  size_t idx;
  size_t dest;
  size_t psl = 1, kpsl;
  size_t mask;

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

  idx = map_index(map, key);
  mask = ((size_t)1 << map->hashbits) - 1;

  for (;;) {
    if (psl > map->psl[idx]) {
      return NGHTTP2_ERR_INVALID_ARGUMENT;
    }

    if (map->keys[idx] == key) {
      dest = idx;
      idx = (idx + 1) & mask;

      for (;;) {
        kpsl = map->psl[idx];
        if (kpsl <= 1) {
          map->psl[dest] = 0;
          break;
        }

        map_set_entry(map, dest, map->keys[idx], map->data[idx], kpsl - 1);

        dest = idx;

        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->psl, 0, sizeof(*map->psl) * ((size_t)1 << map->hashbits));
  map->size = 0;
}

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

Coverage Report

Created: 2025-12-11 07:13

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, uint64_t seed, nghttp2_mem mem) {
37	0	*map = (nghttp2_map){
38	0	.mem = mem,
39	0	.seed = seed,
40	0	};
41	0	}
42
43	0	void nghttp2_map_free(nghttp2_map *map) {
44	0	if (!map) {
45	0	return;
46	0	}
47
48	0	nghttp2_mem_free(map->mem, map->keys);
49	0	}
50
51		int nghttp2_map_each(const nghttp2_map map, int (func)(void data, void ptr),
52	0	void *ptr) {
53	0	int rv;
54	0	size_t i;
55	0	size_t tablelen;
56
57	0	if (map->size == 0) {
58	0	return 0;
59	0	}
60
61	0	tablelen = (size_t)1 << map->hashbits;
62
63	0	for (i = 0; i < tablelen; ++i) {
64	0	if (map->psl[i] == 0) {
65	0	continue;
66	0	}
67
68	0	rv = func(map->data[i], ptr);
69	0	if (rv != 0) {
70	0	return rv;
71	0	}
72	0	}
73
74	0	return 0;
75	0	}
76
77		/* Hasher from
78		https://github.com/rust-lang/rustc-hash/blob/dc5c33f1283de2da64d8d7a06401d91aded03ad4/src/lib.rs
79		to maximize the output's sensitivity to all input bits. */
80	0	#define NGHTTP2_MAP_HASHER 0xf1357aea2e62a9c5ull
81		/* 64-bit Fibonacci hashing constant, Golden Ratio constant, to get
82		the high bits with the good distribution. */
83	0	#define NGHTTP2_MAP_FIBO 0x9e3779b97f4a7c15ull
84
85	0	static size_t map_index(const nghttp2_map *map, nghttp2_map_key_type key32) {
86	0	uint64_t key = (uint64_t)key32;
87
88	0	key += map->seed;
89	0	key *= NGHTTP2_MAP_HASHER;
90	0	return (size_t)((key * NGHTTP2_MAP_FIBO) >> (64 - map->hashbits));
91	0	}
92
93		#ifndef WIN32
94	0	void nghttp2_map_print_distance(const nghttp2_map *map) {
95	0	size_t i;
96	0	size_t idx;
97	0	size_t tablelen;
98
99	0	if (map->size == 0) {
100	0	return;
101	0	}
102
103	0	tablelen = (size_t)1 << map->hashbits;
104
105	0	for (i = 0; i < tablelen; ++i) {
106	0	if (map->psl[i] == 0) {
107	0	fprintf(stderr, "@%zu <EMPTY>\n", i);
108	0	continue;
109	0	}
110
111	0	idx = map_index(map, map->keys[i]);
112	0	fprintf(stderr, "@%zu key=%d base=%zu distance=%u\n", i, map->keys[i], idx,
113	0	map->psl[i] - 1);
114	0	}
115	0	}
116		#endif /* !defined(WIN32) */
117
118		static void map_set_entry(nghttp2_map *map, size_t idx,
119	0	nghttp2_map_key_type key, void *data, size_t psl) {
120	0	map->keys[idx] = key;
121	0	map->data[idx] = data;
122	0	map->psl[idx] = (uint8_t)psl;
123	0	}
124
125		#define NGHTTP2_SWAP(TYPE, A, B) \
126	0	do { \
127	0	TYPE t = (TYPE) * (A); \
128	0	\
129	0	(A) = (B); \
130	0	*(B) = t; \
131	0	} while (0)
132
133		/*
134		* map_insert inserts \|key\| and \|data\| to \|map\|, and returns the index
135		* where the pair is stored if it succeeds. Otherwise, it returns one
136		* of the following negative error codes:
137		*
138		* NGHTTP2_ERR_INVALID_ARGUMENT
139		* The another data associated to \|key\| is already present.
140		*/
141		static nghttp2_ssize map_insert(nghttp2_map *map, nghttp2_map_key_type key,
142	0	void *data) {
143	0	size_t idx = map_index(map, key);
144	0	size_t mask = ((size_t)1 << map->hashbits) - 1;
145	0	size_t psl = 1;
146	0	size_t kpsl;
147
148	0	for (;;) {
149	0	kpsl = map->psl[idx];
150
151	0	if (kpsl == 0) {
152	0	map_set_entry(map, idx, key, data, psl);
153	0	++map->size;
154
155	0	return (nghttp2_ssize)idx;
156	0	}
157
158	0	if (psl > kpsl) {
159	0	NGHTTP2_SWAP(nghttp2_map_key_type, &key, &map->keys[idx]);
160	0	NGHTTP2_SWAP(void *, &data, &map->data[idx]);
161	0	NGHTTP2_SWAP(uint8_t, &psl, &map->psl[idx]);
162	0	} else if (map->keys[idx] == key) {
163		/* This check ensures that no duplicate keys are inserted. But
164		it is just a waste after first swap or if this function is
165		called from map_resize. That said, there is no difference
166		with or without this conditional in performance wise. */
167	0	return NGHTTP2_ERR_INVALID_ARGUMENT;
168	0	}
169
170	0	++psl;
171	0	idx = (idx + 1) & mask;
172	0	}
173	0	}
174
175		/* NGHTTP2_MAP_MAX_HASHBITS is the maximum number of bits used for
176		hash table. The theoretical limit of the maximum number of keys
177		that can be stored is 1 << NGHTTP2_MAP_MAX_HASHBITS. */
178	0	#define NGHTTP2_MAP_MAX_HASHBITS (sizeof(size_t) * 8 - 1)
179
180	0	static int map_resize(nghttp2_map *map, size_t new_hashbits) {
181	0	size_t i;
182	0	size_t tablelen;
183	0	nghttp2_ssize idx;
184	0	nghttp2_map new_map = {
185	0	.mem = map->mem,
186	0	.seed = map->seed,
187	0	.hashbits = new_hashbits,
188	0	};
189	0	void *buf;
190	0	(void)idx;
191
192	0	if (new_hashbits > NGHTTP2_MAP_MAX_HASHBITS) {
193	0	return NGHTTP2_ERR_NOMEM;
194	0	}
195
196	0	tablelen = (size_t)1 << new_hashbits;
197
198	0	buf = nghttp2_mem_calloc(map->mem, tablelen,
199	0	sizeof(nghttp2_map_key_type) + sizeof(void *) +
200	0	sizeof(uint8_t));
201	0	if (buf == NULL) {
202	0	return NGHTTP2_ERR_NOMEM;
203	0	}
204
205	0	new_map.keys = buf;
206	0	new_map.data =
207	0	(void )((uint8_t )new_map.keys + tablelen * sizeof(nghttp2_map_key_type));
208	0	new_map.psl = (uint8_t )new_map.data + tablelen sizeof(void *);
209
210	0	if (map->size) {
211	0	tablelen = (size_t)1 << map->hashbits;
212
213	0	for (i = 0; i < tablelen; ++i) {
214	0	if (map->psl[i] == 0) {
215	0	continue;
216	0	}
217
218	0	idx = map_insert(&new_map, map->keys[i], map->data[i]);
219
220		/* map_insert must not fail because all keys are unique during
221		resize. */
222	0	assert(idx >= 0);
223	0	}
224	0	}
225
226	0	nghttp2_mem_free(map->mem, map->keys);
227	0	map->keys = new_map.keys;
228	0	map->data = new_map.data;
229	0	map->psl = new_map.psl;
230	0	map->hashbits = new_hashbits;
231
232	0	return 0;
233	0	}
234
235		/* NGHTTP2_MAX_PSL_RESIZE_THRESH is the maximum psl threshold. If
236		reached, resize the table. */
237	0	#define NGHTTP2_MAX_PSL_RESIZE_THRESH 128
238
239	0	int nghttp2_map_insert(nghttp2_map map, nghttp2_map_key_type key, void data) {
240	0	int rv;
241	0	size_t tablelen;
242	0	nghttp2_ssize idx;
243
244	0	assert(data);
245
246		/* tablelen is incorrect if map->hashbits == 0 which leads to
247		tablelen = 1, but it is only used to check the load factor, and
248		it works in this special case. */
249	0	tablelen = (size_t)1 << map->hashbits;
250
251		/* Load factor is 7 / 8. Because tablelen is power of 2, (tablelen
252		- (tablelen >> 3)) computes tablelen * 7 / 8. */
253	0	if (map->size + 1 >= (tablelen - (tablelen >> 3))) {
254	0	rv = map_resize(map, map->hashbits ? map->hashbits + 1
255	0	: NGHTTP2_INITIAL_HASHBITS);
256	0	if (rv != 0) {
257	0	return rv;
258	0	}
259
260	0	idx = map_insert(map, key, data);
261	0	if (idx < 0) {
262	0	return (int)idx;
263	0	}
264
265	0	return 0;
266	0	}
267
268	0	idx = map_insert(map, key, data);
269	0	if (idx < 0) {
270	0	return (int)idx;
271	0	}
272
273		/* Resize if psl reaches really large value which is almost
274		improbable, but just in case. */
275	0	if (map->psl[idx] - 1 < NGHTTP2_MAX_PSL_RESIZE_THRESH) {
276	0	return 0;
277	0	}
278
279	0	return map_resize(map, map->hashbits + 1);
280	0	}
281
282	0	void nghttp2_map_find(const nghttp2_map map, nghttp2_map_key_type key) {
283	0	size_t idx;
284	0	size_t psl = 1;
285	0	size_t mask;
286
287	0	if (map->size == 0) {
288	0	return NULL;
289	0	}
290
291	0	idx = map_index(map, key);
292	0	mask = ((size_t)1 << map->hashbits) - 1;
293
294	0	for (;;) {
295	0	if (psl > map->psl[idx]) {
296	0	return NULL;
297	0	}
298
299	0	if (map->keys[idx] == key) {
300	0	return map->data[idx];
301	0	}
302
303	0	++psl;
304	0	idx = (idx + 1) & mask;
305	0	}
306	0	}
307
308	0	int nghttp2_map_remove(nghttp2_map *map, nghttp2_map_key_type key) {
309	0	size_t idx;
310	0	size_t dest;
311	0	size_t psl = 1, kpsl;
312	0	size_t mask;
313
314	0	if (map->size == 0) {
315	0	return NGHTTP2_ERR_INVALID_ARGUMENT;
316	0	}
317
318	0	idx = map_index(map, key);
319	0	mask = ((size_t)1 << map->hashbits) - 1;
320
321	0	for (;;) {
322	0	if (psl > map->psl[idx]) {
323	0	return NGHTTP2_ERR_INVALID_ARGUMENT;
324	0	}
325
326	0	if (map->keys[idx] == key) {
327	0	dest = idx;
328	0	idx = (idx + 1) & mask;
329
330	0	for (;;) {
331	0	kpsl = map->psl[idx];
332	0	if (kpsl <= 1) {
333	0	map->psl[dest] = 0;
334	0	break;
335	0	}
336
337	0	map_set_entry(map, dest, map->keys[idx], map->data[idx], kpsl - 1);
338
339	0	dest = idx;
340
341	0	idx = (idx + 1) & mask;
342	0	}
343
344	0	--map->size;
345
346	0	return 0;
347	0	}
348
349	0	++psl;
350	0	idx = (idx + 1) & mask;
351	0	}
352	0	}
353
354	0	void nghttp2_map_clear(nghttp2_map *map) {
355	0	if (map->size == 0) {
356	0	return;
357	0	}
358
359	0	memset(map->psl, 0, sizeof(map->psl) ((size_t)1 << map->hashbits));
360	0	map->size = 0;
361	0	}
362
363	0	size_t nghttp2_map_size(const nghttp2_map *map) { return map->size; }