Changeset 0db0df2 in mainline for uspace


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

Legend:

Unmodified
Added
Removed

  • uspace/app/hbench/env.c

    r8f8818ac r0db0df2  
    3434 */
    3535
     36#include <adt/hash.h>
    3637#include <stdlib.h>
    3738#include <stdio.h>
    … …  
    4243        ht_link_t link;
    4344
     45        size_t hash;
    4446        char *key;
    4547        char *value;
    … …  
    4951{
    5052        param_t *param = hash_table_get_inst(item, param_t, link);
    51         return str_size(param->key);
     53        return param->hash;
    5254}
    5355
    5456static size_t param_key_hash(const void *key)
    5557{
    56         const char *key_str = key;
    57         return str_size(key_str);
     58        return hash_string(key);
    5859}
    5960
    60 static bool param_key_equal(const void *key, const ht_link_t *item)
     61static bool param_key_equal(const void *key, size_t hash, const ht_link_t *item)
    6162{
    6263        param_t *param = hash_table_get_inst(item, param_t, link);
     64
     65        if (param->hash != hash)
     66                return false;
     67
    6368        const char *key_str = key;
    64 
    6569        return str_cmp(param->key, key_str) == 0;
    6670}
    … …  
    7175        param_t *b = hash_table_get_inst(link_b, param_t, link);
    7276
    73         return str_cmp(a->key, b->key) == 0;
     77        return a->hash == b->hash && str_cmp(a->key, b->key) == 0;
    7478}
    7579
    … …  
    116120        param->key = str_dup(key);
    117121        param->value = str_dup(value);
     122        param->hash = hash_string(key);
    118123
    119124        if ((param->key == NULL) || (param->value == NULL)) {
    … …  
    132137const char *bench_env_param_get(bench_env_t *env, const char *key, const char *default_value)
    133138{
    134         ht_link_t *item = hash_table_find(&env->parameters, (char *) key);
     139        ht_link_t *item = hash_table_find(&env->parameters, key);
    135140
    136141        if (item == NULL) {

  • uspace/app/trace/ipcp.c

    r8f8818ac r0db0df2  
    8484}
    8585
    86 static bool pending_call_key_equal(const void *key, const ht_link_t *item)
     86static bool pending_call_key_equal(const void *key, size_t hash, const ht_link_t *item)
    8787{
    8888        const cap_call_handle_t *chandle = key;

  • uspace/app/trace/proto.c

    r8f8818ac r0db0df2  
    6969}
    7070
    71 static bool srv_proto_key_equal(const void *key, const ht_link_t *item)
     71static bool srv_proto_key_equal(const void *key, size_t hash, const ht_link_t *item)
    7272{
    7373        const int *n = key;
    … …  
    9696}
    9797
    98 static bool method_oper_key_equal(const void *key, const ht_link_t *item)
     98static bool method_oper_key_equal(const void *key, size_t hash, const ht_link_t *item)
    9999{
    100100        const int *n = key;

  • uspace/lib/block/block.c

    r8f8818ac r0db0df2  
    254254}
    255255
    256 static bool cache_key_equal(const void *key, const ht_link_t *item)
     256static bool cache_key_equal(const void *key, size_t hash, const ht_link_t *item)
    257257{
    258258        const aoff64_t *lba = key;

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

    r8f8818ac r0db0df2  
    5050#include <as.h>
    5151#include <abi/mm/as.h>
    52 #include "../private/libc.h"
    5352#include "../private/fibril.h"
    5453
    … …  
    115114}
    116115
    117 static bool interface_key_equal(const void *key, const ht_link_t *item)
     116static bool interface_key_equal(const void *key, size_t hash, const ht_link_t *item)
    118117{
    119118        const iface_t *iface = key;
    … …  
    143142}
    144143
    145 static bool port_key_equal(const void *key, const ht_link_t *item)
     144static bool port_key_equal(const void *key, size_t hash, const ht_link_t *item)
    146145{
    147146        const port_id_t *port_id = key;

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

    r8f8818ac r0db0df2  
    242242}
    243243
    244 static bool client_key_equal(const void *key, const ht_link_t *item)
     244static bool client_key_equal(const void *key, size_t, const ht_link_t *item)
    245245{
    246246        const task_id_t *in_task_id = key;
    … …  
    502502}
    503503
    504 static bool notification_key_equal(const void *key, const ht_link_t *item)
     504static bool notification_key_equal(const void *key, size_t hash, const ht_link_t *item)
    505505{
    506506        const sysarg_t *id = key;

  • uspace/lib/ext4/src/ops.c

    r8f8818ac r0db0df2  
    113113}
    114114
    115 static bool open_nodes_key_equal(const void *key_arg, const ht_link_t *item)
     115static bool open_nodes_key_equal(const void *key_arg, size_t hash, const ht_link_t *item)
    116116{
    117117        const node_key_t *key = key_arg;

  • uspace/lib/nic/src/nic_addr_db.c

    r8f8818ac r0db0df2  
    5252typedef struct nic_addr_entry {
    5353        ht_link_t link;
     54        size_t hash;
    5455        uint8_t len;
    55         uint8_t addr[1];
     56        uint8_t addr[];
    5657} nic_addr_entry_t;
    5758
    … …  
    6061 */
    6162typedef struct {
     63        size_t hash;
    6264        size_t len;
    6365        const uint8_t *addr;
    6466} addr_key_t;
    6567
    66 static bool nic_addr_key_equal(const void *key_arg, const ht_link_t *item)
     68static bool nic_addr_key_equal(const void *key_arg, size_t hash, const ht_link_t *item)
    6769{
    6870        const addr_key_t *key = key_arg;
    6971        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
    70 
    71         return memcmp(entry->addr, key->addr, entry->len) == 0;
     72        return entry->hash == hash && memcmp(entry->addr, key->addr, entry->len) == 0;
    7273}
    7374
    … …  
    8687{
    8788        const addr_key_t *key = k;
    88         return addr_hash(key->len, key->addr);
     89        return key->hash ? key->hash : addr_hash(key->len, key->addr);
    8990}
    9091
    … …  
    9293{
    9394        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
    94         return addr_hash(entry->len, entry->addr);
     95        return entry->hash;
    9596}
    9697
    … …  
    9899{
    99100        nic_addr_entry_t *entry = member_to_inst(item, nic_addr_entry_t, link);
    100 
    101101        free(entry);
    102102}
    … …  
    173173        addr_key_t key = {
    174174                .len = db->addr_len,
    175                 .addr = addr
     175                .addr = addr,
     176                .hash = addr_hash(db->addr_len, addr),
    176177        };
    177178
    … …  
    179180                return EEXIST;
    180181
    181         nic_addr_entry_t *entry = malloc(sizeof(nic_addr_entry_t) + db->addr_len - 1);
     182        nic_addr_entry_t *entry = malloc(offsetof(nic_addr_entry_t, addr) + db->addr_len);
    182183        if (entry == NULL)
    183184                return ENOMEM;
    … …  
    185186        entry->len = (uint8_t) db->addr_len;
    186187        memcpy(entry->addr, addr, db->addr_len);
     188        entry->hash = key.hash;
    187189
    188190        hash_table_insert(&db->set, &entry->link);

  • uspace/lib/nic/src/nic_wol_virtues.c

    r8f8818ac r0db0df2  
    5757}
    5858
    59 static bool nic_wv_key_equal(const void *key, const ht_link_t *item)
     59static bool nic_wv_key_equal(const void *key, size_t hash, const ht_link_t *item)
    6060{
    6161        const nic_wv_id_t *k = key;

  • 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.