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


Ignore:
Timestamp:
2012-10-09T21:16:13Z (12 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
6659037, 7d248e3
Parents:
d1ef4a1 (diff), 97b199b1 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge from lp:~jakub/helenos/gsoc2012-uspace-hash-table-from-adam.

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    rd1ef4a1 r9f4067b6  
    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 = NULL,
     159        .remove_callback = NULL,
    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 = NULL,
    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
Note: See TracChangeset for help on using the changeset viewer.