Changeset 0ca7286 in mainline for uspace/srv/devman/devman.c


Ignore:
Timestamp:
2012-07-21T11:19:27Z (12 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.

File:
1 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
Note: See TracChangeset for help on using the changeset viewer.