Changeset 0db0df2 in mainline for uspace/srv/fs

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/srv/fs

Files:

• cdfs/cdfs_ops.c (modified) (1 diff)
• exfat/exfat_idx.c (modified) (3 diffs)
• fat/fat_idx.c (modified) (3 diffs)
• locfs/locfs_ops.c (modified) (1 diff)
• mfs/mfs_ops.c (modified) (1 diff)
• tmpfs/tmpfs_ops.c (modified) (2 diffs)
• udf/udf_idx.c (modified) (2 diffs)

uspace/srv/fs/cdfs/cdfs_ops.c

@@ -298 +298 @@
 }
 
-static bool nodes_key_equal(const void *k, const ht_link_t *item)
+static bool nodes_key_equal(const void *k, size_t hash, const ht_link_t *item)
 {
         cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link);

uspace/srv/fs/exfat/exfat_idx.c

@@ -37 +37 @@
 
 #include "exfat.h"
-#include "../../vfs/vfs.h"
 #include <errno.h>
 #include <str.h>
@@ -139 +138 @@
 }
 
-static bool pos_key_equal(const void *key, const ht_link_t *item)
+static bool pos_key_equal(const void *key, size_t hash, const ht_link_t *item)
 {
         const pos_key_t *pos = key;
@@ -180 +179 @@
 }
 
-static bool idx_key_equal(const void *key_arg, const ht_link_t *item)
+static bool idx_key_equal(const void *key_arg, size_t hash,
+    const ht_link_t *item)
 {
         exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link);

uspace/srv/fs/fat/fat_idx.c

@@ -37 +37 @@
 
 #include "fat.h"
-#include "../../vfs/vfs.h"
 #include <errno.h>
 #include <str.h>
@@ -139 +138 @@
 }
 
-static bool pos_key_equal(const void *key, const ht_link_t *item)
+static bool pos_key_equal(const void *key, size_t hash, const ht_link_t *item)
 {
         const pos_key_t *pos = key;
@@ -180 +179 @@
 }
 
-static bool idx_key_equal(const void *key_arg, const ht_link_t *item)
+static bool idx_key_equal(const void *key_arg, size_t hash,
+    const ht_link_t *item)
 {
         fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uih_link);

uspace/srv/fs/locfs/locfs_ops.c

@@ -83 +83 @@
 }
 
-static bool services_key_equal(const void *key, const ht_link_t *item)
+static bool services_key_equal(const void *key, size_t hash,
+    const ht_link_t *item)
 {
         const service_id_t *k = key;

uspace/srv/fs/mfs/mfs_ops.c

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

uspace/srv/fs/tmpfs/tmpfs_ops.c

@@ -38 +38 @@
 
 #include "tmpfs.h"
-#include "../../vfs/vfs.h"
 #include <macros.h>
 #include <stdint.h>
@@ -159 +158 @@
 }
 
-static bool nodes_key_equal(const void *key_arg, const ht_link_t *item)
+static bool nodes_key_equal(const void *key_arg, size_t hash,
+    const ht_link_t *item)
 {
         tmpfs_node_t *node = hash_table_get_inst(item, tmpfs_node_t, nh_link);

uspace/srv/fs/udf/udf_idx.c

@@ -35 +35 @@
  */
 
-#include "../../vfs/vfs.h"
 #include <errno.h>
 #include <str.h>
@@ -69 +68 @@
 }
 
-static bool udf_idx_key_equal(const void *k, const ht_link_t *item)
+static bool udf_idx_key_equal(const void *k, size_t hash, const ht_link_t *item)
 {
         const udf_ht_key_t *key = k;