Changeset 0ca7286 in mainline for uspace/srv


Ignore:
Timestamp:
2012-07-21T11:19:27Z (14 years ago)
Author:
Adam Hraska <adam.hraska+hos@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
2732c94
Parents:
1c1da4b
Message:

Added resizing to user space (single-threaded) hash_table. Resizes in a way to mitigate effects of bad hash functions. Change of interface affected many files.

Location:
uspace/srv
Files:
13 edited

Legend:

Unmodified
Added
Removed

  • uspace/srv/devman/devman.c

    r1c1da4b r0ca7286  
    6666/* hash table operations */
    6767
    68 static hash_index_t devices_hash(unsigned long key[])
    69 {
    70         return key[0] % DEVICE_BUCKETS;
    71 }
    72 
    73 static int devman_devices_compare(unsigned long key[], hash_count_t keys,
    74     link_t *item)
     68static size_t devices_key_hash(unsigned long key[])
     69{
     70        return key[0];
     71}
     72
     73static size_t devman_devices_hash(const link_t *item)
     74{
     75        dev_node_t *dev = hash_table_get_instance(item, dev_node_t, devman_dev);
     76        unsigned long key = dev->handle;
     77        return devices_key_hash(&key);
     78}
     79
     80static size_t devman_functions_hash(const link_t *item)
     81{
     82        fun_node_t *fun = hash_table_get_instance(item, fun_node_t, devman_fun);
     83        unsigned long key = fun->handle;
     84        return devices_key_hash(&key);
     85}
     86
     87static size_t loc_functions_hash(const link_t *item)
     88{
     89        fun_node_t *fun = hash_table_get_instance(item, fun_node_t, loc_fun);
     90        unsigned long key = fun->service_id;
     91        return devices_key_hash(&key);
     92}
     93
     94static bool devman_devices_match(unsigned long key[], size_t keys,
     95    const link_t *item)
    7596{
    7697        dev_node_t *dev = hash_table_get_instance(item, dev_node_t, devman_dev);
    … …  
    7899}
    79100
    80 static int devman_functions_compare(unsigned long key[], hash_count_t keys,
    81     link_t *item)
     101static bool devman_functions_match(unsigned long key[], size_t keys,
     102    const link_t *item)
    82103{
    83104        fun_node_t *fun = hash_table_get_instance(item, fun_node_t, devman_fun);
    … …  
    85106}
    86107
    87 static int loc_functions_compare(unsigned long key[], hash_count_t keys,
    88     link_t *item)
     108static bool loc_functions_match(unsigned long key[], size_t keys,
     109    const link_t *item)
    89110{
    90111        fun_node_t *fun = hash_table_get_instance(item, fun_node_t, loc_fun);
    … …  
    92113}
    93114
    94 static void devices_remove_callback(link_t *item)
    95 {
    96 }
    97 
    98 static hash_table_operations_t devman_devices_ops = {
    99         .hash = devices_hash,
    100         .compare = devman_devices_compare,
    101         .remove_callback = devices_remove_callback
     115
     116static hash_table_ops_t devman_devices_ops = {
     117        .hash = devman_devices_hash,
     118        .key_hash = devices_key_hash,
     119        .match = devman_devices_match,
     120        .equal = 0,
     121        .remove_callback = 0
    102122};
    103123
    104 static hash_table_operations_t devman_functions_ops = {
    105         .hash = devices_hash,
    106         .compare = devman_functions_compare,
    107         .remove_callback = devices_remove_callback
     124static hash_table_ops_t devman_functions_ops = {
     125        .hash = devman_functions_hash,
     126        .key_hash = devices_key_hash,
     127        .match = devman_functions_match,
     128        .equal = 0,
     129        .remove_callback = 0
    108130};
    109131
    110 static hash_table_operations_t loc_devices_ops = {
    111         .hash = devices_hash,
    112         .compare = loc_functions_compare,
    113         .remove_callback = devices_remove_callback
     132static hash_table_ops_t loc_devices_ops = {
     133        .hash = loc_functions_hash,
     134        .key_hash = devices_key_hash,
     135        .match = loc_functions_match,
     136        .equal = 0,
     137        .remove_callback = 0
    114138};
    115139
    … …  
    974998        tree->current_handle = 0;
    975999       
    976         hash_table_create(&tree->devman_devices, DEVICE_BUCKETS, 1,
    977             &devman_devices_ops);
    978         hash_table_create(&tree->devman_functions, DEVICE_BUCKETS, 1,
    979             &devman_functions_ops);
    980         hash_table_create(&tree->loc_functions, DEVICE_BUCKETS, 1,
    981             &loc_devices_ops);
     1000        hash_table_create(&tree->devman_devices, 0, 1, &devman_devices_ops);
     1001        hash_table_create(&tree->devman_functions, 0, 1, &devman_functions_ops);
     1002        hash_table_create(&tree->loc_functions, 0, 1, &loc_devices_ops);
    9821003       
    9831004        fibril_rwlock_initialize(&tree->rwlock);
    … …  
    12821303        /* Add the node to the handle-to-node map. */
    12831304        dev->handle = ++tree->current_handle;
    1284         unsigned long key = dev->handle;
    1285         hash_table_insert(&tree->devman_devices, &key, &dev->devman_dev);
     1305        hash_table_insert(&tree->devman_devices, &dev->devman_dev);
    12861306
    12871307        /* Add the node to the list of its parent's children. */
    … …  
    13461366        /* Add the node to the handle-to-node map. */
    13471367        fun->handle = ++tree->current_handle;
    1348         unsigned long key = fun->handle;
    1349         hash_table_insert(&tree->devman_functions, &key, &fun->devman_fun);
     1368        hash_table_insert(&tree->devman_functions, &fun->devman_fun);
    13501369
    13511370        /* Add the node to the list of its parent's children. */
    … …  
    14991518        assert(fibril_rwlock_is_write_locked(&tree->rwlock));
    15001519       
    1501         unsigned long key = (unsigned long) fun->service_id;
    1502         hash_table_insert(&tree->loc_functions, &key, &fun->loc_fun);
     1520        hash_table_insert(&tree->loc_functions, &fun->loc_fun);
    15031521}
    15041522

  • uspace/srv/devman/devman.h

    r1c1da4b r0ca7286  
    5252
    5353#define MATCH_EXT ".ma"
    54 #define DEVICE_BUCKETS 256
    5554
    5655#define LOC_DEVICE_NAMESPACE "devices"

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

    r1c1da4b r0ca7286  
    6363#define NODE_CACHE_SIZE  200
    6464
    65 #define NODES_BUCKETS  256
    66 
    6765#define NODES_KEY_SRVC   0
    6866#define NODES_KEY_INDEX  1
    … …  
    226224static hash_table_t nodes;
    227225
    228 static hash_index_t nodes_hash(unsigned long key[])
    229 {
    230         return key[NODES_KEY_INDEX] % NODES_BUCKETS;
    231 }
    232 
    233 static int nodes_compare(unsigned long key[], hash_count_t keys, link_t *item)
    234 {
    235         cdfs_node_t *node =
    236             hash_table_get_instance(item, cdfs_node_t, nh_link);
    237        
    238         switch (keys) {
    239         case 1:
     226static size_t nodes_key_hash(unsigned long key[])
     227{
     228        return key[NODES_KEY_INDEX];
     229}
     230
     231static size_t nodes_hash(const link_t *item)
     232{
     233        cdfs_node_t *node = hash_table_get_instance(item, cdfs_node_t, nh_link);
     234       
     235        unsigned long key[] = {
     236                [NODES_KEY_INDEX] = node->index
     237        };
     238       
     239        return nodes_key_hash(key);
     240}
     241
     242static bool nodes_match(unsigned long key[], size_t keys, const link_t *item)
     243{
     244        cdfs_node_t *node = hash_table_get_instance(item, cdfs_node_t, nh_link);
     245       
     246        if (keys == 1) {
    240247                return (node->service_id == key[NODES_KEY_SRVC]);
    241         case 2:
     248        } else {
     249                assert(keys == 2);
    242250                return ((node->service_id == key[NODES_KEY_SRVC]) &&
    243251                    (node->index == key[NODES_KEY_INDEX]));
    244         default:
    245                 assert((keys == 1) || (keys == 2));
    246         }
    247        
    248         return 0;
     252        }
     253}
     254
     255static bool nodes_equal(const link_t *item1, const link_t *item2)
     256{
     257        cdfs_node_t *node1 = hash_table_get_instance(item1, cdfs_node_t, nh_link);
     258        cdfs_node_t *node2 = hash_table_get_instance(item2, cdfs_node_t, nh_link);
     259       
     260        return node1->service_id == node2->service_id
     261                && node1->index == node2->index;
    249262}
    250263
    251264static void nodes_remove_callback(link_t *item)
    252265{
    253         cdfs_node_t *node =
    254             hash_table_get_instance(item, cdfs_node_t, nh_link);
     266        cdfs_node_t *node = hash_table_get_instance(item, cdfs_node_t, nh_link);
    255267       
    256268        assert(node->type == CDFS_DIRECTORY);
    … …  
    268280
    269281/** Nodes hash table operations */
    270 static hash_table_operations_t nodes_ops = {
     282static hash_table_ops_t nodes_ops = {
    271283        .hash = nodes_hash,
    272         .compare = nodes_compare,
     284        .key_hash = nodes_key_hash,
     285        .match = nodes_match,
     286        .equal = nodes_equal,
    273287        .remove_callback = nodes_remove_callback
    274288};
    … …  
    353367       
    354368        /* Insert the new node into the nodes hash table. */
    355         unsigned long key[] = {
    356                 [NODES_KEY_SRVC] = node->service_id,
    357                 [NODES_KEY_INDEX] = node->index
    358         };
    359        
    360         hash_table_insert(&nodes, key, &node->nh_link);
     369        hash_table_insert(&nodes, &node->nh_link);
    361370       
    362371        *rfn = FS_NODE(node);
    … …  
    912921}
    913922
     923static bool cache_remove_closed(link_t *item, void *arg)
     924{
     925        size_t *premove_cnt = (size_t*)arg;
     926       
     927        /* Some nodes were requested to be removed from the cache. */
     928        if (0 < *premove_cnt) {
     929                cdfs_node_t *node =     hash_table_get_instance(item, cdfs_node_t, nh_link);
     930
     931                if (!node->opened) {
     932                        hash_table_remove_item(&nodes, item);
     933                       
     934                        --nodes_cached;
     935                        --*premove_cnt;
     936                }
     937        }
     938       
     939        /* Only continue if more nodes were requested to be removed. */
     940        return 0 < *premove_cnt;
     941}
     942
    914943static void cleanup_cache(service_id_t service_id)
    915944{
    916945        if (nodes_cached > NODE_CACHE_SIZE) {
    917                 size_t remove = nodes_cached - NODE_CACHE_SIZE;
    918                
    919                 // FIXME: this accesses the internals of the hash table
    920                 //        and should be rewritten in a clean way
    921                
    922                 for (hash_index_t chain = 0; chain < nodes.entries; chain++) {
    923                         for (link_t *link = nodes.entry[chain].head.next;
    924                             link != &nodes.entry[chain].head;
    925                             link = link->next) {
    926                                 if (remove == 0)
    927                                         return;
    928                                
    929                                 cdfs_node_t *node =
    930                                     hash_table_get_instance(link, cdfs_node_t, nh_link);
    931                                 if (node->opened == 0) {
    932                                         link_t *tmp = link;
    933                                         link = link->prev;
    934                                        
    935                                         list_remove(tmp);
    936                                         nodes.op->remove_callback(tmp);
    937                                         nodes_cached--;
    938                                         remove--;
    939                                        
    940                                         continue;
    941                                 }
    942                         }
    943                 }
     946                size_t remove_cnt = nodes_cached - NODE_CACHE_SIZE;
     947               
     948                if (0 < remove_cnt)
     949                        hash_table_apply(&nodes, cache_remove_closed, &remove_cnt);
    944950        }
    945951}
    … …  
    10071013bool cdfs_init(void)
    10081014{
    1009         if (!hash_table_create(&nodes, NODES_BUCKETS, 2, &nodes_ops))
     1015        if (!hash_table_create(&nodes, 0, 2, &nodes_ops))
    10101016                return false;
    10111017       

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

    r1c1da4b r0ca7286  
    112112static hash_table_t up_hash;
    113113
    114 #define UPH_BUCKETS_LOG 12
    115 #define UPH_BUCKETS     (1 << UPH_BUCKETS_LOG)
    116 
    117114#define UPH_SID_KEY     0
    118115#define UPH_PFC_KEY     1
    119116#define UPH_PDI_KEY     2
    120117
    121 static hash_index_t pos_hash(unsigned long key[])
    122 {
    123         service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
    124         exfat_cluster_t pfc = (exfat_cluster_t)key[UPH_PFC_KEY];
    125         unsigned pdi = (unsigned)key[UPH_PDI_KEY];
    126 
    127         hash_index_t h;
    128 
    129         /*
    130          * The least significant half of all bits are the least significant bits
    131          * of the parent node's first cluster.
    132          *
    133          * The least significant half of the most significant half of all bits
    134          * are the least significant bits of the node's dentry index within the
    135          * parent directory node.
    136          *
    137          * The most significant half of the most significant half of all bits
    138          * are the least significant bits of the device handle.
    139          */
    140         h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
    141         h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
    142             (UPH_BUCKETS_LOG / 2);
    143         h |= (service_id & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
    144             (3 * (UPH_BUCKETS_LOG / 4));
    145 
    146         return h;
    147 }
    148 
    149 static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)
     118static size_t pos_key_hash(unsigned long key[])
     119{
     120        /* Inspired by Effective Java, 2nd edition. */
     121        size_t hash = 17;
     122       
     123        hash = 31 * hash + key[UPH_PFC_KEY];
     124        hash = 31 * hash + key[UPH_PDI_KEY];
     125        hash = 31 * hash + key[UPH_SID_KEY];
     126       
     127        return hash;
     128}
     129
     130static size_t pos_hash(const link_t *item)
     131{
     132        exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uph_link);
     133       
     134        unsigned long pkey[] = {
     135                [UPH_SID_KEY] = fidx->service_id,
     136                [UPH_PFC_KEY] = fidx->pfc,
     137                [UPH_PDI_KEY] = fidx->pdi,
     138        };
     139       
     140        return pos_key_hash(pkey);
     141}
     142
     143static bool pos_match(unsigned long key[], size_t keys, const link_t *item)
    150144{
    151145        service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
    … …  
    169163}
    170164
    171 static void pos_remove_callback(link_t *item)
    172 {
    173         /* nothing to do */
    174 }
    175 
    176 static hash_table_operations_t uph_ops = {
     165static hash_table_ops_t uph_ops = {
    177166        .hash = pos_hash,
    178         .compare = pos_compare,
    179         .remove_callback = pos_remove_callback,
     167        .key_hash = pos_key_hash,
     168        .match = pos_match,
     169        .equal = 0,
     170        .remove_callback = 0,
    180171};
    181172
    … …  
    186177static hash_table_t ui_hash;
    187178
    188 #define UIH_BUCKETS_LOG 12
    189 #define UIH_BUCKETS     (1 << UIH_BUCKETS_LOG)
    190 
    191179#define UIH_SID_KEY     0
    192180#define UIH_INDEX_KEY   1
    193181
    194 static hash_index_t idx_hash(unsigned long key[])
     182static size_t idx_key_hash(unsigned long key[])
    195183{
    196184        service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
    197185        fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
    198186
    199         hash_index_t h;
    200 
    201         h = service_id & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
    202         h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
    203             (UIH_BUCKETS_LOG / 2);
    204 
    205         return h;
    206 }
    207 
    208 static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
     187        /*
     188         * Compute a simple hash unlimited by specific table size as per:
     189         * Effective Java, 2nd edition.
     190         */
     191        size_t hash = 17;
     192        hash = 31 * hash + (size_t)service_id;
     193        hash = 31 * hash + (size_t)index;
     194        return hash;
     195}
     196
     197static size_t idx_hash(const link_t *item)
     198{
     199        exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uih_link);
     200       
     201        unsigned long ikey[] = {
     202                [UIH_SID_KEY] = fidx->service_id,
     203                [UIH_INDEX_KEY] = fidx->index,
     204        };
     205
     206        return idx_key_hash(ikey);
     207}
     208
     209static bool idx_match(unsigned long key[], size_t keys, const link_t *item)
    209210{
    210211        service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
    … …  
    233234}
    234235
    235 static hash_table_operations_t uih_ops = {
     236static hash_table_ops_t uih_ops = {
    236237        .hash = idx_hash,
    237         .compare = idx_compare,
     238        .key_hash = idx_key_hash,
     239        .match = idx_match,
     240        .equal = 0,
    238241        .remove_callback = idx_remove_callback,
    239242};
    … …  
    400403        }
    401404               
    402         unsigned long ikey[] = {
    403                 [UIH_SID_KEY] = service_id,
    404                 [UIH_INDEX_KEY] = fidx->index,
    405         };
    406        
    407         hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
     405        hash_table_insert(&ui_hash, &fidx->uih_link);
    408406        fibril_mutex_lock(&fidx->lock);
    409407        fibril_mutex_unlock(&used_lock);
    … …  
    437435                }
    438436               
    439                 unsigned long ikey[] = {
    440                         [UIH_SID_KEY] = service_id,
    441                         [UIH_INDEX_KEY] = fidx->index,
    442                 };
    443        
    444437                fidx->pfc = pfc;
    445438                fidx->pdi = pdi;
    446439
    447                 hash_table_insert(&up_hash, pkey, &fidx->uph_link);
    448                 hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
     440                hash_table_insert(&up_hash, &fidx->uph_link);
     441                hash_table_insert(&ui_hash, &fidx->uih_link);
    449442        }
    450443        fibril_mutex_lock(&fidx->lock);
    … …  
    456449void exfat_idx_hashin(exfat_idx_t *idx)
    457450{
    458         unsigned long pkey[] = {
    459                 [UPH_SID_KEY] = idx->service_id,
    460                 [UPH_PFC_KEY] = idx->pfc,
    461                 [UPH_PDI_KEY] = idx->pdi,
    462         };
    463 
    464         fibril_mutex_lock(&used_lock);
    465         hash_table_insert(&up_hash, pkey, &idx->uph_link);
     451        fibril_mutex_lock(&used_lock);
     452        hash_table_insert(&up_hash, &idx->uph_link);
    466453        fibril_mutex_unlock(&used_lock);
    467454}
    … …  
    532519int exfat_idx_init(void)
    533520{
    534         if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))
     521        if (!hash_table_create(&up_hash, 0, 3, &uph_ops))
    535522                return ENOMEM;
    536         if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
     523        if (!hash_table_create(&ui_hash, 0, 2, &uih_ops)) {
    537524                hash_table_destroy(&up_hash);
    538525                return ENOMEM;

  • uspace/srv/fs/ext2fs/ext2fs_ops.c

    r1c1da4b r0ca7286  
    6565#define OPEN_NODES_DEV_HANDLE_KEY 0
    6666#define OPEN_NODES_INODE_KEY 1
    67 #define OPEN_NODES_BUCKETS 256
    6867
    6968typedef struct ext2fs_instance {
    … …  
    123122
    124123/* Hash table interface for open nodes hash table */
    125 static hash_index_t open_nodes_hash(unsigned long key[])
    126 {
    127         /* TODO: This is very simple and probably can be improved */
    128         return key[OPEN_NODES_INODE_KEY] % OPEN_NODES_BUCKETS;
    129 }
    130 
    131 static int open_nodes_compare(unsigned long key[], hash_count_t keys,
    132     link_t *item)
     124static size_t open_nodes_key_hash(unsigned long key[])
     125{
     126        /* Hash construction recommended in Effective Java, 2nd Edition. */
     127        size_t hash = 17;
     128        hash = 31 * hash + key[OPEN_NODES_DEV_HANDLE_KEY];
     129        hash = 31 * hash + key[OPEN_NODES_INODE_KEY];
     130        return hash;
     131}
     132
     133static size_t open_nodes_hash(const link_t *item)
     134{
     135        ext2fs_node_t *enode = hash_table_get_instance(item, ext2fs_node_t, link);
     136
     137        assert(enode->instance);
     138        assert(enode->inode_ref);
     139       
     140        unsigned long key[] = {
     141                [OPEN_NODES_DEV_HANDLE_KEY] = enode->instance->service_id,
     142                [OPEN_NODES_INODE_KEY] = enode->inode_ref->index,
     143        };
     144       
     145        return open_nodes_key_hash(key);
     146}
     147
     148static bool open_nodes_match(unsigned long key[], size_t keys,
     149    const link_t *item)
    133150{
    134151        ext2fs_node_t *enode = hash_table_get_instance(item, ext2fs_node_t, link);
    … …  
    145162}
    146163
    147 static void open_nodes_remove_cb(link_t *link)
    148 {
    149         /* We don't use remove callback for this hash table */
    150 }
    151 
    152 static hash_table_operations_t open_nodes_ops = {
     164static hash_table_ops_t open_nodes_ops = {
    153165        .hash = open_nodes_hash,
    154         .compare = open_nodes_compare,
    155         .remove_callback = open_nodes_remove_cb,
     166        .key_hash = open_nodes_key_hash,
     167        .match = open_nodes_match,
     168        .equal = 0,
     169        .remove_callback = 0,
    156170};
    157171
    … …  
    161175int ext2fs_global_init(void)
    162176{
    163         if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS,
    164             OPEN_NODES_KEYS, &open_nodes_ops)) {
     177        if (!hash_table_create(&open_nodes, 0, OPEN_NODES_KEYS, &open_nodes_ops)) {
    165178                return ENOMEM;
    166179        }
    … …  
    362375        *rfn = node;
    363376       
    364         hash_table_insert(&open_nodes, key, &enode->link);
     377        hash_table_insert(&open_nodes, &enode->link);
    365378        inst->open_nodes_count++;
    366379       

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

    r1c1da4b r0ca7286  
    4646#include <malloc.h>
    4747
     48
    4849/** Each instance of this type describes one interval of freed VFS indices. */
    4950typedef struct {
    … …  
    113114static hash_table_t up_hash;
    114115
    115 #define UPH_BUCKETS_LOG 12
    116 #define UPH_BUCKETS     (1 << UPH_BUCKETS_LOG)
    117 
    118116#define UPH_SID_KEY     0
    119117#define UPH_PFC_KEY     1
    120118#define UPH_PDI_KEY     2
    121119
    122 static hash_index_t pos_hash(unsigned long key[])
    123 {
    124         service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
    125         fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
    126         unsigned pdi = (unsigned)key[UPH_PDI_KEY];
    127 
    128         hash_index_t h;
    129 
    130         /*
    131          * The least significant half of all bits are the least significant bits
    132          * of the parent node's first cluster.
    133          *
    134          * The least significant half of the most significant half of all bits
    135          * are the least significant bits of the node's dentry index within the
    136          * parent directory node.
    137          *
    138          * The most significant half of the most significant half of all bits
    139          * are the least significant bits of the device handle.
    140          */
    141         h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
    142         h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
    143             (UPH_BUCKETS_LOG / 2);
    144         h |= (service_id & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
    145             (3 * (UPH_BUCKETS_LOG / 4));
    146 
    147         return h;
    148 }
    149 
    150 static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)
     120static size_t pos_key_hash(unsigned long key[])
     121{
     122        /* Inspired by Effective Java, 2nd edition. */
     123        size_t hash = 17;
     124       
     125        hash = 31 * hash + key[UPH_PFC_KEY];
     126        hash = 31 * hash + key[UPH_PDI_KEY];
     127        hash = 31 * hash + key[UPH_SID_KEY];
     128       
     129        return hash;
     130}
     131
     132static size_t pos_hash(const link_t *item)
     133{
     134        fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link);
     135       
     136        unsigned long pkey[] = {
     137                [UPH_SID_KEY] = fidx->service_id,
     138                [UPH_PFC_KEY] = fidx->pfc,
     139                [UPH_PDI_KEY] = fidx->pdi,
     140        };
     141       
     142        return pos_key_hash(pkey);
     143}
     144
     145static bool pos_match(unsigned long key[], size_t keys, const link_t *item)
    151146{
    152147        service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
    … …  
    170165}
    171166
    172 static void pos_remove_callback(link_t *item)
    173 {
    174         /* nothing to do */
    175 }
    176 
    177 static hash_table_operations_t uph_ops = {
     167static hash_table_ops_t uph_ops = {
    178168        .hash = pos_hash,
    179         .compare = pos_compare,
    180         .remove_callback = pos_remove_callback,
     169        .key_hash = pos_key_hash,
     170        .match = pos_match,
     171        .equal = 0,
     172        .remove_callback = 0,
    181173};
    182174
    … …  
    187179static hash_table_t ui_hash;
    188180
    189 #define UIH_BUCKETS_LOG 12
    190 #define UIH_BUCKETS     (1 << UIH_BUCKETS_LOG)
    191 
    192181#define UIH_SID_KEY     0
    193182#define UIH_INDEX_KEY   1
    194183
    195 static hash_index_t idx_hash(unsigned long key[])
    196 {
    197         service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
    198         fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
    199 
    200         hash_index_t h;
    201 
    202         h = service_id & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
    203         h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
    204             (UIH_BUCKETS_LOG / 2);
    205 
    206         return h;
    207 }
    208 
    209 static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
     184static size_t idx_key_hash(unsigned long key[])
     185{
     186        /*
     187         * Compute a simple hash unlimited by specific table size as per:
     188         * Effective Java, 2nd edition.
     189         */
     190        size_t hash = 17;
     191        hash = 31 * hash + key[UIH_SID_KEY];
     192        hash = 31 * hash + key[UIH_INDEX_KEY];
     193        return hash;
     194}
     195
     196static size_t idx_hash(const link_t *item)
     197{
     198        fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
     199       
     200        unsigned long ikey[] = {
     201                [UIH_SID_KEY] = fidx->service_id,
     202                [UIH_INDEX_KEY] = fidx->index,
     203        };
     204
     205        return idx_key_hash(ikey);
     206}
     207
     208static bool idx_match(unsigned long key[], size_t keys, const link_t *item)
    210209{
    211210        service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
    … …  
    234233}
    235234
    236 static hash_table_operations_t uih_ops = {
     235static hash_table_ops_t uih_ops = {
    237236        .hash = idx_hash,
    238         .compare = idx_compare,
     237        .key_hash = idx_key_hash,
     238        .match = idx_match,
     239        .equal = 0,
    239240        .remove_callback = idx_remove_callback,
    240241};
    … …  
    401402        }
    402403               
    403         unsigned long ikey[] = {
    404                 [UIH_SID_KEY] = service_id,
    405                 [UIH_INDEX_KEY] = fidx->index,
    406         };
    407        
    408         hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
     404        hash_table_insert(&ui_hash, &fidx->uih_link);
    409405        fibril_mutex_lock(&fidx->lock);
    410406        fibril_mutex_unlock(&used_lock);
    … …  
    438434                }
    439435               
    440                 unsigned long ikey[] = {
    441                         [UIH_SID_KEY] = service_id,
    442                         [UIH_INDEX_KEY] = fidx->index,
    443                 };
    444        
    445436                fidx->pfc = pfc;
    446437                fidx->pdi = pdi;
    447438
    448                 hash_table_insert(&up_hash, pkey, &fidx->uph_link);
    449                 hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
     439                hash_table_insert(&up_hash, &fidx->uph_link);
     440                hash_table_insert(&ui_hash, &fidx->uih_link);
    450441        }
    451442        fibril_mutex_lock(&fidx->lock);
    … …  
    457448void fat_idx_hashin(fat_idx_t *idx)
    458449{
    459         unsigned long pkey[] = {
    460                 [UPH_SID_KEY] = idx->service_id,
    461                 [UPH_PFC_KEY] = idx->pfc,
    462                 [UPH_PDI_KEY] = idx->pdi,
    463         };
    464 
    465         fibril_mutex_lock(&used_lock);
    466         hash_table_insert(&up_hash, pkey, &idx->uph_link);
     450        fibril_mutex_lock(&used_lock);
     451        hash_table_insert(&up_hash, &idx->uph_link);
    467452        fibril_mutex_unlock(&used_lock);
    468453}
    … …  
    470455void fat_idx_hashout(fat_idx_t *idx)
    471456{
    472         unsigned long pkey[] = {
    473                 [UPH_SID_KEY] = idx->service_id,
    474                 [UPH_PFC_KEY] = idx->pfc,
    475                 [UPH_PDI_KEY] = idx->pdi,
    476         };
    477 
    478         fibril_mutex_lock(&used_lock);
    479         hash_table_remove(&up_hash, pkey, 3);
     457        fibril_mutex_lock(&used_lock);
     458        hash_table_remove_item(&up_hash, &idx->uph_link);
    480459        fibril_mutex_unlock(&used_lock);
    481460}
    … …  
    532511int fat_idx_init(void)
    533512{
    534         if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))
     513        if (!hash_table_create(&up_hash, 0, 3, &uph_ops))
    535514                return ENOMEM;
    536         if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
     515        if (!hash_table_create(&ui_hash, 0, 2, &uih_ops)) {
    537516                hash_table_destroy(&up_hash);
    538517                return ENOMEM;

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

    r1c1da4b r0ca7286  
    7373#define SERVICES_KEYS        1
    7474#define SERVICES_KEY_HANDLE  0
    75 #define SERVICES_BUCKETS     256
    7675
    7776/* Implementation of hash table interface for the nodes hash table. */
    78 static hash_index_t services_hash(unsigned long key[])
    79 {
    80         return key[SERVICES_KEY_HANDLE] % SERVICES_BUCKETS;
    81 }
    82 
    83 static int services_compare(unsigned long key[], hash_count_t keys, link_t *item)
    84 {
     77
     78static size_t services_key_hash(unsigned long key[])
     79{
     80        return key[SERVICES_KEY_HANDLE];
     81}
     82
     83static size_t services_hash(const link_t *item)
     84{
     85        service_t *dev = hash_table_get_instance(item, service_t, link);
     86        unsigned long key[] = {
     87                [SERVICES_KEY_HANDLE] = dev->service_id
     88        };
     89       
     90        return services_key_hash(key);
     91}
     92
     93static bool services_match(unsigned long key[], size_t keys, const link_t *item)
     94{
     95        assert(keys == 1);
    8596        service_t *dev = hash_table_get_instance(item, service_t, link);
    8697        return (dev->service_id == (service_id_t) key[SERVICES_KEY_HANDLE]);
    … …  
    92103}
    93104
    94 static hash_table_operations_t services_ops = {
     105static hash_table_ops_t services_ops = {
    95106        .hash = services_hash,
    96         .compare = services_compare,
     107        .key_hash = services_key_hash,
     108        .match = services_match,
     109        .equal = 0,
    97110        .remove_callback = services_remove_callback
    98111};
    … …  
    256269                         * below.
    257270                         */
    258                         hash_table_insert(&services, key, &dev->link);
     271                        hash_table_insert(&services, &dev->link);
    259272                       
    260273                        /*
    … …  
    450463bool locfs_init(void)
    451464{
    452         if (!hash_table_create(&services, SERVICES_BUCKETS,
    453             SERVICES_KEYS, &services_ops))
     465        if (!hash_table_create(&services, 0,  SERVICES_KEYS, &services_ops))
    454466                return false;
    455467       

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

    r1c1da4b r0ca7286  
    4040#define OPEN_NODES_SERVICE_KEY 0
    4141#define OPEN_NODES_INODE_KEY 1
    42 #define OPEN_NODES_BUCKETS 256
    4342
    4443static bool check_magic_number(uint16_t magic, bool *native,
    … …  
    6160static int mfs_unlink(fs_node_t *, fs_node_t *, const char *name);
    6261static int mfs_destroy_node(fs_node_t *fn);
    63 static hash_index_t open_nodes_hash(unsigned long key[]);
    64 static int open_nodes_compare(unsigned long key[], hash_count_t keys,
    65     link_t *item);
    66 static void open_nodes_remove_cb(link_t *link);
     62static size_t open_nodes_hash(const link_t *item);
     63static size_t open_nodes_key_hash(unsigned long key[]);
     64static bool open_nodes_match(unsigned long key[], size_t keys,
     65    const link_t *item);
    6766static int mfs_node_get(fs_node_t **rfn, service_id_t service_id,
    6867    fs_index_t index);
    … …  
    9594
    9695/* Hash table interface for open nodes hash table */
    97 static hash_index_t
    98 open_nodes_hash(unsigned long key[])
    99 {
    100         /* TODO: This is very simple and probably can be improved */
    101         return key[OPEN_NODES_INODE_KEY] % OPEN_NODES_BUCKETS;
    102 }
    103 
    104 static int
    105 open_nodes_compare(unsigned long key[], hash_count_t keys,
    106     link_t *item)
    107 {
     96
     97static size_t
     98open_nodes_key_hash(unsigned long key[])
     99{
     100        /* As recommended by Effective Java, 2nd Edition. */
     101        size_t hash = 17;
     102        hash = 37 * hash + key[OPEN_NODES_SERVICE_KEY];
     103        hash = 37 * hash + key[OPEN_NODES_INODE_KEY];
     104        return hash;
     105}
     106
     107static size_t
     108open_nodes_hash(const link_t *item)
     109{
     110        struct mfs_node *m = hash_table_get_instance(item, struct mfs_node, link);
     111       
     112        unsigned long key[] = {
     113                [OPEN_NODES_SERVICE_KEY] = m->instance->service_id,
     114                [OPEN_NODES_INODE_KEY] = m->ino_i->index,
     115        };
     116       
     117        return open_nodes_key_hash(key);
     118}
     119
     120static bool
     121open_nodes_match(unsigned long key[], size_t keys, const link_t *item)
     122{
     123        assert(keys == 2);
    108124        struct mfs_node *mnode = hash_table_get_instance(item, struct mfs_node, link);
    109         assert(keys > 0);
    110         if (mnode->instance->service_id !=
    111             ((service_id_t) key[OPEN_NODES_SERVICE_KEY])) {
    112                 return false;
    113         }
    114         if (keys == 1) {
    115                 return true;
    116         }
    117         assert(keys == 2);
    118         return (mnode->ino_i->index == key[OPEN_NODES_INODE_KEY]);
    119 }
    120 
    121 static void
    122 open_nodes_remove_cb(link_t *link)
    123 {
    124         /* We don't use remove callback for this hash table */
    125 }
    126 
    127 static hash_table_operations_t open_nodes_ops = {
     125       
     126        service_id_t service_id = ((service_id_t) key[OPEN_NODES_SERVICE_KEY]);
     127       
     128        return mnode->instance->service_id == service_id
     129                && mnode->ino_i->index == key[OPEN_NODES_INODE_KEY];
     130}
     131
     132
     133static hash_table_ops_t open_nodes_ops = {
    128134        .hash = open_nodes_hash,
    129         .compare = open_nodes_compare,
    130         .remove_callback = open_nodes_remove_cb,
     135        .key_hash = open_nodes_key_hash,
     136        .match = open_nodes_match,
     137        .equal = 0,
     138        .remove_callback = 0,
    131139};
    132140
    … …  
    134142mfs_global_init(void)
    135143{
    136         if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS,
    137             OPEN_NODES_KEYS, &open_nodes_ops)) {
     144        if (!hash_table_create(&open_nodes, 0, OPEN_NODES_KEYS, &open_nodes_ops)) {
    138145                return ENOMEM;
    139146        }
    … …  
    408415        link_initialize(&mnode->link);
    409416
    410         unsigned long key[] = {
    411                 [OPEN_NODES_SERVICE_KEY] = inst->service_id,
    412                 [OPEN_NODES_INODE_KEY] = inum,
    413         };
    414 
    415417        fibril_mutex_lock(&open_nodes_lock);
    416         hash_table_insert(&open_nodes, key, &mnode->link);
     418        hash_table_insert(&open_nodes, &mnode->link);
    417419        fibril_mutex_unlock(&open_nodes_lock);
    418420        inst->open_nodes_cnt++;
    … …  
    621623        *rfn = node;
    622624
    623         hash_table_insert(&open_nodes, key, &mnode->link);
     625        hash_table_insert(&open_nodes, &mnode->link);
    624626        inst->open_nodes_cnt++;
    625627

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

    r1c1da4b r0ca7286  
    5656#define max(a, b)               ((a) > (b) ? (a) : (b))
    5757
    58 #define NODES_BUCKETS   256
    59 
    6058/** All root nodes have index 0. */
    6159#define TMPFS_SOME_ROOT         0
    … …  
    146144
    147145/* Implementation of hash table interface for the nodes hash table. */
    148 static hash_index_t nodes_hash(unsigned long key[])
    149 {
    150         return key[NODES_KEY_INDEX] % NODES_BUCKETS;
    151 }
    152 
    153 static int nodes_compare(unsigned long key[], hash_count_t keys, link_t *item)
     146static size_t nodes_key_hash(unsigned long key[])
     147{
     148        /* Based on Effective Java, 2nd Edition. */
     149        size_t hash = 17;
     150        hash = 37 * hash + key[NODES_KEY_DEV];
     151        hash = 37 * hash + key[NODES_KEY_INDEX];
     152        return hash;
     153}
     154
     155static size_t nodes_hash(const link_t *item)
     156{
     157        tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t, nh_link);
     158       
     159        unsigned long key[] = {
     160                [NODES_KEY_DEV] = nodep->service_id,
     161                [NODES_KEY_INDEX] = nodep->index
     162        };
     163       
     164        return nodes_key_hash(key);
     165}
     166
     167static bool nodes_match(unsigned long key[], size_t keys, const link_t *item)
    154168{
    155169        tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t,
    … …  
    192206
    193207/** TMPFS nodes hash table operations. */
    194 hash_table_operations_t nodes_ops = {
     208hash_table_ops_t nodes_ops = {
    195209        .hash = nodes_hash,
    196         .compare = nodes_compare,
     210        .key_hash = nodes_key_hash,
     211        .match = nodes_match,
     212        .equal = 0,
    197213        .remove_callback = nodes_remove_callback
    198214};
    … …  
    220236bool tmpfs_init(void)
    221237{
    222         if (!hash_table_create(&nodes, NODES_BUCKETS, 2, &nodes_ops))
     238        if (!hash_table_create(&nodes, 0, 2, &nodes_ops))
    223239                return false;
    224240       
    … …  
    331347
    332348        /* Insert the new node into the nodes hash table. */
    333         unsigned long key[] = {
    334                 [NODES_KEY_DEV] = nodep->service_id,
    335                 [NODES_KEY_INDEX] = nodep->index
    336         };
    337         hash_table_insert(&nodes, key, &nodep->nh_link);
     349        hash_table_insert(&nodes, &nodep->nh_link);
    338350        *rfn = FS_NODE(nodep);
    339351        return EOK;

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

    r1c1da4b r0ca7286  
    5454#include <stdio.h>
    5555
    56 #define TRANS_TABLE_CHAINS 256
    57 
    5856/*
    5957 * Hash table operations for the transition function.
    6058 */
    6159
    62 static hash_index_t trans_op_hash(unsigned long key[]);
    63 static int trans_op_compare(unsigned long key[], hash_count_t keys,
    64     link_t *item);
    65 static void trans_op_remove_callback(link_t *item);
    66 
    67 static hash_table_operations_t trans_ops = {
     60static size_t trans_op_hash(const link_t *item);
     61static size_t trans_op_key_hash(unsigned long key[]);
     62static bool trans_op_match(unsigned long key[], size_t keys, const link_t *item);
     63
     64static hash_table_ops_t trans_ops = {
    6865        .hash = trans_op_hash,
    69         .compare = trans_op_compare,
    70         .remove_callback = trans_op_remove_callback
     66        .key_hash = trans_op_key_hash,
     67        .match = trans_op_match,
     68        .equal = 0,
     69        .remove_callback = 0
    7170};
    7271
    … …  
    7574static gsp_trans_t *trans_new(void);
    7675
    77 /** Initialise scancode parser. */
     76/** Initialize scancode parser. */
    7877void gsp_init(gsp_t *p)
    7978{
    8079        p->states = 1;
    81         hash_table_create(&p->trans, TRANS_TABLE_CHAINS, 2, &trans_ops);
     80        hash_table_create(&p->trans, 0, 2, &trans_ops);
    8281}
    8382
    … …  
    242241static void trans_insert(gsp_t *p, gsp_trans_t *t)
    243242{
    244         unsigned long key[2];
    245 
    246         key[0] = t->old_state;
    247         key[1] = t->input;
    248 
    249         hash_table_insert(&p->trans, key, &t->link);
     243        hash_table_insert(&p->trans, &t->link);
    250244}
    251245
    … …  
    268262 */
    269263
    270 static hash_index_t trans_op_hash(unsigned long key[])
    271 {
    272         return (key[0] * 17 + key[1]) % TRANS_TABLE_CHAINS;
    273 }
    274 
    275 static int trans_op_compare(unsigned long key[], hash_count_t keys,
    276     link_t *item)
    277 {
    278         gsp_trans_t *t;
    279 
    280         t = hash_table_get_instance(item, gsp_trans_t, link);
     264static size_t trans_op_key_hash(unsigned long key[])
     265{
     266        return (key[0] * 17 + key[1]);
     267}
     268
     269static size_t trans_op_hash(const link_t *item)
     270{
     271        gsp_trans_t *t = hash_table_get_instance(item, gsp_trans_t, link);
     272        unsigned long key[] = {
     273                t->old_state,
     274                t->input
     275        };
     276       
     277        return trans_op_key_hash(key);
     278}
     279
     280static bool trans_op_match(unsigned long key[], size_t keys, const link_t *item)
     281{
     282        gsp_trans_t *t = hash_table_get_instance(item, gsp_trans_t, link);
    281283        return ((key[0] == (unsigned long) t->old_state)
    282284            && (key[1] == (unsigned long) t->input));
    283 }
    284 
    285 static void trans_op_remove_callback(link_t *item)
    286 {
    287285}
    288286

  • uspace/srv/ns/service.c

    r1c1da4b r0ca7286  
    4040#include "ns.h"
    4141
    42 #define SERVICE_HASH_TABLE_CHAINS  20
    4342
    4443/** Service hash table item. */
    … …  
    5857 *
    5958 */
    60 static hash_index_t service_hash(unsigned long key[])
     59static size_t service_key_hash(unsigned long key[])
    6160{
    6261        assert(key);
    63         return (key[0] % SERVICE_HASH_TABLE_CHAINS);
     62        return key[0];
     63}
     64
     65static size_t service_hash(const link_t *item)
     66{
     67        hashed_service_t *hs = hash_table_get_instance(item, hashed_service_t, link);
     68        unsigned long key = hs->service;
     69        return service_key_hash(&key);
    6470}
    6571
    … …  
    7985 *
    8086 */
    81 static int service_compare(unsigned long key[], hash_count_t keys, link_t *item)
     87static bool service_match(unsigned long key[], size_t keys, const link_t *item)
    8288{
    8389        assert(key);
    … …  
    105111
    106112/** Operations for service hash table. */
    107 static hash_table_operations_t service_hash_table_ops = {
     113static hash_table_ops_t service_hash_table_ops = {
    108114        .hash = service_hash,
    109         .compare = service_compare,
     115        .key_hash = service_key_hash,
     116        .match = service_match,
     117        .equal = 0,
    110118        .remove_callback = service_remove
    111119};
    … …  
    127135int service_init(void)
    128136{
    129         if (!hash_table_create(&service_hash_table, SERVICE_HASH_TABLE_CHAINS,
    130             3, &service_hash_table_ops)) {
     137        if (!hash_table_create(&service_hash_table, 0, 3, &service_hash_table_ops)) {
    131138                printf(NAME ": No memory available for services\n");
    132139                return ENOMEM;
    … …  
    193200        hs->phone = phone;
    194201        hs->in_phone_hash = call->in_phone_hash;
    195         hash_table_insert(&service_hash_table, keys, &hs->link);
     202        hash_table_insert(&service_hash_table, &hs->link);
    196203       
    197204        return EOK;

  • uspace/srv/ns/task.c

    r1c1da4b r0ca7286  
    4343#include "ns.h"
    4444
    45 #define TASK_HASH_TABLE_CHAINS  256
    46 #define P2I_HASH_TABLE_CHAINS   256
    4745
    4846/* TODO:
    … …  
    7169 *
    7270 */
    73 static hash_index_t task_hash(unsigned long key[])
    74 {
    75         assert(key);
    76         return (LOWER32(key[0]) % TASK_HASH_TABLE_CHAINS);
     71static size_t task_key_hash(unsigned long key[])
     72{
     73        size_t hash = 17;
     74        hash = 37 * hash + key[1];
     75        hash = 37 * hash + key[0];
     76        return hash;
     77}
     78
     79static size_t task_hash(const link_t *item)
     80{
     81        hashed_task_t *ht = hash_table_get_instance(item, hashed_task_t, link);
     82
     83        unsigned long key[] = {
     84                LOWER32(ht->id),
     85                UPPER32(ht->id)
     86        };
     87       
     88        return task_key_hash(key);
    7789}
    7890
    … …  
    8698 *
    8799 */
    88 static int task_compare(unsigned long key[], hash_count_t keys, link_t *item)
     100static bool task_match(unsigned long key[], size_t keys, const link_t *item)
    89101{
    90102        assert(key);
    91         assert(keys <= 2);
     103        assert(keys == 2);
    92104        assert(item);
    93105       
    94106        hashed_task_t *ht = hash_table_get_instance(item, hashed_task_t, link);
    95107       
    96         if (keys == 2)
    97                 return ((LOWER32(key[1]) == UPPER32(ht->id))
    98                     && (LOWER32(key[0]) == LOWER32(ht->id)));
    99         else
    100                 return (LOWER32(key[0]) == LOWER32(ht->id));
     108        return (key[0] == LOWER32(ht->id))
     109                && (key[1] == UPPER32(ht->id));
    101110}
    102111
    … …  
    113122
    114123/** Operations for task hash table. */
    115 static hash_table_operations_t task_hash_table_ops = {
     124static hash_table_ops_t task_hash_table_ops = {
    116125        .hash = task_hash,
    117         .compare = task_compare,
     126        .key_hash = task_key_hash,
     127        .match = task_match,
     128        .equal = 0,
    118129        .remove_callback = task_remove
    119130};
    … …  
    135146 *
    136147 */
    137 static hash_index_t p2i_hash(unsigned long key[])
     148static size_t p2i_key_hash(unsigned long key[])
    138149{
    139150        assert(key);
    140         return (key[0] % TASK_HASH_TABLE_CHAINS);
     151        return key[0];
     152}
     153
     154static size_t p2i_hash(const link_t *item)
     155{
     156        p2i_entry_t *entry = hash_table_get_instance(item, p2i_entry_t, link);
     157        unsigned long key = entry->in_phone_hash;
     158        return p2i_key_hash(&key);
    141159}
    142160
    … …  
    150168 *
    151169 */
    152 static int p2i_compare(unsigned long key[], hash_count_t keys, link_t *item)
     170static bool p2i_match(unsigned long key[], size_t keys, const link_t *item)
    153171{
    154172        assert(key);
    … …  
    173191
    174192/** Operations for task hash table. */
    175 static hash_table_operations_t p2i_ops = {
     193static hash_table_ops_t p2i_ops = {
    176194        .hash = p2i_hash,
    177         .compare = p2i_compare,
     195        .key_hash = p2i_key_hash,
     196        .match = p2i_match,
     197        .equal = 0,
    178198        .remove_callback = p2i_remove
    179199};
    … …  
    193213int task_init(void)
    194214{
    195         if (!hash_table_create(&task_hash_table, TASK_HASH_TABLE_CHAINS,
    196             2, &task_hash_table_ops)) {
     215        if (!hash_table_create(&task_hash_table, 0, 2, &task_hash_table_ops)) {
    197216                printf(NAME ": No memory available for tasks\n");
    198217                return ENOMEM;
    199218        }
    200219       
    201         if (!hash_table_create(&phone_to_id, P2I_HASH_TABLE_CHAINS,
    202             1, &p2i_ops)) {
     220        if (!hash_table_create(&phone_to_id, 0, 1, &p2i_ops)) {
    203221                printf(NAME ": No memory available for tasks\n");
    204222                return ENOMEM;
    … …  
    293311int ns_task_id_intro(ipc_call_t *call)
    294312{
    295         unsigned long keys[2];
    296313       
    297314        task_id_t id = MERGE_LOUP32(IPC_GET_ARG1(*call), IPC_GET_ARG2(*call));
    298         keys[0] = call->in_phone_hash;
     315
     316        unsigned long keys[] = { call->in_phone_hash };
    299317       
    300318        link_t *link = hash_table_find(&phone_to_id, keys);
    … …  
    317335        entry->in_phone_hash = call->in_phone_hash;
    318336        entry->id = id;
    319         hash_table_insert(&phone_to_id, keys, &entry->link);
     337        hash_table_insert(&phone_to_id, &entry->link);
    320338       
    321339        /*
    322340         * Insert into the main table.
    323341         */
    324        
    325         keys[0] = LOWER32(id);
    326         keys[1] = UPPER32(id);
    327342       
    328343        link_initialize(&ht->link);
    … …  
    331346        ht->have_rval = false;
    332347        ht->retval = -1;
    333         hash_table_insert(&task_hash_table, keys, &ht->link);
     348        hash_table_insert(&task_hash_table, &ht->link);
    334349       
    335350        return EOK;

  • uspace/srv/vfs/vfs_node.c

    r1c1da4b r0ca7286  
    5858#define KEY_INDEX       2
    5959
    60 static hash_index_t nodes_hash(unsigned long []);
    61 static int nodes_compare(unsigned long [], hash_count_t, link_t *);
    62 static void nodes_remove_callback(link_t *);
     60static size_t nodes_key_hash(unsigned long []);
     61static size_t nodes_hash(const link_t *);
     62static bool nodes_match(unsigned long [], size_t, const link_t *);
    6363
    6464/** VFS node hash table operations. */
    65 hash_table_operations_t nodes_ops = {
     65hash_table_ops_t nodes_ops = {
    6666        .hash = nodes_hash,
    67         .compare = nodes_compare,
    68         .remove_callback = nodes_remove_callback
     67        .key_hash = nodes_key_hash,
     68        .match = nodes_match,
     69        .equal = 0,
     70        .remove_callback = 0,
    6971};
    7072
    … …  
    7577bool vfs_nodes_init(void)
    7678{
    77         return hash_table_create(&nodes, NODES_BUCKETS, 3, &nodes_ops);
     79        return hash_table_create(&nodes, 0, 3, &nodes_ops);
    7880}
    7981
    … …  
    207209                link_initialize(&node->nh_link);
    208210                fibril_rwlock_initialize(&node->contents_rwlock);
    209                 hash_table_insert(&nodes, key, &node->nh_link);
     211                hash_table_insert(&nodes, &node->nh_link);
    210212        } else {
    211213                node = hash_table_get_instance(tmp, vfs_node_t, nh_link);
    … …  
    240242}
    241243
    242 hash_index_t nodes_hash(unsigned long key[])
    243 {
    244         hash_index_t a = key[KEY_FS_HANDLE] << (NODES_BUCKETS_LOG / 4);
    245         hash_index_t b = (a | key[KEY_DEV_HANDLE]) << (NODES_BUCKETS_LOG / 2);
    246        
    247         return (b | key[KEY_INDEX]) & (NODES_BUCKETS - 1);
    248 }
    249 
    250 int nodes_compare(unsigned long key[], hash_count_t keys, link_t *item)
     244size_t nodes_key_hash(unsigned long key[])
     245{
     246        /* Combine into a hash like they do in Effective Java, 2nd edition. */
     247        size_t hash = 17;
     248        hash = 37 * hash + key[KEY_FS_HANDLE];
     249        hash = 37 * hash + key[KEY_DEV_HANDLE];
     250        hash = 37 * hash + key[KEY_INDEX];
     251        return hash;
     252}
     253
     254size_t nodes_hash(const link_t *item)
     255{
     256        vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
     257       
     258        unsigned long key[] = {
     259                [KEY_FS_HANDLE] = node->fs_handle,
     260                [KEY_DEV_HANDLE] = node->service_id,
     261                [KEY_INDEX] = node->index
     262        };
     263       
     264        return nodes_key_hash(key);
     265}
     266
     267
     268bool nodes_match(unsigned long key[], size_t keys, const link_t *item)
    251269{
    252270        vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
    … …  
    256274}
    257275
    258 void nodes_remove_callback(link_t *item)
    259 {
    260 }
    261276
    262277struct refcnt_data {
    … …  
    267282};
    268283
    269 static void refcnt_visitor(link_t *item, void *arg)
     284static bool refcnt_visitor(link_t *item, void *arg)
    270285{
    271286        vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
    … …  
    275290            (node->service_id == rd->service_id))
    276291                rd->refcnt += node->refcnt;
     292       
     293        return true;
    277294}
    278295
Note: See TracChangeset for help on using the changeset viewer.