Changeset 0db0df2 in mainline for uspace/app/hbench/env.c

Timestamp:

2025-04-07T17:53:53Z (11 days ago)

Author:

Jiří Zárevúcky <zarevucky.jiri@…>

Branches:

master

Children:

0c6fc7a, 45226285, 93de384

Parents:

8f8818ac

git-author:

Jiří Zárevúcky <zarevucky.jiri@…> (2025-04-07 16:41:57)

git-committer:

Jiří Zárevúcky <zarevucky.jiri@…> (2025-04-07 17:53:53)

Message:

Hash table improvements

Implement hash_table_foreach macro, analogous to list_foreach.

Remove superfluous argument to hash_table_find_next().
(If the user needs to recheck the part of the list already
checked by hash_table_find(), they can just rerun that function.)

Add hash argument to hash_table_ops_t::key_equal.
The big change here is that users with big keys can store the hash
value alongside key in their entries, and for the low low cost of
sizeof(size_t) bytes eliminate a bunch of expensive key comparisons.

Also added a hash function for strings and arbitrary data.
Found this one by asking ChatGPT, because the latency of accesses
to my book collection is currently a couple of hours.

+ Some drive-by unused #include removal.

File:

• uspace/app/hbench/env.c (modified) (6 diffs)

uspace/app/hbench/env.c

@@ -34 +34 @@
  */
 
+#include <adt/hash.h>
 #include <stdlib.h>
 #include <stdio.h>
@@ -42 +43 @@
         ht_link_t link;
 
+        size_t hash;
         char *key;
         char *value;
@@ -49 +51 @@
 {
         param_t *param = hash_table_get_inst(item, param_t, link);
-        return str_size(param->key);
+        return param->hash;
 }
 
 static size_t param_key_hash(const void *key)
 {
-        const char *key_str = key;
-        return str_size(key_str);
+        return hash_string(key);
 }
 
-static bool param_key_equal(const void *key, const ht_link_t *item)
+static bool param_key_equal(const void *key, size_t hash, const ht_link_t *item)
 {
         param_t *param = hash_table_get_inst(item, param_t, link);
+
+        if (param->hash != hash)
+                return false;
+
         const char *key_str = key;
-
         return str_cmp(param->key, key_str) == 0;
 }
@@ -71 +75 @@
         param_t *b = hash_table_get_inst(link_b, param_t, link);
 
-        return str_cmp(a->key, b->key) == 0;
+        return a->hash == b->hash && str_cmp(a->key, b->key) == 0;
 }
 
@@ -116 +120 @@
         param->key = str_dup(key);
         param->value = str_dup(value);
+        param->hash = hash_string(key);
 
         if ((param->key == NULL) || (param->value == NULL)) {
@@ -132 +137 @@
 const char *bench_env_param_get(bench_env_t *env, const char *key, const char *default_value)
 {
-        ht_link_t *item = hash_table_find(&env->parameters, (char *) key);
+        ht_link_t *item = hash_table_find(&env->parameters, key);
 
         if (item == NULL) {