Changeset 0db0df2 in mainline for uspace/srv


Ignore:
Timestamp:
2025-04-07T17:53:53Z (11 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
Files:
12 edited

Legend:

Unmodified
Added
Removed

  • uspace/srv/devman/devtree.c

    r8f8818ac r0db0df2  
    3232 */
    3333
    34 #include <errno.h>
    3534#include <io/log.h>
    3635
    … …  
    6160}
    6261
    63 static bool devman_devices_key_equal(const void *key, const ht_link_t *item)
     62static bool devman_devices_key_equal(const void *key, size_t hash, const ht_link_t *item)
    6463{
    6564        const devman_handle_t *handle = key;
    … …  
    6867}
    6968
    70 static bool devman_functions_key_equal(const void *key, const ht_link_t *item)
     69static bool devman_functions_key_equal(const void *key, size_t hash, const ht_link_t *item)
    7170{
    7271        const devman_handle_t *handle = key;
    … …  
    8786}
    8887
    89 static bool loc_functions_key_equal(const void *key, const ht_link_t *item)
     88static bool loc_functions_key_equal(const void *key, size_t hash, const ht_link_t *item)
    9089{
    9190        const service_id_t *service_id = key;

  • uspace/srv/fs/cdfs/cdfs_ops.c

    r8f8818ac r0db0df2  
    298298}
    299299
    300 static bool nodes_key_equal(const void *k, const ht_link_t *item)
     300static bool nodes_key_equal(const void *k, size_t hash, const ht_link_t *item)
    301301{
    302302        cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link);

  • uspace/srv/fs/exfat/exfat_idx.c

    r8f8818ac r0db0df2  
    3737
    3838#include "exfat.h"
    39 #include "../../vfs/vfs.h"
    4039#include <errno.h>
    4140#include <str.h>
    … …  
    139138}
    140139
    141 static bool pos_key_equal(const void *key, const ht_link_t *item)
     140static bool pos_key_equal(const void *key, size_t hash, const ht_link_t *item)
    142141{
    143142        const pos_key_t *pos = key;
    … …  
    180179}
    181180
    182 static bool idx_key_equal(const void *key_arg, const ht_link_t *item)
     181static bool idx_key_equal(const void *key_arg, size_t hash,
     182    const ht_link_t *item)
    183183{
    184184        exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link);

  • uspace/srv/fs/fat/fat_idx.c

    r8f8818ac r0db0df2  
    3737
    3838#include "fat.h"
    39 #include "../../vfs/vfs.h"
    4039#include <errno.h>
    4140#include <str.h>
    … …  
    139138}
    140139
    141 static bool pos_key_equal(const void *key, const ht_link_t *item)
     140static bool pos_key_equal(const void *key, size_t hash, const ht_link_t *item)
    142141{
    143142        const pos_key_t *pos = key;
    … …  
    180179}
    181180
    182 static bool idx_key_equal(const void *key_arg, const ht_link_t *item)
     181static bool idx_key_equal(const void *key_arg, size_t hash,
     182    const ht_link_t *item)
    183183{
    184184        fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uih_link);

  • uspace/srv/fs/locfs/locfs_ops.c

    r8f8818ac r0db0df2  
    8383}
    8484
    85 static bool services_key_equal(const void *key, const ht_link_t *item)
     85static bool services_key_equal(const void *key, size_t hash,
     86    const ht_link_t *item)
    8687{
    8788        const service_id_t *k = key;

  • uspace/srv/fs/mfs/mfs_ops.c

    r8f8818ac r0db0df2  
    115115
    116116static bool
    117 open_nodes_key_equal(const void *key, const ht_link_t *item)
     117open_nodes_key_equal(const void *key, size_t hash, const ht_link_t *item)
    118118{
    119119        const node_key_t *node_key = key;

  • uspace/srv/fs/tmpfs/tmpfs_ops.c

    r8f8818ac r0db0df2  
    3838
    3939#include "tmpfs.h"
    40 #include "../../vfs/vfs.h"
    4140#include <macros.h>
    4241#include <stdint.h>
    … …  
    159158}
    160159
    161 static bool nodes_key_equal(const void *key_arg, const ht_link_t *item)
     160static bool nodes_key_equal(const void *key_arg, size_t hash,
     161    const ht_link_t *item)
    162162{
    163163        tmpfs_node_t *node = hash_table_get_inst(item, tmpfs_node_t, nh_link);

  • uspace/srv/fs/udf/udf_idx.c

    r8f8818ac r0db0df2  
    3535 */
    3636
    37 #include "../../vfs/vfs.h"
    3837#include <errno.h>
    3938#include <str.h>
    … …  
    6968}
    7069
    71 static bool udf_idx_key_equal(const void *k, const ht_link_t *item)
     70static bool udf_idx_key_equal(const void *k, size_t hash, const ht_link_t *item)
    7271{
    7372        const udf_ht_key_t *key = k;

  • uspace/srv/hid/input/gsp.c

    r8f8818ac r0db0df2  
    7676}
    7777
    78 static bool trans_key_equal(const void *key, const ht_link_t *item)
     78static bool trans_key_equal(const void *key, size_t hash, const ht_link_t *item)
    7979{
    8080        const trans_key_t *trans_key = key;

  • uspace/srv/ns/service.c

    r8f8818ac r0db0df2  
    7979}
    8080
    81 static bool service_key_equal(const void *key, const ht_link_t *item)
     81static bool service_key_equal(const void *key, size_t hash,
     82    const ht_link_t *item)
    8283{
    8384        const service_t *srv = key;
    … …  
    102103}
    103104
    104 static bool iface_key_equal(const void *key, const ht_link_t *item)
     105static bool iface_key_equal(const void *key, size_t hash, const ht_link_t *item)
    105106{
    106107        const iface_t *kiface = key;

  • uspace/srv/ns/task.c

    r8f8818ac r0db0df2  
    6666}
    6767
    68 static bool task_key_equal(const void *key, const ht_link_t *item)
     68static bool task_key_equal(const void *key, size_t hash, const ht_link_t *item)
    6969{
    7070        const task_id_t *tid = key;
    … …  
    111111}
    112112
    113 static bool p2i_key_equal(const void *key, const ht_link_t *item)
     113static bool p2i_key_equal(const void *key, size_t hash, const ht_link_t *item)
    114114{
    115115        const sysarg_t *label = key;

  • uspace/srv/vfs/vfs_node.c

    r8f8818ac r0db0df2  
    6262static size_t nodes_key_hash(const void *);
    6363static size_t nodes_hash(const ht_link_t *);
    64 static bool nodes_key_equal(const void *, const ht_link_t *);
     64static bool nodes_key_equal(const void *, size_t, const ht_link_t *);
    6565static vfs_triplet_t node_triplet(vfs_node_t *node);
    6666
    … …  
    294294}
    295295
    296 static bool nodes_key_equal(const void *key, const ht_link_t *item)
     296static bool nodes_key_equal(const void *key, size_t hash, const ht_link_t *item)
    297297{
    298298        const vfs_triplet_t *tri = key;
Note: See TracChangeset for help on using the changeset viewer.