Changeset 062d900 in mainline for uspace/srv


Ignore:
Timestamp:
2012-10-09T11:49:43Z (13 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
4e00f87
Parents:
87e9392
git-author:
Adam Hraska <adam.hraska+hos@…> (2012-10-09 11:49:43)
git-committer:
Jakub Jermar <jakub@…> (2012-10-09 11:49:43)
Message:

Cherrypick userspace hash table changes from lp:~adam-hraska+lp/helenos/rcu/.

Location:
uspace/srv
Files:
21 edited

Legend:

Unmodified
Added
Removed

  • uspace/srv/devman/devman.c

    r87e9392 r062d900  
    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)
    75 {
    76         dev_node_t *dev = hash_table_get_instance(item, dev_node_t, devman_dev);
    77         return (dev->handle == (devman_handle_t) key[0]);
    78 }
    79 
    80 static int devman_functions_compare(unsigned long key[], hash_count_t keys,
    81     link_t *item)
    82 {
    83         fun_node_t *fun = hash_table_get_instance(item, fun_node_t, devman_fun);
    84         return (fun->handle == (devman_handle_t) key[0]);
    85 }
    86 
    87 static int loc_functions_compare(unsigned long key[], hash_count_t keys,
    88     link_t *item)
    89 {
    90         fun_node_t *fun = hash_table_get_instance(item, fun_node_t, loc_fun);
    91         return (fun->service_id == (service_id_t) key[0]);
    92 }
    93 
    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
     68static inline size_t handle_key_hash(void *key)
     69{
     70        devman_handle_t handle = *(devman_handle_t*)key;
     71        return handle;
     72}
     73
     74static size_t devman_devices_hash(const ht_link_t *item)
     75{
     76        dev_node_t *dev = hash_table_get_inst(item, dev_node_t, devman_dev);
     77        return handle_key_hash(&dev->handle);
     78}
     79
     80static size_t devman_functions_hash(const ht_link_t *item)
     81{
     82        fun_node_t *fun = hash_table_get_inst(item, fun_node_t, devman_fun);
     83        return handle_key_hash(&fun->handle);
     84}
     85
     86static bool devman_devices_key_equal(void *key, const ht_link_t *item)
     87{
     88        devman_handle_t handle = *(devman_handle_t*)key;
     89        dev_node_t *dev = hash_table_get_inst(item, dev_node_t, devman_dev);
     90        return dev->handle == handle;
     91}
     92
     93static bool devman_functions_key_equal(void *key, const ht_link_t *item)
     94{
     95        devman_handle_t handle = *(devman_handle_t*)key;
     96        fun_node_t *fun = hash_table_get_inst(item, fun_node_t, devman_fun);
     97        return fun->handle == handle;
     98}
     99
     100static inline size_t service_id_key_hash(void *key)
     101{
     102        service_id_t service_id = *(service_id_t*)key;
     103        return service_id;
     104}
     105
     106static size_t loc_functions_hash(const ht_link_t *item)
     107{
     108        fun_node_t *fun = hash_table_get_inst(item, fun_node_t, loc_fun);
     109        return service_id_key_hash(&fun->service_id);
     110}
     111
     112static bool loc_functions_key_equal(void *key, const ht_link_t *item)
     113{
     114        service_id_t service_id = *(service_id_t*)key;
     115        fun_node_t *fun = hash_table_get_inst(item, fun_node_t, loc_fun);
     116        return fun->service_id == service_id;
     117}
     118
     119
     120static hash_table_ops_t devman_devices_ops = {
     121        .hash = devman_devices_hash,
     122        .key_hash = handle_key_hash,
     123        .key_equal = devman_devices_key_equal,
     124        .equal = 0,
     125        .remove_callback = 0
    102126};
    103127
    104 static hash_table_operations_t devman_functions_ops = {
    105         .hash = devices_hash,
    106         .compare = devman_functions_compare,
    107         .remove_callback = devices_remove_callback
     128static hash_table_ops_t devman_functions_ops = {
     129        .hash = devman_functions_hash,
     130        .key_hash = handle_key_hash,
     131        .key_equal = devman_functions_key_equal,
     132        .equal = 0,
     133        .remove_callback = 0
    108134};
    109135
    110 static hash_table_operations_t loc_devices_ops = {
    111         .hash = devices_hash,
    112         .compare = loc_functions_compare,
    113         .remove_callback = devices_remove_callback
     136static hash_table_ops_t loc_devices_ops = {
     137        .hash = loc_functions_hash,
     138        .key_hash = service_id_key_hash,
     139        .key_equal = loc_functions_key_equal,
     140        .equal = 0,
     141        .remove_callback = 0
    114142};
    115143
    … …  
    9741002        tree->current_handle = 0;
    9751003       
    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);
     1004        hash_table_create(&tree->devman_devices, 0, 0, &devman_devices_ops);
     1005        hash_table_create(&tree->devman_functions, 0, 0, &devman_functions_ops);
     1006        hash_table_create(&tree->loc_functions, 0, 0, &loc_devices_ops);
    9821007       
    9831008        fibril_rwlock_initialize(&tree->rwlock);
    … …  
    10131038        list_initialize(&dev->functions);
    10141039        link_initialize(&dev->driver_devices);
    1015         link_initialize(&dev->devman_dev);
    10161040       
    10171041        return dev;
    … …  
    10601084dev_node_t *find_dev_node_no_lock(dev_tree_t *tree, devman_handle_t handle)
    10611085{
    1062         unsigned long key = handle;
    1063         link_t *link;
    1064        
    10651086        assert(fibril_rwlock_is_locked(&tree->rwlock));
    10661087       
    1067         link = hash_table_find(&tree->devman_devices, &key);
     1088        ht_link_t *link = hash_table_find(&tree->devman_devices, &handle);
    10681089        if (link == NULL)
    10691090                return NULL;
    10701091       
    1071         return hash_table_get_instance(link, dev_node_t, devman_dev);
     1092        return hash_table_get_inst(link, dev_node_t, devman_dev);
    10721093}
    10731094
    … …  
    11441165        link_initialize(&fun->dev_functions);
    11451166        list_initialize(&fun->match_ids.ids);
    1146         link_initialize(&fun->devman_fun);
    1147         link_initialize(&fun->loc_fun);
    11481167       
    11491168        return fun;
    … …  
    12061225fun_node_t *find_fun_node_no_lock(dev_tree_t *tree, devman_handle_t handle)
    12071226{
    1208         unsigned long key = handle;
    1209         link_t *link;
    12101227        fun_node_t *fun;
    12111228       
    12121229        assert(fibril_rwlock_is_locked(&tree->rwlock));
    12131230       
    1214         link = hash_table_find(&tree->devman_functions, &key);
     1231        ht_link_t *link = hash_table_find(&tree->devman_functions, &handle);
    12151232        if (link == NULL)
    12161233                return NULL;
    12171234       
    1218         fun = hash_table_get_instance(link, fun_node_t, devman_fun);
     1235        fun = hash_table_get_inst(link, fun_node_t, devman_fun);
    12191236       
    12201237        return fun;
    … …  
    12941311        /* Add the node to the handle-to-node map. */
    12951312        dev->handle = ++tree->current_handle;
    1296         unsigned long key = dev->handle;
    1297         hash_table_insert(&tree->devman_devices, &key, &dev->devman_dev);
     1313        hash_table_insert(&tree->devman_devices, &dev->devman_dev);
    12981314
    12991315        /* Add the node to the list of its parent's children. */
    … …  
    13161332       
    13171333        /* Remove node from the handle-to-node map. */
    1318         unsigned long key = dev->handle;
    1319         hash_table_remove(&tree->devman_devices, &key, 1);
     1334        hash_table_remove(&tree->devman_devices, &dev->handle);
    13201335       
    13211336        /* Unlink from parent function. */
    … …  
    13581373        /* Add the node to the handle-to-node map. */
    13591374        fun->handle = ++tree->current_handle;
    1360         unsigned long key = fun->handle;
    1361         hash_table_insert(&tree->devman_functions, &key, &fun->devman_fun);
     1375        hash_table_insert(&tree->devman_functions, &fun->devman_fun);
    13621376
    13631377        /* Add the node to the list of its parent's children. */
    … …  
    13791393       
    13801394        /* Remove the node from the handle-to-node map. */
    1381         unsigned long key = fun->handle;
    1382         hash_table_remove(&tree->devman_functions, &key, 1);
     1395        hash_table_remove(&tree->devman_functions, &fun->handle);
    13831396       
    13841397        /* Remove the node from the list of its parent's children. */
    … …  
    14931506{
    14941507        fun_node_t *fun = NULL;
    1495         link_t *link;
    1496         unsigned long key = (unsigned long) service_id;
    14971508       
    14981509        fibril_rwlock_read_lock(&tree->rwlock);
    1499         link = hash_table_find(&tree->loc_functions, &key);
     1510        ht_link_t *link = hash_table_find(&tree->loc_functions, &service_id);
    15001511        if (link != NULL) {
    1501                 fun = hash_table_get_instance(link, fun_node_t, loc_fun);
     1512                fun = hash_table_get_inst(link, fun_node_t, loc_fun);
    15021513                fun_add_ref(fun);
    15031514        }
    … …  
    15111522        assert(fibril_rwlock_is_write_locked(&tree->rwlock));
    15121523       
    1513         unsigned long key = (unsigned long) fun->service_id;
    1514         hash_table_insert(&tree->loc_functions, &key, &fun->loc_fun);
     1524        hash_table_insert(&tree->loc_functions, &fun->loc_fun);
    15151525}
    15161526

  • uspace/srv/devman/devman.h

    r87e9392 r062d900  
    5252
    5353#define MATCH_EXT ".ma"
    54 #define DEVICE_BUCKETS 256
    5554
    5655#define LOC_DEVICE_NAMESPACE "devices"
    … …  
    151150         * Used by the hash table of devices indexed by devman device handles.
    152151         */
    153         link_t devman_dev;
     152        ht_link_t devman_dev;
    154153       
    155154        /**
    … …  
    204203         * Used by the hash table of functions indexed by devman device handles.
    205204         */
    206         link_t devman_fun;
     205        ht_link_t devman_fun;
    207206       
    208207        /**
    209208         * Used by the hash table of functions indexed by service IDs.
    210209         */
    211         link_t loc_fun;
     210        ht_link_t loc_fun;
    212211};
    213212

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

    r87e9392 r062d900  
    3737 */
    3838
     39#include "cdfs_ops.h"
    3940#include <bool.h>
    4041#include <adt/hash_table.h>
     42#include <adt/hash.h>
    4143#include <malloc.h>
    4244#include <mem.h>
    … …  
    5052#include "cdfs.h"
    5153#include "cdfs_endian.h"
    52 #include "cdfs_ops.h"
    5354
    5455/** Standard CD-ROM block size */
    5556#define BLOCK_SIZE  2048
    5657
    57 /** Implicit node cache size
    58  *
    59  * More nodes can be actually cached if the files remain
    60  * opended.
    61  *
    62  */
    63 #define NODE_CACHE_SIZE  200
    64 
    65 #define NODES_BUCKETS  256
    66 
    67 #define NODES_KEY_SRVC   0
    68 #define NODES_KEY_INDEX  1
     58#define NODE_CACHE_SIZE 200
    6959
    7060/** All root nodes have index 0 */
    … …  
    205195        service_id_t service_id;  /**< Service ID of block device */
    206196       
    207         link_t nh_link;           /**< Nodes hash table link */
     197        ht_link_t nh_link;        /**< Nodes hash table link */
    208198        cdfs_dentry_type_t type;  /**< Dentry type */
    209199       
    … …  
    226216static hash_table_t nodes;
    227217
    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:
    240                 return (node->service_id == key[NODES_KEY_SRVC]);
    241         case 2:
    242                 return ((node->service_id == key[NODES_KEY_SRVC]) &&
    243                     (node->index == key[NODES_KEY_INDEX]));
    244         default:
    245                 assert((keys == 1) || (keys == 2));
    246         }
    247        
    248         return 0;
    249 }
    250 
    251 static void nodes_remove_callback(link_t *item)
    252 {
    253         cdfs_node_t *node =
    254             hash_table_get_instance(item, cdfs_node_t, nh_link);
     218/*
     219 * Hash table support functions.
     220 */
     221
     222typedef struct {
     223        service_id_t service_id;
     224    fs_index_t index;
     225} ht_key_t;
     226
     227static size_t nodes_key_hash(void *k)
     228{
     229        ht_key_t *key = (ht_key_t*)k;
     230        return hash_combine(key->service_id, key->index);
     231}
     232
     233static size_t nodes_hash(const ht_link_t *item)
     234{
     235        cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link);
     236        return hash_combine(node->service_id, node->index);
     237}
     238
     239static bool nodes_key_equal(void *k, const ht_link_t *item)
     240{
     241        cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link);
     242        ht_key_t *key = (ht_key_t*)k;
     243       
     244        return key->service_id == node->service_id && key->index == node->index;
     245}
     246
     247static void nodes_remove_callback(ht_link_t *item)
     248{
     249        cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link);
    255250       
    256251        assert(node->type == CDFS_DIRECTORY);
    … …  
    268263
    269264/** Nodes hash table operations */
    270 static hash_table_operations_t nodes_ops = {
     265static hash_table_ops_t nodes_ops = {
    271266        .hash = nodes_hash,
    272         .compare = nodes_compare,
     267        .key_hash = nodes_key_hash,
     268        .key_equal = nodes_key_equal,
     269        .equal = 0,
    273270        .remove_callback = nodes_remove_callback
    274271};
    … …  
    277274    fs_index_t index)
    278275{
    279         unsigned long key[] = {
    280                 [NODES_KEY_SRVC] = service_id,
    281                 [NODES_KEY_INDEX] = index
     276        ht_key_t key = {
     277                .index = index,
     278                .service_id = service_id
    282279        };
    283280       
    284         link_t *link = hash_table_find(&nodes, key);
     281        ht_link_t *link = hash_table_find(&nodes, &key);
    285282        if (link) {
    286283                cdfs_node_t *node =
    287                     hash_table_get_instance(link, cdfs_node_t, nh_link);
     284                    hash_table_get_inst(link, cdfs_node_t, nh_link);
    288285               
    289286                *rfn = FS_NODE(node);
    … …  
    311308        node->opened = 0;
    312309       
    313         link_initialize(&node->nh_link);
    314310        list_initialize(&node->cs_list);
    315311}
    … …  
    353349       
    354350        /* 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);
     351        hash_table_insert(&nodes, &node->nh_link);
    361352       
    362353        *rfn = FS_NODE(node);
    … …  
    508499static fs_node_t *get_cached_node(service_id_t service_id, fs_index_t index)
    509500{
    510         unsigned long key[] = {
    511                 [NODES_KEY_SRVC] = service_id,
    512                 [NODES_KEY_INDEX] = index
     501        ht_key_t key = {
     502                .index = index,
     503                .service_id = service_id
    513504        };
    514505       
    515         link_t *link = hash_table_find(&nodes, key);
     506        ht_link_t *link = hash_table_find(&nodes, &key);
    516507        if (link) {
    517508                cdfs_node_t *node =
    518                     hash_table_get_instance(link, cdfs_node_t, nh_link);
     509                    hash_table_get_inst(link, cdfs_node_t, nh_link);
    519510                return FS_NODE(node);
    520511        }
    … …  
    802793}
    803794
     795static bool rm_service_id_nodes(ht_link_t *item, void *arg)
     796{
     797        service_id_t service_id = *(service_id_t*)arg;
     798        cdfs_node_t *node = hash_table_get_inst(item, cdfs_node_t, nh_link);
     799       
     800        if (node->service_id == service_id) {
     801                hash_table_remove_item(&nodes, &node->nh_link);
     802        }
     803       
     804        return true;
     805}
     806
    804807static void cdfs_instance_done(service_id_t service_id)
    805808{
    806         unsigned long key[] = {
    807                 [NODES_KEY_SRVC] = service_id
    808         };
    809        
    810         hash_table_remove(&nodes, key, 1);
     809        hash_table_apply(&nodes, rm_service_id_nodes, &service_id);
    811810        block_cache_fini(service_id);
    812811        block_fini(service_id);
    … …  
    822821    size_t *rbytes)
    823822{
    824         unsigned long key[] = {
    825                 [NODES_KEY_SRVC] = service_id,
    826                 [NODES_KEY_INDEX] = index
     823        ht_key_t key = {
     824                .index = index,
     825                .service_id = service_id
    827826        };
    828827       
    829         link_t *link = hash_table_find(&nodes, key);
     828        ht_link_t *link = hash_table_find(&nodes, &key);
    830829        if (link == NULL)
    831830                return ENOENT;
    832831       
    833832        cdfs_node_t *node =
    834             hash_table_get_instance(link, cdfs_node_t, nh_link);
     833            hash_table_get_inst(link, cdfs_node_t, nh_link);
    835834       
    836835        if (!node->processed) {
    … …  
    912911}
    913912
     913static bool cache_remove_closed(ht_link_t *item, void *arg)
     914{
     915        size_t *premove_cnt = (size_t*)arg;
     916       
     917        /* Some nodes were requested to be removed from the cache. */
     918        if (0 < *premove_cnt) {
     919                cdfs_node_t *node =     hash_table_get_inst(item, cdfs_node_t, nh_link);
     920
     921                if (!node->opened) {
     922                        hash_table_remove_item(&nodes, item);
     923                       
     924                        --nodes_cached;
     925                        --*premove_cnt;
     926                }
     927        }
     928       
     929        /* Only continue if more nodes were requested to be removed. */
     930        return 0 < *premove_cnt;
     931}
     932
    914933static void cleanup_cache(service_id_t service_id)
    915934{
    916935        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                 }
     936                size_t remove_cnt = nodes_cached - NODE_CACHE_SIZE;
     937               
     938                if (0 < remove_cnt)
     939                        hash_table_apply(&nodes, cache_remove_closed, &remove_cnt);
    944940        }
    945941}
    … …  
    951947                return EOK;
    952948       
    953         unsigned long key[] = {
    954                 [NODES_KEY_SRVC] = service_id,
    955                 [NODES_KEY_INDEX] = index
     949        ht_key_t key = {
     950                .index = index,
     951                .service_id = service_id
    956952        };
    957953       
    958         link_t *link = hash_table_find(&nodes, key);
     954        ht_link_t *link = hash_table_find(&nodes, &key);
    959955        if (link == 0)
    960956                return ENOENT;
    961957       
    962958        cdfs_node_t *node =
    963             hash_table_get_instance(link, cdfs_node_t, nh_link);
     959            hash_table_get_inst(link, cdfs_node_t, nh_link);
    964960       
    965961        assert(node->opened > 0);
    … …  
    10071003bool cdfs_init(void)
    10081004{
    1009         if (!hash_table_create(&nodes, NODES_BUCKETS, 2, &nodes_ops))
     1005        if (!hash_table_create(&nodes, 0, 0, &nodes_ops))
    10101006                return false;
    10111007       

  • uspace/srv/fs/exfat/exfat.h

    r87e9392 r062d900  
    106106typedef struct {
    107107        /** Used indices (position) hash table link. */
    108         link_t          uph_link;
     108        ht_link_t               uph_link;
    109109        /** Used indices (index) hash table link. */
    110         link_t          uih_link;
     110        ht_link_t               uih_link;
    111111
    112112        fibril_mutex_t  lock;

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

    r87e9392 r062d900  
    4141#include <str.h>
    4242#include <adt/hash_table.h>
     43#include <adt/hash.h>
    4344#include <adt/list.h>
    4445#include <assert.h>
    … …  
    9192        if (lock)
    9293                fibril_mutex_lock(&unused_lock);
     94
    9395        list_foreach(unused_list, l) {
    9496                u = list_get_instance(l, unused_t, link);
    … …  
    112114static hash_table_t up_hash;
    113115
    114 #define UPH_BUCKETS_LOG 12
    115 #define UPH_BUCKETS     (1 << UPH_BUCKETS_LOG)
    116 
    117 #define UPH_SID_KEY     0
    118 #define UPH_PFC_KEY     1
    119 #define UPH_PDI_KEY     2
    120 
    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)
    150 {
    151         service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
     116typedef struct {
     117        service_id_t service_id;
    152118        exfat_cluster_t pfc;
    153119        unsigned pdi;
    154         exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uph_link);
    155 
    156         switch (keys) {
    157         case 1:
    158                 return (service_id == fidx->service_id);
    159         case 3:
    160                 pfc = (exfat_cluster_t) key[UPH_PFC_KEY];
    161                 pdi = (unsigned) key[UPH_PDI_KEY];
    162                 return (service_id == fidx->service_id) && (pfc == fidx->pfc) &&
    163                     (pdi == fidx->pdi);
    164         default:
    165                 assert((keys == 1) || (keys == 3));
    166         }
    167 
    168         return 0;
    169 }
    170 
    171 static void pos_remove_callback(link_t *item)
    172 {
    173         /* nothing to do */
    174 }
    175 
    176 static hash_table_operations_t uph_ops = {
     120} pos_key_t;
     121
     122static inline size_t pos_key_hash(void *key)
     123{
     124        pos_key_t *pos = (pos_key_t*)key;
     125       
     126        size_t hash = 0;
     127        hash = hash_combine(pos->pfc, pos->pdi);
     128        return hash_combine(hash, pos->service_id);
     129}
     130
     131static size_t pos_hash(const ht_link_t *item)
     132{
     133        exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uph_link);
     134       
     135        pos_key_t pkey = {
     136                .service_id = fidx->service_id,
     137                .pfc = fidx->pfc,
     138                .pdi = fidx->pdi,
     139        };
     140       
     141        return pos_key_hash(&pkey);
     142}
     143
     144static bool pos_key_equal(void *key, const ht_link_t *item)
     145{
     146        pos_key_t *pos = (pos_key_t*)key;
     147        exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uph_link);
     148       
     149        return pos->service_id == fidx->service_id
     150                && pos->pdi == fidx->pdi
     151                && pos->pfc == fidx->pfc;
     152}
     153
     154static hash_table_ops_t uph_ops = {
    177155        .hash = pos_hash,
    178         .compare = pos_compare,
    179         .remove_callback = pos_remove_callback,
     156        .key_hash = pos_key_hash,
     157        .key_equal = pos_key_equal,
     158        .equal = 0,
     159        .remove_callback = 0,
    180160};
    181161
    … …  
    186166static hash_table_t ui_hash;
    187167
    188 #define UIH_BUCKETS_LOG 12
    189 #define UIH_BUCKETS     (1 << UIH_BUCKETS_LOG)
    190 
    191 #define UIH_SID_KEY     0
    192 #define UIH_INDEX_KEY   1
    193 
    194 static hash_index_t idx_hash(unsigned long key[])
    195 {
    196         service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
    197         fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
    198 
    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)
    209 {
    210         service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
     168typedef struct {
     169        service_id_t service_id;
    211170        fs_index_t index;
    212         exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uih_link);
    213 
    214         switch (keys) {
    215         case 1:
    216                 return (service_id == fidx->service_id);
    217         case 2:
    218                 index = (fs_index_t) key[UIH_INDEX_KEY];
    219                 return (service_id == fidx->service_id) &&
    220                     (index == fidx->index);
    221         default:
    222                 assert((keys == 1) || (keys == 2));
    223         }
    224 
    225         return 0;
    226 }
    227 
    228 static void idx_remove_callback(link_t *item)
    229 {
    230         exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uih_link);
     171} idx_key_t;
     172
     173static size_t idx_key_hash(void *key_arg)
     174{
     175        idx_key_t *key = (idx_key_t*)key_arg;
     176        return hash_combine(key->service_id, key->index);
     177}
     178
     179static size_t idx_hash(const ht_link_t *item)
     180{
     181        exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link);
     182        return hash_combine(fidx->service_id, fidx->index);
     183}
     184
     185static bool idx_key_equal(void *key_arg, const ht_link_t *item)
     186{
     187        exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link);
     188        idx_key_t *key = (idx_key_t*)key_arg;
     189       
     190        return key->index == fidx->index && key->service_id == fidx->service_id;
     191}
     192
     193static void idx_remove_callback(ht_link_t *item)
     194{
     195        exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link);
    231196
    232197        free(fidx);
    233198}
    234199
    235 static hash_table_operations_t uih_ops = {
     200static hash_table_ops_t uih_ops = {
    236201        .hash = idx_hash,
    237         .compare = idx_compare,
     202        .key_hash = idx_key_hash,
     203        .key_equal = idx_key_equal,
     204        .equal = 0,
    238205        .remove_callback = idx_remove_callback,
    239206};
    … …  
    376343        }
    377344               
    378         link_initialize(&fidx->uph_link);
    379         link_initialize(&fidx->uih_link);
    380345        fibril_mutex_initialize(&fidx->lock);
    381346        fidx->service_id = service_id;
    … …  
    400365        }
    401366               
    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);
     367        hash_table_insert(&ui_hash, &fidx->uih_link);
    408368        fibril_mutex_lock(&fidx->lock);
    409369        fibril_mutex_unlock(&used_lock);
    … …  
    417377{
    418378        exfat_idx_t *fidx;
    419         link_t *l;
    420         unsigned long pkey[] = {
    421                 [UPH_SID_KEY] = service_id,
    422                 [UPH_PFC_KEY] = pfc,
    423                 [UPH_PDI_KEY] = pdi,
     379       
     380        pos_key_t pos_key = {
     381                .service_id = service_id,
     382                .pfc = pfc,
     383                .pdi = pdi,
    424384        };
    425385
    426386        fibril_mutex_lock(&used_lock);
    427         l = hash_table_find(&up_hash, pkey);
     387        ht_link_t *l = hash_table_find(&up_hash, &pos_key);
    428388        if (l) {
    429                 fidx = hash_table_get_instance(l, exfat_idx_t, uph_link);
     389                fidx = hash_table_get_inst(l, exfat_idx_t, uph_link);
    430390        } else {
    431391                int rc;
    … …  
    437397                }
    438398               
    439                 unsigned long ikey[] = {
    440                         [UIH_SID_KEY] = service_id,
    441                         [UIH_INDEX_KEY] = fidx->index,
    442                 };
    443        
    444399                fidx->pfc = pfc;
    445400                fidx->pdi = pdi;
    446401
    447                 hash_table_insert(&up_hash, pkey, &fidx->uph_link);
    448                 hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
     402                hash_table_insert(&up_hash, &fidx->uph_link);
     403                hash_table_insert(&ui_hash, &fidx->uih_link);
    449404        }
    450405        fibril_mutex_lock(&fidx->lock);
    … …  
    456411void exfat_idx_hashin(exfat_idx_t *idx)
    457412{
    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);
     413        fibril_mutex_lock(&used_lock);
     414        hash_table_insert(&up_hash, &idx->uph_link);
    466415        fibril_mutex_unlock(&used_lock);
    467416}
    … …  
    469418void exfat_idx_hashout(exfat_idx_t *idx)
    470419{
    471         unsigned long pkey[] = {
    472                 [UPH_SID_KEY] = idx->service_id,
    473                 [UPH_PFC_KEY] = idx->pfc,
    474                 [UPH_PDI_KEY] = idx->pdi,
    475         };
    476 
    477         fibril_mutex_lock(&used_lock);
    478         hash_table_remove(&up_hash, pkey, 3);
     420        fibril_mutex_lock(&used_lock);
     421        hash_table_remove_item(&up_hash, &idx->uph_link);
    479422        fibril_mutex_unlock(&used_lock);
    480423}
    … …  
    484427{
    485428        exfat_idx_t *fidx = NULL;
    486         link_t *l;
    487         unsigned long ikey[] = {
    488                 [UIH_SID_KEY] = service_id,
    489                 [UIH_INDEX_KEY] = index,
     429
     430        idx_key_t idx_key = {
     431                .service_id = service_id,
     432                .index = index,
    490433        };
    491434
    492435        fibril_mutex_lock(&used_lock);
    493         l = hash_table_find(&ui_hash, ikey);
     436        ht_link_t *l = hash_table_find(&ui_hash, &idx_key);
    494437        if (l) {
    495                 fidx = hash_table_get_instance(l, exfat_idx_t, uih_link);
     438                fidx = hash_table_get_inst(l, exfat_idx_t, uih_link);
    496439                fibril_mutex_lock(&fidx->lock);
    497440        }
    … …  
    507450void exfat_idx_destroy(exfat_idx_t *idx)
    508451{
    509         unsigned long ikey[] = {
    510                 [UIH_SID_KEY] = idx->service_id,
    511                 [UIH_INDEX_KEY] = idx->index,
     452        idx_key_t idx_key = {
     453                .service_id = idx->service_id,
     454                .index = idx->index,
    512455        };
    513         service_id_t service_id = idx->service_id;
    514         fs_index_t index = idx->index;
    515456
    516457        /* TODO: assert(idx->pfc == FAT_CLST_RES0); */
    … …  
    523464         * the index hash only.
    524465         */
    525         hash_table_remove(&ui_hash, ikey, 2);
     466        hash_table_remove(&ui_hash, &idx_key);
    526467        fibril_mutex_unlock(&used_lock);
    527468        /* Release the VFS index. */
    528         exfat_index_free(service_id, index);
     469        exfat_index_free(idx_key.service_id, idx_key.index);
    529470        /* The index structure itself is freed in idx_remove_callback(). */
    530471}
    … …  
    532473int exfat_idx_init(void)
    533474{
    534         if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))
     475        if (!hash_table_create(&up_hash, 0, 0, &uph_ops))
    535476                return ENOMEM;
    536         if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
     477        if (!hash_table_create(&ui_hash, 0, 0, &uih_ops)) {
    537478                hash_table_destroy(&up_hash);
    538479                return ENOMEM;
    … …  
    544485{
    545486        /* We assume the hash tables are empty. */
     487        assert(hash_table_empty(&up_hash) && hash_table_empty(&ui_hash));
    546488        hash_table_destroy(&up_hash);
    547489        hash_table_destroy(&ui_hash);
    … …  
    568510}
    569511
     512static bool rm_pos_service_id(ht_link_t *item, void *arg)
     513{
     514        service_id_t service_id = *(service_id_t*)arg;
     515        exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uph_link);
     516
     517        if (fidx->service_id == service_id) {
     518                hash_table_remove_item(&up_hash, item);
     519        }
     520       
     521        return true;
     522}
     523
     524static bool rm_idx_service_id(ht_link_t *item, void *arg)
     525{
     526        service_id_t service_id = *(service_id_t*)arg;
     527        exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link);
     528
     529        if (fidx->service_id == service_id) {
     530                hash_table_remove_item(&ui_hash, item);
     531        }
     532       
     533        return true;
     534}
     535
    570536void exfat_idx_fini_by_service_id(service_id_t service_id)
    571537{
    572         unsigned long ikey[] = {
    573                 [UIH_SID_KEY] = service_id
    574         };
    575         unsigned long pkey[] = {
    576                 [UPH_SID_KEY] = service_id
    577         };
    578 
    579538        /*
    580539         * Remove this instance's index structure from up_hash and ui_hash.
    … …  
    583542         */
    584543        fibril_mutex_lock(&used_lock);
    585         hash_table_remove(&up_hash, pkey, 1);
    586         hash_table_remove(&ui_hash, ikey, 1);
     544        hash_table_apply(&up_hash, rm_pos_service_id, &service_id);
     545        hash_table_apply(&ui_hash, rm_idx_service_id, &service_id);
    587546        fibril_mutex_unlock(&used_lock);
    588547

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

    r87e9392 r062d900  
    5454#include <byteorder.h>
    5555#include <adt/hash_table.h>
     56#include <adt/hash.h>
    5657#include <adt/list.h>
    5758#include <assert.h>

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

    r87e9392 r062d900  
    4949#include <byteorder.h>
    5050#include <adt/hash_table.h>
     51#include <adt/hash.h>
    5152#include <adt/list.h>
    5253#include <assert.h>
    … …  
    6263#define EXT2FS_NODE(node)       ((node) ? (ext2fs_node_t *) (node)->data : NULL)
    6364#define EXT2FS_DBG(format, ...) {if (false) printf("ext2fs: %s: " format "\n", __FUNCTION__, ##__VA_ARGS__);}
    64 #define OPEN_NODES_KEYS 2
    65 #define OPEN_NODES_DEV_HANDLE_KEY 0
    66 #define OPEN_NODES_INODE_KEY 1
    67 #define OPEN_NODES_BUCKETS 256
    6865
    6966typedef struct ext2fs_instance {
    … …  
    7875        ext2_inode_ref_t *inode_ref;
    7976        fs_node_t *fs_node;
    80         link_t link;
     77        ht_link_t link;
    8178        unsigned int references;
    8279} ext2fs_node_t;
    … …  
    122119static FIBRIL_MUTEX_INITIALIZE(open_nodes_lock);
    123120
    124 /* 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)
    133 {
    134         ext2fs_node_t *enode = hash_table_get_instance(item, ext2fs_node_t, link);
    135         assert(keys > 0);
    136         if (enode->instance->service_id !=
    137             ((service_id_t) key[OPEN_NODES_DEV_HANDLE_KEY])) {
    138                 return false;
    139         }
    140         if (keys == 1) {
    141                 return true;
    142         }
    143         assert(keys == 2);
    144         return (enode->inode_ref->index == key[OPEN_NODES_INODE_KEY]);
    145 }
    146 
    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 = {
     121/*
     122 * Hash table interface for open nodes hash table
     123 */
     124
     125typedef struct {
     126        service_id_t service_id;
     127        fs_index_t index;
     128} node_key_t;
     129
     130static size_t open_nodes_key_hash(void *key)
     131{
     132        node_key_t *node_key = (node_key_t*)key;
     133        return hash_combine(node_key->service_id, node_key->index);
     134}
     135
     136static size_t open_nodes_hash(const ht_link_t *item)
     137{
     138        ext2fs_node_t *enode = hash_table_get_inst(item, ext2fs_node_t, link);
     139
     140        assert(enode->instance);
     141        assert(enode->inode_ref);
     142       
     143        return hash_combine(enode->instance->service_id, enode->inode_ref->index);
     144}
     145
     146static bool open_nodes_key_equal(void *key, const ht_link_t *item)
     147{
     148        node_key_t *node_key = (node_key_t*)key;
     149        ext2fs_node_t *enode = hash_table_get_inst(item, ext2fs_node_t, link);
     150       
     151        return node_key->service_id == enode->instance->service_id
     152                && node_key->index == enode->inode_ref->index;
     153}
     154
     155static hash_table_ops_t open_nodes_ops = {
    153156        .hash = open_nodes_hash,
    154         .compare = open_nodes_compare,
    155         .remove_callback = open_nodes_remove_cb,
     157        .key_hash = open_nodes_key_hash,
     158        .key_equal = open_nodes_key_equal,
     159        .equal = 0,
     160        .remove_callback = 0,
    156161};
    157162
    … …  
    161166int ext2fs_global_init(void)
    162167{
    163         if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS,
    164             OPEN_NODES_KEYS, &open_nodes_ops)) {
     168        if (!hash_table_create(&open_nodes, 0, 0, &open_nodes_ops)) {
    165169                return ENOMEM;
    166170        }
    … …  
    316320       
    317321        /* Check if the node is not already open */
    318         unsigned long key[] = {
    319                 [OPEN_NODES_DEV_HANDLE_KEY] = inst->service_id,
    320                 [OPEN_NODES_INODE_KEY] = index,
     322        node_key_t key = {
     323                .service_id = inst->service_id,
     324                .index = index
    321325        };
    322         link_t *already_open = hash_table_find(&open_nodes, key);
     326        ht_link_t *already_open = hash_table_find(&open_nodes, &key);
    323327
    324328        if (already_open) {
    325                 enode = hash_table_get_instance(already_open, ext2fs_node_t, link);
     329                enode = hash_table_get_inst(already_open, ext2fs_node_t, link);
    326330                *rfn = enode->fs_node;
    327331                enode->references++;
    … …  
    357361        enode->references = 1;
    358362        enode->fs_node = node;
    359         link_initialize(&enode->link);
    360363       
    361364        node->data = enode;
    362365        *rfn = node;
    363366       
    364         hash_table_insert(&open_nodes, key, &enode->link);
     367        hash_table_insert(&open_nodes, &enode->link);
    365368        inst->open_nodes_count++;
    366369       
    … …  
    408411int ext2fs_node_put_core(ext2fs_node_t *enode)
    409412{
    410         int rc;
    411 
    412         unsigned long key[] = {
    413                 [OPEN_NODES_DEV_HANDLE_KEY] = enode->instance->service_id,
    414                 [OPEN_NODES_INODE_KEY] = enode->inode_ref->index,
     413        node_key_t key = {
     414                .service_id = enode->instance->service_id,
     415                .index = enode->inode_ref->index
    415416        };
    416         hash_table_remove(&open_nodes, key, OPEN_NODES_KEYS);
     417
     418        hash_table_remove(&open_nodes, &key);
     419       
    417420        assert(enode->instance->open_nodes_count > 0);
    418421        enode->instance->open_nodes_count--;
    419422
    420         rc = ext2_filesystem_put_inode_ref(enode->inode_ref);
     423        int rc = ext2_filesystem_put_inode_ref(enode->inode_ref);
    421424        if (rc != EOK) {
    422425                EXT2FS_DBG("ext2_filesystem_put_inode_ref failed");

  • uspace/srv/fs/ext4fs/ext4fs_ops.c

    r87e9392 r062d900  
    4242#include <malloc.h>
    4343#include <adt/hash_table.h>
     44#include <adt/hash.h>
    4445#include <ipc/loc.h>
    4546#include "ext4fs.h"
    … …  
    4849#define EXT4FS_NODE(node) \
    4950        ((node) ? (ext4fs_node_t *) (node)->data : NULL)
    50 
    51 #define OPEN_NODES_KEYS  2
    52 
    53 #define OPEN_NODES_DEV_HANDLE_KEY  0
    54 #define OPEN_NODES_INODE_KEY       1
    55 
    56 #define OPEN_NODES_BUCKETS  256
    5751
    5852/**
    … …  
    7367        ext4_inode_ref_t *inode_ref;
    7468        fs_node_t *fs_node;
    75         link_t link;
     69        ht_link_t link;
    7670        unsigned int references;
    7771} ext4fs_node_t;
    … …  
    115109
    116110/* Hash table interface for open nodes hash table */
    117 static hash_index_t open_nodes_hash(unsigned long key[])
    118 {
    119         /* TODO: This is very simple and probably can be improved */
    120         return key[OPEN_NODES_INODE_KEY] % OPEN_NODES_BUCKETS;
    121 }
    122 
    123 /** Compare given item with values in hash table.
    124  *
    125  */
    126 static int open_nodes_compare(unsigned long key[], hash_count_t keys,
    127     link_t *item)
    128 {
    129         assert(keys > 0);
    130        
    131         ext4fs_node_t *enode =
    132             hash_table_get_instance(item, ext4fs_node_t, link);
    133        
    134         if (enode->instance->service_id !=
    135             ((service_id_t) key[OPEN_NODES_DEV_HANDLE_KEY]))
    136                 return false;
    137        
    138         if (keys == 1)
    139                 return true;
    140        
    141         assert(keys == 2);
    142        
    143         return (enode->inode_ref->index == key[OPEN_NODES_INODE_KEY]);
    144 }
    145 
    146 /** Empty callback to correct hash table initialization.
    147  *
    148  */
    149 static void open_nodes_remove_cb(link_t *link)
    150 {
    151         /* We don't use remove callback for this hash table */
    152 }
    153 
    154 static hash_table_operations_t open_nodes_ops = {
     111
     112typedef struct {
     113        service_id_t service_id;
     114        fs_index_t index;
     115} node_key_t;
     116
     117static size_t open_nodes_key_hash(void *key_arg)
     118{
     119        node_key_t *key = (node_key_t *)key_arg;
     120        return hash_combine(key->service_id, key->index);
     121}
     122
     123static size_t open_nodes_hash(const ht_link_t *item)
     124{
     125        ext4fs_node_t *enode = hash_table_get_inst(item, ext4fs_node_t, link);
     126        return hash_combine(enode->instance->service_id, enode->inode_ref->index);     
     127}
     128
     129static bool open_nodes_key_equal(void *key_arg, const ht_link_t *item)
     130{
     131        node_key_t *key = (node_key_t *)key_arg;
     132        ext4fs_node_t *enode = hash_table_get_inst(item, ext4fs_node_t, link);
     133       
     134        return key->service_id == enode->instance->service_id
     135                && key->index == enode->inode_ref->index;
     136}
     137
     138static hash_table_ops_t open_nodes_ops = {
    155139        .hash = open_nodes_hash,
    156         .compare = open_nodes_compare,
    157         .remove_callback = open_nodes_remove_cb,
     140        .key_hash = open_nodes_key_hash,
     141        .key_equal = open_nodes_key_equal,
     142        .equal = NULL,
     143        .remove_callback = NULL,
    158144};
    159145
    … …  
    168154int ext4fs_global_init(void)
    169155{
    170         if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS,
    171             OPEN_NODES_KEYS, &open_nodes_ops))
     156        if (!hash_table_create(&open_nodes, 0, 0, &open_nodes_ops))
    172157                return ENOMEM;
    173158       
    … …  
    315300       
    316301        /* Check if the node is not already open */
    317         unsigned long key[] = {
    318                 [OPEN_NODES_DEV_HANDLE_KEY] = inst->service_id,
    319                 [OPEN_NODES_INODE_KEY] = index
     302        node_key_t key = {
     303                .service_id = inst->service_id,
     304                .index = index
    320305        };
    321306       
    322         link_t *already_open = hash_table_find(&open_nodes, key);
     307        ht_link_t *already_open = hash_table_find(&open_nodes, &key);
    323308        ext4fs_node_t *enode = NULL;
    324309        if (already_open) {
    325                 enode = hash_table_get_instance(already_open, ext4fs_node_t, link);
     310                enode = hash_table_get_inst(already_open, ext4fs_node_t, link);
    326311                *rfn = enode->fs_node;
    327312                enode->references++;
    … …  
    364349        enode->references = 1;
    365350        enode->fs_node = fs_node;
    366         link_initialize(&enode->link);
    367351       
    368352        fs_node->data = enode;
    369353        *rfn = fs_node;
    370354       
    371         hash_table_insert(&open_nodes, key, &enode->link);
     355        hash_table_insert(&open_nodes, &enode->link);
    372356        inst->open_nodes_count++;
    373357       
    … …  
    386370int ext4fs_node_put_core(ext4fs_node_t *enode)
    387371{
    388         unsigned long key[] = {
    389                 [OPEN_NODES_DEV_HANDLE_KEY] = enode->instance->service_id,
    390                 [OPEN_NODES_INODE_KEY] = enode->inode_ref->index
    391         };
    392        
    393         hash_table_remove(&open_nodes, key, OPEN_NODES_KEYS);
     372        hash_table_remove_item(&open_nodes, &enode->link);
    394373        assert(enode->instance->open_nodes_count > 0);
    395374        enode->instance->open_nodes_count--;
    … …  
    498477        enode->references = 1;
    499478       
    500         link_initialize(&enode->link);
    501        
    502         unsigned long key[] = {
    503                 [OPEN_NODES_DEV_HANDLE_KEY] = inst->service_id,
    504                 [OPEN_NODES_INODE_KEY] = inode_ref->index
    505         };
    506        
    507479        fibril_mutex_lock(&open_nodes_lock);
    508         hash_table_insert(&open_nodes, key, &enode->link);
     480        hash_table_insert(&open_nodes, &enode->link);
    509481        fibril_mutex_unlock(&open_nodes_lock);
    510482        inst->open_nodes_count++;

  • uspace/srv/fs/fat/fat.h

    r87e9392 r062d900  
    190190typedef struct {
    191191        /** Used indices (position) hash table link. */
    192         link_t          uph_link;
     192        ht_link_t               uph_link;
    193193        /** Used indices (index) hash table link. */
    194         link_t          uih_link;
     194        ht_link_t               uih_link;
    195195
    196196        fibril_mutex_t  lock;

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

    r87e9392 r062d900  
    4141#include <str.h>
    4242#include <adt/hash_table.h>
     43#include <adt/hash.h>
    4344#include <adt/list.h>
    4445#include <assert.h>
    … …  
    5859 */
    5960typedef struct {
    60         link_t          link;
    61         service_id_t    service_id;
     61        link_t link;
     62        service_id_t service_id;
    6263
    6364        /** Next unassigned index. */
    … …  
    9798                        return u;
    9899        }
    99        
     100
    100101        if (lock)
    101102                fibril_mutex_unlock(&unused_lock);
    … …  
    113114static hash_table_t up_hash;
    114115
    115 #define UPH_BUCKETS_LOG 12
    116 #define UPH_BUCKETS     (1 << UPH_BUCKETS_LOG)
    117 
    118 #define UPH_SID_KEY     0
    119 #define UPH_PFC_KEY     1
    120 #define UPH_PDI_KEY     2
    121 
    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)
    151 {
    152         service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
     116typedef struct {
     117        service_id_t service_id;
    153118        fat_cluster_t pfc;
    154119        unsigned pdi;
    155         fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link);
    156 
    157         switch (keys) {
    158         case 1:
    159                 return (service_id == fidx->service_id);
    160         case 3:
    161                 pfc = (fat_cluster_t) key[UPH_PFC_KEY];
    162                 pdi = (unsigned) key[UPH_PDI_KEY];
    163                 return (service_id == fidx->service_id) && (pfc == fidx->pfc) &&
    164                     (pdi == fidx->pdi);
    165         default:
    166                 assert((keys == 1) || (keys == 3));
    167         }
    168 
    169         return 0;
    170 }
    171 
    172 static void pos_remove_callback(link_t *item)
    173 {
    174         /* nothing to do */
    175 }
    176 
    177 static hash_table_operations_t uph_ops = {
     120} pos_key_t;
     121
     122static inline size_t pos_key_hash(void *key)
     123{
     124        pos_key_t *pos = (pos_key_t*)key;
     125       
     126        size_t hash = 0;
     127        hash = hash_combine(pos->pfc, pos->pdi);
     128        return hash_combine(hash, pos->service_id);
     129}
     130
     131static size_t pos_hash(const ht_link_t *item)
     132{
     133        fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uph_link);
     134       
     135        pos_key_t pkey = {
     136                .service_id = fidx->service_id,
     137                .pfc = fidx->pfc,
     138                .pdi = fidx->pdi,
     139        };
     140       
     141        return pos_key_hash(&pkey);
     142}
     143
     144static bool pos_key_equal(void *key, const ht_link_t *item)
     145{
     146        pos_key_t *pos = (pos_key_t*)key;
     147        fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uph_link);
     148       
     149        return pos->service_id == fidx->service_id
     150                && pos->pdi == fidx->pdi
     151                && pos->pfc == fidx->pfc;
     152}
     153
     154static hash_table_ops_t uph_ops = {
    178155        .hash = pos_hash,
    179         .compare = pos_compare,
    180         .remove_callback = pos_remove_callback,
     156        .key_hash = pos_key_hash,
     157        .key_equal = pos_key_equal,
     158        .equal = 0,
     159        .remove_callback = 0,
    181160};
    182161
    … …  
    187166static hash_table_t ui_hash;
    188167
    189 #define UIH_BUCKETS_LOG 12
    190 #define UIH_BUCKETS     (1 << UIH_BUCKETS_LOG)
    191 
    192 #define UIH_SID_KEY     0
    193 #define UIH_INDEX_KEY   1
    194 
    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)
    210 {
    211         service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
     168typedef struct {
     169        service_id_t service_id;
    212170        fs_index_t index;
    213         fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
    214 
    215         switch (keys) {
    216         case 1:
    217                 return (service_id == fidx->service_id);
    218         case 2:
    219                 index = (fs_index_t) key[UIH_INDEX_KEY];
    220                 return (service_id == fidx->service_id) &&
    221                     (index == fidx->index);
    222         default:
    223                 assert((keys == 1) || (keys == 2));
    224         }
    225 
    226         return 0;
    227 }
    228 
    229 static void idx_remove_callback(link_t *item)
    230 {
    231         fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
     171} idx_key_t;
     172
     173static size_t idx_key_hash(void *key_arg)
     174{
     175        idx_key_t *key = (idx_key_t*)key_arg;
     176        return hash_combine(key->service_id, key->index);
     177}
     178
     179static size_t idx_hash(const ht_link_t *item)
     180{
     181        fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uih_link);
     182        return hash_combine(fidx->service_id, fidx->index);
     183}
     184
     185static bool idx_key_equal(void *key_arg, const ht_link_t *item)
     186{
     187        fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uih_link);
     188        idx_key_t *key = (idx_key_t*)key_arg;
     189       
     190        return key->index == fidx->index && key->service_id == fidx->service_id;
     191}
     192
     193static void idx_remove_callback(ht_link_t *item)
     194{
     195        fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uih_link);
    232196
    233197        free(fidx);
    234198}
    235199
    236 static hash_table_operations_t uih_ops = {
     200static hash_table_ops_t uih_ops = {
    237201        .hash = idx_hash,
    238         .compare = idx_compare,
     202        .key_hash = idx_key_hash,
     203        .key_equal = idx_key_equal,
     204        .equal = 0,
    239205        .remove_callback = idx_remove_callback,
    240206};
    … …  
    377343        }
    378344               
    379         link_initialize(&fidx->uph_link);
    380         link_initialize(&fidx->uih_link);
    381345        fibril_mutex_initialize(&fidx->lock);
    382346        fidx->service_id = service_id;
    … …  
    401365        }
    402366               
    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);
     367        hash_table_insert(&ui_hash, &fidx->uih_link);
    409368        fibril_mutex_lock(&fidx->lock);
    410369        fibril_mutex_unlock(&used_lock);
    … …  
    418377{
    419378        fat_idx_t *fidx;
    420         link_t *l;
    421         unsigned long pkey[] = {
    422                 [UPH_SID_KEY] = service_id,
    423                 [UPH_PFC_KEY] = pfc,
    424                 [UPH_PDI_KEY] = pdi,
     379
     380        pos_key_t pos_key = {
     381                .service_id = service_id,
     382                .pfc = pfc,
     383                .pdi = pdi,
    425384        };
    426385
    427386        fibril_mutex_lock(&used_lock);
    428         l = hash_table_find(&up_hash, pkey);
     387        ht_link_t *l = hash_table_find(&up_hash, &pos_key);
    429388        if (l) {
    430                 fidx = hash_table_get_instance(l, fat_idx_t, uph_link);
     389                fidx = hash_table_get_inst(l, fat_idx_t, uph_link);
    431390        } else {
    432391                int rc;
    … …  
    438397                }
    439398               
    440                 unsigned long ikey[] = {
    441                         [UIH_SID_KEY] = service_id,
    442                         [UIH_INDEX_KEY] = fidx->index,
    443                 };
    444        
    445399                fidx->pfc = pfc;
    446400                fidx->pdi = pdi;
    447401
    448                 hash_table_insert(&up_hash, pkey, &fidx->uph_link);
    449                 hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
     402                hash_table_insert(&up_hash, &fidx->uph_link);
     403                hash_table_insert(&ui_hash, &fidx->uih_link);
    450404        }
    451405        fibril_mutex_lock(&fidx->lock);
    … …  
    457411void fat_idx_hashin(fat_idx_t *idx)
    458412{
    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);
     413        fibril_mutex_lock(&used_lock);
     414        hash_table_insert(&up_hash, &idx->uph_link);
    467415        fibril_mutex_unlock(&used_lock);
    468416}
    … …  
    470418void fat_idx_hashout(fat_idx_t *idx)
    471419{
    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);
     420        fibril_mutex_lock(&used_lock);
     421        hash_table_remove_item(&up_hash, &idx->uph_link);
    480422        fibril_mutex_unlock(&used_lock);
    481423}
    … …  
    485427{
    486428        fat_idx_t *fidx = NULL;
    487         link_t *l;
    488         unsigned long ikey[] = {
    489                 [UIH_SID_KEY] = service_id,
    490                 [UIH_INDEX_KEY] = index,
     429
     430        idx_key_t idx_key = {
     431                .service_id = service_id,
     432                .index = index,
    491433        };
    492434
    493435        fibril_mutex_lock(&used_lock);
    494         l = hash_table_find(&ui_hash, ikey);
     436        ht_link_t *l = hash_table_find(&ui_hash, &idx_key);
    495437        if (l) {
    496                 fidx = hash_table_get_instance(l, fat_idx_t, uih_link);
     438                fidx = hash_table_get_inst(l, fat_idx_t, uih_link);
    497439                fibril_mutex_lock(&fidx->lock);
    498440        }
    … …  
    508450void fat_idx_destroy(fat_idx_t *idx)
    509451{
    510         unsigned long ikey[] = {
    511                 [UIH_SID_KEY] = idx->service_id,
    512                 [UIH_INDEX_KEY] = idx->index,
     452        idx_key_t idx_key = {
     453                .service_id = idx->service_id,
     454                .index = idx->index,
    513455        };
    514         service_id_t service_id = idx->service_id;
    515         fs_index_t index = idx->index;
    516456
    517457        assert(idx->pfc == FAT_CLST_RES0);
    … …  
    523463         * the index hash only.
    524464         */
    525         hash_table_remove(&ui_hash, ikey, 2);
     465        hash_table_remove(&ui_hash, &idx_key);
    526466        fibril_mutex_unlock(&used_lock);
    527467        /* Release the VFS index. */
    528         fat_index_free(service_id, index);
     468        fat_index_free(idx_key.service_id, idx_key.index);
    529469        /* The index structure itself is freed in idx_remove_callback(). */
    530470}
    … …  
    532472int fat_idx_init(void)
    533473{
    534         if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))
     474        if (!hash_table_create(&up_hash, 0, 0, &uph_ops))
    535475                return ENOMEM;
    536         if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
     476        if (!hash_table_create(&ui_hash, 0, 0, &uih_ops)) {
    537477                hash_table_destroy(&up_hash);
    538478                return ENOMEM;
    … …  
    544484{
    545485        /* We assume the hash tables are empty. */
     486        assert(hash_table_empty(&up_hash) && hash_table_empty(&ui_hash));
    546487        hash_table_destroy(&up_hash);
    547488        hash_table_destroy(&ui_hash);
    … …  
    568509}
    569510
     511static bool rm_pos_service_id(ht_link_t *item, void *arg)
     512{
     513        service_id_t service_id = *(service_id_t*)arg;
     514        fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uph_link);
     515
     516        if (fidx->service_id == service_id) {
     517                hash_table_remove_item(&up_hash, item);
     518        }
     519       
     520        return true;
     521}
     522
     523static bool rm_idx_service_id(ht_link_t *item, void *arg)
     524{
     525        service_id_t service_id = *(service_id_t*)arg;
     526        fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uih_link);
     527
     528        if (fidx->service_id == service_id) {
     529                hash_table_remove_item(&ui_hash, item);
     530        }
     531       
     532        return true;
     533}
     534
    570535void fat_idx_fini_by_service_id(service_id_t service_id)
    571536{
    572         unsigned long ikey[] = {
    573                 [UIH_SID_KEY] = service_id
    574         };
    575         unsigned long pkey[] = {
    576                 [UPH_SID_KEY] = service_id
    577         };
    578 
    579537        /*
    580538         * Remove this instance's index structure from up_hash and ui_hash.
    … …  
    583541         */
    584542        fibril_mutex_lock(&used_lock);
    585         hash_table_remove(&up_hash, pkey, 1);
    586         hash_table_remove(&ui_hash, ikey, 1);
     543        hash_table_apply(&up_hash, rm_pos_service_id, &service_id);
     544        hash_table_apply(&ui_hash, rm_idx_service_id, &service_id);
    587545        fibril_mutex_unlock(&used_lock);
    588546

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

    r87e9392 r062d900  
    6161        async_sess_t *sess;       /**< If NULL, the structure is incomplete. */
    6262        size_t refcount;
    63         link_t link;
     63        ht_link_t link;
    6464        fibril_condvar_t cv;      /**< Broadcast when completed. */
    6565} service_t;
    … …  
    7171static FIBRIL_MUTEX_INITIALIZE(services_mutex);
    7272
    73 #define SERVICES_KEYS        1
    74 #define SERVICES_KEY_HANDLE  0
    75 #define SERVICES_BUCKETS     256
    76 
    7773/* 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 {
    85         service_t *dev = hash_table_get_instance(item, service_t, link);
    86         return (dev->service_id == (service_id_t) key[SERVICES_KEY_HANDLE]);
    87 }
    88 
    89 static void services_remove_callback(link_t *item)
    90 {
    91         free(hash_table_get_instance(item, service_t, link));
    92 }
    93 
    94 static hash_table_operations_t services_ops = {
     74
     75static size_t services_key_hash(void *key)
     76{
     77        return *(service_id_t*)key;
     78}
     79
     80static size_t services_hash(const ht_link_t *item)
     81{
     82        service_t *dev = hash_table_get_inst(item, service_t, link);
     83        return dev->service_id;
     84}
     85
     86static bool services_key_equal(void *key, const ht_link_t *item)
     87{
     88        service_t *dev = hash_table_get_inst(item, service_t, link);
     89        return (dev->service_id == *(service_id_t*)key);
     90}
     91
     92static void services_remove_callback(ht_link_t *item)
     93{
     94        free(hash_table_get_inst(item, service_t, link));
     95}
     96
     97static hash_table_ops_t services_ops = {
    9598        .hash = services_hash,
    96         .compare = services_compare,
     99        .key_hash = services_key_hash,
     100        .key_equal = services_key_equal,
     101        .equal = 0,
    97102        .remove_callback = services_remove_callback
    98103};
    … …  
    229234                /* Device node */
    230235               
    231                 unsigned long key[] = {
    232                         [SERVICES_KEY_HANDLE] = (unsigned long) node->service_id
    233                 };
    234                 link_t *lnk;
    235                
    236236                fibril_mutex_lock(&services_mutex);
     237                ht_link_t *lnk;
    237238restart:
    238                 lnk = hash_table_find(&services, key);
     239                lnk = hash_table_find(&services, &node->service_id);
    239240                if (lnk == NULL) {
    240241                        service_t *dev = (service_t *) malloc(sizeof(service_t));
    … …  
    256257                         * below.
    257258                         */
    258                         hash_table_insert(&services, key, &dev->link);
     259                        hash_table_insert(&services, &dev->link);
    259260                       
    260261                        /*
    … …  
    279280                                 * entry and free the device structure.
    280281                                 */
    281                                 hash_table_remove(&services, key, SERVICES_KEYS);
     282                                hash_table_remove(&services, &node->service_id);
    282283                                fibril_mutex_unlock(&services_mutex);
    283284                               
    … …  
    288289                        dev->sess = sess;
    289290                } else {
    290                         service_t *dev = hash_table_get_instance(lnk, service_t, link);
     291                        service_t *dev = hash_table_get_inst(lnk, service_t, link);
    291292                       
    292293                        if (!dev->sess) {
    … …  
    450451bool locfs_init(void)
    451452{
    452         if (!hash_table_create(&services, SERVICES_BUCKETS,
    453             SERVICES_KEYS, &services_ops))
     453        if (!hash_table_create(&services, 0,  0, &services_ops))
    454454                return false;
    455455       
    … …  
    555555                /* Device node */
    556556               
    557                 unsigned long key[] = {
    558                         [SERVICES_KEY_HANDLE] = (unsigned long) index
    559                 };
    560                
    561557                fibril_mutex_lock(&services_mutex);
    562                 link_t *lnk = hash_table_find(&services, key);
     558                service_id_t service_index = index;
     559                ht_link_t *lnk = hash_table_find(&services, &service_index);
    563560                if (lnk == NULL) {
    564561                        fibril_mutex_unlock(&services_mutex);
    … …  
    566563                }
    567564               
    568                 service_t *dev = hash_table_get_instance(lnk, service_t, link);
     565                service_t *dev = hash_table_get_inst(lnk, service_t, link);
    569566                assert(dev->sess);
    570567               
    … …  
    621618        if (type == LOC_OBJECT_SERVICE) {
    622619                /* Device node */
    623                 unsigned long key[] = {
    624                         [SERVICES_KEY_HANDLE] = (unsigned long) index
    625                 };
    626620               
    627621                fibril_mutex_lock(&services_mutex);
    628                 link_t *lnk = hash_table_find(&services, key);
     622                service_id_t service_index = index;
     623                ht_link_t *lnk = hash_table_find(&services, &service_index);
    629624                if (lnk == NULL) {
    630625                        fibril_mutex_unlock(&services_mutex);
    … …  
    632627                }
    633628               
    634                 service_t *dev = hash_table_get_instance(lnk, service_t, link);
     629                service_t *dev = hash_table_get_inst(lnk, service_t, link);
    635630                assert(dev->sess);
    636631               
    … …  
    691686       
    692687        if (type == LOC_OBJECT_SERVICE) {
    693                 unsigned long key[] = {
    694                         [SERVICES_KEY_HANDLE] = (unsigned long) index
    695                 };
    696688               
    697689                fibril_mutex_lock(&services_mutex);
    698                 link_t *lnk = hash_table_find(&services, key);
     690                service_id_t service_index = index;
     691                ht_link_t *lnk = hash_table_find(&services, &service_index);
    699692                if (lnk == NULL) {
    700693                        fibril_mutex_unlock(&services_mutex);
    … …  
    702695                }
    703696               
    704                 service_t *dev = hash_table_get_instance(lnk, service_t, link);
     697                service_t *dev = hash_table_get_inst(lnk, service_t, link);
    705698                assert(dev->sess);
    706699                dev->refcount--;
    … …  
    708701                if (dev->refcount == 0) {
    709702                        async_hangup(dev->sess);
    710                         hash_table_remove(&services, key, SERVICES_KEYS);
     703                        service_id_t service_index = index;
     704                        hash_table_remove(&services, &service_index);
    711705                }
    712706               
    … …  
    732726       
    733727        if (type == LOC_OBJECT_SERVICE) {
    734                 unsigned long key[] = {
    735                         [SERVICES_KEY_HANDLE] = (unsigned long) index
    736                 };
    737                
     728
    738729                fibril_mutex_lock(&services_mutex);
    739                 link_t *lnk = hash_table_find(&services, key);
     730                service_id_t service_index = index;
     731                ht_link_t *lnk = hash_table_find(&services, &service_index);
    740732                if (lnk == NULL) {
    741733                        fibril_mutex_unlock(&services_mutex);
    … …  
    743735                }
    744736               
    745                 service_t *dev = hash_table_get_instance(lnk, service_t, link);
     737                service_t *dev = hash_table_get_inst(lnk, service_t, link);
    746738                assert(dev->sess);
    747739               

  • uspace/srv/fs/mfs/mfs.h

    r87e9392 r062d900  
    142142        unsigned refcnt;
    143143        fs_node_t *fsnode;
    144         link_t link;
     144        ht_link_t link;
    145145};
    146146

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

    r87e9392 r062d900  
    3535#include <align.h>
    3636#include <adt/hash_table.h>
     37#include <adt/hash.h>
    3738#include "mfs.h"
    3839
    39 #define OPEN_NODES_KEYS 2
    40 #define OPEN_NODES_SERVICE_KEY 0
    41 #define OPEN_NODES_INODE_KEY 1
    42 #define OPEN_NODES_BUCKETS 256
    4340
    4441static bool check_magic_number(uint16_t magic, bool *native,
    … …  
    6158static int mfs_unlink(fs_node_t *, fs_node_t *, const char *name);
    6259static 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);
    6760static int mfs_node_get(fs_node_t **rfn, service_id_t service_id,
    6861    fs_index_t index);
    … …  
    9588
    9689/* 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 {
    108         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 = {
     90
     91typedef struct {
     92        service_id_t service_id;
     93        fs_index_t index;
     94} node_key_t;
     95
     96static size_t
     97open_nodes_key_hash(void *key)
     98{
     99        node_key_t *node_key = (node_key_t*)key;
     100        return hash_combine(node_key->service_id, node_key->index);
     101}
     102
     103static size_t
     104open_nodes_hash(const ht_link_t *item)
     105{
     106        struct mfs_node *m = hash_table_get_inst(item, struct mfs_node, link);
     107        return hash_combine(m->instance->service_id, m->ino_i->index);
     108}
     109
     110static bool
     111open_nodes_key_equal(void *key, const ht_link_t *item)
     112{
     113        node_key_t *node_key = (node_key_t*)key;
     114        struct mfs_node *mnode = hash_table_get_inst(item, struct mfs_node, link);
     115
     116        return node_key->service_id == mnode->instance->service_id
     117                && node_key->index == mnode->ino_i->index;
     118}
     119
     120static hash_table_ops_t open_nodes_ops = {
    128121        .hash = open_nodes_hash,
    129         .compare = open_nodes_compare,
    130         .remove_callback = open_nodes_remove_cb,
     122        .key_hash = open_nodes_key_hash,
     123        .key_equal = open_nodes_key_equal,
     124        .equal = 0,
     125        .remove_callback = 0,
    131126};
    132127
    … …  
    134129mfs_global_init(void)
    135130{
    136         if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS,
    137             OPEN_NODES_KEYS, &open_nodes_ops)) {
     131        if (!hash_table_create(&open_nodes, 0, 0, &open_nodes_ops)) {
    138132                return ENOMEM;
    139133        }
    … …  
    406400        mnode->refcnt = 1;
    407401
    408         link_initialize(&mnode->link);
    409 
    410         unsigned long key[] = {
    411                 [OPEN_NODES_SERVICE_KEY] = inst->service_id,
    412                 [OPEN_NODES_INODE_KEY] = inum,
    413         };
    414 
    415402        fibril_mutex_lock(&open_nodes_lock);
    416         hash_table_insert(&open_nodes, key, &mnode->link);
     403        hash_table_insert(&open_nodes, &mnode->link);
    417404        fibril_mutex_unlock(&open_nodes_lock);
    418405        inst->open_nodes_cnt++;
    … …  
    513500        mnode->refcnt--;
    514501        if (mnode->refcnt == 0) {
    515                 unsigned long key[] = {
    516                         [OPEN_NODES_SERVICE_KEY] = mnode->instance->service_id,
    517                         [OPEN_NODES_INODE_KEY] = mnode->ino_i->index
    518                 };
    519                 hash_table_remove(&open_nodes, key, OPEN_NODES_KEYS);
     502                hash_table_remove_item(&open_nodes, &mnode->link);
    520503                assert(mnode->instance->open_nodes_cnt > 0);
    521504                mnode->instance->open_nodes_cnt--;
    … …  
    576559
    577560        /* Check if the node is not already open */
    578         unsigned long key[] = {
    579                 [OPEN_NODES_SERVICE_KEY] = inst->service_id,
    580                 [OPEN_NODES_INODE_KEY] = index,
     561        node_key_t key = {
     562                .service_id = inst->service_id,
     563                .index = index
    581564        };
    582         link_t *already_open = hash_table_find(&open_nodes, key);
     565       
     566        ht_link_t *already_open = hash_table_find(&open_nodes, &key);
    583567
    584568        if (already_open) {
    585                 mnode = hash_table_get_instance(already_open, struct mfs_node, link);
     569                mnode = hash_table_get_inst(already_open, struct mfs_node, link);
    586570                *rfn = mnode->fsnode;
    587571                mnode->refcnt++;
    … …  
    614598        mnode->ino_i = ino_i;
    615599        mnode->refcnt = 1;
    616         link_initialize(&mnode->link);
    617600
    618601        mnode->instance = inst;
    … …  
    621604        *rfn = node;
    622605
    623         hash_table_insert(&open_nodes, key, &mnode->link);
     606        hash_table_insert(&open_nodes, &mnode->link);
    624607        inst->open_nodes_cnt++;
    625608

  • uspace/srv/fs/tmpfs/tmpfs.h

    r87e9392 r062d900  
    6262        fs_index_t index;       /**< TMPFS node index. */
    6363        service_id_t service_id;/**< Service ID of block device. */
    64         link_t nh_link;         /**< Nodes hash table link. */
     64        ht_link_t nh_link;              /**< Nodes hash table link. */
    6565        tmpfs_dentry_type_t type;
    6666        unsigned lnkcnt;        /**< Link count. */

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

    r87e9392 r062d900  
    5050#include <sys/types.h>
    5151#include <adt/hash_table.h>
     52#include <adt/hash.h>
    5253#include <as.h>
    5354#include <libfs.h>
    … …  
    5556#define min(a, b)               ((a) < (b) ? (a) : (b))
    5657#define max(a, b)               ((a) > (b) ? (a) : (b))
    57 
    58 #define NODES_BUCKETS   256
    5958
    6059/** All root nodes have index 0. */
    … …  
    142141hash_table_t nodes;
    143142
    144 #define NODES_KEY_DEV   0       
    145 #define NODES_KEY_INDEX 1
    146 
    147 /* 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)
    154 {
    155         tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t,
    156             nh_link);
    157        
    158         switch (keys) {
    159         case 1:
    160                 return (nodep->service_id == key[NODES_KEY_DEV]);
    161         case 2:
    162                 return ((nodep->service_id == key[NODES_KEY_DEV]) &&
    163                     (nodep->index == key[NODES_KEY_INDEX]));
    164         default:
    165                 assert((keys == 1) || (keys == 2));
    166         }
    167 
    168         return 0;
    169 }
    170 
    171 static void nodes_remove_callback(link_t *item)
    172 {
    173         tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t,
    174             nh_link);
     143/*
     144 * Implementation of hash table interface for the nodes hash table.
     145 */
     146
     147typedef struct {
     148        service_id_t service_id;
     149        fs_index_t index;
     150} node_key_t;
     151
     152static size_t nodes_key_hash(void *k)
     153{
     154        node_key_t *key = (node_key_t *)k;
     155        return hash_combine(key->service_id, key->index);
     156}
     157
     158static size_t nodes_hash(const ht_link_t *item)
     159{
     160        tmpfs_node_t *nodep = hash_table_get_inst(item, tmpfs_node_t, nh_link);
     161        return hash_combine(nodep->service_id, nodep->index);
     162}
     163
     164static bool nodes_key_equal(void *key_arg, const ht_link_t *item)
     165{
     166        tmpfs_node_t *node = hash_table_get_inst(item, tmpfs_node_t, nh_link);
     167        node_key_t *key = (node_key_t *)key_arg;
     168       
     169        return key->service_id == node->service_id && key->index == node->index;
     170}
     171
     172static void nodes_remove_callback(ht_link_t *item)
     173{
     174        tmpfs_node_t *nodep = hash_table_get_inst(item, tmpfs_node_t, nh_link);
    175175
    176176        while (!list_empty(&nodep->cs_list)) {
    … …  
    192192
    193193/** TMPFS nodes hash table operations. */
    194 hash_table_operations_t nodes_ops = {
     194hash_table_ops_t nodes_ops = {
    195195        .hash = nodes_hash,
    196         .compare = nodes_compare,
     196        .key_hash = nodes_key_hash,
     197        .key_equal = nodes_key_equal,
     198        .equal = 0,
    197199        .remove_callback = nodes_remove_callback
    198200};
    … …  
    207209        nodep->size = 0;
    208210        nodep->data = NULL;
    209         link_initialize(&nodep->nh_link);
    210211        list_initialize(&nodep->cs_list);
    211212}
    … …  
    220221bool tmpfs_init(void)
    221222{
    222         if (!hash_table_create(&nodes, NODES_BUCKETS, 2, &nodes_ops))
     223        if (!hash_table_create(&nodes, 0, 0, &nodes_ops))
    223224                return false;
    224225       
    … …  
    238239}
    239240
     241static bool rm_service_id_nodes(ht_link_t *item, void *arg)
     242{
     243        service_id_t sid = *(service_id_t*)arg;
     244        tmpfs_node_t *node = hash_table_get_inst(item, tmpfs_node_t, nh_link);
     245       
     246        if (node->service_id == sid) {
     247                hash_table_remove_item(&nodes, &node->nh_link);
     248        }
     249        return true;
     250}
     251
    240252static void tmpfs_instance_done(service_id_t service_id)
    241 {
    242         unsigned long key[] = {
    243                 [NODES_KEY_DEV] = service_id
    244         };
    245         /*
    246          * Here we are making use of one special feature of our hash table
    247          * implementation, which allows to remove more items based on a partial
    248          * key match. In the following, we are going to remove all nodes
    249          * matching our device handle. The nodes_remove_callback() function will
    250          * take care of resource deallocation.
    251          */
    252         hash_table_remove(&nodes, key, 1);
     253{       
     254        hash_table_apply(&nodes, rm_service_id_nodes, &service_id);
    253255}
    254256
    … …  
    272274int tmpfs_node_get(fs_node_t **rfn, service_id_t service_id, fs_index_t index)
    273275{
    274         unsigned long key[] = {
    275                 [NODES_KEY_DEV] = service_id,
    276                 [NODES_KEY_INDEX] = index
     276        node_key_t key = {
     277                .service_id = service_id,
     278                .index = index
    277279        };
    278         link_t *lnk = hash_table_find(&nodes, key);
     280       
     281        ht_link_t *lnk = hash_table_find(&nodes, &key);
     282       
    279283        if (lnk) {
    280284                tmpfs_node_t *nodep;
    281                 nodep = hash_table_get_instance(lnk, tmpfs_node_t, nh_link);
     285                nodep = hash_table_get_inst(lnk, tmpfs_node_t, nh_link);
    282286                *rfn = FS_NODE(nodep);
    283287        } else {
    … …  
    331335
    332336        /* 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);
     337        hash_table_insert(&nodes, &nodep->nh_link);
    338338        *rfn = FS_NODE(nodep);
    339339        return EOK;
    … …  
    346346        assert(!nodep->lnkcnt);
    347347        assert(list_empty(&nodep->cs_list));
    348 
    349         unsigned long key[] = {
    350                 [NODES_KEY_DEV] = nodep->service_id,
    351                 [NODES_KEY_INDEX] = nodep->index
    352         };
    353         hash_table_remove(&nodes, key, 2);
     348       
     349        hash_table_remove_item(&nodes, &nodep->nh_link);
    354350
    355351        /*
    … …  
    476472         * Lookup the respective TMPFS node.
    477473         */
    478         link_t *hlp;
    479         unsigned long key[] = {
    480                 [NODES_KEY_DEV] = service_id,
    481                 [NODES_KEY_INDEX] = index
     474        node_key_t key = {
     475                .service_id = service_id,
     476                .index = index
    482477        };
    483         hlp = hash_table_find(&nodes, key);
     478       
     479        ht_link_t *hlp = hash_table_find(&nodes, &key);
    484480        if (!hlp)
    485481                return ENOENT;
    486         tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t,
    487             nh_link);
     482       
     483        tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t, nh_link);
    488484       
    489485        /*
    … …  
    538534         * Lookup the respective TMPFS node.
    539535         */
    540         link_t *hlp;
    541         unsigned long key[] = {
    542                 [NODES_KEY_DEV] = service_id,
    543                 [NODES_KEY_INDEX] = index
     536        node_key_t key = {
     537                .service_id = service_id,
     538                .index = index
    544539        };
    545         hlp = hash_table_find(&nodes, key);
     540       
     541        ht_link_t *hlp = hash_table_find(&nodes, &key);
     542       
    546543        if (!hlp)
    547544                return ENOENT;
    548         tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t,
    549             nh_link);
     545       
     546        tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t, nh_link);
    550547
    551548        /*
    … …  
    600597         * Lookup the respective TMPFS node.
    601598         */
    602         unsigned long key[] = {
    603                 [NODES_KEY_DEV] = service_id,
    604                 [NODES_KEY_INDEX] = index
     599        node_key_t key = {
     600                .service_id = service_id,
     601                .index = index
    605602        };
    606         link_t *hlp = hash_table_find(&nodes, key);
     603       
     604        ht_link_t *hlp = hash_table_find(&nodes, &key);
     605       
    607606        if (!hlp)
    608607                return ENOENT;
    609         tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t, nh_link);
     608        tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t, nh_link);
    610609       
    611610        if (size == nodep->size)
    … …  
    636635static int tmpfs_destroy(service_id_t service_id, fs_index_t index)
    637636{
    638         link_t *hlp;
    639         unsigned long key[] = {
    640                 [NODES_KEY_DEV] = service_id,
    641                 [NODES_KEY_INDEX] = index
     637        node_key_t key = {
     638                .service_id = service_id,
     639                .index = index
    642640        };
    643         hlp = hash_table_find(&nodes, key);
     641       
     642        ht_link_t *hlp = hash_table_find(&nodes, &key);
    644643        if (!hlp)
    645644                return ENOENT;
    646         tmpfs_node_t *nodep = hash_table_get_instance(hlp, tmpfs_node_t,
     645        tmpfs_node_t *nodep = hash_table_get_inst(hlp, tmpfs_node_t,
    647646            nh_link);
    648647        return tmpfs_destroy_node(FS_NODE(nodep));

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

    r87e9392 r062d900  
    5050
    5151#include <adt/hash_table.h>
     52#include <adt/hash.h>
    5253#include <stdlib.h>
    5354#include <stdio.h>
    5455#include "gsp.h"
    5556
    56 #define TRANS_TABLE_CHAINS  256
    57 
    5857/*
    59  * Hash table operations for the transition function.
    60  */
    61 
    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 = {
    68         .hash = trans_op_hash,
    69         .compare = trans_op_compare,
    70         .remove_callback = trans_op_remove_callback
     58 * Transition function hash table operations.
     59 */
     60typedef struct {
     61        int old_state;
     62        int input;
     63} trans_key_t;
     64
     65static size_t trans_key_hash(void *key)
     66{
     67        trans_key_t *trans_key = (trans_key_t *)key;
     68        return hash_combine(trans_key->input, trans_key->old_state);
     69}
     70
     71static size_t trans_hash(const ht_link_t *item)
     72{
     73        gsp_trans_t *t = hash_table_get_inst(item, gsp_trans_t, link);
     74        return hash_combine(t->input, t->old_state);
     75}
     76
     77static bool trans_key_equal(void *key, const ht_link_t *item)
     78{
     79        trans_key_t *trans_key = (trans_key_t *)key;
     80        gsp_trans_t *t = hash_table_get_inst(item, gsp_trans_t, link);
     81       
     82        return trans_key->input == t->input && trans_key->old_state == t->old_state;
     83}
     84
     85static hash_table_ops_t trans_ops = {
     86        .hash = trans_hash,
     87        .key_hash = trans_key_hash,
     88        .key_equal = trans_key_equal,
     89        .equal = 0,
     90        .remove_callback = 0
    7191};
     92
    7293
    7394static gsp_trans_t *trans_lookup(gsp_t *p, int state, int input);
    … …  
    7596static gsp_trans_t *trans_new(void);
    7697
    77 /** Initialise scancode parser. */
     98/** Initialize scancode parser. */
    7899void gsp_init(gsp_t *p)
    79100{
    80101        p->states = 1;
    81         hash_table_create(&p->trans, TRANS_TABLE_CHAINS, 2, &trans_ops);
     102        hash_table_create(&p->trans, 0, 0, &trans_ops);
    82103}
    83104
    … …  
    223244static gsp_trans_t *trans_lookup(gsp_t *p, int state, int input)
    224245{
    225         link_t *item;
    226         unsigned long key[2];
    227 
    228         key[0] = state;
    229         key[1] = input;
    230 
    231         item = hash_table_find(&p->trans, key);
     246        ht_link_t *item;
     247       
     248        trans_key_t key = {
     249                .input = input,
     250                .old_state = state
     251        };
     252
     253        item = hash_table_find(&p->trans, &key);
    232254        if (item == NULL) return NULL;
    233255
    234         return hash_table_get_instance(item, gsp_trans_t, link);
     256        return hash_table_get_inst(item, gsp_trans_t, link);
    235257}
    236258
    … …  
    242264static void trans_insert(gsp_t *p, gsp_trans_t *t)
    243265{
    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);
     266        hash_table_insert(&p->trans, &t->link);
    250267}
    251268
    … …  
    264281}
    265282
    266 /*
    267  * Transition function hash table operations.
    268  */
    269 
    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);
    281         return ((key[0] == (unsigned long) t->old_state)
    282             && (key[1] == (unsigned long) t->input));
    283 }
    284 
    285 static void trans_op_remove_callback(link_t *item)
    286 {
    287 }
    288283
    289284/**

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

    r87e9392 r062d900  
    5656/** Scancode parser transition. */
    5757typedef struct {
    58         link_t link;            /**< Link to hash table in @c gsp_t */
     58        ht_link_t link;         /**< Link to hash table in @c gsp_t */
    5959
    6060        /* Preconditions */

  • uspace/srv/ns/service.c

    r87e9392 r062d900  
    4040#include "ns.h"
    4141
    42 #define SERVICE_HASH_TABLE_CHAINS  20
    4342
    4443/** Service hash table item. */
    4544typedef struct {
    46         link_t link;
     45        ht_link_t link;
    4746        sysarg_t service;        /**< Service ID. */
    4847        sysarg_t phone;          /**< Phone registered with the service. */
    … …  
    5049} hashed_service_t;
    5150
    52 /** Compute hash index into service hash table.
    53  *
    54  * @param key Pointer keys. However, only the first key (i.e. service number)
    55  *            is used to compute the hash index.
    56  *
    57  * @return Hash index corresponding to key[0].
    58  *
    59  */
    60 static hash_index_t service_hash(unsigned long key[])
     51
     52static size_t service_key_hash(void *key)
    6153{
    62         assert(key);
    63         return (key[0] % SERVICE_HASH_TABLE_CHAINS);
     54        return *(sysarg_t*)key;
    6455}
    6556
    66 /** Compare a key with hashed item.
    67  *
    68  * This compare function always ignores the third key.
    69  * It exists only to make it possible to remove records
    70  * originating from connection with key[1] in_phone_hash
    71  * value. Note that this is close to being classified
    72  * as a nasty hack.
    73  *
    74  * @param key  Array of keys.
    75  * @param keys Must be lesser or equal to 3.
    76  * @param item Pointer to a hash table item.
    77  *
    78  * @return Non-zero if the key matches the item, zero otherwise.
    79  *
    80  */
    81 static int service_compare(unsigned long key[], hash_count_t keys, link_t *item)
     57static size_t service_hash(const ht_link_t *item)
    8258{
    83         assert(key);
    84         assert(keys <= 3);
    85         assert(item);
    86        
    87         hashed_service_t *hs = hash_table_get_instance(item, hashed_service_t, link);
    88        
    89         if (keys == 2)
    90                 return ((key[0] == hs->service) && (key[1] == hs->in_phone_hash));
    91         else
    92                 return (key[0] == hs->service);
     59        hashed_service_t *hs = hash_table_get_inst(item, hashed_service_t, link);
     60        return hs->service;
    9361}
    9462
    95 /** Perform actions after removal of item from the hash table.
    96  *
    97  * @param item Item that was removed from the hash table.
    98  *
    99  */
    100 static void service_remove(link_t *item)
     63static bool service_key_equal(void *key, const ht_link_t *item)
    10164{
    102         assert(item);
    103         free(hash_table_get_instance(item, hashed_service_t, link));
     65        hashed_service_t *hs = hash_table_get_inst(item, hashed_service_t, link);
     66        return hs->service == *(sysarg_t*)key;
    10467}
    10568
    10669/** Operations for service hash table. */
    107 static hash_table_operations_t service_hash_table_ops = {
     70static hash_table_ops_t service_hash_table_ops = {
    10871        .hash = service_hash,
    109         .compare = service_compare,
    110         .remove_callback = service_remove
     72        .key_hash = service_key_hash,
     73        .key_equal = service_key_equal,
     74        .equal = 0,
     75        .remove_callback = 0
    11176};
    11277
    … …  
    12792int service_init(void)
    12893{
    129         if (!hash_table_create(&service_hash_table, SERVICE_HASH_TABLE_CHAINS,
    130             3, &service_hash_table_ops)) {
     94        if (!hash_table_create(&service_hash_table, 0, 0, &service_hash_table_ops)) {
    13195                printf(NAME ": No memory available for services\n");
    13296                return ENOMEM;
    … …  
    145109                pending_conn_t *pr = list_get_instance(cur, pending_conn_t, link);
    146110               
    147                 unsigned long keys[3] = {
    148                         pr->service,
    149                         0,
    150                         0
    151                 };
    152                
    153                 link_t *link = hash_table_find(&service_hash_table, keys);
     111                ht_link_t *link = hash_table_find(&service_hash_table, &pr->service);
    154112                if (!link)
    155113                        continue;
    156114               
    157                 hashed_service_t *hs = hash_table_get_instance(link, hashed_service_t, link);
     115                hashed_service_t *hs = hash_table_get_inst(link, hashed_service_t, link);
    158116                (void) ipc_forward_fast(pr->callid, hs->phone, pr->arg2,
    159117                    pr->arg3, 0, IPC_FF_NONE);
    … …  
    176134int register_service(sysarg_t service, sysarg_t phone, ipc_call_t *call)
    177135{
    178         unsigned long keys[3] = {
    179                 service,
    180                 call->in_phone_hash,
    181                 0
    182         };
    183        
    184         if (hash_table_find(&service_hash_table, keys))
     136        if (hash_table_find(&service_hash_table, &service))
    185137                return EEXISTS;
    186138       
    … …  
    189141                return ENOMEM;
    190142       
    191         link_initialize(&hs->link);
    192143        hs->service = service;
    193144        hs->phone = phone;
    194145        hs->in_phone_hash = call->in_phone_hash;
    195         hash_table_insert(&service_hash_table, keys, &hs->link);
     146        hash_table_insert(&service_hash_table, &hs->link);
    196147       
    197148        return EOK;
    … …  
    210161{
    211162        sysarg_t retval;
    212         unsigned long keys[3] = {
    213                 service,
    214                 0,
    215                 0
    216         };
    217163       
    218         link_t *link = hash_table_find(&service_hash_table, keys);
     164        ht_link_t *link = hash_table_find(&service_hash_table, &service);
    219165        if (!link) {
    220166                if (IPC_GET_ARG4(*call) & IPC_FLAG_BLOCKING) {
    … …  
    239185        }
    240186       
    241         hashed_service_t *hs = hash_table_get_instance(link, hashed_service_t, link);
     187        hashed_service_t *hs = hash_table_get_inst(link, hashed_service_t, link);
    242188        (void) ipc_forward_fast(callid, hs->phone, IPC_GET_ARG2(*call),
    243189            IPC_GET_ARG3(*call), 0, IPC_FF_NONE);

  • uspace/srv/ns/task.c

    r87e9392 r062d900  
    4343#include "ns.h"
    4444
    45 #define TASK_HASH_TABLE_CHAINS  256
    46 #define P2I_HASH_TABLE_CHAINS   256
    4745
    4846/* TODO:
    … …  
    5553/** Task hash table item. */
    5654typedef struct {
    57         link_t link;
     55        ht_link_t link;
    5856       
    5957        task_id_t id;    /**< Task ID. */
    … …  
    6361} hashed_task_t;
    6462
    65 /** Compute hash index into task hash table.
    66  *
    67  * @param key Pointer keys. However, only the first key (i.e. truncated task
    68  *            number) is used to compute the hash index.
    69  *
    70  * @return Hash index corresponding to key[0].
    71  *
    72  */
    73 static hash_index_t task_hash(unsigned long key[])
    74 {
    75         assert(key);
    76         return (LOWER32(key[0]) % TASK_HASH_TABLE_CHAINS);
    77 }
    78 
    79 /** Compare a key with hashed item.
    80  *
    81  * @param key  Array of keys.
    82  * @param keys Must be less than or equal to 2.
    83  * @param item Pointer to a hash table item.
    84  *
    85  * @return Non-zero if the key matches the item, zero otherwise.
    86  *
    87  */
    88 static int task_compare(unsigned long key[], hash_count_t keys, link_t *item)
    89 {
    90         assert(key);
    91         assert(keys <= 2);
    92         assert(item);
    93        
    94         hashed_task_t *ht = hash_table_get_instance(item, hashed_task_t, link);
    95        
    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));
    101 }
    102 
    103 /** Perform actions after removal of item from the hash table.
    104  *
    105  * @param item Item that was removed from the hash table.
    106  *
    107  */
    108 static void task_remove(link_t *item)
    109 {
    110         assert(item);
    111         free(hash_table_get_instance(item, hashed_task_t, link));
     63
     64static size_t task_key_hash(void *key)
     65{
     66        return *(task_id_t*)key;
     67}
     68
     69static size_t task_hash(const ht_link_t  *item)
     70{
     71        hashed_task_t *ht = hash_table_get_inst(item, hashed_task_t, link);
     72        return ht->id;
     73}
     74
     75static bool task_key_equal(void *key, const ht_link_t *item)
     76{
     77        hashed_task_t *ht = hash_table_get_inst(item, hashed_task_t, link);
     78        return ht->id == *(task_id_t*)key;
     79}
     80
     81/** Perform actions after removal of item from the hash table. */
     82static void task_remove(ht_link_t *item)
     83{
     84        free(hash_table_get_inst(item, hashed_task_t, link));
    11285}
    11386
    11487/** Operations for task hash table. */
    115 static hash_table_operations_t task_hash_table_ops = {
     88static hash_table_ops_t task_hash_table_ops = {
    11689        .hash = task_hash,
    117         .compare = task_compare,
     90        .key_hash = task_key_hash,
     91        .key_equal = task_key_equal,
     92        .equal = 0,
    11893        .remove_callback = task_remove
    11994};
    … …  
    12398
    12499typedef struct {
    125         link_t link;
     100        ht_link_t link;
    126101        sysarg_t in_phone_hash;  /**< Incoming phone hash. */
    127102        task_id_t id;            /**< Task ID. */
    128103} p2i_entry_t;
    129104
    130 /** Compute hash index into task hash table.
    131  *
    132  * @param key Array of keys.
    133  *
    134  * @return Hash index corresponding to key[0].
    135  *
    136  */
    137 static hash_index_t p2i_hash(unsigned long key[])
    138 {
    139         assert(key);
    140         return (key[0] % TASK_HASH_TABLE_CHAINS);
    141 }
    142 
    143 /** Compare a key with hashed item.
    144  *
    145  * @param key  Array of keys.
    146  * @param keys Must be less than or equal to 1.
    147  * @param item Pointer to a hash table item.
    148  *
    149  * @return Non-zero if the key matches the item, zero otherwise.
    150  *
    151  */
    152 static int p2i_compare(unsigned long key[], hash_count_t keys, link_t *item)
    153 {
    154         assert(key);
    155         assert(keys == 1);
     105/* phone-to-id hash table operations */
     106
     107static size_t p2i_key_hash(void *key)
     108{
     109        sysarg_t in_phone_hash = *(sysarg_t*)key;
     110        return in_phone_hash;
     111}
     112
     113static size_t p2i_hash(const ht_link_t *item)
     114{
     115        p2i_entry_t *entry = hash_table_get_inst(item, p2i_entry_t, link);
     116        return entry->in_phone_hash;
     117}
     118
     119static bool p2i_key_equal(void *key, const ht_link_t *item)
     120{
     121        sysarg_t in_phone_hash = *(sysarg_t*)key;
     122        p2i_entry_t *entry = hash_table_get_inst(item, p2i_entry_t, link);
     123       
     124        return (in_phone_hash == entry->in_phone_hash);
     125}
     126
     127/** Perform actions after removal of item from the hash table.
     128 *
     129 * @param item Item that was removed from the hash table.
     130 *
     131 */
     132static void p2i_remove(ht_link_t *item)
     133{
    156134        assert(item);
    157        
    158         p2i_entry_t *entry = hash_table_get_instance(item, p2i_entry_t, link);
    159        
    160         return (key[0] == entry->in_phone_hash);
    161 }
    162 
    163 /** Perform actions after removal of item from the hash table.
    164  *
    165  * @param item Item that was removed from the hash table.
    166  *
    167  */
    168 static void p2i_remove(link_t *item)
    169 {
    170         assert(item);
    171         free(hash_table_get_instance(item, p2i_entry_t, link));
     135        free(hash_table_get_inst(item, p2i_entry_t, link));
    172136}
    173137
    174138/** Operations for task hash table. */
    175 static hash_table_operations_t p2i_ops = {
     139static hash_table_ops_t p2i_ops = {
    176140        .hash = p2i_hash,
    177         .compare = p2i_compare,
     141        .key_hash = p2i_key_hash,
     142        .key_equal = p2i_key_equal,
     143        .equal = 0,
    178144        .remove_callback = p2i_remove
    179145};
    … …  
    193159int task_init(void)
    194160{
    195         if (!hash_table_create(&task_hash_table, TASK_HASH_TABLE_CHAINS,
    196             2, &task_hash_table_ops)) {
     161        if (!hash_table_create(&task_hash_table, 0, 0, &task_hash_table_ops)) {
    197162                printf(NAME ": No memory available for tasks\n");
    198163                return ENOMEM;
    199164        }
    200165       
    201         if (!hash_table_create(&phone_to_id, P2I_HASH_TABLE_CHAINS,
    202             1, &p2i_ops)) {
     166        if (!hash_table_create(&phone_to_id, 0, 0, &p2i_ops)) {
    203167                printf(NAME ": No memory available for tasks\n");
    204168                return ENOMEM;
    … …  
    218182                pending_wait_t *pr = list_get_instance(cur, pending_wait_t, link);
    219183               
    220                 unsigned long keys[2] = {
    221                         LOWER32(pr->id),
    222                         UPPER32(pr->id)
    223                 };
    224                
    225                 link_t *link = hash_table_find(&task_hash_table, keys);
     184                ht_link_t *link = hash_table_find(&task_hash_table, &pr->id);
    226185                if (!link)
    227186                        continue;
    228187               
    229                 hashed_task_t *ht = hash_table_get_instance(link, hashed_task_t, link);
     188                hashed_task_t *ht = hash_table_get_inst(link, hashed_task_t, link);
    230189                if (!ht->finished)
    231190                        continue;
    … …  
    238197                }
    239198               
    240                 hash_table_remove(&task_hash_table, keys, 2);
     199                hash_table_remove(&task_hash_table, &pr->id);
    241200                list_remove(cur);
    242201                free(pr);
    … …  
    250209        task_exit_t texit;
    251210       
    252         unsigned long keys[2] = {
    253                 LOWER32(id),
    254                 UPPER32(id)
    255         };
    256        
    257         link_t *link = hash_table_find(&task_hash_table, keys);
     211        ht_link_t *link = hash_table_find(&task_hash_table, &id);
    258212        hashed_task_t *ht = (link != NULL) ?
    259             hash_table_get_instance(link, hashed_task_t, link) : NULL;
     213            hash_table_get_inst(link, hashed_task_t, link) : NULL;
    260214       
    261215        if (ht == NULL) {
    … …  
    281235        }
    282236       
    283         hash_table_remove(&task_hash_table, keys, 2);
     237        hash_table_remove_item(&task_hash_table, link);
    284238        retval = EOK;
    285239       
    … …  
    293247int ns_task_id_intro(ipc_call_t *call)
    294248{
    295         unsigned long keys[2];
    296249       
    297250        task_id_t id = MERGE_LOUP32(IPC_GET_ARG1(*call), IPC_GET_ARG2(*call));
    298         keys[0] = call->in_phone_hash;
    299        
    300         link_t *link = hash_table_find(&phone_to_id, keys);
     251
     252        ht_link_t *link = hash_table_find(&phone_to_id, &call->in_phone_hash);
    301253        if (link != NULL)
    302254                return EEXISTS;
    … …  
    314266         */
    315267       
    316         link_initialize(&entry->link);
    317268        entry->in_phone_hash = call->in_phone_hash;
    318269        entry->id = id;
    319         hash_table_insert(&phone_to_id, keys, &entry->link);
     270        hash_table_insert(&phone_to_id, &entry->link);
    320271       
    321272        /*
    … …  
    323274         */
    324275       
    325         keys[0] = LOWER32(id);
    326         keys[1] = UPPER32(id);
    327        
    328         link_initialize(&ht->link);
    329276        ht->id = id;
    330277        ht->finished = false;
    331278        ht->have_rval = false;
    332279        ht->retval = -1;
    333         hash_table_insert(&task_hash_table, keys, &ht->link);
     280        hash_table_insert(&task_hash_table, &ht->link);
    334281       
    335282        return EOK;
    … …  
    338285static int get_id_by_phone(sysarg_t phone_hash, task_id_t *id)
    339286{
    340         unsigned long keys[1] = {phone_hash};
    341        
    342         link_t *link = hash_table_find(&phone_to_id, keys);
     287        ht_link_t *link = hash_table_find(&phone_to_id, &phone_hash);
    343288        if (link == NULL)
    344289                return ENOENT;
    345290       
    346         p2i_entry_t *entry = hash_table_get_instance(link, p2i_entry_t, link);
     291        p2i_entry_t *entry = hash_table_get_inst(link, p2i_entry_t, link);
    347292        *id = entry->id;
    348293       
    … …  
    357302                return rc;
    358303       
    359         unsigned long keys[2] = {
    360                 LOWER32(id),
    361                 UPPER32(id)
    362         };
    363        
    364         link_t *link = hash_table_find(&task_hash_table, keys);
     304        ht_link_t *link = hash_table_find(&task_hash_table, &id);
    365305        hashed_task_t *ht = (link != NULL) ?
    366             hash_table_get_instance(link, hashed_task_t, link) : NULL;
     306            hash_table_get_inst(link, hashed_task_t, link) : NULL;
    367307       
    368308        if ((ht == NULL) || (ht->finished))
    … …  
    378318int ns_task_disconnect(ipc_call_t *call)
    379319{
    380         unsigned long keys[2];
    381        
    382320        task_id_t id;
    383321        int rc = get_id_by_phone(call->in_phone_hash, &id);
    … …  
    386324       
    387325        /* Delete from phone-to-id map. */
    388         keys[0] = call->in_phone_hash;
    389         hash_table_remove(&phone_to_id, keys, 1);
     326        hash_table_remove(&phone_to_id, &call->in_phone_hash);
    390327       
    391328        /* Mark task as finished. */
    392         keys[0] = LOWER32(id);
    393         keys[1] = UPPER32(id);
    394        
    395         link_t *link = hash_table_find(&task_hash_table, keys);
    396         hashed_task_t *ht =
    397             hash_table_get_instance(link, hashed_task_t, link);
    398         if (ht == NULL)
     329        ht_link_t *link = hash_table_find(&task_hash_table, &id);
     330        if (link == NULL)
    399331                return EOK;
     332
     333        hashed_task_t *ht = hash_table_get_inst(link, hashed_task_t, link);
    400334       
    401335        ht->finished = true;

  • uspace/srv/vfs/vfs.h

    r87e9392 r062d900  
    3636#include <async.h>
    3737#include <adt/list.h>
     38#include <adt/hash_table.h>
    3839#include <fibril_synch.h>
    3940#include <sys/types.h>
    … …  
    112113        unsigned lnkcnt;
    113114
    114         link_t nh_link;         /**< Node hash-table link. */
     115        ht_link_t nh_link;              /**< Node hash-table link. */
    115116
    116117        vfs_node_type_t type;   /**< Partial info about the node type. */

  • uspace/srv/vfs/vfs_node.c

    r87e9392 r062d900  
    4141#include <fibril_synch.h>
    4242#include <adt/hash_table.h>
     43#include <adt/hash.h>
    4344#include <assert.h>
    4445#include <async.h>
    … …  
    5859#define KEY_INDEX       2
    5960
    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 *);
     61static size_t nodes_key_hash(void *);
     62static size_t nodes_hash(const ht_link_t *);
     63static bool nodes_key_equal(void *, const ht_link_t *);
     64static vfs_triplet_t node_triplet(vfs_node_t *node);
    6365
    6466/** VFS node hash table operations. */
    65 hash_table_operations_t nodes_ops = {
     67hash_table_ops_t nodes_ops = {
    6668        .hash = nodes_hash,
    67         .compare = nodes_compare,
    68         .remove_callback = nodes_remove_callback
     69        .key_hash = nodes_key_hash,
     70        .key_equal = nodes_key_equal,
     71        .equal = 0,
     72        .remove_callback = 0,
    6973};
    7074
    … …  
    7579bool vfs_nodes_init(void)
    7680{
    77         return hash_table_create(&nodes, NODES_BUCKETS, 3, &nodes_ops);
     81        return hash_table_create(&nodes, 0, 0, &nodes_ops);
    7882}
    7983
    … …  
    114118                 */
    115119               
    116                 unsigned long key[] = {
    117                         [KEY_FS_HANDLE] = node->fs_handle,
    118                         [KEY_DEV_HANDLE] = node->service_id,
    119                         [KEY_INDEX] = node->index
    120                 };
    121                
    122                 hash_table_remove(&nodes, key, 3);
     120                hash_table_remove_item(&nodes, &node->nh_link);
    123121                free_vfs_node = true;
    124122               
    … …  
    158156{
    159157        fibril_mutex_lock(&nodes_mutex);
    160         unsigned long key[] = {
    161                 [KEY_FS_HANDLE] = node->fs_handle,
    162                 [KEY_DEV_HANDLE] = node->service_id,
    163                 [KEY_INDEX] = node->index
    164         };
    165         hash_table_remove(&nodes, key, 3);
     158        hash_table_remove_item(&nodes, &node->nh_link);
    166159        fibril_mutex_unlock(&nodes_mutex);
    167160        free(node);
    … …  
    182175vfs_node_t *vfs_node_get(vfs_lookup_res_t *result)
    183176{
    184         unsigned long key[] = {
    185                 [KEY_FS_HANDLE] = result->triplet.fs_handle,
    186                 [KEY_DEV_HANDLE] = result->triplet.service_id,
    187                 [KEY_INDEX] = result->triplet.index
    188         };
    189         link_t *tmp;
    190177        vfs_node_t *node;
    191178
    192179        fibril_mutex_lock(&nodes_mutex);
    193         tmp = hash_table_find(&nodes, key);
     180        ht_link_t *tmp = hash_table_find(&nodes, &result->triplet);
    194181        if (!tmp) {
    195182                node = (vfs_node_t *) malloc(sizeof(vfs_node_t));
    … …  
    205192                node->lnkcnt = result->lnkcnt;
    206193                node->type = result->type;
    207                 link_initialize(&node->nh_link);
    208194                fibril_rwlock_initialize(&node->contents_rwlock);
    209                 hash_table_insert(&nodes, key, &node->nh_link);
     195                hash_table_insert(&nodes, &node->nh_link);
    210196        } else {
    211                 node = hash_table_get_instance(tmp, vfs_node_t, nh_link);
     197                node = hash_table_get_inst(tmp, vfs_node_t, nh_link);
    212198                if (node->type == VFS_NODE_UNKNOWN &&
    213199                    result->type != VFS_NODE_UNKNOWN) {
    … …  
    240226}
    241227
    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)
    251 {
    252         vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
    253         return (node->fs_handle == (fs_handle_t) key[KEY_FS_HANDLE]) &&
    254             (node->service_id == key[KEY_DEV_HANDLE]) &&
    255             (node->index == key[KEY_INDEX]);
    256 }
    257 
    258 void nodes_remove_callback(link_t *item)
    259 {
    260 }
    261 
    262228struct refcnt_data {
    263229        /** Sum of all reference counts for this file system instance. */
    … …  
    267233};
    268234
    269 static void refcnt_visitor(link_t *item, void *arg)
    270 {
    271         vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
     235static bool refcnt_visitor(ht_link_t *item, void *arg)
     236{
     237        vfs_node_t *node = hash_table_get_inst(item, vfs_node_t, nh_link);
    272238        struct refcnt_data *rd = (void *) arg;
    273239
    … …  
    275241            (node->service_id == rd->service_id))
    276242                rd->refcnt += node->refcnt;
     243       
     244        return true;
    277245}
    278246
    … …  
    315283}
    316284
     285
     286static size_t nodes_key_hash(void *key)
     287{
     288        vfs_triplet_t *tri = key;
     289        size_t hash = hash_combine(tri->fs_handle, tri->index);
     290        return hash_combine(hash, tri->service_id);
     291}
     292
     293static size_t nodes_hash(const ht_link_t *item)
     294{
     295        vfs_node_t *node = hash_table_get_inst(item, vfs_node_t, nh_link);
     296        vfs_triplet_t tri = node_triplet(node);
     297        return nodes_key_hash(&tri);
     298}
     299
     300static bool nodes_key_equal(void *key, const ht_link_t *item)
     301{
     302        vfs_triplet_t *tri = key;
     303        vfs_node_t *node = hash_table_get_inst(item, vfs_node_t, nh_link);
     304        return node->fs_handle == tri->fs_handle
     305                && node->service_id == tri->service_id
     306                && node->index == tri->index;
     307}
     308
     309static inline vfs_triplet_t node_triplet(vfs_node_t *node)
     310{
     311        vfs_triplet_t tri = {
     312                .fs_handle = node->fs_handle,
     313                .service_id = node->service_id,
     314                .index = node->index
     315        };
     316       
     317        return tri;
     318}
     319
    317320/**
    318321 * @}
Note: See TracChangeset for help on using the changeset viewer.