Changeset 0db0df2 in mainline for uspace/lib

Timestamp:

2025-04-07T17:53:53Z (3 months ago)

Author:

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

Branches:

master

Children:

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.

Location:

uspace/lib

Files:

• block/block.c (modified) (1 diff)
• c/generic/async/ports.c (modified) (3 diffs)
• c/generic/async/server.c (modified) (2 diffs)
• ext4/src/ops.c (modified) (1 diff)
• nic/src/nic_addr_db.c (modified) (8 diffs)
• nic/src/nic_wol_virtues.c (modified) (1 diff)

uspace/lib/block/block.c

@@ -254 +254 @@
 }
 
-static bool cache_key_equal(const void *key, const ht_link_t *item)
+static bool cache_key_equal(const void *key, size_t hash, const ht_link_t *item)
 {
         const aoff64_t *lba = key;

uspace/lib/c/generic/async/ports.c

@@ -50 +50 @@
 #include <as.h>
 #include <abi/mm/as.h>
-#include "../private/libc.h"
 #include "../private/fibril.h"
 
@@ -115 +114 @@
 }
 
-static bool interface_key_equal(const void *key, const ht_link_t *item)
+static bool interface_key_equal(const void *key, size_t hash, const ht_link_t *item)
 {
         const iface_t *iface = key;
@@ -143 +142 @@
 }
 
-static bool port_key_equal(const void *key, const ht_link_t *item)
+static bool port_key_equal(const void *key, size_t hash, const ht_link_t *item)
 {
         const port_id_t *port_id = key;

uspace/lib/c/generic/async/server.c

@@ -242 +242 @@
 }
 
-static bool client_key_equal(const void *key, const ht_link_t *item)
+static bool client_key_equal(const void *key, size_t, const ht_link_t *item)
 {
         const task_id_t *in_task_id = key;
@@ -502 +502 @@
 }
 
-static bool notification_key_equal(const void *key, const ht_link_t *item)
+static bool notification_key_equal(const void *key, size_t hash, const ht_link_t *item)
 {
         const sysarg_t *id = key;

uspace/lib/ext4/src/ops.c

@@ -113 +113 @@
 }
 
-static bool open_nodes_key_equal(const void *key_arg, const ht_link_t *item)
+static bool open_nodes_key_equal(const void *key_arg, size_t hash, const ht_link_t *item)
 {
         const node_key_t *key = key_arg;

uspace/lib/nic/src/nic_addr_db.c

@@ -52 +52 @@
 typedef struct nic_addr_entry {
         ht_link_t link;
+        size_t hash;
         uint8_t len;
-        uint8_t addr[1];
+        uint8_t addr[];
 } nic_addr_entry_t;
 
@@ -60 +61 @@
  */
 typedef struct {
+        size_t hash;
         size_t len;
         const uint8_t *addr;
 } addr_key_t;
 
-static bool nic_addr_key_equal(const void *key_arg, const ht_link_t *item)
+static bool nic_addr_key_equal(const void *key_arg, size_t hash, const ht_link_t *item)
 {
         const addr_key_t *key = key_arg;
         nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
-
-        return memcmp(entry->addr, key->addr, entry->len) == 0;
+        return entry->hash == hash && memcmp(entry->addr, key->addr, entry->len) == 0;
 }
 
@@ -86 +87 @@
 {
         const addr_key_t *key = k;
-        return addr_hash(key->len, key->addr);
+        return key->hash ? key->hash : addr_hash(key->len, key->addr);
 }
 
@@ -92 +93 @@
 {
         nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
-        return addr_hash(entry->len, entry->addr);
+        return entry->hash;
 }
 
@@ -98 +99 @@
 {
         nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
-
         free(entry);
 }
@@ -173 +173 @@
         addr_key_t key = {
                 .len = db->addr_len,
-                .addr = addr
+                .addr = addr,
+                .hash = addr_hash(db->addr_len, addr),
         };
 
@@ -179 +180 @@
                 return EEXIST;
 
-        nic_addr_entry_t *entry = malloc(sizeof(nic_addr_entry_t) + db->addr_len - 1);
+        nic_addr_entry_t *entry = malloc(offsetof(nic_addr_entry_t, addr) + db->addr_len);
         if (entry == NULL)
                 return ENOMEM;
@@ -185 +186 @@
         entry->len = (uint8_t) db->addr_len;
         memcpy(entry->addr, addr, db->addr_len);
+        entry->hash = key.hash;
 
         hash_table_insert(&db->set, &entry->link);

uspace/lib/nic/src/nic_wol_virtues.c

@@ -57 +57 @@
 }
 
-static bool nic_wv_key_equal(const void *key, const ht_link_t *item)
+static bool nic_wv_key_equal(const void *key, size_t hash, const ht_link_t *item)
 {
         const nic_wv_id_t *k = key;