Changeset bc216a0 in mainline for uspace/srv/fs/exfat/exfat_idx.c


Ignore:
Timestamp:
2012-08-07T22:13:44Z (12 years ago)
Author:
Adam Hraska <adam.hraska+hos@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
da68871a
Parents:
b17518e
Message:

Refactored any users of hash_table to use opaque void* keys instead of the cumbersome unsigned long[] keys. Switched from the ad hoc computations of hashes of multiple values to hash_combine().

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    rb17518e rbc216a0  
    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_SID_KEY     0
    115 #define UPH_PFC_KEY     1
    116 #define UPH_PDI_KEY     2
    117 
    118 static size_t pos_key_hash(unsigned long key[])
    119 {
    120         /* Inspired by Effective Java, 2nd edition. */
    121         size_t hash = 17;
    122        
    123         hash = 31 * hash + key[UPH_PFC_KEY];
    124         hash = 31 * hash + key[UPH_PDI_KEY];
    125         hash = 31 * hash + key[UPH_SID_KEY];
    126        
    127         return hash;
    128 }
    129 
    130 static size_t pos_hash(const link_t *item)
    131 {
    132         exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uph_link);
    133        
    134         unsigned long pkey[] = {
    135                 [UPH_SID_KEY] = fidx->service_id,
    136                 [UPH_PFC_KEY] = fidx->pfc,
    137                 [UPH_PDI_KEY] = fidx->pdi,
    138         };
    139        
    140         return pos_key_hash(pkey);
    141 }
    142 
    143 static bool pos_match(unsigned long key[], size_t keys, const link_t *item)
    144 {
    145         service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
     116typedef struct {
     117        service_id_t service_id;
    146118        exfat_cluster_t pfc;
    147119        unsigned pdi;
    148         exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uph_link);
    149 
    150         switch (keys) {
    151         case 1:
    152                 return (service_id == fidx->service_id);
    153         case 3:
    154                 pfc = (exfat_cluster_t) key[UPH_PFC_KEY];
    155                 pdi = (unsigned) key[UPH_PDI_KEY];
    156                 return (service_id == fidx->service_id) && (pfc == fidx->pfc) &&
    157                     (pdi == fidx->pdi);
    158         default:
    159                 assert((keys == 1) || (keys == 3));
    160         }
    161 
    162         return 0;
     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;
    163152}
    164153
    … …  
    166155        .hash = pos_hash,
    167156        .key_hash = pos_key_hash,
    168         .match = pos_match,
     157        .key_equal = pos_key_equal,
    169158        .equal = 0,
    170159        .remove_callback = 0,
    … …  
    177166static hash_table_t ui_hash;
    178167
    179 #define UIH_SID_KEY     0
    180 #define UIH_INDEX_KEY   1
    181 
    182 static size_t idx_key_hash(unsigned long key[])
    183 {
    184         service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
    185         fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
    186 
    187         /*
    188          * Compute a simple hash unlimited by specific table size as per:
    189          * Effective Java, 2nd edition.
    190          */
    191         size_t hash = 17;
    192         hash = 31 * hash + (size_t)service_id;
    193         hash = 31 * hash + (size_t)index;
    194         return hash;
    195 }
    196 
    197 static size_t idx_hash(const link_t *item)
    198 {
    199         exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uih_link);
    200        
    201         unsigned long ikey[] = {
    202                 [UIH_SID_KEY] = fidx->service_id,
    203                 [UIH_INDEX_KEY] = fidx->index,
    204         };
    205 
    206         return idx_key_hash(ikey);
    207 }
    208 
    209 static bool idx_match(unsigned long key[], size_t keys, const 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         exfat_idx_t *fidx = list_get_instance(item, exfat_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         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);
    232196
    233197        free(fidx);
    … …  
    237201        .hash = idx_hash,
    238202        .key_hash = idx_key_hash,
    239         .match = idx_match,
     203        .key_equal = idx_key_equal,
    240204        .equal = 0,
    241205        .remove_callback = idx_remove_callback,
    … …  
    379343        }
    380344               
    381         link_initialize(&fidx->uph_link);
    382         link_initialize(&fidx->uih_link);
    383345        fibril_mutex_initialize(&fidx->lock);
    384346        fidx->service_id = service_id;
    … …  
    415377{
    416378        exfat_idx_t *fidx;
    417         link_t *l;
    418         unsigned long pkey[] = {
    419                 [UPH_SID_KEY] = service_id,
    420                 [UPH_PFC_KEY] = pfc,
    421                 [UPH_PDI_KEY] = pdi,
     379       
     380        pos_key_t pos_key = {
     381                .service_id = service_id,
     382                .pfc = pfc,
     383                .pdi = pdi,
    422384        };
    423385
    424386        fibril_mutex_lock(&used_lock);
    425         l = hash_table_find(&up_hash, pkey);
     387        ht_link_t *l = hash_table_find(&up_hash, &pos_key);
    426388        if (l) {
    427                 fidx = hash_table_get_instance(l, exfat_idx_t, uph_link);
     389                fidx = hash_table_get_inst(l, exfat_idx_t, uph_link);
    428390        } else {
    429391                int rc;
    … …  
    456418void exfat_idx_hashout(exfat_idx_t *idx)
    457419{
    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_remove(&up_hash, pkey, 3);
     420        fibril_mutex_lock(&used_lock);
     421        hash_table_remove_item(&up_hash, &idx->uph_link);
    466422        fibril_mutex_unlock(&used_lock);
    467423}
    … …  
    471427{
    472428        exfat_idx_t *fidx = NULL;
    473         link_t *l;
    474         unsigned long ikey[] = {
    475                 [UIH_SID_KEY] = service_id,
    476                 [UIH_INDEX_KEY] = index,
     429
     430        idx_key_t idx_key = {
     431                .service_id = service_id,
     432                .index = index,
    477433        };
    478434
    479435        fibril_mutex_lock(&used_lock);
    480         l = hash_table_find(&ui_hash, ikey);
     436        ht_link_t *l = hash_table_find(&ui_hash, &idx_key);
    481437        if (l) {
    482                 fidx = hash_table_get_instance(l, exfat_idx_t, uih_link);
     438                fidx = hash_table_get_inst(l, exfat_idx_t, uih_link);
    483439                fibril_mutex_lock(&fidx->lock);
    484440        }
    … …  
    494450void exfat_idx_destroy(exfat_idx_t *idx)
    495451{
    496         unsigned long ikey[] = {
    497                 [UIH_SID_KEY] = idx->service_id,
    498                 [UIH_INDEX_KEY] = idx->index,
     452        idx_key_t idx_key = {
     453                .service_id = idx->service_id,
     454                .index = idx->index,
    499455        };
    500         service_id_t service_id = idx->service_id;
    501         fs_index_t index = idx->index;
    502456
    503457        /* TODO: assert(idx->pfc == FAT_CLST_RES0); */
    … …  
    510464         * the index hash only.
    511465         */
    512         hash_table_remove(&ui_hash, ikey, 2);
     466        hash_table_remove(&ui_hash, &idx_key);
    513467        fibril_mutex_unlock(&used_lock);
    514468        /* Release the VFS index. */
    515         exfat_index_free(service_id, index);
     469        exfat_index_free(idx_key.service_id, idx_key.index);
    516470        /* The index structure itself is freed in idx_remove_callback(). */
    517471}
    … …  
    519473int exfat_idx_init(void)
    520474{
    521         if (!hash_table_create(&up_hash, 0, 3, &uph_ops))
     475        if (!hash_table_create(&up_hash, 0, 0, &uph_ops))
    522476                return ENOMEM;
    523         if (!hash_table_create(&ui_hash, 0, 2, &uih_ops)) {
     477        if (!hash_table_create(&ui_hash, 0, 0, &uih_ops)) {
    524478                hash_table_destroy(&up_hash);
    525479                return ENOMEM;
    … …  
    531485{
    532486        /* We assume the hash tables are empty. */
     487        assert(hash_table_empty(&up_hash) && hash_table_empty(&ui_hash));
    533488        hash_table_destroy(&up_hash);
    534489        hash_table_destroy(&ui_hash);
    … …  
    555510}
    556511
     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
    557536void exfat_idx_fini_by_service_id(service_id_t service_id)
    558537{
    559         unsigned long ikey[] = {
    560                 [UIH_SID_KEY] = service_id
    561         };
    562         unsigned long pkey[] = {
    563                 [UPH_SID_KEY] = service_id
    564         };
    565 
    566538        /*
    567539         * Remove this instance's index structure from up_hash and ui_hash.
    … …  
    570542         */
    571543        fibril_mutex_lock(&used_lock);
    572         hash_table_remove(&up_hash, pkey, 1);
    573         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);
    574546        fibril_mutex_unlock(&used_lock);
    575547
Note: See TracChangeset for help on using the changeset viewer.