Changeset 9f4067b6 in mainline for uspace/srv/fs/fat/fat_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/fat/fat_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>
    … …  
    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 = NULL,
     159        .remove_callback = NULL,
    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 = NULL,
    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
Note: See TracChangeset for help on using the changeset viewer.