Changeset bc216a0 in mainline for uspace/srv/fs/fat/fat_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/fat/fat_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>
    4546#include <fibril_synch.h>
    4647#include <malloc.h>
    47 
    4848
    4949/** Each instance of this type describes one interval of freed VFS indices. */
    … …  
    5959 */
    6060typedef struct {
    61         link_t          link;
    62         service_id_t    service_id;
     61        link_t link;
     62        service_id_t service_id;
    6363
    6464        /** Next unassigned index. */
    … …  
    9898                        return u;
    9999        }
    100        
     100
    101101        if (lock)
    102102                fibril_mutex_unlock(&unused_lock);
    … …  
    114114static hash_table_t up_hash;
    115115
    116 #define UPH_SID_KEY     0
    117 #define UPH_PFC_KEY     1
    118 #define UPH_PDI_KEY     2
    119 
    120 static size_t pos_key_hash(unsigned long key[])
    121 {
    122         /* Inspired by Effective Java, 2nd edition. */
    123         size_t hash = 17;
    124        
    125         hash = 31 * hash + key[UPH_PFC_KEY];
    126         hash = 31 * hash + key[UPH_PDI_KEY];
    127         hash = 31 * hash + key[UPH_SID_KEY];
    128        
    129         return hash;
    130 }
    131 
    132 static size_t pos_hash(const link_t *item)
    133 {
    134         fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link);
    135        
    136         unsigned long pkey[] = {
    137                 [UPH_SID_KEY] = fidx->service_id,
    138                 [UPH_PFC_KEY] = fidx->pfc,
    139                 [UPH_PDI_KEY] = fidx->pdi,
    140         };
    141        
    142         return pos_key_hash(pkey);
    143 }
    144 
    145 static bool pos_match(unsigned long key[], size_t keys, const link_t *item)
    146 {
    147         service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
     116typedef struct {
     117        service_id_t service_id;
    148118        fat_cluster_t pfc;
    149119        unsigned pdi;
    150         fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link);
    151 
    152         switch (keys) {
    153         case 1:
    154                 return (service_id == fidx->service_id);
    155         case 3:
    156                 pfc = (fat_cluster_t) key[UPH_PFC_KEY];
    157                 pdi = (unsigned) key[UPH_PDI_KEY];
    158                 return (service_id == fidx->service_id) && (pfc == fidx->pfc) &&
    159                     (pdi == fidx->pdi);
    160         default:
    161                 assert((keys == 1) || (keys == 3));
    162         }
    163 
    164         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        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;
    165152}
    166153
    … …  
    168155        .hash = pos_hash,
    169156        .key_hash = pos_key_hash,
    170         .match = pos_match,
     157        .key_equal = pos_key_equal,
    171158        .equal = 0,
    172159        .remove_callback = 0,
    … …  
    179166static hash_table_t ui_hash;
    180167
    181 #define UIH_SID_KEY     0
    182 #define UIH_INDEX_KEY   1
    183 
    184 static size_t idx_key_hash(unsigned long key[])
    185 {
    186         /*
    187          * Compute a simple hash unlimited by specific table size as per:
    188          * Effective Java, 2nd edition.
    189          */
    190         size_t hash = 17;
    191         hash = 31 * hash + key[UIH_SID_KEY];
    192         hash = 31 * hash + key[UIH_INDEX_KEY];
    193         return hash;
    194 }
    195 
    196 static size_t idx_hash(const link_t *item)
    197 {
    198         fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
    199        
    200         unsigned long ikey[] = {
    201                 [UIH_SID_KEY] = fidx->service_id,
    202                 [UIH_INDEX_KEY] = fidx->index,
    203         };
    204 
    205         return idx_key_hash(ikey);
    206 }
    207 
    208 static bool idx_match(unsigned long key[], size_t keys, const 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         fat_idx_t *fidx = list_get_instance(item, fat_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         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);
    231196
    232197        free(fidx);
    … …  
    236201        .hash = idx_hash,
    237202        .key_hash = idx_key_hash,
    238         .match = idx_match,
     203        .key_equal = idx_key_equal,
    239204        .equal = 0,
    240205        .remove_callback = idx_remove_callback,
    … …  
    378343        }
    379344               
    380         link_initialize(&fidx->uph_link);
    381         link_initialize(&fidx->uih_link);
    382345        fibril_mutex_initialize(&fidx->lock);
    383346        fidx->service_id = service_id;
    … …  
    414377{
    415378        fat_idx_t *fidx;
    416         link_t *l;
    417         unsigned long pkey[] = {
    418                 [UPH_SID_KEY] = service_id,
    419                 [UPH_PFC_KEY] = pfc,
    420                 [UPH_PDI_KEY] = pdi,
     379
     380        pos_key_t pos_key = {
     381                .service_id = service_id,
     382                .pfc = pfc,
     383                .pdi = pdi,
    421384        };
    422385
    423386        fibril_mutex_lock(&used_lock);
    424         l = hash_table_find(&up_hash, pkey);
     387        ht_link_t *l = hash_table_find(&up_hash, &pos_key);
    425388        if (l) {
    426                 fidx = hash_table_get_instance(l, fat_idx_t, uph_link);
     389                fidx = hash_table_get_inst(l, fat_idx_t, uph_link);
    427390        } else {
    428391                int rc;
    … …  
    464427{
    465428        fat_idx_t *fidx = NULL;
    466         link_t *l;
    467         unsigned long ikey[] = {
    468                 [UIH_SID_KEY] = service_id,
    469                 [UIH_INDEX_KEY] = index,
     429
     430        idx_key_t idx_key = {
     431                .service_id = service_id,
     432                .index = index,
    470433        };
    471434
    472435        fibril_mutex_lock(&used_lock);
    473         l = hash_table_find(&ui_hash, ikey);
     436        ht_link_t *l = hash_table_find(&ui_hash, &idx_key);
    474437        if (l) {
    475                 fidx = hash_table_get_instance(l, fat_idx_t, uih_link);
     438                fidx = hash_table_get_inst(l, fat_idx_t, uih_link);
    476439                fibril_mutex_lock(&fidx->lock);
    477440        }
    … …  
    487450void fat_idx_destroy(fat_idx_t *idx)
    488451{
    489         unsigned long ikey[] = {
    490                 [UIH_SID_KEY] = idx->service_id,
    491                 [UIH_INDEX_KEY] = idx->index,
     452        idx_key_t idx_key = {
     453                .service_id = idx->service_id,
     454                .index = idx->index,
    492455        };
    493         service_id_t service_id = idx->service_id;
    494         fs_index_t index = idx->index;
    495456
    496457        assert(idx->pfc == FAT_CLST_RES0);
    … …  
    502463         * the index hash only.
    503464         */
    504         hash_table_remove(&ui_hash, ikey, 2);
     465        hash_table_remove(&ui_hash, &idx_key);
    505466        fibril_mutex_unlock(&used_lock);
    506467        /* Release the VFS index. */
    507         fat_index_free(service_id, index);
     468        fat_index_free(idx_key.service_id, idx_key.index);
    508469        /* The index structure itself is freed in idx_remove_callback(). */
    509470}
    … …  
    511472int fat_idx_init(void)
    512473{
    513         if (!hash_table_create(&up_hash, 0, 3, &uph_ops))
     474        if (!hash_table_create(&up_hash, 0, 0, &uph_ops))
    514475                return ENOMEM;
    515         if (!hash_table_create(&ui_hash, 0, 2, &uih_ops)) {
     476        if (!hash_table_create(&ui_hash, 0, 0, &uih_ops)) {
    516477                hash_table_destroy(&up_hash);
    517478                return ENOMEM;
    … …  
    523484{
    524485        /* We assume the hash tables are empty. */
     486        assert(hash_table_empty(&up_hash) && hash_table_empty(&ui_hash));
    525487        hash_table_destroy(&up_hash);
    526488        hash_table_destroy(&ui_hash);
    … …  
    547509}
    548510
     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
    549535void fat_idx_fini_by_service_id(service_id_t service_id)
    550536{
    551         unsigned long ikey[] = {
    552                 [UIH_SID_KEY] = service_id
    553         };
    554         unsigned long pkey[] = {
    555                 [UPH_SID_KEY] = service_id
    556         };
    557 
    558537        /*
    559538         * Remove this instance's index structure from up_hash and ui_hash.
    … …  
    562541         */
    563542        fibril_mutex_lock(&used_lock);
    564         hash_table_remove(&up_hash, pkey, 1);
    565         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);
    566545        fibril_mutex_unlock(&used_lock);
    567546
Note: See TracChangeset for help on using the changeset viewer.