← Commit list

7c0c7ca57b

Max Dymond
Max Dymond
2026-09-04
SUCCESS Duration: 421s

Subject

hash: select key operations by type

Binary

No binary (build failed)

Architecture & Compiler Flags

Architecture: x86_64-linux-gnu Compiler: gcc (Ubuntu 11.4.0-1ubuntu1~22.04.3) 11.4.0

—

Build Log

(log yok)

Commit Diff GitHub →

docs/internals/HASH.md +6 -10lib/conncache.c +2 -2lib/easy.c +1 -2lib/hash.c +102 -28lib/hash.h +10 -23lib/multi.c +1 -2lib/multi_ev.c +2 -17lib/url.c +4 -4lib/vdns/dnscache.c +1 -1tests/unit/unit1602.c +1 -2tests/unit/unit1603.c +58 -2
docs/internals/HASH.md+6 -10
@@ -19,8 +19,7 @@ Create a hash table. Add items. Retrieve items. Remove items. Destroy table.
~~~c
void Curl_hash_init(struct Curl_hash *h,
size_t slots,
- hash_function hfunc,
- comp_function comparator,
+ Curl_hash_type type,
Curl_hash_dtor dtor);
~~~
@@ -28,15 +27,12 @@ The call initializes a `struct Curl_hash`.
- `slots` is the number of entries to create in the hash table. Larger is
better (faster lookups) but also uses more memory.
-- `hfunc` is a function pointer to a function that returns a `size_t` value as
- a checksum for an entry in this hash table. Ideally, it returns a unique
- value for every entry ever added to the hash table, but hash collisions are
- handled.
-- `comparator` is a function pointer to a function that compares two hash
- table entries. It should return non-zero if the compared items are
- identical.
+- `type` selects how keys are hashed and compared. `CURL_HASH_TYPE_BYTES`
+ treats keys as exact-length byte sequences. `CURL_HASH_TYPE_SOCKET` treats
+ keys as native `curl_socket_t` values and requires `key_len` to equal
+ `sizeof(curl_socket_t)`.
- `dtor` is a function pointer to a destructor called when an entry is removed
- from the table
+ from the table.
## `Curl_hash_add`
lib/conncache.c+2 -2
@@ -114,8 +114,8 @@ void Curl_cpool_init(struct cpool *cpool,
struct Curl_share *share,
size_t size)
{
- Curl_hash_init(&cpool->dest2bundle, size, Curl_hash_str,
- curlx_str_key_compare, cpool_bundle_free_entry);
+ Curl_hash_init(&cpool->dest2bundle, size, CURL_HASH_TYPE_BYTES,
+ cpool_bundle_free_entry);
cpool->share = share;
cpool->initialized = TRUE;
lib/easy.c+1 -2
@@ -1021,8 +1021,7 @@ CURL *curl_easy_duphandle(CURL *curl)
*/
outcurl->set.buffer_size = data->set.buffer_size;
- Curl_hash_init(&outcurl->meta_hash, 23,
- Curl_hash_str, curlx_str_key_compare,
+ Curl_hash_init(&outcurl->meta_hash, 23, CURL_HASH_TYPE_BYTES,
dupeasy_meta_freeentry);
curlx_dyn_init(&outcurl->state.headerb, CURL_MAX_HTTP_HEADER);
Curl_bufref_init(&outcurl->state.url);
lib/hash.c+102 -28
@@ -23,6 +23,8 @@
***************************************************************************/
#include "curl_setup.h"
+#include <stddef.h> /* for offsetof() */
+
#include "hash.h"
/* random patterns for API verification */
@@ -31,6 +33,80 @@
#define ITERINIT 0x5FEDCBA9
#endif
+typedef size_t (*hash_function)(void *key,
+ size_t key_length,
+ size_t slots_num);
+
+typedef size_t (*comp_function)(void *key1,
+ size_t key1_len,
+ void *key2,
+ size_t key2_len);
+
+/* Curl_hash stores its type in a uint8_t. */
+typedef char hash_types_fit_uint8[
+ ((CURL_HASH_TYPE_LAST - 1) <= UINT8_MAX) ? 1 : -1];
+
+struct hash_functions {
+ hash_function hash;
+ comp_function compare;
+};
+
+/* Avoid treating the variable-length key[1] as a one-byte object. */
+static char *hash_elem_key(struct Curl_hash_element *he)
+{
+ return (char *)he + offsetof(struct Curl_hash_element, key);
+}
+
+static size_t hash_socket(void *key, size_t key_length, size_t slots_num)
+{
+ curl_socket_t socket;
+
+ DEBUGASSERT(key_length == sizeof(socket));
+ if(key_length != sizeof(socket))
+ return 0;
+ memcpy(&socket, key, sizeof(socket));
+ return (size_t)(socket % (curl_socket_t)slots_num);
+}
+
+static size_t compare_socket(void *key1, size_t key1_len,
+ void *key2, size_t key2_len)
+{
+ curl_socket_t socket1;
+ curl_socket_t socket2;
+
+ if((key1_len != sizeof(socket1)) || (key2_len != sizeof(socket2)))
+ return 0;
+ memcpy(&socket1, key1, sizeof(socket1));
+ memcpy(&socket2, key2, sizeof(socket2));
+ return socket1 == socket2;
+}
+
+static size_t compare_bytes(void *key1, size_t key1_len,
+ void *key2, size_t key2_len)
+{
+ return (key1_len == key2_len) && !memcmp(key1, key2, key1_len);
+}
+
+static const struct hash_functions hash_functions[] = {
+ { Curl_hash_str, compare_bytes },
+ { hash_socket, compare_socket }
+};
+
+static const struct hash_functions *hash_get_functions(uint8_t type)
+{
+ DEBUGASSERT(CURL_ARRAYSIZE(hash_functions) == CURL_HASH_TYPE_LAST);
+ if((unsigned int)type >= CURL_HASH_TYPE_LAST)
+ type = CURL_HASH_TYPE_BYTES;
+ return &hash_functions[type];
+}
+
+static bool hash_key_is_valid(uint8_t type, size_t key_len)
+{
+ return (type == CURL_HASH_TYPE_BYTES) ||
+ ((type == CURL_HASH_TYPE_SOCKET) &&
+ (key_len == sizeof(curl_socket_t)));
+}
+
#if 0 /* useful function for debugging hashes and their contents */
void Curl_hash_print(struct Curl_hash *h, void (*func)(void *))
{
@@ -59,7 +135,7 @@ void Curl_hash_print(struct Curl_hash *h, void (*func)(void *))
func(he->ptr);
else
curl_mfprintf(stderr, " [key=%.*s, he=%p, ptr=%p]",
- (int)he->key_len, (char *)he->key,
+ (int)he->key_len, hash_elem_key(he),
(void *)he, (void *)he->ptr);
he = Curl_hash_next_element(&iter);
@@ -69,29 +145,25 @@ void Curl_hash_print(struct Curl_hash *h, void (*func)(void *))
#endif
/* Initializes a hash structure.
- * Return 1 on error, 0 is fine.
*
* @unittest: 1602
* @unittest: 1603
*/
void Curl_hash_init(struct Curl_hash *h,
size_t slots,
- hash_function hfunc,
- comp_function comparator,
+ Curl_hash_type type,
Curl_hash_dtor dtor)
{
DEBUGASSERT(h);
DEBUGASSERT(slots);
- DEBUGASSERT(hfunc);
- DEBUGASSERT(comparator);
+ DEBUGASSERT((unsigned int)type < CURL_HASH_TYPE_LAST);
DEBUGASSERT(dtor);
h->table = NULL;
- h->hash_func = hfunc;
- h->comp_func = comparator;
h->dtor = dtor;
h->size = 0;
h->slots = slots;
+ h->type = (uint8_t)type;
#ifdef DEBUGBUILD
h->init = HASHINIT;
#endif
@@ -109,7 +181,7 @@ static struct Curl_hash_element *hash_elem_create(const void *key,
if(he) {
he->next = NULL;
/* copy the key */
- memcpy(he->key, key, key_len);
+ memcpy(hash_elem_key(he), key, key_len);
he->key_len = key_len;
he->ptr = CURL_UNCONST(p);
he->dtor = dtor;
@@ -124,7 +196,7 @@ static void hash_elem_clear_ptr(struct Curl_hash *h,
DEBUGASSERT(he);
if(he->ptr) {
if(he->dtor)
- he->dtor(he->key, he->key_len, he->ptr);
+ he->dtor(hash_elem_key(he), he->key_len, he->ptr);
else
h->dtor(he->ptr);
he->ptr = NULL;
@@ -155,26 +227,27 @@ static void hash_elem_link(struct Curl_hash *h,
++h->size;
}
-#define CURL_HASH_SLOT(x, y, z) x->table[(x)->hash_func(y, z, (x)->slots)]
-#define CURL_HASH_SLOT_ADDR(x, y, z) &CURL_HASH_SLOT(x, y, z)
-
void *Curl_hash_add2(struct Curl_hash *h, void *key, size_t key_len, void *p,
Curl_hash_elem_dtor dtor)
{
+ const struct hash_functions *functions;
struct Curl_hash_element *he, **slot;
DEBUGASSERT(h);
DEBUGASSERT(h->slots);
DEBUGASSERT(h->init == HASHINIT);
+ if(!hash_key_is_valid(h->type, key_len))
+ return NULL;
if(!h->table) {
h->table = curlx_calloc(h->slots, sizeof(struct Curl_hash_element *));
if(!h->table)
return NULL; /* OOM */
}
- slot = CURL_HASH_SLOT_ADDR(h, key, key_len);
+ functions = hash_get_functions(h->type);
+ slot = &h->table[functions->hash(key, key_len, h->slots)];
for(he = *slot; he; he = he->next) {
- if(h->comp_func(he->key, he->key_len, key, key_len)) {
+ if(functions->compare(hash_elem_key(he), he->key_len, key, key_len)) {
/* existing key entry, overwrite by clearing old pointer */
hash_elem_clear_ptr(h, he);
he->ptr = p;
@@ -211,16 +284,21 @@ void *Curl_hash_add(struct Curl_hash *h, void *key, size_t key_len, void *p)
*/
int Curl_hash_delete(struct Curl_hash *h, void *key, size_t key_len)
{
+ const struct hash_functions *functions;
+
DEBUGASSERT(h);
DEBUGASSERT(h->slots);
DEBUGASSERT(h->init == HASHINIT);
+ if(!hash_key_is_valid(h->type, key_len))
+ return 1;
if(h->table) {
struct Curl_hash_element *he, **he_anchor;
- he_anchor = CURL_HASH_SLOT_ADDR(h, key, key_len);
+ functions = hash_get_functions(h->type);
+ he_anchor = &h->table[functions->hash(key, key_len, h->slots)];
while(*he_anchor) {
he = *he_anchor;
- if(h->comp_func(he->key, he->key_len, key, key_len)) {
+ if(functions->compare(hash_elem_key(he), he->key_len, key, key_len)) {
hash_elem_unlink(h, he_anchor, he);
hash_elem_destroy(h, he);
return 0;
@@ -237,14 +315,19 @@ int Curl_hash_delete(struct Curl_hash *h, void *key, size_t key_len)
*/
void *Curl_hash_pick(struct Curl_hash *h, void *key, size_t key_len)
{
+ const struct hash_functions *functions;
+
DEBUGASSERT(h);
DEBUGASSERT(h->init == HASHINIT);
+ if(!hash_key_is_valid(h->type, key_len))
+ return NULL;
if(h->table) {
struct Curl_hash_element *he;
DEBUGASSERT(h->slots);
- he = CURL_HASH_SLOT(h, key, key_len);
+ functions = hash_get_functions(h->type);
+ he = h->table[functions->hash(key, key_len, h->slots)];
while(he) {
- if(h->comp_func(he->key, he->key_len, key, key_len)) {
+ if(functions->compare(hash_elem_key(he), he->key_len, key, key_len)) {
return he->ptr;
}
he = he->next;
@@ -338,15 +421,6 @@ size_t Curl_hash_str(void *key, size_t key_length, size_t slots_num)
return (h % slots_num);
}
-size_t curlx_str_key_compare(void *k1, size_t key1_len,
- void *k2, size_t key2_len)
-{
- if((key1_len == key2_len) && !memcmp(k1, k2, key1_len))
- return 1;
-
- return 0;
-}
-
void Curl_hash_start_iterate(struct Curl_hash *hash,
struct Curl_hash_iterator *iter)
{
lib/hash.h+10 -23
@@ -25,23 +25,17 @@
***************************************************************************/
#include "curl_setup.h"
-/* Hash function prototype */
-typedef size_t (*hash_function)(void *key,
- size_t key_length,
- size_t slots_num);
-
-/*
- * Comparator function prototype. Compares two keys.
- */
-typedef size_t (*comp_function)(void *key1,
- size_t key1_len,
- void *key2,
- size_t key2_len);
-
typedef void (*Curl_hash_dtor)(void *);
typedef void (*Curl_hash_elem_dtor)(void *key, size_t key_len, void *p);
+/* How keys in a hash are interpreted. */
+typedef enum {
+ CURL_HASH_TYPE_BYTES,
+ CURL_HASH_TYPE_SOCKET,
+ CURL_HASH_TYPE_LAST
+} Curl_hash_type;
+
struct Curl_hash_element {
struct Curl_hash_element *next;
void *ptr;
@@ -52,15 +46,11 @@ struct Curl_hash_element {
struct Curl_hash {
struct Curl_hash_element **table;
-
- /* Hash function to be used for this hash table */
- hash_function hash_func;
- /* Comparator function to compare keys */
- comp_function comp_func;
- /* General element construct, unless element itself carries one */
+ /* General element destructor, unless element itself carries one */
Curl_hash_dtor dtor;
size_t slots;
size_t size;
+ uint8_t type; /* Curl_hash_type */
#ifdef DEBUGBUILD
int init;
#endif
@@ -77,8 +67,7 @@ struct Curl_hash_iterator {
void Curl_hash_init(struct Curl_hash *h,
size_t slots,
- hash_function hfunc,
- comp_function comparator,
+ Curl_hash_type type,
Curl_hash_dtor dtor);
void *Curl_hash_add(struct Curl_hash *h, void *key, size_t key_len, void *p);
@@ -93,8 +82,6 @@ void Curl_hash_clean(struct Curl_hash *h);
void Curl_hash_clean_with_criterium(struct Curl_hash *h, void *user,
int (*comp)(void *, void *));
size_t Curl_hash_str(void *key, size_t key_length, size_t slots_num);
-size_t curlx_str_key_compare(void *k1, size_t key1_len, void *k2,
- size_t key2_len);
void Curl_hash_start_iterate(struct Curl_hash *hash,
struct Curl_hash_iterator *iter);
struct Curl_hash_element *Curl_hash_next_element(
lib/multi.c+1 -2
@@ -259,8 +259,7 @@ struct Curl_multi *Curl_multi_handle(uint32_t xfer_table_size,
Curl_uint32_bset_init(&multi->dirty);
Curl_uint32_bset_init(&multi->pending);
Curl_uint32_bset_init(&multi->msgsent);
- Curl_hash_init(&multi->proto_hash, 23,
- Curl_hash_str, curlx_str_key_compare, ph_freeentry);
+ Curl_hash_init(&multi->proto_hash, 23, CURL_HASH_TYPE_BYTES, ph_freeentry);
multi->multiplexing = TRUE;
multi->max_concurrent_streams = 100;
lib/multi_ev.c+2 -17
@@ -56,21 +56,6 @@ struct mev_sh_entry {
callback at least once */
};
-static size_t mev_sh_entry_hash(void *key, size_t key_length, size_t slots_num)
-{
- curl_socket_t fd = *((curl_socket_t *)key);
- (void)key_length;
- return (fd % (curl_socket_t)slots_num);
-}
-
-static size_t mev_sh_entry_compare(void *k1, size_t k1_len,
- void *k2, size_t k2_len)
-{
- (void)k1_len;
- (void)k2_len;
- return (*((curl_socket_t *)k1)) == (*((curl_socket_t *)k2));
-}
-
/* sockhash entry destructor callback */
static void mev_sh_entry_dtor(void *freethis)
{
@@ -637,8 +622,8 @@ void Curl_multi_ev_conn_done(struct Curl_multi *multi,
void Curl_multi_ev_init(struct Curl_multi *multi, size_t hashsize)
{
- Curl_hash_init(&multi->ev.sh_entries, hashsize, mev_sh_entry_hash,
- mev_sh_entry_compare, mev_sh_entry_dtor);
+ Curl_hash_init(&multi->ev.sh_entries, hashsize, CURL_HASH_TYPE_SOCKET,
+ mev_sh_entry_dtor);
}
void Curl_multi_ev_cleanup(struct Curl_multi *multi)
lib/url.c+4 -4
@@ -470,8 +470,8 @@ CURLcode Curl_open(struct Curl_easy **curl)
data->master_mid = UINT32_MAX;
data->progress.hide = TRUE;
- Curl_hash_init(&data->meta_hash, 23,
- Curl_hash_str, curlx_str_key_compare, easy_meta_freeentry);
+ Curl_hash_init(&data->meta_hash, 23, CURL_HASH_TYPE_BYTES,
+ easy_meta_freeentry);
DEBUGASSERT(STRING_LAST <= UINT8_MAX);
Curl_u8_strset_init(&data->set.strings);
curlx_dyn_init(&data->state.headerb, CURL_MAX_HTTP_HEADER);
@@ -2016,8 +2016,8 @@ static CURLcode url_create_needle(struct Curl_easy *data,
}
/* Do the unfailable inits first, before checks that may early return */
- Curl_hash_init(&needle->meta_hash, 23,
- Curl_hash_str, curlx_str_key_compare, conn_meta_freeentry);
+ Curl_hash_init(&needle->meta_hash, 23, CURL_HASH_TYPE_BYTES,
+ conn_meta_freeentry);
/*************************************************************
* Determine `conn->origin` and populate `data->state.up` and
lib/vdns/dnscache.c+1 -1
@@ -807,7 +807,7 @@ static void dnscache_entry_dtor(void *entry)
*/
void Curl_dnscache_init(struct Curl_dnscache *dns, size_t size)
{
- Curl_hash_init(&dns->entries, size, Curl_hash_str, curlx_str_key_compare,
+ Curl_hash_init(&dns->entries, size, CURL_HASH_TYPE_BYTES,
dnscache_entry_dtor);
}
tests/unit/unit1602.c+1 -2
@@ -32,8 +32,7 @@ static void t1602_mydtor(void *p)
static CURLcode t1602_setup(struct Curl_hash *hash)
{
- Curl_hash_init(hash, 7, Curl_hash_str,
- curlx_str_key_compare, t1602_mydtor);
+ Curl_hash_init(hash, 7, CURL_HASH_TYPE_BYTES, t1602_mydtor);
return CURLE_OK;
}
tests/unit/unit1603.c+58 -2
@@ -44,8 +44,7 @@ static void my_elem_dtor(void *key, size_t key_len, void *p)
static CURLcode t1603_setup(struct Curl_hash *hash_static)
{
- Curl_hash_init(hash_static, slots, Curl_hash_str,
- curlx_str_key_compare, t1603_mydtor);
+ Curl_hash_init(hash_static, slots, CURL_HASH_TYPE_BYTES, t1603_mydtor);
return CURLE_OK;
}
@@ -54,6 +53,61 @@ static void t1603_stop(struct Curl_hash *hash_static)
Curl_hash_destroy(hash_static);
}
+static void t1603_test_socket_type(void)
+{
+ struct Curl_hash hash;
+ curl_socket_t key = 1;
+ curl_socket_t collision = (curl_socket_t)(slots + 1);
+ int value = 1;
+ int collision_value = 2;
+ int replacement_value = 3;
+#if SIZEOF_CURL_SOCKET_T > 4
+ curl_socket_t high_key = ((curl_socket_t)1 << 32) + 1;
+ int high_value = 4;
+#endif
+
+ Curl_hash_init(&hash, slots, CURL_HASH_TYPE_SOCKET, t1603_mydtor);
+ fail_unless(!Curl_hash_add(&hash, &key, sizeof(key) - 1, &value),
+ "invalid socket key length was accepted");
+ fail_unless(!hash.table, "invalid socket key allocated a hash table");
+ fail_unless(!Curl_hash_pick(&hash, &key, sizeof(key) - 1),
+ "invalid socket key lookup succeeded");
+ fail_unless(Curl_hash_delete(&hash, &key, sizeof(key) - 1),
+ "invalid socket key deletion succeeded");
+ fail_unless(Curl_hash_add(&hash, &key, sizeof(key), &value) == &value,
+ "socket key insertion failed");
+ fail_unless(hash.table && hash.table[1],
+ "socket key used the wrong hash slot");
+ fail_unless(Curl_hash_add(&hash, &key, sizeof(key), &replacement_value) ==
+ &replacement_value, "socket key replacement failed");
+ fail_unless(Curl_hash_count(&hash) == 1,
+ "socket key replacement changed the hash count");
+ fail_unless(Curl_hash_pick(&hash, &key, sizeof(key)) == &replacement_value,
+ "socket key replacement lookup failed");
+ fail_unless(Curl_hash_add(&hash, &collision, sizeof(collision),
+ &collision_value) == &collision_value,
+ "colliding socket key insertion failed");
+ fail_unless(Curl_hash_count(&hash) == 2, "wrong socket hash count");
+ fail_unless(Curl_hash_pick(&hash, &collision, sizeof(collision)) ==
+ &collision_value, "colliding socket key lookup failed");
+#if SIZEOF_CURL_SOCKET_T > 4
+ fail_unless(Curl_hash_add(&hash, &high_key, sizeof(high_key), &high_value) ==
+ &high_value, "wide socket key insertion failed");
+ fail_unless(hash.table && hash.table[2],
+ "wide socket key used the wrong hash slot");
+ fail_unless(Curl_hash_count(&hash) == 3, "wrong wide socket hash count");
+ fail_unless(Curl_hash_pick(&hash, &high_key, sizeof(high_key)) ==
+ &high_value, "wide socket key lookup failed");
+#endif
+ fail_unless(!Curl_hash_delete(&hash, &key, sizeof(key)),
+ "socket key deletion failed");
+ fail_unless(!Curl_hash_pick(&hash, &key, sizeof(key)),
+ "deleted socket key was found");
+ fail_unless(Curl_hash_pick(&hash, &collision, sizeof(collision)) ==
+ &collision_value, "collision was lost after deletion");
+ Curl_hash_destroy(&hash);
+}
+
static CURLcode test_unit1603(const char *arg)
{
struct Curl_hash hash_static;
@@ -174,5 +228,7 @@ static CURLcode test_unit1603(const char *arg)
/* Clean up */
Curl_hash_clean(&hash_static);
+ t1603_test_socket_type();
+
UNITTEST_END(t1603_stop(&hash_static))
}