Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r4e00f87 rebddd71  
    4141#include <str.h>
    4242#include <adt/hash_table.h>
    43 #include <adt/hash.h>
    4443#include <adt/list.h>
    4544#include <assert.h>
    … …  
    5958 */
    6059typedef struct {
    61         link_t link;
    62         service_id_t service_id;
     60        link_t          link;
     61        service_id_t    service_id;
    6362
    6463        /** Next unassigned index. */
    … …  
    9897                        return u;
    9998        }
    100 
     99       
    101100        if (lock)
    102101                fibril_mutex_unlock(&unused_lock);
    … …  
    114113static hash_table_t up_hash;
    115114
    116 typedef struct {
    117         service_id_t service_id;
     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
     122static 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
     150static 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];
    118153        fat_cluster_t pfc;
    119154        unsigned pdi;
    120 } pos_key_t;
    121 
    122 static 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 
    131 static 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 
    144 static 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 
    154 static hash_table_ops_t uph_ops = {
     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
     172static void pos_remove_callback(link_t *item)
     173{
     174        /* nothing to do */
     175}
     176
     177static hash_table_operations_t uph_ops = {
    155178        .hash = pos_hash,
    156         .key_hash = pos_key_hash,
    157         .key_equal = pos_key_equal,
    158         .equal = NULL,
    159         .remove_callback = NULL,
     179        .compare = pos_compare,
     180        .remove_callback = pos_remove_callback,
    160181};
    161182
    … …  
    166187static hash_table_t ui_hash;
    167188
    168 typedef struct {
    169         service_id_t service_id;
     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
     195static 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
     209static 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];
    170212        fs_index_t index;
    171 } idx_key_t;
    172 
    173 static 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 
    179 static 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 
    185 static 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 
    193 static void idx_remove_callback(ht_link_t *item)
    194 {
    195         fat_idx_t *fidx = hash_table_get_inst(item, fat_idx_t, uih_link);
     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
     229static void idx_remove_callback(link_t *item)
     230{
     231        fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
    196232
    197233        free(fidx);
    198234}
    199235
    200 static hash_table_ops_t uih_ops = {
     236static hash_table_operations_t uih_ops = {
    201237        .hash = idx_hash,
    202         .key_hash = idx_key_hash,
    203         .key_equal = idx_key_equal,
    204         .equal = NULL,
     238        .compare = idx_compare,
    205239        .remove_callback = idx_remove_callback,
    206240};
    … …  
    343377        }
    344378               
     379        link_initialize(&fidx->uph_link);
     380        link_initialize(&fidx->uih_link);
    345381        fibril_mutex_initialize(&fidx->lock);
    346382        fidx->service_id = service_id;
    … …  
    365401        }
    366402               
    367         hash_table_insert(&ui_hash, &fidx->uih_link);
     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);
    368409        fibril_mutex_lock(&fidx->lock);
    369410        fibril_mutex_unlock(&used_lock);
    … …  
    377418{
    378419        fat_idx_t *fidx;
    379 
    380         pos_key_t pos_key = {
    381                 .service_id = service_id,
    382                 .pfc = pfc,
    383                 .pdi = pdi,
     420        link_t *l;
     421        unsigned long pkey[] = {
     422                [UPH_SID_KEY] = service_id,
     423                [UPH_PFC_KEY] = pfc,
     424                [UPH_PDI_KEY] = pdi,
    384425        };
    385426
    386427        fibril_mutex_lock(&used_lock);
    387         ht_link_t *l = hash_table_find(&up_hash, &pos_key);
     428        l = hash_table_find(&up_hash, pkey);
    388429        if (l) {
    389                 fidx = hash_table_get_inst(l, fat_idx_t, uph_link);
     430                fidx = hash_table_get_instance(l, fat_idx_t, uph_link);
    390431        } else {
    391432                int rc;
    … …  
    397438                }
    398439               
     440                unsigned long ikey[] = {
     441                        [UIH_SID_KEY] = service_id,
     442                        [UIH_INDEX_KEY] = fidx->index,
     443                };
     444       
    399445                fidx->pfc = pfc;
    400446                fidx->pdi = pdi;
    401447
    402                 hash_table_insert(&up_hash, &fidx->uph_link);
    403                 hash_table_insert(&ui_hash, &fidx->uih_link);
     448                hash_table_insert(&up_hash, pkey, &fidx->uph_link);
     449                hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
    404450        }
    405451        fibril_mutex_lock(&fidx->lock);
    … …  
    411457void fat_idx_hashin(fat_idx_t *idx)
    412458{
     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
    413465        fibril_mutex_lock(&used_lock);
    414         hash_table_insert(&up_hash, &idx->uph_link);
     466        hash_table_insert(&up_hash, pkey, &idx->uph_link);
    415467        fibril_mutex_unlock(&used_lock);
    416468}
    … …  
    418470void fat_idx_hashout(fat_idx_t *idx)
    419471{
     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
    420478        fibril_mutex_lock(&used_lock);
    421         hash_table_remove_item(&up_hash, &idx->uph_link);
     479        hash_table_remove(&up_hash, pkey, 3);
    422480        fibril_mutex_unlock(&used_lock);
    423481}
    … …  
    427485{
    428486        fat_idx_t *fidx = NULL;
    429 
    430         idx_key_t idx_key = {
    431                 .service_id = service_id,
    432                 .index = index,
     487        link_t *l;
     488        unsigned long ikey[] = {
     489                [UIH_SID_KEY] = service_id,
     490                [UIH_INDEX_KEY] = index,
    433491        };
    434492
    435493        fibril_mutex_lock(&used_lock);
    436         ht_link_t *l = hash_table_find(&ui_hash, &idx_key);
     494        l = hash_table_find(&ui_hash, ikey);
    437495        if (l) {
    438                 fidx = hash_table_get_inst(l, fat_idx_t, uih_link);
     496                fidx = hash_table_get_instance(l, fat_idx_t, uih_link);
    439497                fibril_mutex_lock(&fidx->lock);
    440498        }
    … …  
    450508void fat_idx_destroy(fat_idx_t *idx)
    451509{
    452         idx_key_t idx_key = {
    453                 .service_id = idx->service_id,
    454                 .index = idx->index,
    455         };
     510        unsigned long ikey[] = {
     511                [UIH_SID_KEY] = idx->service_id,
     512                [UIH_INDEX_KEY] = idx->index,
     513        };
     514        service_id_t service_id = idx->service_id;
     515        fs_index_t index = idx->index;
    456516
    457517        assert(idx->pfc == FAT_CLST_RES0);
    … …  
    463523         * the index hash only.
    464524         */
    465         hash_table_remove(&ui_hash, &idx_key);
     525        hash_table_remove(&ui_hash, ikey, 2);
    466526        fibril_mutex_unlock(&used_lock);
    467527        /* Release the VFS index. */
    468         fat_index_free(idx_key.service_id, idx_key.index);
     528        fat_index_free(service_id, index);
    469529        /* The index structure itself is freed in idx_remove_callback(). */
    470530}
    … …  
    472532int fat_idx_init(void)
    473533{
    474         if (!hash_table_create(&up_hash, 0, 0, &uph_ops))
     534        if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))
    475535                return ENOMEM;
    476         if (!hash_table_create(&ui_hash, 0, 0, &uih_ops)) {
     536        if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
    477537                hash_table_destroy(&up_hash);
    478538                return ENOMEM;
    … …  
    484544{
    485545        /* We assume the hash tables are empty. */
    486         assert(hash_table_empty(&up_hash) && hash_table_empty(&ui_hash));
    487546        hash_table_destroy(&up_hash);
    488547        hash_table_destroy(&ui_hash);
    … …  
    509568}
    510569
    511 static 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 
    523 static 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 
    535570void fat_idx_fini_by_service_id(service_id_t service_id)
    536571{
     572        unsigned long ikey[] = {
     573                [UIH_SID_KEY] = service_id
     574        };
     575        unsigned long pkey[] = {
     576                [UPH_SID_KEY] = service_id
     577        };
     578
    537579        /*
    538580         * Remove this instance's index structure from up_hash and ui_hash.
    … …  
    541583         */
    542584        fibril_mutex_lock(&used_lock);
    543         hash_table_apply(&up_hash, rm_pos_service_id, &service_id);
    544         hash_table_apply(&ui_hash, rm_idx_service_id, &service_id);
     585        hash_table_remove(&up_hash, pkey, 1);
     586        hash_table_remove(&ui_hash, ikey, 1);
    545587        fibril_mutex_unlock(&used_lock);
    546588
Note: See TracChangeset for help on using the changeset viewer.